Image Matching via Loopy RNN

1 Introduction

Image matching is a very important research topic in computer vision, due to its great potential in a wide range of realworld tasks including object/place retrieval [Arandjelovic et al., 2016], person re-identification [Yan et al., 2016b], 3D reconstruction [Cheng et al., 2014], etc. Mathematically, a matching algorithm takes two images as inputs and outputs a score measuring the similarity of the two inputs, i.e., higher score indicates higher similarity between the two inputs. Previous research work is mainly focused on two aspects. On one hand, various image patch descriptors such as SIFT [Lowe, 2004], SURF [Bay et al., 2006], ORB [Rublee et al., 2011], etc., have been proposed to well represent the two patches, based on which the computed distance (e.g., Euclidean distance) can accurately reflect the true relationship between them. On the other hand, metric learning based methods [Jia and Darrell, 2011; Jain et al., 2012] have been B. Observe two images back and forth developed to achieve more discriminative distance measure, which is superior to conventional Euclidean distance.

Figure 1: Difference between one-off matching and recursive matching.

Recently, deep learning has further made significant progress in image matching on both aspects. For feature representation, SIFT based patch descriptors have been replaced with convolutional neural networks (CNN) based ones [Fischer et al., 2014; Paulin et al., 2015]. The results show a significant performance gain. For distance metric learning, endto-end learning infrastructure has been utilized to enhance image matching. One remarkable example is the Siamese network [Bromley et al., 1993], in which two image patches are first input to a two-stream convolutional sub-network (with identical parameters) to extract features, and then combined with a second sub-network (based on fully connected layers) to infer the similarity of two image patches. Siamese network has been widely used in many aspects of computer vision including people re-identification [Yi et al., 2014] and tracking [Bertinetto et al., 2016]. Based on the end-to-end learnable capability provided by Siamese, MatchNet [Han et al., 2015] [Zagoruyko and Komodakis, 2015] has recently boosted patch-based image matching performance.

Despite their remarkable improvements, previous work on matching can all be regarded as a one-off solution, i.e., most algorithms perform the image patch feature extraction and distance calculation for only one time and output the final matching score. However, human's vision system performs matching process in a rather recursive/iterative manner. To judge whether the two images refer to the same species, human's attention is constantly switched between two images and moved to different patches/parts on the images. In other words, one will take turns observing different regions of both images to progressively aggregate information on the matched/un-matched portions of both images and get more and more confident. This process repeats until one is confident enough to make the final judgement. As shown in Figure 1, it is difficult to distinguish if the two birds are from same subspecies by observing the two images once. In this situation, human alternately observes two images and each observation is focused on some parts of the birds, such as the head and leg, etc., and finally makes a confident decision based on integral and local information. From a computational point of view, the above recursive/iterative matching mechanism also has advantages over the conventional one-off approach, as it can progressively attend to more and more discriminative regions of the images and get rid of the issue of cluttered background or irrelevant and noisy image features.

It is thus demanding to develop a computational model or network structure to simulate the recursive mechanism to enhance image matching. Towards this end, it is natural to consider recurrent neural networks (e.g., RNN [Dorffner, 1996], LSTM [Hochreiter and Schmidhuber, 1997]). Intuitively, human's attentive regions/patches on both images could be considered as a sequence of observations. This observation sequence could naturally serves as the input sequence to a RNN/LSTM structure and the aggregated similarity measure could be output from the last (temporal) node of the recurrent network. However, such a sequential model cannot be directly applied for image matching as it violates the symmetric property which is required for a valid matching algorithm. Namely, the output similarity measurement should be unchanged if we switch the order of the two input image patches. To satisfy this symmetric requirement, we propose a loopy recurrent neural network (Loopy RNN). A Loopy RNN inherits basic components and structure of conventional RNN. The major differences between a Loopy RNN structure with a conventional one are that: 1) instead of having an arbitrary number of temporal nodes, it only has two, which correspond to the two input image patches, and 2) these two nodes are cyclicly linked, thus it brings up symmetry property. When applied to image patch matching, Loopy RNN can simulate the iterative process of examining image features from both images alternatively and progressively gather more and more matched information to consolidate the final matching score. To facilitate model training and testing, an approximation from the Loopy RNN structure toward a normal RNN/LSTM structure is developed via duplicating the head and tail nodes for a number of times. To simulate human's perception as well as to guarantee robust matching, it also requires that the confidence of similarity measurement increases when we goes deeper in our recursive matching network. For such a purpose, we utilize a monotonous objective function [Ma et al., 2016], which enforces more penalty to the output associated with deeper node in the network. The proposed Loopy RNN has been experimented on several image matching benchmark including UBS patch dataset [Winder et al., 2009] and Mikolajczyk dataset, and results demonstrate performance gain over Siamese-like networks.

