Search

Novel large margin formulation for semantic similarity learning.Efficient optimization algorithm to solve the proposed semi-definite program (SDP).Thorough experimental study to compare the performances of several algorithms for hierarchical image classification.State-of-the-art classification performance under the hierarchical-loss criterion. In the present paper, a novel image classification method that uses the hierarchical structure of categories to produce more semantic prediction is presented. This implies that our algorithm may not yield a correct prediction, but the result is likely to be semantically close to the right category. Therefore, the proposed method is able to provide a more informative classification result. The main idea of our method is twofold. First, it uses semantic representation, instead of low-level image features, enabling the construction of high-level constraints that exploit the relationship among semantic concepts in the category hierarchy. Second, from such constraints, an optimization problem is formulated to learn a semantic similarity function in a large-margin framework. This similarity function is then used to classify test images. Experimental results demonstrate that our method provides effective classification results for various real-image datasets.

Edge weight-based segmentation methods, such as normalized cut or minimum cut, require a partition number specification for their energy formulation. The number of partitions plays an important role in the segmentation overall quality. However, finding a suitable partition number is a nontrivial problem, and the numbers are ordinarily manually assigned. This is an aspect of the general partition problem, where finding the partition number is an important and difficult issue. In this paper, the edge weights instead of the pixels are partitioned to segment the images. By partitioning the edge weights into two disjoints sets, that is, cut and connect, an image can be partitioned into all possible disjointed segments. The proposed energy function is independent of the number of segments. The energy is minimized by iterating the QPBO-α-expansion algorithm over the pairwise Markov random field and the mean estimation of the cut and connected edges. Experiments using the Berkeley database show that the proposed segmentation method can obtain equivalently accurate segmentation results without designating the segmentation numbers.

Depth estimation is essential in many light field applications. Numerous algorithms have been developed using a range of light field properties. However, conventional data costs fail when handling noisy scenes in which occlusion is present. To address this problem, we introduce a light field depth estimation method that is more robust against occlusion and less sensitive to noise. Two novel data costs are proposed, which are measured using the angular patch and refocus image, respectively. The constrained angular entropy cost (CAE) reduces the effects of the dominant occluder and noise in the angular patch, resulting in a low cost. The constrained adaptive defocus cost (CAD) provides a low cost in the occlusion region, while also maintaining robustness against noise. Integrating the two data costs is shown to significantly improve the occlusion and noise invariant capability. Cost volume filtering and graph cut optimization are applied to improve the accuracy of the depth map. Our experimental results confirm the robustness of the proposed method and demonstrate its ability to produce high-quality depth maps from a range of scenes. The proposed method outperforms other state-of-the-art light field depth estimation methods in both qualitative and quantitative evaluations.

Under the popular Markov random field (MRF) model, low-level vision problems are usually formulated by prior and likelihood models. In recent years, the priors have been formulated from high-order cliques and have demonstrated their robustness in many problems. However, the likelihoods have remained zeroth-order clique potentials. This zeroth-order clique assumption causes inaccurate solution and gives rise to undesirable fattening effect especially when window-based matching costs are employed. In this paper, we investigate high-order likelihood modeling for the stereo matching problem which advocates the dissimilarity measure between the whole reference image and the warped non-reference image. If the dissimilarity measure is evaluated between filtered stereo images, the matching cost can be modeled as high-order clique potentials. When linear filters and nonparametric census filter are used, it is shown that the high-order clique potentials can be reduced to pairwise energy functions. Consequently, a global optimization is possible by employing efficient graph cuts algorithm. Experimental results show that the proposed high-order likelihood models produce significantly better results than the conventional zeroth-order models qualitatively as well as quantitatively.

In this paper, we present a new framework for three-dimensional (3D) reconstruction of multiple rigid objects from dynamic scenes. Conventional 3D reconstruction from multiple views is applicable to static scenes, in which the configuration of objects is fixed while the images are taken. In our framework, we aim to reconstruct the 3D models of multiple objects in a more general setting where the configuration of the objects varies among views. We solve this problem by object-centered decomposition of the dynamic scenes using unsupervised co-recognition approach. Unlike conventional motion segmentation algorithms that require small motion assumption between consecutive views, co-recognition method provides reliable accurate correspondences of a same object among unordered and wide-baseline views. In order to segment each object region, we benefit from the 3D sparse points obtained from the structure-from-motion. These points are reliable and serve as automatic seed points for a seeded-segmentation algorithm. Experiments on various real challenging image sequences demonstrate the effectiveness of our approach, especially in the presence of abrupt independent motions of objects.

Conventional particle filtering-based visual ego-motion estimation or visual odometry often suffers from large local linearization errors in the case of abrupt camera motion. The main contribution of this paper is to present a novel particle filtering-based visual ego-motion estimation algorithm that is especially robust to the abrupt camera motion. The robustness to the abrupt camera motion is achieved by multi-layered importance sampling via particle swarm optimization (PSO), which iteratively moves particles to higher likelihood region without local linearization of the measurement equation. Furthermore, we make the proposed visual ego-motion estimation algorithm in real-time by reformulating the conventional vector space PSO algorithm in consideration of the geometry of the special Euclidean group SE(3), which is a Lie group representing the space of 3-D camera poses. The performance of our proposed algorithm is experimentally evaluated and compared with the local linearization and unscented particle filter-based visual ego-motion estimation algorithms on both simulated and real data sets.

