System using parallel coordinates for automated line detection in noisy images

• US 5,631,982 A
• Filed: 09/14/1994
• Issued: 05/20/1997
• Est. Priority Date: 06/10/1993
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chatterjee, Avijit, Dimsdale, Bernard, Inselberg, Alfred
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): SHALWALA, BIPIN H
• Application Number:
  US08/306,223
• Time in Patent Office: 979 Days
• Field of Search: 382/192, 382/199, 382/202, 382/205, 382/276, 382/224, 382/225, 382/281, 382/288, 382/168
• US Class Current: 382/281
• CPC Class Codes: G06T 2207/10032 Satellite or aerial image; Remote sensing
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

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.

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 X₁ and X₂, 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.

2. 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₁ and X₂ equivalent to the bounds of the corresponding said image pixel pair.

3. 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₁ and X₂ 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₁ and X₂ on said image plane.

4. The process of claim 1 wherein each said image pixel pair in said image plane describes a line (x₂ =mx₁ +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a₁, a₂, b, d, and m≠

1 are real numbers.

5. 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.

6. 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.

7. 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.

8. A system for detecting lines in a image having a plurality of data representing image pixels distributed over an image plane in X₁ and X₂, 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.

9. 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₁ and X₂ corresponding to the extreme bounds of the image pixel pairs represented by said transform points in said at least one cluster.

10. 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₁, P₂) is defined according to the relationships P₁ (x₁₁, x₂₁)=(a₁, ma₁ +b) and P₂ (x₁₂, x₂₂)=(a₂, ma₂ +b), which represent the line x₂ =mx₁ +b in said image plan where a₁, b, d, and m≠

1 are real numbers.

11. 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.

12. 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.

13. 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.

14. 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₁ and X₂ corresponding to the extreme bounds of the image pixel pairs represented by said transform points in said at least one cluster.

15. 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.

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 X₁ and X₂, 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.

17. 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₁ and X₂ equivalent to the bounds of the corresponding said image pixel pair.

18. 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₁ and X₂ 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₂ and X₂ on said image plane.

19. The article of manufacture of claim 16, wherein each said image pixel pair in said image plane describes a line (x₂ =mx₁ +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a₁, a₂, b, d, and m≠

1 are real numbers.

20. 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.

21. 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.

22. 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.

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 X₁ and X₂, 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.

24. 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₁ and X₂ equivalent to the bounds of the corresponding said image pixel pair.

25. 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₁ and X₂ 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₁ and X₂ on said image plane.

26. The apparatus of claim 23, wherein each said image pixel pair in said image plane describes a line (x₂ =mx₁ +b) that is mapped into the transform point (d/(1-m),b/(1-m)) in said parallel coordinates transform plane, where a₁, a₂, b, d, and m≠

1 are real numbers.

27. 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.

28. 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.

29. 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.