12.2 Matching Linear Features

12.2.1 2-D Lines with 2-D Structure

Edmonds, J.,
Maximum Matching and a Polyhedron with (0, 1) Vertices,
NBS(68)(b), 1965, pp.125-130. BibRef 6500

Edmonds, J., and Johnson, E.L.,
Matching, Euler Tours and the Chinese Postman,
Math. Programming(5), 1973, pp. 88-124. BibRef 7300

Gips, J.[James],
A syntax-directed program that performs a three-dimensional perceptual task,
PR(6), No. 3-4, December 1974, pp. 189-199.
WWW Version. 0309Analyze mental rotation problem with line drawings. BibRef

Udupa, K.J., Murthy, I.S.N.,
Some new concepts for encoding line patterns,
PR(7), No. 4, December 1975, pp. 225-233.
WWW Version. 0309A sequence of turning and end points. See also New Concepts for Three-Dimensional Shape Analysis. BibRef

Keegan, J.F., Lesk, A.M.,
How Can You Tell if Two Line Drawings Are the Same?,
CGIP(6), No. 1, February 1977, pp. 90-92.
WWW Version. BibRef 7702

Akl, S.G., Toussaint, G.T.,
An Improved Algorithm to Check for Polygon Similarity,
IPL(7), 1978, pp. 127-128. BibRef 7800
Earlier: PRIP78(39-41). BibRef

Shapiro, L.G.[Linda G.],
Inexact matching of line drawings in a syntactic pattern recognition system,
PR(10), No. 5-6, 1978, pp. 313-321.
WWW Version. 0309 BibRef

Medioni, G.G., and Nevatia, R.,
Matching Images Using Linear Features,
PAMI(6), No. 6, November 1984, pp. 675-685. BibRef 8411 USC Computer Vision BibRef
Earlier:
Matching Linear Features of Images and Maps,
DARPA82(103-111). BibRef
And: A1 only: first title: Ph.D.August 1983, BibRef USC Matching, Lines. Relaxation. This system matches two views of a scene (or a map and an image) where there are few geometric distortions--a global transformation is sufficient to align the line segments in the two views. Given two line segments in the model and a match of one of these with a segment in the image, the valid area of the second segment can be restricted to a parallelogram. This is caused by the fact that the segments are allowed to partially match anywhere along their lengths. This parallelogram is used to judge whether a match is valid when another is assumed. Several matches (3) are derived with a relaxation based procedure that finds a kernel of matching segments. This kernel is used to find all the other matching line segments since the segments in the kernel constrain the position of all the other segments in the image. This method was used in model to image matching and image to image matching and can be used in a multi-resolution mode if desired. See also Segment-Based Stereo Matching. BibRef

Kaufman, P., Medioni, G.G., and Nevatia, R.,
Visual Inspection Using Linear Features,
PR(17), No. 5, 1984, pp. 485-491.
WWW Version. BibRef 8400 USC Computer Vision
PDF Version. BibRef
Earlier: CVPR83(496-497). An application of the segment matching technique. BibRef

Medioni, G.G., Huertas, A., and Wilson, M.R.,
Automatic Registration of Color Separation Films,
MVA(4), No. 1, 1991. BibRef 9100 USC Computer VisionFeature based approach to get very accurate alignment. BibRef

Medioni, G.G.[Gerard G.], Wilson, M.R.[Monti R.], Prohaska, T.F.[Timothy F.], Poretta, L.R.[Lynn R.],
Method and apparatus for registering color separation film,
US_Patent4,849,914, July 18, 1989.
WWW Version. BibRef 8907

Wilson, M.R.[Monti R.], Hutchison, V.E.[Victor E.], Bendure, W.J.[William J.], Anderson, F.W.[Frederick W.],
Method and apparatus for registering color separation film 1,
US_Patent4,641,244, February 3, 1987.
WWW Version. BibRef 8702

Medioni, G., Huertas, A., Wilson, M.R.,
The Registar Machine: From Conception to Installation,
WACV92(224-231).
IEEE Abstract. IEEE Top Reference. BibRef 9200 USC Computer Vision BibRef

Medioni, G.,
Matching Regions in Aerial Images,
CVPR83(364-365). BibRef 8300 USC Computer Vision BibRef
Earlier:
Matching High Level Features of an Aerial Image with a Map or Another Image,
CVWS82(113-115). BibRef

