Abstract
The robust detection of lines and arcs in scanned documents or technical drawings is an important problem in document image understanding. We present a new solution to this problem that works directly on run-length encoded data. The method finds globally optimal solutions to parameterized thick line and arc models. Line thickness is part of the model and directly used during the matching process. Unlike previous approaches, it does not require any thinning or other preprocessing steps, no computation of the line adjacency graphs, and no heuristics. Furthermore, the only search-related parameter that needs to be specified is the desired numerical accuracy of the solution. The method is based on a branch-and-bound approach for the globally optimal detection of these geometric primitives using runs of black pixels in a bi-level image. We present qualitative and quantitative results of the algorithm on images used in the 2003 and 2005 GREC arc segmentation contests.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Elliman, D.: Tif2vec, an algorithm for arc segmentation in engineering drawings. In: Blostein, D., Kwon, Y.-B. (eds.) GREC 2001. LNCS, vol. 2390, pp. 350–359. Springer, Heidelberg (2002)
Wenyin, L.: Report of the arc segmentation contest. In: Lladós, J., Kwon, Y.-B. (eds.) GREC 2003. LNCS, vol. 3088, pp. 364–367. Springer, Heidelberg (2004)
Wenyin, L., Zhai, J., Dori, D.: Extended summary of the arc segmentation contest. In: Blostein, D., Kwon, Y.-B. (eds.) GREC 2001. LNCS, vol. 2390, pp. 343–349. Springer, Heidelberg (2002)
Duda, R.O., Hart, P.E.: Use of the Hough transformation to detect lines and curves in pictures. Communications of the ACM 15, 11–15 (1972)
Wenyin, L., Dori, D.: From raster to vectors: Extracting visual information from line drawings. Pattern Analysis and Applications 2, 10–21 (1999)
Dori, D., Wenyin, L.: Sparse pixel vectorization: An algorithm and its performance evaluation. IEEE Trans. Pattern Analysis Machine Intelligence 21, 202–215 (1999)
Dosch, P., Masini, G., Tombre, K.: Improving arc detection in graphics reognition. In: International Conference on Pattern Recongition, Barcelona, Spain, vol. 2, pp. 2243–2246 (2000)
Hilaire, X.: RANVEC and the arc segmentation contest. In: Blostein, D., Kwon, Y.-B. (eds.) GREC 2001. LNCS, vol. 2390, pp. 359–364. Springer, Heidelberg (2002)
Breuel, T.M.: Fast recognition using adaptive subdivisions of transformation space. In: Proceedings IEEE Conf. on Computer Vision and Pattern Recognition, pp. 445–451 (1992)
Breuel, T.M.: On the use of interval arithmetic in geometric branch-and-bound algorithms. Pattern Recognition Letters 24, 1375–1384 (2003)
Breuel, T.M.: Robust least square baseline finding using a branch and bound algorithm. In: Proceedings of the SPIE - The International Society for Optical Engineering, pp. 20–27 (2002)
Hagedoorn, M., Veltkamp, R.C.: Reliable and efficient pattern matching using an affine invariant metric. International Journal of Computer Vision 31, 203–225 (1999)
Huttenlocher, D.P., Klanderman, G.A., Rucklidge, W.J.: Comparing images using the Hausdorff distance. IEEE Transactions on Pattern Analysis and Machine Intelligence 15, 850–863 (1993)
Jurie, F.: Solution of the simultaneous pose and correspondence problem using Gaussian error model. Computer Vision and Image Understanding 73, 357–373 (1999)
Mount, D.M., Netanyahu, N.S., Moigne, J.L.: Efficient algorithms for robust feature matching. Pattern Recognition 32, 17–38 (1999)
Olson, C.F.: Locating geometric primitives by pruning the parameter space. Pattern Recognition 34, 1247–1256 (2001)
Pavlidis, T.: Algorithms for Graphics and Image Processing. W. H. Freeman & Co., New York (1983)
Forsyth, D.A., Ponce, J.: Computer Vision: A Modern Approach. Prentice Hall, Upper Saddle River (2003)
Breuel, T.M.: Finding lines under bounded error. Pattern Recognition 29, 167–178 (1996)
Hickey, T.J., Ju, Q., van Emden, M.H.: Interval arithmetic: From principles to implementation. JACM 48, 1038–1068 (2001)
Jaulin, L., Kieffer, M., Didrit, O., Walter, E.: Applied Interval Analysis. Springer, Berlin (2001)
Breuel, T.M.: Representations and metrics for off-line handwriting segmentation. In: 8th International Workshop on Frontiers in Handwriting Recognition (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Keysers, D., Breuel, T.M. (2006). Optimal Line and Arc Detection on Run-Length Representations. In: Liu, W., Lladós, J. (eds) Graphics Recognition. Ten Years Review and Future Perspectives. GREC 2005. Lecture Notes in Computer Science, vol 3926. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11767978_34
Download citation
DOI: https://doi.org/10.1007/11767978_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34711-8
Online ISBN: 978-3-540-34712-5
eBook Packages: Computer ScienceComputer Science (R0)