System using parallel coordinates for automated line detection in noisy images
First Claim
Patent Images
1. 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 X1 and X2, 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
29 Claims
-
1. 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 X1 and X2, 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for detecting lines in a image having a plurality of data representing image pixels distributed over an image plane in X1 and X2, 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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. 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 X1 and X2, 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. - View Dependent Claims (17, 18, 19, 20, 21, 22)
-
-
23. 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 X1 and X2, 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. - View Dependent Claims (24, 25, 26, 27, 28, 29)
-
Specification