12.3.2 Piecewise Segment Matching of Contours

Chapter Contents (Back)
Polygon Matching. Matching, Contours. Matching, Lines. Contour Matching.

McKee, J.W., and Aggarwal, J.K.,
Computer Recognition of Partial Views of Curved Objects,
TC(26), No. 8, August, 1977, pp. 790-800. BibRef 7708
Computer Recognition of Partial Views of Three Dimensional Curved Objects,
ICPR76(499-503). BibRef
And: Univ. of TexasCS TR 171, 1975. Recognize Two-Dimensional Objects. A Curve is represented by a variation of the chain code and matching is performed using this representation. BibRef

Perkins, W.A.,
A Model-Based Vision System for Industrial Parts,
TC(27), No. 2, February 1978, pp. 126-143. Industrial Applications. BibRef 7802
A Model Based Vision System for Scenes Containing Multiple Parts,
IJCAI77(678-684). Represent curves using orientation vs. length and "correlate" boundary fragments in this representatio. See also INSPECTOR: A Computer Vision System That Learns to Inspect Parts. BibRef

Perkins, W.A.,
Model-Based Inspection System for Component Boards,
PR(17), No. 1, 1984, pp. 135-140.
WWW Link. BibRef 8400
Simplified Model-Based part Locator,
ICPR80(260-263). Correct component, correct position. BibRef

Davis, L.S.,
Shape Matching Using Relaxation Techniques,
PAMI(1), No. 1, January 1979, pp. 60-72. BibRef 7901
Earlier: PRIP77(191-197). Matching, Contours. Relaxation. Match outlines of islands extracted from a map. This program used a spring template description of shapes (outlines or portions of outlines) and a relaxation based search procedure to find the best match. Complete boundaries from a geographic data-base were used to generate the models. Test templates were composed of portions of similar outlines. Both the model and template were formed from a line segment representation of the contour using a given threshold on the curvature of the underlying boundary curve. These curves are then represented by the sequence of angles and the segments between adjacent angles. Each angle forms a sub-template with pairs of these connected by springs. A local match of a pair of template elements (angles) with a pair of model elements results in tension in the spring joining the template elements. The goal is to find the assignment that minimizes the tension in the springs. To find this minimum, a discrete relaxation procedure is used. First an association graph is constructed where a node corresponds to a single template elements to model element pairing with a weight determined by the local evaluation function (spring tension). The links between nodes correspond to pairs of assignments and are included only if the spring tension caused by the assignments is low enough. (The magnitude of the threshold controls how many possible assignments are tried.) Nodes are pruned if the total neighborhood tension is too large. A second edge (arc) filtering procedure removes the links if the global transform generated from the match for each of the nodes are different. Each of these discrete relaxation operations differs from other discrete methods in that links or nodes only must be adequately consistent, not absolutely consistent. These steps produce a pruned association graph with (possibly) several disjoint subgraphs. Each subgraph corresponds to one global transform to align the template with the model object. The best match is determined by evaluating the several final matches using the spring template evaluation function. This matching procedure is invariant to rotation and translation since the angle between segments is the only direction used. The use of approximate consistency allows for small scale changes or distortions. BibRef

Davis, L.S., Rosenfeld, A.,
An Application of Relaxation Labelling to Spring-Loaded Template Matching,
ICPR76(591-597). BibRef 7600

Henderson, T.C.[Thomas C.], Davis, L.S.[Larry S.],
Hierarchical Models and Analysis of Shape,
PR(14), No. 1-6, 1981, pp. 197-204.
WWW Link. BibRef 8100

Davis, L.S.[Larry S.], Henderson, T.C.[Thomas C.],
Hierarchical Constraint Processes for Shape Analysis,
PAMI(3), No. 3, 1981, pp. 265-277. BibRef 8100

Davis, L.S.,
Representation and Recognition of Cartographic Data,
MDP80(169-189). BibRef 8000

Hakalahti, H., Harwood, D., Davis, L.S.,
Two-Dimensional Object Recognition by Matching Local Properties of Contour Points,
PRL(2), 1984, pp. 227-234. BibRef 8400

