Means and method of representing an object shape by hierarchical boundary decomposition
First Claim
1. A method of extracting information on the shape of an object, said method comprising the steps of:
- (a) generating a two dimensional digital image of said object shape, said image being comprised of points;
(b) identifying the set of boundary points of said digital image;
(c) ordering said boundary points;
(d) at a first hierarchial level selecting a first convex hull subset of said boundary points wherein each point of said first subset is on an outermost portion of said boundary;
(e) partitioning said boundary into segments of either a first or a second kind wherein each of said segments is a group of consecutively ordered ones of said set of boundary points and the endpoints of each of said segments are two points of said first convex hull subset, and wherein said segments of a first kind are smoother than said segments of a second kind according to selected criteria;
(f) at the next hierarchial level selecting for each of said segments of a second kind from the previous hierarchial level a further convex hull subset of said boundary points wherein each point of said further subset is a boundary point on the outermost portions of the corresponding points of each of said segments of a second kind from the previous hierarchial level;
(g) partitioning each of said segments of the second kind into further of said segments of either a first or second kind, according to said criteria;
(h) repeating steps (f) and (g) for each of said segments of a second kind identified in step (g) until no further of said segments of a second kind are identified.
1 Assignment
0 Petitions
Accused Products
Abstract
Information on the shape of an object is extracted by generating an image of the object, encoding and ordering the boundary points of the image, selecting points on the outermost portions of the boundary, partitioning the boundary at the selected points into segments of either a first or second kind wherein the segments are distinguished according to a selected smoothness test, and segments of the first kind are smoother than segments of the second kind, partitioning each segment of the second kind into segments of the first or second kind according to the above test, and continuing the partitioning of each of the segments of the second kind into segments of the first or second kind until no further segments of the second kind are identified. An apparatus for performing the above steps is also disclosed.
-
Citations
6 Claims
-
1. A method of extracting information on the shape of an object, said method comprising the steps of:
-
(a) generating a two dimensional digital image of said object shape, said image being comprised of points; (b) identifying the set of boundary points of said digital image; (c) ordering said boundary points; (d) at a first hierarchial level selecting a first convex hull subset of said boundary points wherein each point of said first subset is on an outermost portion of said boundary; (e) partitioning said boundary into segments of either a first or a second kind wherein each of said segments is a group of consecutively ordered ones of said set of boundary points and the endpoints of each of said segments are two points of said first convex hull subset, and wherein said segments of a first kind are smoother than said segments of a second kind according to selected criteria; (f) at the next hierarchial level selecting for each of said segments of a second kind from the previous hierarchial level a further convex hull subset of said boundary points wherein each point of said further subset is a boundary point on the outermost portions of the corresponding points of each of said segments of a second kind from the previous hierarchial level; (g) partitioning each of said segments of the second kind into further of said segments of either a first or second kind, according to said criteria; (h) repeating steps (f) and (g) for each of said segments of a second kind identified in step (g) until no further of said segments of a second kind are identified. - View Dependent Claims (2, 3, 4, 5, 6)
-
Specification