US6466696B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Deriving polygonal boundaries from quadtree representation
Assignee: Canon Inc
•
Filing: 1999-05-17
•
Granted: 2002-10-15
•
Expires: 2019-05-17
Abstract
Abstract A method of conversion of a quadtree representation of image data into a corresponding representation of edges of regions within the image is disclosed. In one configuration the method comprises recursively processing ( 70 ) each quadrant using a number of steps. A first step examines if the quadrant is of a first particular uniform type ( 74 ), and if so, the method forms a series of lists ( 76 ) defining the boundary structure of the quadrant. A second step examines if the quadrant is of a second particular uniform type ( 80 ), and if so, the method forms a series of empty lists ( 82 ). A third step is applied where a quadrant is of an intermediate type containing data values of the first particular uniform type and the second particular uniform type, and the method divides the quadrant into a series of sub-quadrants ( 84,88 ) and recursively ( 86 ) applies the first, second and third steps to each of the sub-quadrants in accordance with the quadtree representation. The method combines the results produced from the recursive application to produce an intermediate description of the border regions of the quadrant such that the intermediate description of the root node of the quadtree comprises a description of the border of regions of the first particular uniform type of the image data.
Inventors
- 👤 George Politis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 00:45
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/12; G06T2207/00; G06T2207/10; G06T2207/10016; G06T2207/20; G06T2207/20016
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
187 words
A method of conversion of a quadtree representation of image data into a corresponding representation of edges of regions within said image, the method comprising the steps of: recursively processing each cell of the quadtree such that: (a) where said cell is of a first particular uniform type, creating a polygonal representation of an area bounded by the cell, and forming a description of the structure of the borders of said cell; (b) where said cell is of a second particular uniform type forming empty border descriptions for the cell; (c) where said 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) a 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 descriptions for the entire cell; such that, at a root quadtree cell, a polygonal description of the region represented by the quadtree is formed.
Claim 2
Independent Claim
187 words
A method of conversion of a quadtree representation of image data into a corresponding representation of edges of regions within said image, the method comprising the steps of: recursively processing each cell of the quadtree such that: (a) where said cell is of a first particular uniform type, creating a polygonal representation of an area bounded by the cell, and forming a description of the structure of the borders of said cell; (b) where said cell is of a second particular uniform type forming empty border descriptions for the cell; (c) where said 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) a 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 descriptions for the entire cell; such that, at a root quadtree cell, a polygonal description of the region represented by the quadtree is formed.
Claim 3
Dependent Claim
26 words
A method according to claim 1 wherein said combining utilizes the border lists of the common border of the cell or node areas to be combined.
Claim 4
Dependent Claim
31 words
A method according to claim 2 wherein each cell or node's border description is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 5
Dependent Claim
25 words
A method according to claim 3 wherein said utilization of border lists of the common border is based on the merging of two sorted lists.
Claim 6
Dependent Claim
26 words
A method according to claim 1 wherein the component regions represented by the tree are identified by examining the boundary structures created by the recursive process.
Claim 7
Dependent Claim
41 words
A method according to claim 5 wherein any of the following cleaning up operations are performed on said identified regions: (a) joining collinear edges; and/or (b) removing doubled up points; and/or (c) discarding degenerate regions that include only a single point.
Claim 8
Independent Claim
253 words
A method of conversion of a tree representation of one or more data regions with each tree node representing a cell of regional data of a first particular uniform type, a second particular uniform type or a mixture of said types and wherein when a node represents a mixture of said types said node includes a number of child nodes representing sub-regions of said data, said conversion being to a corresponding representation of edges of data regions, the method comprising the steps of: recursively processing each node of said tree representation such that: (a) where the corresponding said cell is of the 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 the corresponding said cell is of the second particular uniform type forming empty border descriptions for the cell; (c) where the corresponding said 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 border descriptions for the 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.
Claim 9
Independent Claim
253 words
A method of conversion of a tree representation of one or more data regions with each tree node representing a cell of regional data of a first particular uniform type, a second particular uniform type or a mixture of said types and wherein when a node represents a mixture of said types said node includes a number of child nodes representing sub-regions of said data, said conversion being to a corresponding representation of edges of data regions, the method comprising the steps of: recursively processing each node of said tree representation such that: (a) where the corresponding said cell is of the 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 the corresponding said cell is of the second particular uniform type forming empty border descriptions for the cell; (c) where the corresponding said 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 border descriptions for the 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.
Claim 10
Dependent Claim
26 words
A method according to claim 7 wherein said combining utilizes the border lists of the common border of the cell or node areas to be combined.
Claim 11
Dependent Claim
33 words
A method according to claim 8 wherein a border description of each cell or node is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 12
Dependent Claim
25 words
A method according to claim 9 wherein said utilization of border lists of the common border is based on the merging of two sorted lists.
Claim 13
Dependent Claim
26 words
A method according to claim 8 wherein the component regions represented by the tree are identified by examining the boundary structures created by the recursive process.
Claim 14
Dependent Claim
50 words
A method according to claim 11 wherein one or more cleaning up operations are performed on said identified regions, the cleaning up operations being selected from the group consisting of: (a) joining collinear edges; (b) removing doubled up points; and (c) discarding degenerate regions that include only a single point.
Claim 15
Independent Claim
204 words
A method of converting a quadtree representation of image data into a corresponding representation of edges of regions within said image, said method comprising the steps of: recursively processing each cell of the quadtree 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 borders of said cell; (b) where a cell is of a second particular uniform type forming empty border descriptions for the cell; (c) where a cell is of a third type not being one of said first or second types, said cell is divided into sub-cells, (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the quadtree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining said border descriptions to construct border descriptions for the entirety of said cell; to thereby form, at a root quadtree cell, a polygonal description of the region represented by the quadtree.
Claim 16
Independent Claim
204 words
A method of converting a quadtree representation of image data into a corresponding representation of edges of regions within said image, said method comprising the steps of: recursively processing each cell of the quadtree 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 borders of said cell; (b) where a cell is of a second particular uniform type forming empty border descriptions for the cell; (c) where a cell is of a third type not being one of said first or second types, said cell is divided into sub-cells, (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the quadtree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining said border descriptions to construct border descriptions for the entirety of said cell; to thereby form, at a root quadtree cell, a polygonal description of the region represented by the quadtree.
Claim 17
Dependent Claim
44 words
A method according to claim 13 wherein said first particular uniform type refers to a cell whose leaf node is entirely within the represented region, and said second particular uniform type refers to a cell whose leaf node is entirely outside the represented region.
Claim 18
Dependent Claim
23 words
A method according to claim 13 wherein said combining utilizes the border lists of the common borders between said sub-cells to be combined.
Claim 19
Dependent Claim
29 words
A method according to claim 15 wherein each said border description is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 20
Dependent Claim
30 words
A method according to claim 16 wherein the utilization of border lists of any one said common border is based on the merging of two sorted ones of said lists.
Claim 21
Dependent Claim
25 words
A method according to claim 13 wherein said cells represented by said quadtree are identified by examining the boundary structures created by said recursive processing.
Claim 22
Dependent Claim
45 words
A method according to claim 18 further comprising performing cleaning up operations on said identified cells, said operations being selected from the group consisting of: (a) joining collinear edges; (b) removing doubled up points; and (c) discarding degenerate cells that include only a single point.
Claim 23
Independent Claim
282 words
A method of converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said method comprising the steps of: recursively processing each said node of said tree representation such that: (a) where the corresponding said cell is of said first particular uniform type, creating a polygon that represents the area bounded by said cell, and forming a description of the structure of borders of said cell; (b) where the corresponding said cell is of said second particular uniform type forming empty border descriptions for said cell; (c) where the corresponding said cell is of said third type, dividing said cell into sub-cells, and (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the tree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining border descriptions for said cell; to thereby form, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 24
Independent Claim
282 words
A method of converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said method comprising the steps of: recursively processing each said node of said tree representation such that: (a) where the corresponding said cell is of said first particular uniform type, creating a polygon that represents the area bounded by said cell, and forming a description of the structure of borders of said cell; (b) where the corresponding said cell is of said second particular uniform type forming empty border descriptions for said cell; (c) where the corresponding said cell is of said third type, dividing said cell into sub-cells, and (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the tree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining border descriptions for said cell; to thereby form, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 25
Dependent Claim
43 words
A method according to claim 20 wherein said first particular uniform type refers to cell whose leaf node is entirely within the represented region, and said second particular uniform type refers to a cell whose leaf node is entirely outside the represented region.
Claim 26
Dependent Claim
14 words
A method according to claim 20 wherein said tree representation comprises a quadtree representation.
Claim 27
Dependent Claim
23 words
A method according to claim 20 wherein said combining utilizes the border lists of the common borders between said sub-cells to be combined.
Claim 28
Dependent Claim
28 words
A method according to claim 23 wherein said border description is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 29
Dependent Claim
30 words
A method according to claim 24 wherein the utilization of border lists of any one said common border is based on the merging of two sorted ones of said lists.
Claim 30
Dependent Claim
26 words
A method according to claim 20 wherein said cells represented by said tree representation are identified by examining the boundary structures created by said recursive processing.
Claim 31
Dependent Claim
45 words
A method according to claim 26 further comprising performing cleaning up operations on said identified cells, said operations being selected from the group consisting of: (a) joining collinear edges; (b) removing doubled up points; and (c) discarding degenerate cells that include only a single point.
Claim 32
Dependent Claim
323 words
Apparatus for converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said apparatus comprising: means for recursively processing each said node of said tree representation, said means for recursively processing comprising: first means for determining if the corresponding said cell is of said first particular uniform type, and if so, creating a polygon that represents an area bounded by said cell, and forming a description of the structure of borders of said cell; second means for determining if the corresponding said cell is of said second particular uniform type, and if so, forming empty border descriptions for said cell; third means for determining if the corresponding said cell is of said third type, and if so, dividing said cell into sub-cells, said third means including fourth means for recursively applying the processes of said first, second and third means to each of said sub-cells in accordance with the tree representation, fifth means for obtaining from said fourth means a border description of each border of each said sub-cell; sixth means for using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and seventh means for combining border descriptions for said cell; said means for recursively processing thereby forming, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 33
Dependent Claim
323 words
Apparatus for converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said apparatus comprising: means for recursively processing each said node of said tree representation, said means for recursively processing comprising: first means for determining if the corresponding said cell is of said first particular uniform type, and if so, creating a polygon that represents an area bounded by said cell, and forming a description of the structure of borders of said cell; second means for determining if the corresponding said cell is of said second particular uniform type, and if so, forming empty border descriptions for said cell; third means for determining if the corresponding said cell is of said third type, and if so, dividing said cell into sub-cells, said third means including fourth means for recursively applying the processes of said first, second and third means to each of said sub-cells in accordance with the tree representation, fifth means for obtaining from said fourth means a border description of each border of each said sub-cell; sixth means for using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and seventh means for combining border descriptions for said cell; said means for recursively processing thereby forming, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 34
Dependent Claim
43 words
Apparatus according to claim 28 wherein said first particular uniform type refers to a cell whose leaf node is entirely within the represented region, and said second particular uniform type refers to a cell whose leaf node is entirely outside the represented region.
Claim 35
Dependent Claim
13 words
Apparatus according to claim 28 wherein said tree representation comprises a quadtree representation.
Claim 36
Dependent Claim
23 words
Apparatus according to claim 28 wherein said seventh means utilizes the border lists of the common borders between said sub-cells to be combined.
Claim 37
Dependent Claim
28 words
Apparatus according to claim 31 wherein each said border description is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 38
Dependent Claim
29 words
Apparatus according to claim 32 wherein the utilization of border lists of any one said common border is based on the merging of two sorted ones of said lists.
Claim 39
Dependent Claim
27 words
Apparatus according to claim 28 wherein said cells represented by said tree representation are identified by examining the boundary structures created by said means for recursive processing.
Claim 40
Dependent Claim
47 words
Apparatus according to claim 34 further comprising eighth means for performing cleaning up operations on said identified cells, said operations being selected from the group consisting of: (a) joining collinear edges; (b) removing doubled up points; and (c) discarding degenerate cells that include only a single point.
Claim 41
Dependent Claim
294 words
A computer readable medium incorporating a computer program product for converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said computer program product implementing a method comprising the steps of: recursively processing each said node of said tree representation such that: (a) where the corresponding said cell is of said first particular uniform type, creating a polygon that represents the area bounded by said cell, and forming a description of the structure of borders of said cell; (b) where the corresponding said cell is of said second particular uniform type forming empty border descriptions for said cell; (c) where the corresponding said cell is of said third type, dividing said cell into sub-cells, and (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the tree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining border descriptions for said cell; to thereby form, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 42
Dependent Claim
294 words
A computer readable medium incorporating a computer program product for converting a tree representation of one or more data regions to a corresponding representation of edges of said data regions, said tree representation being formed by a plurality of nodes each representing a cell of regional data of a first particular uniform type, a second particular uniform type, or of a third type not being one of the first or second types, and wherein when one said node represents data of said third type, said one node includes a number of child nodes representing sub-regions of said data described by corresponding sub-cells, said computer program product implementing a method comprising the steps of: recursively processing each said node of said tree representation such that: (a) where the corresponding said cell is of said first particular uniform type, creating a polygon that represents the area bounded by said cell, and forming a description of the structure of borders of said cell; (b) where the corresponding said cell is of said second particular uniform type forming empty border descriptions for said cell; (c) where the corresponding said cell is of said third type, dividing said cell into sub-cells, and (i) recursively applying steps (a) to (c) to each of said sub-cells in accordance with the tree representation, (ii) obtaining from step (i) a border description of each border of each said sub-cell; (iii) using said border descriptions to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (iv) combining border descriptions for said cell; to thereby form, for a root node of the tree representation, a boundary structure of the one or more regions of the tree defined by the nodes of first particular uniform type.
Claim 43
Dependent Claim
46 words
A computer readable medium according to claim 36 wherein said first particular uniform type refers to a cell whose leaf node is entirely within the represented region, and said second particular uniform type refers to a cell whose leaf node is entirely outside the represented region.
Claim 44
Dependent Claim
16 words
A computer readable medium according to claim 36 wherein said tree representation comprises a quadtree representation.
Claim 45
Dependent Claim
25 words
A computer readable medium according to claim 36 wherein said combining utilizes the border lists of the common borders between said sub-cells to be combined.
Claim 46
Dependent Claim
31 words
A computer readable medium according to claim 39 wherein each said border description is a list of the first of each pair of vertices whose interconnecting edge lies along said border.
Claim 47
Dependent Claim
32 words
A computer readable medium according to claim 40 wherein the utilization of border lists of any one said common border is based on the merging of two sorted ones of said lists.
Claim 48
Dependent Claim
28 words
A computer readable medium according to claim 36 wherein said cells represented by said tree representation are identified by examining the boundary structures created by said recursive processing.
Claim 49
Dependent Claim
47 words
A computer readable medium according to claim 42 further comprising performing cleaning up operations on said identified cells, said operations being selected from the group consisting of: (a) joining collinear edges; (b) removing doubled up points; and (c) discarding degenerate cells that include only a single point.
Claim 50
Independent Claim
213 words
A method of converting a quadtree representation of image data into a corresponding representation of edges of regions within said image, said method comprising the steps of: (A) processing each cell of the quadtree by: (A1) determining if said cell is of a first particular uniform type, and if so creating a polygon that represents the area bounded by the cell, and forming a description of the structure of the borders of said cell; (A2) where said cell is not of said first type, determining if said cell is of a second particular uniform type, and if so, forming empty border descriptions for the cell; (A3) where said cell is of a third type not being one of said first or second types, dividing said cell into sub-cells, and processing said sub-cells according to steps (A) in accordance with the quadtree representation; (B) obtaining the border descriptions form step (A); (B2) using said border descriptions from steps (A1) and (A2) to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (B2) combining said border descriptions to construct border descriptions for the entirety of said cell; to thereby form, at a root quadtree cell, a polygonal description of the region represented by the quadtree.
Claim 51
Independent Claim
213 words
A method of converting a quadtree representation of image data into a corresponding representation of edges of regions within said image, said method comprising the steps of: (A) processing each cell of the quadtree by: (A1) determining if said cell is of a first particular uniform type, and if so creating a polygon that represents the area bounded by the cell, and forming a description of the structure of the borders of said cell; (A2) where said cell is not of said first type, determining if said cell is of a second particular uniform type, and if so, forming empty border descriptions for the cell; (A3) where said cell is of a third type not being one of said first or second types, dividing said cell into sub-cells, and processing said sub-cells according to steps (A) in accordance with the quadtree representation; (B) obtaining the border descriptions form step (A); (B2) using said border descriptions from steps (A1) and (A2) to combine the polygonal representations for each said sub-cell into a polygonal representation for the entirety of said cell, and (B2) combining said border descriptions to construct border descriptions for the entirety of said cell; to thereby form, at a root quadtree cell, a polygonal description of the region represented by the quadtree.
References Cited (Backward Citations)
US5724494A
Cited
US5745121A
Cited
US6084908A
Cited
US6144773A
Cited
US6005981A
Cited
US6163626A
Cited
US6182114B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-14 | 2006-04-15 | 2006-10-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-14 | 2010-04-15 | 2010-10-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-14 | 2014-04-15 | 2014-10-15 | $7700.00 | Window Closed / Lapsed |