Extended algorithm to construct a quadtree from Freeman chain code in four directions

Authors

  • Andrej Nerat University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Damjan Strnad University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Eva Zupančič University of Maribor, Faculty of Electrical Engineering and Computer Science
  • Borut Žalik University of Maribor, Faculty of Electrical Engineering and Computer Science

DOI:

https://doi.org/10.5566/ias.2095

Keywords:

chain code, quadtree, chain code to quadtree conversion, space filling curve, Z-order curve

Abstract

This paper introduces improvements to the algorithm that was proposed in 2001 by Chen and Chen. The algorithm constructs a quadtree directly from Freeman chain code in four directions. We have improved the algorithm in two ways: Firstly, a time efficient solution using the space filling Z-order curve is proposed for a self-intersection case that was not considered by Chen and Chen. Secondly, the algorithm is expanded to handle geometric objects containing holes. The computational efficiency of the extended algorithm was confirmed by the experiments.

References

Anand S, Knott K (1991). An algorithm for converting the boundary representation of a CAD model to its octree representation. COMPUT IND ENG 21:343 – 7.

Bader M (2012). Space-filling curves: an introduction with applications in scientific computing, vol. 9. Springer Science & Business Media.

Bribiesca E (1999). A new chain code. PATTERN RECOGN 32:235 – 51.

Bribiesca E, Bribiesca-Contreras F, Ángel Carrillo-Bermejo, Bribiesca-Correa G, Hevia-Montiel N (2019). A chain code for representing high definition contour shapes. J VIS COMMUN IMAGE R 61:93 – 104.

Bribiesca E, Bribiesca-Contreras G (2014). 2d tree object representation via the slope chain code. PATTERN RECOGN 47:3242 – 53.

Chen Z, Chen IP (2001). A simple recursive method for converting a chain code into a quadtree with a lookup table. IMAGE VISION COMPUT 19:413–26.

Finkel RA, Bentley JL (1974). Quad trees: a data structure for retrieval on composite keys. ACTA INFORM 4:1–9.

Freeman H (1961). On the encoding of arbitrary geometric configurations. IEEE T COMPUT EC-10:260 – 8.

Hoffmann CM (1989). Geometric and Solid Modeling: An Introduction. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Krishnan R, Das A, Gurumoorthy B (1996). Octree encoding of B-rep based objects. COMPUT GRAPH 20:107 – 14. Computer Graphics in Singapore.

Lattanzi M, Shaffer C (1991). An optimal boundary to quadtree conversion algorithm. CVGIP IMAG UNDERSTAN 53:303–12.

Lemus E, Bribiesca E, Garduño E (2014). Representation of enclosing surfaces from simple voxelized objects by means of a chain code. PATTERN RECOGN 47:1721 – 30.

Mäntylä M (1987). An Introduction to Solid Modeling. New York, NY, USA: Computer Science Press, Inc.

Mark D, Abel D (1985). Linear quadtrees from vector representations of polygons. IEEE T PATTERN ANAL PAMI-7:344–9.

Mortensen ME (1985). Geometric Modeling. New York, NY, USA: John Wiley & Sons, Inc.

Sagan H (1994). Lebesgue’s Space-Filling Curve. New York, NY: Springer New York, 69–83.

Sagan H (2012). Space-filling curves. Springer Science & Business Media.

Samet H (1980). Region representation: quadtree from chain codes. COMMUN ACM 23:163–70.

Shih FY, Wong WT (2001). An adaptive algorithm for conversion from quadtree to chain codes. PATTERN RECOGN 34:631 – 9.

Sánchez-Cruz H, López-Valdez HH, Cuevas FJ (2014). A new relative chain code in 3d. PATTERN RECOGN 47:769 – 88.

Sánchez-Cruz H, Rodrı́guez-Dagnino RM (2005). Compressing bilevel images by means of a three-bit chain code. OPT ENG 44:1–8.

Žalik B, Mongus D, Žalik KR, Lukač N (2016). Chain code compression using string transformation techniques. DIGIT SIGNAL PROCESS 53:1–10.

Webber R (1984). Analysis of Quadtree Algorithms. Ph.D. thesis, Computer Science Department, University of Maryland, College Park, MD.

Žalik B, Mongus D, Liu YK, Lukač N (2016). Unsigned Manhattan chain code. J VIS COMMUN IMAGE R 38:186 – 94.

Žalik B, Mongus D, Lukač N, Žalik KR (2018). Efficient chain code compression with interpolative coding. INFORM SCIENCES 439/440:39–49.

Žalik B, Mongus D, Žalik KR, Lukač N (2017). Boolean operations on rasterized shapes represented by chain codes using space filling curves. J VIS COMMUN IMAGE R 49:420–32.

Downloads

Published

2019-12-13

How to Cite

Nerat, A., Strnad, D., Zupančič, E., & Žalik, B. (2019). Extended algorithm to construct a quadtree from Freeman chain code in four directions. Image Analysis and Stereology, 38(3), 227–235. https://doi.org/10.5566/ias.2095

Issue

Vol. 38 No. 3 (2019)

Section

Original Research Paper

License

Copyright (c) 2019 Image Analysis & Stereology

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.