Method of determining vanishing point location from an image

• US 6,778,699 B1
• Filed: 09/29/2000
• Issued: 08/17/2004
• Est. Priority Date: 03/27/2000
• Status: Expired due to Term

• Current Assignee: Monument Peak Ventures, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Eastman Kodak Company
• Inventors: Gallagher, Andrew C.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/675,826
• Time in Patent Office: 1,418 Days
• Field of Search: 382/201, 382/202, 382/162, 382/165, 382/100, 345/419
• US Class Current: 382/165
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components

Abstract

A method of determining a vanishing point related to an image, the method includes the steps of: detecting line segments in the image; determining intersections from pairs of line segments; assigning a probability to each intersection of the pairs of line segments; determining a local maximum corresponding to a plurality of probabilities; and outputting an estimated vanishing point vector ν_E that corresponds to the determined local maximum such that an estimated location of the vanishing point about the estimated vanishing point vector ν_E results.

Claims

1. A method of determining a vanishing point related to an image, the method comprises the steps of:

(a) detecting line segments in the image;

(b) determining intersections from pairs of line segments;

(c) assigning a probability to each intersection of the pairs of line segments;

(d) determining a local maximum corresponding to a plurality of probabilities; and

(e) outputting an estimated vanishing point vector ν

E that corresponds to the determined local maximum such that an estimated location of the vanishing point about the estimated vanishing point vector ν

_E results.

2. The method as recited in claim 1, wherein the step of determining a local maximum further comprises the steps of:

(i) clustering the intersections using the plurality of probabilities as weights to generate cluster means;

(ii) determining the local maximum corresponding to the plurality of cluster means; and

(iii) outputting the estimated vanishing point location from the local maximum corresponding to the plurality of cluster means.

3. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value that is related to a color of the line segment.

4. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value that is related to line segment length.

5. The method as recited in claim 4, wherein the feature value is the line segment length provided by a smallest line segment.

6. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value that is related to coordinates of the intersection.

7. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value that is related to a difference in angle of the pairs of line segments.

8. The method as recited in claim 3, wherein the feature value is related to a difference between an average color of the line segments.

9. The method as recited in claim 8, wherein the feature value is related to an angle between a neutral axis and a vector connecting the average color of the line segments.

10. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value coefficient related to the probability that the intersection is coincident with an accurate vanishing point having a correlating greater probability, wherein the feature value is greater.

11. The method as recited in claim 1, wherein the step of assigning a probability includes the step of calculating a feature value coefficient related to the probability that the intersection is coincident with an accurate vanishing point having a correlating lesser probability, wherein the feature value is lesser.

12. The method as recited in claim 1, wherein the step of assigning a probability further comprises the steps of:

(i) providing at least F_Hij feature value coefficients, wherein

(ii) multiplying the at least F_Hij feature value coefficients; and

(iii) determining an overall feature value coefficient.

13. The method recited in claim 12, wherein the step of assigning a probability further comprising the steps of:

(iv) selecting a cluster of high feature value coefficients from the intersection; and

(v) locating the vanishing point using the cluster.

21. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 1.

22. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 2.

23. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 3.

24. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 4.

25. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 5.

26. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 6.

27. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 7.

28. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 8.

29. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 9.

30. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 10.

31. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 11.

32. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 12.

33. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 13.

14. A method of determining the vanishing point related to an image, the method comprising the steps of:

a) determining line segments in the image;

b) measuring color features related to differences in color found between pairs of line segments; and

c) applying the color features to locate the vanishing point.

15. The method as recited in claim 14, wherein the step of applying color features further comprises the steps of:

(i) determining intersections from pairs of line segments; and

(ii) applying the color features and the intersections to output a vanishing point location.

16. The method as recited in claim 15, wherein the step of applying color features further comprises the steps of:

(i) assigning a probability, based on the color features, to each of the intersecting pairs of line segments; and

(ii) determining a local maximum corresponding to each probability assigned to the intersecting pairs of line segments, and outputting an estimated vanishing point location.

34. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 14.

35. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 15.

36. A computer storage medium having instructions stored therein for causing a computer to perform the method of claim 16.

17. A system for locating a vanishing point in a photographic image, comprises:

a) a line segment detector for outputting a list of line segments;

b) an intersection computer for finding an intersection of each possible pair of line segments in the list of line segments;

c) an intersection probability determiner for assigning a posterior probability to the intersection;

d) a clusterer for inputting the intersection and corresponding probability, and performing a clustering operation using the probability as weight to determine a cluster means;

e) a maximum finder for considering a fixed region size about the cluster means and determines a corresponding score; and

f) a line segment assignor for assigning line segments to a vanishing point vector such that the location of the vanishing point is found.

18. The system claimed in claim 17, wherein the line segment detector further comprises:

(i) a gradient magnitude computer for operating upon a digital image channel in order to compute a squared gradient magnitude at each location in the digital image channel;

(ii) a threshold applicator for determining edges of a digital image based on a threshold value;

(iii) a median applicator for applying a binary map of edge pixels to remove spurious signals;

(iv) a gradient orientation calculator, wherein a gradient orientation value is determined for each edge location in a cleaned edge map;

(v) a gradient orientation binner, wherein the gradient orientation binner quantifies the gradient orientation value to form a binned gradient image channel;

(vi) a connected components applicator for finding spatially connected regions of pixels with a common gradient orientation bin value;

(vii) a feature extractor, wherein features concerning a line support region are computed; and

(viii) a feature threshold applicator, wherein line segments that are of low quality are removed.

19. The system claimed in claim 17, wherein the intersection computer further comprises:

(i) a unit normal calculator, wherein the unit normal calculator appends a unit normal to features associated with each given line segment;

(ii) an intersection finder, wherein the intersection finder determines a Gaussian vector representation of the intersection of any two line segments; and

(iii) a reliability checker, wherein the intersection that cannot aid in determining the vanishing point is excluded.

20. The system claimed in claim 17, wherein intersection probability assignor further comprises:

(i) a plurality of feature calculators, wherein a plurality of features are calculated for each intersection;

(ii) a plurality of probability calculators for determining a plurality of posterior probabilities; and

(iii) a probability combiner, wherein the plurality of posterior probabilities are combined.