Matching by Linear Programming and Successive Convexification

TitleMatching by Linear Programming and Successive Convexification
Publication TypeJournal Article
Year of Publication2007
AuthorsJiang, H., M. S. Drew, and Z. - N. Li
JournalPattern Analysis and Machine Intelligence, IEEE Transactions on
Pagination959 -975
Date Publishedjun.
KeywordsAlgorithms, Artificial Intelligence, Automated, Computer-Assisted, convex programming, image enhancement, Image Interpretation, image matching, Information Storage and Retrieval, label set matching, Linear, linear programming, metric labeling, numerical analysis, original cost function, Pattern Recognition, Programming, Reproducibility of Results, Sensitivity and Specificity, signal processing, Subtraction Technique, successive convexification

We present a novel convex programming scheme to solve matching problems, focusing on the challenging problem of matching in a large search range and with cluttered background. Matching is formulated as metric labeling with L1 regularization terms, for which we propose a novel linear programming relaxation method and an efficient successive convexification implementation. The unique feature of the proposed relaxation scheme is that a much smaller set of basis labels is used to represent the original label space. This greatly reduces the size of the searching space. A successive convexification scheme solves the labeling problem in a coarse to fine manner. Importantly, the original cost function is reconvexified at each stage, in the new focus region only, and the focus region is updated so as to refine the searching result. This makes the method well-suited for large label set matching. Experiments demonstrate successful applications of the proposed matching scheme in object detection, motion estimation, and tracking


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2020 The University of British Columbia