Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-10-21
2003-03-11
Au, Amelia M. (Department: 2723)
Image analysis
Pattern recognition
Feature extraction
C382S199000
Reexamination Certificate
active
06532304
ABSTRACT:
CROSS-REFERENCES TO RELATED APPLICATIONS
This Application is related to the following Application:
Warping Geometric Objects, by Hongche Liu and Shyam Kuttikkad, filed the same day as the present application.
The above-cited Application is incorporated herein by reference.
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention is directed toward analyzing sets of geometric objects.
2. Description of Related Art
Physical areas are often modeled using geometric objects. Examples of such physical areas include a geographic region and a building's floor plan. One example of a model using two-dimensional geometric objects is a map of a geographic region, such as a city.
FIG. 1
illustrates a map that is formed by a set of geometric objects. The objects in
FIG. 1
include points
60
-
70
, arcs
80
-
91
, and polygons
50
-
51
. Each arc
80
-
91
represents a road and is bounded at each of its ends by a point. For example, arc
80
is bounded at one end by point
60
and at another end by point
62
. Each arc can be co-bounded by one or two polygons. For example, arc
86
is co-bounded by polygons
50
and
51
, while arc
85
is only co-bounded by polygon
50
. Each polygon
50
and
51
is formed by a set of arcs that define the boundary of the polygon. For example, polygon
50
is defined by boundary arcs
81
,
82
,
83
,
84
,
85
, and
86
.
Different models of the same physical area often provide different quality details about the area. Differences between models of the same area can occur, because models can be distorted, so that all the features in the model are not depicted in their true positions. Such distortions are often localized, with different regions of the model being distorted differently. In paper models, distortion can be caused by paper stretching, folding, and scaling. In electronic models, distortion can be caused when the model is transformed into digital form.
By repositioning different models of the same area, a more accurate new model can be created.
FIG. 2
illustrates a map
100
of an area that is neither very smooth nor accurate.
FIG. 3
shows a more accurate map
110
of the same area as map
100
. The differences between maps
100
and
110
are illustrated in
FIG. 4
, which shows an overlay
120
of maps
100
and
110
. A repositioning process can be performed to utilize the details of both maps
100
and
110
to obtain an improved new map.
The use of repositioning is particularly beneficial and practical in generating electronic maps. There are often many different maps available for a particular region. By making use of a computer to reposition the many maps that are available for a region, a very accurate new map can be generated in a time efficient and cost efficient manner.
When performing repositioning, matching points in the models being repositioned are identified and employed to generate a transformation model for warping points in one of the models into a new model. In order to determine matching points, matching arcs in the models are first identified and then used in a process for identifying the matching points.
Traditional processes for identifying matching arcs typically use attributes associated with the arcs to identify matches. For maps, one example of such as attribute is a street name that is associated with an arc. In such an example, matching arcs can be identified by finding arcs with matching street names. However, many models do not provide attributes for each arc. As a result, less matching arcs and matching points are identified, thereby compromising the repositioning result.
Accordingly, there is a need for identifying matching arcs in a set of models without relying on attributes being associated with the arcs.
SUMMARY OF THE INVENTION
The present invention, roughly described, provides for identifying matching arcs in sets of geometric objects, such as a pair of electronic maps, without relying on attributes being assigned to the arcs. Matching arcs are identified by making use of the geometric and topological information that is associated with each set of geometric objects.
An arc in a first set of geometric objects is identified as matching an arc in a second set of geometric objects, when the arc in the first set is co-bounded on both sides by polygons which match the corresponding co-bounding polygons of the arc in the second set. Accordingly, an initial determination is made of which polygons in the first set of geometric objects match polygons in the second set of geometric objects.
Polygon matching is performed by determining a set of similarity metrics for each pairing of a polygon in the first set of geometric objects and a polygon in the second set of geometric objects. The polygons with the greatest degree of similarity, based on the set of similarity metrics, are then identified as matching, provided a minimum degree of similarity is indicated by the set of similarity metrics. In accordance with the present invention, similarity metrics for proximity, area, shape and rotation are determined. Further, each of these metrics are determined in an isolated fashion, so that no other metric is reflected in the metric being measured.
Once matching arcs are identified, they are assigned attributes. In one embodiment of the present invention, the assigned attribute is a label formed by a concatenation of assigned unique identifiers for each co-bounding matched polygon. In an alternate embodiment, the assigned attribute is a label, such as a street name. The assigned attributes enable traditional attribute-based arc matching followed by node matching to utilize the identified arcs for locating matching points in the first set of geometric objects and the second set of geometric objects.
These and other objects and advantages of the present invention will appear more clearly from the following description in which the preferred embodiment of the present invention has been set forth in conjunction with the drawings.
REFERENCES:
patent: 4805127 (1989-02-01), Hata et al.
patent: 5486822 (1996-01-01), Tenmoku et al.
patent: 5845228 (1998-12-01), Uekawa et al.
patent: 5878164 (1999-03-01), Brown et al.
patent: 6026189 (2000-02-01), Greenspan
Zhu et al, “FORMS: A Flexible Object Recognition and Modelling System”; IEEE Paper ISBN: 0-8186-7042-8, pp. 465-472, Jun. 1995.*
Cakmakov et al, “A Model for Polygon Similarity estimation”; IEEE Paper ISBN: 0-8186-2760-3, pp. 701-705, May 1992.*
Lu et al, “Hierarchical Shape Recognition Using Polygon Approximation and Dynamic Alignment”; IEEE Paper CH2561-9, vol. 2, pp. 976-979, Apr. 1988.*
Shum et al, “On 3D Shape Similarity”; IEEE Paper ISBN: 0-8186-7258-7, pp. 526-531, Jun. 1996.*
Marshall Bern and David Epstein, Mesh Generation and Optimal Triangulation, Computing and Euclidean Geometry, Ding-Zhu Du and Frank Hwang editors, World Scientific, Singapore, pp. 1-78, 1992.
Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, First Workshop on Applied computational Geometry (Philadelphia, Pennsylvania) pp. 1-10, ACM, May 1996.
Jim Ruppert, A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms 18(3):1-46, May 1995.
Kuttikkad Shyam
Liu Hongche
Au Amelia M.
Dastouri Mehrdad
Fliesler Dubb Meyer & Lovejoy LLP
Tele Atlas North America, Inc.
LandOfFree
Matching geometric objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Matching geometric objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matching geometric objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3054851