Method and means for recognizing patterns represented in logarithmic polar coordinates

• US 5,063,604 A
• Filed: 11/08/1989
• Issued: 11/05/1991
• Est. Priority Date: 11/08/1989
• Status: Expired due to Term

• Current Assignee: Carefusion 303 Incorporated (Becton, Dickinson & Co)
• Original Assignee: Transitions Research Corp.
• Inventors: Weiman, Carl F. R.
• Primary Examiner(s): Moore, David K.
• Assistant Examiner(s): Mancuso, Joseph
• Application Number:
  US07/434,100
• Time in Patent Office: 727 Days
• Field of Search: 382/41, 382/43, 382/10, 382/16, 382/25, 364/725, 364/731, 364/826, 358/140
• US Class Current: 382/170
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

Image processing method and apparatus wherein candidate points are first selected in a log-polar image domain. The points may be selected by edge detection, thresholding, or any method suitable for identifying image points which are likely to lie on some feature of interest. For every candidate point there is drawn, also in the log-polar domain, a mirror image of a curve that represents the log-polar image of a straight line. There is accumulated a log-polar domain histogram of "hits" from the drawing process. Finally, a peak bin is selected. The position of the peak bin corresponds to the position of the recognized line.

Claims

1. A method of processing image data to detect the presence of an extended feature or features of interest therein, the method comprising the steps of:

providing an image represented in a logarithmic polar (log-polar) coordinate system;

selecting image points which are candidates for membership in the feature of interest;

for each selected image point, constructing a curve in the same logarithmic polar coordinate system as the image, the curve characterizing the locus of possible locations of the feature of interest consistent with the selected image point;

accumulating a histogram whose bins coincide with points in the same logarithmic polar coordinate system as the image, which bins contain counts of the number of constructed curves intersecting at the location of the bin; and

selecting bins having greatest counts as representing the locations of definitive points for characterizing the location of the extended feature of interest within the image.

2. A method as set forth in claim 1 and including an additional step of:

constructing the detected features by marking points in the image, using the locations of the peak bins as a reference point for the construction.

3. A method as set forth in claim 1 where the extended features of interest are curves, including lines.

4. A method as set forth in claim 3 where the curves are straight lines.

5. A method as set forth in claim 4 wherein the step of constructing a curve constructs a curve that is a mirror image of a curve in logarithmic polar coordinates that corresponds to a straight line.

6. A method as set forth in claim 3 where the curves are circles through the origin of the log-polar coordinate system.

7. A method as set forth in claim 6 wherein the step of constructing a curve constructs a curve that is a mirror image of a curve in logarithmic polar coordinates that the corresponds to a circle through the origin of the log-polar coordinate system.

8. A method as set forth in claim 3 where the curves are parabolas or hyperbolas whose focuses are at the origin of the log-polar coordinate system.

9. A method as set forth in claim 1 wherein the step of providing ar image includes a step of capturing an image with a polar exponential sensor array.

10. A method as set forth in claim 1 wherein the step of providing an image includes a step of mapping Cartesian image coordinates to log-polar coordinates by using a hardware address lookup table and an accumulator memory.

11. A method as set forth in claim 1 wherein the step of providing an image includes a step of conducting light from image points through an optic fiber bundle to photosensitive locations in a photosensor chip.

12. A method as set forth in claim 1 wherein the step of selecting image points includes a step of applying a function whose domain is a local neighborhood of a candidate pixel, the process of selection being determined by the value of the function.

13. A method as set forth in claim 6 wherein the step of constructing a curve includes a step of incrementing the contents of a memory array whose elements are addressed by an address generated by the curve construction process.

14. A method as set forth in claim 1 wherein the step of constructing a curve includes a step of incrementing an array variable in a software program, which variable is specified by the curve construction process.

15. Image processing apparatus for detecting the presence of a feature of interest within an image comprising:

means for providing image data in a log-polar format;

means for selecting candidate points within the image data;

means for constructing, for every candidate point, a mirror image of the point'"'"'s apical log-line;

means, coupled to the means for constructing, for storing values in bins of a histogram; and

means for selecting a bin of the histogram having a peak value, the position of the selected bin corresponding to a position of the feature of interest within the image.

16. Image processing apparatus as set forth in claim 15 wherein the means for selecting candidate points within the image includes means for performing an edge detection operation on the image data.

17. Image processing apparatus as set forth in claim 16 wherein the means for performing edge detection includes:

means for applying an n×

m pixel neighborhood operator to the image data; and

means for detecting the presence of image pixels having a value equal to or greater than a predetermined threshold value.

18. A method of processing a set of multi-dimensional data elements so as to detect an extended feature or features of interest, each feature being comprised of a plurality of the multi-dimensional data elements, comprising the steps of:

providing a representation of the multi-dimensional data elements in a logarithmic-polar coordinate system;

selecting multi-dimensional data elements that are candidates for membership in the feature of interest;

for each selected multi-dimensional data element, constructing a curve in the same logarithmic-polar coordinate system as that in which the multi-dimensional data element is represented, the curve characterizing a locus of possible locations of the feature of interest, consistent with the selected multi-dimensional data element;

accumulating a histogram having bins that coincide with points int the same logarithmic-polar coordinate system as the representation of the multi-dimensional data elements, which bins contain counts of the number of constructed curves intersecting at the location of the bin; and

selecting bins having greatest counts as representing parameters that characterize the extended feature or features of interest.

19. A method as set forth in claim 18 wherein the step of providing a representation of the multi-dimensional data elements in log-polar format includes a step of viewing an environment with an image sensor array means constructed to generate image data in log-polar format.

20. A method as set forth in claim 19 wherein the method of processing a set of multi-dimensional elements is accomplished locally within the image sensor array means.

21. A method as set forth in claim 19 wherein the feature of interest is selected from the group consisting of straight lines, curved lines, conic sections and combinations thereof.

22. A method as set forth in claim 18 wherein the step of providing includes a step of mapping non-log-polar coordinates to log-polar coordinates using a look-up table means.

23. A method as set forth in claim 18 wherein the step of selecting multi-dimensional data elements includes a step of applying a function whose domain is a local neighborhood of a multi-dimensional data element, the process of selecting being determined by the value of the function.

24. Apparatus for processing a set of multi-dimensional data elements so as to detect an extended feature or features of interest, each feature being comprised of a plurality of the multi-dimensional data elements, comprising:

means for providing a representation of the multi-dimensional data elements in a logarithmic-polar coordinate system;

means for selecting multi-dimensional data elements that are candidates for membership in the feature of interest;

means for constructing, for each selected multi-dimensional data element, a curve in the same logarithmic-polar coordinate system as that in which the multi-dimensional data element is represented, the curve being constructed so as to characterize a locus of possible locations of the feature of interest, consistent with the selected multi-dimensional data element;

means for accumulating a histogram having bins that coincide with points in the same logarithmic-polar coordinate system as the representation of the multi-dimensional data elements, which bins contain counts of the number of constructed curves intersecting at the location of the bin; and

means for selecting bins having greatest counts as representing parameters that characterize the extended feature or features of interest.

25. Apparatus as set forth in claim 24 wherein the means for providing the multi-dimensional data elements in the log-polar format includes image sensor means constructed to generate image data in the log-polar format.