7.8.2 Quadtree Generation and Computations

Bentley, J.L., Stanat, D.F.,
Analysis of Range Searches in Quad Trees,
IPL(3), No. 6, July 1975, pp. 170-173. BibRef 7507

Lee, D.T., Wong, C.K.,
Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Search Trees and Quad Trees,
Acta Inf.(9), No. 1, 1977, pp. 23-29. BibRef 7700

Hunter, G.M., Steiglitz, K.,
Operations on Images Using Quad Trees,
PAMI(1), No. 2, April 1979, pp. 145-153. BibRef 7904
Earlier: PRAI-78(184). BibRef

Hunter, G.M., Steiglitz, K.,
Linear Transformation of Pictures Represented by Quad Trees,
CGIP(10), No. 3, July 1979, pp. 289-296.
Elsevier DOI BibRef 7907

Samet, H.[Hanan],
An Algorithm for Converting Rasters to Quadtrees,
PAMI(3), No. 1, January 1981, pp. 93-95. BibRef 8101

Samet, H.[Hanan],
Algorithms for the Conversion of Quadtrees to Rasters,
CVGIP(26), No. 1, April 1984, pp. 1-16.
Elsevier DOI BibRef 8404

Samet, H.[Hanan],
Reconstruction of Quadtrees from Quadtree Medial Axis Transforms,
CVGIP(29), No. 3, 1985, pp. 311-328.
Elsevier DOI BibRef 8500

Shaffer, C.A.[Clifford A.], Samet, H.[Hanan],
Optimal Quadtree Construction Algorithms,
CVGIP(37), No. 3, March 1987, pp. 402-419.
Elsevier DOI BibRef 8703
And:
An Optimal Quadtree Construction Algorithm,
ICPR86(317-319). BibRef

Shaffer, C.A.[Clifford A.], Samet, H.[Hanan],
Set Operations for Unaligned Linear Quadtrees,
CVGIP(50), No. 1, April 1990, pp. 29-49.
Elsevier DOI Minimized the nodes for union and intersection operations. BibRef 9004

Samet, H.[Hanan], Shaffer, C.A.[Clifford A.],
A Model for the Analysis of Neighbor Finding in Pointer Based Quadtrees,
PAMI(7), No. 6, November 1985, pp. 717-720. Refined the model for neighbor finding to show it was not as bad as the earlier numbers did. BibRef 8511

Samet, H.[Hanan],
Neighbor Finding Techniques for Images Represented by Quadtrees,
CGIP(18), No. 1, January 1982, pp. 37-57.
Elsevier DOI BibRef 8201
Earlier:
Neighbor Finding in Quadtrees,
PRIP81(68-74). BibRef

Samet, H.[Hanan],
Neighbor Finding in Images Represented by Octrees,
CVGIP(46), No. 3, June 1989, pp. 367-386.
Elsevier DOI BibRef 8906

Samet, H.[Hanan], Shaffer, C.A.[Clifford A.], Nelson, R.C., Huang, Y.G., Fujimura, K., Rosenfeld, A.,
Recent Developments in Linear Quadtree-Based Geographic Information Systems,
IVC(5), No. 3, August 1987, pp. 187-197.
Elsevier DOI BibRef 8708

Vaishnavi, V.[Vijay], Wood, D.[Derick],
Data Structures for the Rectangle Containment and Enclosure Problems,
CGIP(13), No. 4, August 1980, pp. 372-384.
Elsevier DOI Segment Tree description for geometric objects. BibRef 8008

Li, M.[Ming], Grosky, W.I.[William I.], Jain, R.C.[Ramesh C.],
Normalized Quadtrees with Respect to Translations,
CGIP(20), No. 1, September 1982, pp. 72-81.
Elsevier DOI BibRef 8209
And: PRIP81(60-62). BibRef

Grosky, W.I.[William I.], Jain, R.C.[Ramesh C.],
Optimal Quadtrees for Image Segments,
PAMI(5), No. 1, January 1983, pp. 77-83. BibRef 8301

Oliver, M.A., Wiseman, N.E.,
Operations on Quadtree-Encoded Images,
Computer Journal(26), No. 1, February 1983, pp. 83-91. BibRef 8302
And:
Operations on Quadtree Leaves and Related Image Areas,
Computer Journal(26), No. 4, November 1983, pp. 375-380. BibRef

Mark, D.M., Abel, D.J.,
Linear Quadtrees from Vector Representations of Polygons,
PAMI(7), No. 3, May 1985, pp. 344-349. BibRef 8505

Chaudhuri, B.B.,
Applications of Quadtree, Octree, and Binary Tree Decomposition Techniques to Shape Analysis and Pattern Recognition,
PAMI(7), No. 6, November 1985, pp. 652-661. BibRef 8511