The pixel labeling problems in computer vision are often formulated as energy minimization tasks. Algorithms such as graph cuts and belief propagation are prominent; however, they are only applicable for specific energy forms. For general optimization, Markov Chain Monte Carlo (MCMC) based simulated annealing can estimate the minima states very slowly. This paper presents a sampling paradigm for faster optimization. First, in contrast to previous MCMCs, the role of detailed balance constraint is eliminated. The reversible Markov chain jumps are essential for sampling an arbitrary posterior distribution, but they are not essential for optimization tasks. This allows a computationally simple window cluster sample. Second, the proposal states are generated from combined sets of local minima which achieve a substantial increase in speed compared to uniformly labeled cluster proposals. Third, under the coarse-to-fine strategy, the maximum window size variable is incorporated along with the temperature variable during simulated annealing. The proposed window annealing is experimentally shown to be many times faster and capable of finding lower energy compared to the previous Gibbs and Swendsen-Wang cut (SW-cut) sampler. In addition, the proposed method is compared with other deterministic algorithms like graph cut, belief propagation, and spectral method in their own specific energy forms. Window annealing displays competitive performance in all domains.

Graph matching is a fundamental problem in computer vision. In this paper, we propose a novel graph matching algorithm based on tabu search [13]. The proposed method solves graph matching problem by casting it into an equivalent weighted maximum clique problem of the corresponding association graph, which we further penalize through introducing negative weights. Subsequent tabu search optimization allows for overcoming the convention of using positive weights. The method's distinct feature is that it utilizes the history of search to make more strategic decisions while looking for the optimal solution, thus effectively escaping local optima and in practice achieving superior results. The proposed method, unlike the existing algorithms, enables direct optimization in the original discrete space while encouraging rather than artificially enforcing hard one-to-one constraint, thus resulting in better solution. The experiments demonstrate the robustness of the algorithm in a variety of settings, presenting the state-of-the-art results. The code is available at http://cv.snu.ac.kr/research/~DTSGM/.

In this paper, we present a new surfel (surface element) based multi-view stereo algorithm that runs entirely on GPU. We utilize the flexibility of surfel-based 3D shape representation and global optimization by graph cuts in the same framework. Unlike previous works, the algorithm is optimized to massive parallel processing on GPU. First, we construct surfel candidates by local stereo matching and voting. After refining the position and orientation of the surfel candidates, we extract the optimal surfels by employing graph cuts under photo-consistency and surfel orientation constraints. In contrast to the conventional voxel based methods, the proposed algorithm utilizes more accurate photo-consistency and reconstructs the 3D shape up to sub-voxel accuracy. The orientation of the constructed surfel candidates imposes an effective constraint that reduces the effect of the minimal surface bias. The entire processing pipeline is implemented on the latest GPU to significantly speed up the processing. The experimental results show that the proposed approach reconstructs the 3D shape of an object accurately and efficiently, which runs more than 100 times faster than on CPU.

In this paper, we propose a novel occlusion invariant face recognition algorithm based on Selective Local Non-negative Matrix Factorization (S-LNMF) technique. The proposed algorithm is composed of two phases; the occlusion detection phase and the selective LNMF-based recognition phase. We use a local approach to effectively detect partial occlusions in an input face image. A face image is first divided into a finite number of disjointed local patches, and then each patch is represented by PCA (Principal Component Analysis), obtained by corresponding occlusion-free patches of training images. And the 1-NN threshold classifier is used for occlusion detection for each patch in the corresponding PCA space. In the recognition phase, by employing the LNMF-based face representation, we exclusively use the LNMF bases of occlusion-free image patches for face recognition. Euclidean nearest neighbor rule is applied for the matching. We have performed experiments on AR face database that includes many occluded face images by sunglasses and scarves. The experimental results demonstrate that the proposed local patch-based occlusion detection technique works well and the S-LNMF method shows superior performance to other conventional approaches.

In this paper we propose an efficient line feature-based 2D object recognition algorithm using a novel entropy correspondence measure (ECM) that encodes the probabilistic similarity between two line feature sets. Since the proposed ECM-based method uses the whole structural information of objects simultaneously for matching, it overcomes the common drawbacks of the conventional techniques that are based on feature to feature correspondence. Moreover, since ECM is endowed with probabilistic attribute, it shows quite robust performance in the noisy environment. In order to enhance the recognition performance and speed, line features are pre-clustered into several groups according to their inclination by an eigen analysis, and then ECM is applied to each corresponding group individually. Experimental results on real images demonstrate that the proposed algorithm has superior performance to those of the conventional algorithms in both the accuracy and the computational efficiency, in the noisy environment.

