This paper formulates multi-image matching as a low-rank matrix recovery problem, and maximize pairwise feature affinities and cycle consistency across multiple images simultaneously.
Suppose we have $n$ images and $p_i$ features from each image $i$. Our goal is to find consistent feature correspondences across all the images.
Problem definition
Pairwise matching
To match an image pair $(i,j)$, we compute similarities for all pairs of feature points from two images.
Spatial rigidity is also prefferd, which means the relative location between two features in an image should be similar to that between their correspondences in the other image.
We aim to emphasieze both fearture similarity and spatial rigidity to obtain affinity scores of candidate matches and store them in a matrix $S_{ij}\in \mathbb R^{p_i\times p_j}$.
The feature correspondences for image pair $(i,j)$ is denoted as a permutation matrix $X_{ij}\in{0,1}^{p_i, p_j}$, which satisfies the doubly stochastic constraints:
$$
0\leq X_{ij}1\leq 1,0\leq X_{ij}^T\leq1. \tag{1}\label{1}
$$
and we can maximize the inner product betwween $X_{ij}$ and $S_{ij}$ by the Hungarian algorithm.
Cycle consistency
The cycle consistency can be described by:
$$
X_{ij}=X_{iz}X_{zj} \tag{2}
$$
for any three images $(i,z,j)$ and can be extended to the case with more images.
We define a virtual “universe” as the set of unique feartures that appear in the image collection. Each point in the universe may be obseved by several iamges and the corresponding matching should satisfy $X_{ij}=A_iA_j^T$, where $A_i\in {0,1}^{p_i\times k}$ denotes the map from image $i$ to the universe, $k$ is the number of points in the universe, and $k\geq p_i$ for all $i$.
The correspondence for all $m=\sum_{i=1}^n p_i$ featues in the image collection is denoted by $X\in {0,1}^{m\times m}$:
$$
X=
\begin{pmatrix}
X_{11}&X_{12}&\cdots&X_{1n}\
X_{21}&X_{22}&\cdots&X_{2n}\
\vdots&\vdots&\ddots&\vdots\
X_{n1}&\cdots&\cdots&X_{nn}
\end{pmatrix},\tag{3}
$$
And all $A_i$s are concatenated as rows in a matrix $A\in {m,k}$, so we can write $X$ as
$$
X=AA^T, \tag{4}
$$
It is clear that $X$ should be both positive semidefinite and low-rank:
$$
X\succeq 0,\quad rank(X)\leq k \tag{5}
$$
Joint matching
Given ${S_{ij}| a\leq i,j\leq n}$, our goal is to find globally consistent matches $X$. We formulate the problem as a low-rank matrix recovery problem.
We make the following relaxations:
- $X$ is treated as a real matrix $X\in [0,1]^{m\times m}$ instead of a binary matrix
- Rank of $X$ is replaced by the nuclear norm $||X||_*$(sum of singular values)
Besides constraints in $(\ref{double})$, additional constraints shall be imposed on $X$ after relaxation:
$$
X_{ii}=I_{p_i},\quad 1\leq i\leq n, \tag{6} \label{6}
$$
$$
X_{ij}=X_{ji}^T, 1\leq i,j\leq n, i\neq j,\tag 7 \label{7}
$$
$$
0\leq X\leq1 \tag 8, \label 8
$$
Combining three factors,
- We maximize the inner product between $X_{ij}$ and $S_{ij}$ for all $i$ and $j$ as multiple linear assignment problems.
- We minimize the rank of $X$ to maintain cycle consistency.
- We minimize the sum of values in $X$ to induce sparsity.
We obtain our cost function:
$$
\begin{align}
f(X)&=-\sum_{i=1}^n\sum_{j=1}^n\langle S_{ij},X_{ij}\rangle+\alpha\langle1,X\rangle+\lambda||X||*\
&=-\langle S-\alpha1,X\rangle+\lambda||X||*
\end{align} \tag{9}
$$
where $\langle\cdot,\cdot\rangle$ denotes the inner product, $\alpha$=0.1 is the weight of sparsity.
Finally, we obtain the following optimization problem:
$$
min \langle W,X\rangle + \lambda ||X||_*,\
\text{s.t.} X\in \mathcal C, \tag{10}
$$
where $W=\alpha 1-S$ and $\mathcal C$ denotes the set of matrices satisfying the constraints given in $(\ref{1}), (\ref{6}), (\ref{7}), (\ref{8})$.
Algorithm
Recent results on low-rank optimization have shown that one can solve the problem more efficiently via a change of variables $X=AB^T$, where $A,B\in \mathbb R^{m\times k}$ are new variables $X=AB^T$ with a smaller dimension $k<m$.
And with the equation,
$$
||X||*=\min{A,B:AB^T=X} \frac{1}{2}(||A||^2_F+||B||F^2), \tag{11}
$$
we finally obtain the following formulation:
$$
\min{X,A,B} \langle W,X\rangle +\frac{\lambda}{2}||A||_F^2+\frac{\lambda}{2}||B||_F^2,\
\text{s.t.}\ X=AB^T,\ X\in \mathcal C \tag{12} \label{12}
$$
and we can apply ADMM to solve it.
The augmented Lagrangian of $(\ref{12})$ is:
$L_\mu(X,A,B,Y)=\langle W,X\rangle+\frac{\lambda}{2}||A||^2_F+\frac{\lambda}{2}||B||^2_F+\langle Y,X-AB^T\rangle+\frac{\mu}{2}||X-AB^T||^2_F$
where $Y$ is the dual variable and $\mu$ controls the step size in optimization.
The overall algorithm is:
Selection of $k$
A heuristic choive is to set $k=2\hat r$, where $\hat r$ is a rough estimate of the size of the universe.