Bauer, M.A.[Michael A.],
Set Operations on Linear Quadtrees,
CVGIP(29), No. 2, February 1985, pp. 248-258.
Elsevier DOI BibRef 8502

Lauzon, J.P.[Jean Paul], Mark, D.M.[David M.], Kikuchi, L.[Lawrence], Guevara, J.A.[J. Armando],
Two-Dimensional Run-Encoding for Quadtree Representation,
CVGIP(30), No. 1, April 1985, pp. 56-69.
Elsevier DOI Run Length Code. BibRef 8504

Peters, F.J.[Frans J.],
An Algorithm for Transformations of Pictures by Quadtrees,
CVGIP(32), No. 3, December 1985, pp. 397-403.
Elsevier DOI Translation, scaling, and rotations. BibRef 8512

Ravindran, S., Manohar, M.,
Algorithm For Converting A Forest Of Quadtrees To A Binary Array,
IVC(5), No. 4, November 1987, pp. 297-300.
Elsevier DOI BibRef 8711

Li, S.X.[Shu-Xiang], Loew, M.H.[Murray H.],
The Quadcode and Its Arithmetic,
CACM(30), No. 7, July 1987, pp. 621-626. The code is a direct representation of the image, not exactly a quadtree. BibRef 8707

van Lierop, M.L.P.[Marloes L.P.],
Geometrical Transformations on Pictures Represented by Leafcodes,
CVGIP(33), No. 1, January 1986, pp. 81-98.
Elsevier DOI BibRef 8601

Walsh, T.R.,
Efficient Axis-Translation of Binary Digital Pictures by Blocks in Linear Quadtree Representation,
CVGIP(41), No. 3, March 1988, pp. 282-292.
Elsevier DOI BibRef 8803

Bhaskar, S.K., Rosenfeld, A.[Azriel], Wu, A.Y.[Angela Y.],
Parallel Processing of Regions Represented by Linear Quadtrees,
CVGIP(42), No. 3, June 1988, pp. 371-380.
Elsevier DOI BibRef 8806

Wu, A.Y.[Angela Y.], Bhaskar, S.K., Rosenfeld, A.[Azriel],
Parallel Processing of Region Boundaries,
PR(22), No. 2, 1989, pp. 165-172.
Elsevier DOI BibRef 8900

Wu, A.Y.[Angela Y.], Rosenfeld, A.[Azriel],
Parallel processing of encoded bit strings,
PR(21), No. 6, 1988, pp. 559-565.
Elsevier DOI 0309
BibRef

Gao, P.[Peng], Smith, T.R.[Terence R.],
Space Efficient Hierarchical Structures: Relatively Addressed Compact Quadtrees for GISs,
IVC(7), No. 3, August 1989, pp. 173-177.
Elsevier DOI GIS. BibRef 8908

Holroyd, F.C., Mason, D.C.,
Efficient Linear Quadtree Construction Algorithm,
IVC(8), No. 3, August 1990, pp. 218-224.
Elsevier DOI BibRef 9008

Shaffer, C.A.[Clifford A.], Stout, Q.F.[Quentin F.],
Linear Time Distance Transforms for Quadtrees,
CVGIP(54), No. 2, September 1991, pp. 215-223.
Elsevier DOI Compute the chessboard distance for both pointer and linear quadtrees. BibRef 9109

Lattanzi, M.R.[Mark R.], Shaffer, C.A.[Clifford A.],
An Optimal Boundary to Quadtree Conversion Algorithm,
CVGIP(53), No. 3, May 1991, pp. 303-312.
Elsevier DOI This uses the linear quadtree rather than the pointer quadtree, create the linear quadtree nodes for the boundary, then fill in the interior. BibRef 9105

Shaffer, C.A.[Clifford A.],
A Formula for Computing the Number of Quadtree Node Fragments Created by a Shift,
PRL(7), 1988, pp. 45-49. BibRef 8800

Schrack, G.[Günther],
Finding Neighbors of Equal Size in Linear Quadtrees and Octrees in Constant Time,
CVGIP(55), No. 3, May 1992, pp. 221-230.
Elsevier DOI Constant time algorithm in linear quadtrees. BibRef 9205

Kasif, S.,
Optimal Parallel Algorithms for Quadtree Problems,
CVGIP(59), No. 3, May 1994, pp. 281-285.
DOI Link BibRef 9405

Dehne, F., Rauchaplin, A., Ferreira, A.G.,
Hypercube Algorithms for Parallel-Processing of Pointer-Based Quadtrees,
CVIU(62), No. 1, July 1995, pp. 1-10.
DOI Link BibRef 9507

Schrack, G.F.[Günther F.], Gargantini, I.[Irene],
Mirroring and Rotating Images in Linear Quadtree Form with Few Machine Instructions,
IVC(11), No. 2, March 1993, pp. 112-118.
Elsevier DOI BibRef 9303

