nips nips2006 nips2006-34 knowledge-graph by maker-knowledge-mining

34 nips-2006-Approximate Correspondences in High Dimensions

Source: pdf

Author: Kristen Grauman, Trevor Darrell

Abstract: Pyramid intersection is an efﬁcient method for computing an approximate partial matching between two sets of feature vectors. We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. The matching similarity is computed in linear time and forms a Mercer kernel. Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate that our approach can maintain constant accuracy even as the feature dimension increases. When used as a kernel in a discriminative classiﬁer, our approach achieves improved object recognition results over a state-of-the-art set kernel. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract Pyramid intersection is an efﬁcient method for computing an approximate partial matching between two sets of feature vectors. [sent-5, score-0.538]

2 We introduce a novel pyramid embedding based on a hierarchy of non-uniformly shaped bins that takes advantage of the underlying structure of the feature space and remains accurate even for sets with high-dimensional feature vectors. [sent-6, score-1.152]

3 Whereas previous matching approximation algorithms suffer from distortion factors that increase linearly with the feature dimension, we demonstrate that our approach can maintain constant accuracy even as the feature dimension increases. [sent-8, score-0.529]

4 1 Introduction When a single data object is described by a set of feature vectors, it is often useful to consider the matching or “correspondence” between two sets’ elements in order to measure their overall similarity or recover the alignment of their parts. [sent-10, score-0.447]

5 The optimal correspondences—those that minimize the matching cost—require cubic time to compute, which quickly becomes prohibitive for sizeable sets and makes processing realistic large data sets impractical. [sent-17, score-0.435]

6 In this paper we present a new algorithm for computing an approximate partial matching between point sets that can remain accurate even for sets with high-dimensional feature vectors, and beneﬁts from taking advantage of the underlying structure in the feature space. [sent-20, score-0.695]

7 For two such histograms (pyramids), the matching cost is efﬁciently calculated by counting the number of features that intersect in each bin, and weighting these match counts according to geometric estimates of inter-feature distances. [sent-22, score-0.634]

8 Our method allows for partial matchings, which means that the input sets can have varying numbers of features in them, and outlier features from the larger set can be ignored with no penalty to the matching cost. [sent-23, score-0.498]

9 The matching score is computed in time linear in the number of features per set, and it forms a Mercer kernel suitable for use within existing kernel-based algorithms. [sent-24, score-0.448]

10 In this paper we demonstrate how, unlike previous set matching approximations (including our original pyramid match algorithm [7]), the proposed approach can maintain consistent accuracy as the dimension of the features within the sets increases. [sent-25, score-1.128]

11 Finally, using our matching measure as a kernel in a discriminative classiﬁer, we achieve improved object recognition results over a state-of-the-art set kernel on a benchmark data set. [sent-27, score-0.429]

12 2 Related Work Several previous matching approximation methods have also considered a hierarchical decomposition of the feature space to reduce matching complexity, but all suffer from distortion factors that scale linearly with the feature dimension [4, 8, 1, 7]. [sent-28, score-0.853]

13 We build on our pyramid match algorithm [7], a partial matching approximation that also uses histogram intersection to efﬁciently count matches implicitly formed by the bin structures. [sent-30, score-1.658]

14 However, in contrast to [7], our use of data-dependent, non-uniform bins and a more precise weighting scheme results in matchings that are consistently accurate for structured, high-dimensional data. [sent-31, score-0.416]

15 A variant of the pyramid match applied to spatial features was shown to be effective for matching quantized features in [10]. [sent-33, score-1.092]

16 The actual tree structure employed is similar to the one constructed in this work; however, whereas the authors of [13] are interested in matching individual features to one another to access an inverted ﬁle, our approach computes approximate correspondences between sets of features. [sent-35, score-0.51]

17 3 Approach The main contribution of this work is a new very efﬁcient approximate bipartite matching method that measures the correspondence-based similarity between unordered, variable-sized sets of vectors, and can optionally extract an explicit correspondence ﬁeld. [sent-39, score-0.492]

18 We call our algorithm the vocabulary-guided (VG) pyramid match, since the histogram pyramids are deﬁned by the “vocabulary” or structure of the feature space, and the pyramids are used to count implicit matches. [sent-40, score-1.069]

19 The basic idea is to ﬁrst partition the given feature space into a pyramid of non-uniformly shaped regions based on the distribution of a provided corpus of feature vectors. [sent-41, score-0.823]

20 Point sets are then encoded as multi-resolution histograms determined by that pyramid, and an efﬁcient intersection-based computation between any two histogram pyramids yields an approximate matching score for the original sets. [sent-42, score-0.644]

