Density maximization for improving graph matching with its applications

Graph matching has been widely used in both image

processing and computer vision domain due to its powerful

performance for structural pattern representation. However,

it poses three challenges to image sparse feature matching:

1) the combinatorial nature limits the size of the possible

matches; 2) it is sensitive to outliers because its objective function

prefers more matches; and 3) it works poorly when handling

many-to-many object correspondences, due to its assumption of

one single cluster of true matches. In this paper, we address

these challenges with a unified framework called density

maximization (DM), which maximizes the values of a proposed

graph density estimator both locally and globally. DM leads

to the integration of feature matching, outlier elimination, and

cluster detection. Experimental evaluation demonstrates that

it significantly boosts the true matches and enables graph

matching to handle both outliers and many-to-many object

correspondences. We also extend it to dense correspondence

estimation and obtain large improvement over the state-of-the-art

methods. We further demonstrate the usefulness of our methods

using three applications: 1) instance-level image retrieval;

2) mask transfer; and 3) image enhancement.