Matsuyama, T., Arita, H., and Nagao, M.,
Structural Matching of Line Drawings Using the Geometric Relationship between Line Segments,
CVGIP(27), No. 2, August 1984, pp. 177-194. (Kyoto)
WWW Version. Relationships between pairs of lines are used in the matching process. The relations seem to be sets of three lines which intersect one line. The properties would then be related to this pattern. This may be useful. BibRef 8408

McIntosh, J.H., and Mutch, K.M.,
Matching Straight Lines,
CVGIP(43), No. 3, September 1988, pp. 386-408.
WWW Version. The matching is based on parameters extracted from the regions where the straight line is located (i.e. features of the segments), not on adjacencies, contours, etc. BibRef 8809

Liu, Y.[Yuncai], and Huang, T.S.,
Determining Straight Line Correspondences from Intensity Images,
PR(24), No. 6, 1991, pp. 489-504.
WWW Version. For use of this algorithm: See also Estimation of Rigid Body Motion Using Straight Line Correspondences. See also Rigid Object Motion Estimation from Intensity Images Using Straight Line Correspondences. BibRef 9100

Borgefors, G.[Gunilla],
Hierarchical Chamfer Matching: A Parametric Edge Matching Algorithm,
PAMI(10), No. 6, November 1988, pp. 849-865.
IEEE Abstract. IEEE Top Reference.
WWW Version. BibRef 8811
Earlier:
An Improved Version of the Chamfer Matching Algorithm,
ICPR84(1175-1177). BibRef
Earlier:
Chamfering: A fast method for obtaining approximations of the Euclidean distance in N dimensions,
SCIA83(250-255). Pyramid Structure. Chamfer Matching. Matching, Chamfer. Applies chamfer techniques to a pyramid representation for efficiency. BibRef

Burr, D.J.,
Elastic Matching of Line Drawings,
PAMI(3), No. 6, November 1981, pp. 708-713. BibRef 8111
Earlier: ICPR80(223-228). (Bell Labs). Interesting for a low level Comparison of lines using a local stretching of the segment data. E.g. use for determining edge-edge match in a global system. BibRef

Burr, D.J.,
A Technique for Comparing Curves,
PRIP79(271-277). BibRef 7900

Fritsch, D.S., Pizer, S.M., Morse, B.S., Eberly, D.H., Liu, A.,
The Multiscale Medial Axis and Its Applications in Image Registration,
PRL(15), No. 5, May 1994, pp. 445-452. Medial Axis Transform. BibRef 9405

Cox, I.J., Kruskal, J.B., and Wallach, D.A.,
Predicting and Estimating the Accuracy of a Subpixel Registration Algorithm,
PAMI(12), No. 8, August 1990, pp. 721-734.
IEEE Abstract. IEEE Top Reference.
WWW Version. Discusses different causes of errors and enables the prediction of the match error. BibRef 9008

Cox, I.J., and Kruskal, J.B.,
On the Congruence of Noisy Images to Line Segment Models,
ICCV88(252-258).
IEEE Abstract. IEEE Top Reference. Find the closest line. See the above for an analysis. BibRef 8800

Barrow, H.G., Tenenbaum, J.M., Bolles, R.C., and Wolf, H.C.,
Parametric Correspondence and Chamfer Matching: Two New Techniques for Image Matching,
IJCAI77(659-663). BibRef 7700
And: DARPA77(21-27). Matching, Chamfer. Chamfer matching. The early incomplete chamfer matching paper. Weight the distance from the ideal match, store the values in an image. This is used to guide the search for the best fit. k For the model, a chamfer image is created where the image value is based on the distance to a line in the model (this is the derivation of the name). There is no better reference that I know, this one is poor, but at the time there were fewer journal publications. BibRef

Lai, J.Z.C.,
Sensitivity Analysis Of Line Correspondence,
SMC(25), No. 6, June 1995, pp. 1016-1023. BibRef 9506

Clark, C.S., Conti, D.K., Eckhardt, W.O., McCulloh, T.A., Nevatia, R., and Tseng, D.Y.,
Matching of Natural Terrain Scenes,
ICPR80(217-222). (Hughes). BibRef 8000 USC Computer Vision Matching, Lines. The program matches two views of a scene with natural terrain using the boundaries of dominant objects. The input line segments can be generated by any means, but this paper used objects extracted by a histogram based segmentation procedure that gets some of the more obvious regions. Straight lines segment representations of the regions provide the input to the matching procedure. From three lines in the image, form an initial guess for the match. Evaluate the match by applying the computed transform to all other lines and finding corresponding line segments in the second view. The best match, in terms of the number and quality of the matching segments, provides the global transformation between the two views. BibRef