21 The implicit matching version of our method estimates the inter-feature distances based on their respective distances to the bin centers. [sent-43, score-0.807]

22 To produce an explicit correspondence ﬁeld between the sets, we use the pyramid construct to divide-and-conquer the optimal matching computation. [sent-44, score-0.955]

23 (a) Uniform bins (b) Vocabulary-guided bins Figure 1: Rather than carve the feature space into uniformly-shaped partitions (left), we let the vocabulary (structure) of the feature space determine the partitions (right). [sent-52, score-0.916]

24 As a result, the bins are better concentrated on decomposing the space where features cluster, particularly for high-dimensional feature spaces. [sent-53, score-0.452]

25 Features are red points, bin centers are larger black points, and blue lines denote bin boundaries. [sent-56, score-0.808]

26 A partial matching between two point sets is an assignment that maps all points in the smaller set to some subset of the points in the larger (or equally-sized) set. [sent-57, score-0.515]

27 Given point sets X and Y, where m = |X|, n = |Y|, and m ≤ n, a partial matching M (X, Y; π) = {(x1 , yπ1 ), . [sent-58, score-0.401]

28 The cost of a partial matching is the sum of the distances between matched points: ∗ C (M(X, Y; π)) = xi ∈X ||xi − yπi ||2 . [sent-65, score-0.45]

29 The optimal partial matching M(X, Y; π ) uses the ∗ ∗ assignment π that minimizes this cost: π = argminπ C (M(X, Y; π)). [sent-66, score-0.399]

30 1 Building Vocabulary-Guided Pyramids The ﬁrst step is to generate the structure of the vocabulary-guided (VG) pyramid to deﬁne the bin placement for the multi-resolution histograms used in the matching. [sent-71, score-1.036]

31 We would like the bins in the pyramid to follow the feature distribution and concentrate partitions where the features actually fall. [sent-73, score-1.044]

32 We randomly select some example feature vectors from the feature type of interest to form the representative feature corpus, and perform hierarchical k-means clustering with the Euclidean distance to build the pyramid tree. [sent-75, score-0.951]

33 Then the clustering is repeated recursively L − 1 times on each of these groups, ﬁlling out a tree with L total levels containing k i bins (nodes) at level i, where levels are counted from the root (i = 0) to the leaves (i = L − 1). [sent-79, score-0.477]

34 ) For each bin in the VG pyramid we record its diameter, which we estimate empirically based on the maximal inter-feature distance between any points from the initial feature corpus that were assigned to it. [sent-82, score-1.175]

35 A point’s placement in the pyramid is determined by comparing it to the appropriate k bin centers at each of the L pyramid levels. [sent-84, score-1.562]

36 The histogram count is incremented for the bin (among the k choices) that the point is nearest to in terms of the same distance function used to cluster the initial corpus. [sent-85, score-0.586]

37 This amounts to a total of kL distances that must be computed between a point and the pyramid’s bin centers. [sent-88, score-0.483]

38 Given the bin structure of the VG pyramid, a point set X is mapped to its pyramid: Ψ (X) = [H0 (X), . [sent-89, score-0.427]

39 Each entry in this histogram is a triple p, n, d giving the bin index, the bin count, and the bin’s points’ maximal distance to the bin center, respectively. [sent-96, score-1.368]

40 Storing the VG pyramid itself requires space for O(k L ) d-dimensional feature vectors, i. [sent-97, score-0.65]

41 However, each point set’s histogram is stored sparsely, meaning only O(mL) nonzero bin counts are maintained to encode the entire pyramid for a set with m features. [sent-100, score-1.12]

42 , pi ], pj ∈ [1, k] denotes the indices of the clusters traversed from the root so far, n ∈ Z+ denotes the count for the bin (initially 1), and d ∈ denotes the distance computed between the inserted point and the current bin’s center. [sent-107, score-0.538]

43 Upon reaching the leaf level, p is an L-dimensional path-vector indicating which of the k bins were chosen at each level, and every path-vector uniquely identiﬁes some bin on the pyramid. [sent-108, score-0.703]

44 Maintaining the maximum distance of any point in a bin to the bin center will allow us to efﬁciently estimate inter-point distances at the time of matching, as described in Section 3. [sent-112, score-0.921]

45 2 Vocabulary-Guided Pyramid Match Given two point sets’ pyramid encodings, we efﬁciently compute the approximate matching score using a simple weighted intersection measure. [sent-115, score-0.963]