In this paper, we propose a new stereo matching algorithm using an iterated graph cuts and mean shift filtering technique. Our algorithm estimates the disparity map progressively through the following two steps. In the first step, with a previously estimated RDM (reliable disparity map) that consists of sparse ground control points, an updated dense disparity map is constructed through a RDM constrained energy minimization framework that can cope with occlusion. The graph cuts technique is employed for the solution of the proposed energy model. In the second step, more accurate and denser RDM is estimated through the disparity crosschecking technique and the mean shift filtering in the CSD (color-spatial-disparity) space. The proposed algorithm expands the reliable disparities in RDM repeatedly through the above two steps until it converges. Experimental results on the standard data set demonstrate that the proposed algorithm achieves comparable performance to the state-of-the-arts, and gives excellent results especially in the areas such as the disparity discontinuous boundaries and occluded regions, where the conventional methods usually suffer.

Existing approaches to template-based visual tracking, in which the objective is to continuously estimate the spatial transformation parameters of an object template over video frames, have primarily been based on deterministic optimization, which as is well-known can result in convergence to local optima. To overcome this limitation of the deterministic optimization approach, in this paper we present a novel particle filtering approach to template-based visual tracking. We formulate the problem as a particle filtering problem on matrix Lie groups, specifically the three-dimensional Special Linear group SL(3) and the two-dimensional affine group Aff(2). Computational performance and robustness are enhanced through a number of features: (i) Gaussian importance functions on the groups are iteratively constructed via local linearization; (ii) the inverse formulation of the Jacobian calculation is used; (iii) template resizing is performed; and (iv) parent-child particles are developed and used. Extensive experimental results using challenging video sequences demonstrate the enhanced performance and robustness of our particle filtering-based approach to template-based visual tracking. We also show that our approach outperforms several state-of-the-art template-based visual tracking methods via experiments using the publicly available benchmark data set.

Several state-of-the-art video deblurring methods are based on a strong assumption that the captured scenes are static. These methods fail to deblur blurry videos in dynamic scenes. We propose a video deblurring method to deal with general blurs inherent in dynamic scenes, contrary to other methods. To handle locally varying and general blurs caused by various sources, such as camera shake, moving objects, and depth variation in a scene, we approximate pixel-wise kernel with bidirectional optical flows. Therefore, we propose a single energy model that simultaneously estimates optical flows and latent frames to solve our deblurring problem. We also provide a framework and efficient solvers to optimize the energy model. By minimizing the proposed energy function, we achieve significant improvements in removing blurs and estimating accurate optical flows in blurry frames. Extensive experimental results demonstrate the superiority of the proposed method in real and challenging videos that state-of-the-art methods fail in either deblurring or optical flow estimation., CVPR 2015 oral

Feature correspondence plays a central role in various computer vision applications. It is widely formulated as a graph matching problem due to its robust performance under challenging conditions, such as background clutter, object deformation and repetitive patterns. A variety of fast and accurate algorithms have been proposed for graph matching. However, most of them focus on improving the recall of the solution while rarely considering its precision, thus inducing a solution with numerous outliers. To address both precision and recall feature correspondence should rather be formulated as a subgraph matching problem. This paper proposes a new subgraph matching formulation which uses a compactness prior, an additional constraint that prefers sparser solutions and effectively eliminates outliers. To solve the new optimization problem, we propose a meta-algorithm based on Markov chain Monte Carlo. By constructing Markov chain on the restricted search space instead of the original solution space, our method approximates the solution effectively. The experiments indicate that our proposed formulation and algorithm significantly improve the baseline performance under challenging conditions when both outliers and deformation noise are present.

Graph cuts-based algorithms have achieved great success in energy minimization for many computer vision applications. These algorithms provide approximated solutions for multi-label energy functions via move-making approach. This approach fuses the current solution with a proposal to generate a lower-energy solution. Thus, generating the appropriate proposals is necessary for the success of the move-making approach. However, not much research efforts has been done on the generation of "good" proposals, especially for non-metric energy functions. In this paper, we propose an application-independent and energy-based approach to generate "good" proposals. With these proposals, we present a graph cuts-based move-making algorithm called GA-fusion (fusion with graph approximation-based proposals). Extensive experiments support that our proposal generation is effective across different classes of energy functions. The proposed algorithm outperforms others both on real and synthetic problems., CVPR2015

In this paper, we propose a novel model-based perceptual grouping algorithm for the line features of 3-D polyhedral objects. Given a 3-D polyhedral model, perceptual grouping is performed to extract a set of 3-D line segments which are geometrically consistent with the 3-D model. Unlike the conventional approaches, grouping is done in 3-D space in a model-based framework. In our unique approach, a decision tree classifier is employed for encoding and retrieving the geometric information of the 3-D model. A Gestalt graph is constructed by classifying input instances into proper Gestalt relations using the decision tree. The Gestalt graph is then decomposed into a few subgraphs, yielding appropriate groups of features. As an application, we suggest a 3-D object recognition system which can be accomplished by selecting a best-matched group. In order to evaluate the performance of the proposed algorithm, experiments are carried out on both synthetic and real scenes.

In this paper, we propose a new efficient topology estimation algorithm to construct a multiresolution polygonal mesh from measured three-dimensional (3-D) range data. The topology estimation problem is defined under the constraints of cognition, compactness, and regularity, and the algorithm is designed to be applied to either a cloud of points or a dense mesh. The proposed algorithm initially segments the range data into a finite number of Voronoi patches using the K-means clustering algorithm. Each patch is then approximated by an appropriate polygonal and eventually a triangular mesh model. In order to improve the equiangularity of the mesh, we employ a dynamic mesh model, in which the mesh finds its equilibrium state adaptively, according to the equiangularity constraint. Experimental results demonstrate that satisfactory equiangular triangular mesh models can be constructed rapidly at various resolutions, while yielding tolerable modeling error.

