Method and device for detecting straight line

• US 9,449,245 B2
• Filed: 10/29/2014
• Issued: 09/20/2016
• Est. Priority Date: 02/22/2014
• Status: Active Grant

• Current Assignee: Xiaomi Inc. (Xiaomi Corp.)
• Original Assignee: Xiaomi Inc. (Xiaomi Corp.)
• Inventors: Wang, Baichao, Wang, Lin, Chen, Zhijun
• Primary Examiner(s): Bayat, Ali
• Application Number:
  US14/526,521
• Publication Number:
  US 20150242699A1
• Time in Patent Office: 692 Days
• Field of Search: 382/170
• US Class Current: 1/1
• CPC Class Codes: G06V 10/443 by matching or filtering
• 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/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis

Abstract

The present disclosure relates to a method and a device for detecting a straight line. The method includes: acquiring a Histogram of Oriented Gradients (HOG) feature set for each respective pixel point in an image, wherein the HOG feature set is configured to reflect straight line characteristics of a localized portion where the pixel point locates; determining at least one candidate direction of a straight line to be detected according to the HOG feature sets of the respective pixel points; and detecting a direction and a position of the straight line precisely according to the candidate direction. The present disclosure efficiently avoids the errors caused by binarization, and increases the accuracy of the detection of straight line.

Claims

1. A method for detecting a straight line, comprising:

acquiring a Histogram of Oriented Gradients (HOG) feature set for each respective pixel point in an image, wherein the HOG feature set is configured to reflect straight line characteristics of a localized portion where the pixel point locates;

determining at least one candidate direction of a straight line to be detected according to the HOG feature sets of the respective pixel points;

generating at least one scan line paralleled to the candidate direction for each of the candidate directions;

calculating a matching distance of each scan line respectively, wherein the matching distance of the scan line is configured to reflect a degree of proximity of the scan line to the straight line to be detected;

selecting the scan line having a minimum matching distance as a candidate straight line; and

detecting the direction and the position of the straight line to be detected according to the candidate straight line.

2. The method according to claim 1, wherein acquiring the HOG feature set for each respective pixel point comprises:

calculating an oriented gradient set g(i, j) of the pixel point, for each respective pixel point (i, j), wherein the oriented gradient set g(i, j) includes oriented gradient values of the pixel point in K directions, and an oriented gradient value of the pixel point in any direction refers to an absolute value of a difference between a gray value of the pixel point and a gray value of an adjacent pixel point in the direction, wherein K≧

2; and

calculating a HOG feature set h(i, j) of the pixel point according to the oriented gradient set g(i, j) of the pixel point.

3. The method according to claim 2, wherein calculating the HOG feature set h(i, j) of the pixel point according to the oriented gradient set g(i, j) of the pixel point comprises:

calculating local gradient values h_k(i, j) of the pixel point in the K directions respectively, wherein a local gradient value h_k(i, j) in a k direction is equal to a sum of the oriented gradient values of all pixel points within the localized portion where the pixel point locates in the k direction;

calculating an average gradient value h_norm(i, j) of the pixel point, wherein the average gradient value h_norm(i, j) is equal to the square root of the sum of the squares (SRSS) of the respective local gradient values h_k(i, j) of the pixel point;

dividing the local gradient value h_k(i, j) by the average gradient value h_norm(i, j) to obtain a HOG feature h_k(i, j) of the pixel point in the k direction; and

determining a set of HOG features in the K directions as the HOG feature set h(i, j) of the pixel point.

4. The method according to claim 3, wherein the method further comprises:

detecting whether the average gradient value h_norm(i, j) is smaller than a predetermined average value T_norm for each respective pixel point (i, j); and

setting the respective HOG features in the HOG feature set h(i, j) of the pixel point to zero, if the average gradient value h_norm(i, j) is detected to be smaller than the predetermined average value T_norm.

5. The method according to claim 2, wherein determining the at least one candidate direction of the straight line to be detected according to the HOG feature sets of the respective pixel points comprises:

selecting a direction corresponding to a HOG feature having a maximum value in the HOG feature set as a main direction of the localized portion where the pixel point locates;

analyzing statistics of vote numbers of the main directions of the localized portions where the respective pixel points locate in the K directions; and

selecting a direction perpendicular to a direction having a vote number that exceeds a vote threshold as a candidate direction of the straight line to be detected.