46 The basic intuition is to start collecting groups of matched points from the bottom of the pyramid up, i. [sent-117, score-0.638]

47 In this way, we will ﬁrst consider matching the closest points (at the leaves), and as we climb to the higher-level clusters in the pyramid we will allow increasingly further points to be matched. [sent-120, score-0.932]

48 We deﬁne the number of new matches within a bin to be a count of the minimum number of points either of the two input sets contributes to that bin, minus the number of matches already counted by any of its child bins. [sent-121, score-0.763]

49 Let nij (X) denote the element n from p, n, d j , the j th bin entry of histogram Hi (X), and let ch (nij (X)) denote the element n for the hth child bin of that entry, 1 ≤ h ≤ k. [sent-123, score-1.068]

50 Given point sets X and Y, we compute the matching score via their pyramids Ψ(X) and Ψ(Y) as follows: C (Ψ(X), Ψ(Y)) = i L−1 X X k i=0 j=1 " wij min (nij (X), nij (Y)) − k X h=1 # min (ch (nij (X)) , ch (nij (Y))) . [sent-125, score-0.731]

51 (1) The outer sum loops over the levels in the pyramids; the second sum loops over the bins at a given level, and the innermost sum loops over the children of a given bin. [sent-126, score-0.411]

52 The number of new matches calculated for a bin is weighted by wij , an estimate of the distance between points contained in the bin. [sent-131, score-0.607]

53 1 With a VG pyramid match there are two alternatives for the distance estimate: (a) weights based on the diameters of the pyramid’s bins, or (b) input-dependent weights based on the maximal distances of the points in the bin to its center. [sent-132, score-1.297]

54 Option (b)’s input-speciﬁc weights estimate the distance between any two points in the bin as the sum of the stored maximal to-center distances from either input set: wij = dij (X) + dij (Y). [sent-134, score-0.659]

55 This weighting 1 To use our matching as a cost function, weights are set as the distance estimates; to use as a similarity measure or kernel, weights are set as (some function of) the inverse of the distance estimates. [sent-135, score-0.516]

56 A key aspect of our method is that we obtain a measure of matching quality between two point sets without computing pair-wise distances between their features—an O(m2 ) savings over sub-optimal greedy matchings. [sent-140, score-0.421]

57 Instead, we exploit the fact that the points’ placement in the pyramid reﬂects their distance from one another. [sent-141, score-0.635]

58 The only inter-feature distances computed are the kL distances needed to insert a point into the pyramid, and this small one-time cost is amortized every time we re-use a histogram to approximate another matching against a different point set. [sent-142, score-0.565]

59 However, in [7], bins are constructed to uniformly partition the space, bin diameters exponentially increase over the levels, and intersections are weighted indistinguishably across an entire level. [sent-144, score-0.737]

60 In contrast, here we have developed a pyramid embedding that partitions according to the distribution of features, and weighting schemes that allow more precise approximations of the inter-feature costs. [sent-145, score-0.668]

61 As we will show in Section 4, our VG pyramid match remains accurate and efﬁcient even for high-dimensional feature spaces, while the uniform-bin pyramid match is limited in practice to relatively low-dimensional features. [sent-146, score-1.479]

62 For the increased accuracy our method provides, there are some complexity trade-offs versus [7], which does not require computing any distances to place the points into bins; their uniform shape and size allows points to be placed directly via division by bin size. [sent-147, score-0.618]

63 On the other hand, sorting the bin indices with the VG method has a lower complexity, since the values only range to k, the branch factor, which is typically much smaller than the aspect ratio that bounds the range in [7]. [sent-148, score-0.458]

64 1 as: C (Ψ(X), Ψ(Y)) = i=0 j=1 (wij − pij ) min (nij (X), nij (Y)), where pij refers to the weight associated with the parent bin of the j th node at level i. [sent-158, score-0.594]

65 [14], and since kernels are closed under summation and scaling by a positive constant [15], we have that the VG pyramid match is a Mercer kernel if wij ≥ pij . [sent-161, score-0.783]

66 This inequality holds if every child bin receives a similarity weight that is greater than its parent bin, or rather that every child bin has a distance estimate that is less than that of its parent. [sent-162, score-0.939]

67 In this case, the VG pyramid decomposes the required matching computation into a hierarchy of smaller matchings. [sent-167, score-0.848]

68 Upon encountering a bin with a nonzero intersection, the optimal matching is computed between only those features from the two sets that fall into that particular bin. [sent-168, score-0.883]

69 All points that are used in that per-bin matching are then ﬂagged as matched and may not take part in subsequent matchings at coarser resolutions of the pyramid. [sent-169, score-0.471]

