CLIAMS:
1. A computer implemented method for detecting straight lines in a digital image, comprising:
identifying, using a processor, a plurality of candidate points in a digital image comprising at least one element;
determining a set of candidate points from the plurality of candidate points corresponding to each of multiple origins in the digital image, wherein the set of candidate points comprises highest number of collinear points; and
outputting at least one best fit line passing through at least one of multiple sets of candidate points, wherein the at least one best fit line corresponds to the at least one element in the digital image.

2. The method of claim 1, wherein said at least one of the multiple sets of candidate points comprises maximum number of collinear candidate points among the multiple sets of candidate points.

3. The method of claim 1, wherein the maximum number of candidate points intersects at one of the multiple origins.

4. The method of claim 1, wherein identifying the plurality of candidate points in the digital image comprises:
converting the digital image into a gradient image by filtering the digital image; and
identifying a plurality of candidate points in the gradient image.

5. The method of claim 1, wherein determining the set of candidate points from the plurality of candidate points corresponding to said each of the multiple origins in the digital image comprises:
computing a slope value associated with each of the plurality of candidate points corresponding to one of the multiple origins on an axis;
identifying a set of candidate points with identical slope value from the plurality of candidate points for each of the multiple origins;
determining next origin along the axis; and
repeating the steps of computing a slope value, identifying a set of candidate points and determining a next origin along the axis till a set of candidate points for each of the multiple origins are determined.

6. The method of claim 5, wherein outputting the at least one best fit line passing through the at least one of multiple sets of candidate points comprises:
determining a set of candidate points from the multiple sets of candidate points having maximum number of collinear points with respect to at least one of the multiple origins; and
outputting at least one best fit line starting from said one of the multiple origins and passing through the determined set of candidate points.

7. The method of claim 5, wherein determining the set of candidate points from the plurality of candidate points corresponding to said each of multiple origins in the digital image comprises:
generating an accumulator array containing a plurality of accumulator values, each of the accumulator values indicates number of candidate points having identical slope value for each of the multiple origins.

8. The method of claim 7, wherein outputting the at least one best fit line passing through the at least one of multiple sets of candidate points comprises:
determining a highest accumulator value from the plurality of accumulator values in the accumulator array, wherein the highest accumulator value corresponds to maximum number of collinear candidate points among the multiple sets of candidate points with respect to one of the multiple origins; and
outputting at least one best fit line starting from said one of the multiple origins and passing through the collinear candidate points.

9. The method of claim 1, wherein the at least one element in the digital image comprises character, marking, number, symbol, data, graphics, an edge and an object.

10. The method of claim 1, further comprising:
selecting candidate points from the plurality of candidate points which lie within a quadrant corresponding to each of the multiple origins for detecting a straight line in the digital image.

11. The method of claim 1, further comprising:
determining densely populated candidate points from the plurality of candidate points in the digital image;
defining a region of interest encompassing the densely populated candidate points; and
shifting vertical and horizontal axes to a new origin corresponding to the region of interest which encompasses the densely populated candidate points.

12. An apparatus comprising:
a processor; and
a memory coupled to the processor, wherein the memory comprises:
a candidate point determination module configured for identifying a plurality of candidate points in a digital image comprising at least one element;
a straight line detection module configured for determining a set of candidate points from the plurality of candidate points corresponding to each of multiple origins in the digital image, wherein the set of candidate points comprises highest number of collinear points; and
an output module configured for outputting at least one best fit line passing through at least one of multiple sets of candidate points, wherein the at least one best fit line corresponds to the at least one element in the digital image.

13. The apparatus of claim 12, wherein in identifying the plurality of candidate points in the digital image, the candidate point determination module is configured for:
converting the digital image into a gradient image by filtering the digital image; and
identifying a plurality of candidate points in the gradient image.

14. The apparatus of claim 12, wherein in determining the set of candidate points from the plurality of candidate points corresponding to said each of the multiple origins in the digital image, the straight line detection module is configured for:
computing a slope value associated with each of the plurality of candidate points corresponding to one of the multiple origins on an axis;
identifying a set of candidate points with identical slope value from the plurality of candidate points for each of the multiple origins;
determining next origin along the axis; and
repeating the steps of computing a slope value, identifying a set of candidate points and determining a next origin along the axis till a set of candidate points for each of the multiple origins are determined.