Ayache, N.J.[Nicholas J.], and Faugeras, O.D.,
HYPER: A New Approach for the Recognition and Positioning of Two-Dimensional Objects,
PAMI(8), No. 1, January 1986, pp. 44-54. BibRef 8601
A New Method for the Recognition and Positioning of 2-D Objects,
ICPR84(1274-1277). BibRef
Earlier: A1 only:
A Model Based Vision System to Identify and Locate Partially Visible Industrial Parts,
CVPR83(492-494). Matching, Contours. Recognize Two-Dimensional Objects. The model and the image are composed of closed contours of industrial parts. These parts can have extra pieces (sprues) and can be overlapping, thus there is a need to match when there are few actual matching segments. The procedure works by first finding a few matches using privileged segments (usually long segments). These starting matches are used to generate a transformation from model to image. The hypothesis is evaluated by finding other segments that match using position along the contour. There are some good things, but it can be made simpler. BibRef

Faugeras, O.D., Ayache, N.J., Faverjon, B.,
A Geometric Matcher for Recognizing and Positioning 3-D Rigid Objects,
CAIA84(218-224). BibRef 8400

Ayache, N.J., Faverjon, B., Boissonnat, J.D., Bollack, B.,
Automatic Handling of Overlapping Workpieces,
ICPR84(837-839). BibRef 8400

Avis, D., Elgindy, H.,
A Combinatorial Approach to Polygon Similarity,
IT(29), 1983, pp. 148-150. BibRef 8300

Berman, S., Parikh, P., Lee, C.S.G.,
Computer Recognition of Two Overlapping Parts Using a Single Camera,
Computer(18), No. 3, March 1985, pp. 70-80. BibRef 8503

Turney, J.L., Mudge, T.N., and Volz, R.A.,
Recognizing Partially Occluded Parts,
PAMI(7), No. 4, July 1985, pp. 410-421. (Univ. of Mich.) Recognize Two-Dimensional Objects. Not really contour matching, but they use binary templates represented as boundaries. The first step is to determine the salient features and weight these more strongly in the match, a form of template matching. BibRef 8507

Vernon, D.[David],
Two-Dimensional Object Recognition Using Partial Contours,
IVC(5), No. 1, February 1987, pp. 21-27.
WWW Link. BibRef 8702

Wallace, A.M.,
Matching Segmented Scenes to Models Using Pairwise Relationships between Features,
IVC(5), No. 2, May 1987, pp. 114-120.
WWW Link. BibRef 8705

Paglieroni, D.W.[David W.], Jain, A.K.[Anil K.],
Fast Classification Of Discrete Shape Contours,
PR(20), No. 6, 1987, pp. 583-598.
WWW Link. BibRef 8700

Manay, S.[Siddharth], Paglieroni, D.W.[David W.],
Matching Flexible Polygons to Fields of Corners Extracted from Images,
Springer DOI 0708

Gorman, J.W., Mitchell, O.R., and Kuhl, F.P.,
Partial Shape Recognition Using Dynamic Programming,
PAMI(10), No. 2, March 1988, pp. 257-266.
IEEE DOI Yet another contour recognition experiment. BibRef 8803

Kamgar-Parsi, B.[Behzad], Margalit, A.[Avraham], Rosenfeld, A.[Azriel],
Matching General Polygonal Arcs,
CVGIP(53), No. 2, March 1991, pp. 227-234.
WWW Link. BibRef 9103
And: Erratum: CVGIP(54), No. 2, September 1991, pp. 307.
WWW Link. Break into equal length line segments and match using sum of squared distances between corresponding points on the arcs. Use for finding the piece of a long arc that matches a short arc. BibRef

Rao, N.S.V., Wu, W., Glover, C.W.,
Algorithms for Recognizing Planar Polygonal Configurations Using Perspective Images,
RA(8), No. 4, August 1992, pp. 480-485. Assume it is planar and matching is simplified. BibRef 9208

Ueda, N., and Suzuki, S.,
Learning Visual Models from Shape Contours Using Multiscale Convex/Concave Structure Matching,
PAMI(15), No. 4, April 1993, pp. 337-352.
IEEE DOI BibRef 9304
Automatic Shape Model Acquisition Using Multiscale Segment Matching,
ICPR90(I: 897-902).
IEEE DOI Extract the salient features from a set of samples to produce a prototype of the object. BibRef

Milios, E.E.[Evangelos E.],
Shape Matching Using Curvature Processes,
CVGIP(47), No. 2, August 1989, pp. 203-226.
WWW Link. Matching with some deformation. Represent the shape as concave and convex segments of the contour, match segments using dynamic programming, recover the differences. BibRef 8908

Mitiche, A.[Amar], and Aggarwal, J.K., (UTexas),
Contour Registration by Shape-Specific Points for Shape Matching,
CVGIP(22), No. 3, June 1983, pp. 396-408.
WWW Link. Registration is used as a preprocessor for contour shape matching. The translation, rotation and scale parameters are computed by assuming certain points are equivalent, e.g. centroid, points farthest (nearest) from centroid, etc. BibRef 8306

