Image analysis – Pattern recognition – Classification
Reexamination Certificate
1999-05-17
2002-10-15
Boudreau, Leo (Department: 2721)
Image analysis
Pattern recognition
Classification
C375S240030, C375S240160, C382S226000, C382S240000, C709S203000, C709S246000
Reexamination Certificate
active
06466696
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of digital data processing and, in particular, to the utilisation of quadtree representations of data.
BACKGROUND OF THE INVENTION
The utilisation of quadtree data representations in the field of computer data storage is well known. Quadtrees have particular application in representing image data, however, they are not limited thereto and apply generally to any data, including data having multiple dimensions, where extensions to structures such as octrees is also well known. For a comprehensive survey of the field of quadtrees and related hierarchical data structures, reference is made to “The Quadtree and Related Hierarchical Data Structures” by Hanan Samet appearing in
Computer Surveys
, Vol. 16, No. 2, June 1984 at pages 187-260 (hereinafter Samet).
A quadtree representation is often utilised in image data storage for its known advantages. However, it is often necessary to determine a boundary of a structure within an image given a quadtree representation of a whole image. Various techniques for determining a boundary of a portion of an image given a quadtree representation of the image are known. For example, Samet refers to one form of region determination described in “Region Representation: Boundary Codes from Quadtrees” by C. R. Dyer, A. Rosenfield, and H. Samet, appearing in the
Communications of the ACM
, March 1980, Vol. 23, No. 3 at page 171-179 (hereinafter Dyer et al.).
Unfortunately, such techniques have a number of significant disadvantages. For example, the technique of Dyer et al. utilises the presence of backpointers within the quadtree. That is, each tree node requires a pointer to its parent node. However, this is not always easily possible. For example, in a situation where set operations (union, intersection, difference) are frequently being performed, it is advantageous to reuse cells between quadtrees. The utilisation of quadtrees for set operations is fully discussed in the aforementioned survey article. Using such operations, any cell may have more than one parent since it may be part of more than one tree and multiple backpointers would have to be provided.
The method of Dyer et al. is also unable to handle quadtrees containing a number of disjoint boundaries as well as boundaries that form islands inside holes.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide for an alternative method and apparatus for the derivation of a boundary representation of regions within quadtree type represented data, images for example.
In accordance with a first aspect of the present invention, there is provided a method of conversion of a quadtree type representation of image type data into a corresponding representation of edges of regions within the image type, the method comprising the steps of:
recursively processing each quadrant of the quadtree type representation such that:
(a) where a cell is of a first particular uniform type, creating a polygon that represents the area bounded by the cell, and forming a description of the structure of the cell's borders;
(b) where a cell is of a second particular uniform type forming empty border descriptions for the cell;
(c) where a cell is divided into quadrants,
(i) recursively applying steps (a) to (c) to each of the quadrants in accordance with the quadtree representation,
(ii) obtaining from step (i) border description of each border of each quadrant;
(iii) using said border descriptions to combine the polygonal representations for each quadrant of the cell into a polygonal representation for the entire cell, and
(iv) combining said border descriptions to construct border description for the entire cell;
such that, for the root node of the tree, a boundary structure is formed of the one or more regions of the tree defined by the nodes of first particular uniform type.
In accordance with a second aspect of the present invention, there is provided a method of conversion of a tree representation of one or more data regions with each tree node representing regional data of a first particular uniform type, a second particular uniform type or a mixture of the types and wherein when a node represents a mixture of the types it includes a number of child nodes representing sub-regions of the data, the conversion being to a corresponding representation of edges of data regions, the method comprising the steps of:
recursively processing each node of the tree representation such that:
(a) where a node's regional data is of a first particular uniform type, creating a structure defining the boundary structure of the regional data, and forming a description of the structure of the borders of the area represented by the node;
(b) where a node's regional data is of a second particular uniform type, forming a null description of the structure of the borders of the area represented by the node;
(c) where a node's regional data is of an intermediate type containing data values of the first particular uniform type and the second particular uniform type;
(i) recursively applying the steps (a) to (c) to each of the child nodes,
(ii) obtaining from step (i) border descriptions of each border of each child node,
(iii) using said border descriptions to combine the boundary structures of the regions represented by each child node into a boundary structure of the region represented by the node, and
(iv) combining border descriptions of the child nodes as necessary to produce border descriptions of the structure of the borders of the area represented by the node;
such that, for the root node of the tree, a boundary structure is formed of the one or more regions of the tree defined by the nodes of first particular uniform type. Other aspects of the invention to be described include apparatus for performing the conversion, and a computer readable medium including a computer program product for performing the conversion.
The preferred embodiments of the present invention, however, will be described with reference to image data and the quadtree representation.
REFERENCES:
patent: 5724494 (1998-03-01), Politis
patent: 5745121 (1998-04-01), Politis
patent: 6005981 (1999-12-01), Ng et al.
patent: 6084908 (2000-07-01), Chiang et al.
patent: 6144773 (2000-11-01), Kolarov et al.
patent: 6163626 (2000-12-01), Andrew
patent: 6182114 (2001-01-01), Yap et al.
Charles R. Dyer, et al., “Region Representation: Boundary Codes from Quadtrees”, Communications of the ACM, Mar. 1980, vol. 23, No. 3, pp. 171-179.
Hanan Samet, “The Quadtree and Related Hierarchical Data Structures”, Computing Surveys, Jun. 1984, vol. 16, No. 2, pp. 187-260.
C.R. Dyer et al., “Region Representation: Boundary Codes from Quadtrees”, Communications of the ACM, Mar. 1980, vol. 23, No. 3, pp. 171-179.
H. Samet, “The Quadtree and Related Hierarchical Data Structures”, ACM Computing Systems, Jun. 1984, vol. 16, No. 2, pp. 187-260.
Boudreau Leo
Desire Gregory
LandOfFree
Deriving polygonal boundaries from quadtree representation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deriving polygonal boundaries from quadtree representation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deriving polygonal boundaries from quadtree representation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2998639