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

Wojciech Bieniecki, Sebastian Stoliński


The paper provides a comparison of three variants of algorithms for automatic assessment of some examination 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.


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

Ballard, D.H. (1987). Generalizing the Hough transform to detect arbitrary shapes. In Readings in computer vision (pp. 714-725)

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

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

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)

Davies, E.R. (1989). Finding ellipses using the generalised Hough transform. Pattern Recognition Letters, 9(2), 87-96

Davies, E.R. (1989). Minimising the search space for polygon detection using the generalised Hough transform. Pattern recognition letters, 9(3), 181-192

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

E-ocenianie – electronic assessment. Accessed: 2017-04-11

Fowles, D., Adams, C. (2005). How does assessment differ when e-marking replaces paper-based marking. IAEA paper v3 (cra+ def). doc

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.

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

Gander, W., Golub, G.H., Strebel, R. (1994). Leastsquares fitting of circles and ellipses. BIT Numerical Mathematics, 34(4), 558-578

Illingworth, J., Kittler, J. (1988). A survey of the Hough transform. Computer vision, graphics, and image processing, 44(1), 87-116

Kierkegaard, P. (1992). A method for detection of circular arcs based on the Hough transform. Machine Vision and Applications, 5(4), 249-263

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

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

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

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

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

Otsu, N. (1979). A threshold selection method from gray-level histograms. IEEE transactions on systems, man, and cybernetics, 9(1), 62-66

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

Pao, D., Li, H.F., Jayakumar, R. (1993). A decomposable parameter space for the detection of ellipses. Pattern recognition letters, 14(12), 951-958

Pei, S.C., Horng, J.H. (1995). Circular arc detection based on Hough transform. Pattern recognition letters, 16(6), 615-625

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

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

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

Sim, G., Holifield, P., Brown, M. (2004). Implementation of computer assisted assessment: lessons from the literature. ALT-J, 12(3), 215-229

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

System of external exams. Accessed: 2017-04-11.

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

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)

Thelwall, M. (2000). Computer-based assessment: a versatile educational tool. Computers & Education, 34(1), 37-49

Wiak, S., Szumigaj, K., Wydawnictwo, P.Ł. (2013). System informatyczny zdalnego egzaminowania – strategia, logika systemu, architektura, ewaluacja: (platforma informatyczna e-matura), Politechnika Łódzka

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

Xie, M. (1994). Stereo and motion matching: a Hough-transform inspired method. Pattern recognition letters, 15(11), 1143-1150

Yao, J., Agrawala, M. (2013). Linelens: Automatic data extraction from line charts. In Visualization, UC Berkeley CS 294-10 Fall 2013

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

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


  • There are currently no refbacks.