In this paper, we propose a novel 2-D partial matching algorithm using the model-based probabilistic analysis of feature correspondences in the relation vector space, which is quite robust to shape variations due to noise and occlusions and invariant to 2-D geometric transformations as well. We represent an object using the attributed relational graph (ARG) model with nodes (features) of a set of the binary relation vectors. By defining relation vector space which can describe the structural information of an object centered at a specific feature, and modeling distortions due to partial occlusion or the input noise statistically in this space, lost features can be easily identified, so that the partial matching is performed efficiently. The proposed partial matching algorithm consists of two-phases. First, a finite number of candidate subgraphs are selected in an image, by using the logical constraint embedding local and structural consistency as well as the correspondence measure between model and image features. Second, the feature loss detection is done iteratively by the error detection and voting scheme through the error analysis in the relation vector space. Experimental results on real images demonstrate that the proposed algorithm has superior performance to those of the conventional relaxation algorithms, by localizing target objects robustly and correctly even in severely noisy and occluded scenes.

In this paper, we propose a new 3D target recognition algorithm using a single image. Our approach is based on geometrically invariant relationships. By employing a practical CCD camera model for projective image formation, and analyzing the constraints on the projection parameters, we derive two invariant relationships using six pairs of 3D space features and corresponding image features, such as points and lines. Compared to the conventional approach in which only a single invariant relationship is derived from six point pairs based on the general finite projective camera model, the two relationships obtained from the practical camera model can increase the effectiveness of matching. Based on the derived invariant relationships, a new view-invariant object recognition algorithm using a single image is proposed. The performance of the proposed recognition algorithm is demonstrated by various computer simulations on synthetic and real images of objects. The experimental results show that 3D objects in the image can be robustly recognized, using the linear features, by the proposed algorithm.

This paper proposes a robust tracking method that uses interval analysis. Any single posterior model necessarily includes a modeling uncertainty (error), and thus, the posterior should be represented as an interval of probability. Then, the objective of visual tracking becomes to find the best state that maximizes the posterior and minimizes its interval simultaneously. By minimizing the interval of the posterior, our method can reduce the modeling uncertainty in the posterior. In this paper, the aforementioned objective is achieved by using the M4 estimation, which combines the Maximum a Posterior (MAP) estimation with Minimum Mean-Square Error (MMSE), Maximum Likelihood (ML), and Minimum Interval Length (MIL) estimations. In the M4 estimation, our method maximizes the posterior over the state obtained by the MMSE estimation. The method also minimizes interval of the posterior by reducing the gap between the lower and upper bounds of the posterior. The gap is reduced when the likelihood is maximized by the ML estimation and the interval length of the state is minimized by the MIL estimation. The experimental results demonstrate that M4 estimation can be easily integrated into conventional tracking methods and can greatly enhance their tracking accuracy. In several challenging datasets, our method outperforms state-of-the-art tracking methods.

Markov chain Monte Carlo (MCMC) is an elegant tool, widely used in variety of areas. In computer vision, it has been used for the inference on the Markov random field model (MRF). However, MCMC less concerned than other deterministic approaches although it converges to global optimal solution in theory. The major obstacle is its slow convergence. To come up with faster sampling method, we investigate two ideas: breaking detailed balance and updating multiple nodes at a time. Although detailed balance is considered to be essential element of MCMC, it actually is not the necessary condition for the convergence. In addition, exploiting the structure of MRF, we introduce a new kernel which updates multiple nodes in a scanline rather than a single node. Those two ideas are integrated in a novel way to develop an efficient method called scanline sampler without detailed balance. In experimental section, we apply our method to the OpenGM2 benchmark of MRF optimization and show the proposed method achieves faster convergence than the conventional approaches.

Most state-of-the-art dynamic scene deblurring methods based on accurate motion segmentation assume that motion blur is small or that the specific type of motion causing the blur is known. In this paper, we study a motion segmentation-free dynamic scene deblurring method, which is unlike other conventional methods. When the motion can be approximated to linear motion that is locally (pixel-wise) varying, we can handle various types of blur caused by camera shake, including out-of-plane motion, depth variation, radial distortion, and so on. Thus, we propose a new energy model simultaneously estimating motion flow and the latent image based on robust total variation (TV)-L1 model. This approach is necessary to handle abrupt changes in motion without segmentation. Furthermore, we address the problem of the traditional coarse-to-fine deblurring framework, which gives rise to artifacts when restoring small structures with distinct motion. We thus propose a novel kernel re-initialization method which reduces the error of motion flow propagated from a coarser level. Moreover, a highly effective convex optimization-based solution mitigating the computational difficulties of the TV-L1 model is established. Comparative experimental results on challenging real blurry images demonstrate the efficiency of the proposed method.

