Dynamic line-detection system for processors having limited internal memory

• US 9,349,069 B2
• Filed: 11/21/2011
• Issued: 05/24/2016
• Est. Priority Date: 11/21/2011
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Habbu, Raghavendra, Haribhatt, Akshayakumar, Vijayakumar, Rajesh, Mahapatra, Rajesh, Karanam, Gopal
• Primary Examiner(s): Abimbola, Kehinde O
• Application Number:
  US13/300,993
• Publication Number:
  US 20130128045A1
• Time in Patent Office: 1,646 Days
• Field of Search: 348/148
• US Class Current: 1/1
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding
• CPC Class Codes: G06V 20/588 Recognition of the road, e.g. of lane markings; Recognition of the vehicle driving pattern in relation to the road

Abstract

A line-detection system computes, using a local memory, a result of a partial conversion of image-space pixel data from image space to Hough space. The result is analyzed for edges corresponding to a line present in the partial conversion. The line is compared against other lines detected in previously computed partial results to identify a longest line in the image.

Claims

1. A method for detecting a line in an image with limited local memory space, the method comprising:

computing, using a local memory, a result of a partial conversion of image-space pixel data to Hough-space data;

storing the result of the partial conversion in a one-dimensional accumulator array in the local memory, wherein the result comprises vote counts corresponding to ρ

values for a predetermined value of θ

;

detecting a line present in the partial conversion by finding a local maximum in the vote counts stored in the one-dimensional accumulator array;

if the vote count of the local maximum is greater than vote count of the previously found local maximum associated with other lines detected from previously computed results, storing the line by filling an empty slot in a detected-line array with the line, or by replacing one previously detected line having a smallest vote count in the detected-line array; and

reusing the one dimensional accumulator array in the local memory to compute and analyze further results comprising vote counts corresponding to ρ

values for other values of θ

.

2. The method of claim 1, wherein computing the result of the partial conversion comprises a linear access of the image-space pixel data.

3. The method of claim 1, further comprising dividing a range of θ

into a plurality of discrete values within a predetermined range and assigning a value of θ

to each partial conversion.

4. The method of claim 1, wherein:

computing the result of the partial conversion comprises computing a plurality of ρ

values using the image-space pixel data and the predetermined value of θ

associated with the partial conversion; and

storing the result of the partial conversion comprises incrementing vote counts corresponding to the ρ

values for the predetermined value of θ

in the one-dimensional accumulator array of the local memory.

5. The method of claim 1, further comprising comparing the vote count of the local maximum against a vote count of a previously found local maximum associated with the other lines detected from the previously computed results stored in the detected line array.

6. The method of claim 1, further comprising comparing the vote counts of the one-dimensional array against a predetermined threshold.

7. The method of claim 1, wherein replacing one previously detected line comprises overwriting a previously detected but shorter line.

8. The method of claim 1, wherein the line is stored in the detected-line array if the line is not within a noise value of a previously detected line currently stored in the detected-line array.

9. The method of claim 1, wherein the line is stored in the detected-line array if the line is (i) within a noise value of a previously detected line currently stored in the detected-line array and (ii) is longer than the previously detected line.

22. The method of claim 8, wherein the noise value corresponds to a noise parameter defined for ρ

.

23. The method of claim 8, wherein the noise value corresponds to a noise parameter defined for θ

.

10. A system for detecting lines in an image with limited local memory space, the system comprising:

a local memory; and

a processor connected to the local memory via a high-speed interface, the processor configured for;

computing, using the local memory, a result of a partial conversion of image-space pixel data from image space to Hough space;

storing the result of the partial conversion in a one-dimensional accumulator array in the local memory, wherein the result comprises vote counts corresponding to ρ

values for a value of θ

;

analyzing the result for a line present in the partial conversion by finding a local maximum in the vote counts stored in the one-dimensional accumulator array;

if the vote count of the local maximum is greater than vote count of the previously found local maximum associated with other lines detected from previously computed results, storing the line by filling an empty slot in a detected-line array with the line, or by replacing one previously detected line having a smallest vote count in the detected-line array; and

computing, analyzing, and storing further results comprising vote counts corresponding to ρ

values for other values of θ

using the same one dimensional accumulator array in the local memory.

11. The system of claim 10, further comprising a main memory for storing the image-space pixel data, the main memory being connected to the processor via a slow-speed interface.

12. The system of claim 10, wherein a size of the image-space pixel data is greater than a size of the local memory.

13. The system of claim 10, wherein the processor is a digital signal processor or a low-power processor.

14. The system of claim 10, further comprising a camera for generating the image-space pixel data.

15. The system of claim 10, further comprising an input port for receiving the image-space pixel data from a local storage medium or from a network.

16. The system of claim 10, wherein the processor is further configured for comparing the vote counts of one-dimensional array against a predetermined threshold before a candidate vote count qualifies as a potential local maximum.

17. The system of claim 10 , wherein the local memory comprises the detected-line array for storing the line.

18. The system of claim 10 , wherein:

the local memory is inside the processor.

19. The system of claim 10 , wherein storing the line comprises storing the line in the detected-line array if the line is (i) within a noise value of a previously detected line currently stored in the detected-line array and (ii) is longer than the previously detected line.

20. A lane-detection system with limited local memory space for analyzing roadway images received from a vehicle-mounted camera, the lane-detection system comprising:

a local memory; and

a processor connected to the local memory via a high-speed interface, the processor configured for;

receiving image-space pixel data from the camera corresponding to detected edges in the roadway image;

computing, using the local memory, a result of a partial conversion of the image-space pixel data from image space to Hough space, wherein the result comprises vote counts corresponding to ρ

values for a value of θ

;

storing the result of the partial conversion in a one-dimensional accumulator array in the local memory;

analyzing the result for an edge corresponding to a line present in the partial conversion by finding a local maximum in the vote counts stored in the one-dimensional accumulator array;

if the vote count of the local maximum is greater than vote count of the previously found local maximum associated with other lines detected from previously computed results, storing the line by filling an empty slot in a detected-line array with the line, or by replacing one previously detected line having a smallest vote count in the detected-line array;

reusing the one dimensional accumulator array in the local memory to compute and analyze further results comprising vote counts corresponding to ρ

values for other values of θ

; and

detecting a lane based on the identified longest line in the detected line array.

21. The lane-detection system of claim 20, wherein the line comprises a lane marker.