2 RelatedWork

Two key components are included in image matching, one is extracting proper features from the original image and the other is measuring the distance of the features to describe the similarity of images. At first, hand-craft features such as SIFT [Lowe, 2004] and DAISY [Tola et al., 2008] are cooperated with fixed metric method like Graph Model [Yan et al., 2016a; 2015a; 2015b] to match images. It means that the two parts of matching (extracting feature and measuring similarity) are independent when using above methods and the isolation hinders the improvement of performance. To break the isolation, researchers propose learning descriptors or similarity metric in condition of fixed the other part. For example, [Brown et al., 2011] learns the descriptors by minimizing the classification error and [Jain et al., 2012] learns the metric by treating it as a linear transformation. Learning descriptors and metric jointly is proposed to make the cooperation of the two parts more powerful. In [Trzcinski et al., 2012], boosting trick is adopted to learn descriptors and metrics and achieved great performance. The performance of these methods are limited by the hand-crafted features, while the proposed method employs deep features and achieves better performance.

The advent of CNNs has tremendously promoted the development of many branches of computer vision including image matching. In [Krizhevsky et al., 2012], the performance of convolutional descriptor from AlexNet (trained on ImageNet) has been proved more effective than SIFT in most cases. In [Ren et al., 2017], CNN also was used to compute dense correspondence. Combining CNN and Siamese structure [Bromley et al., 1993], it is natural to train the network in an end-to-end manner, i.e., learn descriptor and metric jointly. MatchNet of [Han et al., 2015] employs a Siamese network in which some convolutional layers are adopted as a feature extractor and fully connected layers as a comparator to measure similarity. [Zagoruyko and Komodakis, 2015] explores different architectures to do patch-based image matching including Siamese (share parameter of CNN), Pseudo-Siamese (unshare parameter of CNN), and 2-channel (treat two patches as two channels of an image). In virtue of CNN's advantage, these methods obtain great promotion compared with previous traditional methods. These methods mentioned above can all be regarded as one-off, i.e., descriptors are compared just once. The Loopy RNN proposed in this paper learns the descriptors and metric jointly like Siamese, however, draws the conclusion by repeating comparing the descriptors. Note that Shyam et al. published a paper based on similar idea, which they call Attentive Recurrent Comparators [Shyam et al., 2017]. We recommend the readers to also refer to this contemporary work.

3 Methodology

The goal of this work is to develop a recusive/iterative matching framework to imitate the matching mechanism of human perception. To this end, we propose a loopy recurrent neural network (Loopy RNN) which not only aggregates individual matching attempts and progressively yields more and more confident matching result but also preserves the symmetric property.

3.1 Loopy Recursive Neural Network

Architecture. The basic structure of a loopy recurrent neural network (Loopy RNN) is illustrated in Figure 2. Our Loopy RNN consists of two sub-networks sharing parameter. Two recurrent nodes compose a sub-network. In this work, we adopt a standard long short-term memory (LSTM) [Hochreiter and Schmidhuber, 1997] node with input/output/forget/hidden cells as an atomic node of a Loopy RNN. Therefore we denote two sub-networks as LSTM and LSTM ′ respectively. For LSTM, two nodes are n1, n2. For LSTM ′ , two nodes are n′1 , n′2 . As illustrated in Figure 2, the difference between a sub-network RNN and a normal RNN architecture lies in the connection between nodes, i.e., a normal RNN is a linear structure, a Loopy RNN is a circular structure with the output of the tail node linked to its head node.

We denote xA, xB as a pair of inputs, i.e., features of image patches. hA(B), oA(B) are the hidden state and output node corresponding to input image A (or B). For each node of LSTM, three gates input gate i, output gate o, and forget gate f as well as a memory cell c are included. The LSTM nodes in our loopy network are updated as follows:

where σ is the sigmoid function and ⊙ denotes the elementwise multiplication operator. W∗, U∗ and V∗ are the weight matrices, and b∗ are the bias vectors. The memory cell cA(B) is a weighted sum of the previous memory cell cB(A) and a function of the current input.