In this paper, we derive new geometric invariants for structured 3D points and lines from single image under projective transform, and we propose a novel model-based 3D object recognition algorithm using them. Based on the matrix representation of the transformation between space features (points and lines) and the corresponding projected image features, new geometric invariants are derived via the determinant ratio technique. First, an invariant for six points on two adjacent planes is derived, which is shown to be equivalent to Zhu's result [1], but in simpler formulation. Then, two new geometric invariants for structured lines are investigated: one for five lines on two adjacent planes and the other for six lines on four planes. By using the derived invariants, a novel 3D object recognition algorithm is developed, in which a hashing technique with thresholds and multiple invariants for a model are employed to overcome the over-invariant and false alarm problems. Simulation results on real images show that the derived invariants remain stable even in a noisy environment, and the proposed 3D object recognition algorithm is quite robust and accurate.

The aim of motion stereo is to extract the 3-D information of an object from images of a moving camera using the geometric relationships between corresponding points. This paper presents an accurate and robust motion stereo algorithm employing multiple images, taken under a general motion. The object functions for individual stereo pairs are represented, with respect to the distance, then these object functions are integrated considering the position of cameras and the shape of the object functions. By integrating the general motion stereo images, we not only reduce the ambiguities in correspondence, but also improve the precision of the reconstruction. Also by introducing an adaptive window technique, we can alleviate the effect of projective distortion in matching features and improve the accuracy greatly. Experimental results on a synthetic and real data set are presented to demonstrate the performance of the proposed algorithm.

Many state-of-the-art optical flow estimation algorithms optimize the data and regularization terms to solve ill-posed problems. In this paper, in contrast to the conventional optical flow framework that uses a single or fixed data model, we study a novel framework that employs locally varying data term that adaptively combines different multiple types of data models. The locally adaptive data term greatly reduces the matching ambiguity due to the complementary nature of the multiple data models. The optimal number of complementary data models is learnt by minimizing the redundancy among them under the minimum description length constraint (MDL). From these chosen data models, a new optical flow estimation energy model is designed with the weighted sum of the multiple data models, and a convex optimization-based highly effective and practical solution that finds the optical flow, as well as the weights is proposed. Comparative experimental results on the Middlebury optical flow benchmark show that the proposed method using the complementary data models outperforms the state-of-the art methods.

Most conventional single image deblurring methods assume that the underlying scene is static and the blur is caused by only camera shake. In this paper, in contrast to this restrictive assumption, we address the deblurring problem of general dynamic scenes which contain multiple moving objects as well as camera shake. In case of dynamic scenes, moving objects and background have different blur motions, so the segmentation of the motion blur is required for deblurring each distinct blur motion accurately. Thus, we propose a novel energy model designed with the weighted sum of multiple blur data models, which estimates different motion blurs and their associated pixel-wise weights, and resulting sharp image. In this framework, the local weights are determined adaptively and get high values when the corresponding data models have high data fidelity. And, the weight information is used for the segmentation of the motion blur. Non-local regularization of weights are also incorporated to produce more reliable segmentation results. A convex optimization-based method is used for the solution of the proposed energy model. Experimental results demonstrate that our method outperforms conventional approaches in deblurring both dynamic scenes and static scenes.

In this paper, a robust visual tracking method is proposed by casting tracking as an estimation problem of the joint space of non-rigid appearance model and state. Conventional trackers which use templates as the appearance model do not handle ambiguous samples effectively. On the other hand, trackers that use non-rigid appearance models have low discriminative power and lack methods for restoring methods from inaccurately labeled data. To address this problem, multiple non-rigid appearance models are proposed. The probabilities from these models are effectively marginalized by using the particle Markov chain Monte Carlo framework which provides an exact and efficient approximation of the joint density through marginalization and the theoretical evidences of convergence. An appearance model combines multiple classification results with different features and multiple models can infer an accurate solution despite the failure of several models. The proposed method exhibits high accuracy compared with nine other state-of-the-art trackers in various sequences and the result was analyzed both analyzed both qualitatively and quantitatively.

In this paper, we propose a new eigenvector-based line feature matching algorithm, which is invariant to the in-plane rotation, translation, and scale. First, in order to reduce the number of possible matches, we use a preliminary correspondence test that generates a set of finite candidate models, by restricting combinations of line features in the input image. This approach resolves an inherent problem relating to ordering and correspondence in an eigenvector/modal approach. Second, we employ the modal analysis, in which the Gaussian weighted proximity matrices for reference and candidate models are constructed to record the relative distance and angle information between line features for each model. Then, the modes of the proximity matrices of the two models are compared to yield the dissimilarity measure, which describes the quantitative degree of the difference between the two models. Experimental results for synthetic and real images show that the proposed algorithm performs matching of the line features with affine variation fast and efficiently and provides the degree of dissimilarity in a quantitative way.

In this paper, a new recognition algorithm for 2D object contours, based on the decimated wavelet transform, is presented, emphasizing the starting point dependency problem. The proposed matching algorithm consists of two parts: Firstly, we present new data structures for the decimated wavelet representation and a searching algorithm to estimate the misalignment between the starting points for the reference model and unknown object. We also adopt a polynomial approximation technique and propose a fast searching algorithm. And then, matching is performed in an aligned condition on the multiresolutional wavelet representation. By employing a variable-rate decimation scheme, we can achieve fast and accurate recognition results, even in the presence of heavy noise. We provide an analysis on the computational complexity, showing that our approach requires only less than 25% of the computational load required for the conventional method 1]. Various experimental results on both synthetic and real imagery are presented to demonstrate the performance of the proposed algorithm. The simulation results show that the proposed algorithm successfully estimates the misalignment and classifies 2D object contours, even for the input SNR = 5 dB.