15. The apparatus of claim 14, wherein in outputting the at least one best fit line passing through the at least one of multiple sets of candidate points, the output module is configured for:
determining a set of candidate points from the multiple sets of candidate points having maximum number of collinear points with respect to at least one of the multiple origins; and
outputting at least one best fit line starting from said one of the multiple origins and passing through the determined set of candidate points.

16. The apparatus of claim 15, wherein in determining the set of candidate points from the plurality of candidate points corresponding to said each of multiple origins in the digital image, the straight line detection module is configured for:
generating an accumulator array containing a plurality of accumulator values, each of the accumulator values indicates number of candidate points having identical slope value for each of the multiple origins.

17. The apparatus of claim 16, wherein in outputting the at least one best fit line passing through the at least one of multiple sets of candidate points, the output module is configured for:
determining a highest accumulator value from the plurality of accumulator values in the accumulator array, wherein the highest accumulator value corresponds to maximum number of collinear candidate points among the multiple sets of candidate points with respect to one of the multiple origins; and
outputting at least one best fit line starting from said one of the multiple origins and passing through the collinear candidate points.

18. A non-transitory computer-readable storage medium having instructions stored therein, that when executed by an image processing device, cause the image processing device to perform a method comprising:
identifying a plurality of candidate points in a digital image comprising at least one element;
determining a set of candidate points from the plurality of candidate points corresponding to each of multiple origins in the digital image, wherein the set of candidate points comprises highest number of collinear points; and
outputting at least one best fit line passing through at least one of multiple sets of candidate points, wherein the at least one best fit line corresponds to the at least one element in the digital image.

19. A method for monitoring position of a vehicle on a road, comprising:
determining, using a processor, a plurality of candidate points in a digital image of a road;
determining multiple sets of candidate points in the plurality of candidate points corresponding to multiple origins in the digital image, wherein each of the multiple sets of candidate points comprises collinear candidate points;
detecting lane markings on the road with respect to the position of the vehicle based on the multiple sets of candidate points corresponding to the multiple origins; and
monitoring the position of the vehicle on the road based on the identified lane markings on the road.

20. The method of claim 19, wherein determining the plurality of candidate points in the digital image of the road comprises:
converting the digital image of the road into a gradient image;
generating a plurality of scan lines within a region of interest on the gradient image; and
determining a plurality of candidate points at the intersection of one or more of the plurality of scan lines and pixels in the gradient image with high gradient value.

21. The method of claim 20, wherein determining the multiple sets of candidate points in the plurality of candidate points corresponding to multiple origins in the digital image comprises:
computing a slope value associated with each of the plurality of candidate points corresponding to each of the multiple origins on an axis;
identifying a set of candidate points with identical slope value from the plurality of candidate points for each of the multiple origins;
determining next origin along the axis; and
repeating the steps of computing a slope value, identifying a set of candidate points and determining a next origin along the axis till a set of candidate points for each of the multiple origins are determined.

22. The method of claim 21, wherein detecting the lane markings on the road with respect to the position of the vehicle based on the multiple sets of candidate points corresponding to the multiple origins comprises:
plotting a straight line passing through each set of candidate points on either side of the vehicle, wherein the straight line represents lane marking on the road.

23. The method of claim 22, wherein monitoring the position of the vehicle on the road based on the identified lane markings on the road comprises:
determining whether the vehicle is within the detected lane markings; and
generating an alert notification indicating that the vehicle has departed from the detected lane markings if the vehicle is not within the detected lane markings.

24. An apparatus for monitoring position of a vehicle on a road, the apparatus comprising:
a processor; and
a memory coupled to the processor, wherein the memory comprises:
a candidate point determination module configured for determining a plurality of candidate points in a digital image of a road;
a lane detection module configured for a determining multiple sets of candidate points in the plurality of candidate points corresponding to multiple origins in the digital image, wherein each of the multiple sets of candidate points comprises collinear candidate points, and detecting lane markings on the road with respect to the position of the vehicle based on the multiple sets of candidate points corresponding to the multiple origins; and
a position monitoring module configured for monitoring the position of the vehicle on the road based on the detecting lane markings on the road.

25. The apparatus of claim 24, wherein in determining the plurality of candidate points in the digital image of the road, the candidate point determination module is configured for:
converting the digital image of the road into a gradient image;
generating a plurality of scan lines within a region of interest on the gradient image; and
determining a plurality of candidate points at the intersection of one or more of the plurality of scan lines and pixels in the gradient image with high gradient value.

