Identification and Assessment of Selected Handwritten Function Graphs Using Least Square Approximation Combined with General Hough Transform

• Autorzy: Bieniecki W. , Stoliński S.

Identyfikatory

DOI

10.1515/ipc-2017-0019

• Języki publikacji: EN

Abstrakty

EN

The paper provides a comparison of three variants of algorithms for automatic assessment of some xamination tasks involving sketching a function graph based on image processing. Three types of functions have been considered: linear, quadratic, and trigonometric. The assumption adopted in the design of the algorithm is to map the way the examiner assesses the solutions and to achieve the evaluation quality close to the one obtained in manual evaluation. In particular, the algorithm should not reject a partly correct solution and also extract the correct solution from other lines, deletions and corrections made by a student. Essential subproblems to solve in our scheme concern image segmentation, object identification and automatic understanding. We consider several techniques based on Hough Transform, least square fitting and nearest neighbor based classification. The most reliable solution is an algorithm combining least square fitting and Hough Transform.

Słowa kluczowe

EN

computer aided assessment; Generalized Hough Transform; least square approximation; supervised classification

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2017
• Tom: Vol. 22, no. 4
• Strony: 23--42
• Opis fizyczny: Bibliogr. 39 poz., rys.

Twórcy

autor

Bieniecki W.

• Lodz University of Technology, Institute of Applied Computer Science

autor

Stoliński S.

• Lodz University of Technology, Institute of Applied Computer Science

Bibliografia

