US5146549A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for identifying a pair of groups in an image having a minimum separation distance
Assignee: Sharp Corp
•
Filing: 1991-06-04
•
Granted: 1992-09-08
•
Expires: 2011-06-04
Abstract
Abstract A method and apparatus for determining which pair of a plurality of objects in an image has a minimum separation distance. In the method, centroids of groups are ordered in a sequence according to X and Y coordinates. A distance is measured between a reference object and an object adjacent in the ordered sequence to the reference. Objects in the sequence which are not adjacent in the sequence to the reference are excluded from measurement based upon relationships between the coordinate values of the reference object, the adjacent object and the non adjacent object being evaluated for exclusion. This exclusion reduces the total number of steps necessary to determine which pair of objects has the minimum distance. Distance measurements are made to non-excluded objects. Similar steps are repeated for other reference objects. The pair objects which have the smallest measured distance are indicated as the objects having the minimum separation. In the apparatus, the image is stored in a frame memory and an index indicating the centroid of the group may also be stored. The memory may be read in a raster scan order, thus generating an ordered sequence of centroid locations.
Inventors
- 👤 Ryohei Kumagai
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 20:01
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/60; G06T7/66
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
132 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations corresponding to coordinates of centroids of groups in the original image; generating a table of x- and y-coordinates of centroids of groups in the image, said table organized in order of centroid coordinates: excluding particular pairs of groups from further processing based on relative locations of coordinates of group centroids in the table; measuring distances between centroids of non-excluded pairs of groups; and generating a representation of the original image indicating which pair of groups in the image have the minimum measured distance between centroids.
Claim 2
Independent Claim
132 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations corresponding to coordinates of centroids of groups in the original image; generating a table of x- and y-coordinates of centroids of groups in the image, said table organized in order of centroid coordinates: excluding particular pairs of groups from further processing based on relative locations of coordinates of group centroids in the table; measuring distances between centroids of non-excluded pairs of groups; and generating a representation of the original image indicating which pair of groups in the image have the minimum measured distance between centroids.
Claim 3
Dependent Claim
35 words
An image processing method according to claim 1, wherein the step of generating a table includes a step of registering an index for each centroid at a place of each centroid in a frame memory.
Claim 4
Dependent Claim
28 words
An image processing method according to claim 1, wherein the step of generating a table includes a step of arranging centroid locations in said table in raster order.
Claim 5
Dependent Claim
43 words
An image processing method according to claim 1, wherein said step of calculating distances is performed first with respect to an entry adjacent to a reference entry in the table and then in order of increasing separation in the table from a reference.
Claim 6
Independent Claim
191 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations corresponding to coordinates of centroids of groups in the original image; generating an ordered sequence of coordinates of centroids of objects in the image; measuring a separation distance between a first reference object and an object which is adjacent to the first reference object in the ordered sequence; excluding from further processing with respect to the first reference object an object which is not adjacent to the first reference object in the ordered sequence when a coordinate value of the non-adjacent object centroid and a coordinate value of the adjacent object centroid satisfy a predetermined condition; measuring a separation distance between the first-reference-object centroid and the centroid of a non-excluded object; generating a representation of the original image indicating the first reference object and the object having the smallest measured distance to the first reference object as the pair having the minimum separation distance.
Claim 7
Independent Claim
191 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations corresponding to coordinates of centroids of groups in the original image; generating an ordered sequence of coordinates of centroids of objects in the image; measuring a separation distance between a first reference object and an object which is adjacent to the first reference object in the ordered sequence; excluding from further processing with respect to the first reference object an object which is not adjacent to the first reference object in the ordered sequence when a coordinate value of the non-adjacent object centroid and a coordinate value of the adjacent object centroid satisfy a predetermined condition; measuring a separation distance between the first-reference-object centroid and the centroid of a non-excluded object; generating a representation of the original image indicating the first reference object and the object having the smallest measured distance to the first reference object as the pair having the minimum separation distance.
Claim 8
Dependent Claim
112 words
A method as in claim 5 further comprising steps of: measuring a separation distance between a second reference object and an object which is adjacent to the second reference object in the ordered sequence; excluding a non-adjacent object from further processing with respect to the second reference object when a coordinate value of the non-adjacent object centroid and a coordinate value of the second adjacent reference object centroid satisfy a predetermined condition; measuring a separation distance between the second-reference-object centroid and centroids of non-excluded objects; and indicating, as the object pair having the minimum separation distance, the reference object and corresponding other object for which the measured separation distance is a minimum.
Claim 9
Dependent Claim
25 words
A method as in claim 5 wherein the coordinates are of a cartesian coordinate system having a first axis, X and a second axis, Y.
Claim 10
Dependent Claim
31 words
A method as in claim 7 wherein the step of generating an ordered sequence includes a step of ordering the locations of object centroids in order of their Y coordinate values.
Claim 11
Dependent Claim
38 words
A method as in claim 8 wherein the step of generating an ordered sequence includes a step of further ordering the locations of object centroids having the same Y coordinate values in order of their X coordinate values.
Claim 12
Dependent Claim
55 words
A method as in claim 8 wherein the step of excluding an object from further processing includes a step of comparing the X coordinate value of the reference object, X K , the X coordinate value of the adjacent object, X K+1 , and the X coordinate value of a non-adjacent object, X K+2 .
Claim 13
Dependent Claim
40 words
A method as in claim 10 wherein the step of excluding a non-adjacent object includes a step of excluding a non-adjacent object from further processing with respect to the first reference object when X K ≧X K+1 ≧X K+2 .
Claim 14
Dependent Claim
40 words
A method as in claim 10 wherein the step of excluding a non-adjacent object includes a step of excluding a non-adjacent object from further processing with respect to the first reference object when X K ≦X K+1 ≦X K+2 .
Claim 15
Dependent Claim
25 words
A method as in claim 5 further comprising steps of measuring separation distance between the first-reference-object centroid and a plurality of centroids of non-excluded objects.
Claim 16
Dependent Claim
38 words
A method as in claim 13 wherein the steps of measuring separation distance are performed with respect to non-adjacent objects in order of increasing separation of the non-adjacent objects from the first reference object in the ordered sequence.
Claim 17
Independent Claim
129 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations representing coordinates of centroids of groups in the original image; generating a table of x- and y-coordinates of centroids of groups, said table organized in order of centroid coordinates: excluding particular pairs of groups from further processing based on relative location of coordinates of group centroids in the table; measuring distances between centroids of non-excluded pairs of groups; and generating a representation of the original image designating a pair of groups in the original image having the minimum measured distance between centroids.
Claim 18
Independent Claim
129 words
A method for transforming an original image into a modified image comprising steps of: generating a first representation of the original image in a frame memory; generating a second representation of the image in a frame memory, said second representation including indices stored in frame memory locations representing coordinates of centroids of groups in the original image; generating a table of x- and y-coordinates of centroids of groups, said table organized in order of centroid coordinates: excluding particular pairs of groups from further processing based on relative location of coordinates of group centroids in the table; measuring distances between centroids of non-excluded pairs of groups; and generating a representation of the original image designating a pair of groups in the original image having the minimum measured distance between centroids.
References Cited (Backward Citations)
US4706213A
Cited
US4837563A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-08 | 1996-03-09 | 1996-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-08 | 2000-03-09 | 2000-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-08 | 2004-03-09 | 2004-09-08 | $7700.00 | Window Closed / Lapsed |