26. The apparatus of claim 25, wherein in determining the multiple sets of candidate points in the plurality of candidate points corresponding to multiple origins in the digital image, the lane detection module configured for:
computing a slope value associated with each of the plurality of candidate points corresponding to each of the multiple origins on an axis;
identifying a set of candidate points with identical slope value from the plurality of candidate points for each of the multiple origins;
determining next origin along the axis; and
repeating the steps of computing a slope value, identifying a set of candidate points and determining a next origin along the axis till a set of candidate points for each of the multiple origins are determined.

27. The apparatus of claim 26, wherein in detecting the lane markings on the road with respect to the position of the vehicle based on the multiple sets of candidate points corresponding to the multiple origins, the lane detection module is configured for:
plotting a straight line passing through each set of candidate points on either side of the vehicle, wherein the straight line represents lane marking on the road.

28. The apparatus of claim 27, wherein in monitoring the position of the vehicle on the road based on the detected lane markings on the road, the position monitoring module is configured for:
determining whether the vehicle is within the detected lane markings; and
generating an alert notification indicating that the vehicle has departed from the detected lane markings if the vehicle is not within the detected lane markings.

29. The apparatus of claim 24, further comprising:
an image capturing device configured for capturing the digital image of the road in real time.

30. The apparatus of claim 24, further comprising:
an output device configured for displaying the position of the vehicle with respect to the detected lane markings on the road.

31. A non-transitory computer-readable storage medium having instructions stored therein, that when executed by a vehicle position monitoring apparatus, cause the vehicle position monitoring apparatus to perform a method comprising:
determining a plurality of candidate points in a digital image of a road;
determining multiple sets of candidate points in the plurality of candidate points corresponding to multiple origins in the digital image, wherein each of the multiple sets of candidate points comprises collinear candidate points;
detecting lane markings on the road with respect to the position of the vehicle based on the multiple sets of candidate points corresponding to the multiple origins; and
monitoring the position of the vehicle on the road based on the identified lane markings on the road.
,TagSPECI:FIELD OF THE INVENTION

The present invention generally relates to image processing systems, and more particularly relates to straight line detection in a digital image.

BACKGROUND OF THE INVENTION

In the era of digital world, digitization of an image and image processing techniques plays a vital role. Image processing systems use a variety of signal processing standards for customizing an image for its innumerable use in various applications. One such important advancement in the field of image processing technology is the straight line detection systems. Straight line detection systems are used to detect the straight lines in various shapes in an image. Straight line detection systems are widely applicable in lane departure warning systems, optical character recognition (OCR), and number plate recognition system, graphics library, and any statistical applications of determining a best fit line.

In the image processing systems, a variety of techniques have been introduced to detect straight lines in an image. One of the currently known techniques includes Hough Transform which is capable of detecting straight lines for a given shape or shapes of a given image. Typically, Hough Transform technique is used to locate straight lines, circles, parabolas, ellipses, etc. However, the Hough Transform technique suffers from large processing time and space requirements, detection of false positives, low peaks for short lines and incapability in preserving edge pixel connectivity.

BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS

Figure 1 is a block diagram illustrating an image processing device configured for detecting straight lines in a digital image, according to one embodiment.

Figure 2 is a process flowchart illustrating an exemplary method of detecting straight lines in a digital image, according to one embodiment.

Figures 3 to 8 are schematic representations illustrating a process of detecting straight lines in a digital image, according to one embodiment.

Figure 9 is a block diagram illustrating a vehicle position monitoring apparatus configured for monitoring position of a vehicle with respect to lane markings on a road, according to one embodiment.

Figure 10 illustrates a process flowchart of an exemplary method of monitoring position of a vehicle on a road, according to one embodiment.

Figures 11-15 are schematic representations illustrating an exemplary process of detecting position of a vehicle with respect to lanes marked on a road, according to one embodiment.

The drawings described herein are for illustration purposes only and are not intended to limit the scope of the present disclosure in any way.

DETAILED DESCRIPTION OF THE INVENTION

The present invention provides a method and apparatus for detecting straight lines in a digital image. In the following detailed description of the embodiments of the invention, reference is made to the accompanying drawings that form a part hereof, and in which are shown by way of illustration specific embodiments in which the invention may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the invention, and it is to be understood that other embodiments may be utilized and that changes may be made without departing from the scope of the present invention. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

