On the Farey sequence and its augmentation for applications to image analysis

Pratihar, S. ; Bhowmick, P.

International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 3, pp. 637-658.

Résumé

We introduce a novel concept of the augmented Farey table (AFT). Its purpose is to store the ranks of fractions of a Farey sequence in an efficient manner so as to return the rank of any query fraction in constant time. As a result, computations on the digital plane can be crafted down to simple integer operations; for example, the tasks like determining the extent of collinearity of integer points or of parallelism of straight lines—often required to solve many image-analytic problems—can be made fast and efficient through an appropriate AFT-based tool. We derive certain interesting characterizations of an AFT for its efficient generation. We also show how, for a fraction not present in a Farey sequence, the rank of the nearest fraction in that sequence can efficiently be obtained by the regula falsi method from the AFT concerned. To assert its merit, we show its use in two applications—one in polygonal approximation of digital curves and the other in skew correction of engineering drawings in document images. Experimental results indicate the potential of the AFT in such image-analytic applications.

Détail

Keywords: Farey sequence, Farey table, fraction rank, theory of fractions, image analysis
Mots-clés : sekwencja Fareya, rząd frakcji, analiza obrazu

Bibliographie

[1] Amin, A. and Fischer, S. (2000). A document skew detection method using the Hough transform, Pattern Analysis and Applications 3(3): 243–253.

[2] Attneave, F. (1954). Some informational aspects of visual perception, Psychological Review 61(3): 183–193.

[3] Bhowmick, P. and Bhattacharya, B.B. (2007). Fast polygonal approximation of digital curves using relaxed straightness properties, IEEE Transactions on Pattern Analysis and Machine Intelligence 29(9): 1590–1602.

[4] Buzer, L. (2009). Optimal simplification of polygonal chains for subpixel-accurate rendering, Computational Geometry 42(1): 45–59.

[5] Cao, Y., Wang, S. and Li, H. (2003). Skew detection and correction in document images based on straight-line fitting, Pattern Recognition Letters 24(12): 1871–1879.

[6] Charrier, E. and Buzer, L. (2009). Approximating a real number by a rational number with a limited denominator: A geometric approach, Discrete Applied Mathematics 157(16): 3473–3484.

[7] Chaudhuri, B.B. and Pal, U. (1997). Skew angle detection of digitized Indian script documents, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(2): 182–186.

[8] Chou, C., Chu, S. and Chang, F. (2007). Estimation of skew angles for scanned documents based on piecewise covering by parallelograms, Pattern Recognition 40(2): 443–455.

[9] Chung, K.L., Liao, P.H. and Chang, J.M. (2008). Novel efficient two-pass algorithm for closed polygonal approximation based on LISE and curvature constraint criteria, Journal of Visual Communication and Image Representation 19(4): 219–230.

[10] Cormen, T.H., Leiserson, C.E. and Rivest, R.L. (2000). Introduction to Algorithms, Prentice Hall of India, New-Delhi.

[11] Das, A.K. and Chanda, B. (2001). A fast algorithm for skew detection of document images using morphology, International Journal on Document Analysis and Recognition 4(2): 109–114.

[12] Das, S., Halder, K., Pratihar, S. and Bhowmick, P. (2010). Properties of Farey sequence and their applications to digital image processing, 4th International Conference on Information Processing, Bangalore, India, pp. 71–81.

[13] Devaney, R.L. (1999). The Mandelbrot set, the Farey tree, and the Fibonacci sequence, The American Mathematical Monthly 106(04): 289–302.

[14] Dinesh, R. and Guru, D.S. (2009). Non-parametric adaptive approach for the detection of dominant points on boundary curves based on non-symmetric region of support, International Journal of Image and Graphics 9(4): 541–557.

[15] Graham, R., Knuth, D. and Patashnik, O. (1994). Concrete Mathematics, Addison-Wesley, London.

[16] Hardy, G.H. and Wright, E.M. (1968). An Introduction to the Theory of Numbers, Oxford University Press, New York, NY.

[17] Hinds, S., Fisher, J. and D’Amato, D.P. (1990). A document skew detection method using run length encoding and the Hough transform, Proceedings of the International Conference on Pattern Recognition, Los Alamitos, CA, USA, pp. 464–468.

[18] Hu, H. and Yan, H. (1997). Polygonal approximation of digital curves based on the principles of perceptual organization, Pattern Recognition 30(5): 701–718.

[19] Jiang, H.-F., Han, C.-C. and Fan, K.-C. (1997). A fast approach to the detection and correction of skew documents, Pattern Recognition Letters 18(7): 675–686.