Most conventional SFS (shape from shading) algorithms have been developed under three basic assumptions on surface properties and imaging geometry to simplify the problem, namely, a Lambertian surface, a distant point light source and orthographic projection. In this research, we derive a physics-based generalized reflectance map model which includes diffuse and specular reflection effects, a nearby point light source and perspective projection, and then we develop a new direct shape recovery algorithm from shaded images. The basic idea of our solution method is to discretize the image irradiance equation with a finite triangular element surface model, to express the resulting nonlinear system of equations in terms of depth variables only and to recover the object shape by linearizing the nonlinear equations and minimizing a quadratic cost functional. We perform numerical experiments with one or multiple photometric stereo images to demonstrate the performance of the derived physics-based reflectance map model and the proposed SFS algorithm.

We propose a novel tracking algorithm that robustly tracks the target by finding the state which minimizes uncertainty of the likelihood at current state. The uncertainty of the likelihood is estimated by obtaining the gap between the lower and upper bounds of the likelihood. By minimizing the gap between the two bounds, our method finds the confident and reliable state of the target. In the paper, the state that gives the Minimum Uncertainty Gap (MUG) between likelihood bounds is shown to be more reliable than the state which gives the maximum likelihood only, especially when there are severe illumination changes, occlusions, and pose variations. A rigorous derivation of the lower and upper bounds of the likelihood for the visual tracking problem is provided to address this issue. Additionally, an efficient inference algorithm using Interacting Markov Chain Monte Carlo is presented to find the best state that maximizes the average of the lower and upper bounds of the likelihood and minimizes the gap between two bounds simultaneously. Experimental results demonstrate that our method successfully tracks the target in realistic videos and outperforms conventional tracking methods.

We propose a novel nonparametric approach for semantic segmentation using high-order semantic relations. Conventional context models mainly focus on learning pairwise relationships between objects. Pairwise relations, however, are not enough to represent high-level contextual knowledge within images. In this paper, we propose semantic relation transfer, a method to transfer high-order semantic relations of objects from annotated images to unlabeled images analogous to label transfer techniques where label information are transferred. We first define semantic tensors representing high-order relations of objects. Semantic relation transfer problem is then formulated as semi-supervised learning using a quadratic objective function of the semantic tensors. By exploiting low-rank property of the semantic tensors and employing Kronecker sum similarity, an efficient approximation algorithm is developed. Based on the predicted high-order semantic relations, we reason semantic segmentation and evaluate the performance on several challenging datasets.

Based on the traditional problem formulation, it is difficult to integrate the two important vision cues, i.e., shading and stereo, for shape reconstruction due to conflicting albedo and image projection assumptions. In this research, we propose a novel scheme to integrate shading and stereo. First, by using the photometric ratio, we derive a new SFS (shape from shading) formulation where no albedo is needed for shape reconstruction. Then, we establish a unified framework for the integration of photometric ratio and stereo by employing perspective projection on a parametric surface via minimizing a cost functional which consists of a weighted sum of shading and stereo errors. Simulation results are given to show the performance of our new robust algorithm.

International audience; Graph matching is a powerful tool for computer vision and machine learning. In this paper, a novel approach to graph matching is developed based on the sequential Monte Carlo framework. By constructing a sequence of intermediate target distributions, the proposed algorithm sequentially performs a sampling and importance resampling to maximize the graph matching objective. Through the sequential sampling procedure, the algorithm effectively collects potential matches under one-to-one matching constraints to avoid the adverse effect of outliers and deformation. Experimental evaluations on synthetic graphs and real images demonstrate its higher robustness to deformation and outliers.

We propose a novel tracking algorithm based on the Wang-Landau Monte Carlo (WLMC) sampling method for dealing with abrupt motions efficiently. Abrupt motions cause conventional tracking methods to fail because they violate the motion smoothness constraint. To address this problem, we introduce the Wang-Landau sampling method and integrate it into a Markov Chain Monte Carlo (MCMC)-based tracking framework. By employing the novel density-of-states term estimated by the Wang-Landau sampling method into the acceptance ratio of MCMC, our WLMC-based tracking method alleviates the motion smoothness constraint and robustly tracks the abrupt motions. Meanwhile, the marginal likelihood term of the acceptance ratio preserves the accuracy in tracking smooth motions. The method is then extended to obtain good performance in terms of scalability, even on a high-dimensional state space. Hence, it covers drastic changes in not only position but also scale of a target. To achieve this, we modify our method by combining it with the N-fold way algorithm and present the N-Fold Wang-Landau (NFWL)-based tracking method. The N-fold way algorithm helps estimate the density-of-states with a smaller number of samples. Experimental results demonstrate that our approach efficiently samples the states of the target, even in a whole state space, without loss of time, and tracks the target accurately and robustly when position and scale are changing severely.