Figure 1 is a block diagram illustrating an image processing device 102 configured for detecting straight lines in a digital image, according to one embodiment. The image processing device 102 includes a processor 104, a memory unit 106, a storage unit 114, an output device 116 and a communication interface 118 coupled to a bus 120.

The image processing device 102 may include additional components not shown in Figure 1 for purposes of clarity. For example, the image processing device 102 may also include an image capturing unit, a speaker, in examples where the image processing device 102 is capable of capturing images and for generating voice alerts.

The processor 104 may be configured to implement functionality and/or process instructions for execution within the image processing device 102. The processor 104 may be capable of processing instructions stored in the memory or instructions stored on the storage unit 114. The processor 104 may include any one or more of a processor, a controller, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or equivalent discrete or integrated logic circuitry. Additionally, the functions attributed to the processor 104, in this disclosure, may be embodied as software, firmware, hardware or any combination thereof.

The memory unit 106 may be configured to store information within the image processing device 102 during operation. The memory unit 106 may, in some examples, be described as a computer-readable storage medium. The memory unit 106 may be described as a volatile memory, meaning that the memory does not maintain stored contents when the computer is turned off. Examples of volatile memories include random access memories (RAM), dynamic random access memories (DRAM), static random access memories (SRAM), and other forms of volatile memories known in the art. In some examples, the memory unit 106 may be used to store program instructions for execution by the processor 104.

For example, the memory unit 106 includes a candidate point determination module 108, a straight line detection module 110 and an output module 112 stored in the form of program instructions for execution by the processor 104. The candidate point determination module 108, a straight line detection module 110 and an output module 112 can be implemented as software, hardware, or some combination of software and hardware. For example, the candidate point determination module 108, a straight line detection module 110 and an output module 112 could be implemented as a part of an application specific integrated circuit (ASIC).

According to the present invention, the candidate point determination module 108 is configured for identifying a plurality of candidate points in an image. The straight line detection module 110 is configured for determining multiple sets of candidate points having equal slope corresponding to multiple origins and detect a straight line passing through a set of candidate points having highest number of collinear candidate points among the multiple sets of candidate points, where the straight line correspond to at least one element in the digital image. The output module 112 is configured for outputting the detected straight line on the output device 116 (e.g., display unit).

The storage unit 114 may include one or more computer-readable storage media. The storage device 114 may include non-volatile storage elements. Examples of such non-volatile storage elements may include magnetic hard discs, optical discs, floppy discs, flash memories, or forms of electrically programmable memories (EPROM) or electrically erasable and programmable (EEPROM) memories. In addition, the storage device 114 may, in some examples, be considered a non-transitory storage medium. The term “non-transitory” may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. However, the term “non-transitory” should not be interpreted to mean that the storage device 114 is non-movable. In some examples, the storage device may 114 be configured to store larger amounts of information than the memory unit 106. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in Random Access Memory (RAM) or cache).

The communication interface 118 may be used to transmit or receive instructions over a network using a bus 120 coupled to the communication interface 118. The communication interface 118 may be a part of the processor 104 or may be a separate component. The communication interface 118 may be created in software or may be a physical connection in hardware. The communication interface 118 may be configured to connect with a network, external media, a display or any other component in the system, or in combinations thereof.

Figure 2 is a process flowchart 200 illustrating an exemplary method of detecting straight lines in a digital image, according to one embodiment. The steps 202 to 216 depict a process performed by an image processing device 102 to detect a straight line in an image.

At step 202, an image in which a straight line is to be detected is obtained from the storage unit 114. In one embodiment, an image captured by an image capturing unit (not shown in Figure 1) and temporarily stored in the storage unit 114 is retrieved for detecting a straight line. In another embodiment, an image is selected from a plurality of images in the storage unit 114. At step 204, the digital image is converted to a gradient image. In one exemplary implementation, the image is converted to gradient image using the Sobel filter. Alternatively, the digital image is converted to gradient image using any gradient image generation algorithms well known in the art.

At step 206, a plurality of candidate points is identified in the gradient image. A group of pixels in the gradient image having high intensity values compared to other pixels are identified as a candidate point. All pixels groups having high intensity values compared to other regions in the gradient image are declared as candidate points. In this manner, the plurality of candidate points is identified in the gradient image. At step 208, an origin is selected from multiple origins on an axis of the gradient image. For example, an origin (0,0) at the intersection of the X axis and Y axis of the gradient image is selected for detecting one or more best fit lines in the gradient image with respect to the origin (0,0).