Proof of Symmetry: Because of the dual structure, it's straightforward to prove the symmetry of the proposed Loopy network. If we use F(xA, xB) and F(xB, xA) denoting the final output hidden states of different input orders (xA, xB) and (xB, xA) respectively, i.e., average of the first node's output. The symmetric property of matching requires that F(xA, xB) = F(xB, xA). As shown in Figure 2, the hidden state of node n1 with input xA is denoted as hn1,A. And hn′1 ,B is the hidden state of node n′1 with input xB. F(xA, xB) is the final hidden state which is used to determine the similarity with the input order (xA, xB). F(xA, xB) and F(xB, xA) are determined as follows:

LSTM and LSTM ′ share parameters, therefore

from Equation 2 and 3,

Thus it's proven that the proposed Loopy RNN structure possess symmetry property.

3.2 Loopy RNN for Image Matching

To facilitate image (patch) matching, additional network components shall be augmented/modified to the basic structure of Loopy RNN. First, a feature extraction sub-network, i.e., a CNN network, is utilized to map the original image patch to a learned feature space, to input to the core structure of loopy RNN (denoted as FeatureNet in the rest of this paper). Second, as it is generally not feasible to train/test a loopy structure, we develop a simple yet effective structural approximation to convert a Loopy RNN into a conventional LSTM network to measure the similarity of a pair of features (denoted as MetricNet). Details are given as follows.

FeatureNet. We adopt the feature network of MatchNet [Han et al., 2015] as our network prototype for extracting deep features, named as FeatureNet. The structure of FeatureNet is modulated from AlexNet [Krizhevsky et al., 2012]. The detailed network structure of FeatureNet is illustrated in Figure 3. Note that the input patch size of FeatureNet is 64 × 64 and the output feature dimension (which is connected to the core structure of Loopy RNN) is 4096. For the purpose of simplicity, in our work, dropout and local response normalization layers are omitted, since our input is image patch rather than the entire image (which is more complicated). Note that the feature extraction sub-networks for different input image patches share the same parameters.

MetricNet. Although the two-node Loopy RNN has very simple structure, both forward and backward (training) computation for such a loopy structure is infeasible. Therefore, it is required to develop a simpler network structure which should not only mimic the recursive nature of Loopy RNN but also possess the advantage of easy training/testing. We observe that for a two-node Loopy RNN, the sequence of inputs could be regarded as an infinite repeat of both inputs. For example, for two image patches IA and IB, their descriptors (the output feature vector from FeatureNet) are denoted by xA and xB respectively, then the input to the two-node Loopy RNN is the alternative sequence xA → xB → xA → .... Motivated by this observation, we therefore utilize a conventional RNN/LSTM structure with a sequence of finite K repeated (xA, xB) patterns as input to approximate the Loopy RNN matching network, as shown in Figure 3. Thus it breaks the loopy structure to a standard RNN/LSTM structure, and off-the-shelf training algorithm could be directly applied. The proposed approximation has two advantages: 1) as information aggregates quickly through recursion, the output of network becomes stable after just a few repeats, i.e., K could be small, which makes model training and inference very efficient; 2) if we regard each time step in the approximated LSTM network as an attention switch to one of the images, the proposed approximation naturally simulates the recursive matching process of human, i.e., iteratively switches attention between two input images and makes deeper and deeper comparisons.

Corresponding to the input sequence, our approximate LSTM network outputs a sequence of pair-wise matching features as h0 → h1 → h2 → ... → hn-3 → hn-2 → hn-1. Each pair-wise feature vector hn encodes the similarity/comparison information aggregated from repeated input information from both images up to time step n. In contrast to previous matching algorithms which output only a scalar value to indicate similarity, our model outputs a feature vector to encode the similarity relationship between images, which conveys richer information and is more flexible for postprocessing (in cases where later fusion is preferred). These output similarly feature vectors are sent to a softmax layer to determine the final similarity score, i.e., the final output of our network is a sequence of scores which describing the similarity of two image patches, denoted by s0 → s1 → s2 → ... → sn-3 → sn-2 → sn-1. sn is computed as follows:

where θ is the set of softmax layer parameters. Each sn ranges in the interval [0, 1] and greater value indicates higher similarity. In fact, the first pair-wise feature h0 and first score s0 are abandoned as Figure 3 showed, because only single patch information instead of pair-wise information is included in first node.

3.3 Monotonous Loss

As the network's attention iteratively switches between two input image patches and more and more comparisons are made, the measurement for similarity should be more and more confident. In other words, it is required that the similarity score of the correct category should be monotonically non-decreasing as the information propagates deeper along the proposed matching network, as illustrated in Figure 3. However, a plain cross-entropy loss does not enforce such a monotonous non-decreasing property. We therefore use a monotonous loss [Ma et al., 2016], which extends the conventional cross-entropy loss to enforce the accuracy of prediction increase when the matching process goes deeper. Mathematically, we can express this loss as:

Here, Lmn denotes the monotonous loss at time-step n, which penalizes the corresponding node if the output similarity score violates the monotonous rule. y is the ground truth label, i.e., 1 for matched and 0 for un-matched. sn is the predicted similarity score at time step n and spre n is the maximum (y = 1) or minimum (y = 0) prediction score until time step n - 1. The max operation of Equation 6 picks out the nodes that violate the monotonous rule. Denoted by Lcn as the standard cross-entropy loss, the overall loss could be expressed as:

where λ is a weighting factor for both types of losses.

3.4 Implementation Details

Data Preparation. Data imbalance is a common problem in patch-based image matching, because the number of positive pairs is far less than the number of negative pairs. A sampler which generates equal number of positive and negative pairs in a mini-batch is employed to prevent excessive bias to negative pairs. To improve the generalization capability, we augment the dataset by vertically and horizontally flipping the original patch and rotating to 90, 180, 270 degrees. Following the previous work [Han et al., 2015], we map each pixel value x (in [0,255]) to (x - 128)/160.

Network Parameter and Training. The details of FeatureNet are listed in Table 1. For MetricNet, there are 3 key factors which influence the performance of Loopy RNN model: 1) the weighting factor of monotonous loss λ; 2) the number of RNN nodes N (N ∈ {6, 8, 10, 12}); 3) the output dimension of LSTM node D (D ∈ {512, 1024, 1536, 2048}).

Our models are trained on Caffe [Jia et al., 2014] and optimized by Stochastic Gradient Descent (SGD) with the batchsize 32. Learning rate is set to 0.01 at the beginning and decreased once every 1000 iterations. Our model converges to the steady state after about 70 epoches.

4 Experiments

We evaluate our Loopy RNN network on two datasets: UBC dataset [Winder et al., 2009] and Mikolajczyk Dataset [Brown et al., 2011]. Extensive experimental evaluations and in-depth analysis of the proposed method are presented in this section.

4.1 Dataset and EvaluationMetric

UBC Dataset. UBC includes three subsets: Liberty, Notredame and Yosemite. The number of image patches in the three subsets are 450k, 468k, and 634k respectively. For the three subsets, 100k, 200k, and 500k pre-generated pairs are provided and the number of positive pairs equals to negative pairs. Each patch in the dataset has a fixed size of 64×64, which corresponds to the input dimension of our FeatureNet.

We follow the standard evaluation protocol [Brown et al., 2011], i.e., the model is iteratively trained on one subset and tested on the other two subsets, FPR95 (false positive rate at 95% recall) is adopted as the evaluation metric, the lower the better.

Mikolajczyk Dataset. Mikolajczyk dataset is composed of 48 images in 8 sequences and each sequence corresponds to one of 5 transformations: viewpoint change, compression, Mean FPR95

7

6.8

6.6

6.4

6.2

512 1024 1536 2048

D(N=10)

blur, lighting change and zoom with gradually increasing amount of transformation. Among 6 images of a sequence, one is reference image and the rest are transformed from reference image with different transformation magnitude, i.e., the degree of transformation. The ground truth homography between reference image and transformation images are provided for evaluation. We follow the method of [Mikolajczyk and Schmid, 2005] to test our model. MAP (Mean Average Precision), which measures the area under the precisionrecall curve is adopted as the evaluation metric.

4.2 Evaluation on UBC

In testing phase, we adopt the mean score of all nodes (except first node) as the final similarity score if monotonous loss is not used, i.e., λ = 0. Otherwise, the final score is the mean of the last two nodes' score, i.e., for a sequence of 8 nodes, s1, s2, ..., s7 are scores of last 7 nodes respectively, the final score s = 1 7 (s1 + s2 + ... + s7) if λ = 0, otherwise s = 12 (s6 + s7).