Recent studies on visual tracking have shown significant improvement in accuracy by handling the appearance variations of the target object. Whereas most studies present schemes to extract the time-invariant characteristics of the target and adaptively update the appearance model, the present paper concentrates on modeling the probabilistic dependency between sequential target appearances (Fig. 1-(a)). To actualize this interest, a new Bayesian tracking framework is formulated under the autoregressive Hidden Markov Model (AR-HMM), where the probabilistic dependency between sequential target appearances is implied. During the learning phase at each time step, the proposed tracker separates formerly seen target samples into several clusters based on their visual similarity, and learns cluster-specific classifiers as multiple appearance models, each of which represents a certain type of the target appearance. Then the dependency between these appearance models is learned. During the searching phase, the target state is estimated by inferring the most probable appearance model under the consideration of its dependency on formerly utilized appearance models. The proposed method is tested on 12 challenging video sequences containing targets with abrupt appearance variations, and demonstrates that it outperforms current state-of-the-art methods in accuracy.

Mode-seeking has been widely used as a powerful data analysis technique for clustering and filtering in a metric feature space. We introduce a versatile and efficient modeseeking method for “graph” representation where general embedding of relational data is possible beyond metric spaces. Exploiting the global structure of the graph by random walks, our method intrinsically combines modeseeking with ranking on the graph, and performs robust analysis by seeking high-ranked authoritative data and suppressing low-ranked noise and outliers. This enables modeseeking to be applied to a large class of challenging real-world problems involving graph representation which frequently arises in computer vision. We demonstrate our method on various synthetic experiments and real applications dealing with noisy and complex data such as scene summarization and object-based image matching.

Graph matching is widely used in a variety of scientific fields, including computer vision, due to its powerful performance, robustness, and generality. Its computational complexity, however, limits the permissible size of input graphs in practice. Therefore, in real-world applications, the initial construction of graphs to match becomes a critical factor for the matching performance, and often leads to unsatisfactory results. In this paper, to resolve the issue, we propose a novel progressive framework which combines probabilistic progression of graphs with matching of graphs. The algorithm efficiently re-estimates in a Bayesian manner the most plausible target graphs based on the current matching result, and guarantees to boost the matching objective at the subsequent graph matching. Experimental evaluation demonstrates that our approach effectively handles the limits of conventional graph matching and achieves significant improvement in challenging image matching problems.

Most conventional SFS (shape from shading) algorithms have been developed under the assumption of orthographic projection. However, the assumption is not valid when an object is not far away from the camera and, therefore, it causes severe reconstruction error in many real applications. In this research, we develop a new iterative algorithm for recovering surface heights from shaded images obtained with perspective projection. By dividing an image into a set of nonoverlapping triangular domains and approximating a smooth surface by the union of triangular surface patches, we can relate image brightness in the image plane directly to surface nodal heights in the world space via a linearized reflectance map based on the perspective projection model. To determine the surface height, we consider the minimization of a cost functional defined to be the sum of squares of the brightness error by solving a system of equations parameterized by nodal heights. Furthermore, we apply a successive linearization scheme in which the linearization of the reflectance map is performed with respect to surface nodal heights obtained from the previous iteration so that the approximation error of the reflectance map is reduced and accuracy of the reconstructed surface is improved iteratively. The proposed method reconstructs surface heights directly and does not require any additional integrability constraint. Simulation results for synthetic and real images are demonstrated to show the performance and efficiency of our new method.

Under the popular Bayesian approach, a stereo problem can be formulated by defining likelihood and prior. Likelihoods are often associated with unary terms and priors are defined by pair-wise or higher order cliques in Markov random field (MRF). In this paper, we propose to use high order likelihood model in stereo. Numerous conventional patch based matching methods such as normalized cross correlation, Laplacian of Gaussian, or census filters are designed under the naive assumption that all the pixels of a patch have the same disparities. However, patch-wise cost can be formulated as higher order cliques for MRF so that the matching cost is a function of image patch's disparities. A patch obtained from the projected image by a disparity map should provide a better match without the blurring effect around disparity discontinuities. Among patch-wise high order matching costs, the census filter approach can be easily reduced to pair-wise cliques. The experimental results on census filter-based high order likelihood demonstrate the advantages of high order likelihood over independent identically distributed unary model.

We propose a novel tracking framework called visual tracker sampler that tracks a target robustly by searching for the appropriate trackers in each frame. Since the real-world tracking environment varies severely over time, the trackers should be adapted or newly constructed depending on the current situation. To do this, our method obtains several samples of not only the states of the target but also the trackers themselves during the sampling process. The trackers are efficiently sampled using the Markov Chain Monte Carlo method from the predefined tracker space by proposing new appearance models, motion models, state representation types, and observation types, which are the basic important components of visual trackers. Then, the sampled trackers run in parallel and interact with each other while covering various target variations efficiently. The experiment demonstrates that our method tracks targets accurately and robustly in the real-world tracking environments and outperforms the state-of-the-art tracking methods.

Establishing correspondences between two feature sets is a fundamental issue in computer vision, pattern recognition, and machine learning. This problem can be well formulated as graph matching in which nodes represent feature points while edges describe pairwise relations between feature points. Recently, several researches have tried to embed higher-order relations of feature points by hyper-graph matching formulations. In this paper, we generalize the previous hyper-graph matching formulations to cover relations of features in arbitrary orders, and propose a novel state-of-the-art algorithm by reinterpreting the random walk concept on the hyper-graph in a probabilistic manner. Adopting personalized jumps with a reweighting scheme, the algorithm effectively reflects the one-to-one matching constraints during the random walk process. Comparative experiments on synthetic data and real images show that the proposed method clearly outperforms existing algorithms especially in the presence of noise and outliers.