70 4 Results In this section, we provide results to empirically demonstrate our matching’s accuracy and efﬁciency on real data, and we compare it to a pyramid match using a uniform partitioning of the feature space. [sent-170, score-0.871]

71 In addition to directly evaluating the matching scores and correspondence ﬁelds, we show that our method leads to improved object recognition performance when used as a kernel within a discriminative classiﬁer. [sent-171, score-0.499]

72 9 1000 0 2000 4000 6000 8000 0 10000 2000 4000 6000 8000 10000 Uniform bin pyramid match ranks Rank correlations, d=8(R=0. [sent-176, score-1.16]

73 7 0 0 Uniform bin pyramid match ranks Optimal ranks Spearman rank correlation with optimal match (R) 1 Optimal ranks Uniform bin pyramid VG pyramid − input−specific weights VG pyramid − global weights 9000 8000 Ranking quality over feature dimensions 1. [sent-182, score-3.79]

74 Left: The set rankings produced with the VG pyramid match are consistently accurate for increasing feature dimensions, while the accuracy with uniform bins degrades about linearly in the feature dimension. [sent-184, score-1.31]

75 For each feature dimension, we built a VG pyramid with k = 10 and L = 5, encoded the 100 point sets as pyramids, and computed the pair-wise matching scores with both our method and the optimal least-cost matching. [sent-190, score-1.093]

76 If our measure is approximating the optimal matching well, we should ﬁnd the ranking we induce to be highly correlated with the ranking produced by the optimal matching for the same data. [sent-191, score-0.72]

77 The left plot in Figure 2 shows the Spearman correlation scores against the optimal measure for both our method (with both weighting options) and the approximation in [7] for varying feature dimensions for the 10,000 pair-wise matching scores for the 100 test sets. [sent-194, score-0.64]

78 While the VG pyramid match remains consistently accurate for high feature dimensions (R = 0. [sent-196, score-0.861]

79 95 with input-speciﬁc weights), the accuracy of the uniform bins degrades rapidly for dimensions over 10. [sent-197, score-0.436]

80 The ranking quality of the input-speciﬁc weighting scheme (blue diamonds) is somewhat stronger than that of the “global” bin diameter weighting scheme (green squares). [sent-198, score-0.587]

81 For the low-dimensional features, the methods perform fairly comparably; however, for the full 128-D features, the VG pyramid match is far superior (rightmost column). [sent-201, score-0.681]

82 Computing the pyramid structure from the feature corpus took about three minutes in Matlab; this is a one-time ofﬂine cost. [sent-204, score-0.695]

83 For a pyramid matching to work well, the gradation in bin sizes up the pyramid must be such that at most levels of the pyramid we can capture distinct groups of points to match within the bins. [sent-205, score-2.592]

84 That is, unless all the points in two sets are equidistant, the bin placement must allow us to match very near points at the ﬁnest resolutions, and gradually add matches that are more distant at coarser resolutions. [sent-206, score-0.817]

85 In high dimensions with uniform partitions, points begin sharing a bin “all at once”; in contrast, the VG bins still accrue new matches consistently across levels since the decomposition is tailored to where points cluster in the feature space. [sent-211, score-1.152]

86 ) match (share bins), the bins are so large that almost all of them match. [sent-225, score-0.423]

87 The matching score is then approximately the number of points weighted by a single bin size. [sent-226, score-0.762]

88 Approximate Correspondence Fields: For the same image data, we ran the explicit matching variant of our method and compared the induced correspondences to those produced by the globally optimal measure. [sent-229, score-0.41]

89 However, in high dimensions, the time required by the uniform bin pyramid with the optimal per-bin matching approaches the time required by the optimal matching itself. [sent-237, score-1.701]

90 In contrast, the expense of the VG pyramid matching remains steady and low, even for high dimensions, since data-dependent pyramids better divide the matching labor into the natural segments in the feature space. [sent-239, score-1.39]

91 The VG bins divide the computation so it can be done inexpensively, while the uniform bins divide the computation poorly and must compute it expensively, but about as accurately. [sent-241, score-0.672]

92 Likewise, the error for the uniform bins when using a per-bin random assignment is very high for any but the lowest dimensions (red line on left plot), since such a large number of points are being randomly assigned to one another. [sent-242, score-0.508]

93 In contrast, the VG bins actually result in similar errors whether the points in a bin are matched optimally or randomly (blue and pink lines on left plot). [sent-243, score-0.784]