Wilke, L.M.[Lars M.], Schrack, G.F.[Günther F.],
Improved Mirroring And Rotation Functions For Linear Quadtree Leaves,
IVC(13), No. 6, August 1995, pp. 491-495.
Elsevier DOI BibRef 9508

Shusterman, E., Feder, M.,
Image compression via improved quadtree decomposition algorithms,
IP(3), No. 2, March 1994, pp. 207-215.
IEEE DOI 0402
BibRef

Vassilakopoulos, M., Manolopoulos, Y., Economou, K.,
Overlapping Quadtrees for the Representation of Similar Images,
IVC(11), No. 5, June 1993, pp. 257-262.
Elsevier DOI BibRef 9306

Manolopoulos, Y., Nardelli, E., Proietti, G., Vassilakopoulos, M.,
On the Creation of Quadtrees by Using a Branching-Process,
IVC(14), No. 2, March 1996, pp. 159-164.
Elsevier DOI 9607
BibRef

Lee, S.S.[Shung-Shing], Horng, S.J.[Shi-Jinn], Tsai, H.R.[Horng-Ren], Tsai, S.S.[Shun-Shan],
Building a Quadtree and Its Applications on a Reconfigurable Mesh,
PR(29), No. 9, September 1996, pp. 1571-1579.
Elsevier DOI Parallel Algorithms. Reconfigurable Mesh. BibRef 9609

Ziavras, S.G.[Sotirios G.], Alexandridis, N.A.[Nikitas A.],
Improved Algorithms for Translation of Pictures Represented by Leaf Codes,
IVC(6), No. 1, February 1988, pp. 13-20.
Elsevier DOI BibRef 8802

Faloutsos, C.,
Analytical Results on the Quadtree Decomposition of Arbitrary Rectangles,
PRL(13), 1992, pp. 31-40. BibRef 9200

Webber, R.E., Dillencourt, M.B.,
Compressing Quadtrees Via Common Subtree Merging,
PRL(9), 1989, pp. 193-200. BibRef 8900

Menon, S., Gao, P., Smith, T.R.,
Multi-Colored Quadtrees for GIS: Exploiting Bit-Parallelism for Rapid Boolean Overlay,
PRL(8), 1988, pp. 171-179. BibRef 8800

Schreiber, F.A., Wolfler, R.C.,
Use of Neural Networks to Estimate the Number of Nodes of an Edge Quadtree,
GMIP(59), No. 2, March 1997, pp. 61-72. 9704
BibRef

Lin, T.W.[Tsong-Wuu],
Set Operations on Constant Bit-Length Linear Quadtrees,
PR(30), No. 7, July 1997, pp. 1239-1249.
Elsevier DOI 9707
BibRef

Chen, P.M.[Pei-Min],
A Quadtree Normalization Scheme Based on Cyclic Translations,
PR(30), No. 12, December 1997, pp. 2053-2064.
Elsevier DOI 9805
BibRef

Sarkar, D.[Debranjan], Gupta, N.[Nishit],
Operations on binary images represented by interpolation based bintrees,
PRL(20), No. 4, April 1999, pp. 395-403. BibRef 9904

Tsai, Y.H.[Yao-Hong], Chung, K.L.[Kuo-Liang],
Some image operations on S-tree-related spatial data structures,
IVC(17), No. 12, October 1999, pp. 897-904.
Elsevier DOI BibRef 9910

Laferte, J.M., Perez, P., Heitz, F.,
Discrete Markov Image Modeling and Inference on the Quadtree,
IP(9), No. 3, March 2000, pp. 390-404.
IEEE DOI 0003
BibRef

Laferte, J.M., Heitz, F., Perez, P.,
A Multiresolution EM Algorithm for Unsupervised Image Classification Using a Quadtree Model,
ICPR96(II: 849-853).
IEEE DOI 9608
(IRISA/INRIA, F) BibRef

Ito, A., Inoue, K., Wang, Y.,
Decomposition Principle for Analyzing Region Quadtrees,
PRAI(13), No. 4, June 1999, pp. 555. 0005
BibRef

Aizawa, K., Nakamura, A.,
Quadtree Adjoining Grammar,
PRAI(13), No. 4, June 1999, pp. 573. 0005
BibRef

Ewert, S., van der Walt, A.,
A Hierarchy Result for Random Forbidding Context Picture Grammars,
PRAI(13), No. 7, November 1999, pp. 997. 0005
BibRef

Racherla, G.[Gopal], Radhakrishnan, S.[Sridhar], Oommen, B.J.[B. John],
Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects,
PR(35), No. 10, October 2002, pp. 2303-2309.
Elsevier DOI 0206
Extension to allow for real time implementations. I.e. no sorting to insert/delete. BibRef