• [1] Ahn, S.J., Rauh, W., Warnecke, H. J. (2001). Least-squares orthogonal distances fitting of circle, sphere, ellipse, hyperbola, and parabola. Pattern Recognition, 34(12), 2283-2303
• [2] Ballard, D.H. (1987). Generalizing the Hough transform to detect arbitrary shapes. In Readings in computer vision (pp. 714-725)
• [3] Stolinski, S., Bieniecki, W., Stasiak-Bieniecka, M. (2014, September). Computer aided assessment of linear and quadratic function graphs using leastsquares fitting. In Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on (pp. 651-658). IEEE
• [4] Croft, A.C., Danson, M., Dawson, B.R., Ward, J.P. (2001). Experiences of using computer assisted assessment in engineering mathematics. Computers & Education, 37(1), 53-66
• [5] Davies, E.R. (1986). Reduced parameter spaces for polygon detection using the generalized hough transform. In Proc. International Conference on Pattern Recognition (ICPRŠ86) (pp. 495-497)
• [6] Davies, E.R. (1989). Finding ellipses using the generalised Hough transform. Pattern Recognition Letters, 9(2), 87-96
• [7] Davies, E.R. (1989). Minimising the search space for polygon detection using the generalised Hough transform. Pattern recognition letters, 9(3), 181-192
• [8] Duda, R.O., Hart, P.E. (1972). Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM, 15(1), 11-15
• [9] E-ocenianie – electronic assessment. http://eocenianie.pl/. Accessed: 2017-04-11
• [10] Fowles, D., Adams, C. (2005). How does assessment differ when e-marking replaces paper-based marking. IAEA paper v3 (cra+ def). doc
• [11] Fuda, T., Omachi, S., Aso, H. (2007). Recognition of line graph images in documents by tracing connected components. Systems and Computers in Japan, 38(14), 103-114.
• [12] Li, H.F., Pao, D., Jayakumar, R. (1989). Improvements and systolic implementation of the Hough transformation for straight line detection. Pattern Recognition, 22(6), 697-706
• [13] Gander, W., Golub, G.H., Strebel, R. (1994). Leastsquares fitting of circles and ellipses. BIT Numerical Mathematics, 34(4), 558-578
• [14] Illingworth, J., Kittler, J. (1988). A survey of the Hough transform. Computer vision, graphics, and image processing, 44(1), 87-116
• [15] Kierkegaard, P. (1992). A method for detection of circular arcs based on the Hough transform. Machine Vision and Applications, 5(4), 249-263
• [16] Leavers, V.F. (1992). The dynamic generalized Hough transform: its relationship to the probabilistic Hough transforms and an application to the concurrent detection of circles and ellipses. CVGIP: Image understanding, 56(3), 381-398
• [17] Lo, R.C., Tsai, W.H. (1995). Gray-scale Hough transform for thick line detection in gray-scale images. Pattern Recognition, 28(5), 647-661
• [18] Lu, X., Kataria, S., Brouwer, W.J., Wang, J.Z., Mitra, P., Giles, C.L. (2009). Automated analysis of images in documents for intelligent document search. International Journal on Document Analysis and Recognition (IJDAR), 12(2), 65-81
• [19] Mishchenko, A., Vassilieva, N. (2011, September). Chart image understanding and numerical data extraction. In Digital Information Management (ICDIM), 2011 Sixth International Conference on (pp. 115-120). IEEE
• [20] Nair, R.R., Sankaran, N., Nwogu, I., Govindaraju, V. (2015, August). Automated analysis of line plots in documents. In Document Analysis and Recognition (ICDAR), 2015 13th International Conference on (pp. 796-800). IEEE
• [21] Otsu, N. (1979). A threshold selection method from gray-level histograms. IEEE transactions on systems, man, and cybernetics, 9(1), 62-66
• [22] Pao, D., Li, H.F., Jayakumar, R. (1990, June). Detecting parameteric curves using the straight line Hough transform. In Pattern Recognition, 1990. Proceedings., 10th International Conference on (Vol. 1, pp. 620-625). IEEE
• [23] Pao, D., Li, H.F., Jayakumar, R. (1993). A decomposable parameter space for the detection of ellipses. Pattern recognition letters, 14(12), 951-958
• [24] Pei, S.C., Horng, J.H. (1995). Circular arc detection based on Hough transform. Pattern recognition letters, 16(6), 615-625
• [25] Ramos, P.M., Serra, A.C. (2008). A new sine-fitting algorithm for accurate amplitude and phase measurements in two channel acquisition systems. Measurement, 41(2), 135-143
• [26] Sambell, K., Sambell, A., Sexton, G. (1999). Student perceptions of the learning benefits of computer-assisted assessment: A case study in electronic engineering. S. Brown, P. Race, & J. Bull, Computer-assisted assessment in higher education, 179-191
• [27] Savva, M., Kong, N., Chhajta, A., Fei-Fei, L., Agrawala, M., Heer, J. (2011, October). Revision: Automated classification, analysis and redesign of chart images. In Proceedings of the 24th annual ACM symposium on User interface software and technology (pp. 393-402). ACM
• [28] Sim, G., Holifield, P., Brown, M. (2004). Implementation of computer assisted assessment: lessons from the literature. ALT-J, 12(3), 215-229
• [29] Stolinski, S., Bieniecki, W. (2014). Computer aided evaluation of selected examination tasks in mathematics using generalized Hough Transform. In Modelling and Identification Algorithms for Emerging Applications in Data and Signal Processing (pp. 185–199). Wydaw. Politech., Lodz
• [30] System of external exams. https://www.nik.gov.pl/kontrole/P/14/022/. Accessed: 2017-04-11.
• [31] Takagi, N. (2009, October). Mathematical figure recognition for automating production of tactile graphics. In Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on (pp. 4651-4656). IEEE
• [32] Takagi, N. (2012). On consideration of a pattern recognition method for mathematical graphs with broken lines. In International Workshop on Digitization and E-Inclusion in Mathematics and Science (DEIMS 2012), Tokyo (pp. 43-51)
• [33] Thelwall, M. (2000). Computer-based assessment: a versatile educational tool. Computers & Education, 34(1), 37-49
• [34] Wiak, S., Szumigaj, K., Wydawnictwo, P.Ł. (2013). System informatyczny zdalnego egzaminowania – strategia, logika systemu, architektura, ewaluacja: (platforma informatyczna e-matura), Politechnika Łódzka
• [35] Wu, P., Carberry, S., Elzer, S., Chester, D. (2010). Recognizing the intended message of line graphs. In Diagrammatic Representation and Inference (pp. 220-234). Springer, Berlin, Heidelberg
• [36] Xie, M. (1994). Stereo and motion matching: a Hough-transform inspired method. Pattern recognition letters, 15(11), 1143-1150
• [37] Yao, J., Agrawala, M. (2013). Linelens: Automatic data extraction from line charts. In Visualization, UC Berkeley CS 294-10 Fall 2013
• [38] Yuen, H.K., Princen, J., Illingworth, J., Kittler, J. (1990). Comparative study of Hough transform methods for circle finding. Image and vision computing, 8(1), 71-77
• [39] Zorski, W., Foxon, B., Blackledge, J., Turner, M. (1999). Application of the circle Hough transform with a clustering technique to segmentation of digital images. Biuletyn Instytutu Automatyki i Robotyki, 5(10), 69-79.