94 Pyramid matching method Vocabulary-guided bins Uniform bins Mean recognition rate/class (d=128 / d=10) 99. [sent-244, score-0.931]

95 7e-4 This again indicates that tuning the pyramid bins to the data’s distribution achieves a much more suitable breakdown of the computation, even in high dimensions. [sent-252, score-0.856]

96 Realizing Improvements in Recognition: Finally, we have experimented with the VG pyramid match within a discriminative classiﬁer for an object recognition task. [sent-253, score-0.757]

97 To form a Mercer kernel, the weights were set according to each bin diameter Aij : wij = e−Aij /σ , with σ set automatically as the mean distance between a sample of features from the training set. [sent-258, score-0.617]

98 The table shows our improvements over the uniform-bin pyramid match kernel. [sent-259, score-0.681]

99 The VG pyramid match is more accurate and requires minor additional computation. [sent-260, score-0.705]

100 Conclusion: We have introduced a linear-time method to compute a matching between point sets that takes advantage of the underlying structure in the feature space and remains consistently accurate and efﬁcient for high-dimensional inputs on real image data. [sent-264, score-0.507]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('pyramid', 0.557), ('bin', 0.404), ('vg', 0.325), ('bins', 0.299), ('matching', 0.291), ('pyramids', 0.158), ('match', 0.124), ('nij', 0.106), ('feature', 0.093), ('matches', 0.079), ('ranks', 0.075), ('uniform', 0.074), ('spearman', 0.066), ('correspondence', 0.065), ('dimensions', 0.063), ('vocabulary', 0.062), ('guided', 0.062), ('mercer', 0.06), ('features', 0.06), ('distances', 0.056), ('histogram', 0.055), ('weighting', 0.054), ('correspondences', 0.052), ('sets', 0.051), ('diameter', 0.048), ('count', 0.048), ('hi', 0.048), ('wij', 0.048), ('counts', 0.046), ('rankings', 0.046), ('corpus', 0.045), ('placement', 0.044), ('recognition', 0.042), ('optimal', 0.042), ('points', 0.042), ('per', 0.041), ('matchings', 0.039), ('matched', 0.039), ('level', 0.038), ('rank', 0.037), ('entry', 0.036), ('partial', 0.036), ('scores', 0.036), ('shaped', 0.035), ('nonzero', 0.035), ('partitions', 0.035), ('diameters', 0.034), ('distance', 0.034), ('intersection', 0.034), ('child', 0.034), ('object', 0.034), ('levels', 0.034), ('vision', 0.033), ('hierarchical', 0.033), ('approximate', 0.033), ('option', 0.032), ('coarser', 0.031), ('specific', 0.031), ('triple', 0.031), ('kernel', 0.031), ('histograms', 0.031), ('assignment', 0.03), ('formed', 0.03), ('resolutions', 0.029), ('oct', 0.029), ('ch', 0.029), ('grauman', 0.029), ('sift', 0.029), ('distortion', 0.029), ('sorted', 0.029), ('indices', 0.029), ('correlations', 0.029), ('similarity', 0.029), ('cost', 0.028), ('ranking', 0.027), ('gradation', 0.026), ('voronoi', 0.026), ('counted', 0.026), ('dij', 0.026), ('loops', 0.026), ('vectors', 0.025), ('image', 0.025), ('sorting', 0.025), ('score', 0.025), ('plot', 0.025), ('accurate', 0.024), ('lists', 0.024), ('pij', 0.023), ('optionally', 0.023), ('dimension', 0.023), ('weights', 0.023), ('clustering', 0.023), ('tree', 0.023), ('point', 0.023), ('partitioning', 0.023), ('approximations', 0.022), ('cluster', 0.022), ('quantization', 0.022), ('june', 0.022), ('index', 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999976 34 nips-2006-Approximate Correspondences in High Dimensions

Author: Kristen Grauman, Trevor Darrell

2 0.25738144 17 nips-2006-A recipe for optimizing a time-histogram

Author: Hideaki Shimazaki, Shigeru Shinomoto

Abstract: The time-histogram method is a handy tool for capturing the instantaneous rate of spike occurrence. In most of the neurophysiological literature, the bin size that critically determines the goodness of the ﬁt of the time-histogram to the underlying rate has been selected by individual researchers in an unsystematic manner. We propose an objective method for selecting the bin size of a time-histogram from the spike data, so that the time-histogram best approximates the unknown underlying rate. The resolution of the histogram increases, or the optimal bin size decreases, with the number of spike sequences sampled. It is notable that the optimal bin size diverges if only a small number of experimental trials are available from a moderately ﬂuctuating rate process. In this case, any attempt to characterize the underlying spike rate will lead to spurious results. Given a paucity of data, our method can also suggest how many more trials are needed until the set of data can be analyzed with the required resolution. 1

3 0.15215936 66 nips-2006-Detecting Humans via Their Pose

Author: Alessandro Bissacco, Ming-Hsuan Yang, Stefano Soatto

Abstract: We consider the problem of detecting humans and classifying their pose from a single image. Speciﬁcally, our goal is to devise a statistical model that simultaneously answers two questions: 1) is there a human in the image? and, if so, 2) what is a low-dimensional representation of her pose? We investigate models that can be learned in an unsupervised manner on unlabeled images of human poses, and provide information that can be used to match the pose of a new image to the ones present in the training set. Starting from a set of descriptors recently proposed for human detection, we apply the Latent Dirichlet Allocation framework to model the statistics of these features, and use the resulting model to answer the above questions. We show how our model can efﬁciently describe the space of images of humans with their pose, by providing an effective representation of poses for tasks such as classiﬁcation and matching, while performing remarkably well in human/non human decision problems, thus enabling its use for human detection. We validate the model with extensive quantitative experiments and comparisons with other approaches on human detection and pose matching. 1