To verify the effectiveness of our Loopy RNN network, we compare our model with two recent works which apply CNN on patch-based image matching: MatchNet [Han et al., 2015] and [Zagoruyko and Komodakis, 2015]. Table 2 lists the comparison results. Our best model achieves 6.32% average error rate with monotonous loss and parameter N = 10,D = 1024. nSIFT concat.+NNet is the concatenation of SIFT feature and neural network. Our network outperforms this model by a large margin mainly because our feature extracted by FeatureNet is more effective. Before metric network, MatchNet has the same architecture with our network and MatchNet achieves 7.75% average FPR95. Therefore the 1.43% promotion compared with MatchNet completely comes from the combination of our Loopy RNN architecture and monotonous loss. The rest networks are all Siamese-like. Compared with Siamese and Pseudo-Siamese network, the FPR95 of our network decreases 3.75% and 3.3% respectively. The gain comes from the FeatureNet and our Loopy RNN network. Siamese-2stream and Siamese-2stream-l2 utilize information of different resolutions and achieves 7.63% and 9.67% average FPR95 respectively. Even only using information of one resolution, our model still obtains 1.31%, 3.34% improvement on FPR95. To verify the effect of monotonous loss, we list the results of our model without monotonous loss. It is obvious that the performance decreases compared with the model with monotonous loss. The experiment results illustrate that our Loopy RNN architecture has superiority over Siamese network and monotonous loss assists Loopy RNN to obtain further performance gain.

2ch-2stream network [Zagoruyko and Komodakis, 2015] obtains better performance than our network. It achieves the performance by treating two grayscale patches as two channels of a new image and classifying the new image into two category. The 2ch-2stream network performs better because it disposes two images jointly at the very beginning. Then each feature map includes the pair's feature. Because feature map can't input to the LSTM node directly, in our network, it is necessary to extract feature vector from image. Thus our FeatureNet disposes two images respectively. Only in MetricNet, pair's feature is disposed. From image to feature vector, our network misses some pair information compared with the 2-channel network.

Parameter Analysis. On one hand, we find that large λ makes the proposed network hard to converge. Thus we can not set λ to a large value. On the other hand, λ is used for balancing the weights of monotonous loss and crossentropy loss. Too small value of λ weakens the function of monotonous loss. As a result, we set λ = 0.4 empirically. Figure 4 shows the experiment results with different LSTM output dimension D and loopy time N. We fix N as 10 and test the model with different D (Figure 4(a)), then we fix D as 1024 and test our model with different N (Figure 4(b)). We observe that higher dimension results to better performance as well as computational complexity. Here, we set D as 1024. For N, larger loopy time promotes the performance, however, when N exceeds 10, the performance saturates. Thus we set N to 10. This is because that the network already has enough observations for making the judgement. Based on the above analysis, we choose the model with parameter N = 10, D = 1024 as our best models even though the N = 10, D = 2048 model outperforms the former a little.

4.3 Evaluation On Local Descriptors

We compare our network with five networks of [Zagoruyko and Komodakis, 2015] that are tested on the same dataset. MSER SIFT uses the Euclidean distance of SIFT features to measure the similarity of two patches. The other three models, MSER Imagenet, MSER Siam-2stream-l2 and MSER Siam-SPP-l2 substitute SIFT feature with CNN feature. MSER 2ch-2stream dispose 2 images as mentioned above. All the models are trained on the Liberty dataset. We test our model under different transformation with increasing magnitudes. Figure 5 illustrates the overall results. Our network outperforms most networks, especially in the extreme case.

Transformation Magnitude

Figure 5: Evaluation on the Mikolajczyk dataset. Our model is trained on Liberty with N = 10, D = 1024.

When transformation magnitude equals to 5, our network and 2ch-2stream greatly outperforms other networks by approximately 10%, which demonstrates the robustness of our model. MSER Siam-SPP-l2 is a network with SPP layer which makes the network able to deal with patches of different scale. Although our model only deals with single scale patches, it still outperforms MSER Siam-SPP-l2 in most cases. When magnitude equals to 1, 2, 5, MAP of our model achieves better performances by about 2%, 4% and 9% respectively compared with MSER Siam-SPP-l2. The performance of our network is comparable with the 2ch-2stream network. This indicates that our loopy network has good generalization ability as it performs well on different datasets.

5 Conclusion

In this paper, we propose a novel Loopy RNN which matches a pair of patches in a recurrent manner. Based on widely used cross-entropy loss, we add the monotonous loss aiming at restricting the output of a sequence. Combined with monotonous cross-entropy loss, our network imitates human to observe the two patches back and forth and the judgement become more and more confident in this process. Our experimental results show the effectiveness of the proposed method.

Acknowledgements

The work was supported by State Key Research and Development Program (2016YFB1001003). This work was partially supported by a grant from the National Natural Science Foundation of China under contract No.U1611461, NSFC (61502301), China's Thousand Youth Talents Plan, National Natural Science Foundation of China (61521062), the 111 Project (B07022) and the Opening Project of Shanghai Key Laboratory of Digital Media Processing and Transmissions.