Image analysis – Applications – Vehicle or traffic control
Reexamination Certificate
2001-01-30
2004-04-27
Patel, Jayanti K. (Department: 2625)
Image analysis
Applications
Vehicle or traffic control
C701S028000
Reexamination Certificate
active
06728392
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data representations of geographic features and more particularly, the present invention relates to a way to measure how closely one geometric shape matches another geometric shape.
The need to compare geometric shapes arises in various applications relating to the use of data representations of geographic features. Some of these applications include vehicle positioning, measuring geographic database accuracy, and road sign recognition. For instance, in a vehicle positioning application, one way to determine the position of a moving vehicle with respect to a map database that represents the road network upon which the vehicle is traveling is to find the best match between the vehicle's path, as determined by processing sensor data, and the data representation of the roads that form the road network upon which the vehicle is traveling.
One standard method for determining geometric distortion (i.e., how much one geometric shape is different from another geometric shape) involves finding the area between the two shapes.
FIG. 1
illustrates this standard method.
FIG. 1
shows a geometric shape labeled “shape A” and another shape labeled “shape B.” In order for this standard process to yield a true measure of distortion, it is required that the shapes be aligned to minimize the area. This alignment is shown in
FIG. 1
by the line labeled “Shape B aligned with Shape A.” However, it is not always clear how to perform this alignment, especially automatically. An alternative is to compute the area for all translations and rotations of the two geometric shapes. The minimum area computed is a measure of the geometric distortion between the two shapes. This process can be time consuming and computationally intensive.
Accordingly, there exists a need for an improved way to compare one geometric shape to another geometric shape.
SUMMARY OF THE INVENTION
To address these and other objectives, the present invention provides a method for comparing geometric shapes to each other. The method includes determination of a rotational variation coefficient. Tangent vectors at corresponding locations along the geometric shapes to be compared are determined and the angle between pairs of tangent vectors for each of these locations is plotted as a function of the distance along the shapes. The variance of the plot around the mean value is the rotational variation coefficient. This process defines a rotational variation metric which indicates how closely the two geometric shapes match.
The rotational variation metric can be used in various applications that use geographic data. The rotational variation metric can be used in vehicle positioning. By using the rotational variation metric to compare the vehicle trajectory determined from sensors to the paths of roads as represented in a map database, the location on the road on which the vehicle is likely to be located can be determined.
The rotational variation metric can be also be used for road sign recognition. The outline of an object in a detected image is compared to a plurality of different road sign shape templates. Using the rotational variation metric, the sign shape template that most closely matches the outline of the object in the detected image indicates the most likely sign.
The rotational variation metric can also be used for evaluating geographic database accuracy. The shapes of data representations of geographic features represented in a geographic database are compared to the ground truth representations of the actual features. The rotational variation metric indicates how closely the geographic database representation of each geographic feature matches the actual geographic feature.
REFERENCES:
patent: 5438517 (1995-08-01), Sennott et al.
patent: 5470233 (1995-11-01), Fruchterman et al.
patent: 5497451 (1996-03-01), Holmes
patent: 5566288 (1996-10-01), Koerhsen
patent: 6029173 (2000-02-01), Meek et al.
patent: 6078849 (2000-06-01), Brady et al.
patent: 6138084 (2000-10-01), Mine
patent: 6224736 (2001-05-01), Miyamoto
patent: 6424736 (2002-07-01), Meitzler et al.
patent: 6441752 (2002-08-01), Fomukong
patent: 6532304 (2003-03-01), Liu et al.
patent: 0 394 517 (1993-06-01), None
patent: 0 807 803 (1997-11-01), None
patent: WO 95/32483 (1995-11-01), None
U.S. patent application Ser. No. 09/729,939, filed Dec. 5, 2000, entitled “Method and System for Representation of Geographic Features in a Computer-Based System”.
U.S. patent application Ser. No. 09/772,587, filed Jan. 30, 2001, entitled “Bowing Coefficient Representation of Curvature of Geographic Features”.
Azarian Seyey
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
Patel Jayanti K.
LandOfFree
Shape comparison using a rotational variation metric and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shape comparison using a rotational variation metric and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shape comparison using a rotational variation metric and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3273317