4 0.14739154 39 nips-2006-Balanced Graph Matching

Author: Timothee Cour, Praveen Srinivasan, Jianbo Shi

Abstract: Graph matching is a fundamental problem in Computer Vision and Machine Learning. We present two contributions. First, we give a new spectral relaxation technique for approximate solutions to matching problems, that naturally incorporates one-to-one or one-to-many constraints within the relaxation scheme. The second is a normalization procedure for existing graph matching scoring functions that can dramatically improve the matching accuracy. It is based on a reinterpretation of the graph matching compatibility matrix as a bipartite graph on edges for which we seek a bistochastic normalization. We evaluate our two contributions on a comprehensive test set of random graph matching problems, as well as on image correspondence problem. Our normalization procedure can be used to improve the performance of many existing graph matching algorithms, including spectral matching, graduated assignment and semideﬁnite programming. 1

5 0.098940931 110 nips-2006-Learning Dense 3D Correspondence

Author: Florian Steinke, Volker Blanz, Bernhard Schölkopf

Abstract: Establishing correspondence between distinct objects is an important and nontrivial task: correctness of the correspondence hinges on properties which are difﬁcult to capture in an a priori criterion. While previous work has used a priori criteria which in some cases led to very good results, the present paper explores whether it is possible to learn a combination of features that, for a given training set of aligned human heads, characterizes the notion of correct correspondence. By optimizing this criterion, we are then able to compute correspondence and morphs for novel heads. 1

6 0.094474487 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

7 0.094052508 201 nips-2006-Using Combinatorial Optimization within Max-Product Belief Propagation

8 0.078039549 103 nips-2006-Kernels on Structured Objects Through Nested Histograms

9 0.07469213 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

10 0.074037939 122 nips-2006-Learning to parse images of articulated bodies

11 0.071244031 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

12 0.064455397 55 nips-2006-Computation of Similarity Measures for Sequential Data using Generalized Suffix Trees

13 0.062509425 74 nips-2006-Efficient Structure Learning of Markov Networks using $L 1$-Regularization

14 0.062014367 130 nips-2006-Max-margin classification of incomplete data

15 0.057409178 65 nips-2006-Denoising and Dimension Reduction in Feature Space

16 0.056461647 99 nips-2006-Information Bottleneck Optimization and Independent Component Extraction with Spiking Neurons

17 0.054933671 175 nips-2006-Simplifying Mixture Models through Function Approximation

18 0.052967921 5 nips-2006-A Kernel Method for the Two-Sample-Problem

19 0.050774235 115 nips-2006-Learning annotated hierarchies from relational data

20 0.050222769 199 nips-2006-Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.18), (1, 0.011), (2, 0.092), (3, -0.012), (4, 0.099), (5, -0.002), (6, -0.106), (7, -0.026), (8, 0.039), (9, -0.122), (10, 0.011), (11, 0.075), (12, 0.088), (13, 0.015), (14, 0.236), (15, -0.052), (16, -0.224), (17, -0.093), (18, 0.077), (19, -0.211), (20, 0.061), (21, -0.075), (22, 0.106), (23, -0.027), (24, 0.03), (25, -0.1), (26, 0.229), (27, -0.108), (28, 0.035), (29, 0.101), (30, -0.012), (31, 0.03), (32, 0.063), (33, 0.018), (34, -0.121), (35, 0.061), (36, 0.077), (37, 0.044), (38, -0.09), (39, 0.077), (40, -0.003), (41, -0.065), (42, -0.046), (43, -0.168), (44, -0.162), (45, 0.119), (46, 0.036), (47, 0.119), (48, -0.118), (49, 0.048)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.95950747 34 nips-2006-Approximate Correspondences in High Dimensions