della Ventura, A., Ongaro, P., and Schettini, R.,
Search and Replace of 2-D Objects in Digital Images,
VF91(205-212). Mostly an application of matching. BibRef 9100

Lu, C.C., Dunham, J.G.,
Shape-Matching Using Polygon Approximation and Dynamic Alignment,
PRL(14), No. 12, December 1993, pp. 945-949. BibRef 9312

Boissonnat, J.D.,
Stable Matching Between a Hand Structure and an Object Silhouette,
PAMI(4), No. 6, November 1982, pp. 603-612. First compute the possible stable positions (for 1 finger) for all possible local shapes (restricted set) and the conditions for a valid grasp for the given gripper configuration. Experiments on the bin of parts problem using range data. Good. BibRef 8211

Kashyap, R.L., and Oomman, B.J.,
A Geometrical Approach to Polygonal Dissimilarity and Shape Matching,
PAMI(4), No. 6, November 1982, pp. 649-654. BibRef 8211
And: ICPR82(472-479). Two metrics, first overlap error, second minimum integral error between polygons. Align 2 edges (at midpoints) go around the figure and compute the difference between the corresponding points in each (each step is the same proportion of the border length). BibRef

Smith, S.P.[Stephen P.], Jain, A.K.[Anil K.],
Chord Distributions for Shape Matching,
CGIP(20), No. 3, November 1982, pp. 259-271.
WWW Link. BibRef 8211
Earlier: PRIP81(168-170). BibRef

You, Z.S.[Zhi-Sheng], Jain, A.K.[Anil K.],
Performance Evaluation of Shape Matching via Chord Length Distribution,
CVGIP(28), No. 2, November 1984, pp. 185-198.
WWW Link. Matching, Evaluation. (Michigan State) This paper uses outlines like those used by Davis (above) but does not refer to his paper. The outlines were distorted and then these results were used in the matching experiments. BibRef 8411

Alt, H., Behrends, B., Blomer, J.,
Approximate Matching of Polygonal Shapes,
AMAI(13), No. 3-4, 1995, pp. 251-265. BibRef 9500

Ventura, J.A., Nain, L.Y., and Wan, W.,
Optimal Matching of General Polygons Based on the Minimum Zone Error,
PRL(16), 1995, pp. 1125-1136. BibRef 9500

Ventura, J.A., Chen, J.M.,
Optimal Matching of Nonconvex Polygons,
PRL(14), 1993, pp. 445-452. BibRef 9300

Cox, P., Maitre, H., Minoux, M., Ribeiro, C.C.[Celso C.],
Optimal Matching of Convex Polygons,
PRL(9), 1989, pp. 327-334. BibRef 8900

Griffin, P.M.,
Correspondence of 2-D Projections by Bipartite Matching,
PRL(9), 1989, pp. 361-366. BibRef 8900

Kamgar-Parsi, B.[Behzad], Kamgar-Parsi, B.[Behrooz],
Matching Sets of 3D Line Segments with Application to Polygonal Arc Matching,
PAMI(19), No. 10, October 1997, pp. 1090-1099.
Matching 3-D Arcs,
Equal length line segments. Representation of arcs. Find shortest arc in long curve. Decompose the contour and match. BibRef

Kamgar-Parsi, B.[Behzad], Kamgar-Parsi, B.[Behrooz],
Algorithms for Matching 3D Line Sets,
PAMI(26), No. 5, May 2004, pp. 582-593.
IEEE Abstract. 0404
Solution of the Finite-to-Finite, Finite-to-Infinite and Infinite-to-Infinite matching problems. Built on See also Matching of 3D Polygonal Arcs. and See also Matching Sets of 3D Line Segments with Application to Polygonal Arc Matching. BibRef

Kamgar-Parsi, B., Kangar-Parsi, B.,
An invariant, closed-form solution for matching sets of 3D lines,
CVPR04(II: 431-436).

Kamgar-Parsi, B.[Behzad], Kamgar-Parsi, B.[Behrooz],
An Open Problem in Matching Sets of 3D Lines,
Line Matching: Solutions and Unsolved Problems,
ICIP01(II: 905-908).

Chen, J.M.,
Optimal Matching of Closed Contours with Line Segments and Arcs,
PRL(18), No. 6, June 1997, pp. 567-574. 9710

