iccv iccv2013 iccv2013-10 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sadeep Jayasumana, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi
Abstract: We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall’s shape manifold. Different representations of 2D shapes are known to generate different nonlinear spaces. Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. Here, we propose to map shapes on Kendall’s shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. We demonstrate the benefits of our approach over the state-of-the-art methods on shape classification, clustering and retrieval.
Reference: text
sentIndex sentText sentNum sentScore
1 au Abstract We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall’s shape manifold. [sent-4, score-1.07]
2 Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. [sent-6, score-0.67]
3 Here, we propose to map shapes on Kendall’s shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. [sent-7, score-0.86]
4 To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. [sent-8, score-0.889]
5 This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. [sent-9, score-1.088]
6 While a number of methods have been proposed to encode shapes as mathematical objects [28], Kendall’s shape manifold remains the most popular and widely used shape representation. [sent-15, score-0.99]
7 In Kendall’s framework, a 2D shape represented by m landmarks can be treated as a point in the complex projective space CPm−2 [10]. [sent-16, score-0.449]
8 A common approach to cope with the nonlinearity of a manifold consists in approximating the manifold-valued data with its projection to a tangent space at a particular point on the manifold (e. [sent-21, score-0.974]
9 However, while the resulting space is indeed Euclidean, such a tangent space approximation can significantly distort the original manifold-valued data, especially in regions far from the point around which the tangent space was computed. [sent-25, score-0.486]
10 It would therefore seem natural and attractive to extend this approach to manifold-valued data and embed the manifold in a high dimensional Reproducing Kernel Hilbert Space (RKHS), where Euclidean geometry applies. [sent-27, score-0.498]
11 Such a mapping however, requires a kernel function, which, according to Mercer’s theorem, must be positive definite. [sent-28, score-0.513]
12 One could think of replacing the Euclidean distance in the popular Gaussian radial basis function with the metric on the manifold to obtain a kernel function. [sent-29, score-0.849]
13 However, a kernel function derived in this manner is not positive definite in general. [sent-30, score-0.867]
14 In this paper, we introduce the Procrustes Gaussian kernel, a provably positive definite kernel on the shape manifold. [sent-31, score-1.141]
15 Being positive definite, this kernel function allows us to embed the shape manifold in a high dimensional Hilbert space. [sent-32, score-1.242]
16 To the best of our knowledge, this represents the first embedding of the shape manifold in a Hilbert space, thus letting us generalize the use of kernel methods to the shape manifold. [sent-33, score-1.326]
17 The advantage of such an embedding is twofold: First, it enables the use of well established recognition methods that require linear geometry on the nonlinear shape manifold. [sent-34, score-0.405]
18 Second, as evidenced by kernel methods on Rn, embedding a lower dimensional space in a higher dimensional one helps identifying complex patterns in a given data distribution. [sent-35, score-0.663]
19 More specifically, we make use of the full Procrustes disopyright 1249 tance [10, 5] as the distance measure on the shape manifold, and show that it gives rise to a positive definite Gaussian kernel. [sent-36, score-0.792]
20 We exploit this kernel in four different algorithms; support vector machines (SVM), multiple kernel learning (MKL), kernel principal component analysis and kernel kmeans. [sent-37, score-1.609]
21 To demonstrate the benefits of the Hilbert space embedding of shapes obtained with our kernel, we tackle the tasks of shape classification, clustering and retrieval. [sent-38, score-0.515]
22 Our experimental evaluation shows that our manifold-based kernel methods outperform tangent space approaches and other shape analysis baselines on these tasks. [sent-39, score-0.856]
23 Most of these representations yield nonlinear shape spaces where Euclidean geometry does not apply. [sent-43, score-0.431]
24 In this paper, we study the popular and successful shape manifold introduced by Kendall, where a shape is represented by a finite number of landmarks. [sent-44, score-0.874]
25 The lack of Euclidean structure of the shape manifold has made it impossible to utilize well known algorithms, such as SVM, to perform shape recognition while accounting for the manifold structure. [sent-45, score-1.251]
26 Alternatively, recognition has been performed by attempting to model the probability distribution of shape data on the complex unit sphere with a complex Bingham distribution [5, 8], or rotation invariant distributions [8]. [sent-47, score-0.449]
27 Furthermore, our experience with Euclidean spaces strongly suggests that better classifiers can be obtained by exploiting kernel methods. [sent-49, score-0.486]
28 The term kernel is used somewhat loosely in the literature of shape analysis without special attention to positive definiteness. [sent-50, score-0.758]
29 The use of a non-positive definite Chamfer kernel was proposed in [26, 29] in the context of shape detection. [sent-51, score-0.99]
30 In [8], a rotation invariant kernel was introduced and shown to be effective for shape recognition. [sent-52, score-0.733]
31 The notion of invariant kernel functions was also studied in a more general context in [7] and [25]. [sent-53, score-0.438]
32 A number of positive definite kernels, derived from learnt distances, were proposed in [6]. [sent-55, score-0.476]
33 Recently, we introduced positive definite kernels on a different manifold [9]. [sent-59, score-0.933]
34 According to Mercer’s theorem, only positive definite kernels define valid RKHSs. [sent-60, score-0.58]
35 While attempts have been made to exploit non-positive definite kernels [27, 17], many of them have the drawback of altering the eigenvalues of the kernel matrix to artificially make it positive definite [27]. [sent-62, score-1.348]
36 In this paper, we introduce a provably positive definite kernel for the shape manifold. [sent-63, score-1.141]
37 This allows us to exploit existing powerful kernel methods for shape analysis. [sent-64, score-0.682]
38 Since rotations correspond to multiplication by complex numbers of unit magnitude, the shape manifold is infact the complex projective space CPm−2. [sent-72, score-0.763]
39 The geometry of the shape manifold is non-trivial, as a shape is represented by an equivalence class of complex vectors. [sent-73, score-0.933]
40 In particular, the most popular distance on the shape manifold is the full Procrustes distance. [sent-76, score-0.7]
41 A Hilbert Space Embedding of Shapes In this section, we discuss the advantages of embedding the shape manifold in a high-dimensional Hilbert space, and introduce a positive definite kernel on the shape manifold that makes such an embedding possible. [sent-106, score-2.201]
42 In short, points on a manifold M are mapped to elements in a high (possibly i anf minaitnei)f odlidm Mens aiornea ml Hapilpbeedrt t space He,n tthse in Cauchy completion oinfi ttehe) space spanned by tre spaal-cveal Hue,d th feu Cncatuiochnys on M. [sent-111, score-0.469]
43 A kernel function k : (M M) → R is used to odenf Mine . [sent-112, score-0.391]
44 sT mhea tiencghn itic aal R difficulty in utilizing Hilbert space embeddings with manifold-valued data arises from the fact that, according to Mercer’s theorem, the kernel function must be positive definite to define a valid RKHS. [sent-114, score-0.94]
45 While many positive definite kernel func- tions are known for Rn, generalizing them to manifolds is not straightforward. [sent-115, score-0.908]
46 Identifying such positive definite kernel functions on manifolds would, however, be greatly beneficial. [sent-116, score-0.908]
47 Afo Pldositive Definite Kernel on the Shape ManiIn this section, we introduce a kernel function on the shape manifold and prove its positive definiteness. [sent-120, score-1.134]
48 Our kernel is inspired by the Gaussian radial basis function (RBF) that has proven very effective in Euclidean spaces. [sent-121, score-0.419]
49 This yields the kernel kP ([zi] , [zj]) := exp(−d2FP ([zi] , [zj] )/2σ2), that we name Procrustes ]G)a :u=ss eixapn (k−erdnel. [sent-123, score-0.391]
50 While this may seem straightforward, our main contribution comes from the proof that this kernel is positive definite. [sent-124, score-0.544]
51 Let SPm denote the (2m 4) dimensional manifold of 2D shapes dedfiennedot by m l(2anmdm −a 4rk)s d [i5m]. [sent-126, score-0.532]
52 e Wnsieo now present our − ×× main theorem which defines a real-valued positive definite kernel on SPm. [sent-127, score-0.964]
53 The Procrustes Gaussian kernel kP : (SPm SPm) → R : kP([z1], [z2]) := exp(−d2F(PS(P[z1],× ×[z2 S])P/2σ2), where dFP is the full ePxrpoc(r−usdtes distance between two shapes [z1] and [z2], is a positive definite kernel for all σ ∈ R. [sent-130, score-1.445]
54 We start with the definition of positive and negative definite kernels. [sent-134, score-0.508]
55 Although common kernels used in computer vision and machine learning are real-valued, the term positive definite kernels covers the more general case of complex-valued kernels. [sent-135, score-0.684]
56 A kernel f : (X DXe) →ini iCo nis called positive d neofnineimtep if ≥0 Tfohre a klelr n e ∈l f N is,{ caxl1le,d. [sent-140, score-0.513]
57 e following lemma lets us establish the relationship between complex and real valued positive definite kernels. [sent-161, score-0.633]
58 T Lheet Xker bneel a e nxopn(e−mtp fty( sxe1t , axn2d)) f is positive definite for earlnl etl >. [sent-196, score-0.476]
59 This theorem lets us conclude that the positive definiteness of the Gaussian RBF kernel generated by a distance function follows from the negative definiteness of the squared distance function. [sent-202, score-0.911]
60 Note that, in itself, this is an important result since it states the sufficient and necessary conditions to perform kernel methods on any manifold with the Gaussian kernel defined on it. [sent-203, score-1.135]
61 The kernel f : (SPm SPm) f([z1] , [z2] ) := d2FP ([z1] , [z2]) = 1 − | ? [sent-210, score-0.391]
62 It is well-known that the kernel g1 : Cm Cm → C : g1(z1,z2) = ? [sent-214, score-0.391]
63 tw =o positive idsef ailnsiote p koesir-nels is again positive definite (see Theorem 3. [sent-225, score-0.598]
64 12 in [2]), g := g1g2 is also a positive definite kernel. [sent-227, score-0.476]
65 However, it can be shown using counterexamples that none of these yield positive definite Gaussian kernels of all values of σ. [sent-241, score-0.605]
66 In particular, we note that the rotation invariant kernel proposed in [8] uses the partial Procrustes distance and hence is not positive definite. [sent-243, score-0.656]
67 − − − The rotation invariant kernel matrix computed from these pre-shapes and σ = 2 has negative eigenvalues. [sent-269, score-0.52]
68 This proves that the rotation invariant kernel is not a valid Mercer kernel. [sent-270, score-0.488]
69 Kernel Methods on the Shape Manifold The proposed Procrustes Gaussian kernel allows us to exploit algorithms designed for Rn on the shape manifold while accounting for the true geometry of the manifold. [sent-272, score-1.127]
70 ) and HP to denote the Procrustes Gaussian kernel on S(. [sent-277, score-0.391]
71 Kernel Support Vector Machines on SPm We first discuss the use of kernel SVM for binary classification on a manifold. [sent-282, score-0.433]
72 Learning a kernel SVM cons]i ∈sts SinP optimizing ∈th {e− parameters nofa hyperplane in HP so as to separate the positive and negaat hivyep examples w Hith maximum margin. [sent-285, score-0.535]
73 This procedure is equivalent to a standard kernel SVM formulation with a kernel matrix generated from the proposed manifold-aware kernel function. [sent-288, score-1.173]
74 As will be shown in our experiments, utilizing kernel SVM on the manifold yields more accurate results than existing approaches that make use of nearestneighbor methods, kernel SVM in the tangent space, and other more sophisticated methods [8]. [sent-291, score-1.309]
75 Given the kernel kP, each function gj can be }1N, K(pjq) used to compute a kernel matrix K(j) such that = kP (gj (xp) , gj (xq)). [sent-315, score-0.9]
76 With data on the shape manifold, MKL provides us with a powerful tool to combine different shape representations. [sent-325, score-0.513]
77 Kernel PCA on SPm In Euclidean spaces, kernel PCA [20] has proven effective at reducing the dimensionality of the data while accounting for its nonlinearities. [sent-331, score-0.446]
78 This representation, however, was obtained by accounting for the geometry of the manifold via our kernel. [sent-336, score-0.445]
79 It allows us to perform nearest-neighbor search with the Euclidean distance in a low-dimensional Euclidean space instead of having to exploit nonlinear shape distances. [sent-338, score-0.437]
80 As a result, shape retrieval can be made efficient using algorithms such as k-d trees, which cannot be utilized with nonlinear shape distances. [sent-339, score-0.595]
81 Kernel k-means on SPm Finally, we also study the use of kernel k-means on the shape manifold for clustering applications. [sent-342, score-1.028]
82 We follow the standard one-vs-one kernel SVM classification procedure. [sent-360, score-0.433]
83 The optimum value of the kernel bandwidth σ was determined to be 0. [sent-361, score-0.412]
84 Note that our approach outperforms the methods in [1] and tangent space kernel SVM with the usual Gaussian RBF kernel. [sent-377, score-0.661]
85 the Procrustes distance, as well as for tangent space SVM, for which we used the usual Euclidean Gaussian RBF kernel which is known to be positive definite. [sent-378, score-0.783]
86 As before, our kernel SVM on the shape manifold method attains the highest accuracy. [sent-389, score-0.989]
87 A one-vs-all classification procedure was employed with kernel SVM. [sent-399, score-0.457]
88 In Table 3, we compare the results obtained with our shape manifold kernel SVM to Procrustes 1-NN classification, kernel SVM on the tangent space, and the results reported in [1]. [sent-402, score-1.554]
89 While we make use of fewer examples to learn our classifier, our kernel allows us to achieve better accuracy. [sent-406, score-0.414]
90 4 Swedish Leaves We now demonstrate the benefits of our kernel on the problem of leaf identification. [sent-419, score-0.418]
91 We therefore used the shape manifold MKL framework proposed in Section 5. [sent-427, score-0.598]
92 For each object in the dataset, we used 20 images to determine the kernel bandwidth σ and report results on the remaining images. [sent-439, score-0.412]
93 Note that the Manifold KM algorithm is computationally more demanding than our kernel k-means algorithm since it involves repeatedly computing Procrustes distances and Procrustes means. [sent-449, score-0.434]
94 Shape Retrieval Finally, we exploited our kernel for the task of shape retrieval. [sent-452, score-0.636]
95 State-of-the-art shape retrieval methods [13, 1] perform exhaustive nearest neighbor search over the entire database using nonlinear distances between the shapes, which does not scale with the database size. [sent-453, score-0.461]
96 We also evaluated our manifold kernel PCA algorithm against (non-kernel) PCA and kernel PCA on the tangent space, with the ETH dataset in the setting described in Section 6. [sent-465, score-1.309]
97 Conclusion In this paper we have introduced a positive definite kernel on the shape manifold that allows us to embed the manifold in a high-dimensional RKHS. [sent-479, score-1.886]
98 This Procrustes Gaussian kernel has let us extend popular kernel methods in Eu- clidean spaces to the shape manifold while accounting for the geometry of the manifold. [sent-480, score-1.596]
99 This could be attributed to the fact that kernel methods perform recognition in a high-dimensional space while most existing methods resort to simple nearest neighbor search. [sent-483, score-0.505]
100 In the future, we plan to extend the use of our Procrustes Gaussian kernel to other kernel algorithms. [sent-484, score-0.782]
wordName wordTfidf (topN-words)
[('kernel', 0.391), ('definite', 0.354), ('manifold', 0.353), ('procrustes', 0.305), ('shape', 0.245), ('tangent', 0.174), ('hilbert', 0.167), ('mkl', 0.157), ('spm', 0.152), ('euclidean', 0.139), ('positive', 0.122), ('kendall', 0.117), ('shapes', 0.116), ('kp', 0.111), ('kkm', 0.108), ('kernels', 0.104), ('theorem', 0.097), ('swedish', 0.096), ('landmarks', 0.094), ('zi', 0.089), ('svm', 0.075), ('spaces', 0.07), ('embedding', 0.069), ('km', 0.069), ('cicjf', 0.065), ('dimensional', 0.063), ('mercer', 0.061), ('hp', 0.059), ('gj', 0.059), ('definiteness', 0.058), ('nonempty', 0.058), ('rbf', 0.056), ('accounting', 0.055), ('nonlinear', 0.054), ('leaves', 0.052), ('fish', 0.051), ('retrieval', 0.051), ('rotation', 0.05), ('usual', 0.05), ('pca', 0.048), ('invariant', 0.047), ('space', 0.046), ('distance', 0.046), ('embed', 0.045), ('dfp', 0.043), ('squid', 0.043), ('distances', 0.043), ('classification', 0.042), ('gaussian', 0.042), ('manifolds', 0.041), ('lemma', 0.04), ('clustering', 0.039), ('bingham', 0.038), ('bull', 0.038), ('cpm', 0.038), ('master', 0.038), ('lets', 0.038), ('geometry', 0.037), ('nearest', 0.037), ('acknowledged', 0.036), ('karcher', 0.036), ('projective', 0.033), ('negative', 0.032), ('canberra', 0.032), ('latecki', 0.032), ('cm', 0.032), ('complex', 0.031), ('proof', 0.031), ('neighbor', 0.031), ('rkhs', 0.031), ('popular', 0.031), ('provably', 0.029), ('radial', 0.028), ('accuracies', 0.028), ('landmark', 0.027), ('leaf', 0.027), ('embeddings', 0.027), ('nonlinearity', 0.027), ('classes', 0.026), ('full', 0.025), ('classifiers', 0.025), ('yield', 0.025), ('reproducing', 0.025), ('valued', 0.025), ('employed', 0.024), ('mapped', 0.024), ('unit', 0.024), ('prove', 0.023), ('exploit', 0.023), ('zj', 0.023), ('us', 0.023), ('hyperplane', 0.022), ('machines', 0.022), ('equivalence', 0.022), ('bandwidth', 0.021), ('sphere', 0.021), ('riemannian', 0.021), ('projection', 0.021), ('arc', 0.02), ('yi', 0.02)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000002 10 iccv-2013-A Framework for Shape Analysis via Hilbert Space Embedding
Author: Sadeep Jayasumana, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi
Abstract: We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall’s shape manifold. Different representations of 2D shapes are known to generate different nonlinear spaces. Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. Here, we propose to map shapes on Kendall’s shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. We demonstrate the benefits of our approach over the state-of-the-art methods on shape classification, clustering and retrieval.
2 0.21867026 295 iccv-2013-On One-Shot Similarity Kernels: Explicit Feature Maps and Properties
Author: Stefanos Zafeiriou, Irene Kotsia
Abstract: Kernels have been a common tool of machine learning and computer vision applications for modeling nonlinearities and/or the design of robust1 similarity measures between objects. Arguably, the class of positive semidefinite (psd) kernels, widely known as Mercer’s Kernels, constitutes one of the most well-studied cases. For every psd kernel there exists an associated feature map to an arbitrary dimensional Hilbert space H, the so-called feature space. Tdihme mnsaiionn reason ebreth sipnadc ep s Hd ,ke threne slos’-c c aplolpedul aferiattyu rise the fact that classification/regression techniques (such as Support Vector Machines (SVMs)) and component analysis algorithms (such as Kernel Principal Component Analysis (KPCA)) can be devised in H, without an explicit defisnisiti (oKnP of t)h)e c feature map, only by using athne xkperlniceitl (dtehfeso-called kernel trick). Recently, due to the development of very efficient solutions for large scale linear SVMs and for incremental linear component analysis, the research to- wards finding feature map approximations for classes of kernels has attracted significant interest. In this paper, we attempt the derivation of explicit feature maps of a recently proposed class of kernels, the so-called one-shot similarity kernels. We show that for this class of kernels either there exists an explicit representation in feature space or the kernel can be expressed in such a form that allows for exact incremental learning. We theoretically explore the properties of these kernels and show how these kernels can be used for the development of robust visual tracking, recognition and deformable fitting algorithms. 1Robustness may refer to either the presence of outliers and noise the robustness to a class of transformations (e.g., translation). or to ∗ Irene Kotsia ,†,? ∗Electronics Laboratory, Department of Physics, University of Patras, Greece ?School of Science and Technology, Middlesex University, London i .kot s i @mdx . ac .uk a
3 0.20084615 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
Author: Hongteng Xu, Hongyuan Zha
Abstract: Data sparsity has been a thorny issuefor manifold-based image synthesis, and in this paper we address this critical problem by leveraging ideas from transfer learning. Specifically, we propose methods based on generating auxiliary data in the form of synthetic samples using transformations of the original sparse samples. To incorporate the auxiliary data, we propose a weighted data synthesis method, which adaptively selects from the generated samples for inclusion during the manifold learning process via a weighted iterative algorithm. To demonstrate the feasibility of the proposed method, we apply it to the problem of face image synthesis from sparse samples. Compared with existing methods, the proposed method shows encouraging results with good performance improvements.
4 0.1705551 81 iccv-2013-Combining the Right Features for Complex Event Recognition
Author: Kevin Tang, Bangpeng Yao, Li Fei-Fei, Daphne Koller
Abstract: In this paper, we tackle the problem of combining features extracted from video for complex event recognition. Feature combination is an especially relevant task in video data, as there are many features we can extract, ranging from image features computed from individual frames to video features that take temporal information into account. To combine features effectively, we propose a method that is able to be selective of different subsets of features, as some features or feature combinations may be uninformative for certain classes. We introduce a hierarchical method for combining features based on the AND/OR graph structure, where nodes in the graph represent combinations of different sets of features. Our method automatically learns the structure of the AND/OR graph using score-based structure learning, and we introduce an inference procedure that is able to efficiently compute structure scores. We present promising results and analysis on the difficult and large-scale 2011 TRECVID Multimedia Event Detection dataset [17].
5 0.15735763 435 iccv-2013-Unsupervised Domain Adaptation by Domain Invariant Projection
Author: Mahsa Baktashmotlagh, Mehrtash T. Harandi, Brian C. Lovell, Mathieu Salzmann
Abstract: Domain-invariant representations are key to addressing the domain shift problem where the training and test examples follow different distributions. Existing techniques that have attempted to match the distributions of the source and target domains typically compare these distributions in the original feature space. This space, however, may not be directly suitable for such a comparison, since some of the features may have been distorted by the domain shift, or may be domain specific. In this paper, we introduce a Domain Invariant Projection approach: An unsupervised domain adaptation method that overcomes this issue by extracting the information that is invariant across the source and target domains. More specifically, we learn a projection of the data to a low-dimensional latent space where the distance between the empirical distributions of the source and target examples is minimized. We demonstrate the effectiveness of our approach on the task of visual object recognition and show that it outperforms state-of-the-art methods on a standard domain adaptation benchmark dataset.
6 0.15705416 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
7 0.13686912 293 iccv-2013-Nonparametric Blind Super-resolution
8 0.13260859 70 iccv-2013-Cascaded Shape Space Pruning for Robust Facial Landmark Detection
10 0.12338392 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
11 0.12215926 297 iccv-2013-Online Motion Segmentation Using Dynamic Label Propagation
12 0.12017893 116 iccv-2013-Directed Acyclic Graph Kernels for Action Recognition
13 0.1167491 48 iccv-2013-An Adaptive Descriptor Design for Object Recognition in the Wild
14 0.11584765 307 iccv-2013-Parallel Transport of Deformations in Shape Space of Elastic Surfaces
15 0.11533463 100 iccv-2013-Curvature-Aware Regularization on Riemannian Submanifolds
16 0.10690516 437 iccv-2013-Unsupervised Random Forest Manifold Alignment for Lipreading
17 0.10650744 257 iccv-2013-Log-Euclidean Kernels for Sparse Representation and Dictionary Learning
18 0.10526152 35 iccv-2013-Accurate Blur Models vs. Image Priors in Single Image Super-resolution
19 0.10201098 321 iccv-2013-Pose-Free Facial Landmark Fitting via Optimized Part Mixtures and Cascaded Deformable Shape Model
topicId topicWeight
[(0, 0.182), (1, 0.019), (2, -0.064), (3, -0.055), (4, -0.059), (5, 0.071), (6, 0.07), (7, 0.021), (8, 0.03), (9, -0.109), (10, -0.051), (11, -0.114), (12, -0.026), (13, -0.092), (14, 0.042), (15, 0.021), (16, 0.068), (17, -0.032), (18, -0.003), (19, -0.167), (20, 0.066), (21, 0.079), (22, 0.133), (23, 0.14), (24, -0.018), (25, 0.106), (26, 0.01), (27, 0.085), (28, -0.041), (29, 0.075), (30, -0.08), (31, 0.013), (32, -0.191), (33, -0.072), (34, 0.119), (35, 0.167), (36, 0.053), (37, -0.032), (38, -0.062), (39, -0.097), (40, -0.064), (41, -0.074), (42, 0.015), (43, -0.053), (44, 0.024), (45, 0.021), (46, 0.084), (47, -0.065), (48, -0.1), (49, -0.12)]
simIndex simValue paperId paperTitle
same-paper 1 0.97718841 10 iccv-2013-A Framework for Shape Analysis via Hilbert Space Embedding
Author: Sadeep Jayasumana, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi
Abstract: We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall’s shape manifold. Different representations of 2D shapes are known to generate different nonlinear spaces. Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. Here, we propose to map shapes on Kendall’s shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. We demonstrate the benefits of our approach over the state-of-the-art methods on shape classification, clustering and retrieval.
2 0.7055741 295 iccv-2013-On One-Shot Similarity Kernels: Explicit Feature Maps and Properties
Author: Stefanos Zafeiriou, Irene Kotsia
Abstract: Kernels have been a common tool of machine learning and computer vision applications for modeling nonlinearities and/or the design of robust1 similarity measures between objects. Arguably, the class of positive semidefinite (psd) kernels, widely known as Mercer’s Kernels, constitutes one of the most well-studied cases. For every psd kernel there exists an associated feature map to an arbitrary dimensional Hilbert space H, the so-called feature space. Tdihme mnsaiionn reason ebreth sipnadc ep s Hd ,ke threne slos’-c c aplolpedul aferiattyu rise the fact that classification/regression techniques (such as Support Vector Machines (SVMs)) and component analysis algorithms (such as Kernel Principal Component Analysis (KPCA)) can be devised in H, without an explicit defisnisiti (oKnP of t)h)e c feature map, only by using athne xkperlniceitl (dtehfeso-called kernel trick). Recently, due to the development of very efficient solutions for large scale linear SVMs and for incremental linear component analysis, the research to- wards finding feature map approximations for classes of kernels has attracted significant interest. In this paper, we attempt the derivation of explicit feature maps of a recently proposed class of kernels, the so-called one-shot similarity kernels. We show that for this class of kernels either there exists an explicit representation in feature space or the kernel can be expressed in such a form that allows for exact incremental learning. We theoretically explore the properties of these kernels and show how these kernels can be used for the development of robust visual tracking, recognition and deformable fitting algorithms. 1Robustness may refer to either the presence of outliers and noise the robustness to a class of transformations (e.g., translation). or to ∗ Irene Kotsia ,†,? ∗Electronics Laboratory, Department of Physics, University of Patras, Greece ?School of Science and Technology, Middlesex University, London i .kot s i @mdx . ac .uk a
3 0.66728199 259 iccv-2013-Manifold Based Face Synthesis from Sparse Samples
Author: Hongteng Xu, Hongyuan Zha
Abstract: Data sparsity has been a thorny issuefor manifold-based image synthesis, and in this paper we address this critical problem by leveraging ideas from transfer learning. Specifically, we propose methods based on generating auxiliary data in the form of synthetic samples using transformations of the original sparse samples. To incorporate the auxiliary data, we propose a weighted data synthesis method, which adaptively selects from the generated samples for inclusion during the manifold learning process via a weighted iterative algorithm. To demonstrate the feasibility of the proposed method, we apply it to the problem of face image synthesis from sparse samples. Compared with existing methods, the proposed method shows encouraging results with good performance improvements.
4 0.62202907 227 iccv-2013-Large-Scale Image Annotation by Efficient and Robust Kernel Metric Learning
Author: Zheyun Feng, Rong Jin, Anil Jain
Abstract: One of the key challenges in search-based image annotation models is to define an appropriate similarity measure between images. Many kernel distance metric learning (KML) algorithms have been developed in order to capture the nonlinear relationships between visual features and semantics ofthe images. Onefundamental limitation in applying KML to image annotation is that it requires converting image annotations into binary constraints, leading to a significant information loss. In addition, most KML algorithms suffer from high computational cost due to the requirement that the learned matrix has to be positive semi-definitive (PSD). In this paper, we propose a robust kernel metric learning (RKML) algorithm based on the regression technique that is able to directly utilize image annotations. The proposed method is also computationally more efficient because PSD property is automatically ensured by regression. We provide the theoretical guarantee for the proposed algorithm, and verify its efficiency and effectiveness for image annotation by comparing it to state-of-the-art approaches for both distance metric learning and image annotation. ,
5 0.61078572 307 iccv-2013-Parallel Transport of Deformations in Shape Space of Elastic Surfaces
Author: Qian Xie, Sebastian Kurtek, Huiling Le, Anuj Srivastava
Abstract: Statistical shape analysis develops methods for comparisons, deformations, summarizations, and modeling of shapes in given data sets. These tasks require afundamental tool called parallel transport of tangent vectors along arbitrary paths. This tool is essential for: (1) computation of geodesic paths using either shooting or path-straightening method, (2) transferring deformations across objects, and (3) modeling of statistical variability in shapes. Using the square-root normal field (SRNF) representation of parameterized surfaces, we present a method for transporting deformations along paths in the shape space. This is difficult despite the underlying space being a vector space because the chosen (elastic) Riemannian metric is non-standard. Using a finite-basis for representing SRNFs of shapes, we derive expressions for Christoffel symbols that enable parallel transports. We demonstrate this framework using examples from shape analysis of parameterized spherical sur- faces, in the three contexts mentioned above.
6 0.60369915 257 iccv-2013-Log-Euclidean Kernels for Sparse Representation and Dictionary Learning
7 0.56592309 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
8 0.55843437 48 iccv-2013-An Adaptive Descriptor Design for Object Recognition in the Wild
9 0.55573481 347 iccv-2013-Recursive Estimation of the Stein Center of SPD Matrices and Its Applications
10 0.53580624 117 iccv-2013-Discovering Details and Scene Structure with Hierarchical Iconoid Shift
11 0.53177017 293 iccv-2013-Nonparametric Blind Super-resolution
13 0.51183009 114 iccv-2013-Dictionary Learning and Sparse Coding on Grassmann Manifolds: An Extrinsic Solution
14 0.50281197 178 iccv-2013-From Semi-supervised to Transfer Counting of Crowds
15 0.48960653 177 iccv-2013-From Point to Set: Extend the Learning of Distance Metrics
16 0.46930501 368 iccv-2013-SYM-FISH: A Symmetry-Aware Flip Invariant Sketch Histogram Shape Descriptor
17 0.4678905 21 iccv-2013-A Method of Perceptual-Based Shape Decomposition
18 0.45031917 134 iccv-2013-Efficient Higher-Order Clustering on the Grassmann Manifold
19 0.44965538 77 iccv-2013-Codemaps - Segment, Classify and Search Objects Locally
topicId topicWeight
[(2, 0.076), (7, 0.029), (12, 0.011), (26, 0.067), (31, 0.041), (38, 0.208), (42, 0.151), (48, 0.011), (64, 0.031), (73, 0.013), (78, 0.012), (89, 0.205), (98, 0.041)]
simIndex simValue paperId paperTitle
1 0.92264044 84 iccv-2013-Complex 3D General Object Reconstruction from Line Drawings
Author: Linjie Yang, Jianzhuang Liu, Xiaoou Tang
Abstract: An important topic in computer vision is 3D object reconstruction from line drawings. Previous algorithms either deal with simple general objects or are limited to only manifolds (a subset of solids). In this paper, we propose a novel approach to 3D reconstruction of complex general objects, including manifolds, non-manifold solids, and non-solids. Through developing some 3D object properties, we use the degree of freedom of objects to decompose a complex line drawing into multiple simpler line drawings that represent meaningful building blocks of a complex object. After 3D objects are reconstructed from the decomposed line drawings, they are merged to form a complex object from their touching faces, edges, and vertices. Our experiments show a number of reconstruction examples from both complex line drawings and images with line drawings superimposed. Comparisons are also given to indicate that our algorithm can deal with much more complex line drawings of general objects than previous algorithms. 1. Introduction and Related Work A 2D line drawing is the most straightforward way of illustrating a 3D object. Given a line drawing representing a 3D object, our visual system can understand the 3D structure easily. For example, we can interpret without difficulty the line drawing shown in Fig. 1(a) as a castle with four walls and one door. Imitating this ability has been a longstanding and challenging topic in computer vision when a line drawing is as complex as this example. The applications of this work include 3D object design in CAD and for 3D printers, 3D query generation for 3D object retrieval, and 3D modeling from images. In this paper, same as the majority of related work, a line drawing is defined as the orthogonal projection of the Fig.1 (a)Alinedrawing(rae)pres nti gac stle.(b)The3Dm(obd)el of the line drawing. edges and vertices of a 3D object in a generic view, and objects with planar surfaces are considered. A line drawing is represented by an edge-vertex graph. It can be obtained by the user/designer who draws on the screen with a tablet pen, a mouse, or a finger (on a touch sensitive screen), with all, with some, or without hidden edges and vertices. Line labeling is the earliest work to interpret line drawings [1], [17]. It searches for a set of consistent labels such as convex, concave, and occluding from a line drawing to test its correctness and/or realizability. Line labeling itself cannot recover 3D shape from a line drawing. Later, 3D reconstruction from the contours (line drawings) of objects in images is studied [19], [14], [13], which handles simple objects only. Model-based 3D reconstruction [2], [3], [20] can deal with more complex objects, but these methods require to pre-define a set of parametric models. Recently, popular methods of 3D reconstruction from line drawings are optimization based, which are most related to our work and are reviewed next. These methods can be classified into two categories: one dealing with manifolds and the other dealing with general objects. A general object can be a manifold, non-manifold solid, or non-solid. Manifolds are a subset of solids, defined as follows: A manifold, or more rigorously 2D manifold, is a solid where every point on its surface has a neighborhood topologically equivalent to an open diskin the 2D Euclidean space. 1433 In this paper, a solid is a portion of 3D space bounded by planar faces, and a manifold is also bounded by planar faces. Each edge of such manifolds is shared exactly by two faces [4]. Most 3D reconstruction methods from a line drawing assume that the face topology of the line drawing is known in advance. This information can reduce the reconstruction complexity greatly. Algorithms have been developed to find faces from a line drawing in [16], [10], and [9], where [16] and [10] are for general objects and [9] for manifolds. Optimization-based 3D reconstruction depends on some critera (also called image regularities) that simulate our visual perception. Marill proposes a very simple but effective criterion to reconstruct a simple object: minimizing the standard deviation of the angles (MSDA) in the object [11]. Later, other regularities are proposed to deal with more complex objects such as face planarity, line parallelism, isometry, and corner orthogonality [5], [6], [15], [18]. In these methods, an objective function ?C Φ(z1,z2, ...,zNv) = ?ωiφi(z1,z2, ...,zNv) (1) i?= ?1 is minimized to derive the depths z1, z2 , ..., zNv , where Nv is the number of vertices in the line drawing, φi , i = 1, 2, ..., C, are the regularities, and ωi , i = 1, 2, ..., C, are the weights. The main problem in this approach is that these algorithms are easy to get trapped into local minima (obtaining failed results) when a line drawing is complex with many vertices, due to the search in a highdimensional space (Nv dimensions) with the non-convex objective function. For example, the search space is of 56 dimensions for the object in Fig. 1(a). To alleviate this problem, Liu et al. formulate 3D reconstruction in a lower dimensional space so that the optimization procedure has a better chance to find desired results [7]. For the complex object in Fig. 1(a), however, the search in a space with 18 dimensions is still too difficult for it to obtain a satisfactory 3D object (see Section 3). The methods in [5], [6], [15], [18], and [7] reconstruct general objects, and the one in [7] can deal with more complex objects than the other four. But these algorithms cannot avoid the local minimum problem in a high dimensional search space when a line drawing is complex. In [8], a divide-and-conquer (D&C;) strategy is used to tackle this problem. It first separates a complex line drawing into multiple simpler ones, then independently recovers the 3D objects from these line drawings, and finally merges them to form a complete object. Since the separated line drawings are much simpler than the original one, the 3D reconstruction from each of them is an easy task. This D&C; approach handles manifolds only. Based on known faces found by the face identification algorithm in [9], it uses manifold properties to find internal faces Fig.2(a)Asimaeplhdmiafnbo(ldagc)withnae'fahdc'eisfba'nd(obgcn)'eitrnalfce (a, b, c, d). (b) Decomposition result from the internal face. (a) (b) (c) (d) Fig. 3. (a) A non-manifold solid. (b) Expected decomposition of (a). (c) A sheet object. (d) Expected decomposition of (c). from a line drawing and then separates the line drawing from the internal faces. An internal face is defined as an imaginary face lying inside a manifold with only its edges visible on the surface [8]. It is not a real face but can be considered as two coincident real faces of identical shape belonging to two manifolds. For example, Fig. 2(a) shows a manifold with nine faces. The D&C; first finds the internal face (a, b, c, d) and then decomposes the line drawing from this internal face (Fig. 2(b)). However, handling manifolds only limits the applica- tions of [8]. In many applications in computer vision and graphics such as 3D object matching, retrieval, and rendering, it is unnecessary to represent objects as manifolds, in order to facilitate data processing and reduce data storage. For example, a flat ground can be represented by a sheet (one face), but if it is represented by a manifold, a thin box with six faces has to be used. Fig. 1(a), Fig. 3(a), and Fig. 3(c) are line drawings of three non-manifolds. In this paper, we propose a novel approach to 3D reconstruction of complex general objects based on visual perception, object properties, and new line drawing decomposition. Compared with previous methods, ours can deal with much more complex line drawings of general objects. It can handle not only manifolds but also non-manifold solids and non-solids, and is insensitive to sketching errors. 2. General Object Reconstruction We also use the D&C; strategy to deal with 3D reconstruction from a line drawing representing a complex general object. The key is how to decompose a complex line drawing of any objects into multiple simpler line drawings. These decomposed line drawings should represent objects that are in accordance with our visual perception, which makes the 3D reconstruction from these line drawings easier and better because the regularities used to build an objective function for reconstruction follow human perception of 1434 common objects [11], [5], [6], [15], [18]. Before the decomposition of a line drawing, we assume that all the real and internal faces of the object have been obtained from the line drawing using a face identification algorithm. For example, the algorithm in [10] finds 10 faces from the line drawing in Fig. 2(a) (including the internal face), and obtains 12 and 7 faces from the line drawings in Figs. 3(a) and (c), respectively. 2.1. Decomposing line drawings of solids In this subsection, we consider the line drawings of solids first. The decomposition method will be extended to the line drawings of general objects in the next subsection. It is not difficult to see that in general, a complex object, especially a manmade complex object, can be considered as the combinations of multiple smaller objects. The most common combination is the touch of two faces from two different objects such as the one in Fig. 2. Other combinations are the touches among lines, faces, and vertices. Our target is to decompose a complex solid into multiple primitive solids. Before the definition of a primitive solid, we introduce a term called the degree of freedom of a solid. Definition 1. The degree of freedom (DoF) of a 3D solid represented by a line drawing is the minimal number of zcoordinates that can uniquely determine this 3D solid. This is the first time that the concept of DoF is used to decompose line drawings. Now let us consider a simple object in Fig. 4(a). The cube has six faces: (v1, v2 , v3 , v4), (v1, v2, v6, v5), (v1, v4, v8, v5), (v2 , v3, v7, v6), (v4, v3, v7, v8), and (v6, v7, v8, v5). We can show that the cube is determined if the z-coordinates of its four non-coplanar vertices are known. Without loss of generality, suppose z1, z2, z4, and z5 are known. Since the 3D coordinates of v1, v2, and v4 are fixed (remind that the x- and y-coordinates of all the vertices are known under the orthogonal projection), the 3D plane passing through the face (v1, v2 , v3, v4) is determined, and thus z3 can be calculated. Similarly, z6 and z8 can be obtained. Finally, z7 can be computed with the 3D coordinates of v3, v4, and v8 known, which determine the plane passing through the face (v4, v3, v7, v8). So the 3D cube can be determined by the known four z-coordinates, z1, z2, z4, and z5. Further, it can be verified that three 3D vertices cannot determine this object uniquely because they can only define one face in 3D space. Therefore, the DoF of the cube is 4. Similar analysis allows us to know that the solids in Fig. 2(b), Fig. 3(b), and Fig. 4(b) all have DoF 4, while the two solids in Fig. 2(a) and Fig. 3(a) have DoFs 5 and 6, respectively. From these analysis, we can have the intuition that solids with DoF 4 serve as the building blocks of more complex solids whose DoFs are more than 4. Besides, we have the following property: Property 1. There is no solid with DoF less than 4. Fv5(1iga).4v (26a)Av48cubev3w7hos(be)DoFis4.(b)Anedo(tch)fergBasbolifdAwhosfCeDocFji is also 4. (c) Part of a line drawing with each vertex of degree 3. This property is easy to verify. A solid with fewest faces is a tetrahedron. Every two of its four faces are not co-planar. Three 3D vertices of a tetrahedron can only determine one 3D face. Next, we define primitive solids. Definition 2. A 3D solid represented by a line drawing is called a primitive solid if its DoF is 4. Property 2. If every vertex of a 3D solid represented by a line drawing has degree 31, then it is a primitive solid. Proof. Let part of such a line drawing be the one as shown in Fig. 4(c). At each vertex, every two of the three edges form a face, because a solid is bounded by faces without dangling faces and edges. Let the three paths fA, fB, and fC in Fig. 4(c) denote the three faces at vertex a. Without loss of generality, suppose that the four zcoordinates (and thus the four 3D coordinates) of vertices a, b, c, and d are known. Then the three planes passing through fA, fB, and fC are determined in 3D space. With the two known 3D planes passing through fA and fB at vertex b, the 3D coordinates of vertices g and h connected to b can be computed. Similarly, the 3D coordinates of vertices e and f connected to d and the 3D coordinates of vertices i and j connected to c can be obtained. Furthermore, all the 3D coordinates of the other vertices connected to e, f, g, h, i, and j can be derived in the same way. This derivation can propagate to all the vertices of this solid. Therefore, the DoF of this solid is 4 and it is a primitive solid. Property 3. The DoF of a solid is 5 which is obtained by gluing two faces of two primitive solids. Proof. Let the two primitive solids be PS1 and PS2 and their corresponding gluing faces be f1and f2, respectively. The DoFs of PS1 and PS2 are both 4. Suppose that PS1 is determined in 3D space, which requires four z-coordinates. Then f1and f2 are also determined in 3D space. When the z-coordinates of three vertices on PS2 are known based on f2, one more z-coordinate of a vertex not coplanar with f2 on PS2 can determine PS2 in 3D space. Therefore, the DoF of the combined solid is 5. Fig. 2 is a typical example of two primitive solids gluing together along faces. Fig. 3(a) is an example of two primitive solids gluing together along edges. Two primitive solids may also connect at one vertex. The following property is easy to verify. 1The degree of a vertex is the number of edges connected to this vertex. 1435 Property 4. The DoF of a solid is 6 which is obtained by gluing two edges of two primitive solids. The DoF of a solid is 7 which is obtained by gluing two vertices oftwoprimitive solids. From the above properties, we can see that primitive solids are indeed the “smallest” solids in terms of DoF and they can serve as the building blocks to construct more complex solids. Therefore, our next target is to decompose a line drawing representing a complex solid into multiple line drawings representing primitive solids. Before giving Definition 3, we define some terms first. Vertex set of a face. The vertex set V er(f) of a face f is the set of all the vertices of f. Fixed vertex. A fixed vertex is one with its z-coordinate (thus its 3D coordinate) known. Unfixed vertex. An unfixed vertex is one with its zcoordinate unknown. Fixed face. A fixed face is one with its 3D position determined by its three fixed vertices. Unfixed face. An unfixed face is one with its 3D position undetermined. Definition 3. Let the vertex set and the face set of a line drawing be V = {v1, v2 , ..., vn} and F = {f1, f2 , ..., fm}, respectively, w =he {rve n and m are Fthe = n{fumbers of th}e, vertices and the faces, respectively. Also let Vfixed, Ffixed, Vunfixed, and Funfixed be the sets of fixed vertices, fixed faces, unfixed vertices, and unfixed faces, respectively. Suppose that an initial set of two fixed neighboring faces sharing an edge is Finitial with all their fixed vertices in Vinitial. The final Ffixed in Algorithm 1 is called the maximum extended face set (MEFS) from Finitial. In Algorithm 1, a face f that satisfies the condition in step 3 is a face that has been determined in 3D space by the current fixed vertices in Ffixed. When this face is found, it becomes a fixed face and all its vertices become fixed vertices. The DoF of the initial two fixed faces combined is 4. It is not difficult to see that the algorithm does not increase the initial DoF, and thus the final object represented by the MEFS also has DoF 4. Next, let us consider a simple example shown in Fig. 2(a) with the following three cases: Case 1. Suppose that Finitial = {(e, f,g, h) , (e, f,b, a)}, Vinitial = {e, f,g, h, b, a}, and th{e( algorithm a(de,dfs tbh,ea f}a,c Ves into Ffixed ,ing thh,isb aor}d,e ar:n (f th,e g, c, obr)i →m (a, b, c, d) → (e, h, d, a) →i ( tgh, hs, odr, dce)r. T (fhe,gn tch,eb )fin →al object ,fod)und → by t,hhe, algorithm (isg thh,ed c,uc)b.e. Note that the algorithm does not add any triangular faces into Ffixed because they do not satisfy the condition in step 3. Case 2. If Finitial = {(b, i,a) , (b, i,c)}, then the final object found is the pyramid, abn,id, tah)e, algorithm hdoenes t nhoet f iandadl any rectangular faces except (a, b, c, d) into Ffixed. Case 3. If Finitial = {(b, a, i) , (e, f,b, a)}, the algorithm cannot find any othe=r f a{(cebs,a at,oi a)d,(de ,tof Ffixed. tThheus al, gito rfaitihlsto find the cube or pyramid. Algorithm 1 Face extending procedure Initialization: F, F, Initialization: Funfixed = F \ Finitial , Ffixed = Finitial , Vfixed = Vinitial, Vunfixed = FV \ \ FVinitial. 1. do the following steps until no face satisfies the condition in step 3; 2. Find a face f ∈ Funfixed that satisfies 3. the number ofnon-collinear vertices in V er(f) ∩Vfixed is more than 2; 4. Add face f into Ffixed and delete it from Funfixed; 5. For each vertex v ∈ V er(f), if v ∈ Vunfixed, add v into Vfixed and delete it from Vunfixed; Return The final Ffixed. Fig.5(a)Ac(oam)plexinedrawingofn (-bm)anifolds id.(b)The decomposition result by our algorithm. In case 3, the object represented by the MEFS has only two initial faces and this object is discarded. In order not to miss a primitive solid, we run Algorithm 1 multiple times each with a different pair of neighboring faces in Finitial. Then, we can always have Finitial with its two faces from one primitive solid. For the object in Fig. 2(a), we can always find the cube and the pyramid. Note that the same primitive solid may be found multiple times from different Finitial, and finally we keep only one copy of each different object (cube and pyramid in this example). When a complex solid is formed by more than two primitive solids, Algorithm 1 can still be used to find the primitive solids, which is the decomposition result of the complex line drawing. More complex examples are given in Section 3. Besides, Algorithm 1 can also deal with complex solids formed by gluing primitive solids between edges and vertices. Fig. 5(a) is a solid constructed by gluing eight primitive solids between faces, edges, and vertices. Running Algorithm 1multiple times with different pairs of neighboring faces in Finitial generates the primitive solids as shown in Fig. 5(b). 2.2. Decomposing line drawings of general objects A general object can be a manifold, non-manifold solid, or non-solid. Given a line drawing representing a general object, it is unknown whether this object consists of only primitive solids. However, we can always apply Algorithm 1to the line drawing multiple times, each with a 1436 Obj6(4)O b j 15( 94)(ca)O b j 24(9 7)Obj3(7)(bd) Fig. 6. Illustration of our decomposition method. (a) A line drawing. (b) The set of MEFSs from (a). (c) The weighted objectcoexistence graph where the maximum weight clique is shown in bold. (d) The decomposition of (a). different pair of neighboring faces in Finitial, generating a set SMEFS of MEFSs (recall that an MEFS with only two initial neighboring faces is discarded). In what follows, we also call an MEFS an object, which is represented by the MEFS. Note that an MEFS generated from a general line drawing may not be a primitive solid, but its DoF must be 4. Objects of DoF 4 have relatively simple structures and are easy to be reconstructed. A number of decomposition examples of complex general line drawings can be seen from the experimental section. One issue existing in this decomposition method is that two different MEFSs may share many faces. For example, from the line drawing in Fig. 6(a), all different MEFSs found by running Algorithm 1multiple times are shown in Fig. 6(b), where Obj 1and Obj 5 share four faces, and so do Obj 2 and Obj 6. Obviously, Obj 5 and Obj 6 are not necessary. Next we define object coexistence and a rule to choose objects. Definition 4. Two objects are called coexistent if they share no face or share only coplanar faces. Rule 1. Choose a subset of SMEFS such that in the subset, all the objects are coexistent and the number of total faces is maximized. From Definition 4, Obj 1 and Obj 5 are not coexistent in Fig. 6, and Obj 2 and Obj 6 are not either. If Obj 5 and Obj 6 are kept with Obj 1and Obj 2 discarded, many faces in the original object will be missing. Rule 1guarantees that Obj 1and Obj 2 are kept but not Obj 5 and Obj 6. Algorithm 2 Decomposition of a general line drawing Algorithm 2 Decomposition of a general line drawing Input: A Line Drawing: G = (V,E,F). Initialization: SMEFS = ∅, SMWC = ∅. 1. for each pair of neighboring faces {fa , fb} in F do 2. Call Algorithm 1with Finitial = {fa , fb} and Vinitial = V er(fa) ∪ V er(fb); 3. if the returned Ffixed from Algorithm 1contains more than two faces do 4. SMEFS ← Ffixed; 5. Construct the object-coexistence graph Gobj with SMEFS ; 6. SMWC ← the maximum weight clique found from Gobj ; 7. for each face f not contained in SMWC do 8. Attach f to the object in SMWC that contains the maximum number of the vertices of f; Return SMWC. Fig.7 (a)Ashe tobjec(ta)with23faces.(b)Decompositon(br)esult by Algorithm 2 with the modification in Algorithm 1. We formulate Rule 1 as a maximum weight clique problem (MWCP), which is to find a clique2 of the maximum weight from a weighted graph. First, we construct a weighted graph, called the object-coexistence graph, in which a vertex denotes an object in SMEFS and there is an edge connecting two vertices if the two objects represented by the two vertices are coexistent. Besides, each vertex is assigned a weight equal to the number of the faces of the corresponding object. The MWCP is a well-known NP-hard problem. In our application, however, solving this problem is fast enough since an object-coexistence graph usually has less than 20 objects (vertices). We use the algorithm in [12] to deal with this problem. Fig. 6(c) is the object-coexistence graph constructed from the six objects in Fig. 6(b), where the weights of the vertices are denoted by the numbers in the parentheses. The maximum weight clique is shown in bold. From Fig. 6, we see that the face (14, 13, 26, 25) is not contained in SWMC, which is used to store the objects in the maximum weight clique. This face is finally attached to Obj 3. In general, each of the faces not in SWMC is attached to an object that contains the maximum number of the vertices of this face. If there are two or more objects that contain the same number of the vertices of this face, this face is assigned to any of them. 2A clique is a subgraph of a graph such that subgraph are connected by an edge. every two vertices in the 1437 Algorithm 2 shows the complete algorithm to decompose a general line drawing. Steps 7 and 8 attach the faces not in SMWC to some objects in SMWC. A common complex object usually consists of primitive solids and sheets, and Algorithm 2 works well for the decomposition of most complex line drawings. However, there are still some line drawings the algorithm cannot deal with. Such an example is shown in Fig. 7(a) which is a sheet object with 23 faces. In Algorithm 1, with any pair of initial neighboring faces, there is no any other face satisfying the condition in step 3, thus no object of DoF 4 will be found. The following scheme can solve this problem. Given a line drawing, steps 1–6 in Algorithm 2 are used to decompose it into multiple objects of DoF 4. If there are separate groups of faces not in SMWC, where the faces in each group are connected, then attach the groups each with less than four faces to some objects in SMWC3 (the attachment method is similar to steps 7 and 8 in Algorithm 2). For a group with four or more connected faces, Algorithm 2 is applied to it with a minor modification in Algorithm 1. The modification is to set Finitial to contain three connected faces whose combined DoF is 5. This modification allows the search of objects of DoF 5. Suppose the object in Fig. 7(a) is such a group. Applying Algorithm 2 to it with the minor modification generates the decomposition result as shown in Fig. 7(b). 2.3. 3D Reconstruction A complex line drawing can be decomposed into several simpler ones using the method proposed in Sections 2. 1 and 2.2. The next step is to reconstruct a 3D object from each ofthem, which is an easy task because the decomposed line drawings are simple. The method in [6] or [7] can carry out this task very well. We use the one in [6] for our work with the objective function Φ(z1 , z2 , ..., zNv ) constructed by these five image regularities: MSDA, face planarity, line parallelism, isometry, and corner orthogonality. The details of the regularities can be found from [6]. After obtaining the 3D objects from all the decomposed line drawings, the next step is to merge them to form one complex object. When merging two 3D objects, since they are reconstructed separately, the gluing parts (face or edge) of them are usually not of the same size. Then one object is automatically rescaled according to the sizes of the two gluing parts, and the vertices of the gluing part of this object are also adjusted so that the two parts are the same. After merging all the 3D objects, the whole object is fine-tuned by minimizing the objective function Φ on the object. We can also apply our method to reconstruct 3D shapes from objects in images. First, the user draws a line drawing along the visible edges of an object and he/she can also 3The reason to attach a group with less than four faces to an object in SMWC is that this group is small and is not necessary to be an independent object to reconstruct. guess (draw) the hidden edges. Then from this line drawing, our approach described above reconstructs the 3D geometry of the object in the image. 3. Experimental Results In this section, we show a number of complex 3D reconstruction examples from both line drawings and images to demonstrate the performance of our approach. The first set of experiments in Fig. 8 has nine complex line drawings. Fig. 8(a) is a manifold, and the others are nonmanifold solids or non-solids. The decompositions of the line drawings are also given in the figure, from which we can see that the results are in accordance with our visual perception very well. All the primitive solids are found by our algorithm. It is the successful decompositions that make the 3D reconstructions from these complex line drawings possible. The expected satisfactory reconstruction results are shown also in Fig. 8 each in two views. Fig. 9 shows another set of 3D reconstructions from objects in images with line drawings drawn on the objects. The decomposition results are omitted due to the space limitation. Each reconstruction result obtained by our algorithm is shown in two views with the texture from the image mapped onto the surface. We can see that the results are very good. The details of the objects and the line drawings can be shown by enlarging the figures on the screen. Among all the previous algorithms for general object reconstruction, the one in [7] can deal with most complex objects. Due to the local minimum problem in a high dimensional search space, however, this algorithm cannot handle line drawings as complex as those in Figs. 8 and 9. For example, Fig. 10(a) shows its reconstruction result from the line drawing in Fig. 8(c), which is a failure. The reader may wonder what happens if the 3D reconstruction is based on an arbitrary decomposition of a complex line drawing, instead of the proposed one. Fig. 10(b) shows such a decomposition from Fig. 8(c). Based on this decomposition, the 3D reconstruction result obtained by the scheme described in Section 2.3 is given in Fig. 10(c), which is a failure. The failure is caused by two reasons: (i) An arbitrary decomposition usually does not generate common objects, which makes the image regularities less meaningful for the 3D reconstruction. (ii) The gluing of 3D objects from the decomposition in Fig. 10(b) is difficult because of the irregular touches between the objects. The fine-tuning processing (see Section 2.3) cannot reduce the large distortion to an acceptable result. Note that since our algorithm is not limited to manifolds, it can deal with line drawings with some or without hidden lines. The third line drawing in Fig. 9 is an example where some hidden lines are not drawn. Most of the line drawings in this paper look tidy. This 1438 (g)(h)(i) Fig. 8. Nine complex line drawings, their decompositons, and 3D reconstruction results in two views wher dif er nt col rs are used to denote the faces (better viewed on the screen). Fig.9 Fourimages,thecorespondi glinedrawings,andther constructed3Dobjectswith exturemap ed,eachs owni twoviews. The details can be seen by enlarging the figures on the screen. 1439 Fig.10(.a( ) Afailedreconstru(cb)tionbythealgorithm(ci)n[7].(b)An Fig.1 .(a ) Alinedrawingwith(bs)trongsketchingero(sc.)(b)(c) arbitrary decomposition of the line drawing in Fig. 8(c) without using our decomposition method. (c) Failed 3D reconstruction based on the decomposition in (b). Two views ofthe successful reconstruction result by our algorithm. is for easy observation of the objects. In fact, our algorithm is not sensitive to sketching errors. Take Fig. 8(a) as an example and assume it is an accurate projection of the 3D object. Then, random variations are generated with the Gaussian distribution N(0, σ2) on the 2D locations of the vertices. Fig. 11(a) is a resulting noisy line drawing with σ = W/200 where W is the width of the line drawing in Fig. 8(a). From Fig. 11, we see that even for this line drawing with strong sketching errors, our algorithm can still obtain the good reconstruction result. Our algorithm is implemented in C++. The computational time includes two parts: line drawing decomposition and 3D reconstruction. The main computation is consumed by the second part. On average, a common PC takes about one minute to obtain the reconstruction from each of the line drawings in Figs. 8 and 9. 4. Conclusion Previous algorithms of 3D object reconstruction from line drawings either deal with simple general objects or are limited to only manifolds (a subset of solids). In this paper, we have proposed a novel approach that can handle complex general objects, including manifolds, nonmanifold solids, and non-solids. It decomposes a complex line drawing into simpler ones according to the degree of freedom of objects, which is based on the developed 3D object properties. After 3D objects are reconstructed from the decomposed line drawings, they are merged to form a complex object. We have shown a number of reconstruction examples with comparison to the best previous algorithm. The results indicate that our algorithm can tackle much more complex line drawings of general objects and is insensitive to sketching errors. The future work includes (i) the correction of the distortions of 3D objects reconstructed from images caused by the perspective projection, and (ii) the extension of this work to objects with curved faces. Acknowledgements This work was supported by grants from Natural Science Foundation of China (No. try, Trade, and Information Shenzhen Municipality, and Guangdong Science, Technology Commission China (No. Innovative 201001D0104648280). 61070148), Indusof JC201005270378A), Research Team Program (No. Jianzhuang Liu is the correspond- ing author. References [1] M. Clowes. On seeing things. Artificial Intelligence, 2:79–1 16, 1971. [2] P. Debevec, C. Taylor, and J. Malik. Modeling and rendering architecture from photographs: A hybrid geometry- and image-based approach. Proc. ACM SIGGRAPH, pages 11–20, 1996. [3] D. Jelinek and C. Taylor. Reconstruction of linearly parameterized models from single images with a camera of unknown focal length. IEEE T-PAMI, 23(7):767–773, 2001. [4] D. E. LaCourse. Handbook of Solid Modeling. McGraw-Hill, 1995. [5] Y. Leclerc and M. Fischler. An optimization-based approach to the interpretation of single line drawings as 3D wire frames. IJCV, 9(2): 113–136, 1992. [6] H. Lipson and M. Shpitalni. Optimization-based reconstruction of a 3d object from a single freehand line drawing. Computer-Aided Design, 28(7):651–663, 1996. [7] J. Liu, L. Cao, Z. Li, and X. Tang. Plane-based optimization for 3D object reconstruction from single line drawings. IEEE T-PAMI, 30(2):315–327, 2008. [8] J. Liu, Y. Chen, and X. Tang. Decomposition of complex line drawings with hidden lines for 3d planar-faced manifold object [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] reconstruction. IEEE T-PAMI, 33(1):3–15, 2011. J. Liu, Y. Lee, and W. Cham. Identifying faces in a 2D line drawing representing a manifold object. IEEE T-PAMI, 24(12): 1579–1593, 2002. J. Liu and X. Tang. Evolutionary search for faces from line drawings. IEEE T-PAMI, 27(6):861–872, 2005. T. Marill. Emulating the human interpretation of line-drawings as three-dimensional objects. IJCV, 6(2): 147–161, 1991 . P. R. J. O¨sterg a˚rd. A new algorithm for the maximum-weight clique problem. Nordic J. of Computing, 8(4):424–436, Dec. 2001 . H. Shimodaira. A shape-from-shading method of polyhedral objects using prior information. IEEE T-PAMI, 28(4):612–624, 2006. I. Shimshoni and J. Ponce. Recovering the shape of polyhedra using line-drawing analysis and complex reflectance models. Computer Vision and Image Understanding, 65(2):296–3 10, 1997. K. Shoji, K. Kato, and F. Toyama. 3-d interpretation of single line drawings based on entropy minimization principle. CVPR, 2001. M. Shpitalni and H. Lipson. Identification of faces in a 2d line drawing projection of a wireframe object. IEEE T-PAMI, 18(10), 1996. K. Sugihara. Machine interpretation of line drawings. MIT Press, 1986. A. Turner, D. Chapman, and A. Penn. Sketching space. Computer and Graphics, 24:869–879, 2000. F. Ulupinar and R. Nevatia. Shape from contour: straight homogeneous generalized cylinders and constant cross-section generalized cylinders. IEEE T-PAMI, 17(2): 120–135, 1995. T. Xue, J. Liu, and X. Tang. Example-based 3d object reconstruction from line drawings. CVPR, 2012. 1440
same-paper 2 0.85637957 10 iccv-2013-A Framework for Shape Analysis via Hilbert Space Embedding
Author: Sadeep Jayasumana, Mathieu Salzmann, Hongdong Li, Mehrtash Harandi
Abstract: We propose a framework for 2D shape analysis using positive definite kernels defined on Kendall’s shape manifold. Different representations of 2D shapes are known to generate different nonlinear spaces. Due to the nonlinearity of these spaces, most existing shape classification algorithms resort to nearest neighbor methods and to learning distances on shape spaces. Here, we propose to map shapes on Kendall’s shape manifold to a high dimensional Hilbert space where Euclidean geometry applies. To this end, we introduce a kernel on this manifold that permits such a mapping, and prove its positive definiteness. This kernel lets us extend kernel-based algorithms developed for Euclidean spaces, such as SVM, MKL and kernel PCA, to the shape manifold. We demonstrate the benefits of our approach over the state-of-the-art methods on shape classification, clustering and retrieval.
3 0.84807217 267 iccv-2013-Model Recommendation with Virtual Probes for Egocentric Hand Detection
Author: Cheng Li, Kris M. Kitani
Abstract: Egocentric cameras can be used to benefit such tasks as analyzing fine motor skills, recognizing gestures and learning about hand-object manipulation. To enable such technology, we believe that the hands must detected on thepixellevel to gain important information about the shape of the hands and fingers. We show that the problem of pixel-wise hand detection can be effectively solved, by posing the problem as a model recommendation task. As such, the goal of a recommendation system is to recommend the n-best hand detectors based on the probe set a small amount of labeled data from the test distribution. This requirement of a probe set is a serious limitation in many applications, such as ego-centric hand detection, where the test distribution may be continually changing. To address this limitation, we propose the use of virtual probes which can be automatically extracted from the test distribution. The key idea is – that many features, such as the color distribution or relative performance between two detectors, can be used as a proxy to the probe set. In our experiments we show that the recommendation paradigm is well-equipped to handle complex changes in the appearance of the hands in firstperson vision. In particular, we show how our system is able to generalize to new scenarios by testing our model across multiple users.
4 0.83278698 437 iccv-2013-Unsupervised Random Forest Manifold Alignment for Lipreading
Author: Yuru Pei, Tae-Kyun Kim, Hongbin Zha
Abstract: Lipreading from visual channels remains a challenging topic considering the various speaking characteristics. In this paper, we address an efficient lipreading approach by investigating the unsupervised random forest manifold alignment (RFMA). The density random forest is employed to estimate affinity of patch trajectories in speaking facial videos. We propose novel criteria for node splitting to avoid the rank-deficiency in learning density forests. By virtue of the hierarchical structure of random forests, the trajectory affinities are measured efficiently, which are used to find embeddings of the speaking video clips by a graph-based algorithm. Lipreading is formulated as matching between manifolds of query and reference video clips. We employ the manifold alignment technique for matching, where the L∞norm-based manifold-to-manifold distance is proposed to find the matching pairs. We apply this random forest manifold alignment technique to various video data sets captured by consumer cameras. The experiments demonstrate that lipreading can be performed effectively, and outperform state-of-the-arts.
5 0.82879829 197 iccv-2013-Hierarchical Joint Max-Margin Learning of Mid and Top Level Representations for Visual Recognition
Author: Hans Lobel, René Vidal, Alvaro Soto
Abstract: Currently, Bag-of-Visual-Words (BoVW) and part-based methods are the most popular approaches for visual recognition. In both cases, a mid-level representation is built on top of low-level image descriptors and top-level classifiers use this mid-level representation to achieve visual recognition. While in current part-based approaches, mid- and top-level representations are usually jointly trained, this is not the usual case for BoVW schemes. A main reason for this is the complex data association problem related to the usual large dictionary size needed by BoVW approaches. As a further observation, typical solutions based on BoVW and part-based representations are usually limited to extensions of binary classification schemes, a strategy that ignores relevant correlations among classes. In this work we propose a novel hierarchical approach to visual recognition based on a BoVW scheme that jointly learns suitable midand top-level representations. Furthermore, using a maxmargin learning framework, the proposed approach directly handles the multiclass case at both levels of abstraction. We test our proposed method using several popular bench- mark datasets. As our main result, we demonstrate that, by coupling learning of mid- and top-level representations, the proposed approach fosters sharing of discriminative visual words among target classes, being able to achieve state-ofthe-art recognition performance using far less visual words than previous approaches.
6 0.82820284 95 iccv-2013-Cosegmentation and Cosketch by Unsupervised Learning
7 0.79881251 123 iccv-2013-Domain Adaptive Classification
8 0.79854625 438 iccv-2013-Unsupervised Visual Domain Adaptation Using Subspace Alignment
9 0.79703951 26 iccv-2013-A Practical Transfer Learning Algorithm for Face Verification
10 0.7946341 181 iccv-2013-Frustratingly Easy NBNN Domain Adaptation
11 0.7943117 328 iccv-2013-Probabilistic Elastic Part Model for Unsupervised Face Detector Adaptation
12 0.79409957 44 iccv-2013-Adapting Classification Cascades to New Domains
13 0.79334193 327 iccv-2013-Predicting an Object Location Using a Global Image Representation
14 0.79310429 392 iccv-2013-Similarity Metric Learning for Face Recognition
15 0.79186457 97 iccv-2013-Coupling Alignments with Recognition for Still-to-Video Face Recognition
16 0.79163325 45 iccv-2013-Affine-Constrained Group Sparse Coding and Its Application to Image-Based Classifications
17 0.79152471 165 iccv-2013-Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies
18 0.79007447 360 iccv-2013-Robust Subspace Clustering via Half-Quadratic Minimization
19 0.79000825 122 iccv-2013-Distributed Low-Rank Subspace Segmentation
20 0.78992438 233 iccv-2013-Latent Task Adaptation with Large-Scale Hierarchies