At step 210, slope value associated with each of the plurality of candidate points corresponding to the selected origin is computed. For example, slope value (Mp) associated with a candidate point (p) for the selected origin on the X-axis is computed using following equation:

M_p=Y_p/((X_p-origin))

where, Mp is slope value of candidate point (p), Xp and Yp is location of candidate point (p) with respect to X axis and Y axis, and origin corresponds to the value of the shifted origin.

At step 212, a set of candidate points with identical slope value are identified from the plurality of candidate points for the selected origin. The candidate points with identical slope are deemed to be collinear with respect to the selected origin. In some embodiments, a maximum number of collinear candidate points are identified to form a set of candidate points. In other embodiments, a number of collinear candidate points above a threshold value are identified to form a set of candidate points. For example, maximum occurrence (Forigin) of identical slope value with respect to the selected origin is computed using the following equation:
F_((origin))=max ( freq ( M_p ) ),
The maximum of Forigin determines intercept of a line which contains maximum number of collinear points.

At step 214, it is determined whether the set of candidate points are determined for all origins. If set of candidate points are not determined for all origins, then the process repeats the steps 208 to 212 in which a next origin among multiple origins is selected and set of candidate points for the selected origin is determined. If set of candidate points are determined for all origins, then at step 216, a set of candidate points associated with one of the multiple origins is identified from the identified sets of candidate points, where the set of candidate points contains highest number of collinear points among the identified sets of candidate points. In some embodiments, highest number of collinear points among the identified sets of candidate points is determined using an accumulator array. The accumulator array is plotted with origin on the X-axis and slope values on the Y-axis. For example, an accumulator array contains accumulator values of slope(s) for each origin. The accumulator value for an origin is incremented when there exists another candidate point with identical slope value. Once slope values for candidate points for all origins are completed, the highest accumulator value in the accumulator array is identified and a straight line is plotted using the origin and the slope value of the identified accumulator value.

At step 218, a straight line starting from said one of the multiple origins and passing through the determined set of candidate points is output on the output device 116 (e.g., a display unit). Additionally, information associated with the set of candidate points, and the associated origin is stored in the storage unit 114 for further processing. One skilled in the art will understand that the straight line outputted by the output device 116 corresponds to one or more pixels representing an element in the digital image. The element in the digital image may include, but are not limited to, lane markings, colored markings, numbers, characters, polygon, data, graphics, symbols, objects, edges, and so on.

Figures 3 to 8 are schematic representations illustrating a process of detecting straight lines in a digital image, according to one embodiment. Consider that a straight line needs to be detected in a digital image 302 as shown in Figure 3. Based on the input image 302, the candidate point determination module 108 identifies points P1 to P10 as candidate points 304 in the image 302. In one exemplary implementation, the candidate point determination module 108 determines the candidate points P1 to P10 by applying one dimensional filter on the image 302.

For ease of computation, the straight line detection module 110 generates X and Y axes for the image 302. As can be seen from Figure 3, the horizontal axis is the X axis for the image 302 and the vertical axis is the Y axis for the image 302. Further, the X axis and the Y axis are equally divided into a pre-defined number of portions.

Further, the straight line detection module 110 selects point (0,0) as a first origin for detecting best fit lines. With respect to the origin (0,0), the straight line detection module 110 computes slope value for each of the candidate points P1 to P10. Thereafter, the straight line detection module 110 identifies the points P3, P9, and P10 as a set of candidate points having equal slope value. Accordingly, the straight line detection module 110 draws a best fit line 402 starting from the origin (0,0) and passing through the candidate points P3, P9 and P10 as shown in Figure 4.

Once the best fit line with respect to the origin (0,0) is determined, the straight line detection module 110 shifts the origin along the X-axis to point (0.5,0). Thus, the point (0.5,0) is selected as a new origin. The straight line detection module 110 computes slope value for each of the candidate points P1 to P10 with respect to the origin (0.5,0). The straight line detection module 110 determines whether any of the candidate points P1 to P10 are having identical slope value. The straight line detection module 110 determines that none of the candidate points P1 to P10 are having identical slope value. Therefore, the straight line detection module 110 selects the point (1,0) as a next origin along the X-axis. Further, the straight line detection module 110 computes slope value for the candidate points P1 to P10 with respect to the origin (1,0).

