7.8.2 Quadtree Generation and Computations

Chapter Contents (Back)
Quadtree, Features. Region Operations, Quadtree.

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
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
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
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

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.

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

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

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

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

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.

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

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

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

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

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

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

Aizawa, K.[Kunio], Tanaka, S.[Shojiro],
A Constant-Time Algorithm for Finding Neighbors in Quadtrees,
PAMI(31), No. 7, July 2009, pp. 1178-1183.
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.
Joint motion and geometry modeling with quad-tree leaf merging,
Motion Modeling with Geometry and Quad-tree Leaf Merging,
ICIP07(II: 297-300).
Hierarchical and Polynomial Motion Modeling with Quad-Tree Leaf Merging,

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.
Joint scalable modeling of motion and boundary geometry with quad-tree node merging,

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.

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

Banerjee, S.[Srutarshi], Wang, Z.W.[Zihao W.], Chopp, H.H.[Henry H.], Cossairt, O.[Oliver], Katsaggelos, A.K.[Aggelos K.],
Lossy Event Compression Based on Image-Derived Quad Trees and Poisson Disk Sampling,
Image segmentation, Histograms, Visualization, Image coding, Quantization (signal), Lossy Event Compression, Quad tree segmentation BibRef

Scholefield, A.[Adam], Dragotti, P.L.[Pier Luigi],
Image restoration using a sparse quadtree decomposition representation,

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

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

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,
IEEE DOI BibRef 9400

Kummert, Ń.[Ńgnes], Kabos, S.[SŠndor],
Calculation and estimation of sample statistics of binary images using quadtree data representations,
Springer DOI 9309

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

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

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

Last update:Nov 30, 2023 at 15:51:27