Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
2000-05-10
2002-10-08
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
Reexamination Certificate
active
06463180
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention.
This invention relates in general to computer aided design (CAD) systems, and more particularly, to a method, apparatus and article of manufacture for performing spatial index compression through spatial subdivision encoding.
2. Description of Related Art.
Spatial indices are useful in graphical applications such as computer-assisted drafting (CAD), where data has spatial extents and often the user is working with a subset of data defined by a spatial subset of the database extents. In typical CAD applications, the database is saved in a binary file. Since projects are organized and information exchanged through these files, it is beneficial to store data in a compressed form in such a way that access and decoding of the data is efficient as well.
Numerous structures have been proposed to represent spatial data, including an oct-tree and an R-tree, as described in Hanan Samet, “The Design and Analysis of Spatial Data Structures,”
Addison
-
Wesley
, 1990, which is incorporated by reference herein.
Although the oct-tree structure has the benefit of simplicity, there are limitations to the oct-tree:
Objects that lie on partitioning planes end up near the root, even if they are of small extents.
The oct-tree does not handle data that degenerates along a dimension. For example, if the data set consists of buildings of all the same height (Z extent), they will all end up being classified at the root. The oct-tree lacks the ability to adapt to such a situation. A quad-tree would be an appropriate structure for this case.
The R-Tree is object-extent-based, as opposed to global-extent-subdivision-based, as described in A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching,”
Proceedings of the Annual Meeting ACM SIGMOD
, Boston, Mass., 1984, which is incorporated by reference herein.
Although the R-Tree has the advantage of generality, there are also limitations to the R-tree:
Input data distribution can skew the R-tree and make it degenerate fairly easily. For example, if the first object added to the tree spans the database extents, then adding subsequent objects will force the node containing the first large) object to migrate to a greater depth. So the tree will essentially become linear. This sensitivity to input data distribution makes it necessary to introduce additional heuristics in tree creation in order to control degeneracies.
The present invention describes a restricted version of the R-tree that enhances the oct-tree to solve specific limitations of the oct-tree. The present invention solves some oct-tree limitations without permitting the degeneracies possible in the general R-tree. For convenience of notation, this structure is called a Cell tree, where each node in the tree is known as a Cell. A pointer-less representation is used for making the structure persistent.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, apparatus and article of manufacture for reducing the total storage used in representing data having spatial extents. The data is represented in a tree structure having a plurality of nodes, wherein each of the nodes has parent and child relationship to one or more others of the nodes in the tree structure. An encoded representation of the relation of a child node's extents with respect to its parent is stored in the node. A preorder traversal of the tree structure is performed to store it compactly in an output file.
REFERENCES:
patent: 5280547 (1994-01-01), Mahoney
patent: 5463389 (1995-10-01), Klayman
patent: 5530957 (1996-06-01), Koenig
patent: 5551027 (1996-08-01), Choy et al.
patent: 5572221 (1996-11-01), Marlevi et al.
patent: 5592667 (1997-01-01), Bugajski
patent: 5606669 (1997-02-01), Bertin et al.
patent: 5640551 (1997-06-01), Chu et al.
patent: 5647058 (1997-07-01), Agrawal et al.
patent: 5664174 (1997-09-01), Agrawal et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5737732 (1998-04-01), Gibson et al.
patent: 5752243 (1998-05-01), Reiter et al.
patent: 5781906 (1998-07-01), Aggarwal et al.
patent: 5799312 (1998-08-01), Rigoutsos
patent: 5825936 (1998-10-01), Clarke et al.
patent: 5847761 (1998-12-01), Uz et al.
patent: 5883823 (1999-03-01), Ding
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5893104 (1999-04-01), Srinivasan et al.
patent: 5945982 (1999-08-01), Higashio et al.
patent: 5953722 (1999-09-01), Lampert et al.
patent: 5963956 (1999-10-01), Smartt
patent: 5968109 (1999-10-01), Israni et al.
patent: 5977890 (1999-11-01), Rigoutsos et al.
patent: 6081624 (2000-06-01), Krishnaswamy
patent: 6092065 (2000-07-01), Floratos et al.
patent: 6161105 (2000-12-01), Keighan et al.
patent: 6308177 (2001-10-01), Israni et al.
Samet, Hanan, “The Design and Analysis of Spatial Data Structure,” Addison-Wesley, 1990.
Guttman, Antonin, “R-Trees: A Dynamic Index Structure For Spatial Searching,” Proceedings of the Annual Meeting ACM SIGMOD, Boston, MA, 1983, pp. 47-57.
Frank, Andrew U. and Barrera, Renato, “The Fieldtree: A Data Structure for Geographic Information Systems,” Design and Implementation of Large Spatial Databases, Lecture Notes in Computer Science Series #409, Springer-Varlag, 1989, pp. 29-44.
Autodesk, Inc.
Couso Jose L.
Gates & Cooper LLP
LandOfFree
Spatial index compression through spatial subdivision encoding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Spatial index compression through spatial subdivision encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spatial index compression through spatial subdivision encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2937070