Solving Dense Image Matching in Real-Time using Discrete-Continuous Optimization
6
Citation
0
Reference
20
Related Paper
Citation Trend
Abstract:
Dense image matching is a fundamental low-level problem in Computer Vision, which has received tremendous attention from both discrete and continuous optimization communities. The goal of this paper is to combine the advantages of discrete and continuous optimization in a coherent framework. We devise a model based on energy minimization, to be optimized by both discrete and continuous algorithms in a consistent way. In the discrete setting, we propose a novel optimization algorithm that can be massively parallelized. In the continuous setting we tackle the problem of non-convex regularizers by a formulation based on differences of convex functions. The resulting hybrid discrete-continuous algorithm can be efficiently accelerated by modern GPUs and we demonstrate its real-time performance for the applications of dense stereo matching and optical flow.Keywords:
Discrete optimization
Minification
Optical Flow
Cite
Algorithms for discrete energy minimization are of fundamental importance in computer vision. In this paper, we focus on the recent technique proposed by Wainwright et al. [33]--tree-reweighted max-product message passing (TRW). It was inspired by the problem of maximizing a lower bound on the energy. However, the algorithm is not guaranteed to increase this bound--it may actually go down. In addition, TRW does not always converge. We develop a modification of this algorithm which we call sequential tree-reweighted message passing. Its main property is that the bound is guaranteed not to decrease. We also give a weak tree agreement condition which characterizes local maxima of the bound with respect to TRW algorithms. We prove that our algorithm has a limit point that achieves weak tree agreement. Finally, we show that, our algorithm requires half as much memory as traditional message passing approaches. Experimental results demonstrate that on certain synthetic and real problems, our algorithm outperforms both the ordinary belief propagation and tree-reweighted algorithm in [33]. In addition, on stereo problems with Potts interactions, we obtain a lower energy than graph cuts.
Tree (set theory)
Belief Propagation
Energy minimization
k-minimum spanning tree
Cite
Citations (1,150)
All known solutions of the shape based segmentation problem are slower than real-time application requirements. In this paper, the problem is formulated as a global optimization problem for an energy objective function with several constraints. This formulation allows the use of the global optimization solvers as a solution. However, this solution will be slow as it requires the evaluation of the objective function for several thousand times. The objective function computation is one of the critical factors that affect the time needed to reach a solution. The authors implemented two accelerated parallel versions of the solution that integrates the objective function and the pattern search solver. The first uses a GPU accelerated implementation of the objective function and the second uses a CPU parallel version which is executed on several processors/cores. The results of the proposed solution show that the GPU version has substantial speed compared to other approaches.
Solver
Pattern search
Speedup
Cite
Citations (2)
Abstract : As part of an extended research project on the parallel decomposition of linear programs, a parallel algorithm for Staircase Linear Programs was designed and implemented. This class of problems encompasses a large range of planning problems and when decomposed has simple subproblem formulations and communication patterns. This makes its solution a manageable step toward our eventual goal of producing a general code that automatically exploits problem structures of various forms. The results presented here were derived from an implementation for a Sequent Balance 8000 shared-memory multiprocessor. The algorithm itself is message-based but can run on either shared-or distributed-memory parallel computers. A simple diet planning problem is used to demonstrate the principles of the algorithm's development and performance. When applied to this problem, the parallel decomposition algorithm shows promise relative to present serial optimization codes. The nonlinear optimization code MINOS 5.1 is used both as a basis for comparison and as a generic subproblem solver. The greatest room for speedup is in exploiting problem structures. The results show that decomposition can improve efficiency even with a single processor. Examples are given where multiple processors lead to greater efficiency.
Cite
Citations (5)
Techniques for mapping image processing and computer vision algorithms onto a class of hierarchically structured systems are presented. In order to produce mappings of maximum efficiency, objective functions that measure the quality of given mappings with respect to particular optimization goals are proposed. The effectiveness and the computation complexity of mapping algorithms that yield very high performance by minimizing the objective functions are discussed. Performance results are also presented.< >
Cite
Citations (0)
Regularization
Cite
Citations (10)
We propose a parallel and distributed algorithm for solving discrete labeling problems in large scale random fields. Our approach is motivated by the following observations: i) very large scale image and video processing problems, such as labeling dozens of million pixels with thousands of labels, are routinely faced in many application domains; ii) the computational complexity of the current state-of-the-art inference algorithms makes them impractical to solve such large scale problems; iii) modern parallel and distributed systems provide high computation power at low cost. At the core of our algorithm is a tree-based decomposition of the original optimization problem which is solved using a non convex form of the method of alternating direction method of multipliers (ADMM). This allows efficient parallel solving of resulting sub-problems. We evaluate the efficiency and accuracy offered by our algorithm on several benchmark lowlevel vision problems, on both CPU and Nvidia GPU. We consistently achieve a factor of speed-up compared to dual decomposition (DD) approach and other ADMM-based approaches.
Benchmark (surveying)
Approximate inference
Cite
Citations (19)
This paper presents a new static and dynamic recursive parallel algorithm for the convex hull problem. This algorithm is a parallel adaptation of the Graham Scan and Quick Hull algorithms. The computational model selected for this algorithm is the associative computing model (ASC) which supports massive parallelism through the use of data parallelism and constant time associative search and maximum functions. Also, ASC can be supported on existing SIMD computers. The static algorithm requires O(n) space, O(log n) average case running time, and O(n) worst case running time. If O(log n) ISs are used the, static algorithm should have an average running time of O(log log n).
Output-sensitive algorithm
SIMD
Associative property
Cite
Citations (8)
We present a new algorithmic framework which enables making a full use of the large potential of data parallelism available on 2D processor arrays for the implementation of nonlinear multigrid relaxation methods. This framework leads to fast convergence towards quasi-optimal solutions. It is demonstrated on two different low-level vision applications.< >
Multigrid method
Markov random field
Cite
Citations (0)
Minification
Popularity
Energy minimization
Cite
Citations (4)
Solver
Matrix (chemical analysis)
Cite
Citations (16)