6. The method according to claim 1, wherein calculating the matching distance of each scan line respectively comprises:

acquiring n sample points by sampling on the scan line for each of the scan lines, wherein n≧

1;

calculating a matching distance between a HOG feature set for each of the respective sample points and a template HOG feature set in a direction perpendicular to the candidate direction; and

summing matching distances of the n sample points to obtain the matching distance of the scan line.

7. The method according to claim 1, wherein detecting the direction and the position of the straight line according to the candidate straight line comprises:

generating a rectangular region having a predetermined size by using the candidate straight line as a central axis;

selecting u points and v points respectively on two sides of the rectangular region perpendicular to the candidate straight line, and connecting every two points on the two sides to obtain u*v line segments, wherein u≧

1, v≧

1;

calculating a matching distance of each line segment respectively among the u*v line segments, wherein the matching distance of the line segment is configured to reflect a degree of proximity of the line segment to the straight line to be detected; and

selecting a straight line with a line segment having a minimum matching distance as the straight line to be detected.

8. The method according to claim 1, wherein the method further comprises:

detecting whether a second straight line to be detected that meets a first predetermined condition exists for any straight line to be detected in the image, wherein the first predetermined condition includes that the second straight line to be detected and the straight line to be detected have an intersecting point within the image and an angle smaller than an angle threshold value;

adding the second straight line to be detected to a candidate straight line set if the second straight line to be detected that meets the first predetermined condition exists;

detecting whether a third straight line to be detected that meets a second predetermined condition exists for any two of the second straight lines to be detected in the candidate straight line set, wherein the second predetermined condition includes that the third straight line to be detected is different from the straight line to be detected, and the third straight line to be detected intersects both of the two second straight lines to be detected with two intersection points both within the image;

adding a quadrilateral composed of the straight line to be detected, the two second straight lines to be detected and the third straight line to be detected to a candidate rectangle set, if the third straight line to be detected that meets the second predetermined condition exists;

calculating a matching distance of the quadrilateral for each quadrilateral in the candidate rectangle set, wherein the matching distance of the quadrilateral is configured to reflect a degree of proximity of the quadrilateral to a rectangle to be detected, and the matching distance of the quadrilateral is equal to a sum of matching distances of line segments corresponding to four sides of the quadrilateral; and

determining a quadrilateral having a minimum matching distance or a matching distance smaller than a matching threshold value as the rectangle to be detected.

9. A device for detecting a straight line, comprising:

a processor; and

a memory for storing instructions executable by the processor, for performing;

acquiring a Histogram of Oriented Gradients (HOG) feature set for each respective pixel point in an image, wherein the HOG feature set is configured to reflect straight line characteristics of a localized portion where the pixel point locates;

determining at least one candidate direction of a straight line to be detected according to the HOG feature sets of the respective pixel points;

generating at least one scan line paralleled to the candidate direction for each of the candidate directions;

calculating a matching distance of each scan line respectively, wherein the matching distance of the scan line is configured to reflect a degree of proximity of the scan line to the straight line to be detected;

selecting the scan line having a minimum matching distance as a candidate straight line; and

detecting the direction and the position of the straight line to be detected according to the candidate straight line.

10. The device according to claim 9, wherein acquiring the HOG feature set for each respective pixel points comprises:

calculating an oriented gradient set g(i, j) of the pixel point, for each respective pixel point (i, j), wherein the oriented gradient set g(i, j) includes oriented gradient values of the pixel point in K directions, and an oriented gradient value of the pixel point in any direction refers to an absolute value of a difference between a gray value of the pixel point and a gray value of an adjacent pixel point in the direction, wherein K≧

2; and

calculating a HOG feature set h(i, j) of the pixel point according to the oriented gradient set g(i, j) of the pixel point.

11. The device according to claim 10, wherein calculating the HOG feature set h(i, j) of the pixel point according to the oriented gradient set g(i, j) of the pixel point comprises:

calculating local gradient values h_k(i, j) of the pixel point in the K directions respectively, wherein a local gradient value h_k(i, j) in a k direction is equal to a sum of the oriented gradient values of all pixel points within the localized portion where the pixel point locates in the k direction;

calculating an average gradient value h_norm(i, j) of the pixel point, wherein the average gradient value h_norm(i, j) is equal to the square root of the sum of the squares (SRSS) of a sum of squares of the respective local gradient values h_k(i, j) of the pixel point;

