cvpr cvpr2013 cvpr2013-126 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Michael Donoser, Horst Bischof
Abstract: In this paper we revisit diffusion processes on affinity graphs for capturing the intrinsic manifold structure defined by pairwise affinity matrices. Such diffusion processes have already proved the ability to significantly improve subsequent applications like retrieval. We give a thorough overview of the state-of-the-art in this field and discuss obvious similarities and differences. Based on our observations, we are then able to derive a generic framework for diffusion processes in the scope of retrieval applications, where the related work represents specific instances of our generic formulation. We evaluate our framework on several retrieval tasks and are able to derive algorithms that e. g. achieve a 100% bullseye score on the popular MPEG7 shape retrieval data set.
Reference: text
sentIndex sentText sentNum sentScore
1 at cg Abstract In this paper we revisit diffusion processes on affinity graphs for capturing the intrinsic manifold structure defined by pairwise affinity matrices. [sent-3, score-1.201]
2 Such diffusion processes have already proved the ability to significantly improve subsequent applications like retrieval. [sent-4, score-0.819]
3 Based on our observations, we are then able to derive a generic framework for diffusion processes in the scope of retrieval applications, where the related work represents specific instances of our generic formulation. [sent-6, score-1.171]
4 achieve a 100% bullseye score on the popular MPEG7 shape retrieval data set. [sent-9, score-0.5]
5 First, the manifold, defined by the provided affinity matrix, is interpreted as a weighted graph, where each element is represented by a node, and edges connect all nodes with corresponding edge weights proportional to the pairwise affinity values. [sent-18, score-0.354]
6 The most common diffusion processes are based on random walks, where a transition matrix defines probabilities for walking from one node to a neighboring one, which are fixed proportional to the provided affinities. [sent-20, score-1.179]
7 By repeatedly making random walk steps on the graph, affinities are spread on the manifold, which in turn improves the obtainable retrieval scores. [sent-21, score-0.572]
8 Let us consider a toy example to illustrate the useful- ness of such diffusion processes for retrieval tasks. [sent-22, score-0.986]
9 Figure 1 shows a toy pattern, where two query points are defined, and as the scope of retrieval is to return the most similar examples from the database, all other elements are labeled according to the larger affinity to one of the two query points. [sent-23, score-0.641]
10 As can be seen without diffusion the underlying manifold is not considered and retrieval performance is insufficient. [sent-24, score-0.947]
11 In comparison, after diffusing the similarities through the manifold and capturing the intrinsic global manifold structure, we get significantly improved retrieval results. [sent-25, score-0.374]
12 In general, diffusion processes iteratively update the provided affinity matrices, until some kind of convergence is achieved. [sent-26, score-1.0]
13 Therefore, in this paper we mainly focus on iterative diffusion processes, where we further speed up the process, by sparsifying the graph structure, e. [sent-29, score-0.783]
14 To summarize, diffusion processes have shown to be an indispensable tool for improving retrieval performance. [sent-33, score-0.986]
15 Additionally, we outline relations to a game theoretical process and derive a novel formulation for diffu1 1 13 3 31 12 80 8 Figure 1: Illustration of usefulness of diffusion processes for retrieval. [sent-35, score-0.921]
16 Affinities before (left) and after (right) the diffusion are used to assign each element to the highlighted query samples according to their pairwise affinities. [sent-36, score-0.899]
17 Applying a diffusion process spreads affinities and allows to significantly improve retrieval performance (best viewed in color). [sent-38, score-1.056]
18 Finally, it turns out, that all these methods can be summarized into one, generic diffusion framework, which we describe in Section 3. [sent-40, score-0.739]
19 obtains a 100% bullseye score on the × popular MPEG7 data set, as it is shown in Section 4. [sent-45, score-0.333]
20 Related Work We start by reviewing the state-of-the art in the field of retrieval, with a specific focus on methods based on diffusion processes. [sent-47, score-0.75]
21 Diffusion processes in general start from a provided pairwise N N affinity matrix A, which relates pNro dviidffeerde pnta rewleimseen Nts ×to Nea achff ontithyer m. [sent-48, score-0.435]
22 aFtririxst step, i sc hto r einlateter-s pret the matrix A as a graph G = (V, E), consisting of N nporedtes th vi ∈a Vrix , aAnd a edges eij G∈ =E ( tVh,aEt l)i,n kco nnosidsetsin tgo oefa cNh other, fixing Vth ,e a edge weights ∈to Eth teh provided affinity vaaclhues Aij . [sent-49, score-0.276]
23 Diffusion processes then spread the affinity values through the entire graph, based on the defined edge weights. [sent-50, score-0.296]
24 This process is interpretable as a random walk on the graph, where a so-called transition matrix defines probabilities for walking from one node to a neighboring node. [sent-51, score-0.533]
25 As we will see in the following discussion of related work, diffusion processes mainly differ in (a) initialization, (b) definition of the transition matrix and (c) definition of the diffusion process. [sent-53, score-1.79]
26 Thus, P is a row-stochastic matrix (rows sum up to 1), containing the transition probabilities for a random walk in the corresponding graph. [sent-61, score-0.465]
27 Indeed, the iterative process converges to the left eigenvector of the transition matrix P with corresponding eigenvalue 1. [sent-67, score-0.426]
28 The random walk model was later extended to one of the first and most successful retrieval methods: the Google PageRank system [17]. [sent-68, score-0.331]
29 Thus, the standard random walk is modified, and at each time step t a random walk step is done with probability α, whereas a random jump to an arbitrary node is made with probability (1 α). [sent-72, score-0.387]
30 Main difference to PageRank is the slightly adapted transition matrix defined as PNC = D−1/2 AD−1/2 , (7) which we denote as PNC because of its analogy to the normalized Graph Laplacian used in normalized cut segmentation. [sent-80, score-0.273]
31 This matrix is symmetric (in contrast to the random walk transition matrix P). [sent-81, score-0.512]
32 A related diffusion process origins from the field of semi-supervised learning denoted as label propagation (LP) [24], where the goal is to spread information from labeled to unlabeled data. [sent-83, score-0.849]
33 Label Propagation applies the standard random walk diffusion step (Equation 4), but in contrast injects query information in a specific manner by fixing f (i) = 1after each diffusion step. [sent-85, score-1.683]
34 Running this diffusion process for infinite time converges to a constant vector and assigns each node the same label (since only the query is labeled). [sent-86, score-0.913]
35 Thus, graph transduction cannot be written in matrix form as shown in Equation 6, since the matrix A differs for all query elements. [sent-90, score-0.38]
36 More interesting, normalization is based on an analysis ofthe nearest neighbors (NN) ofthe query, which constrains the diffusion process locally and yields different transition matrices for each query element. [sent-92, score-1.136]
37 In [21] the idea of constraining the diffusion graph to local neighborhoods is further investigated (LCDP). [sent-94, score-0.794]
38 Authors also use a kNN-Graph to define the locality, but in contrast to [2] additionally adapt the diffusion process. [sent-95, score-0.698]
39 The paper describes that this idea can be encoded into the diffusion process by adapting the update step to Wt+1 = PWt PT . [sent-98, score-0.813]
40 (8) Interestingly, in [22] exactly the same diffusion step is derived from a different point of view. [sent-99, score-0.698]
41 It is denoted as tensor graph diffusion (TGD) and aims at integrating relations of higher order than pairwise affinities into the diffusion process. [sent-100, score-1.694]
42 The diffusion process on such a graph again converges to a non-trivial solution. [sent-103, score-0.823]
43 Nevertheless, this form of diffusion is impracticable since the graphs are really huge. [sent-104, score-0.734]
44 For this reason, authors show that the diffusion process on the tensor graph is identical to a modified diffusion process on the standard graph, which turns out to be the same as in [21] (see Equation 8). [sent-105, score-1.568]
45 In [20] another variant to define a neighborhood graph for diffusion, denoted as shortest path propagation (SPP), was presented, where shortest paths were independently analyzed for each query element. [sent-106, score-0.368]
46 Again, just for retrieving the improved neighborhood graph an independent diffusion process has to be applied, which significantly increases runtime. [sent-111, score-0.832]
47 In contrast, diffusion maps [4] are also based on a diffusion process on a graph and additionally induce a global similarity metric. [sent-113, score-1.497]
48 Also for diffusion maps the random walk transition matrix P is used to propagate affinities through the manifold. [sent-114, score-1.263]
49 The final diffusion map distances (for a fixed t) can be found in closed form, by eigenvalue weighted Euclidean distances between eigenvectors of P. [sent-115, score-0.752]
50 1 1 13 3 32 2 202 0 Recently, in [8] a self-smoothing operator (SSO) was introduced which is related to diffusion maps. [sent-117, score-0.698]
51 This approach was extended in [19] by a slight adaption ofthe diffusion step denoted as selfdiffusion (SD), where a closed form solution for specific t values was provided. [sent-119, score-0.752]
52 Interestingly also the recently quite popular evolutionary replicator dynamics (RD) can be interpreted as diffusion process on a matrix. [sent-121, score-0.911]
53 RD are a first order evolutionary dynamic from the field of game theory defined by the following diffusion process fti+1= fti f(tATAft)fit, (9) where fti is the i-th element ofthe vector f. [sent-125, score-0.977]
54 As can be seen the iterative process highly relates to diffusion processes if written in matrix notation as Wt+1 = Wt ? [sent-141, score-0.983]
55 Although, the matrix A is not a valid transition matrix it encodes the same global information as the commonly used P and is therefore, also applicable for diffusion. [sent-148, score-0.348]
56 Also methods from the field of clustering are frequently based on such diffusion processes, and we would like to mention the most related ones. [sent-149, score-0.753]
57 This method is also based on the observation that the largest eigenvector of the random walk transition matrix P is always a constant vector with eigenvalue 1. [sent-151, score-0.506]
58 In [3], a method denoted as authority shift clustering (ASC) was proposed, where the personalized PageRank matrix is considered in the diffusion process and during evolution the emerging clusters are analyzed and linked to each other to define a hierarchical clustering result. [sent-153, score-1.044]
59 Finally, a few methods try to improve provided affinity matrices without diffusion processes. [sent-154, score-0.859]
60 The main idea is to build a specific graph structure and simply let the shortest path through the graph define the new affinities between the elements. [sent-160, score-0.294]
61 To summarize, a lot of different diffusion principles have been proposed in the last years. [sent-161, score-0.698]
62 Improving Retrieval by Diffusion Based on the findings on related work in the field of retrieval, we are able to formulate a generic framework for diffusion processes, where all methods discussed in the previous section represent single instances of our framework. [sent-167, score-0.802]
63 Our generic formulation then allows to define and validate a set of novel diffusion processes, that are thoroughly eval- × uated in the experimental section. [sent-168, score-0.787]
64 All affinity values together form the N N input affinity matrix A defined as A=⎜⎝⎛A N. [sent-177, score-0.351]
65 Initialization W0Transition TDiffusion Table 1: Overview of related work in the field of diffusion processes. [sent-182, score-0.728]
66 All methods start from the defined initialization W0 (first column) and iteratively propagate similarities through the underlying manifold using the defined transition matrix T (second column) in the defined diffusion scheme (third column). [sent-183, score-1.199]
67 The goal of retrieval is to consider each element xi as independent query and rank all other points according to their pairwise affinities to the specified query point xi. [sent-185, score-0.619]
68 Thus, we next define a generic diffusion framework, which converts a given affinity matrix A into a novel, diffused version A∗ . [sent-188, score-0.952]
69 Analyzing the related work, it can clearly be seen that diffusion processes mainly consist of three important steps: (A) Initialization, (B) Definition of the transition matrix and (C) Definition of the diffusion process. [sent-190, score-1.79]
70 Our framework allows four types of initialization (A1)-(A4) (Table 2), six different types of transition matrices (B 1)-(B6) (Table 3) and finally three main diffusion variants (C1)-(C3) (Table 4). [sent-192, score-1.013]
71 F×or 6 a×ll 3co =mb 7i2na ptioosnssib we essta trot from the initialization W0, and apply iterative updates using the transition matrix T in the defined diffusion process, as long as the average number of changing elements in the obtained rankings between two subsequent iterations is below ? [sent-195, score-1.095]
72 Therefore, we focus on the iterative diffusion processes that converge to the same solution and that are directly applicable for large scale analysis. [sent-200, score-0.841]
73 Experiments Goal of our experiments is a thorough comparison of the achievable performance of the 72 diffusion variants that can be applied based on the generic framework described in the last section. [sent-203, score-0.815]
74 We implemented our diffusion framework in Matlab and code is provided at http : / /vh . [sent-205, score-0.698]
75 cent years, concerning (a) the shape matching algorithms applied for defining the pairwise affinities and (b) the improvements in the field of diffusion processes. [sent-215, score-0.906]
76 Retrieval accuracy is measured by ranking all other elements for each query and calculating the average number of occurrences of elements of the same category as the query, within the 40 first ranked elements. [sent-217, score-0.259]
77 This measure is denoted as the bullseye score and its upper limit is 100%, which means that for each query the 20 instances of the same category are ranked within the first 40. [sent-218, score-0.513]
78 If directly analyzing the distance matrix of [7] without ap- plying diffusion we get a baseline bullseye score of 93. [sent-219, score-1.139]
79 Retrieval score is again measured by a bullseye score, analyzing the 15 most similar instances. [sent-225, score-0.366]
80 The same representation as for YALE data set is used to build the distance matrix, and the bullseye score considering 15 closest neighbors is used to evaluate retrieval quality. [sent-229, score-0.534]
81 Evaluation of Retrieval Performance As a first experiment we identify the most promising combination out of our pool of 72 variants, by analyzing the best achievable bullseye score after diffusion. [sent-234, score-0.405]
82 Tables 5 (MPEG7), 6 (YALE) and 7 (ORL) list bullseye scores in a compactified manner. [sent-241, score-0.311]
83 oca Flu neighbors by adapting tthhee transition matrix P to the k-nearest neighbors PkNN (B4) or to the dominant set PDS (B5) seems to bring the largest boost in performance, especially for the diffusion variants (C1) and (C2). [sent-250, score-1.171]
84 Thus, PkNN seems the way to go, because PDS requires significantly more time (since for obtaining the dominant set an independent diffusion step is required), while in essence results are not substantially different. [sent-251, score-0.759]
85 Only, if using the game theoretical diffusion (C3) one has to initialize either using the affinity matrix A (A1) or the transition matrix P (A3), other initializations do not provide reasonable results for (C3). [sent-255, score-1.223]
86 In overall, starting from the kNN-PageRank transition matrix PkNN (A4) seems to lead to fastest convergence and best performance, which up to now has only be considered in the clustering approach of [3]. [sent-256, score-0.329]
87 To summarize, as most promising combination, we choose to initialize the diffusion process by the transition matrix PkNN (A4), to constrain the transition matrix to the k-nearest neighbors (B4) and to apply the higher-order diffusion process (C2). [sent-257, score-2.091]
88 Influence of Locality As we demonstrated in the last section, constraining the diffusion process locally is a promising direction to improve retrieval scores. [sent-262, score-0.997]
89 Obtainable scores for the most promising diffusion variant (see previous section) are shown in Figure 2. [sent-264, score-0.761]
90 c eO ins MsigPnEifGic7a nthtley c imhopicreov iesd insignificant, from K = 9 upwards the diffusion process always leads to a 100% bullseye score, since this data set is already satu- rated. [sent-266, score-1.023]
91 On the other two data sets YALE and ORL, tuning of K allows to improve performance, where on ORL an optimal bullseye score of 77. [sent-267, score-0.333]
92 35% sults, researching methods to automatically find an optimal K for constrained diffusion processes in an efficient manner seems to be a promising future direction of research. [sent-339, score-0.889]
93 As can be seen, we are able to demonstrate for the first time a 100% bullseye score on this challenging data set, i. [sent-344, score-0.333]
94 1 1 13 3 32 2 246 4 Figure 2: Influence of adapting the local neighborhood on the obtainable retrieval scores (best viewed in color). [sent-347, score-0.334]
95 Conclusion In this paper we introduced a generic diffusion framework evaluated in the scope of retrieval applications. [sent-359, score-0.951]
96 Our diffusion methods start from different initializations, and use different combinations of transition matrix and diffusion process variants, to iteratively spread affinities through the underlying data manifold. [sent-360, score-1.92]
97 We further outlined that the state-of-the-art in this field represents specific instances of our diffusion framework. [sent-361, score-0.761]
98 We provided a thorough evaluation, highlighting that constraining the diffusion locally achieves the most promising boost in performance, where automatically selecting a reasonable local neighborhood size is still an open issue. [sent-362, score-0.886]
99 The best performing instance of our generic framework for example achieved a 100% bullseye score on the popular MPEG7 data set. [sent-363, score-0.374]
100 Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval. [sent-493, score-0.758]
wordName wordTfidf (topN-words)
[('diffusion', 0.698), ('bullseye', 0.287), ('transition', 0.198), ('retrieval', 0.167), ('pagerank', 0.159), ('affinity', 0.138), ('walk', 0.135), ('orl', 0.133), ('affinities', 0.128), ('yale', 0.127), ('query', 0.123), ('processes', 0.121), ('pknn', 0.09), ('pnc', 0.09), ('personalized', 0.083), ('obtainable', 0.076), ('matrix', 0.075), ('asc', 0.074), ('similarities', 0.067), ('evolutionary', 0.064), ('graph', 0.063), ('dynamics', 0.063), ('wt', 0.058), ('initialization', 0.057), ('manifold', 0.056), ('pairwise', 0.05), ('lcdp', 0.048), ('replicator', 0.048), ('thoroughly', 0.048), ('score', 0.046), ('ranking', 0.046), ('eigenvector', 0.045), ('scope', 0.045), ('elements', 0.045), ('idsc', 0.044), ('transduction', 0.044), ('update', 0.043), ('generic', 0.041), ('webpage', 0.04), ('latecki', 0.04), ('fti', 0.04), ('shortest', 0.04), ('game', 0.039), ('nevertheless', 0.039), ('thorough', 0.039), ('promising', 0.039), ('simplex', 0.038), ('process', 0.038), ('variants', 0.037), ('spread', 0.037), ('ft', 0.037), ('impracticable', 0.036), ('pds', 0.036), ('tgd', 0.036), ('xnc', 0.036), ('knn', 0.035), ('neighbors', 0.034), ('adapting', 0.034), ('rating', 0.034), ('tensor', 0.033), ('constraining', 0.033), ('instances', 0.033), ('analyzing', 0.033), ('neighborhood', 0.033), ('tpg', 0.032), ('meta', 0.032), ('sso', 0.032), ('seems', 0.031), ('dominant', 0.03), ('field', 0.03), ('node', 0.03), ('closed', 0.03), ('authority', 0.03), ('relates', 0.029), ('aij', 0.029), ('random', 0.029), ('air', 0.029), ('element', 0.028), ('probabilities', 0.028), ('diffusing', 0.028), ('underlying', 0.026), ('donoser', 0.025), ('spreads', 0.025), ('clustering', 0.025), ('derive', 0.025), ('denoted', 0.024), ('eigenvalue', 0.024), ('converges', 0.024), ('scores', 0.024), ('matrices', 0.023), ('evolution', 0.023), ('analyzed', 0.023), ('iterative', 0.022), ('locally', 0.022), ('start', 0.022), ('influence', 0.022), ('highlighting', 0.022), ('listed', 0.022), ('pt', 0.022), ('propagation', 0.022)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999917 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
Author: Michael Donoser, Horst Bischof
Abstract: In this paper we revisit diffusion processes on affinity graphs for capturing the intrinsic manifold structure defined by pairwise affinity matrices. Such diffusion processes have already proved the ability to significantly improve subsequent applications like retrieval. We give a thorough overview of the state-of-the-art in this field and discuss obvious similarities and differences. Based on our observations, we are then able to derive a generic framework for diffusion processes in the scope of retrieval applications, where the related work represents specific instances of our generic formulation. We evaluate our framework on several retrieval tasks and are able to derive algorithms that e. g. achieve a 100% bullseye score on the popular MPEG7 shape retrieval data set.
2 0.29633415 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Author: Vittal Premachandran, Ramakrishna Kakarala
Abstract: Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a “good” neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task. The most common way to select a local neighborhood has been to use the k-nearest neighborhood (k-NN) selection criterion. However, it has the tendency to include noisy edges. In this paper, we propose a way to select a robust neighborhood using the consensus of multiple rounds of k-NNs. We explain how using consensus information can give better control over neighborhood selection. We also explain in detail the problems with another recently proposed neighborhood selection criteria, i.e., Dominant Neighbors, and show that our method is immune to those problems. Finally, we show the results from experiments in which we compare our method to other neighborhood selection approaches. The results corroborate our claims that consensus ofk-NNs does indeed help in selecting more robust and stable localities.
3 0.22429971 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
Author: Lili Tao, Bogdan J. Matuszewski
Abstract: In this paper, a novel approach based on a non-linear manifold learning technique is proposed to recover 3D nonrigid structures from 2D image sequences captured by a single camera. Most ofthe existing approaches assume that 3D shapes can be accurately modelled in a linear subspace. These techniques perform well when the deformations are relatively small or simple, but fail when more complex deformations need to be recovered. The non-linear deformations are often observed in highly flexible objects for which the use of the linear model is impractical. A specific type of shape variations might be governed by only a small number of parameters, therefore can be wellrepresented in a low dimensional manifold. We learn a nonlinear shape prior using diffusion maps method. The key contribution in this paper is the introduction of the shape prior that constrain the reconstructed shapes to lie in the learned manifold. The proposed methodology has been validated quantitatively and qualitatively on 2D points sequences projected from the 3D motion capture data and real 2D video sequences. The comparisons oftheproposed man- ifold based method against several state-of-the-art techniques are shown on different types of deformable objects.
4 0.22268742 93 cvpr-2013-Constraints as Features
Author: Shmuel Asafi, Daniel Cohen-Or
Abstract: In this paper, we introduce a new approach to constrained clustering which treats the constraints as features. Our method augments the original feature space with additional dimensions, each of which derived from a given Cannot-link constraints. The specified Cannot-link pair gets extreme coordinates values, and the rest of the points get coordinate values that express their spatial influence from the specified constrained pair. After augmenting all the new features, a standard unconstrained clustering algorithm can be performed, like k-means or spectral clustering. We demonstrate the efficacy of our method for active semi-supervised learning applied to image segmentation and compare it to alternative methods. We also evaluate the performance of our method on the four most commonly evaluated datasets from the UCI machine learning repository.
5 0.12967317 405 cvpr-2013-Sparse Subspace Denoising for Image Manifolds
Author: Bo Wang, Zhuowen Tu
Abstract: With the increasing availability of high dimensional data and demand in sophisticated data analysis algorithms, manifold learning becomes a critical technique to perform dimensionality reduction, unraveling the intrinsic data structure. The real-world data however often come with noises and outliers; seldom, all the data live in a single linear subspace. Inspired by the recent advances in sparse subspace learning and diffusion-based approaches, we propose a new manifold denoising algorithm in which data neighborhoods are adaptively inferred via sparse subspace reconstruction; we then derive a new formulation to perform denoising to the original data. Experiments carried out on both toy and real applications demonstrate the effectiveness of our method; it is insensitive to parameter tuning and we show significant improvement over the competing algorithms.
6 0.11807931 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
7 0.11096448 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
8 0.085914679 309 cvpr-2013-Nonparametric Scene Parsing with Adaptive Feature Relevance and Semantic Context
9 0.080808178 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
10 0.07899534 260 cvpr-2013-Learning and Calibrating Per-Location Classifiers for Visual Place Recognition
11 0.069565967 301 cvpr-2013-Multi-target Tracking by Rank-1 Tensor Approximation
13 0.06105205 456 cvpr-2013-Visual Place Recognition with Repetitive Structures
14 0.060087159 375 cvpr-2013-Saliency Detection via Graph-Based Manifold Ranking
15 0.058869876 366 cvpr-2013-Robust Region Grouping via Internal Patch Statistics
16 0.058703315 56 cvpr-2013-Bayesian Depth-from-Defocus with Shading Constraints
17 0.057769906 106 cvpr-2013-Deformable Graph Matching
18 0.057255704 82 cvpr-2013-Class Generative Models Based on Feature Regression for Pose Estimation of Object Categories
19 0.056257237 327 cvpr-2013-Pattern-Driven Colorization of 3D Surfaces
20 0.054837205 259 cvpr-2013-Learning a Manifold as an Atlas
topicId topicWeight
[(0, 0.146), (1, -0.003), (2, -0.013), (3, 0.025), (4, 0.074), (5, -0.006), (6, -0.04), (7, -0.114), (8, -0.064), (9, -0.045), (10, 0.038), (11, 0.038), (12, -0.087), (13, -0.029), (14, -0.024), (15, -0.054), (16, -0.049), (17, -0.018), (18, -0.021), (19, -0.037), (20, 0.092), (21, 0.057), (22, 0.003), (23, 0.107), (24, 0.03), (25, -0.005), (26, 0.144), (27, -0.031), (28, -0.033), (29, 0.088), (30, 0.093), (31, -0.137), (32, 0.036), (33, -0.022), (34, 0.024), (35, 0.08), (36, 0.058), (37, -0.022), (38, -0.04), (39, -0.077), (40, 0.004), (41, -0.061), (42, 0.002), (43, 0.146), (44, -0.038), (45, -0.095), (46, -0.054), (47, 0.242), (48, 0.097), (49, 0.01)]
simIndex simValue paperId paperTitle
same-paper 1 0.96048641 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
Author: Michael Donoser, Horst Bischof
Abstract: In this paper we revisit diffusion processes on affinity graphs for capturing the intrinsic manifold structure defined by pairwise affinity matrices. Such diffusion processes have already proved the ability to significantly improve subsequent applications like retrieval. We give a thorough overview of the state-of-the-art in this field and discuss obvious similarities and differences. Based on our observations, we are then able to derive a generic framework for diffusion processes in the scope of retrieval applications, where the related work represents specific instances of our generic formulation. We evaluate our framework on several retrieval tasks and are able to derive algorithms that e. g. achieve a 100% bullseye score on the popular MPEG7 shape retrieval data set.
2 0.87959391 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
Author: Vittal Premachandran, Ramakrishna Kakarala
Abstract: Propagating similarity information along the data manifold requires careful selection of local neighborhood. Selecting a “good” neighborhood in an unsupervised setting, given an affinity graph, has been a difficult task. The most common way to select a local neighborhood has been to use the k-nearest neighborhood (k-NN) selection criterion. However, it has the tendency to include noisy edges. In this paper, we propose a way to select a robust neighborhood using the consensus of multiple rounds of k-NNs. We explain how using consensus information can give better control over neighborhood selection. We also explain in detail the problems with another recently proposed neighborhood selection criteria, i.e., Dominant Neighbors, and show that our method is immune to those problems. Finally, we show the results from experiments in which we compare our method to other neighborhood selection approaches. The results corroborate our claims that consensus ofk-NNs does indeed help in selecting more robust and stable localities.
3 0.66555375 93 cvpr-2013-Constraints as Features
Author: Shmuel Asafi, Daniel Cohen-Or
Abstract: In this paper, we introduce a new approach to constrained clustering which treats the constraints as features. Our method augments the original feature space with additional dimensions, each of which derived from a given Cannot-link constraints. The specified Cannot-link pair gets extreme coordinates values, and the rest of the points get coordinate values that express their spatial influence from the specified constrained pair. After augmenting all the new features, a standard unconstrained clustering algorithm can be performed, like k-means or spectral clustering. We demonstrate the efficacy of our method for active semi-supervised learning applied to image segmentation and compare it to alternative methods. We also evaluate the performance of our method on the four most commonly evaluated datasets from the UCI machine learning repository.
4 0.57355994 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
Author: Song Cao, Noah Snavely
Abstract: Recognizing the location of a query image by matching it to a database is an important problem in computer vision, and one for which the representation of the database is a key issue. We explore new ways for exploiting the structure of a database by representing it as a graph, and show how the rich information embedded in a graph can improve a bagof-words-based location recognition method. In particular, starting from a graph on a set of images based on visual connectivity, we propose a method for selecting a set of subgraphs and learning a local distance function for each using discriminative techniques. For a query image, each database image is ranked according to these local distance functions in order to place the image in the right part of the graph. In addition, we propose a probabilistic method for increasing the diversity of these ranked database images, again based on the structure of the image graph. We demonstrate that our methods improve performance over standard bag-of-words methods on several existing location recognition datasets.
5 0.5281378 106 cvpr-2013-Deformable Graph Matching
Author: Feng Zhou, Fernando De_la_Torre
Abstract: Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to many problems in computer vision. Although widely used, existing GM algorithms cannot incorporate global consistence among nodes, which is a natural constraint in computer vision problems. This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. The key idea of this work is a new factorization of the pair-wise affinity matrix. This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. Second, it provides a unified view of many GM methods and extends the standard iterative closest point algorithm. Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. Experimental results on synthetic and real databases illustrate how DGM outperforms state-of-the-art algorithms for GM. The code is available at http : / / human s en s ing . c s . cmu .edu / fgm.
6 0.5230425 343 cvpr-2013-Query Adaptive Similarity for Large Scale Object Retrieval
7 0.5160194 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
8 0.51217884 191 cvpr-2013-Graph-Laplacian PCA: Closed-Form Solution and Robustness
9 0.50616843 306 cvpr-2013-Non-rigid Structure from Motion with Diffusion Maps Prior
10 0.47449508 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
11 0.46901494 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
12 0.45906535 259 cvpr-2013-Learning a Manifold as an Atlas
13 0.4580884 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
14 0.44058412 405 cvpr-2013-Sparse Subspace Denoising for Image Manifolds
15 0.43118948 193 cvpr-2013-Graph Transduction Learning with Connectivity Constraints with Application to Multiple Foreground Cosegmentation
16 0.42384094 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
17 0.41857782 240 cvpr-2013-Keypoints from Symmetries by Wave Propagation
18 0.40425 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
19 0.4032732 260 cvpr-2013-Learning and Calibrating Per-Location Classifiers for Visual Place Recognition
20 0.38996506 276 cvpr-2013-MKPLS: Manifold Kernel Partial Least Squares for Lipreading and Speaker Identification
topicId topicWeight
[(10, 0.106), (16, 0.014), (26, 0.061), (33, 0.344), (67, 0.068), (69, 0.039), (87, 0.071), (99, 0.203)]
simIndex simValue paperId paperTitle
1 0.93992865 181 cvpr-2013-Fusing Depth from Defocus and Stereo with Coded Apertures
Author: Yuichi Takeda, Shinsaku Hiura, Kosuke Sato
Abstract: In this paper we propose a novel depth measurement method by fusing depth from defocus (DFD) and stereo. One of the problems of passive stereo method is the difficulty of finding correct correspondence between images when an object has a repetitive pattern or edges parallel to the epipolar line. On the other hand, the accuracy of DFD method is inherently limited by the effective diameter of the lens. Therefore, we propose the fusion of stereo method and DFD by giving different focus distances for left and right cameras of a stereo camera with coded apertures. Two types of depth cues, defocus and disparity, are naturally integrated by the magnification and phase shift of a single point spread function (PSF) per camera. In this paper we give the proof of the proportional relationship between the diameter of defocus and disparity which makes the calibration easy. We also show the outstanding performance of our method which has both advantages of two depth cues through simulation and actual experiments.
Author: Won Hwa Kim, Moo K. Chung, Vikas Singh
Abstract: The analysis of 3-D shape meshes is a fundamental problem in computer vision, graphics, and medical imaging. Frequently, the needs of the application require that our analysis take a multi-resolution view of the shape ’s local and global topology, and that the solution is consistent across multiple scales. Unfortunately, the preferred mathematical construct which offers this behavior in classical image/signal processing, Wavelets, is no longer applicable in this general setting (data with non-uniform topology). In particular, the traditional definition does not allow writing out an expansion for graphs that do not correspond to the uniformly sampled lattice (e.g., images). In this paper, we adapt recent results in harmonic analysis, to derive NonEuclidean Wavelets based algorithms for a range of shape analysis problems in vision and medical imaging. We show how descriptors derived from the dual domain representation offer native multi-resolution behavior for characterizing local/global topology around vertices. With only minor modifications, the framework yields a method for extracting interest/key points from shapes, a surprisingly simple algorithm for 3-D shape segmentation (competitive with state of the art), and a method for surface alignment (without landmarks). We give an extensive set of comparison results on a large shape segmentation benchmark and derive a uniqueness theorem for the surface alignment problem.
3 0.92624164 73 cvpr-2013-Bringing Semantics into Focus Using Visual Abstraction
Author: C. Lawrence Zitnick, Devi Parikh
Abstract: Relating visual information to its linguistic semantic meaning remains an open and challenging area of research. The semantic meaning of images depends on the presence of objects, their attributes and their relations to other objects. But precisely characterizing this dependence requires extracting complex visual information from an image, which is in general a difficult and yet unsolved problem. In this paper, we propose studying semantic information in abstract images created from collections of clip art. Abstract images provide several advantages. They allow for the direct study of how to infer high-level semantic information, since they remove the reliance on noisy low-level object, attribute and relation detectors, or the tedious hand-labeling of images. Importantly, abstract images also allow the ability to generate sets of semantically similar scenes. Finding analogous sets of semantically similar real images would be nearly impossible. We create 1,002 sets of 10 semantically similar abstract scenes with corresponding written descriptions. We thoroughly analyze this dataset to discover semantically important features, the relations of words to visual features and methods for measuring semantic similarity.
4 0.90837312 130 cvpr-2013-Discriminative Color Descriptors
Author: Rahat Khan, Joost van_de_Weijer, Fahad Shahbaz Khan, Damien Muselet, Christophe Ducottet, Cecile Barat
Abstract: Color description is a challenging task because of large variations in RGB values which occur due to scene accidental events, such as shadows, shading, specularities, illuminant color changes, and changes in viewing geometry. Traditionally, this challenge has been addressed by capturing the variations in physics-basedmodels, and deriving invariants for the undesired variations. The drawback of this approach is that sets of distinguishable colors in the original color space are mapped to the same value in the photometric invariant space. This results in a drop of discriminative power of the color description. In this paper we take an information theoretic approach to color description. We cluster color values together based on their discriminative power in a classification problem. The clustering has the explicit objective to minimize the drop of mutual information of the final representation. We show that such a color description automatically learns a certain degree of photometric invariance. We also show that a universal color representation, which is based on other data sets than the one at hand, can obtain competing performance. Experiments show that the proposed descriptor outperforms existing photometric invariants. Furthermore, we show that combined with shape description these color descriptors obtain excellent results on four challenging datasets, namely, PASCAL VOC 2007, Flowers-102, Stanford dogs-120 and Birds-200.
same-paper 5 0.90710837 126 cvpr-2013-Diffusion Processes for Retrieval Revisited
Author: Michael Donoser, Horst Bischof
Abstract: In this paper we revisit diffusion processes on affinity graphs for capturing the intrinsic manifold structure defined by pairwise affinity matrices. Such diffusion processes have already proved the ability to significantly improve subsequent applications like retrieval. We give a thorough overview of the state-of-the-art in this field and discuss obvious similarities and differences. Based on our observations, we are then able to derive a generic framework for diffusion processes in the scope of retrieval applications, where the related work represents specific instances of our generic formulation. We evaluate our framework on several retrieval tasks and are able to derive algorithms that e. g. achieve a 100% bullseye score on the popular MPEG7 shape retrieval data set.
6 0.90527326 98 cvpr-2013-Cross-View Action Recognition via a Continuous Virtual Path
7 0.88328511 416 cvpr-2013-Studying Relationships between Human Gaze, Description, and Computer Vision
8 0.87893206 43 cvpr-2013-Analyzing Semantic Segmentation Using Hybrid Human-Machine CRFs
9 0.8776418 82 cvpr-2013-Class Generative Models Based on Feature Regression for Pose Estimation of Object Categories
10 0.87759435 25 cvpr-2013-A Sentence Is Worth a Thousand Pixels
11 0.87704718 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
12 0.87692273 202 cvpr-2013-Hierarchical Saliency Detection
13 0.87682676 168 cvpr-2013-Fast Object Detection with Entropy-Driven Evaluation
14 0.87611574 242 cvpr-2013-Label Propagation from ImageNet to 3D Point Clouds
15 0.87577105 196 cvpr-2013-HON4D: Histogram of Oriented 4D Normals for Activity Recognition from Depth Sequences
16 0.87561607 187 cvpr-2013-Geometric Context from Videos
17 0.8756094 207 cvpr-2013-Human Pose Estimation Using a Joint Pixel-wise and Part-wise Formulation
18 0.8754825 15 cvpr-2013-A Lazy Man's Approach to Benchmarking: Semisupervised Classifier Evaluation and Recalibration
19 0.87522811 284 cvpr-2013-Mesh Based Semantic Modelling for Indoor and Outdoor Scenes
20 0.87510687 173 cvpr-2013-Finding Things: Image Parsing with Regions and Per-Exemplar Detectors