Chan, Y.K.[Yung-Kuan],
Block image retrieval based on a compressed linear quadtree,
IVC(22), No. 5, 1 May 2004, pp. 391-397.
Elsevier DOI 0403
BibRef

Leelapatra, W.[Watis], Kanchanasut, K.[Kanchana], Lursinsap, C.[Chidchanok],
Displacement BDD and geometric transformations of binary decision diagram encoded images,
PRL(29), No. 4, 1 March 2008, pp. 438-456.
Elsevier DOI 0711
Binary decision diagram; Transition branch; Translation; Rotation BibRef

Kumar, B.P.[B. Praveen], Gupta, P.[Phalguni], Hwang, C.J.,
An Efficient Quadtree Datastructure For Neighbor Finding Algorithm,
IJIG(1), No. 4, October 2001, pp. 619-633. 0110
BibRef

Aizawa, K.[Kunio], Tanaka, S.[Shojiro],
A Constant-Time Algorithm for Finding Neighbors in Quadtrees,
PAMI(31), No. 7, July 2009, pp. 1178-1183.
IEEE DOI 0905
Find neighbors in quadtree. BibRef

Mathew, R.K.[Reji K.], Taubman, D.S.[David S.],
Quad-Tree Motion Modeling With Leaf Merging,
CirSysVideo(20), No. 10, October 2010, pp. 1331-1345.
IEEE DOI 1011
BibRef
And:
Joint motion and geometry modeling with quad-tree leaf merging,
ICIP08(2872-2875).
IEEE DOI 0810
BibRef
Earlier:
Motion Modeling with Geometry and Quad-tree Leaf Merging,
ICIP07(II: 297-300).
IEEE DOI 0709
BibRef
Earlier:
Hierarchical and Polynomial Motion Modeling with Quad-Tree Leaf Merging,
ICIP06(1881-1884).
IEEE DOI 0610
BibRef

Mathew, R.K.[Reji K.], Taubman, D.S.[David S.],
Scalable Modeling of Motion and Boundary Geometry With Quad-Tree Node Merging,
CirSysVideo(21), No. 2, February 2011, pp. 178-192.
IEEE DOI 1103
BibRef
Earlier:
Joint scalable modeling of motion and boundary geometry with quad-tree node merging,
ICIP09(3745-3748).
IEEE DOI 0911
BibRef

Mathew, R.K.[Reji K.], Taubman, D.S.[David S.], Zanuttigh, P.,
Scalable Coding of Depth Maps With R-D Optimized Embedding,
IP(22), No. 5, May 2013, pp. 1982-1995.
IEEE DOI 1304
BibRef

Kim, H.Y.[Hong-Yeon], Kang, S.[Sungmin], Lee, S.[Seokjoo], Min, J.K.[Jun-Ki],
The Efficient Algorithms for Constructing Enhanced Quadtrees Using MapReduce,
IEICE(E99-D), No. 4, April 2016, pp. 918-926.
WWW Link. 1604
BibRef

Scholefield, A.[Adam], Dragotti, P.L.[Pier Luigi],
Image restoration using a sparse quadtree decomposition representation,
ICIP09(1473-1476).
IEEE DOI 0911
BibRef

Holt, K.M., Neuhoff, D.L.,
Strategies for quadtree predictive image coding,
ICIP03(II: 247-250).
IEEE DOI 0312
BibRef

Teng, C.Y.[Chia-Yuan], Neuhoff, D.L.,
A new quadtree predictive image coder,
ICIP95(II: 73-76).
IEEE DOI 9510
BibRef

Lee, M.[Michael], Samet, H.[Hanan],
Navigating through Triangle Meshes Implemented as Linear Quadtrees,
UMD--TR3900, April 1998
WWW Link. BibRef 9804

Ogniewicz, R.L.,
Sekeleton-Space: a Multiscale Shape Description Combining Region and Boundary Information,
CVPR94(746-751).
IEEE DOI BibRef 9400

Kummert, Á.[Ágnes], Kabos, S.[Sándor],
Calculation and estimation of sample statistics of binary images using quadtree data representations,
CAIP93(58-64).
Springer DOI 9309
BibRef

Fan, N.P., Li, C.C.,
Computing Quadtree Medial Axis Transform by a Multi-Layered Pyramid of Lisp-Processor Arrays,
CVPR88(628-634).
IEEE DOI BibRef 8800

Punys, J.,
Hierarchical 2D shape representation and compression by rectangles,
ICPR88(II: 675-677).
IEEE DOI 8811
BibRef

Chapter on 2-D Feature Analysis, Extraction and Representations, Shape, Skeletons, Texture continues in
Quadtree Boundary Operations .