Clark, C.S., Luk, A., McNary, C.,
Feature Based Scene Analysis and Model Matching,
NATO ASI(), Pattern Recognition and Signal Processing Paris, 1978. Early version of the other Clark et al. papers. BibRef 7800

Clark, C.S., Eckhardt, W.O., McNary, C., Nevatia, R., Olin, K., and van Orden, E.,
High Accuracy Model Matching for Scenes Containing Man-Made Structures,
SPIE(186), Symposium on Digital Processing of Aerial Images, 1979, pp. 54-62. BibRef 7900 USC Computer VisionRelated to the first Clark et al. paper. BibRef

Xie, M.,
Cooperative Strategy for Matching Multilevel Edge Primitives,
IVC(13), No. 2, March 1995, pp. 89-99.
WWW Version. BibRef 9503

Beveridge, J.R., and Riseman, E.M.,
Optimal Geometric Model-Matching under Full 3D Perspective,
CVIU(61), No. 3, May 1995, pp. 351-364.
WWW Version.
Postscript Version. BibRef 9505
Earlier:
Hybrid Weak-Perspective and Full-Perspective Matching,
CVPR92(432-438).
IEEE Abstract. IEEE Top Reference.
Postscript Version. BibRef
Earlier:
Can Too Much Perspective Spoil the View? A Case Study in 2D Affine Versus 3D Perspective Model Matching,
DARPA92(655-663). BibRef
And: COINSTR-91-86, November 1991. BibRef

Beveridge, J.R., Riseman, E.M.,
How Easy Is Matching 2D Line Models Using Local Search?,
PAMI(19), No. 6, June 1997, pp. 564-579.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9708
Postscript Version. BibRef

Beveridge, J.R.[J. Ross], Graves, C.R.[Christopher R.], Steinborn, J.[Jim],
Comparing Random-Starts Local Search with Key-Feature Matching,
IJCAI97(1476-1481).
Postscript Version. BibRef 9700

Beveridge, J.R.,
Local Search Algorithms for Geometric Object Recognition: Finding the Optimal Correspondence and Pose,
UMassTR 93-71, September 1993. BibRef 9309 Ph.D.Thesis.
Postscript Version. BibRef

Whitley, D., Beveridge, J.R., Graves, C., Mathias, K.,
Test Driving Three 1995 Genetic Algorithms: New Test Functions and Geometric Matching,
Heuristics(1), No. 1, 1995, pp. 77-104. BibRef 9500

Collins, R.T., and Beveridge, J.R.,
Matching Perspective Views of Coplanar Structures Using Projective Unwarping and Similarity Matching,
CVPR93(240-245).
IEEE Abstract. IEEE Top Reference. BibRef 9300
And: DARPA93(459-463). BibRef
And: COINS94-06, February 1994. Line segment matching for rectification. BibRef

Beveridge, J.R., Riseman, E.R., Graves, C.R.,
Demonstrating Polynomial Run-Time Growth for Local Search Matching,
SCV95(533-538).
IEEE Top Reference. Colorado State Univ.. U. of Massachusetts. Colorado State Univ.. BibRef 9500

Beveridge, J.R., Weiss, R., and Riseman, E.M.,
Optimization of 2-Dimensional Model Matching,
ICPR90(I: 18-23).
IEEE DOI Reference BibRef 9000
And: DARPA89(815-830). BibRef
And:
Optimization of 2-Dimensional Model Matching Under Rotation, Translation and Scale,
COINSTR-89-57, June 1989. Given a line model and edges in the image, match by a Hough approach over global translation and rotation. This is followed by a local search to find the exact match. The results are good, but the idea is basic. BibRef

Stevens, M.R., Beveridge, J.R.[J. Ross],
Precise Matching of 3-D Target Models to Multisensor Data,
IP(6), No. 1, January 1997, pp. 126-142.
IEEE DOI Reference 9703
Postscript Version. BibRef

Stevens, M.R.[Mark R.], Beveridge, J.R.[J. Ross],
Localized Scene Interpretation from 3D Models, Range, and Optical Data,
CVIU(80), No. 2, November 2000, pp. 111-129. 0012
WWW Version. BibRef

