cvpr cvpr2013 cvpr2013-162 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Abstract: Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.
Reference: text
sentIndex sentText sentNum sentScore
1 FAsT-Match: Fast Affine Template Matching Simon Korman Daniel Reichman Tel-Aviv University Weizmann Institute Abstract Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. [sent-1, score-1.091]
2 There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. [sent-2, score-0.248]
3 For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. [sent-3, score-0.23]
4 As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. [sent-5, score-0.807]
5 To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations. [sent-7, score-0.808]
6 Introduction Image matching is a core computer vision task and template matching is an important sub-class of it. [sent-9, score-0.559]
7 We propose an algorithm that matches templates under arbitrary 2D affine transformations. [sent-10, score-0.344]
8 The algorithm is fast and is guaranteed to find a solution that is within an additive error of the global optimum. [sent-11, score-0.136]
9 Template matching under more general conditions, which include also rotation, scale or 2D affine transformation leads to an explosion in the number of potential transformations that must be evaluated. [sent-16, score-0.942]
10 Fast-Match deals with this explosion by properly discretizing the space of 2D affine transformations. [sent-17, score-0.363]
11 The key observation is that the number of potential transformations that should be evaluated can be bounded based on the assumption that images are smooth. [sent-18, score-0.284]
12 Small variations in the parameters of the transformation will result in small variations in the location of the mapping, and because of the image smoothness assumption, the Sum-of-AbsoluteDifference (SAD) error measure will not change much. [sent-19, score-0.32]
13 Gilad Tsur Shai Avidan Weizmann Institute Tel-Aviv University Given a desired accuracy level δ we construct a net of transformations such that each transformation (outside the net) has an SAD error which differs by no more than δ from that of some transformation in the net. [sent-20, score-1.257]
14 For each transformation within the net we approximate the SAD error using random sampling. [sent-21, score-0.736]
15 When δ is small the net size becomes large and we apply a branch-and-bound approach. [sent-22, score-0.416]
16 We start with a sparse net, discard all transformations in the net whose errors are not within a bound from the best error in the net and then increase the sampling rate around the remaining ones. [sent-23, score-1.22]
17 Fast-Match, on the other hand, does not rely on an initial guess and is guaranteed to find an approximation to the global optimum. [sent-27, score-0.131]
18 Such methods assume that feature points can be reliably detected and matched in both the image and the template so that there are enough potent matches to estimate the global 2D affine transformation, perhaps using RANSAC [4]. [sent-29, score-0.708]
19 Despite the large body of work in this field, the process can fail, especially if there are not enough distinct features in the template or the image. [sent-30, score-0.412]
20 OF is clearly less practical when the size of the template is considerably smaller than the size of the image because it does not have a good initial guess. [sent-32, score-0.385]
21 In such cases we can use feature point matching to seed the initial guess of an OF algorithm. [sent-33, score-0.139]
22 However, it is increasingly difficult to detect distinct feature points as the size of the template decreases. [sent-34, score-0.385]
23 They find the correct template location (green parallelogram) given a close enough initialization (dashed green parallelogram), but might fail (converge to solid red parallelogram) with a less accurate initialization (dashed red parallelogram). [sent-44, score-0.412]
24 They typically will not detect a single matching feature in such an example. [sent-46, score-0.087]
25 While strictly speaking, Fast-Match minimizes the SAD error and our experiments validate this, we also show that minimizing SAD error serves as a proxy to finding the location of the template and we show results to this effect. [sent-50, score-0.507]
26 Often, even when the size of the template is small, Fast-Match can still find the correct match, whereas feature based methods struggle to detect and match feature points between the template and the image. [sent-51, score-0.77]
27 We run it on a large number of images to evaluate its performance on templates of different sizes, and in the presence of different levels of degradation (JPEG artifacts, blur, and gaussian noise). [sent-53, score-0.159]
28 Background Our work grew out of the template matching literature which we review next. [sent-58, score-0.472]
29 Template Matching Evaluating only a subset of the possible transformations was considered in the limited context of Template Matching under 2D translation. [sent-61, score-0.248]
30 [1] derive an upper bound on appearance distance, given the spatial overlap of two windows in an image, and use it to bound the distances of many window pairs between two images. [sent-63, score-0.158]
31 ” and devise a new rank measure that determines if one can slide the test window by more than one pixel. [sent-65, score-0.1]
32 Extending Template Matching to work with more general transformations was also considered in the past. [sent-66, score-0.248]
33 [6] proposed an affine image model for motion estimation, between images which have undergone a mild affine deformation. [sent-68, score-0.619]
34 They exhaustively search a range of the affine space (practically - a very limited one, with only uniform scale). [sent-69, score-0.296]
35 Kim and Ara u´jo [7] proposed a grayscale template matching algorithm that considers also rotation and scale. [sent-71, score-0.607]
36 Finally, Tsai and Chiang [21] developed a template matching method that considers also rotation, which is based on wavelet decompositions and ring projections. [sent-73, score-0.529]
37 The latter three methods do not provide guarantees regarding the approximation quality of the matching. [sent-74, score-0.09]
38 Unlike our method, which works in appearance space, their method minimizes the distance from the target transformation in parameter space. [sent-76, score-0.301]
39 Alternatively, one can use feature-based methods such as SIFT [10], or its variant ASIFT [14] which is designed to be affine invariant. [sent-81, score-0.296]
40 Given enough corresponding feature points it is possible to compute the global affine transformation between the images. [sent-83, score-0.596]
41 This approach relies on the assumption that the same interest points can be detected in each image independently and that the image descriptors are invariant to 2D affine transformations so that they can be matched across images. [sent-84, score-0.544]
42 Other related work Our work is also inspired by techniques from the field of sublinear algorithms. [sent-85, score-0.137]
43 The use of sublinear algorithms in image processing was advocated by Rashkodnikova [17] and followed by Tsur and Ron [18] as well as by Kleiner et al. [sent-86, score-0.137]
44 1 We w×inll refer to I1 as the template and to I2 as the image. [sent-92, score-0.385]
45 ∈Iq∈mNa(xp)|I(p) − I(q)| We deal with affine transformations in the plane that have scaling factors in the range [1/c, c] for a fixed positive constant c. [sent-95, score-0.571]
46 Such a transformation T can be seen as multiplying the pixel vector by a 2 2 non-singular matrix and adding a ”thteran psixlaetlio vne”ct vector, t2h×en2 rounding duolawrn m tahter resulting numbers. [sent-96, score-0.3]
47 Such a transformation can be parameterized by six degrees of freedom. [sent-97, score-0.273]
48 Let ΔT(I1 , I2) be the (normalized) sum of absolute differences (SAD) distance between two images I1, I2 with respect to a transformation T that maps pixels p ∈ I1 to pixels itn t oI2 a. [sent-98, score-0.341]
49 Tmhaeminimum over all affine transformations T of ΔT (I1, I2) is denoted by Δ(I1 , I2). [sent-103, score-0.544]
50 A crucial component of our algorithm is the net of transformations. [sent-104, score-0.416]
51 This net is composed of a small set of transformations, such that any affine transformation is ”close” to a transformation in the net. [sent-105, score-1.258]
52 This will enable us to consaisd ethr only a laimriaitteiodn ns eVt ooff tIransformations, rather than the complete set of affine transformations. [sent-126, score-0.296]
53 For a positive α, a net of (affine) transformations T = {TiF}oilr=1 a i pso an α-cover nife fto orf every ae)ff itnraen tsrfaonrmsfoatrmioantsio Tn T =, {thTer}e exists some Tj in T , such that ? [sent-128, score-0.664]
54 δn1-cover of the set of affine transformations, where δ ∈ (0, 1] is an accuracy parameter wanhsicfohr misa an input hoefr tehe δ algorithm. [sent-132, score-0.296]
55 Ta nhe a nccuumrbaceyr of transformations in the net grows as a function of δ. [sent-133, score-0.664]
56 n [9] we show how to construct such a net Nδ, of size ? [sent-135, score-0.416]
57 Algorithm Description Θ We describe a fast randomized algorithm that returns, with high probability, a transformation T such that ΔT(I1 , I2) is close to Δ(I1 , I2). [sent-140, score-0.273]
58 The algorithm examines the transformations in the net Nδ. [sent-141, score-0.71]
59 These guarantees are given as a function of the net’s parameter δ and of the total variation V of I1. [sent-143, score-0.125]
60 Denote the resulting value dT Return the transformation T with the minimal value dT In Step 1 of the algorithm we give a sublinear approximation of ΔT (I1, I2), that is presented in subsection 3. [sent-145, score-0.449]
61 We proceed to bound the difference between the quality of the algorithm’s result and that of the optimal transformation in terms of two parameters - V and δ, where fδo ramlsaot coonn tirnol tse mthes soifze t woof tphaer mnete aernsd -h Venc aen dde δte,r wmhineerse the running time. [sent-147, score-0.338]
62 We first establish the following theorem which helps to bound the difference between ΔT? [sent-148, score-0.134]
63 (I1, I2) and ΔT(I1 , I2) for a general affine transformation T? [sent-149, score-0.569]
64 (−I1 1 , )I2 i)s and ΔT(I1 , I2) is bounded by the total sum of differences between vertically neighboring pixels in I1. [sent-173, score-0.101]
65 Likewise, when the translations are by k pixels and by k + δn1 pixels - the change in the SAD is bounded by the total − × variation multiplied by δn1 . [sent-175, score-0.209]
66 We measured the total variation of 9500 random templates from the Pascal dataset [3]. [sent-197, score-0.122]
67 2, implies that Algorithm 1 is guaranteed to provide an additive approximation of O(δ), for a given precision parameter δ. [sent-201, score-0.162]
68 Approximating the Distance dT(I1 , I2) We now turn to describe the sublinear algorithm which we use in Step 1 of the algorithm to approximate ΔT (I1, I2). [sent-204, score-0.137]
69 and a transformation T Output: An estimate of the distance ΔT(I1 , I2) • Sample m = Θ(1/? [sent-210, score-0.273]
70 1 Given images I1 and I2 and an affine transformation T, Algorithm 2 returns a value dT such that |dT − ΔT (I1, I2) | ≤ ? [sent-220, score-0.569]
71 For simplicity the space of transformations is in 1D (x-axis) against the SAD-error (y-axis). [sent-231, score-0.248]
72 Horizontal dotted lines are SAD errors of: Black (Optimal transformation, which is generally off the net), Red (best transformation found on the net), Green (closest-to-Optimal transformation on the net) and Blue (threshold). [sent-234, score-0.546]
73 The Branch-and-Bound Scheme To achieve an additive approximation of O(δ) in Algorithm 1 we must test the complete net of transformations Nδ, whose size is Θ( · ( Achieving a satisfactory error rate would require a net Nδ where δ is small. [sent-238, score-1.215]
74 ·u (sing value of δ (linear in 1/δ6) renders our algorithm impractical, despite the fact that our testing of each transformation is extremely efficient. [sent-240, score-0.273]
75 To overcome this difficulty, we devise a branch-and-bound scheme, using nets of increasing resolution while testing small fractions of the transformations in the rapidly growing nets. [sent-241, score-0.314]
76 As a result, the number of transformations we test in order to achieve a certain precision is reduced dramatically. [sent-243, score-0.282]
77 In each stage, Algorithm 1 is run on a subset S of the net Nδ. [sent-246, score-0.416]
78 Figure 2 gives an illustration of transformations exaNmined by the algorithm and their errors (in particular Opt - the optimal, Best - the best examined, and Closest - the closest on the net to opt). [sent-247, score-0.735]
79 We denote by e(Opt) the error of opt and similarly for best and closest. [sent-248, score-0.149]
80 We wish to rule out a large portion of the transformation space before proceeding to the next finer resolution net, where the main concern is that the optimal transformation should not be ruled out. [sent-249, score-0.546]
81 Had we known e(Closest), we could have used it as a threshold, ruling out all transformations with error exceeding it. [sent-250, score-0.322]
82 We achieve high success rates across the dataset, with the exception of the higher degradation levels of the ’Wall’ and ’Boat’ sequences. [sent-263, score-0.111]
83 Note that, the smaller the template area in the target image, the more demanding the overlap error criterion becomes8. [sent-264, score-0.46]
84 The results of Experiment II can not 7Note that because we are approximating a projective transformation using an affine one (which means matching a general quadrilateral using a parallelogram), the optimal overlap error may be far greater than 0. [sent-267, score-0.832]
85 Performance dimensions: under different template sizes and image degradations. [sent-270, score-0.413]
86 Analysis is presented for two different template In each, the x-axis stands for the increasing levels of image degradation, ranging from 0 (no degradation) to 5 (highest). [sent-272, score-0.414]
87 Fast-Match is capable of handling smaller and smaller template sizes, while the feature based method ASIFT, deteriorates significantly as template dimension decreases. [sent-274, score-0.77]
88 be compared with those of [12] as they do not deal directly with template or image matching. [sent-277, score-0.412]
89 In this experiment too, Fast-Match deals well with photometric changes as well as the blur and JPEG artifacts. [sent-278, score-0.102]
90 This dataset is more challenging for the performance of the algorithm, as well as for experimentation: The template typically includes several planes (which do not map to the other image under a rigid transformation), partial occlusions and changes of illumination and of viewpoint. [sent-285, score-0.385]
91 As there is no rigid transformation between the images, we evaluated the performance of fast match on 200 images visually. [sent-286, score-0.273]
92 In most of the remaining cases producing a good mapping from the given template was impossible: On 40 of the images, the location corresponding to the template was not present in the other image, or that the template spanned several planes which can not be mapped uniquely. [sent-288, score-1.237]
93 In each of the remaining images a blue parallelogram indicates the mapping produced by FastMatch, while a green quadrilateral marks the ground truth. [sent-292, score-0.35]
94 Conclusions We presented a new algorithm, Fast-Match, which extends template matching to handle arbitrary 2D igpaowmn ldsgytho1ecms9atnlhuocedgfibr tlhwodifceabtsuymniodeafgtimnhlepsoFadutwigen aohdstrelipon6c[sm. [sent-293, score-0.472]
95 Zurich Dataset [19] - Good Examples: In the blue rectangle on the left of each pair of images is the template presented to Fast-Match. [sent-301, score-0.414]
96 In the blue parallelogram on the right is the re- gion matched by the algorithm. [sent-302, score-0.246]
97 Zurich Dataset [19] - the remaining: Failures (row 1), Occlusions (row 2), Template or Target template is out of plane/image (row 3) demonstrating that it performs well, being robust to different real-world conditions. [sent-305, score-0.385]
98 An interesting direction for future research is to apply similar methods to more diverse families of transformations (e. [sent-307, score-0.248]
99 Motion displacement estimation using an affine model for image matching. [sent-347, score-0.296]
100 Asift: A new framework for fully affine invariant image comparison. [sent-402, score-0.296]
wordName wordTfidf (topN-words)
[('net', 0.416), ('template', 0.385), ('affine', 0.296), ('transformation', 0.273), ('transformations', 0.248), ('sad', 0.239), ('parallelogram', 0.217), ('asift', 0.137), ('sublinear', 0.137), ('degradation', 0.111), ('opt', 0.102), ('tsur', 0.093), ('matching', 0.087), ('zurich', 0.082), ('grayscale', 0.074), ('closest', 0.071), ('theorem', 0.069), ('mikolajczyk', 0.066), ('bound', 0.065), ('fuh', 0.062), ('kleiner', 0.062), ('pele', 0.062), ('quadrilateral', 0.062), ('reichman', 0.062), ('slide', 0.061), ('dt', 0.061), ('guess', 0.052), ('korman', 0.051), ('guarantees', 0.051), ('additive', 0.049), ('ron', 0.048), ('templates', 0.048), ('error', 0.047), ('examines', 0.046), ('ouyang', 0.046), ('holds', 0.044), ('buildings', 0.043), ('variation', 0.043), ('ara', 0.042), ('mapping', 0.042), ('mapped', 0.04), ('guaranteed', 0.04), ('approximation', 0.039), ('approximating', 0.039), ('devise', 0.039), ('jpeg', 0.039), ('photometric', 0.038), ('explosion', 0.038), ('weizmann', 0.037), ('alexe', 0.036), ('bounded', 0.036), ('blur', 0.035), ('mea', 0.035), ('precision', 0.034), ('return', 0.034), ('pixels', 0.034), ('tsai', 0.033), ('rotation', 0.033), ('tj', 0.032), ('total', 0.031), ('translations', 0.031), ('mappings', 0.03), ('tian', 0.03), ('claim', 0.029), ('deals', 0.029), ('blue', 0.029), ('wavelet', 0.029), ('stands', 0.029), ('minimizes', 0.028), ('sizes', 0.028), ('wall', 0.028), ('overlap', 0.028), ('baker', 0.028), ('discard', 0.028), ('considers', 0.028), ('eisp', 0.027), ('eoqfu', 0.027), ('titr', 0.027), ('awi', 0.027), ('ofvisual', 0.027), ('hdo', 0.027), ('chiang', 0.027), ('diagrams', 0.027), ('ethl', 0.027), ('fractions', 0.027), ('ncdl', 0.027), ('newman', 0.027), ('provable', 0.027), ('qfr', 0.027), ('ruling', 0.027), ('tahter', 0.027), ('tam', 0.027), ('tchoants', 0.027), ('trmhea', 0.027), ('undergone', 0.027), ('vne', 0.027), ('werman', 0.027), ('enough', 0.027), ('runtime', 0.027), ('deal', 0.027)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000014 162 cvpr-2013-FasT-Match: Fast Affine Template Matching
Author: Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Abstract: Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.
2 0.15394616 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
Author: Elhanan Elboer, Michael Werman, Yacov Hel-Or
Abstract: The graph Laplacian operator, which originated in spectral graph theory, is commonly used for learning applications such as spectral clustering and embedding. In this paper we explore the Laplacian distance, a distance function related to the graph Laplacian, and use it for visual search. We show that previous techniques such as Matching by Tone Mapping (MTM) are particular cases of the Laplacian distance. Generalizing the Laplacian distance results in distance measures which are tolerant to various visual distortions. A novel algorithm based on linear decomposition makes it possible to compute these generalized distances efficiently. The proposed approach is demonstrated for tone mapping invariant, outlier robust and multimodal template matching.
3 0.14558627 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
Author: Jiayi Ma, Ji Zhao, Jinwen Tian, Zhuowen Tu, Alan L. Yuille
Abstract: We present a new point matching algorithm for robust nonrigid registration. The method iteratively recovers the point correspondence and estimates the transformation between two point sets. In the first step of the iteration, feature descriptors such as shape context are used to establish rough correspondence. In the second step, we estimate the transformation using a robust estimator called L2E. This is the main novelty of our approach and it enables us to deal with the noise and outliers which arise in the correspondence step. The transformation is specified in a functional space, more specifically a reproducing kernel Hilbert space. We apply our method to nonrigid sparse image feature correspondence on 2D images and 3D surfaces. Our results quantitatively show that our approach outperforms state-ofthe-art methods, particularly when there are a large number of outliers. Moreover, our method of robustly estimating transformations from correspondences is general and has many other applications.
4 0.12073255 423 cvpr-2013-Template-Based Isometric Deformable 3D Reconstruction with Sampling-Based Focal Length Self-Calibration
Author: Adrien Bartoli, Toby Collins
Abstract: It has been shown that a surface deforming isometrically can be reconstructed from a single image and a template 3D shape. Methods from the literature solve this problem efficiently. However, they all assume that the camera model is calibrated, which drastically limits their applicability. We propose (i) a general variational framework that applies to (calibrated and uncalibrated) general camera models and (ii) self-calibrating 3D reconstruction algorithms for the weak-perspective and full-perspective camera models. In the former case, our algorithm returns the normal field and camera ’s scale factor. In the latter case, our algorithm returns the normal field, depth and camera ’s focal length. Our algorithms are the first to achieve deformable 3D reconstruction including camera self-calibration. They apply to much more general setups than existing methods. Experimental results on simulated and real data show that our algorithms give results with the same level of accuracy as existing methods (which use the true focal length) on perspective images, and correctly find the normal field on affine images for which the existing methods fail.
5 0.10096467 46 cvpr-2013-Articulated and Restricted Motion Subspaces and Their Signatures
Author: Bastien Jacquet, Roland Angst, Marc Pollefeys
Abstract: Articulated objects represent an important class ofobjects in our everyday environment. Automatic detection of the type of articulated or otherwise restricted motion and extraction of the corresponding motion parameters are therefore of high value, e.g. in order to augment an otherwise static 3D reconstruction with dynamic semantics, such as rotation axes and allowable translation directions for certain rigid parts or objects. Hence, in this paper, a novel theory to analyse relative transformations between two motion-restricted parts will be presented. The analysis is based on linear subspaces spanned by relative transformations. Moreover, a signature for relative transformations will be introduced which uniquely specifies the type of restricted motion encoded in these relative transformations. This theoretic framework enables the derivation of novel algebraic constraints, such as low-rank constraints for subsequent rotations around two fixed axes for example. Lastly, given the type of restricted motion as predicted by the signature, the paper shows how to extract all the motion parameters with matrix manipulations from linear algebra. Our theory is verified on several real data sets, such as a rotating blackboard or a wheel rolling on the floor amongst others.
6 0.091965638 170 cvpr-2013-Fast Rigid Motion Segmentation via Incrementally-Complex Local Models
7 0.090567522 177 cvpr-2013-FrameBreak: Dramatic Image Extrapolation by Guided Shift-Maps
8 0.087580033 457 cvpr-2013-Visual Tracking via Locality Sensitive Histograms
9 0.086823069 334 cvpr-2013-Pose from Flow and Flow from Pose
10 0.080389701 97 cvpr-2013-Correspondence-Less Non-rigid Registration of Triangular Surface Meshes
11 0.075906716 361 cvpr-2013-Robust Feature Matching with Alternate Hough and Inverted Hough Transforms
12 0.074530423 107 cvpr-2013-Deformable Spatial Pyramid Matching for Fast Dense Correspondences
13 0.073411748 244 cvpr-2013-Large Displacement Optical Flow from Nearest Neighbor Fields
14 0.071646139 106 cvpr-2013-Deformable Graph Matching
15 0.070740514 307 cvpr-2013-Non-uniform Motion Deblurring for Bilayer Scenes
17 0.069604389 369 cvpr-2013-Rotation, Scaling and Deformation Invariant Scattering for Texture Discrimination
18 0.068387479 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
19 0.068308778 153 cvpr-2013-Expanded Parts Model for Human Attribute and Action Recognition in Still Images
20 0.067601822 109 cvpr-2013-Dense Non-rigid Point-Matching Using Random Projections
topicId topicWeight
[(0, 0.16), (1, 0.06), (2, -0.011), (3, 0.018), (4, 0.014), (5, 0.004), (6, 0.011), (7, -0.063), (8, -0.008), (9, -0.016), (10, -0.002), (11, 0.072), (12, -0.044), (13, -0.045), (14, 0.039), (15, -0.095), (16, 0.015), (17, -0.019), (18, 0.075), (19, 0.035), (20, -0.022), (21, -0.014), (22, 0.053), (23, -0.059), (24, 0.045), (25, -0.023), (26, -0.042), (27, 0.03), (28, 0.046), (29, 0.077), (30, 0.032), (31, -0.003), (32, 0.022), (33, -0.034), (34, 0.027), (35, -0.05), (36, -0.105), (37, 0.082), (38, 0.035), (39, 0.064), (40, 0.005), (41, 0.042), (42, 0.018), (43, 0.027), (44, 0.028), (45, -0.066), (46, 0.043), (47, -0.033), (48, 0.06), (49, -0.01)]
simIndex simValue paperId paperTitle
same-paper 1 0.9413389 162 cvpr-2013-FasT-Match: Fast Affine Template Matching
Author: Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Abstract: Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.
2 0.84541082 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
Author: Jiayi Ma, Ji Zhao, Jinwen Tian, Zhuowen Tu, Alan L. Yuille
Abstract: We present a new point matching algorithm for robust nonrigid registration. The method iteratively recovers the point correspondence and estimates the transformation between two point sets. In the first step of the iteration, feature descriptors such as shape context are used to establish rough correspondence. In the second step, we estimate the transformation using a robust estimator called L2E. This is the main novelty of our approach and it enables us to deal with the noise and outliers which arise in the correspondence step. The transformation is specified in a functional space, more specifically a reproducing kernel Hilbert space. We apply our method to nonrigid sparse image feature correspondence on 2D images and 3D surfaces. Our results quantitatively show that our approach outperforms state-ofthe-art methods, particularly when there are a large number of outliers. Moreover, our method of robustly estimating transformations from correspondences is general and has many other applications.
3 0.77816683 47 cvpr-2013-As-Projective-As-Possible Image Stitching with Moving DLT
Author: Julio Zaragoza, Tat-Jun Chin, Michael S. Brown, David Suter
Abstract: We investigate projective estimation under model inadequacies, i.e., when the underpinning assumptions oftheprojective model are not fully satisfied by the data. We focus on the task of image stitching which is customarily solved by estimating a projective warp — a model that is justified when the scene is planar or when the views differ purely by rotation. Such conditions are easily violated in practice, and this yields stitching results with ghosting artefacts that necessitate the usage of deghosting algorithms. To this end we propose as-projective-as-possible warps, i.e., warps that aim to be globally projective, yet allow local non-projective deviations to account for violations to the assumed imaging conditions. Based on a novel estimation technique called Moving Direct Linear Transformation (Moving DLT), our method seamlessly bridges image regions that are inconsistent with the projective model. The result is highly accurate image stitching, with significantly reduced ghosting effects, thus lowering the dependency on post hoc deghosting.
4 0.74975282 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
Author: Elhanan Elboer, Michael Werman, Yacov Hel-Or
Abstract: The graph Laplacian operator, which originated in spectral graph theory, is commonly used for learning applications such as spectral clustering and embedding. In this paper we explore the Laplacian distance, a distance function related to the graph Laplacian, and use it for visual search. We show that previous techniques such as Matching by Tone Mapping (MTM) are particular cases of the Laplacian distance. Generalizing the Laplacian distance results in distance measures which are tolerant to various visual distortions. A novel algorithm based on linear decomposition makes it possible to compute these generalized distances efficiently. The proposed approach is demonstrated for tone mapping invariant, outlier robust and multimodal template matching.
5 0.69714481 424 cvpr-2013-Templateless Quasi-rigid Shape Modeling with Implicit Loop-Closure
Author: Ming Zeng, Jiaxiang Zheng, Xuan Cheng, Xinguo Liu
Abstract: This paper presents a method for quasi-rigid objects modeling from a sequence of depth scans captured at different time instances. As quasi-rigid objects, such as human bodies, usually have shape motions during the capture procedure, it is difficult to reconstruct their geometries. We represent the shape motion by a deformation graph, and propose a model-to-partmethod to gradually integrate sampled points of depth scans into the deformation graph. Under an as-rigid-as-possible assumption, the model-to-part method can adjust the deformation graph non-rigidly, so as to avoid error accumulation in alignment, which also implicitly achieves loop-closure. To handle the drift and topological error for the deformation graph, two algorithms are introduced. First, we use a two-stage registration to largely keep the rigid motion part. Second, in the step of graph integration, we topology-adaptively integrate new parts and dynamically control the regularization effect of the deformation graph. We demonstrate the effectiveness and robustness of our method by several depth sequences of quasi-rigid objects, and an application in human shape modeling.
6 0.67390281 317 cvpr-2013-Optimal Geometric Fitting under the Truncated L2-Norm
7 0.65886247 177 cvpr-2013-FrameBreak: Dramatic Image Extrapolation by Guided Shift-Maps
8 0.65493065 361 cvpr-2013-Robust Feature Matching with Alternate Hough and Inverted Hough Transforms
9 0.60280079 106 cvpr-2013-Deformable Graph Matching
10 0.59699535 194 cvpr-2013-Groupwise Registration via Graph Shrinkage on the Image Manifold
11 0.59347796 97 cvpr-2013-Correspondence-Less Non-rigid Registration of Triangular Surface Meshes
12 0.58906996 138 cvpr-2013-Efficient 2D-to-3D Correspondence Filtering for Scalable 3D Object Recognition
13 0.57785839 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
14 0.57224321 352 cvpr-2013-Recovering Stereo Pairs from Anaglyphs
15 0.57201064 240 cvpr-2013-Keypoints from Symmetries by Wave Propagation
16 0.57155114 31 cvpr-2013-Accurate and Robust Registration of Nonrigid Surface Using Hierarchical Statistical Shape Model
17 0.556898 23 cvpr-2013-A Practical Rank-Constrained Eight-Point Algorithm for Fundamental Matrix Estimation
18 0.54974514 195 cvpr-2013-HDR Deghosting: How to Deal with Saturation?
19 0.54381812 74 cvpr-2013-CLAM: Coupled Localization and Mapping with Efficient Outlier Handling
20 0.53053129 373 cvpr-2013-SWIGS: A Swift Guided Sampling Method
topicId topicWeight
[(2, 0.19), (10, 0.145), (16, 0.034), (26, 0.063), (28, 0.011), (33, 0.277), (67, 0.052), (69, 0.04), (80, 0.012), (87, 0.077)]
simIndex simValue paperId paperTitle
1 0.91587842 361 cvpr-2013-Robust Feature Matching with Alternate Hough and Inverted Hough Transforms
Author: Hsin-Yi Chen, Yen-Yu Lin, Bing-Yu Chen
Abstract: We present an algorithm that carries out alternate Hough transform and inverted Hough transform to establish feature correspondences, and enhances the quality of matching in both precision and recall. Inspired by the fact that nearby features on the same object share coherent homographies in matching, we cast the task of feature matching as a density estimation problem in the Hough space spanned by the hypotheses of homographies. Specifically, we project all the correspondences into the Hough space, and determine the correctness of the correspondences by their respective densities. In this way, mutual verification of relevant correspondences is activated, and the precision of matching is boosted. On the other hand, we infer the concerted homographies propagated from the locally grouped features, and enrich the correspondence candidates for each feature. The recall is hence increased. The two processes are tightly coupled. Through iterative optimization, plausible enrichments are gradually revealed while more correct correspondences are detected. Promising experimental results on three benchmark datasets manifest the effectiveness of the proposed approach.
same-paper 2 0.89111149 162 cvpr-2013-FasT-Match: Fast Affine Template Matching
Author: Simon Korman, Daniel Reichman, Gilad Tsur, Shai Avidan
Abstract: Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.
3 0.86584741 5 cvpr-2013-A Bayesian Approach to Multimodal Visual Dictionary Learning
Author: Go Irie, Dong Liu, Zhenguo Li, Shih-Fu Chang
Abstract: Despite significant progress, most existing visual dictionary learning methods rely on image descriptors alone or together with class labels. However, Web images are often associated with text data which may carry substantial information regarding image semantics, and may be exploited for visual dictionary learning. This paper explores this idea by leveraging relational information between image descriptors and textual words via co-clustering, in addition to information of image descriptors. Existing co-clustering methods are not optimal for this problem because they ignore the structure of image descriptors in the continuous space, which is crucial for capturing visual characteristics of images. We propose a novel Bayesian co-clustering model to jointly estimate the underlying distributions of the continuous image descriptors as well as the relationship between such distributions and the textual words through a unified Bayesian inference. Extensive experiments on image categorization and retrieval have validated the substantial value of the proposed joint modeling in improving visual dictionary learning, where our model shows superior performance over several recent methods.
4 0.8587386 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
Author: Ian Endres, Kevin J. Shih, Johnston Jiaa, Derek Hoiem
Abstract: We propose a method to learn a diverse collection of discriminative parts from object bounding box annotations. Part detectors can be trained and applied individually, which simplifies learning and extension to new features or categories. We apply the parts to object category detection, pooling part detections within bottom-up proposed regions and using a boosted classifier with proposed sigmoid weak learners for scoring. On PASCAL VOC 2010, we evaluate the part detectors ’ ability to discriminate and localize annotated keypoints. Our detection system is competitive with the best-existing systems, outperforming other HOG-based detectors on the more deformable categories.
5 0.85721701 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
Author: Brandon Rothrock, Seyoung Park, Song-Chun Zhu
Abstract: In this paper we present a compositional and-or graph grammar model for human pose estimation. Our model has three distinguishing features: (i) large appearance differences between people are handled compositionally by allowingparts or collections ofparts to be substituted with alternative variants, (ii) each variant is a sub-model that can define its own articulated geometry and context-sensitive compatibility with neighboring part variants, and (iii) background region segmentation is incorporated into the part appearance models to better estimate the contrast of a part region from its surroundings, and improve resilience to background clutter. The resulting integrated framework is trained discriminatively in a max-margin framework using an efficient and exact inference algorithm. We present experimental evaluation of our model on two popular datasets, and show performance improvements over the state-of-art on both benchmarks.
6 0.85709792 414 cvpr-2013-Structure Preserving Object Tracking
7 0.85672492 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
8 0.85597235 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
9 0.85591394 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
10 0.8551963 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
11 0.85514134 325 cvpr-2013-Part Discovery from Partial Correspondence
12 0.85444099 408 cvpr-2013-Spatiotemporal Deformable Part Models for Action Detection
13 0.85332036 143 cvpr-2013-Efficient Large-Scale Structured Learning
14 0.85306001 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image
15 0.85283053 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
16 0.85242903 267 cvpr-2013-Least Soft-Threshold Squares Tracking
17 0.85212487 331 cvpr-2013-Physically Plausible 3D Scene Tracking: The Single Actor Hypothesis
18 0.85205615 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
19 0.85192013 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
20 0.85158223 14 cvpr-2013-A Joint Model for 2D and 3D Pose Estimation from a Single Image