Shan, Y.[Ying], Zhang, Z.Y.[Zheng-You],
New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation,
IJCV(46), No. 2, February 2002, pp. 157-171.
DOI Link 0201
Earlier: A2, A1:
A Progressive Scheme for Stereo Matching,
SMILE00(68 ff.).
Springer DOI 0209

Zabulis, X.[Xenophon], Sporring, J.[Jon], Orphanoudakis, S.C.[Stelios C.],
Perceptually relevant and piecewise linear matching of silhouettes,
PR(38), No. 1, January 2005, pp. 75-93.
WWW Link. 0410
Correspondences of landmarks then the boundaries between landmarks. BibRef

Liu, H.R.[Hai-Rong], Cao, S.J.[Sheng-Jiao], Yan, S.C.[Shui-Cheng],
Automated Assembly of Shredded Pieces From Multiple Photos,
MultMed(13), No. 5, 2011, pp. 1154-1162.

Ataer-Cansizoglu, E.[Esra], Bas, E.[Erhan], Kalpathy-Cramer, J.[Jayashree], Sharp, G.C.[Greg C.], Erdogmus, D.[Deniz],
Contour-based shape representation using principal curves,
PR(46), No. 4, April 2013, pp. 1140-1150.
Elsevier DOI 1301
Shape representation and analysis; Curve/contour matching BibRef

Laiche, N.[NacÚra], Larabi, S.[Slimane], Ladraa, F.[Farouk], Khadraoui, A.[Abdelnour],
Curve normalization for shape retrieval,
SP:IC(29), No. 4, 2014, pp. 556-571.
Elsevier DOI 1404
Curvature points BibRef

Meng, Q., Fu, Z., Huang, Y., Shen, M.,
A Fast Matching Approach of Polygon Features,
AnnalsPRS(I-2), No. 2012, pp. 45-49.
HTML Version. 1209

Richardson, T., Wang, S.[Song],
Nonrigid Shape Correspondence Using Landmark Sliding, Insertion and Deletion,
MICCAI05(II: 435-442). BibRef 0500

Wang, S.[Song], Kubota, T., Richardson, T.,
Shape correspondence through landmark sliding,
CVPR04(I: 143-150).
Match a set of landmarks along the contour. BibRef

Rothwell, C.A.,
Reasoning about Occlusions During Hypothesis Verification,
Springer DOI Analysis of matching methods. BibRef 9600

Serra, B.[Bruno], Berthod, M.[Marc],
Optimal Subpixel Matching of Contour Chains and Segments,
IEEE DOI BibRef 9500

Serra, B., Berthod, M.,
Subpixel Contour Matching Using Continuous Dynamic Programming,
IEEE DOI BibRef 9400

Price, K.E.,
Matching Closed Contours,
CVWS84(130-134). BibRef 8400 USC Computer Vision BibRef
And: DARPA84(169-175). BibRef
And: ICPR84(990-992). Closed contours provide many constraints on the possible matches. This paper uses a simple idea to match contours of single objects with collections of these objects that include many occlusions and overlaps. Initial matches are found using only the angle between segments as the feature. Several (3) consecutive matching angles indicate a possible match and give a transformation (rotation and translation) that would align the contour model contour with at least part of the image contour. These possible matches are checked by transforming the model contour and checking for overlaps of the line segments representing the contour in a manner much like the work of Clark( See also Matching of Natural Terrain Scenes. ) or Medioni ( See also Matching Images Using Linear Features. ). BibRef

Zielke, T., von Seelen, W.,
Matching Conic Curve Segments,
IEEE DOI BibRef 9200

Jacobs, D.W.,
GROPER: A Grouping Based Recognition System for Two Dimensional Objects,
CVWS87(164-169). Recognize Two-Dimensional Objects. The lines representing the contours of the overlapping objects are grouped together. The groups are then recognized. Not as good as the contour matching programs. BibRef 8700

van Hove, P.[Patrick],
Model-Based Silhouette Recognition,
CVWS87(88-93). BibRef 8700
Silhouette-Slice Theorems,
CVWS87(295-297). Recognize Two-Dimensional Objects. A tree-search recognition using the contour edges represented as line segments. BibRef

Hashim, R., Martin, W.N.,
Recognizing Shapes via Random Chord Samplings,
CVPR86(637-639). BibRef 8600

Chapter on Registration, Matching and Recognition Using Points, Lines, Regions, Areas, Surfaces continues in
Partial Contour Matching, Piecewise Segments .

Last update:Sep 25, 2017 at 16:36:46