Author: Kristen Grauman, Trevor Darrell

2 0.73967737 17 nips-2006-A recipe for optimizing a time-histogram

Author: Hideaki Shimazaki, Shigeru Shinomoto

3 0.52738941 39 nips-2006-Balanced Graph Matching

Author: Timothee Cour, Praveen Srinivasan, Jianbo Shi

4 0.45915997 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

Author: Graham Mcneill, Sethu Vijayakumar

Abstract: Correspondence algorithms typically struggle with shapes that display part-based variation. We present a probabilistic approach that matches shapes using independent part transformations, where the parts themselves are learnt during matching. Ideas from semi-supervised learning are used to bias the algorithm towards ﬁnding ‘perceptually valid’ part structures. Shapes are represented by unlabeled point sets of arbitrary size and a background component is used to handle occlusion, local dissimilarity and clutter. Thus, unlike many shape matching techniques, our approach can be applied to shapes extracted from real images. Model parameters are estimated using an EM algorithm that alternates between ﬁnding a soft correspondence and computing the optimal part transformations using Procrustes analysis.

5 0.42828494 66 nips-2006-Detecting Humans via Their Pose

Author: Alessandro Bissacco, Ming-Hsuan Yang, Stefano Soatto

6 0.40276301 201 nips-2006-Using Combinatorial Optimization within Max-Product Belief Propagation

7 0.3707138 110 nips-2006-Learning Dense 3D Correspondence

8 0.31619522 5 nips-2006-A Kernel Method for the Two-Sample-Problem

9 0.31245926 174 nips-2006-Similarity by Composition

10 0.30095977 122 nips-2006-Learning to parse images of articulated bodies

11 0.29912031 55 nips-2006-Computation of Similarity Measures for Sequential Data using Generalized Suffix Trees

12 0.29586592 162 nips-2006-Predicting spike times from subthreshold dynamics of a neuron

13 0.28031147 103 nips-2006-Kernels on Structured Objects Through Nested Histograms

14 0.27283764 155 nips-2006-Optimal Single-Class Classification Strategies

15 0.25473192 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

16 0.25358042 179 nips-2006-Sparse Representation for Signal Classification

17 0.24271773 99 nips-2006-Information Bottleneck Optimization and Independent Component Extraction with Spiking Neurons

18 0.24228846 185 nips-2006-Subordinate class recognition using relational object models

19 0.23695914 130 nips-2006-Max-margin classification of incomplete data

