Image analysis – Color image processing – Pattern recognition or classification using color
Reexamination Certificate
2000-09-29
2004-08-17
Chang, Jon (Department: 2623)
Image analysis
Color image processing
Pattern recognition or classification using color
C382S201000, C382S202000
Reexamination Certificate
active
06778699
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of estimating the vanishing points of an image. More specifically, the present invention relates to applying a method to accurately locate the vanishing point.
BACKGROUND OF THE INVENTION
A vanishing point is a result of the perspective projection of a three dimensional scene onto a two dimensional image plane. A vanishing point refers to the point in the image plane (that is, a two dimensional projection of the three dimensional scene) where parallel lines in the scene meet. Vanishing points generally only have relevance for images containing a structure having at least two line segments. Consequently, line segments that are relevant to vanishing points may be constructed from images that include man-made structures.
Vanishing point detection in the field of camera technology is important because detecting the vanishing point of an image can be a significant first step in correcting for image rotation caused by a user's inability to hold the camera level. Several ideas and methods on how to detect vanishing points have been proposed and attempted.
Barnard, in “Interpreting Perspective Images”,
Artificial Intelligence
, vol. 21 first proposed the idea of using a Gaussian sphere as an accumulator space for vanishing point detection. The “plane of interpretation” is identified as the plane passing through the center of the sphere (the origin or focal point of the optical system) and both ends of a particular line segment. Each bin of the Gaussian sphere accumulator that falls on the intersection of the Gaussian sphere and the interpretation plane (this intersection forms a great circle) is incremented. After this procedure is completed for all line segments, the vanishing points may be found by searching for local maxima on the sphere. The position of the local maximum represents the vanishing point vector. The location of the vanishing point in the image plane may be determined by projecting this vector back onto the image plane. One difficulty with Barnard's approach is that the partitioning of the Gaussian sphere causes non-uniform bin sizes that affect the final results.
Magee and Aggarwal, in “Determining Vanishing Points From Perspective Images,”
Computer Vision, Graphics, and Image Processing
, vol. 26 propose a vanishing point detection scheme that is similar to Barnard's method, primarily because a Gaussian sphere is again utilized. However, in this method the Gaussian sphere is not used as an accumulator. In the Magee and Aggarwal method, cross products operations are performed in order to identify the intersections of line segments on the Gaussian sphere, and afterwards a list of all intersections of each pair of line segments is collected. A clustering operation is performed to find common intersections that are identified as possible vanishing points. Also, Magee and Aggarwal show that the algorithm is insensitive to focal length. Their method has several advantages. First, the accuracy of the estimated vanishing point is not limited to the quantization of the Gaussian sphere. Second, Magee and Aggarwal consider each intersection individually. Therefore, an intersection that is not feasible (for example, an intersection that occurs within the endpoints of one of the two component line segments) as a vanishing point may be rejected. This selection of feasible vanishing points is not possible with the accumulator space method of Barnard or Brillault and O'Mahony, which consider only line segments rather than intersections.
Lutton, Maitre, and Lopez-Krahe in “Contribution to the Determination of Vanishing Points Using Hough Transform,”
IEEE Transactions on Pattern Analysis and Machine Intelligence
, vol. 16, no. 4 introduced a probability mask on the Gaussian sphere in order to compensate for the finite extent of the image. In Barnard's algorithm, the great circle associated with every line segment passes through the projection of the image onto the sphere. This makes the algorithm more likely to detect a vanishing point that falls within the image than outside of the image. The probability mask attempts to account for this effect by considering the probability of two random lines (i.e., noise) intersecting at any given place on the Gaussian sphere. However, the authors fail to take into consideration the prior probability of the actual vanishing point locations, and instead assume that all vanishing points are equally likely. This assumption is far from the actual case. In addition, the authors describe an effort to account for errors in line segment identification. Rather than incrementing only the bins falling on the great circle, the authors propose incrementing the bins falling in a swath about the great circle.
The swath size is determined by possible interpretation planes passing through the endpoints of the line segments. Consequently, longer line segments that have a higher degree of certainty, will cause incrementalism over a more narrow swath on the Gaussian sphere. A weight based on the line length is distributed evenly among all bins contained in the swath. However, this weighting scheme is based upon assumption rather than actual ground truth data. As an additional algorithm feature, three vanishing points corresponding with the three orthogonal dimensions are simultaneously detected. This feature adds robustness for scenes containing all dimensions, although, many scenes contain structure without containing all three dimensions. Additionally, this algorithm feature requires the use of an accurate focal length. Finally, this algorithm cannot calculate any single intersection of two line segments, thus omitting some of the advances made by Magee and Aggarwal.
Therefore, a need exists for overcoming the above-described drawbacks. In particular, a need exists for a method to determine the most likely vanishing point location while considering the collection of numerous intersections and conditional probabilities.
SUMMARY OF THE INVENTION
The above noted need is met according to the present invention by providing 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 &ngr;
E
that corresponds to the determined local maximum such that an estimated location of the vanishing point about the estimated vanishing point vector &ngr;
E
results.
As a new approach to vanishing point detection, ground truth data is utilized to establish conditional probabilities in a cross product scheme similar to Magee's. Features pertaining to the two line segments forming each intersection are used to determine the conditional probability that the intersection is coincident to a ground truth vanishing point. Weighted clustering is then performed to determine the most likely vanishing point location, considering the collection of intersections and conditional probabilities. This algorithm is based upon the ground truth vanishing point data derived from the 86 images in a training set. This algorithm represents the first reported use of ground truth data for training an automatic vanishing point detection algorithm.
These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings.
REFERENCES:
patent: 6011585 (2000-01-01), Anderson
patent: 6304298 (2001-10-01), Steinberg et al.
patent: 03238566 (1991-10-01), None
Collins et al. “Vanishing Point Calculation as a Statistical Inference on the Unit Sphere.” Proc. Third Int. Conf. on Computer Vision, Dec. 4, 1990, pp. 400-403.*
McLean et al. “Vanishing Point Detection by Line Clustering.”
Chang Jon
Eastman Kodak Company
Shaw Stephen H.
LandOfFree
Method of determining vanishing point location from an image does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of determining vanishing point location from an image, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining vanishing point location from an image will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329993