dividing the local gradient value h_k(i, j) by the average gradient value h_norm(i, j) to obtain a HOG feature h_k(i, j) of the pixel point in the k direction; and

determining a set of HOG features in the K directions as the HOG feature set h(i, j) of the pixel point.

12. The device according to claim 11, wherein the processor is further configured to performing:

detecting whether the average gradient value h_norm(i, j) is smaller than a predetermined average value T_norm for each respective pixel point (i, j); and

setting the respective HOG features in the HOG feature set h(i, j) of the pixel point to zero, if the average gradient value h_norm(i, j) is detected to be smaller than the predetermined average value T_norm.

13. The device according to claim 10, wherein determining the at least one candidate direction of the straight line to be detected according to the HOG feature sets of the respective pixel points comprises:

selecting a direction corresponding to a HOG feature having a maximum value in the HOG feature set as a main direction of the localized portion where the pixel point locates;

Analyzing statistics of vote numbers of the main directions of the localized portions where the respective pixel points locate in the K directions; and

selecting a direction perpendicular to a direction having a vote number that exceeds a vote threshold as a candidate direction of the straight line to be detected.

14. The device according to claim 9, wherein calculating the matching distance of each scan line respectively comprises:

acquiring n sample points by sampling on the scan line for each of the scan lines, wherein n≧

1;

calculating a matching distance between a HOG feature set for each of the respective sample points and a template HOG feature set in a direction perpendicular to the candidate direction; and

summing matching distances of the n sample points to obtain the matching distance of the scan line.

15. The device according to claim 9, wherein detecting the direction and the position of the straight line according to the candidate straight line comprises:

generating a rectangular region having a predetermined size by using the candidate straight line as a central axis;

selecting u points and v points respectively on two sides of the rectangular region perpendicular to the candidate straight line, and connecting every two points on the two sides to obtain u*v line segments, wherein u≧

1, v≧

1;

calculating a matching distance of each line segment respectively among the u*v line segments, wherein the matching distance of the line segment is configured to reflect a degree of proximity of the line segment to the straight line to be detected; and

selecting a straight line with a line segment having a minimum matching distance as the straight line to be detected.

16. The device according to claim 9, wherein the processor is further configured to perform:

detecting whether a second straight line to be detected that meets a first predetermined condition exists for any straight line to be detected in the image, wherein the first predetermined condition includes that the second straight line to be detected and the straight line to be detected have an intersecting point within the image and an angle smaller than an angle threshold value;

adding the second straight line to be detected to a candidate straight line set if the second straight line to be detected that meets the first predetermined condition exists;

detecting whether a third straight line to be detected that meets a second predetermined condition exists for any two of the second straight lines to be detected in the candidate straight line set, wherein the second predetermined condition includes that the third straight line to be detected is different from the straight line to be detected, and the third straight line to be detected intersects both of the two second straight lines to be detected with two intersection points both within the image;

adding a quadrilateral composed of the straight line to be detected, the two second straight lines to be detected and the third straight line to be detected to a candidate rectangle set, if the third straight line to be detected that meets the second predetermined condition exists;

calculating a matching distance of the quadrilateral for each quadrilateral in the candidate rectangle set, wherein the matching distance of the quadrilateral is configured to reflect a degree of proximity of the quadrilateral to a rectangle to be detected, and the matching distance of the quadrilateral is equal to a sum of matching distances of line segments corresponding to four sides of the quadrilateral; and

determining a quadrilateral having a minimum matching distance or a matching distance smaller than a matching threshold value as the rectangle to be detected.

17. A non-transitory readable storage medium comprising instructions, executable by a processor in a device, for performing a method for detecting a straight line, wherein the method comprises:

acquiring a Histogram of Oriented Gradients (HOG) feature set for each respective pixel point in an image, wherein the HOG feature set is configured to reflect straight line characteristics of a localized portion where the pixel point locates;

determining at least one candidate direction of a straight line to be detected according to the HOG feature sets of the respective pixel points;

generating at least one scan line paralleled to the candidate direction for each of the candidate directions;

calculating a matching distance of each scan line respectively, wherein the matching distance of the scan line is configured to reflect a degree of proximity of the scan line to the straight line to be detected;

selecting the scan line having a minimum matching distance as a candidate straight line; and

detecting the direction and the position of the straight line to be detected according to the candidate straight line.