text: We propose a novel multi-scale template matching method which is robust against both scaling and rotation in unconstrained environments. The key component behind is a similarity measure referred to as scalable diversity similarity (SDS). Specifically, SDS exploits bidirectional diversity of the nearest neighbor (NN) matches between two sets of points. To address the scale-robustness of the similarity measure, local appearance and rank information are jointly used for the NN search. Furthermore, by introducing penalty term on the scale change, and polar radius term into the similarity measure, SDS is shown to be a well-performing similarity measure against overall size and rotation changes, as well as non-rigid geometric deformations, background clutter, and occlusions. The properties of SDS are statistically justified, and experiments on both synthetic and real-world data show that SDS can significantly outperform state-of-the-art methods.
  @cite_18: In image retrieval based on color, the weighted distance between color histograms of two images, represented as a quadratic form, may be defined as a match measure. However, this distance measure is computationally expensive and it operates on high dimensional features (O(N)). We propose the use of low-dimensional, simple to compute distance measures between the color distributions, and show that these are lower bounds on the histogram distance measure. Results on color histogram matching in large image databases show that prefiltering with the simpler distance measures leads to significantly less time complexity because the quadratic histogram distance is now computed on a smaller set of images. The low-dimensional distance measure can also be used for indexing into the database. >
  @cite_14: This paper describes a method for robust real-time pattern matching. We first introduce a family of image distance measures, the Image Hamming Distance Family. Members of this family are robust to occlusion, small geometrical transforms, light changes, and nonrigid deformations. We then present a novel Bayesian framework for sequential hypothesis testing on finite populations. Based on this framework, we design an optimal rejection acceptance sampling algorithm. This algorithm quickly determines whether two images are similar with respect to a member of the Image Hamming Distance Family. We also present a fast framework that designs a near- optimal sampling algorithm. Extensive experimental results show that the sequential sampling algorithm's performance is excellent. Implemented on a Pentium IV 3 GHz processor, the detection of a pattern with 2,197 pixels in 640times480 pixel frames, where in each frame the pattern rotated and was highly occluded, proceeds at only 0.022 seconds per frame.
  @cite_4: 
  @cite_7: We present an efficient and noise robust template matching method based on asymmetric correlation (ASC). The ASC similarity function is invariant to affine illumination changes and robust to extreme noise. It correlates the given non-normalized template with a normalized version of each image window in the frequency domain. We show that this asymmetric normalization is more robust to noise than other cross correlation variants, such as the correlation coefficient. Direct computation of ASC is very slow, as a DFT needs to be calculated for each image window independently. To make the template matching efficient, we develop a much faster algorithm, which carries out a prediction step in linear time and then computes DFTs for only a few promising candidate windows. We extend the proposed template matching scheme to deal with partial occlusion and spatially varying light change. Experimental results demonstrate the robustness of the proposed ASC similarity measure compared to state-of-the-art template matching methods.
  @cite_9: We investigate the properties of a metric between two distributions, the Earth Mover's Distance (EMD), for content-based image retrieval. The EMD is based on the minimal cost that must be paid to transform one distribution into the other, in a precise sense, and was first proposed for certain vision problems by Peleg, Werman, and Rom. For image retrieval, we combine this idea with a representation scheme for distributions that is based on vector quantization. This combination leads to an image comparison framework that often accounts for perceptual similarity better than other previously proposed methods. The EMD is based on a solution to the transportation problem from linear optimization, for which efficient algorithms are available, and also allows naturally for partial matching. It is more robust than histogram matching techniques, in that it can operate on variable-length representations of the distributions that avoid quantization and other binning problems typical of histograms. When used to compare distributions with the same overall mass, the EMD is a true metric. In this paper we focus on applications to color and texture, and we compare the retrieval performance of the EMD with that of other distances.
  @cite_21: A new method for real time tracking of non-rigid objects seen from a moving camera is proposed. The central computational module is based on the mean shift iterations and finds the most probable target position in the current frame. The dissimilarity between the target model (its color distribution) and the target candidates is expressed by a metric derived from the Bhattacharyya coefficient. The theoretical analysis of the approach shows that it relates to the Bayesian framework while providing a practical, fast and efficient solution. The capability of the tracker to handle in real time partial occlusions, significant clutter, and target scale variations, is demonstrated for several image sequences.
  @cite_6: Locally Orderless Tracking (LOT) is a visual tracking algorithm that automatically estimates the amount of local (dis)order in the target. This lets the tracker specialize in both rigid and deformable objects on-line and with no prior assumptions. We provide a probabilistic model of the target variations over time. We then rigorously show that this model is a special case of the Earth Mover's Distance optimization problem where the ground distance is governed by some underlying noise model. This noise model has several parameters that control the cost of moving pixels and changing their color. We develop two such noise models and demonstrate how their parameters can be estimated on-line during tracking to account for the amount of local (dis)order in the target. We also discuss the significance of this on-line parameter update and demonstrate its contribution to the performance. Finally we show LOT's tracking capabilities on challenging video sequences, both commonly used and new, displaying performance comparable to state-of-the-art methods.
  @cite_0: We propose a fast algorithm for speeding up the process of template matching that uses M-estimators for dealing with outliers. We propose a particular image hierarchy called the p-pyramid that can be exploited to generate a list of ascending lower bounds of the minimal matching errors when a nondecreasing robust error measure is adopted. Then, the set of lower bounds can be used to prune the search of the p-pyramid, and a fast algorithm is thereby developed in this paper. This fast algorithm ensures finding the global minimum of the robust template matching problem in which a nondecreasing M-estimator serves as an error measure. Experimental results demonstrate the effectiveness of our method.
  @cite_5: This paper proposes a new template matching method that is robust to outliers and fast enough for real-time operation. The template and image are densely transformed in binary code form by projecting and quantizing histograms of oriented gradients. The binary codes are matched by a generic method of robust similarity applicable to additive match measures, such as L p - and Hamming distances. The robust similarity map is computed efficiently via a proposed Inverted Location Index structure that stores pixel locations indexed by their values. The method is experimentally justified in large image patch datasets. Challenging applications, such as intra-category object detection, object tracking, and multimodal image matching are demonstrated.
  @cite_10: In the majority of robot applications, including human-computer interaction, template matching is used to find a specific area in a given image or a frame of video stream. Flexible and robust template matching algorithm necessitates feature extraction, for example gradient calculation. This requires complex calculation which causes bad response time of the system. An alternative solution is the use of index table, which stores coordinates that have the same grey level. However, due to the mechanism of the matching algorithm, it is necessary to have several disadvantages in the algorithm. But these restrictions are less important, and there is an idea that copes with these limitations. This paper proposes fast and robust template matching algorithm that uses grey level index table and image rank technique. This algorithm can find specific area under the given template query image with 30 Gaussian noise.
  @cite_12: A fast pattern matching scheme termed matching by tone mapping (MTM) is introduced which allows matching under nonlinear tone mappings. We show that, when tone mapping is approximated by a piecewise constant linear function, a fast computational scheme is possible requiring computational time similar to the fast implementation of normalized cross correlation (NCC). In fact, the MTM measure can be viewed as a generalization of the NCC for nonlinear mappings and actually reduces to NCC when mappings are restricted to be linear. We empirically show that the MTM is highly discriminative and robust to noise with comparable performance capability to that of the well performing mutual information, but on par with NCC in terms of computation time.
  @cite_17: Color-based trackers recently proposed in [3,4,5] have been proved robust and versatile for a modest computational cost. They are especially appealing for tracking tasks where the spatial structure of the tracked objects exhibits such a dramatic variability that trackers based on a space-dependent appearance reference would break down very fast. Trackers in [3,4,5] rely on the deterministic search of a window whose color content matches a reference histogram color model.Relying on the same principle of color histogram distance, but within a probabilistic framework, we introduce a new Monte Carlo tracking technique. The use of a particle filter allows us to better handle color clutter in the background, as well as complete occlusion of the tracked entities over a few frames.This probabilistic approach is very flexible and can be extended in a number of useful ways. In particular, we introduce the following ingredients: multi-part color modeling to capture a rough spatial layout ignored by global histograms, incorporation of a background color model when relevant, and extension to multiple objects.
summary: In unconstrained environments, to deal with nonrigid transformations and other noises, involving global information instead of pixel-wise local information for designing a robust similarity is a key cue. Histogram matching (HM) @cite_18 @cite_21 @cite_17 , which mainly measure the similarity between two color histograms, is not restricted by geometric transformation. However, it is usually not a good choice when background clutter and occlusions appear within the windows. Earth mover's distance (EMD) @cite_9 is proposed to measure the similarity between two probability distributions. Furthermore, a more robust approach @cite_6 is proposed by using spatial-appearance representation to measure the EMD. Tone mapping similarity measure @cite_12 is proposed for handling noise, which is approximated by a piece-wise constant linear function. Asymmetric correlation @cite_7 is proposed to deal with both the noise and illumination changes. Other measures focus on improving the robustness against noise as proposed in M-estimator @cite_0 @cite_5 and Hamming-based distance @cite_10 @cite_14 . We refer the interested readers to a comprehensive survey @cite_4 .