Real time implementation of the hough transform

• US 5,430,810 A
• Filed: 06/18/1993
• Issued: 07/04/1995
• Est. Priority Date: 11/20/1990
• Status: Expired due to Fees

• Current Assignee: IMRA America Incorporated (Aisin Corp.)
• Original Assignee: IMRA America Incorporated (Aisin Corp.)
• Inventors: Saeki, Takao
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Chang, Jon
• Application Number:
  US08/078,071
• Time in Patent Office: 746 Days
• Field of Search: 382/1, 382/8, 382/41, 382/22, 382/27, 364/725, 364/826, 364/424.07, 364/424.02, 358/103, 348/113
• US Class Current: 382/281
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

In accordance with the present invention, a method and apparatus are disclosed for real-time processing of digitized image data using an implementation of the Hough transform. More specifically, frames of image data are received and stored as pixel arrays in a rectangular coordinate system. Pixels having values above a predetermined intensity are subsequently transformed into polar coordinate space. Maximum meeting points of curves associated with all pixels which have been transformed into polar coordinate space are then identified using a real-time, hardware implementation of a neuro-Hough transform for analyzing windowed portions of the digitized image. The present invention identifies maximum meeting points in polar coordinate space using a neuro-Hough transform implemented as a single chip.

Claims

1. A device for processing an image to recognize characteristic features of the image comprising:

an image processor for identifying characteristic features of an image, said image processor adding values associated with rectangular coordinates of pixels representing a windowed partition of an image to provide plural counts, each count corresponding to a number of occurrences for each of plural polar coordinate values determined from said rectangular coordinates using a Hough transform in an array of overlapping polar coordinate values, said image processor further including;

a plurality of comparators for comparing the plural counts of said polar coordinate values with one another in parallel;

at least one logic device for logically combining outputs of said comparators to identify at least one local maxima count; and

at least one additional comparator for comparing the at least one local maxima count with an adaptive threshold to identify at least one maximum meeting point of polar coordinate values, said at least one maximum meeting point representing a characteristic feature of said image.

2. Device according to claim 1, wherein said image processor further includes a plurality of adders, each of said adders receiving parallel inputs from pixels having predetermined rectangular coordinates.

3. Device according to claim 1, wherein said image processor further includes means, responsive to said at least one logic device, for selectively gating a plurality of local maxima counts, in parallel, for said windowed partition.

4. Device according to claim 3, wherein a plurality of maximum meeting points are detected in parallel using said plurality of local maxima counts and a plurality of adaptive thresholds.

5. Device according to claim 4, wherein each adaptive threshold is independently determined for each polar coordinate location in a polar coordinate space.

6. Device according to claim 4, wherein each adaptive threshold is determined using a rectangular coordinate partition which includes values representing a totally black image.

7. Device according to claim 1, wherein said image processor further includes a plurality of analog adders to produce said plural counts.

8. Device according to claim 1, wherein said image processor further includes a plurality of digital counters to produce said plural counts.

9. Device according to claim 1, wherein an output of said at least one additional comparator corresponds to polar coordinates of a line in said image.

10. Device according to claim 1, wherein said image processor further includes at least one programmable logic array which receives parallel inputs from all pixels in said windowed partition having predetermined rectangular coordinates to produce said plural counts.

11. Device according to claim 10, wherein a plurality of maximum meeting points are detected in parallel by comparing a plurality of local maxima with a plurality of adaptive thresholds.

12. Device according to claim 11, wherein each adaptive threshold is independently determined for each polar coordinate location in a polar coordinate space.

13. Device according to claim 1, wherein said image processor is implemented as a single chip integrated circuit.

14. A device according to claim 1, wherein said windowed partition is a fifteen pixel by fifteen pixel window.

15. A device according to claim 1, further including:

means for storing polar coordinates which correspond to said at least one maximum meeting point as a representation of said image for providing a vehicle guidance control signal.

21. A system according to claim 15, further including:

means for storing polar coordinates which correspond to said at least one maximum meeting point as a representation of said image for providing a vehicle guidance control signal.

16. An image processing system for processing an image to recognize characteristic features of an image, said image processing system comprising:

an imaging device for generating image data;

a frame buffer for receiving frames of analog image data from the imaging device at a data acquiring rate;