20 0.22785324 78 nips-2006-Fast Discriminative Visual Codebooks using Randomized Clustering Forests

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(1, 0.079), (3, 0.038), (7, 0.073), (9, 0.053), (20, 0.021), (21, 0.026), (22, 0.064), (44, 0.069), (57, 0.127), (65, 0.066), (69, 0.064), (71, 0.013), (87, 0.19), (90, 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.89519656 123 nips-2006-Learning with Hypergraphs: Clustering, Classification, and Embedding

Author: Dengyong Zhou, Jiayuan Huang, Bernhard Schölkopf

Abstract: We usually endow the investigated objects with pairwise relationships, which can be illustrated as graphs. In many real-world problems, however, relationships among the objects of our interest are more complex than pairwise. Naively squeezing the complex relationships into pairwise ones will inevitably lead to loss of information which can be expected valuable for our learning tasks however. Therefore we consider using hypergraphs instead to completely represent complex relationships among the objects of our interest, and thus the problem of learning with hypergraphs arises. Our main contribution in this paper is to generalize the powerful methodology of spectral clustering which originally operates on undirected graphs to hypergraphs, and further develop algorithms for hypergraph embedding and transductive classiﬁcation on the basis of the spectral hypergraph clustering approach. Our experiments on a number of benchmarks showed the advantages of hypergraphs over usual graphs. 1

2 0.86284119 144 nips-2006-Near-Uniform Sampling of Combinatorial Spaces Using XOR Constraints

Author: Carla P. Gomes, Ashish Sabharwal, Bart Selman

Abstract: We propose a new technique for sampling the solutions of combinatorial problems in a near-uniform manner. We focus on problems speciﬁed as a Boolean formula, i.e., on SAT instances. Sampling for SAT problems has been shown to have interesting connections with probabilistic reasoning, making practical sampling algorithms for SAT highly desirable. The best current approaches are based on Markov Chain Monte Carlo methods, which have some practical limitations. Our approach exploits combinatorial properties of random parity (XOR) constraints to prune away solutions near-uniformly. The ﬁnal sample is identiﬁed amongst the remaining ones using a state-of-the-art SAT solver. The resulting sampling distribution is provably arbitrarily close to uniform. Our experiments show that our technique achieves a signiﬁcantly better sampling quality than the best alternative. 1

same-paper 3 0.85147494 34 nips-2006-Approximate Correspondences in High Dimensions

Author: Kristen Grauman, Trevor Darrell

4 0.71484518 8 nips-2006-A Nonparametric Approach to Bottom-Up Visual Saliency

Author: Wolf Kienzle, Felix A. Wichmann, Matthias O. Franz, Bernhard Schölkopf

Abstract: This paper addresses the bottom-up inﬂuence of local image information on human eye movements. Most existing computational models use a set of biologically plausible linear ﬁlters, e.g., Gabor or Difference-of-Gaussians ﬁlters as a front-end, the outputs of which are nonlinearly combined into a real number that indicates visual saliency. Unfortunately, this requires many design parameters such as the number, type, and size of the front-end ﬁlters, as well as the choice of nonlinearities, weighting and normalization schemes etc., for which biological plausibility cannot always be justiﬁed. As a result, these parameters have to be chosen in a more or less ad hoc way. Here, we propose to learn a visual saliency model directly from human eye movement data. The model is rather simplistic and essentially parameter-free, and therefore contrasts recent developments in the ﬁeld that usually aim at higher prediction rates at the cost of additional parameters and increasing model complexity. Experimental results show that—despite the lack of any biological prior knowledge—our model performs comparably to existing approaches, and in fact learns image features that resemble ﬁndings from several previous studies. In particular, its maximally excitatory stimuli have center-surround structure, similar to receptive ﬁelds in the early human visual system. 1

5 0.71371436 112 nips-2006-Learning Nonparametric Models for Probabilistic Imitation

Author: David B. Grimes, Daniel R. Rashid, Rajesh P. Rao

Abstract: Learning by imitation represents an important mechanism for rapid acquisition of new behaviors in humans and robots. A critical requirement for learning by imitation is the ability to handle uncertainty arising from the observation process as well as the imitator’s own dynamics and interactions with the environment. In this paper, we present a new probabilistic method for inferring imitative actions that takes into account both the observations of the teacher as well as the imitator’s dynamics. Our key contribution is a nonparametric learning method which generalizes to systems with very different dynamics. Rather than relying on a known forward model of the dynamics, our approach learns a nonparametric forward model via exploration. Leveraging advances in approximate inference in graphical models, we show how the learned forward model can be directly used to plan an imitating sequence. We provide experimental results for two systems: a biomechanical model of the human arm and a 25-degrees-of-freedom humanoid robot. We demonstrate that the proposed method can be used to learn appropriate motor inputs to the model arm which imitates the desired movements. A second set of results demonstrates dynamically stable full-body imitation of a human teacher by the humanoid robot. 1

6 0.70744348 160 nips-2006-Part-based Probabilistic Point Matching using Equivalence Constraints

7 0.70406473 118 nips-2006-Learning to Model Spatial Dependency: Semi-Supervised Discriminative Random Fields

8 0.70374233 110 nips-2006-Learning Dense 3D Correspondence

9 0.70278019 167 nips-2006-Recursive ICA

10 0.70263332 72 nips-2006-Efficient Learning of Sparse Representations with an Energy-Based Model

11 0.70243657 42 nips-2006-Bayesian Image Super-resolution, Continued

12 0.70088768 158 nips-2006-PG-means: learning the number of clusters in data

13 0.70006269 3 nips-2006-A Complexity-Distortion Approach to Joint Pattern Alignment

14 0.69994277 94 nips-2006-Image Retrieval and Classification Using Local Distance Functions

15 0.69975364 119 nips-2006-Learning to Rank with Nonsmooth Cost Functions

16 0.69884217 43 nips-2006-Bayesian Model Scoring in Markov Random Fields

17 0.69603771 76 nips-2006-Emergence of conjunctive visual features by quadratic independent component analysis

18 0.69428658 175 nips-2006-Simplifying Mixture Models through Function Approximation

19 0.69199657 47 nips-2006-Boosting Structured Prediction for Imitation Learning

20 0.69185394 79 nips-2006-Fast Iterative Kernel PCA