Abstract
Visibility partitions play an important role in computer vision and pattern matching. This paper studies a new type of visibility, reflection-visibility, with applications in affine pattern matching: it is used in the definition of the reflection metric between two patterns consisting of line segments. This metric is affine invariant, and robust against noise, deformation, blurring, and cracks. We present algorithms that compute the reflection visibility partition in O((n+k) log(n)+v) randomised time, where k is the number of visibility edges (at most O(n 2)), and v is the number of vertices in the partition (at most O(n 2 +k 2). We use this partition to compute the reflection metric in O(r(n A + n B )) randomised time, for two line segment unions, with n A and n B line segments, separately, where r is the complexity of the overlay of two reflection-visibility partitions (at most O(nA 4 + nB 4)).
supported by Philips Research
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. K. Agarwal and M. Sharir. On the number of views of polyhedral terrains. Discrete & Computational Geometry, 12:177–182, 1994. 359
B. Aronov, L. J. Guibas, M. Teichmann, and L. Zhang. Visibility queries in simple polygons and applications. In ISAAC, pages 357–366, 1998. 359
T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai. Visibility of disjoint polygons. Algorithmica, 1:49–63, 1986. 359, 361
P. Bose, A. Lubiw, and I. Munro. Efficient visibility queries in simple polygons. In 4th Canadian Conference on Computational Geometry, 1992. To appear in International Journal of Computational Geometry and Applications. 359
K. W. Bowyer and C. R. Dyer. Aspect graphs: An introduction and survey of recent results. Int. J. of Imaging Systems and Technology, 2:315–328, 1990. 359
I. Chakravarty and H. Freeman. Characteristic views as a basis for threedimensional object recognition. In Proc. SPIE: Robot Vision, pages 37–45, 1982. 358
M. de Berg, D. Halperin, M. H. Overmars, and M. van Kreveld. Sparse arrangements and the number of views of polyhedral scenes. Int. J. Computational Geometry & Applications, 7(3):175–195, 1997. 359
H. Everett. Visibility graph recognition. PhD thesis, Department of Computer Science, University of Toronto, 1990. 359
S. K. Ghosh. On recognizing and characterizing visibility graphs of simple polygons. Discrete & Computational Geometry, 17(2):143–162, 1997. 359
S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing, 20:888–910, 1991. 364
Z. Gigus, J. Canny, and R. Seidel. Efficiently computing and representing aspect graphs of polyhedral objects. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13:542–551, 1991. 359
N. Grimal, J. Hallof, and D. van der Plas. Hieroglyphica, sign list. http://www.ccer.theo.uu.nl/hiero/hiero.html, 1993. 360
L. J. Guibas, Rajeev Motwani, and Prabhakar Raghavan. The robot localisation problem. SIAM J. Computing, 26(4), 1997. 359
M. Hagedoorn. Pattern matching using similarity measures PhD thesis, Department of Computer Science, Utrecht University, ISBN90-393-2460-3, 2000. 359
M. Hagedoorn, M. H. Overmars, and R. C. Veltkamp. New visibility partitions with applications in affine pattern matching. Technical Report UU-CS-1999-21, Utrecht University, Padualaan 14, 3584 CH Utrecht, the Netherlands, July 1999. http://www.cs.uu.nl/docs/research/publication/TechRep.html. 364, 365, 367
M. Hagedoorn and R. C. Veltkamp. Measuring resemblance of complex patterns. In L. Perroton G. Bertrand, M. Couprie, editor, Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science 1568, pages 286–298, 1999. Springer. 359, 367
D. J. Kriegman and J. Ponce. Computing exact aspect graphs of curved objects: Solids of revolution. ACM Symp. Computational Geometry, 5:119–135, 1990. 359
D. T. Lee. Proximity and Reachability in the plane. PhD thesis, University of Illinois at Urbana-Champaign, 1978. 358
Y. Lin and S. S. Skiena. Complexity aspects of visibility graphs. International Journal of Computational Geometry and Applications, 5:289–312, 1995. 359
K. Mulmuley. Computational Geometry: An introduction through randomized algorithms. Prentice Hall, 1994. 361, 364
W. H. Plantinga and C. R. Dyer. Visibility, occlusion and the aspect graph. ACM Symp. Computational Geometry, 5(2):137–160, 1990. 359
M. Pocchiola and G. Vegter. Topologically sweeping visibility complexes via pseudotriangulations. Discrete & Computational Geometry, 16(4):419–453, 1996. 359, 364
E. Welzl. Constructing the visibility graph for n-line segments in O(n2) time. Inform. Process. Lett., 20:167–171, 1985. 359
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hagedoorn, M., Overmars, M., Veltkamp, R.C. (2000). A New Visibility Partition for Affine Pattern Matching. In: Borgefors, G., Nyström, I., di Baja, G.S. (eds) Discrete Geometry for Computer Imagery. DGCI 2000. Lecture Notes in Computer Science, vol 1953. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44438-6_30
Download citation
DOI: https://doi.org/10.1007/3-540-44438-6_30
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41396-7
Online ISBN: 978-3-540-44438-1
eBook Packages: Springer Book Archive