Once the slope values are computed, the straight line detection module 110 determines a maximum number of candidate points which have identical slope value. For the origin (1,0), the straight line detection module 110 determines that the candidate points P1, P2, P3, P6 and P7 are collinear, i.e., having identical slope values. Accordingly, the straight line detection module 110 draws a best fit line 502 starting from the origin (1,0) and passing through the candidate points P1, P2, P3, P6 and P7 as shown in Figure 5. In this manner, the straight line detection module 110 determines best fit lines for all origins along the X-axis as shown in Figure 6. Exemplary slope values computed for the candidate points P1 to P10 for each of the origins (0,0), (0.5), (1,0), (1.5,0), (2,0), (2.5,0), (3,0), (3.5,0), (4,0), (4.5,0), and (5,0) is shown in Table 1 below.

Table 1

Upon computing slope values for each of the origins, the straight line detection module 110 identifies a best fit line passing through maximum number of candidate points with respect to a particular origin. From Table 1, the straight line detection module 110 determines the best fit line starting at the origin (1,0) and passing through the candidate points P1, P2, P3, P6 and P7 as a straight line as the best fit line is passing through maximum number of collinear candidate points. Accordingly, the straight line detection module 110 outputs the straight line starting at the origin (1,0) and passing through the candidate points P1, P2, P3, P6 and P7 on the output device 116.

In some embodiments, the straight line detection module 110 generates an accumulator array containing a plurality of accumulator values, each accumulator value indicates number of candidate points having identical slope value for a particular origin. The output module 112 determines the highest accumulator value from the plurality of accumulator values in the accumulator array, where the highest accumulator value corresponds to maximum number of collinear candidate points with identical slope value for one of the origins. Based on the highest accumulator value, the output module 112 plots a straight line based on the origin (1,0) and the slope value (2) corresponding to the highest accumulator value.

Although, the above description describes shifting the origin along the X-axis, one skilled in the art would understand that the straight line detection module 110 may also select origin along the Y-axis for detecting a straight line.

In some embodiments, the straight line detection module 110 considers candidate points which are a part of quadrant of the newly selected origin for computing the slope value. For example, as shown in Figure 7, upon shifting the origin 702 to the point (2,0) from the point (1.5,0) on the X-axis, the straight line detection module 110 identifies candidate points P2, P3, P5, P6, P7, P8, P9, and P10 as part of quadrant. As a consequence, the straight line detection module 110 omits the candidate points P1 and P4 that are outside the quadrant formed due to the new origin (2,0) for detecting the best fit line. This would eliminate duplicates and decrease computational time required for detecting straight line by the image processing device 102.

In other embodiments, the straight line detection module 110 may determine candidate points that are densely populated and define a region of interest covering the densely populated candidate points. In these embodiments, the straight line detection module 110 may redefine X and Y axes based on the region of interest. For example, as shown in Figure 8, the X and Y axis is shifted from the origin (0,0) to a new origin 802 (1.5, 1.5), where the X and Y axes cover the candidate points P2, P3, P5, P6, P7, P8, P9, and P10. The straight line detection module 110 may determine slope of candidate points with respect to multiple origins along the X axis and/or the Y axis and identify best fit line for each of the multiple origins as explained above.

Figure 9 is a block diagram illustrating a vehicle position monitoring apparatus 902 configured for monitoring position of a vehicle with respect to lane markings on a road, according to one embodiment. The vehicle position monitoring apparatus 902 includes a processor 904, a memory unit 906, a storage unit 914, an output device 916 and an image capturing device 918, and a bus 920.

The processor 904 may be configured to implement functionality and/or process instructions for execution within the vehicle position monitoring apparatus 902. The processor 904 may be capable of processing instructions stored in the memory unit 906 or instructions stored on the storage unit 914. The processor 904 may include any one or more of a processor, a controller, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or equivalent discrete or integrated logic circuitry. Additionally, the functions attributed to the processor 904, in this disclosure, may be embodied as software, firmware, hardware or any combination thereof.

The memory unit 906 may be configured to store information within the vehicle position monitoring apparatus 902 during operation. The memory unit 906 may, in some examples, be described as a computer-readable storage medium. The memory unit 906 may be described as a volatile memory, meaning that the memory does not maintain stored contents when the computer is turned off. Examples of volatile memories include random access memories (RAM), dynamic random access memories (DRAM), static random access memories (SRAM), and other forms of volatile memories known in the art. In some examples, the memory unit 906 may be used to store program instructions for execution by the processor 904.