an analog-to-digital converter for converting said frames of analog image data into digitized image frames, said digitized image frames having a plurality of pixel values; and

an image processor for transforming rectangular coordinates associated with each of said pixel values in a rectangular coordinate space window into polar coordinate space coordinates using a Hough transform, and for detecting and processing a plurality of local maxima meeting points of said polar space coordinates in parallel at said data acquiring rate to detect at least one maximum meeting point using at least one adaptive threshold, each of said local maxima meeting points corresponding to a number of occurrences of a polar coordinate set associated with said transformed rectangular coordinates and being used to detect said at least one maximum meeting point as a characteristic feature for portions of a digitized image frame which have been selected using said rectangular coordinate space window.

17. System according to claim 16, wherein an adaptive threshold is independently determined for each polar coordinate location in said polar coordinate space.

18. System according to claim 16, wherein said image processor is formed as a single chip processor.

19. System according to claim 16, wherein said image processor uses a plurality of windows in polar coordinate space to determine said plurality of local maxima meeting points of said rectangular coordinate space window in parallel.

20. System according to claim 19, wherein each of said plurality of polar coordinate space windows is a 3 by 3 pixel array, and is used to examine data obtained from said rectangular coordinate space window in parallel.

22. A method for processing image data to recognize characteristic features of an image for vehicle guidance, comprising the steps of:

processing the image data in an image processor to identify characteristic features of the image, said step of processing including the steps of;

adding values associated with rectangular coordinates of pixels representing a windowed partition of the image to provide a count of a number of occurrences for each of plural polar coordinate values in an array of overlapping polar coordinate values;

comparing said counts of said polar coordinate values with one another in parallel;

logically combining results of said comparing step to identify a plurality of local maxima meeting points of said polar coordinate values; and

comparing the logically combined results of the comparing step with at least one predetermined threshold to detect and output at least one of said counts as at least one maximum meeting point of said polar coordinate values, said at least one maximum meeting point being output as a characteristic feature of said image and a vehicle guidance control signal which guides a vehicle.

23. Method according to claim 22, wherein said step of logically combining uses plural polar coordinate space windows to determine local maxima meeting points from which said at least one maximum meeting point is selected.

24. Method according to claim 23, wherein said polar coordinate space windows are used to determine local maxima meeting points in parallel for portions of a digitized image frame which had been selected using said windowed partition.

25. Method according to claim 22, wherein said step of logically combining uses a polar coordinate space window formed as a 3 by 3 pixel array to examine data obtained from said windowed partition.

26. Method according to claim 22, further including a step of:

storing polar coordinates which correspond to said at least one maximum meeting point as a representation of said image and as said vehicle guidance control signal.

27. Method according to claim 22, wherein said step of logically combining is performed by a single chip processor.

28. A method for processing image data to recognize characteristic features of an image for vehicle guidance comprising the steps of:

generating the image data using an image device;

acquiring frames of analog image data from said image device at a data acquiring rate;

converting said frames of analog image data into digitized image frames, said digitized image frames having a plurality of pixel values; and

transforming rectangular coordinates associated with each of said pixel values in a rectangular coordinate space window into polar coordinate space coordinates using a Hough transform, and using a plurality of polar coordinate space windows formed as 3 by 3 pixel arrays to examine data obtained from said rectangular space window in an image processor and to detect and output at least one maximum meeting point at said data acquiring rate, said at least one maximum meeting point corresponding to a number of occurrences of a polar coordinate set associated with said rectangular coordinate space window, and being output as a characteristic feature of said image and a vehicle guidance control signal which guides a vehicle.

29. Method according to claim 28, wherein said step of transforming and detecting is performed by a single chip processor.

30. Method according to claim 28, wherein said step of transforming and detecting uses said plurality of said polar coordinate space windows to determine local maxima meeting points from which said at least one maximum meeting point is selected.

31. Method according to claim 30, wherein said polar coordinate space windows are used to determine local maxima meeting points in parallel for portions of a digitized image frame which had been selected using said rectangular coordinate space window.

32. A method according to claim 28, further including a step of:

storing polar coordinates which correspond to said at least one maximum meeting point as a representation of said image and as said vehicle guidance control signal.