Abstract
In this paper, we study the problem of recognizing man-made objects and present a novel affine-invariant feature, Lowrank SIFT, which exploits the regular appearance property in man-made objects. The proposed feature achieves full affine invariance without needing to simulate over affine parameter space. We rectify local patches by converting them to their low-rank forms to achieve skew invariance, and perform the way similar to conventional SIFT to resolve rotation, translation and scaling ambiguity. The main contributions lie in two-fold: our method seeks to leverage low-rank prior to estimate affine parameters for local patches directly and we propose a fast algorithm to compute such parameters by introducing the Low-rank Integral Map. Besides, we describe a pipeline of constructing a geotagged building database from the ground up. We demonstrate the effectiveness of our approach in the application to place recognition.
I. INTRODUCTION
Constructing features with different invariance properties is the building block of image matching, which in turn is fundamental to the task of place recognition. The enthusiasm of seeking all kinds of invariance largely arises due to the complexity of camera model, as different camera conditions and viewpoints can lead to different deformations for the same object. Current image matching methods usually consist of three stages. First, interest points are detected at descriptive locations, such as corners or blobs. Next, an invariant descriptor is associated to the region around each interest point. This step is crucial as it is where the main challenges of eliminating irrelevance and finding the intrinsic local representation lie. Finally, correspondences are established between source and target images using descriptor vectors, and matched images are retrieved. In this scenario, images of same object under different viewpoints should have as similar feature representations as possible.
Given the three-stage procedure there are two challenging problems to address. The first one, named feature selection, is related to how to effectively select features of interest from the entire feature set. Many investigations are done by exploiting the intrinsic property of features. Li et al. [1] does filtering by assigning a posterior probability to each feature. A similar approach is [2] , which tries to detect informative fragments from image and uses them as features directly. Turcot and Lowe [3] selects features appearing repetitively in multiple images, while abandons those occasionally occur. All these methods lead to compressed and more representative feature set. Nevertheless, Schindler et al. [4] takes a different approach by letting the set of features remain the same, and instead uses the feature information to guide the building process of vocabulary trees.
A more difficult problem would be using what feature to achieve invariance. Recent years the design of robust features have drawn much attention. All the features proposed could be categorized based on the degree of invariance they achieve and what methods they use. One of the most notable features is SIFT [5] , which achieves partial affine invariance by normalizing translation and rotation, and achieves full scale invariance by simulating the scale parameter. Moment-based Harris-Affine [6] and Hessian-Affine [7] detect corners of interest first and then iteratively estimate the transform parameters. There are also region-based features such as MSER [8] and LLD [9] , which try to normalize the most robust image level sets and level lines to get the standard form. ASIFT [10] , as an extension of SIFT, takes one step further and achieves full affine invariance using both normalization and simulation to resolve affine ambiguity. However, the mentioned feature are mostly general and are not designed for any specific objects, so they do not take into account the intrinsic properties of the objects they describe.
Inspired by a recent global feature named Transform Invariant Low-Rank Texture (TILT) [11] , our proposed feature takes a different approach by seeking invariance based on local geometry as well as low-level hue and 978-1-4799-5751-4/14/$31.00 ©2014 IEEE gradient information. Similar to TILT, the method exploits the low-rank property of certain objects but we treat it locally. The feature, named Low-rank SIFT, complements SIFT with two significant properties. First, it achieves full affine invariance when applied to objects with local lowrank structure. Second, instead of simulating local affine parameters, it estimates and normalizes them directly.
The main contributions of our work could be summarized as:
• We propose a novel framework for affine-invariant feature detection and representation, and use it to achieve robust place recognition.
• We define a novel concept, the Low-rank Integral Map, which enables fast low-rank optimization at multiple locations.
• We describe our method of constructing a benchmark database for place recognition. The database contains buildings of different styles. The pipeline of computing Low-rank SIFT and recognizing place is illustrated in Fig. 1 .
II. LOW-RANK SIFT: AN OVERVIEW Background and Observation. Morel's effort of introducing ASIFT and other features under a unified framework prove that, with the affine camera model, local perspective effects can be modeled with an affine transform [10] :
The affine transform could be further decomposed into translation, scaling, rotation and skew.
In spite the formulations are different for each feature, there are two different ways to achieve invariance against these transforms: normalization and simulation. With normalization, a local patch is converted to its standard form. In the example of SIFT, translation is easily normalized by translating a patch to the origin point. Rotation could be normalized by computing a principle direction and rotate the patch until its principle direction coincides with a fixed axis. Notwithstanding above, skew is more difficult to normalize. ASIFT simulates all possible deformations and performs matching using the entire simulated image set simulated. Admittedly, given inadequate information, normalizing the parameters of skew is ill-posed as there lacks standard form for a random patch. However, if a local patch contains regular structure, such as significant horizontal/vertical lines, we can rectify the patch to make horizontal lines go horizontal and vertical lines vertical. In this way, skew transform is normalized with the patch rectified to standard shape. We can summarize our observatoin as follows:
When a local patch of an image is subject to regular appearance, we can remove its skew ambiguity by rectifying the patch with an affine transform. Formulation. Fig. 2 illustrates how an object and an image patch could be rectified and standardized. In order to formulate the rectification process into a tangible problem, proper mathematical representation is needed for rectified patch. Inspired by TILT, we note that a rectified patch in our scenario is intrinsically low-rank, and could be decomposed into a basic matrix whose rank is small and an error matrix whose entries are sparse. In this regard, finding the optimal transform could be formulated into the following optimization problem:
where I is the original patch, I 0 and E are the low-rank matrix and error matrix we seek to optimize respectively. λ is a weight parameter, and the l 0 norm measures the sparsity of noise. τ is the transform we desire to compute. In spite our formulation is identical to TILT, it has two fundamental differences: first, instead of seeking a global lowrank transform, we find local low-rank structure in search of local invariance. Second, we employ the Augmented Lagrange Method (ALM) solver similar to TILT, but based on its property of locality, we define and compute Low-rank Integral Map first and use it to accelerate the process. Our feature is also more flexible than TILT as we are able to treat a larger group of global deformations by approximating them with local affine transformations. The Low-rank Prior. The success of Low-rank SIFT lies in the assumption of local regularity. In order to validate our assumption, we did a field test using our place recognition dataset. The dataset contains rectified building images of different styles. We select a few images from several cities. For each image, we conduct an arbitrary prospective transform to simulate different camera viewpoints. For each image, we randomly sample several patches on the surface of building, and rectify them locally with low-rank pursuit (Equation 1). The transformed patch is then compared against the original one. As we expected, we see a huge increase of similarity after performing low-rank transform (Table I) Table I . Similarities between deformed patch and original one before and after performing low-rank transform on deformed patch
Fixing the Aspect Ratio. Under the hood, skew is caused by the change of relative orientation and scale of camera axes, which involves two parameters. Low-rank transform only normalized the first one by forcing the two axes to be mutually orthogonal but their relative scale remains unknown. For example, for a rectangle projected as a parallelogram, after a low-rank transform it is possible to be converted to a square. Fortunately in our experiment, we found this issue largely minor, and we can simply fix the aspect ratio, which has trivial impact on image matching results. This could be explained from two aspects. First, our interest point are mostly detected at corners, thus changing local aspect ratio results in similar patches. Second, SIFT itself is a robust descriptor against mild deformation as well. From this respect, The key effect of Low-rank SIFT is to alleviate SIFT's sensitivity to large skew.
III. COMPUTING LOW-RANK SIFT
By way of analysis above, Low-rank SIFT could be computed via the following three stages. First, feature points are detected using Harris Corner detector. Then, we perform low-rank transform on each feature point to locally rectify each patch. Finally, descriptors for the transformed patch at each point are computed using SIFT. Note that the combination of Harris Corner Detector and SIFT is conventional which was first introduced in [12] . The Computational Cost. To compute Low-rank SIFT descriptors for an entire image of moderate size, as many as hundreds of low-rank optimizations on all feature points could be expected. Using the Augmented Lagrange Multiplier (ALM) solver [13] , each low-rank transform contains multiple iterations of singular value decomposition and is computationally intensive. Although local patch size is relatively small (in experiment we restrict the size to be 50×50, as low-rank optimization would fail when the matrix size is overly small [14] ), it would still take up to 0.2 seconds per patch on average [15] . For an image with 500 feature points, it would take more than one minute to find the low-rank structure of every patch and rectify each of them, which is infeasible for fast image retrieval. In light of this we developed methods to reduce the time cost. Low-Rank Integral Map. The Computation of Low-rank Integral Map is a pre-processing step for fast computation of low-rank transform at any point, inspired by integral image used in SURF [16] for fast computation of pixel sum of any region. We first partition the image into m × n nonoverlapping blocks, and then for each block we compute a low-rank transform that rectifies that block. The map is defined as the union of all block transforms. For any given point, we could find the block containing that point, and propagate the already computed low-rank transform from block center to that point. The next theorem lays the foundation for our low-rank propagation.
Theorem 3.1 Local low-rank transform at any point as its center could be approximated by the transform centered at a neighboring point.
The theorem could be explained by the fact that, given any neighboring patch, we can assume they have almost identical affine property. That being said, T 0 which rectifies the patch around p 0 will rectify the patch around p as well when applied. Therefore, T could be approximated by T 0 plus a shift of center from p 0 to p, i.e. T = T 0 • T t , where T t represents the translation matrix from p 0 to p.
Empirically, if the image does not suffer from dramatic distortion, block size of 60 × 60 usually works well for the purpose of approximating low-rank transform everywhere. In this way we reduce the number of low-rank optimizations to only a few. Fast Low-Rank Factorization. The computation of lowrank integral map could be expedited, inspired by many of the recent fast low-rank factorization methods [17] , [18] . One of the main ideas behind these methods is to pre-process the input matrix, either reduce its dimension or regularize its structure. We also observe that for adjacent patches, they usually share similar affine property. Therefore we could use the already computed transform of neighboring block as prior information to pre-transform a block. Experiments for each block j in row i do 6: if j=1 then 7: Compute low-rank transform Tij for Bij. 8 :
Pre-transform Bij to B ij using T i(j−1) .
10:
Compute low-rank transform Tij for Bij based on B ij . Let P be the 50 × 50 patch around pi.
19:
Let Ti be the pre-computed low-rank transform, when Bi is the block containing pi. Let T be the combined transform after translating Ti to pi. Compute P = P • T and p = T (p).
20:
Compute SIFT descriptor vi of point p and patch P . 21: end for 22: Return: Low-rank SIFT vector V = {vi}.
show that it greatly reduces the rounds of iterations as with this pre-processing step a block could already be roughly rectified. Another approach helpful to us is paralleled processing. This is possible as the optimization of blocks are mutually independent. In practice, we combine these two methods. We paralleling process each row and for each block in one row we process it sequentially and leverage computed transform of adjacent block.
The Low-rank SIFT algorithm is summarized in Algorithm 1.
IV. EXPERIMENTS
We demonstrate the effectiveness of Low-rank SIFT by showing its superior performance in place recognition task. Buildings, unlike natural objects, are usually redundant in regularity, and are perfect candidate to utilize the power of Low-rank SIFT. This section is organized as follows. First, our method of constructing database of geotagged building images is described. Next, place recognition performance using Low-rank SIFT is compared against Harris corner, ASIFT and MSER detectors, all of which are combined with SIFT descriptor. Experiment results are then analyzed and discussed. Constructing Database of Geotagged Buildings. The flourish of web geography services such as Google Earth and Bing Map makes it possible to fetch large geographical data from online directly. We propose a method to automatically construct database of geotagged building images by automatically downloading, extracting and processing images from Google Streetview. The database is then used in our place recognition experiment.
Given the coordinate of the city to construct the database with as input, our method consists of the following steps. 1. We sample 2D panorama images and 3D depth maps at the vicinity of the given location from Google Streetview. 3D depth maps provides depth information for each 2D image at pixel level. We will then get rectified building images using combined 2D-3D information. 2. Sky is segmented from 2D image using color. This is because 3D depth map is usually very inaccurate at top parts of buildings due to limited laser scan range, thus sky is used to refine the upper boundary. 3. We fit planes with 3D points and project the 3D planes back to 2D images. Façades are cropped using both planes and sky. 4. Buildings of panoramic view are transformed to perspective view based on the geometry of panorama. 5. Perspective view is further rectified based on 3D points, whose spatial coordinates are used to compute the appropriate transform. Geolocation acquired with Google Streetview is saved along with the rectified image. Table II listed the cities we have in our database and the quantity of building images in each city. The quality of our image is not flawless. Sometimes there are blurs and occlusions, and for some images the top part of buildings are rather obscure. Nevertheless we find it sufficient for effective place recognition. As the size of panorama image is very large, it also takes a significant amount of time to generate the database, where each city would take up to half a day to execute on an ordinary machine. Place Recognition with Feature Selection. We test place recognition using Low-rank SIFT and other features using acquired database. Vocabulary tree model for object recognition [19] is employed as it is scalable and fast enough for database of large size, as is in our case. The vocabulary tree is constructed using features of images in database and feature vector of query image is supplied and traverses the tree, and the nodes visited are used to compare and compute their similarity scores. We adopt a novel scheme to select useful features from query image, and found it capable of improving our recognition performance significantly (Table III) . The reason for feature selection is that query images, unlike those in database which are mostly cropped and clean, usually suffer from noise and occlusions (sky, tree and pedestrian). Based on the low-rank property of local patch of buildings, we only keep interest points of those with patches of certain rank, and filter the rest. Typically valid rank should not be too small which corresponds to homogeneous color (sky), nor should it be overly large which corresponds to natural objects. In experiment we found retaining patches of rank between 2 to 5 generally works well for feature selection purpose.
Performance of different features are listed and compared in Table III and Fig. 3 . Our query images are randomly selected from online, containing both buildings and other scenes. We see significant performance improvement by using Low-rank SIFT. Our result also beats previous place recognition performance benchmark of [20] . As expected, improvements are mostly contributed by building queries, i.e., those with regular structures and able to leverage Lowrank SIFT, rather than queries of open scenes. A successful example is shown in Fig. 3 , where perspective view of DoubleTree hotel is given as input, and only Low-rank SIFT successfully identifies the location. The success of Low-rank SIFT comes as no surprise. By carefully examining the distance between query image and database, we found the minimum distance, i.e. distance of the closest match, drops as much as 50% after applying Lowrank SIFT. More concrete analysis indicates that once rectified, most query features would fall in the same node with their correctly matched features in database. Our method is also efficient, as computation of Low-rank SIFT plus image retrieval could mostly be accomplished within 5 seconds. Failure cases are usually caused by severe image distortion that could not be recovered using local affine transform, or when the scene is undermined by large occlusions.
V. CONCLUSION
In this paper, we propose a novel affine invariant feature for place recognition by exploiting the local low-rank property of man-made objects. The feature could be computed efficiently using Low-rank Integral Map and be further compressed based on local patch rank. Experiment shows its superior performance against other conventional features. There are two limitations however. First, low-rank pursuit could easily fail at boundary or noisy locations. Second, the time cost is higher than computing SIFT alone so real-time processing is hindered. As future work, we aim to better address these two issues, and develop the feature to expand its usage to other computer vision tasks, such as image matching and repetition detection.

{'paper_id': '10080367', 'title': 'Low-rank SIFT: An affine invariant feature for place recognition', 's2_url': 'https://api.semanticscholar.org/CorpusID:10080367', 'source': 'S2ORC'}