For example, the memory unit 906 includes a candidate point determination module 908, a lane detection module 910 and a positioning monitoring module 912 stored in the form of program instructions for execution by the processor 904. The candidate point determination module 908, the lane detection module 910 and the lane departure warning module 912 can be implemented as software, hardware, or some combination of software and hardware. For example, the candidate point determination module 908, the lane detection module 910 and the lane departure warning module 912 could be implemented as a part of an application specific integrated circuit (ASIC).

According to the present invention, the candidate point determination module 908 cause the processor 904 to generate scan lines in a region of interest of an image of a road and determine a plurality of candidate points in the image based on the scan lines. The lane detection module 910 cause the processor 904 to determine sets of candidate points having identical slopes and detect lane markings on the road based on the determined sets of candidate points. The lane departure warning module 912 cause the processor 904 to determine whether the vehicle is within the detected lane markings and generate an alert notification on the output device 916 if the vehicle is departed from the lane marked on the road.

The storage unit 914 may include one or more computer-readable storage media. The storage device 914 may include non-volatile storage elements. Examples of such non-volatile storage elements may include magnetic hard discs, optical discs, floppy discs, flash memories, or forms of electrically programmable memories (EPROM) or electrically erasable and programmable (EEPROM) memories. In addition, the storage device 914 may, in some examples, be considered a non-transitory storage medium. The term “non-transitory” may indicate that the storage medium is not embodied in a carrier wave or a propagated signal. However, the term “non-transitory” should not be interpreted to mean that the storage device 914 is non-movable. In some examples, the storage device may 914 be configured to store larger amounts of information than the memory unit 906. In certain examples, a non-transitory storage medium may store data that can, over time, change (e.g., in Random Access Memory (RAM) or cache). The image capturing apparatus 918 is configured for capturing images of a road and storing the captured images in the storage unit 914.

Figure 10 illustrates a process flowchart 1000 of an exemplary method of monitoring position of a vehicle on a road, according to one embodiment. The process 1000 facilitates to determine position of the vehicle with respect to lane markings on the road and generate an alert notification if the vehicle is not within the lane marked on the road.

At step 1002, an image of a road is captured by the image capturing apparatus 918 in the real time. At step 1004, the image of the road is converted into a gradient image. At step 1006, a region of interest containing lane region in the image is defined.

At step 1008, a plurality of scan lines within the region of interest of the gradient image are generated. For example, the scan lines may be horizontal line drawn within the region of interest. At step 1010, a plurality of candidate points are determined at the intersection of one or more scan lines and pixels in the gradient image having high intensity values. For example, the pixels corresponding to the lane marking have high intensity values in the gradient image as compared to the pixels corresponding to the road surface. Hence, it is possible to detect intersection of the lane marking and the scan lines. Each intersection of the lane marking and a scan line is considered as a candidate point for detection of a lane.

At step 1012, an origin is selected from multiple origins in the gradient image. For example, an origin (0,0) is selected for determining lane markings. At step 1014, a slope value is computed for each of candidate points with respect to the selected origin. At step 1016, a set of candidate points having identical slope value with respect to the selected origin are identified from the plurality of candidate points. In other words, at step 1016, the candidate points which are collinear to each other are identified as a set of candidate points. At step 1018, it is determined whether a set of candidate points are determined for all origins. If the set of candidate points are not determined for all the origins, then the process repeats the steps 1012 to 1018 till a set of candidate points are determined for all the origins.

If a set of candidate points are determined for all origins, then at step 1020, lane markings on the road with respect to the position of the vehicle are determined based on the sets of candidate points corresponding to multiple origins. In one embodiment, a set of candidate points on either side of the vehicle are determined from the multiple sets of candidate points. In this embodiment, a straight line passing though the set of candidate points is plotted. The straight line corresponds to the lane marking on either side of the vehicle.

At step 1022, it is determined whether the vehicle is within the lane marked on the road based on the position of the vehicle with respect to the lane markings. If it is determined that the vehicle is not within the lane, then at step 1024, an alert notification indicating that the vehicle has departed from the detected lane markings is generated. In one embodiment, a warning sound indicating that the vehicle has departed from the detected lane markings is generated via audio signals. In another embodiment, the position of the vehicle with respect to the detected lane markings on the road is displayed on the output device 916 (e.g., a display unit). In yet another embodiment, the position of the vehicle with respect to the detected lane marking on the road is provided via a haptic alert. One skilled in the art may envision that various other warning systems may be used to indicate that the vehicle has departed from the detected lane markings.