Stevens, M.R.[Mark R.], Beveridge, J.R.[J. Ross],
Integrating Graphics and Vision for Object Recognition,
KluwerOctober 2000, ISBN 0-7923-7207-7.
WWW Version. BibRef 0010

Stevens, M.R., Beveridge, J.R.,
Interleaving 3D Model Feature Prediction and Matching to Suport Multi-Sensor Object Recognition,
ICPR96(I: 607-611).
IEEE DOI Reference 9608 BibRef ARPA96(699-706). (Colorado State Univ., USA)
Postscript Version. And the IUW Version:
Postscript Version. BibRef

Stevens, M.R.,
Reasoning About Object Appearance in the Context of a Scene,
Ph.D.Thesis, Colorado State University, 1999. BibRef 9900

Beveridge, J.R., Graves, C., Lesher, C.E.,
Local Search as a Tool for Horizon Line Matching,
ARPA96(683-686).
Postscript Version. BibRef 9600

Lee, C.H., Joshi, A.,
On Correspondence, Line Tokens And Missing Tokens,
PR(28), No. 11, November 1995, pp. 1751-1764.
WWW Version. BibRef 9511

Bhandarkar, S.M., Suk, M.,
Sensitivity Analysis for Matching and Pose Computation Using Dihedral Junctions,
PR(24), No. 6, 1991, pp. 505-513.
WWW Version. BibRef 9100

Nagao, M.,
Shape Recognition by Human-Like Trial and Error Random Processes,
PRAI(10), 1996, pp. 473-490. BibRef 9600

Lee, H.J., Yu, D.J.,
Line-Based Structural Matching Via Segment Splitting,
PRL(11), 1990, pp. 181-189. BibRef 9000

Christie, S., Kvasnik, F.,
Correlation and Image Recognition with Surface-Scattered Light,
AppOpt(36), No. 14, May 10 1997, pp. 3013-3021. 9706 BibRef

Atalay, V.[Volkan], Yilmaz, M.U.[M. Ugur],
A matching algorithm based on linear features,
PRL(19), No. 9, 31 July 1998, pp. 857-867. BibRef 9807

Pearce, A.R.[Adrian R.], Caelli, T.M.[Terry M.],
Interactively Matching Hand-Drawings Using Induction,
CVIU(73), No. 3, March 1999, pp. 391-403.
WWW Version. BibRef 9903

Park, S.H.[Sang Ho], Lee, K.M.[Kyoung Mu], Lee, S.U.[Sang Uk],
A Line Feature Matching Technique Based on an Eigenvector Approach,
CVIU(77), No. 3, March 2000, pp. 263-283. 0004
WWW Version. BibRef

Zhu, Z.F.[Zhen-Feng], Tang, M.[Ming], Lu, H.Q.[Han-Qing],
A new robust circular Gabor based object matching by using weighted Hausdorff distance,
PRL(25), No. 4, March 2004, pp. 515-523.
WWW Version. 0402Matching edge maps from Gabor edge filter. BibRef

Meikle, S.[Stuart], Amavasai, B.P., Caparrelli, F.,
Towards real-time object recognition using pairs of lines,
RealTimeImg(11), No. 1, February 2005, pp. 31-43.
WWW Version. 0506 BibRef

Du, H.[Hao], Chen, Y.Q.[Yan Qiu],
Rectified nearest feature line segment for pattern classification,
PR(40), No. 5, May 2007, pp. 1486-1497.
WWW Version. 0702Pattern classification; Nearest feature line; Rectified nearest feature line segment; Distribution concentration; Interpolation and extrapolation accuracy BibRef

Trias-Sanz, R.[Roger], Pierrot-Deseilligny, M.[Marc], Louchet, J.[Jean], Stamon, G.[Georges],
Methods for Fine Registration of Cadastre Graphs to Images,
PAMI(29), No. 11, November 2007, pp. 1990-2000.
IEEE DOI Reference 0711Match edges in imprecise graph to precise edges in the image. BibRef

Trias-Sanz, R., Pierrot-Deseilligny, M.,
A region-based method for graph to image registration with an application to cadastre data,
ICIP04(III: 1703-1706).
IEEE DOI Reference 0505 BibRef

Ko, S.[San], Lee, K.M.[Kyoung Mu],
Structural Object Recognition Using Entropy Correspondence Measure of Line Features,
IEICE(E91-D), No. 1, January 2008, pp. 78-85.
WWW Version. 0801 BibRef