[20] Klette, R. and Rosenfeld, A. (2004). Digital Geometry: Geometric Methods for Digital Picture Analysis, Morgan Kaufmann, San Francisco, CA.

[21] Knuth, D. E. (1997). The Art of Computer Programming, Vol. 2, 3rd Edn., Addison-Wesley, Boston, MA.

[22] Koutroumbas, K.D. (2012). Piecewise linear curve approximation using graph theory and geometrical concepts, IEEE Transactions on Image Processing 21(9): 3877–3887.

[23] Kumar, M.P., Goyal, S., Jawahar, C.V. and Narayanan, P.J. (2002). Polygonal approximation of closed curves across multiple views, 3rd Indian Conference on Computer Vision, Graphics and Image Processing, Ahmadabad, India, pp. 317–322.

[24] Le, D.S., Thoma, G.R. andWechsler, H. (1994). Automatic page orientation and skew angle detection for binary document images, Pattern Recognition 27(10): 1325–1344.

[25] Li, S., Shen, Q. and Sun, J. (2007). Skew detection using wavelet decomposition and projection profile analysis, Pattern Recognition Letters 28(5): 555–562.

[26] Liu, H., Latecki, L. and Liu, W. (2008). A unified curvature definition for regular, polygonal, and digital planar curves, International Journal of Computer Vision 80(1): 104–124.

[27] Manjunath, V.N., Kumar, G.H. and Shivakumara, P. (2006). Skew detection technique for binary document images based on Hough transform, International Journal of Information and Communication Engineering 3(7): 493–499.

[28] Masood, A. (2008). Dominant point detection by reverse polygonization of digital curves, Image and Vision Computing 26(5): 702–715.

[29] Melkman, A. and O’Rourke, J. (1988). On polygonal chain approximation, in G.T. Toussaint (Ed.), Computational Morphology, North-Holland, Amsterdam, pp. 87–95.

[30] Mikolajczyk, K. and Schmid, C. (2005). A performance evaluation of local descriptors, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(10): 1615–1630.

[31] Mokhtarian, F. and Mohanna, F. (2002). Content-based video database retrieval through robust corner tracking, IEEE Workshop on Multimedia Signal Processing, St. Thomas, Virgin Islands, USA, pp. 224–228.

[32] Neumann, R. and Teisseron, G. (2002). Extraction of dominant points by estimation of the contour fluctuations, Pattern Recognition 35(7): 1447–1462.

[33] Neville, E.H. (1950). The Farey Series of Order 1025, Cambridge University Press, Cambridge.

[34] Nguyen, T.P. and Debled-Rennesson, I. (2011). A discrete geometry approach for dominant point detection, Pattern Recognition 44(1): 32–44.

[35] Nikiel, S. (2007). A proposition of mobile fractal image decompression, International Journal of Applied Mathematics and Computer Science 17(1): 129–136, DOI: 10.2478/v10006-007-0012-5.

[36] O’Connell, K.J. (1997). Object-adaptive vertex based shape coding method, IEEE Transactions on Circuits and Systems for Video Technology 7(1): 251–255.

[37] Parvez, M.T. and Mahmoud, S.A. (2010). Polygonal approximation of digital planar curves through adaptive optimizations, Pattern Recognition Letters 31(13): 1997–2005.

[38] Pătraşcu, C.E. and Pătraşcu, M. (2004). Computing order statistics in the Farey sequence, Symposium on Algorithmic Number Theory, Burlington, VT, USA, pp. 358–366.

[39] Pavlidis, T. and Zhou, J. (1991). Page segmentation by white streams, International Conference on Document Analysis and Recognition, Saint-Malo, France, pp. 945–953.

[40] Pawlewicz, J. and Pătraşcu, M. (2009). Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons, Algorithmica 55(2): 271–282.

[41] Prasad, D.K., Leung, M.K.H., Quek, C. and Cho, S. (2012). A novel framework for making dominant point detection methods non-parametric, Image and Vision Computing 30(11): 843–859.

[42] Pratihar, S. and Bhowmick, P. (2009). A thinning-free algorithm for straight edge detection in a gray-scale image, International Conference on Advances on Pattern Recognition, Kolkata, India, pp. 341–344.

[43] Pratihar, S. and Bhowmick, P. (2010). Vectorization of thick digital lines using Farey sequence and geometric refinement, ICVGIP, Chennai, India, pp. 518–525.

