US5631982A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System using parallel coordinates for automated line detection in noisy images
Assignee: International Business Machines Corp
•
Filing: 1994-09-14
•
Granted: 1997-05-20
•
Expires: 2014-09-14
Abstract
Abstract A system for detecting lines in images using line neighborhoods and a parallel coordinate transformation. The process introduces the concept of line neighborhoods to accommodate the uncertainty in line detection arising from image noise. Because line neighborhoods in Cartesian coordinates have ambiguous and unbounded regions and always overlap one another, a parallel coordinate transform is used to transform Cartesian coordinate image plane line segments to points in a bounded and nonambiguous region of the parallel coordinate transform plane. Line detection then becomes a simple problem of detecting point clusters in the parallel coordinate transform plane.
Inventors
- 👤 Alfred Inselberg
- 👤 Avijit Chatterjee
- 👤 Bernard Dimsdale
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 18:55
CPC Classifications
G; G06; G06T; G06T7/00; G06T7/10; G06T7/12; G06V; G06V10/00; G06V10/40; G06V10/48; G06T2207/00; G06T2207/10; G06T2207/10032; G06T2207/20; G06T2207/20048; G06T2207/20061; G06T2207/30; G06T2207/30181; G06T2207/30184
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
191 words
A computer-implemented process comprising the steps of: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in each of said at least one cluster in said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one correspond line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 2
Dependent Claim
191 words
A computer-implemented process comprising the steps of: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in each of said at least one cluster in said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one correspond line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 3
Dependent Claim
44 words
The process of claim 1 wherein said first mapping step (b) comprises the step of: (b.1) associating said parallel coordinates transform point with upper and lower bounds in X 1 and X 2 equivalent to the bounds of the corresponding said image pixel pair.
Claim 4
Dependent Claim
69 words
The process of claim 2 wherein said second mapping step (f) comprises the steps of: (f.1) detecting the extreme said upper and lower bounds in X 1 and X 2 for all said transform points in said at least one cluster; and (f.2) extending each of said at least one detected line to said extreme upper and lower bounds in X 1 and X 2 on said image plane.
Claim 5
Dependent Claim
51 words
The process of claim 1 wherein each said image pixel pair in said image plane describes a line (x 2 =mx 1 +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a 1 , a 2 , b, d, and m≠1 are real numbers.
Claim 6
Dependent Claim
55 words
The process of claim 1 wherein said selecting step (a) comprises the steps of: (a.1) discarding all said image pixel pairs that are separated by a distance greater than a predetermined maximum threshold distance; and (a.2) discarding all said image point pairs that are separated by a distance less than a predetermined minimum threshold distance.
Claim 7
Dependent Claim
49 words
The process of claim 1 wherein said first mapping step (b) is independently performed (1) for all said image pixel pairs corresponding to line segments having nonpositive slope and (2) for all said image pixel pairs corresponding to line segments having positive slope after multiplying said positive slope by-1.
Claim 8
Dependent Claim
46 words
The process of claim 1 wherein said storing step (g) comprises the step of: (g.1) associating each of said at least one detected line with a quality measure corresponding to the number of said transform points in the corresponding one of said at least one cluster.
Claim 9
Independent Claim
242 words
A system for detecting lines in a image having a plurality of data representing image pixels distributed over an image plane in X 1 and X 2 , said system comprising: image storage means for storing said image pixel data; selection means coupled to said image storage means for selecting a plurality of pairs of said image pixels; first mapping means coupled to said selection means for transforming each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; transform storage means coupled to said first mapping means for storing a plurality of data representing said transform points and their associated said neighborhood buckets; bucket counting means coupled to said transform storage means for assigning a bucket point count to each said neighborhood bucket representing the number of said transform points in said each neighborhood bucket; cluster detection means coupled to said bucket counting means for identifying at least one cluster of said transform points in said parallel coordinates transform plane, said cluster being associated with a local maximum in said bucket point count; second mapping means coupled to said cluster detection means for transforming said at least one cluster to the first detected line in said image plane; line storage means coupled to said second mapping means for storing a plurality of data representing said first detected line; and a visual display to present an image of the first detected line.
Claim 10
Independent Claim
242 words
A system for detecting lines in a image having a plurality of data representing image pixels distributed over an image plane in X 1 and X 2 , said system comprising: image storage means for storing said image pixel data; selection means coupled to said image storage means for selecting a plurality of pairs of said image pixels; first mapping means coupled to said selection means for transforming each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; transform storage means coupled to said first mapping means for storing a plurality of data representing said transform points and their associated said neighborhood buckets; bucket counting means coupled to said transform storage means for assigning a bucket point count to each said neighborhood bucket representing the number of said transform points in said each neighborhood bucket; cluster detection means coupled to said bucket counting means for identifying at least one cluster of said transform points in said parallel coordinates transform plane, said cluster being associated with a local maximum in said bucket point count; second mapping means coupled to said cluster detection means for transforming said at least one cluster to the first detected line in said image plane; line storage means coupled to said second mapping means for storing a plurality of data representing said first detected line; and a visual display to present an image of the first detected line.
Claim 11
Dependent Claim
54 words
The system of claim 8 wherein said second mapping means comprises: line extension means for extending said first detected line to the extreme upper and lower bounds in X 1 and X 2 corresponding to the extreme bounds of the image pixel pairs represented by said transform points in said at least one cluster.
Claim 12
Dependent Claim
103 words
The system of claim 9 wherein said first mapping means comprises: computation means for computing said transform point (x, y) in said parallel coordinates transform plane according to the relationships x=d/(1-m) and y=b/(1-m), where the corresponding said image pixel pair (P 1 , P 2 ) is defined according to the relationships P 1 (x 11 , x 21 )=(a 1 , ma 1 +b) and P 2 (x 12 , x 22 )=(a 2 , ma 2 +b), which represent the line x 2 =mx 1 +b in said image plan where a 1 , b, d, and m≠1 are real numbers.
Claim 13
Dependent Claim
31 words
The system of claim 10 further comprising: display means coupled to said line storage means and to said image storage means for creating a visible image of said first detected line.
Claim 14
Dependent Claim
31 words
The system of claim 8 further comprising: display means coupled to side line storage means and to said image storage means for creating a visible image of said first detected line.
Claim 15
Dependent Claim
39 words
The system of claim 8 wherein said selection means comprises: sorting means for distinguishing among said image pixel pairs according to a separation distance greater than a predetermined minimum threshold distance and less than a predetermined maximum threshold distance.
Claim 16
Dependent Claim
54 words
The system of claim 8 wherein said second mapping means comprises: line extension means for extending said first detected line to the extreme upper and lower bounds in X 1 and X 2 corresponding to the extreme bounds of the image pixel pairs represented by said transform points in said at least one cluster.
Claim 17
Dependent Claim
39 words
The system of claim 8 wherein said second, mapping means further comprises: quality labelling means for associating said first detected line with a quality measure corresponding to the number of said transform points in said at least one cluster.
Claim 18
Dependent Claim
216 words
An article of manufacture comprising a digital data storage media tangibly embodying a program of machine-readable instructions to perform method steps for detecting lines in an image, said method steps comprising: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in said at least one cluster in each of said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one corresponding detected line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 19
Dependent Claim
216 words
An article of manufacture comprising a digital data storage media tangibly embodying a program of machine-readable instructions to perform method steps for detecting lines in an image, said method steps comprising: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in said at least one cluster in each of said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one corresponding detected line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 20
Dependent Claim
46 words
The article of manufacture of claim 16, wherein said first mapping step (b) comprises the step of: (b.1) associating said parallel coordinates transform point with upper and lower bounds in X 1 and X 2 equivalent to the bounds of the corresponding said image pixel pair.
Claim 21
Dependent Claim
71 words
The article of manufacture of claim 17, wherein said second mapping step (f) comprises the steps of: (f.1) detecting the extreme said upper and lower bounds in X 1 and X 2 for all said transform points in said at least one cluster; and (f.2) extending each of said at least one detected line to said extreme upper and lower bounds in X 2 and X 2 on said image plane.
Claim 22
Dependent Claim
53 words
The article of manufacture of claim 16, wherein each said image pixel pair in said image plane describes a line (x 2 =mx 1 +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a 1 , a 2 , b, d, and m≠1 are real numbers.
Claim 23
Dependent Claim
57 words
The article of manufacture of claim 16, wherein said selecting step (a) comprises the steps of: (a.1) discarding all said image pixel pairs that are separated by a distance greater than a predetermined maximum threshold distance; and (2.a) discarding all said image pixel pairs that are separated by a distance less than a predetermined minimum threshold distance.
Claim 24
Dependent Claim
52 words
The article of manufacture of claim 16, wherein said first mapping step (b) is independently performed (1) for all said image pixel pairs corresponding to line segments having nonpositive slope and (2) for all said image pixel pairs corresponding to line segments having positive slope after multiplying said positive slope by -1.
Claim 25
Dependent Claim
48 words
The article of manufacture of claim 21, wherein said storing step (g) comprises the step of: (g.1) associating each of said at least one detected line with a quality measure corresponding to the number of said transform points in the corresponding one of said at least one cluster.
Claim 26
Independent Claim
207 words
An apparatus comprising a digital data computer programmed to perform method steps to detect lines in an image, said method steps comprising: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in said at least one cluster in each of said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one corresponding detected line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 27
Independent Claim
207 words
An apparatus comprising a digital data computer programmed to perform method steps to detect lines in an image, said method steps comprising: (a) receiving an image containing an object and having a plurality of image pixels represented by data distributed over an image plane in X 1 and X 2 , and selecting a plurality of pairs of said image pixels; (b) mapping each said image pixel pair to a transform point in a parallel coordinates transform plane having a plurality of neighborhood buckets; (c) counting the number of said transform points in each said neighborhood bucket to create a bucket point count for said each neighborhood bucket; (d) analyzing said bucket point counts to detect at least one cluster of said transform points in said parallel coordinates transform plane; (e) locating the center point in said at least one cluster in each of said parallel coordinates transform plane; (f) detecting lines in the image plane by mapping each said center point in said at least one cluster to a corresponding detected line in said image plane; (g) storing a plurality of data representing said at least one corresponding detected line; and (h) presenting an image of the at least one detected line on a visual display.
Claim 28
Dependent Claim
44 words
The apparatus of claim 23, wherein said first mapping step (b) comprises the step of: (b.1) associating said parallel coordinates transform point with upper and lower bounds in X 1 and X 2 equivalent to the bounds of the corresponding said image pixel pair.
Claim 29
Dependent Claim
70 words
The apparatus of claim 24, wherein said second mapping step (f) comprises the steps of: (f. 1) detecting the extreme said upper and lower bounds in X 1 and X 2 for all said transform points in said at least one cluster; and (f.2) extending each of said at least one detected line to said extreme upper and lower bounds in X 1 and X 2 on said image plane.
Claim 30
Dependent Claim
51 words
The apparatus of claim 23, wherein each said image pixel pair in said image plane describes a line (x 2 =mx 1 +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a 1 , a 2 , b, d, and m≠1 are real numbers.
Claim 31
Dependent Claim
55 words
The apparatus of claim 23, wherein said selecting step (a) comprises the steps of: (a.1) discarding all said image pixel pairs that are separated by a distance greater than a predetermined maximum threshold distance; and (a.2) discarding all said image pixel pairs that are separated by a distance less than a predetermined minimum threshold distance.
Claim 32
Dependent Claim
49 words
The apparatus of claim 23, wherein said first mapping step (b) is independently performed (1) for all said image pixel pairs corresponding to line segments having nonpositive slope and (2) for all said image pixel pairs corresponding to line segments having positive slope after multiplying said positive slope by-1.
Claim 33
Dependent Claim
46 words
The apparatus of claim 23, wherein said storage step (g) comprises the step of: (g.1) associating each of said at least one detected line with a quality measure corresponding to the number of said transform points in the corresponding one of said at least one cluster.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-19 | 2000-11-18 | 2001-05-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-19 | 2004-11-18 | 2005-05-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-19 | 2008-11-18 | 2009-05-20 | $7700.00 | Window Closed / Lapsed |