Particle Filters are a traditional optimization tool for nonlinear, non-Gaussian dynamic-state estimation such as visual tracking. The particle filters, however, suffer from particle degeneracy problem which is caused by the mismatch between the proposal distribution and the target distribution. In this paper, we propose a method for improving the performance of the particle filter via multiswarm-based Particle Swarm Optimization (PSO). We utilize PSO to obtain samples that are well matched with the likelihood distribution, and its converging property is handled with the exclusion between particles. Additionally, we incorporate multiswarm algorithm in the PSO combined particle filter to deal with ambiguities in estimation task. The resulting filter is applied to the object tracking problem with ambiguous observations, and its performance is tested. We present the experimental results that demonstrate improved accuracy with the same or less computational cost.

Most high dynamic range image (HDRI) algorithms assume stationary scene for registering multiple images which are taken under different exposure settings. In practice, however, there can be some global or local movements between images caused by either camera or object motions. This situation usually causes ghost artifacts which make the same object appear multiple times in the resultant HDRI. To solve this problem, most conventional algorithms conduct ghost detection procedures followed by ghost region filling with the estimated radiance values. However, usually these methods largely depend on the accuracy of the ghost detection results, and thus often suffer from color artifacts around the ghost regions. In this paper, we propose a new robust ghost-free HDRI generation algorithm that does not require accurate ghost detection and not suffer from the color artifact problem. To deal with the ghost problem, our algorithm utilizes the global intensity transfer functions obtained from joint probability density functions (pdfs) between different exposure images. Then, to estimate reliable radiance values, we employ a generalized weighted filtering technique using the global intensity transfer functions. Experimental results show that our method produces the state-of-the-art performance in generating ghost-free HDR images.

The authors propose to combine a triangular element surface model with a linearized reflectance map to formulate the shape-from-shading problem. The main idea is to approximate a smooth surface by the union of triangular surface patches called triangular elements and express the approximating surface as a linear combination of a set of nodal basis functions. Since the surface normal of a triangular element is uniquely determined by the heights of its three vertices (or nodes), image brightness can be directly related to nodal heights using the linearized reflectance map. The surface height can then be determined by minimizing a quadratic cost functional corresponding to the squares of brightness errors and solved effectively with the multigrid computational technique. The proposed method does not require any integrability constraint or artificial assumptions on boundary conditions. Simulation results for synthetic and real images are presented to illustrate the performance and efficiency of the method. >

We propose a novel stochastic graph matching algorithm based on data-driven Markov Chain Monte Carlo (DDMCMC) sampling technique. The algorithm explores the solution space efficiently and avoid local minima by taking advantage of spectral properties of the given graphs in data-driven proposals. Thus, it enables the graph matching to be robust to deformation and outliers arising from the practical correspondence problems. Our comparative experiments using synthetic and real data demonstrate that the algorithm outperforms the state-of-the-art graph matching algorithms.

In this paper, we present a method that recognizes single or multiple common actions between a pair of video sequences. We establish an energy function that evaluates geometric and photometric consistency, and solve the action recognition problem by optimizing the energy function. The proposed stochastic inference algorithm based on the Monte Carlo method explores the video pair from the local spatio-temporal interest point matches to find the common actions. Our algorithm works in unsupervised way without prior knowledge about the type and the number of common actions. Experiments show that our algorithm produces promising results on single and multiple action recognition.

This paper deals with feature matching and segmentation of common objects in a pair of images, simultaneously. For the feature matching problem, the matching likelihoods of all feature correspondences are obtained by combining their discriminative power with the spatial coherence constraint that favors their spatial aggregation via object segmentation. At the same time, for the object segmentation problem, our algorithm estimates the object likelihood that each subregion is a commonly existing part in two images by the affinity propagation of the resulted matching likelihoods. Since these two problems are related to each other, our main idea to solve them is to integrate all the priors about them into a unified framework, that consists of several correlated quadratic cost functions. Eventually, all matching and object likelihoods are estimated simultaneously as a solution of linear system of equations. Based on these likelihoods, we finally recover the optimal feature matches and the common object parts by imposing simple sequential mapping and thresholding techniques, respectively. The experiments demonstrate the superiority of our algorithm compared with the conventional methods.

Many vision applications have been formulated as Markov Random Field (MRF) problems. Although many of them are discrete labeling problems, continuous formulation often achieves great improvement on the qualities of the solutions in some applications such as stereo matching and optical flow. In continuous formulation, however, it is much more difficult to optimize the target functions. In this paper, we propose a new method called fusion move driven Markov Chain Monte Carlo method (MCMC-F) that combines the Markov Chain Monte Carlo method and the fusion move to solve continuous MRF problems effectively. This algorithm exploits powerful fusion move while it fully explore the whole solution space. We evaluate it using the stereo matching problem. We empirically demonstrate that the proposed algorithm is more stable and always finds lower energy states than the state-of-the art optimization techniques.