iccv iccv2013 iccv2013-309 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
Reference: text
sentIndex sentText sentNum sentScore
1 A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. [sent-12, score-0.199]
2 This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. [sent-14, score-0.707]
3 curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. [sent-17, score-0.644]
4 In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. [sent-19, score-1.204]
5 Introduction Optimization of curvature and higher-order regularizers, in general, has significant potential in segmentation, stereo, 3D reconstruction, image restoration, in-painting, and other applications. [sent-21, score-0.644]
6 success of global optimization methods for first-order MRF models [3, 10] researchers now focus on more difficult second-order functionals [34] including various discrete approximations of curvature [27, 7, 30]. [sent-29, score-0.771]
7 Similarly, recent progress on global optimization techniques for first-order continuous geometric functionals [20, 23, 16, 35] has lead to extensions for curvature [4]. [sent-30, score-0.731]
8 Our technique evaluates curvature using small patches either on a grid or on a cell complex, as illustrated in Fig. [sent-38, score-0.937]
9 In case of a grid, our patches use a novel integral geometry approach to evaluating curvature. [sent-40, score-0.35]
10 The relationship to previous discrete MRF models for curvature is discussed in Section 2. [sent-42, score-0.684]
11 We also propose a very simple and efficient optimization technique, partial enumeration, directly applicable to our patch-based curvature model and some other high-order problems. [sent-43, score-0.722]
12 Our approach reduces high-order discrete energy formulations to pair-wise Constraint Satisfaction Problem with unary costs (uCSP). [sent-44, score-0.413]
13 2936 (a) curvature patches on a cell complex (basic geometry) (b) our cell-complex patches (8-connected), up to symmetries, and resulting segmentation. [sent-47, score-0.978]
14 (c) curvature patches on a pixel grid (integral geometry) up to symmetries, and resulting segmentation. [sent-48, score-0.901]
15 Figure 1: Evaluating curvature of a segment on a complex (a,b) and on a grid (c,d) using s? [sent-49, score-0.714]
16 We use (overlapping) patches created for each vertex on a complex (a) and for each pixel on a gr? [sent-54, score-0.221]
17 ts W Woef all cells adjacent to a vertex and a grid patch (c,d) is a square window centered at a pixel. [sent-57, score-0.219]
18 However, each corner on a grid (c) should be evaluated using integral geometry by summing over multiple patches covering the corner. [sent-62, score-0.396]
19 The accuracy of integral geometry approach to curvature on a grid is comparable to the standard basic geometry used on complexes, see (b) and (d). [sent-69, score-0.955]
20 Curvature on patches and related work We discuss approximation of curvature in the context of binary segmentation with regularization energy E(S) =? [sent-71, score-1.055]
21 1(a) can be seen as “dual” methods for estimating curvature in exactly the same way as geo-cuts [2] and complexbased approach in [3 1] are “dual” methods for evaluating geometric length. [sent-76, score-0.668]
22 Our grid-patch approach to curvature extends ideas in geo-cuts [2] that showed how discrete MRFbased regularization methods can use integral geometry to accurately approximate length via Cauchy-Crofton formula. [sent-77, score-0.932]
23 1(a) uses an alternative method for approximating curvature based on standard geometry as in [27, 7, 30]. [sent-81, score-0.754]
24 Our patch-based curvature models could be seen as extensions of functional lifting [4] or label elevation [21]. [sent-82, score-0.671]
25 Our patch variables include enough information about the local boundary to reduce the curvature to unary terms. [sent-85, score-0.903]
26 Their integer LP approach to curvature is formulated over a large number of binary variables defined on fine geometric primitives (vertexes, faces, edges, pairs of edges, etc), which are tied by constraints. [sent-87, score-0.709]
27 In contrast, our unary representation of curvature uses larger scale geometric primitives (overlapping patches) tied by consistency constraints. [sent-88, score-0.813]
28 Unlike [27] and us, [7, 30] represent curvature via high-order factors. [sent-90, score-0.644]
29 While integral geometry estimates curvature on a pixel grid as accurately as the standard geometry on a cell complex, see Figs. [sent-96, score-1.011]
30 Grid patches were also recently used for curvature evaluation in [28]. [sent-99, score-0.799]
31 The mathematicaljustification of this approach to curvature estimation is not fully explained and several presented plots indicate its limited accuracy. [sent-103, score-0.644]
32 As stated in [28], “the plots do also reveal the fact that we consistently overestimate the true curvature cost. [sent-104, score-0.644]
33 ” The extreme “hard” case of this method may reduce to our technique if the cost of each pattern is assigned according to our integral geometry equations in Fig. [sent-105, score-0.254]
34 Simple Patch-based Optimization One way to optimize our patch-based curvature model is to formulate the optimization problem on the original image pixel grid ? [sent-109, score-0.786]
35 We propose a different approach for optimizing our highorder curvature models that equivalently reformulates the problem on a new graph, see Fig. [sent-118, score-0.693]
36 One naive approach applicable to NP-hard highorder energies on small images is exhaustive search that enumerates all possible labelings of the underlying pixel graph. [sent-121, score-0.254]
37 If some set of relatively small overlapping patches covers all high-order factors, we can build a new graph where nodes correspond to patches (a)pixel-basedgraph(b)patch-basedgraph Figure 2: Patch-based models in Fig. [sent-123, score-0.434]
38 1, represented either on a pixel-graph with high-order interactions (a) or on a patch-graph where each patch corresponds to one node (b). [sent-124, score-0.21]
39 In (b) the curvature reduces to unary terms, but the graph includes pairwise consistency constraints due to patch overlaps. [sent-125, score-1.009]
40 Note that high-order interactions reduce to unary potentials, but, due to patch overlap, hard pair-wise consistency constraints must be enforced. [sent-128, score-0.312]
41 Our general approach transforms a high-order optimization problem to a pair-wise Constraint Satisfaction Problem with unary costs (uCSP). [sent-129, score-0.213]
42 ,W ien r geefenrteor nlo, dpeastc hine Vs i as super bneo dbeigsg. [sent-138, score-0.317]
43 ,β) Pαβ(Xα,Xβ) (3) ∈E The label Xα of a super node α corresponds to the state of all individual pixels xα within the patch. [sent-145, score-0.354]
44 By enumerating all possible pixel states within the patch we can now encode the higher order factor Eα (xα) into the unary term Uα (Xα) of (3). [sent-146, score-0.328]
45 Optimization of pairwise energy (3) can be addressed with standard methods like [13, 9] that can be modified for our specific consistency constraints to gain significant speed-up (see Sec. [sent-153, score-0.23]
46 LP relaxations When we apply method like TRW-S [13] to energy (3), we essentially solve a higher-order relaxation of the original energy (2). [sent-156, score-0.41]
47 We then argue that the complexity of message passing in our scheme roughly matches that of other techniques that solve a similar relaxation. [sent-161, score-0.212]
48 Researchers also considered alternative techniques for converting a high-order energy of binary variables into a pairwise one. [sent-167, score-0.234]
49 We will compare to one such technique, [11], which generalizes roof duality to factors of order 3 and 4. [sent-168, score-0.291]
50 Application to π/2-precision curvature In this section we illustrate our approach on a very coarse approximation of curvature where we only allow boundary edges that are either horizontal or vertical. [sent-171, score-1.34]
51 s dTehre t patches hesav ine Figure 4: Four of the 16 patch states used to encode curvature with penalties 0, π/2, 0 and 2π respectively. [sent-177, score-0.956]
52 To compute the curvature contribution of a patch we need to determine which of the 4 pixel boundaries also belong to the segmentation boundary. [sent-179, score-0.853]
53 This is done in a sliding sw oinfd soizwe 2fa s×hio 2n i,n tthoa ts uisp, super enos. [sent-194, score-0.289]
54 Each super node label can take 16 values corresponding to states of the individual pixels. [sent-196, score-0.396]
55 The curvature interaction and data terms of the original problem are now transformed to unary potentials. [sent-197, score-0.752]
56 Note that since patches are overlapping pixels can be contained in up to four super nodes. [sent-198, score-0.469]
57 In order not to change the energy we therefore weight the contribution from the original unary term, f(x) in (1), to each patch such that the total contribution is 1. [sent-199, score-0.37]
58 For simplicity we give pixels that occur k times the weight 1/k in each super node. [sent-200, score-0.32]
59 Finally to ensure that each pixel takes the same value in all the super nodes where it is contained we add the ”consistency” edges E between neighboring super nodes (see Fig. [sent-201, score-0.79]
60 Our two approaches from Figure 1 and [27, 7, 30] all assign the same curvature costs for the patches in Figure 4. [sent-204, score-0.864]
61 The messages sent during optimization has the form mtαβ(Xβ) = mXαin(Pαβ(Xα,Xβ) + h(Xα)), (4) × where h is some function of super node label Xα. [sent-209, score-0.421]
62 To compute the message we order the labels of both node α and β into (disjoint) groups according to the assignments of the shared pixels. [sent-210, score-0.242]
63 8%) (100%) (100%) · 2 curvature with different regularization weight tight lower bOouurn rde. [sent-231, score-0.764]
64 TRW-S with super nodes gives a are rreesnutlt rse gwulhaerniz using wthee ghheutr λis (titcosp proposed mfoarg speedup Win- [11]). [sent-245, score-0.353]
65 Figure 3 compares our approach for π/2-precision curvature to Generalized Roof Duality (GRD) [11]. [sent-248, score-0.644]
66 We used TRW-S [13] with 2 2 patches and our efficient message passing [sc1h3e]m weit. [sent-249, score-0.367]
67 Lower Bounds using Trees As observed in [7] the 2 2 curvature interaction reducAess t oob pairwise nin [t7e]ra tchteio 2ns × × be 2tw ceurenva atullr eth ien pixels oinn t rheepatch. [sent-253, score-0.723]
68 Therefore it could in principle be solved using roof duality (RD) [25] or TRW-S [13]. [sent-256, score-0.291]
69 ) However, it may still be useful to form super nodes. [sent-258, score-0.289]
70 Sub-trees with super nodes are in general stronger than regular trees. [sent-260, score-0.38]
71 We can foonrsmid a rsim foirla erx asumbp-tlree teh eT2 s×u2b using Tth ien super rneo (d6e)s. [sent-265, score-0.317]
72 N siomtei tahra stu tbh-ter edges that occur twice within the super nodes have half the weight of the corresponding edges in Figure 6. [sent-267, score-0.488]
73 Looking in the super nodes and considering the consistency edges we see that we can find two instances of T within T2×2 (see Figure 7) both with weights 1/2 (here tThe w edges tThat have weight 1 are allowed to belong to both trees). [sent-268, score-0.489]
74 e TIn a similar way, we can construct even stronger trees by increasing the patch size further (event though the interactions might already be contained in the patches). [sent-272, score-0.226]
75 If we group super nodes in a sliding window approach we obtain a graph with 3 3 patches, see Figure 9. [sent-273, score-0.388]
76 Figure9:Super-dupernodescontai=ni gpatchesofsize3× are ××× × created by grouping super dneosd ceos otfa nsizineg g2 p cinr a sliding gwroinudpionwg f saushpeiorn n. [sent-276, score-0.289]
77 o 2h eins groups 3of× ×23 2e In Table 1 the same problem as in Figure 3 is solved using TRW-S without forming any super nodes. [sent-277, score-0.321]
78 Application to π/4 and π/8 precision curvature For patches of size 2 2 it is only possible to encourage horFizoorn ptaatl cahneds v oefrt siiczael 2 bo×u2nd itar iises o. [sent-280, score-0.799]
79 n lInyd peoesds,i along a diagonal boundary edge all 2 2 patches look like the second patch ibno Figure e4d. [sent-281, score-0.27]
80 gTeo amlla 2k ×e th 2e p matcohdeesl more aickceu trhaete s eacnodn idnc plautdceh directions that are multiples of π/4 radians we will look at patches of a larger size, see Figure 1(c). [sent-282, score-0.267]
81 5 · -16039 -19990 10 Table 1: Same as in Figure 3 without super nodes. [sent-296, score-0.289]
82 For multiples of π/4 radians it is enough to have 3 3 patches latnidpl efosr o πf/ π8/ r4ad raiadniasn we use patches oof h saivzee 53 53. [sent-297, score-0.422]
83 To compute the specific label costs we generate representative windows of size slightly larger than the patch (for 3 3 patches we use 5 5 windows) that contain either a straight lhinees or a tera 5ns ×iti 5on w ibnedtwoweesn) thwaot doinrteacitnio neist eofr known angle difference. [sent-300, score-0.391]
84 From this window we can determine which super node assignments occur in the vicinity of different transitions. [sent-301, score-0.416]
85 We extract all the assignments and constrain their sum, as shown in Figure 1, to be the known curvature of the window. [sent-302, score-0.702]
86 Note that all methods except GTRWS use our super node construction, here we use the single separator implementation [14]. [sent-316, score-0.327]
87 Thus, GTRW-S solves a weaker relaxation of the energy (this is confirmed by the numbers in Table 2). [sent-317, score-0.219]
88 For the patch assignments that we do not use to model curvature we specify a large cost (1000) to ensure that these are not selected. [sent-319, score-0.817]
89 For MPLP [29] we allow 10,000 iterations of clustering and we stop running if the duality gap is less than 10−4. [sent-324, score-0.31]
90 Figure 11: ×× × × Logarithmic over time for the 2 time plot for energy and lower bound 2 experiment in Table 2. [sent-326, score-0.266]
91 9 Lower bound Time (s) Energy Lower bound Time (s) Energy Lower bound Time (s) 1749. [sent-334, score-0.228]
92 Other Applications × × Our framework does not only work for curvature but applies to a general class of problems. [sent-354, score-0.644]
93 In this section we will test our partial enumeration approach for other problems than curvature regularization. [sent-355, score-0.834]
94 In contrast (e) shows the solution obtained when forming super nodes with patches of size 3 3 and then applying TRW-S. [sent-364, score-0.54]
95 To compute the move [34] first reduces the interactions (using auxiliary nodes) and applies Roof duality (RD) [25]. [sent-375, score-0.278]
96 pSaitncchee tsh oef fin sitzeera 3cti ×on 3s, wthialtl occur in as many as three super nodes we weight these so that the energy does not change. [sent-377, score-0.531]
97 We also tested the ”improve” heuristic [25] which gave a reduction in duality gap for RD. [sent-381, score-0.281]
98 Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations. [sent-500, score-0.212]
99 A linear framework for region-based image segmentation and inpainting involving curvature penalization. [sent-617, score-0.717]
100 Revisiting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction. [sent-652, score-0.219]
wordName wordTfidf (topN-words)
[('curvature', 0.644), ('super', 0.289), ('duality', 0.197), ('patches', 0.155), ('enumeration', 0.152), ('energy', 0.147), ('message', 0.146), ('energies', 0.126), ('ucsp', 0.115), ('patch', 0.115), ('unary', 0.108), ('integral', 0.101), ('satisfaction', 0.094), ('roof', 0.094), ('gap', 0.084), ('regularization', 0.077), ('bound', 0.076), ('mplp', 0.075), ('rd', 0.075), ('relaxation', 0.072), ('multiples', 0.071), ('geometry', 0.07), ('grid', 0.07), ('grd', 0.069), ('transations', 0.069), ('passing', 0.066), ('costs', 0.065), ('nodes', 0.064), ('assignments', 0.058), ('interactions', 0.057), ('globerson', 0.053), ('mrf', 0.053), ('edges', 0.052), ('pairwise', 0.051), ('deconvolution', 0.051), ('geman', 0.051), ('highorder', 0.049), ('stereo', 0.048), ('functionals', 0.047), ('labelings', 0.047), ('complexes', 0.046), ('meltzer', 0.046), ('mrfbased', 0.046), ('olsson', 0.046), ('relaxations', 0.044), ('technique', 0.044), ('lower', 0.043), ('convergent', 0.042), ('states', 0.042), ('inpainting', 0.041), ('yuri', 0.041), ('radians', 0.041), ('trws', 0.041), ('masnou', 0.041), ('boykov', 0.04), ('approximating', 0.04), ('optimization', 0.04), ('discrete', 0.04), ('pattern', 0.039), ('intelligence', 0.039), ('node', 0.038), ('partial', 0.038), ('canadian', 0.038), ('csp', 0.038), ('maths', 0.038), ('variables', 0.036), ('woodford', 0.036), ('graph', 0.035), ('vertex', 0.034), ('consistency', 0.032), ('forming', 0.032), ('segmentation', 0.032), ('pixel', 0.032), ('disparity', 0.031), ('arxiv', 0.031), ('enumerating', 0.031), ('occur', 0.031), ('kahl', 0.03), ('symmetries', 0.03), ('boundaries', 0.03), ('lp', 0.03), ('tied', 0.029), ('windows', 0.029), ('running', 0.029), ('formulations', 0.029), ('kolmogorov', 0.029), ('ien', 0.028), ('triple', 0.027), ('stronger', 0.027), ('trees', 0.027), ('label', 0.027), ('messages', 0.027), ('gibbs', 0.026), ('siam', 0.026), ('lth', 0.025), ('overlapping', 0.025), ('cell', 0.024), ('evaluating', 0.024), ('ul', 0.024), ('reduces', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999869 309 iccv-2013-Partial Enumeration and Curvature Regularization
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
2 0.4370375 389 iccv-2013-Shortest Paths with Curvature and Torsion
Author: Petter Strandmark, Johannes Ulén, Fredrik Kahl, Leo Grady
Abstract: This paper describes a method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our globally optimal method uses line graphs and its runtime is polynomial in the size of the discretization, often in the order of seconds on a single computer. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have almost one hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of regularization based on curvature while torsion is still only tractable for small-scale problems.
3 0.41162744 296 iccv-2013-On the Mean Curvature Flow on Graphs with Applications in Image and Manifold Processing
Author: Abdallah El_Chakik, Abderrahim Elmoataz, Ahcene Sadi
Abstract: In this paper, we propose an adaptation and transcription of the mean curvature level set equation on a general discrete domain (weighted graphs with arbitrary topology). We introduce the perimeters on graph using difference operators and define the curvature as the first variation of these perimeters. Our proposed approach of mean curvature unifies both local and non local notions of mean curvature on Euclidean domains. Furthermore, it allows the extension to the processing of manifolds and data which can be represented by graphs.
4 0.21042807 100 iccv-2013-Curvature-Aware Regularization on Riemannian Submanifolds
Author: Kwang In Kim, James Tompkin, Christian Theobalt
Abstract: One fundamental assumption in object recognition as well as in other computer vision and pattern recognition problems is that the data generation process lies on a manifold and that it respects the intrinsic geometry of the manifold. This assumption is held in several successful algorithms for diffusion and regularization, in particular, in graph-Laplacian-based algorithms. We claim that the performance of existing algorithms can be improved if we additionally account for how the manifold is embedded within the ambient space, i.e., if we consider the extrinsic geometry of the manifold. We present a procedure for characterizing the extrinsic (as well as intrinsic) curvature of a manifold M which is described by a sampled point cloud in a high-dimensional Euclidean space. Once estimated, we use this characterization in general diffusion and regularization on M, and form a new regularizer on a point cloud. The resulting re-weighted graph Laplacian demonstrates superior performance over classical graph Laplacian in semisupervised learning and spectral clustering.
5 0.12620306 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
6 0.10716303 429 iccv-2013-Tree Shape Priors with Connectivity Constraints Using Convex Relaxation on General Graphs
7 0.10459989 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
8 0.092508189 186 iccv-2013-GrabCut in One Cut
9 0.087329134 317 iccv-2013-Piecewise Rigid Scene Flow
10 0.086507075 42 iccv-2013-Active MAP Inference in CRFs for Efficient Semantic Segmentation
11 0.083298855 394 iccv-2013-Single-Patch Low-Rank Prior for Non-pointwise Impulse Noise Removal
12 0.082767949 387 iccv-2013-Shape Anchors for Data-Driven Multi-view Reconstruction
13 0.082621604 101 iccv-2013-DCSH - Matching Patches in RGBD Images
14 0.075607672 156 iccv-2013-Fast Direct Super-Resolution by Simple Functions
15 0.073828667 144 iccv-2013-Estimating the 3D Layout of Indoor Scenes and Its Clutter from Depth Sensors
16 0.073062025 264 iccv-2013-Minimal Basis Facility Location for Subspace Segmentation
17 0.07236439 104 iccv-2013-Decomposing Bag of Words Histograms
18 0.071872383 132 iccv-2013-Efficient 3D Scene Labeling Using Fields of Trees
19 0.07042399 300 iccv-2013-Optical Flow via Locally Adaptive Fusion of Complementary Data Costs
20 0.070074014 237 iccv-2013-Learning Graph Matching: Oriented to Category Modeling from Cluttered Scenes
topicId topicWeight
[(0, 0.18), (1, -0.079), (2, -0.03), (3, -0.01), (4, -0.004), (5, 0.061), (6, -0.073), (7, -0.007), (8, 0.052), (9, -0.177), (10, -0.092), (11, 0.042), (12, 0.011), (13, 0.1), (14, 0.143), (15, 0.116), (16, -0.037), (17, -0.072), (18, -0.029), (19, -0.023), (20, 0.054), (21, 0.105), (22, 0.034), (23, -0.142), (24, 0.027), (25, 0.156), (26, -0.129), (27, -0.177), (28, 0.171), (29, -0.001), (30, -0.353), (31, -0.094), (32, 0.018), (33, 0.056), (34, -0.07), (35, -0.257), (36, -0.046), (37, -0.011), (38, -0.032), (39, 0.088), (40, -0.095), (41, 0.017), (42, -0.115), (43, -0.012), (44, -0.038), (45, -0.028), (46, -0.079), (47, 0.085), (48, -0.013), (49, 0.062)]
simIndex simValue paperId paperTitle
same-paper 1 0.95517749 309 iccv-2013-Partial Enumeration and Curvature Regularization
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
2 0.94195604 389 iccv-2013-Shortest Paths with Curvature and Torsion
Author: Petter Strandmark, Johannes Ulén, Fredrik Kahl, Leo Grady
Abstract: This paper describes a method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our globally optimal method uses line graphs and its runtime is polynomial in the size of the discretization, often in the order of seconds on a single computer. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have almost one hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of regularization based on curvature while torsion is still only tractable for small-scale problems.
3 0.90238643 296 iccv-2013-On the Mean Curvature Flow on Graphs with Applications in Image and Manifold Processing
Author: Abdallah El_Chakik, Abderrahim Elmoataz, Ahcene Sadi
Abstract: In this paper, we propose an adaptation and transcription of the mean curvature level set equation on a general discrete domain (weighted graphs with arbitrary topology). We introduce the perimeters on graph using difference operators and define the curvature as the first variation of these perimeters. Our proposed approach of mean curvature unifies both local and non local notions of mean curvature on Euclidean domains. Furthermore, it allows the extension to the processing of manifolds and data which can be represented by graphs.
4 0.69000459 100 iccv-2013-Curvature-Aware Regularization on Riemannian Submanifolds
Author: Kwang In Kim, James Tompkin, Christian Theobalt
Abstract: One fundamental assumption in object recognition as well as in other computer vision and pattern recognition problems is that the data generation process lies on a manifold and that it respects the intrinsic geometry of the manifold. This assumption is held in several successful algorithms for diffusion and regularization, in particular, in graph-Laplacian-based algorithms. We claim that the performance of existing algorithms can be improved if we additionally account for how the manifold is embedded within the ambient space, i.e., if we consider the extrinsic geometry of the manifold. We present a procedure for characterizing the extrinsic (as well as intrinsic) curvature of a manifold M which is described by a sampled point cloud in a high-dimensional Euclidean space. Once estimated, we use this characterization in general diffusion and regularization on M, and form a new regularizer on a point cloud. The resulting re-weighted graph Laplacian demonstrates superior performance over classical graph Laplacian in semisupervised learning and spectral clustering.
5 0.4924342 429 iccv-2013-Tree Shape Priors with Connectivity Constraints Using Convex Relaxation on General Graphs
Author: Jan Stühmer, Peter Schröder, Daniel Cremers
Abstract: We propose a novel method to include a connectivity prior into image segmentation that is based on a binary labeling of a directed graph, in this case a geodesic shortest path tree. Specifically we make two contributions: First, we construct a geodesic shortest path tree with a distance measure that is related to the image data and the bending energy of each path in the tree. Second, we include a connectivity prior in our segmentation model, that allows to segment not only a single elongated structure, but instead a whole connected branching tree. Because both our segmentation model and the connectivity constraint are convex, a global optimal solution can be found. To this end, we generalize a recent primal-dual algorithm for continuous convex optimization to an arbitrary graph structure. To validate our method we present results on data from medical imaging in angiography and retinal blood vessel segmentation.
6 0.40914038 324 iccv-2013-Potts Model, Parametric Maxflow and K-Submodular Functions
7 0.35091403 408 iccv-2013-Super-resolution via Transform-Invariant Group-Sparse Regularization
8 0.3365483 312 iccv-2013-Perceptual Fidelity Aware Mean Squared Error
10 0.32090947 421 iccv-2013-Total Variation Regularization for Functions with Values in a Manifold
11 0.3085331 171 iccv-2013-Fix Structured Learning of 2013 ICCV paper k2opt.pdf
12 0.29129767 88 iccv-2013-Constant Time Weighted Median Filtering for Stereo Matching and Beyond
13 0.28970078 98 iccv-2013-Cross-Field Joint Image Restoration via Scale Map
14 0.27544379 215 iccv-2013-Incorporating Cloud Distribution in Sky Representation
16 0.27050856 42 iccv-2013-Active MAP Inference in CRFs for Efficient Semantic Segmentation
17 0.2701512 394 iccv-2013-Single-Patch Low-Rank Prior for Non-pointwise Impulse Noise Removal
18 0.26853696 200 iccv-2013-Higher Order Matching for Consistent Multiple Target Tracking
19 0.2668398 329 iccv-2013-Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
20 0.26564115 63 iccv-2013-Bounded Labeling Function for Global Segmentation of Multi-part Objects with Geometric Constraints
topicId topicWeight
[(2, 0.06), (7, 0.021), (26, 0.123), (27, 0.013), (31, 0.053), (34, 0.016), (40, 0.023), (42, 0.104), (48, 0.017), (64, 0.029), (73, 0.04), (87, 0.208), (89, 0.178)]
simIndex simValue paperId paperTitle
same-paper 1 0.84965277 309 iccv-2013-Partial Enumeration and Curvature Regularization
Author: Carl Olsson, Johannes Ulén, Yuri Boykov, Vladimir Kolmogorov
Abstract: Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. This partial enumeration technique reduces complex highorder energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. Our main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach. 1
2 0.78838724 330 iccv-2013-Proportion Priors for Image Sequence Segmentation
Author: Claudia Nieuwenhuis, Evgeny Strekalovskiy, Daniel Cremers
Abstract: We propose a convex multilabel framework for image sequence segmentation which allows to impose proportion priors on object parts in order to preserve their size ratios across multiple images. The key idea is that for strongly deformable objects such as a gymnast the size ratio of respective regions (head versus torso, legs versus full body, etc.) is typically preserved. We propose different ways to impose such priors in a Bayesian framework for image segmentation. We show that near-optimal solutions can be computed using convex relaxation techniques. Extensive qualitative and quantitative evaluations demonstrate that the proportion priors allow for highly accurate segmentations, avoiding seeping-out of regions and preserving semantically relevant small-scale structures such as hands or feet. They naturally apply to multiple object instances such as players in sports scenes, and they can relate different objects instead of object parts, e.g. organs in medical imaging. The algorithm is efficient and easily parallelized leading to proportion-consistent segmentations at runtimes around one second.
3 0.77029979 156 iccv-2013-Fast Direct Super-Resolution by Simple Functions
Author: Chih-Yuan Yang, Ming-Hsuan Yang
Abstract: The goal of single-image super-resolution is to generate a high-quality high-resolution image based on a given low-resolution input. It is an ill-posed problem which requires exemplars or priors to better reconstruct the missing high-resolution image details. In this paper, we propose to split the feature space into numerous subspaces and collect exemplars to learn priors for each subspace, thereby creating effective mapping functions. The use of split input space facilitates both feasibility of using simple functionsfor super-resolution, and efficiency ofgenerating highresolution results. High-quality high-resolution images are reconstructed based on the effective learned priors. Experimental results demonstrate that theproposed algorithmperforms efficiently and effectively over state-of-the-art methods.
4 0.75952703 150 iccv-2013-Exemplar Cut
Author: Jimei Yang, Yi-Hsuan Tsai, Ming-Hsuan Yang
Abstract: We present a hybrid parametric and nonparametric algorithm, exemplar cut, for generating class-specific object segmentation hypotheses. For the parametric part, we train a pylon model on a hierarchical region tree as the energy function for segmentation. For the nonparametric part, we match the input image with each exemplar by using regions to obtain a score which augments the energy function from the pylon model. Our method thus generates a set of highly plausible segmentation hypotheses by solving a series of exemplar augmented graph cuts. Experimental results on the Graz and PASCAL datasets show that the proposed algorithm achievesfavorable segmentationperformance against the state-of-the-art methods in terms of visual quality and accuracy.
5 0.75783777 414 iccv-2013-Temporally Consistent Superpixels
Author: Matthias Reso, Jörn Jachalsky, Bodo Rosenhahn, Jörn Ostermann
Abstract: Superpixel algorithms represent a very useful and increasingly popular preprocessing step for a wide range of computer vision applications, as they offer the potential to boost efficiency and effectiveness. In this regards, this paper presents a highly competitive approach for temporally consistent superpixelsfor video content. The approach is based on energy-minimizing clustering utilizing a novel hybrid clustering strategy for a multi-dimensional feature space working in a global color subspace and local spatial subspaces. Moreover, a new contour evolution based strategy is introduced to ensure spatial coherency of the generated superpixels. For a thorough evaluation the proposed approach is compared to state of the art supervoxel algorithms using established benchmarks and shows a superior performance.
6 0.75701892 196 iccv-2013-Hierarchical Data-Driven Descent for Efficient Optimal Deformation Estimation
7 0.75498295 95 iccv-2013-Cosegmentation and Cosketch by Unsupervised Learning
8 0.75331831 326 iccv-2013-Predicting Sufficient Annotation Strength for Interactive Foreground Segmentation
9 0.7528832 8 iccv-2013-A Deformable Mixture Parsing Model with Parselets
10 0.75216013 295 iccv-2013-On One-Shot Similarity Kernels: Explicit Feature Maps and Properties
11 0.75214005 102 iccv-2013-Data-Driven 3D Primitives for Single Image Understanding
12 0.75168449 258 iccv-2013-Low-Rank Sparse Coding for Image Classification
13 0.75137699 245 iccv-2013-Learning a Dictionary of Shape Epitomes with Applications to Image Labeling
14 0.75043863 411 iccv-2013-Symbiotic Segmentation and Part Localization for Fine-Grained Categorization
15 0.74991089 6 iccv-2013-A Convex Optimization Framework for Active Learning
16 0.7498554 21 iccv-2013-A Method of Perceptual-Based Shape Decomposition
17 0.74977481 137 iccv-2013-Efficient Salient Region Detection with Soft Image Abstraction
18 0.74976099 329 iccv-2013-Progressive Multigrid Eigensolvers for Multiscale Spectral Segmentation
19 0.74968827 349 iccv-2013-Regionlets for Generic Object Detection
20 0.74919957 376 iccv-2013-Scene Text Localization and Recognition with Oriented Stroke Detection