| 1. |
- Fredriksson, Johan, et al.
(författare)
-
Tighter Relaxations for Higher-Order Models based on Generalized Roof Duality
- 2012
-
Ingår i: Lecture Notes in Computer Science (Computer Vision - ECCV 2012. Workshops and Demonstrations, Florence, Italy, October 7-13, 2012, Proceedings, Part III). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783642338854 - 9783642338847 ; 7585, s. 273-282
-
Konferensbidrag (refereegranskat)abstract
- Many problems in computer vision can be turned into a large-scale boolean optimization problem, which is in general NP-hard. In this paper, we further develop one of the most successful approaches, namely roof duality, for approximately solving such problems for higher-order models. Two new methods that can be applied independently or in combination are investigated. The first one is based on constructing relaxations using generators of the submodular function cone. In the second method, it is shown that the roof dual bound can be applied in an iterated way in order to obtain a tighter relaxation. We also provide experimental results that demonstrate better performance with respect to the state-of-the-art, both in terms of improved bounds and the number of optimally assigned variables.
|
|
| 2. |
- Kahl, Fredrik, et al.
(författare)
-
Generalized roof duality
- 2012
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 1872-6771 .- 0166-218X. ; 160:16-17, s. 2419-2434
-
Tidskriftsartikel (refereegranskat)abstract
- The roof dual bound for quadratic unconstrained binary optimization is the basis for several methods for efficiently computing the solution to many hard combinatorial problems. It works by constructing the tightest possible lower-bounding submodular function, and instead of minimizing the original objective function, the relaxation is minimized. However, for higher-order problems the technique has been less successful. A standard technique is to first reduce the problem into a quadratic one by introducing auxiliary variables and then apply the quadratic roof dual bound, but this may lead to loose bounds. We generalize the roof duality technique to higher-order optimization problems. Similarly to the quadratic case, optimal relaxations are defined to be the ones that give the maximum lower bound. We show how submodular relaxations can efficiently be constructed in order to compute the generalized roof dual bound for general cubic and quartic pseudo-boolean functions. Further, we prove that important properties such as persistency still hold, which allows us to determine optimal values for some of the variables. From a practical point of view, we experimentally demonstrate that the technique outperforms the state of the art for a wide range of applications, both in terms of lower bounds and in the number of assigned variables. (C) 2012 Elsevier B.V. All rights reserved.
|
|
| 3. |
- Kahl, Fredrik, et al.
(författare)
-
Generalized Roof Duality for Pseudo-Boolean Optimization
- 2011
-
Ingår i: IEEE International Conference on Computer Vision (ICCV). ; , s. 255-262
-
Konferensbidrag (refereegranskat)abstract
- The number of applications in computer vision that model higher-order interactions has exploded over the last few years. The standard technique for solving such problems is to reduce the higher-order objective function to a quadratic pseudo-boolean function, and then use roof duality for obtaining a lower bound. Roof duality works by constructing the tightest possible lower-bounding submodular function, and instead of optimizing the original objective function, the relaxation is minimized. We generalize this idea to polynomials of higher degree, where quadratic roof duality appears as a special case. Optimal relaxations are defined to be the ones that give the maximum lower bound. We demonstrate that important properties such as persistency still hold and how the relaxations can be efficiently constructed for general cubic and quartic pseudo-boolean functions. From a practical point of view, we show that our relaxations perform better than state-of-the-art for a wide range of problems, both in terms of lower bounds and in the number of assigned variables.
|
|
| 4. |
- Strandmark, Petter, et al.
(författare)
-
Curvature Regularization for Curves and Surfaces in a Global Optimization Framework
- 2011
-
Ingår i: Lecture Notes in Computer Science.
-
Konferensbidrag (refereegranskat)abstract
- Length and area regularization are commonplace for inverse problems today. It has however turned out to be much more difficult to incorporate a curvature prior. In this paper we propose several improvements to a recently proposed framework based on global optimization. We identify and solve an issue with extraneous arcs in the original formulation by introducing region consistency constraints. The mesh geometry is analyzed both from a theoretical and experimental viewpoint and hexagonal meshes are shown to be superior. We demonstrate that adaptively generated meshes significantly improve the performance. Our final contribution is that we generalize the framework to handle mean curvature regularization for 3D surface completion and segmentation.
|
|
| 5. |
- Strandmark, Petter
(författare)
-
Discrete Optimization in Early Vision - Model Tractability Versus Fidelity
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Early vision is the process occurring before any semantic interpretation of an image takes place. Motion estimation, object segmentation and detection are all parts of early vision, but recognition is not. Some models in early vision are easy to perform inference with---they are tractable. Others describe the reality well---they have high fidelity. This thesis improves the tractability-fidelity trade-off of the current state of the art by introducing new discrete methods for image segmentation and other problems of early vision. The first part studies pseudo-boolean optimization, both from a theoretical perspective as well as a practical one by introducing new algorithms. The main result is the generalization of the roof duality concept to polynomials of higher degree than two. Another focus is parallelization; discrete optimization methods for multi-core processors, computer clusters, and graphical processing units are presented. Remaining in an image segmentation context, the second part studies parametric problems where a set of model parameters and a segmentation are estimated simultaneously. For a small number of parameters these problems can still be optimally solved. One application is an optimal method for solving the two-phase Mumford-Shah functional. The third part shifts the focus to curvature regularization---where the commonly used length and area penalization is replaced by curvature in two and three dimensions. These problems can be discretized over a mesh and special attention is given to the mesh geometry. Specifically, hexagonal meshes in the plane are compared to square ones and a method for generating adaptive meshes is introduced and evaluated. The framework is then extended to curvature regularization of surfaces. Finally, the thesis is concluded by three applications to early vision problems: cardiac MRI segmentation, image registration, and cell classification.
|
|
| 6. |
- Strandmark, Petter
(författare)
-
Early Vision Optimization: Parametric Models, Parallelization and Curvature
- 2010
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Early vision is the process occurring before any semantic interpretation of an image takes place. Motion estimation, object segmentation and detection are all parts of early vision, but recognition is not. Many of these tasks are formulated as optimization problems and one of the key factors for the success of recent methods is that they seek to compute globally optimal solutions. This thesis is concerned with improving the efficiency and extending the applicability of the current state of the art. This is achieved by introducing new methods of computing solutions to image segmentation and other problems of early vision. The first part studies parametric problems where model parameters are estimated in addition to an image segmentation. For a small number of parameters these problems can still be solved optimally. In the second part the focus is shifted toward curvature regularization, i.e. when the commonly used length and area regularization is replaced by curvature in two and three dimensions. These problems can be discretized over a mesh and special attention is given to the mesh geometry. Specifically, hexagonal meshes are compared to square ones and a method for generating adaptive methods is introduced and evaluated. The framework is then extended to curvature regularization of surfaces. Thirdly, fast methods for finding minimal graph cuts and solving related problems on modern parallel hardware are developed and extensively evaluated. Finally, the thesis is concluded with two applications to early vision problems: heart segmentation and image registration.
|
|
| 7. |
- Strandmark, Petter, et al.
(författare)
-
HEp-2 Staining Pattern Classification
- 2012
-
Ingår i: Pattern Recognition (ICPR), 2012 21st International Conference on. - 9781467322164
-
Konferensbidrag (refereegranskat)abstract
- Classifying images of HEp-2 cells from indirect immunofluorescence has important clinical applications. We have developed an automatic method based on random forests that classifies an HEp-2 cell image into one of six classes. The method is applied to the data set of the ICPR 2012 contest. The previously obtained best accuracy is 79.3% for this data set, whereas we obtain an accuracy of 97.4%. The key to our result is due to carefully designed feature descriptors for multiple level sets of the image intensity. These features characterize both the appearance and the shape of the cell image in a robust manner.
|
|
| 8. |
- Strandmark, Petter, et al.
(författare)
-
Joint Random Sample Consensus and Multiple Motion Models for Robust Video Tracking
- 2009
-
Ingår i: Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 5575/2009, s. 450-459:5575, s. 450-459
-
Konferensbidrag (refereegranskat)abstract
- We present a novel method for tracking multiple objects in video captured by a non-stationary camera. For low quality video, RANSAC estimation fails when the number of good matches shrinks below the minimum required to estimate the motion model. This paper extends RANSAC in the following ways: (a) Allowing multiple models of different complexity to be chosen at random; (b) Introducing a conditional probability to measure the suitability of each transformation candidate, given the object locations in previous frames; (c) Determining the best suitable transformation by the number of consensus points, the probability and the model complexity. Our experimental results have shown that the proposed estimation method better handles video of low quality and that it is able to track deformable objects with pose changes, occlusions, motion blur and overlap. We also show that using multiple models of increasing complexity is more effective than just using RANSAC with the complex model only.
|
|
| 9. |
- Strandmark, Petter, et al.
(författare)
-
Optimal Levels for the Two-phase, Piecewise Constant Mumford-Shah Functional
- 2009
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- Recent results have shown that denoising an image with the Rudin, Osher and Fatemi (ROF) total variation model can be accomplished by solving a series of binary optimization problems. We observe that this fact can be used in the other direction. The procedure is applied to the two-phase, piecewise constant Mumford-Shah functional, where an image is approximated with a function taking only two values. When the difference between the two levels is kept constant, a global optimum can be found efficiently. This allows us to solve the full problem with branch and bound in only one dimension.
|
|
| 10. |
- Strandmark, Petter, et al.
(författare)
-
Optimizing Parametric Total Variation Models
- 2009
-
Ingår i: [Host publication title missing]. ; , s. 2240-2247
-
Konferensbidrag (refereegranskat)abstract
- One of the key factors for the success of recent energy minimization methods is that they seek to compute global solutions. Even for non-convex energy functionals, optimization methods such as graph cuts have proven to produce high-quality solutions by iterative minimization based on large neighborhoods, making them less vulnerable to local minima. Our approach takes this a step further by enlarging the search neighborhood with one dimension. In this paper we consider binary total variation problems that depend on an additional set of parameters. Examples include: (i) the Chan-Vese model that we solve globally (ii) ratio and constrained minimization which can be formulated as parametric problems, and (iii) variants of the Mumford-Shah functional. Our approach is based on a recent theorem of Chambolle which states that solving a one-parameter family of binary problems amounts to solving a single convex variational problem. We prove a generalization of this result and show how it can be applied to parametric optimization.
|
|
