Simplicial Complex based Point Correspondence between Images warped onto Manifolds
Overview
There exists a longstanding line of research on finding bijective correspondences (i.e.,assignments / matchings) between two sets of visual features. Notable applications include stereo matching, structure from motion (SfM), and image registration, etc. You can see our work from ICML 2018 on matching between two images in this blogpost.
The recent proliferation of spherical images (e.g., omnidirectional and panoramic images captured from cameras mounted on drones and autonomous vehicles) and more generally, images warped onto manifolds with non-trivial curvatures, has sparked a heightened interest in assignment algorithms on warped images due to projection. Thus, we present our work from our ECCV 2020 paper titled “Simplicial Complex based Point Correspondence between Images warped onto Manifolds”. Our code is available here.
Challenges
Although assignment problems have been well studied for decades in computer vision, a majority of the work has only focused on matching points between planar (flat) images. Therefore, matching points on images with warping transformations which fall into the category of projective parametric models remains a challenging task, mainly due to the introduction of undesirable artifacts like severe distortions in pairwise distances between landmark points, non-linear distortions in local geometries, noise, illumination, blur, and occlusions, on flattening.
When dealing with matchings on curved geometries, primarily two types of methods are employed. Some putative matchings are computed to estimate a fundamental matrix that captures the epipolar geometry of the 3D image. Stereo rectification uses this fundamental matrix to re-project the two images on the same flat plane with row images aligned in parallel, followed by a re-matching to improve matching accuracy. Alternatively, geometric alignment on the fundamental matrix is used to verify and distinguish inliers from outliers, so that outliers can be pruned post matching to further boost accuracy. Elements warped on the curved manifold cannot be metrically sampled in such methods and hence severe distortions are introduced, which is also consistent with the findings in our empirical studies.
Problem Definition
Our problem consists of first constructing geometric simplicial complexes between landmark points given on curved manifolds with set of vertices, followed by finding an optimal (i.e., least cost) assignment between a pair of such geometric simplicial complexes by matching simplices of the same dimension, one dimension at a time. The edges/arcs in simplicial complexes are given by geodesics between select few pairs of vertices, from their corresponding vertex sets.
Our Method
Building a Simplicial Complex on a Curved Manifold
We construct a graph-induced simplicial complex, which is built upon a graph connecting the landmark points.
Graph Construction Let (P,g) denote the set of landmark points P with a metric g that denotes the geodesic distance between a pair of points on manifold M. Additionally, let the k-neighborhood N_k(u) denote the set of k nearest neighbors of landmark point u ∈ P (inclusive of u) on manifold M according to the geodesic metric g.
Considering all ordered pairs (u,v), where u,v ∈ P, an undirected edge/arc is introduced between points u and v, when their corresponding k-neighborhoods N_k(u) and N_k(v) have a non-empty intersection, i.e., N_k(u) ⋂ N_k(v) ≠ Ø. All such edges are collected into a set denoted by E.
This completes the construction of our underlying graph G=(P,E). Observe that the vertex set (landmarks) P form the 0-skeleton K^(0)(G) and the sets E and P together form the 1-skeleton K^(1)(G), of our graph-induced simplicial complex that we will denote by K(G).
Recall that a n-clique in a graph is a complete subgraph between n vertices, i.e., it consists of n vertices and C(n,2) edges.
Graph-induced complex K(G) is defined as the simplicial complex where a n-simplex σ^(n) = {p_1, p_2,… , p_(n+1)} is in K(G), if and only if there exists a (n+1)-clique {p_1, p_2,… , p_(n+1)} ⊆ P in the underlying graph G=(P,E). In words, the cliques of the underlying graph G=(P,E) form the simplices in K(G) because cliques satisfy both conditions of being a simplicial complex (which can be trivially verified). In order to be used in our assignment algorithm, we must represent the graph-induced simplicial complex K(G) as a set of boundary matrices, which we present next.
Matrix representation of K(G) Given K(G) and its p-skeleton K^(p)(G) that contains cliques upto size p+1, we represent it as a boundary matrix M_p ∈ ℤ^{n×m} defined as
where a_ij = 1 if and only if the i-th (p-1)-simplex τ^(p-1) is a facet of the j-th p-simplex σ^(p), otherwise a_ij = 0.
Observe that the p-th boundary matrix M_p captures all possible relationships between p-simplices and their (p-1)-simplex boundaries (or facets). Boundary matrix M_p is made for each p-skeleton and therefore K(G) is expressed as a set of boundary matrices { M_p } in which p ranges from 1 to h, where h=dim(K(G)).
Assignment Algorithm
Given a boundary matrix M_p ∈ ℤ^{n×m} that represents a p-skeleton K^(p)(G), we first capture the geodesic neighborhood geometry of simplices in M_p. This neighborhood of a simplex is then elegantly captured by affine weight vectors, which are later used in the matching algorithm.
Next, we describe the construction of a cost matrix that is needed to compute assignments between M_p ∈ ℤ^{n×m} and M’_p ∈ ℤ^{n’×m’}. We begin by constructing two cost matrices C^(p-1) ∈ ℝ^{n×n’} and C^(p) ∈ ℝ^{m×m’} to measure the Euclidean distance between the affine weight vectors of (p-1)-simplices and the Euclidean distance between the affine weight vectors of p-simplices, respectively.
We combine both the cost matrices in a single geodesic-cost matrix L^(p). The diagonal and off-diagonal entries of matrix L^(p) capture the Euclidean distances between the affine weight vectors of (p-1)-simplices and the Euclidean distances between the affine weight vectors of p-simplices, respectively. Therefore, our QAP can now be formulated as
where X_p is a permutation matrix and vec(X_p) is it’s vector representation. Our solution to the above Equation is concisely outlined in Algorithm. As we solve a QAP from highest to lowest dimension p-skeleton, we track the (p-1)-simplices whose matchings are induced by higher order simplex matches. On finding (p-1)-simplices that have the lowest cost and cannot be improved by solving a lower level QAP, we eliminate such simplices, causing the size of the matrix to shrink in subsequent iterations, leading to substantial speedups.
Example
We illustrate with an example the bijective assignment produced by our algorithm between cliques / simplices of a pair of graph-induced spherical simplicial complexes, as shown in Figure below. We consider two simplicial complexes K and K’ each embedded on S², with 20 and 16 vertices, respectively. Matching of corresponding 3-cliques and 2-cliques are mentioned in the Table. Matching between vertices (1-cliques) is shown by marking them with the same label on both spheres.
Matching Results
We match pairwise images directly on the warped images on curved manifolds as shown in Figures. The comparison between standard higher-order graph matching (Tensor) and our method on manifold is shown in using Chinese vases and Fundus images, respectively.
We observe from Figures that the Tensor based method does not perform well on warped images. Although, the matching does improve when images are flattened to reduce the effect of curvature in Figure. Our method outperforms the baseline and has amaximum number of correct matches.
For matches between spherical and planar images, we find two variants which match between a spherical and a planar image and matching between different types of spherical images.
Implementation
The code for our paper is provided in this github repository. Following are the steps to reproduce the results:
- Clone the repository and set up the MATLAB environment.
git clone https://github.com/charusharma1991/PointCorrespondence2. To run end to end matching model to generate results for “Desktop” dataset, do the following:
end2end.m 3. To reproduce results mentioned in Table 2, do the following:
main.mThis will generate results for our method (OurWarped). The results would be generated in the output files.
Citation
Please cite the paper if you use this code.
@article{sharma2020simplicial,
title={Simplicial Complex based Point Correspondence between Images warped onto Manifolds},
author={Sharma, Charu and Kaul, Manohar},
journal={arXiv preprint arXiv:2007.02381},
year={2020}
}Thanks for reading this article. For any query or suggestions, please write to charusharma1991@gmail.com.