Figures 11-15 are schematic representations illustrating an exemplary process of detecting position of a vehicle with respect to lanes marked on a road, according to one embodiment. In Figure 11, an image 1102 of a road 1106 on which a vehicle 1104 is moving is shown. When the image 1102 is inputted, the candidate point determination module 908 generates scan lines 1108 within a region of interest in the image 1102. The scan lines are imaginary horizontal lines crossing lane markings in the image 1102. The scan lines enable the candidate point determination module 908 to identify one or more candidate points for detecting lane markings. Referring to Figure 12, the candidate point determination module 908 determines intersection points of scan lines and pixels of the image 1102 having high intensity values as candidate points 1202. The pixels of the image 1102 having intensity values correspond to lane markings on the road.

Once the candidate points 1202 are identified in the image 1102, the lane detection module 910 determines one or more sets of candidate points 1302, where each set of candidate points 1302 contains candidate points with identical slope values with respect to a particular origin. For determining set of candidate points 1302, the lane detection module 910 selects an origin among multiple origins along X axis and/or Y axis. Further, the lane detection module 910 determines slope value for each of the candidate points in the image 1102 with respect to the selected origin. Then, the lane detection module 910 determines a set of candidate points 1302 which are collinear, i.e., having identical slope with respect to the selected origin. The process is repeated for all of multiple origins. Consequently, the lane detection module 910 obtains multiple sets of candidate points 1302 corresponding to the multiple origins as shown in Figure 13.

The lane detection module 910 plots a straight line passing through each set of candidate points 1302. The lane detection module 910 divides the region of interest into halves and selects straight lines with specific slope direction as a candidate lines for lane marking. Further, the lane detection module 910 validates the candidate lines to determine presence of lane on the road 1106. For all the selected candidate lines, certain features of the lines are evaluated to validate them as lane markings. Some of the features evaluated include distance between the lanes, whether the lanes meet at the vanishing point, the angle between the lines, dark white patch of the stretch, etc. A minimum of two of these features have to be met in order to validate the selected candidate lines as lane markings. It should be noted that, any other features known in the art may be utilized to validate the candidate lines as the lane markings. In this manner, the lane detection module 910 detects lane markings in the image 1102. As shown in Figure 14, the lane detection module 910 determines lane markings 1402 on left and right side of the vehicle 1104. Further, the lane detection module 910 determines whether the position of the vehicle 1104 is within the determined lane markings 1402. If the lane detection module 910 determines that the vehicle 1104 has departed from the lane markings 1402, then the lane detection module 910 generates an alert notification indicating departure of the vehicle 1104 from the determined lane markings 1402 on the road 1106. As shown in Figure 15, since the vehicle 1104 has departed outside the lane markings 1402, the lane detection module 910 generates an alert notification to the driver of the vehicle 1104.

Although, the present invention is described with respect to lane marking system, one skilled in the art would envision that the present invention for straight line detection can be also used in various other applications such as but not limited to sign board detection, data statistics, various regression analysis techniques, graphics library, license plate recognition, and character recognition. For example, for detecting a sign board on a road side in an image, region of interest in the image on either sides of the road is selected and contours is identified in the selected region of interest using canny edge detector. Once the contours are identified, the identified contours in the region of interest are codified using chain code. Further, the closed or almost closed contours are selected for candidate point determination, and candidate points corresponding to the filtered contours are determined. Furthermore, best fit lines are determined based on the slope of candidate points with respect to each of the multiple origins, and straight lines which have similar length, width and aspect ratio are identified from the best fit lines. Accordingly, the sign board is detected in the image based on the identified straight lines. Additionally, the sign board is displayed on a display unit fitted in the vehicle.

The present embodiments have been described with reference to specific example embodiments; it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the various embodiments. Furthermore, the various devices, modules, and the like described herein may be enabled and operated using hardware circuitry, for example, complementary metal oxide semiconductor based logic circuitry, firmware, software and/or any combination of hardware, firmware, and/or software embodied in a machine readable medium. For example, the various electrical structure and methods may be embodied using transistors, logic gates, and electrical circuits, such as application specific integrated circuit.