Efficient processing of quadtree data

Details Efficient processing of quadtree data Efficient processing of quadtree data

1999-10-21

2003-02-25

Chang, Jon (Department: 2623)

Image analysis

Image compression or coding

Pyramid, hierarchy, or tree structure

Reexamination Certificate

active

06526176

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to data processing and, more particularly, to processing of data having a quadtree topology.
The quadtree is a data structure that is widely used in image processing, computer graphics, data compression, and other applications. The quadtree can be viewed as a tree in which each node has at most four children.
FIG. 1
illustrates an image where each picture area can be divided into four parts, and each resulting area can be recursively divided to thus yield areas of, effectively, any desired small size. It should be kept in mind that although the following discussion illustratively speaks in terms of an image, which is a 2-dimensional object, the principles disclosed herein apply to a much broader range of useful applications.
To efficiently process the
FIG. 1
image, it might be advantageous to subdivide the image into large areas in portions of the image that change little, and to subdivide the image into small areas in portions of the image that change a lot. The same situation exists in topographical rendering problems, where the topography of a three-dimensional surface (e.g., a hill, a face, a dress) is represented in triangles, and each node of the quadtree stores 8 triangle surfaces oriented in 3-D space.
In processing data that is represented in a quadtree data structure and stored in memory, it is often necessary to traverse the quadtree. Traversing from a child node to the immediately previous parent node is quite simple. Traversing from a child node to an earlier ancestor node is slightly more difficult and more time consuming, but still quite easy. Traversing from some arbitrary node at some level to another arbitrary node in another level, where there is no direct connection between the nodes except by traversing a number of levels up the quadtree, can become quite time consuming. To move to a same-level neighbor in the quadtree can actually require the use of significant processing resources just to find out how to reach that neighbor node (i.e., how high up the tree one needs to traverse, and which branches down one must select).
Prior art attempts at solving this problem are reported on by a number of researchers. In “Finding neighbors of equal size in linear quadtrees and octrees in constant time,”
CVGIP: Image Understanding
, 55(3):221-230, May 1992, G. Schrack shows how to travel between neighbor nodes in the quadtree (located at the same level). However, the Schrack method is limited to accessing neighbor nodes. In “Navigating through meshes implemented as linear quadtrees,”
Technical Report, Computer Science Dept., Center for Automation Research, University of Maryland
, CS-TR-3900, April, 1998, Samet et al show how to store a particular class of triangulations in a quadtree and how to assign to each triangle a binary index (vector of 0's and 1's) so that neighbor triangles at the same level and neighbors located at a different level can be accessed in constant time. However, the Semet et al method implies storing an explicit index in each quadtree node, which increases the storage requirements and exacerbates what is a critical issue with a linear quadtree.
Further, both works restrict the quadtree traversal to neighbor nodes. Thus, the known art has not solved the general problem of efficiently traversing from one node to any other arbitrary node.
SUMMARY OF THE INVENTION
The deficiencies in the prior art are overcome and a technical advance is realized with a simple, algorithmic, indexing of the quadtree nodes. The indexing is arranged to insure that the index value of a node in column i and row j differs from the index value of a node in row k and column i by a value that is constant, regardless of the value of row j. Similarly, the index value of a node in row j and column i differs from the index value of a node in row k and column i by a value that is a constant, regardless of the value of column i. With such an arrangement, no indexing information, or pointer information, needs to be stored. Moreover, traversal from any node to any other node can be accomplished with a single calculation followed by a single traversal which, in the context of this disclosure, is considered to be a single step.


REFERENCES:
patent: 5228098 (1993-07-01), Crinon et al.
patent: 6356665 (2002-03-01), Lei et al.
Gargantini. “An Effective Way to Represent Quadtrees.” Communications of the ACM, vol. 25, No. 12, Dec. 1982, pp. 905-910.*
Samet. “The Quadtree and Related Hierarchical Data Structures.” Computing Surveys. vol. 16, No. 2, Jun. 1984, pp. 187-260.*
Clarke. Digital Compression of Still Images and Video. Academic Press, 1995, pp. 195-205.*
Zemanek. “Parallel Set Operations with Visual Data.” Proc. of the 22nd EUROMICRO Conference, EUROMICRO 96, Beyond 2000: Hardware and Software Design Strategies, Sep. 1996, pp. 529-536.*
Seetharaman et al. “Image Processing in a Tree of Peano Coded Images.” Proc. fourth IEEE Int. Workshop on Computer Architecture for Machine Perception, Oct. 1997, pp. 229-234.*
Gaede et al. “Multidimensional Access Methods.” ACM Computing Surveys, vol. 30, No. 2, Jun. 1998, pp. 170-231.*
Samet et al,Technical Report, Computer Science Dept., Center for Automation Research, University of Maryland,CS-TR-3900, Apr., 1998.

Affiliated with

Also associated with

Rating

Efficient processing of quadtree data does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient processing of quadtree data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient processing of quadtree data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3179843