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

Andrej Nerat; Damjan Strnad; Eva Zupančič; Borut Žalik

doi:10.5566/ias.2095

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, Á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, Garduño E (2014). Representation of enclosing surfaces from simple voxelized objects by means of a chain code. PATTERN RECOGN 47:1721 – 30.

Mäntylä 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.

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

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

Žalik B, Mongus D, Žalik KR, Lukač 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.

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

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

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