[44] Pratihar, S. and Bhowmick, P. (2011). Skew correction of engineering drawings by digital-geometric analysis of Farey ranks, International Conference on Image Information Processing (ICIIP), Shimla, India, pp. 1–6.

[45] Pratihar, S., Bhowmick, P., Sural, S. and Mukhopadhyay, J. (2013). Skew correction of document images by rank analysis in Farey sequence, International Journal of Pattern Recognition and Artificial Intelligence 27(7): Article ID 1353004.

[46] Ray, B.K. and Ray, K.S. (1992). An algorithm for detection of dominant points and polygonal approximation of digitized curves, Pattern Recognition Letters 13(12): 849–856.

[47] Ray, K.S. and Ray, B.K. (2013). Polygonal approximation of digital curve based on reverse engineering concept, International Journal of Image and Graphics 13(4): Article ID 1350017.

[48] Rosin, P.L. (1997). Techniques for assessing polygonal approximation of curves, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(6): 659–666.

[49] Rosin, P.L. and West, G.A.W. (1988). Detection of circular arcs in images, 4th Alvey Vision Conference, Manchester, UK, pp. 259–263.

[50] Rosin, P.L. and West, G.A.W. (1995). Non-parametric segmentation of curves into various representations, IEEE Transactions on Pattern Analysis and Machine Intelligence 17(12): 1140–1153.

[51] Routledge, N. (2008). Computing Farey series, Mathematical Gazette 92(523): 55–62.

[52] Sarkar, B., Singh, L.K. and Sarkar, D. (2004). A genetic algorithm-based approach for detection of significant vertices for polygonal approximation of digital curves, International Journal of Image and Graphics 4(2): 223–239.

[53] Schroeder, M. (2006). Fractions: Continued, Egyptian and Farey, in M.R. Schroeder (Ed.), Number Theory in Science and Communication, Springer, Berlin/Heidelberg, pp. 55–86.

[54] Singh, C., Bhatia, N. and Kaur, A. (2008). Hough transform based fast skew detection and accurate skew correction methods, Pattern Recognition 41(12): 3528–3546.

[55] Srihari, S.N. and Govindraju, V. (1989). Analysis of textual images using the Hough transform, Machine Vision Applications 2(3): 141–153.

[56] Teh, C.H. and Chin, R.T. (1989). On the detection of dominant points on digital curves, IEEE Transactions on Pattern Analysis and Machine Intelligence 2(8): 859–872.

[57] Van, T.T. and Le, T.M. (2016). Content-based image retrieval using a signature graph and a self-organizing map, International Journal of Applied Mathematics and Computer Science 26(2): 423–438, DOI: 10.1515/amcs-2016-0030.

[58] Wall, K. and Danielsson, P.-E. (1984). A fast sequential method for polygonal approximation of digitized curves, Computer Vision Graphics and Image Processing 28(3): 220–227.

[59] Wang, K., Shi, T., Liao, G. and Xia, Q. (2013). Image registration using a point-line duality based line matching method, Journal of Visual Communication and Image Representation 24(5): 615–626.

[60] Wang, L., Neumann, U. and You, S. (2009). Wide-baseline image matching using line signatures, International Conference on Computer Vision (ICCV), Kyoto, Japan, pp. 1311–1318.

[61] Yan, H. (1993). Skew correction of document images using interline cross-correlation, CVGIP: Graphical Models and Image Processing 55(6): 538–543.

[62] Yin, P.-Y. (2001). Skew detection and block classification of printed documents, Image and Vision Computing 19(8): 567–579.

[63] Yin, P.Y. (2003). Ant colony search algorithms for optimal polygonal approximation of plane curves, Pattern Recognition 36(8): 1783–1797.

[64] Yin, P.Y. (2004). A discrete particle swarm algorithm for optimal polygonal approximation of digital curves, Journal of Visual Communication and Image Representation 15(2): 241–260.

[65] Yu, B. and Jain, A.K. (1996). A robust and fast skew detection algorithm for generic documents, Pattern Recognition 29(10): 1599–1630.

[66] Yuan, B. and Tan, C.L. (2007). Convex hull based skew estimation, Pattern Recognition 40(2): 456–475.

[67] Zhang, L. and Koch, R. (2013). An efficient and robust line segment matching approach based on LBD descriptor and pairwise geometric consistency, Journal of Visual Communication and Image Representation 24(7): 794–805.

[68] Zhang, Q., Wang, Y. and Wang, L. (2015). Registration of images with affine geometric distortion based on maximally stable extremal regions and phase congruency, Image and Vision Computing 36(C): 23–39.