Yu, Z.W.[Zhan-Wu], Prinet, V., Pan, C.[Chunhong],
A novel two-steps strategy for automatic GIS-image registration,
ICIP04(III: 1711-1714).
IEEE DOI Reference 0505 BibRef

Chan, H.B., Hung, Y.S.,
Matching patterns of line segments by eigenvector decomposition,
Southwest02(286-289).
IEEE Top Reference. 0208 BibRef

Kawaguchi, T.[Tsuyoshi], Sinozaki, T.[Takayuki], Nagata, R.I.[Ryo-Ichi],
Detection of Target Models in 2D Images by Line-Based Matching and a Genetic Algorithm,
ICIP99(II:710-714).
IEEE Abstract. IEEE Top Reference. BibRef 9900

Laumy, M., Dhome, M., La Preste, J.T.,
Segments Matching: Comparison Between a Neural Approach and a Classical Optimization Way,
ICPR96(IV: 261-265).
IEEE DOI Reference 9608(Univ. Blaise Pascal, F) BibRef

Sugiyama, T., Abe, K.,
Edge Feature Analysis by a Vectorized Feature Extractor and in Multiple Edges,
ICPR96(II: 280-284).
IEEE DOI Reference 9608(Shizuoka Univ., J) BibRef

Marchand-Maillet, S., Sharaiha, Y.M.,
A Minimum Spanning Tree Approach to Line Image Analysis,
ICPR96(II: 225-230).
IEEE DOI Reference 9608(Imperial College of Science, Technology and Medicine, UK) BibRef

de Knecht, J., Schutte, K.,
Finding map correspondence using geometric models,
ICPR96(II: 755-759).
IEEE DOI Reference 9608(Delft Univ. of Technology, NL) BibRef

Cross, A.D.J., Hancock, E.R.,
Relational Matching with Stochastic Optimisation,
SCV95(365-370).
IEEE Top Reference. Relaxation. University of York. Graph based matching for line drawings (map) with an image. BibRef 9500

Cross, A.D.J., Hancock, E.R.,
Holistic matching,
ECCV98(II: 140).
WWW Version. BibRef 9800

Finch, A.M., Hancock, E.R., Wilson, R.C.,
Relational Matching With Mean Field Annealing,
ICPR96(II: 359-363).
IEEE DOI Reference 9608(Univ. of York, UK) BibRef

Heller, A.J., and Stenstrom, J.R.,
Verification of Recognition and Alignment Hypotheses by Means of Edge Verification Statistics,
DARPA89(957-966). Line Segment based matching to verify recognition results. The line must be in the right area. BibRef 8900

Jones, M.J.[Michael J.], Poggio, T.[Tomaso],
Model-Based Matching by Linear Combinations of Prototypes,
DARPA97(1357-1366). BibRef 9700

Jones, M.J.[Michael J.], Poggio, T.[Tomaso],
Model-Based Matching of Line Drawings by Linear Combinations of Prototypes,
ICCV95(531-536).
IEEE DOI Reference
WWW Version. BibRef 9500
And: MIT AI Memo-1559, December 1995. BibRef
And: Update: MIT AI Memo-1583.
WWW Version. And the updated version:
WWW Version. Basic line/contour match with prototypes. BibRef

Jiang, X.Y., Meier, U., Bunke, H.,
Scale-Invariant Polyhedral Object Recognition Using Fragmentary Edge Segments,
ICPR94(A:850-853).
IEEE DOI Reference BibRef 9400

Meer, P., Weiss, I.,
Point/Line Correspondence under 2D Projective Transformation,
ICPR92(I:399-402).
IEEE DOI Reference BibRef 9200

Laganière, R.[Robert], Mitiche, A.[Amar],
A 3D interpretation system based on consistent labeling of a set of propositions. Application to the interpretation of straight line correspondences,
ECCV90(521-525).
Springer DOI Reference 9004 BibRef

Nakamura, Y., Nagao, M.,
Recognition of Overlapping 2-D Objects by Local Feature Construction Method,
ICPR88(II: 1046-1048).
IEEE DOI Reference
IEEE Top Reference. BibRef 8800

Pan, F., Gu, W.K., Jing, R.J.,
A Back Tracking Algorithm for Matching Two Line Drawings of a 3-D Moving Object,
ICPR86(1096-1098). BibRef 8600

Chapter on Registration, Matching and Recognition Using Points, Lines, Regions, Areas, Surfaces continues in
2-D/2-D Lines Accumuation Techniques .