1Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs

Karteek Alahari

Description

Niveau: Supérieur, Doctorat, Bac+8
1Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs Karteek Alahari, Student Member, IEEE, Pushmeet Kohli, Member, IEEE, and Philip H. S. Torr, Senior Member, IEEE Abstract—In this paper, we present novel techniques that improve the computational and memory efficiency of algorithms for solving multi-label energy functions arising from discrete MRFs or CRFs. These methods are motivated by the observations that the performance of minimization algorithms depends on: (a) the initialization used for the primal and dual variables; and (b) the number of primal variables involved in the energy function. Our first method (dynamic ?-expansion) works by ‘recycling' results from previous problem instances. The second method simplifies the energy function by ‘reducing' the number of unknown variables present in the problem. Further, we show that it can also be used to generate a good initialization for the dynamic ?-expansion algorithm by ‘reusing' dual variables. We test the performance of our methods on energy functions encountered in the problems of stereo matching, and colour and object based segmentation. Experimental results show that our methods achieve a substantial improvement in the performance of ?-expansion, as well as other popular algorithms such as sequential tree-reweighted message passing, and max-product belief propagation. We also demonstrate the applicability of our schemes for certain higher order energy functions, such as the one described in [1], for interactive texture based image and video segmentation.

• multi-label energy


• algorithm


• procedure can


• all neighbours


• using all


• algorithms


• energy functions


• belled using

Sujets

• Oxford Brookes University
• Microsoft
• Algorithm

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 15
• Langue: English

Extrait

1

Dynamic Hybrid Algorithms for MAP Inference in Discrete MRFs Karteek Alahari, Student Member, IEEE, Pushmeet Kohli, Member, IEEE, and Philip H. S. Torr, Senior Member, IEEE

Abstract —Inthispaper,wepresentnoveltechniquesthatimprovethecomputationalandmemoryefciencyofalgorithmsforsolving multi-label energy functions arising from discrete MRF s or C RF s. These methods are motivated by the observations that the performance of minimization algorithms depends on: (a) the initialization used for the primal and dual variables; and (b) the number of primal variables involved in the energy function. Our rst method (dynamic α -expansion) works by `recycling' results from previous problem instances. The second method simplies the energy function by `reducing' the number of unknown variables present in the problem. Further, we show that it can also be used to generate a good initialization for the dynamic α -expansion algorithm by `reusing' dual variables. We test the performance of our methods on energy functions encountered in the problems of stereo matching, and colour and object based segmentation. Experimental results show that our methods achieve a substantial improvement in the performance of α -expansion, as well as other popular algorithms such as sequential tree-reweighted message passing, and max-product belief propagation. We also demonstrate the applicability of our schemes for certain higher order energy functions, such as the one described in [1], for interactive texture based image and video segmentation. In most cases we achieve a 10-15 times speed-up in the computation time. Our modied α -expansion algorithm provides similar performance to Fast-PD [2], but is conceptually much simpler. Both α - expansion and Fast-PD can be made orders of magnitude faster when used in conjunction with the `reduce' scheme proposed in this paper. Index Terms —Markov Random Fields, Multi-label Problems, Energy Minim ization, Approximate Algorithms. F

1 I NTRODUCTION ing these functions. They have been shown to give excel- M ANY problemsincomputervisionsuchasimage l c v e o is n n i t s o i r n d e e s [ r u 3 a l ] t b , s le [ o 6 n ] a . m di H o s u o cr n w et e e v f e M r, t R i F t m s h e e t s y t e p o ic a s a l o l g l l o v y r e i u t s h p e r m o d s b i l n e ca m c n o s m t w a p k h u e i t c e a h r segmentation, stereo matching, image restoration, and panoramic stitching involve inferring the maximum  t o a posteriori ( MAP )solutionofaprobabilitydistribution i m nv o o v l e v s e to a w la a r r g d e s n th u e m e b r e a r o o f f l v ar a g ri e ab v l i e d s e . o A s s a c n o d m gi p g u a t p e i r x v el is i ion defined by a discrete MRF or CRF [3], [4], [5], [6]. The MAP m- solutioncanbefoundbyminimizinganenergyorcost i a m ge p s o , r c t o n m t. p I u n t d at e i e o d n , al th e e ffi la ci s e t n f c e y w is ye b a e r c s o h m a i v n e g s i e n e c n re a as l i o n t gl o y f function.Inthelastfewyears,drivenbyitsapplicability, attentio a nbeingdevotedtoisingtheperformanceof energy minimization has become a very active area  ncrea of research [6]. Although, minimizing a general MRF minimization algorithms [2], [14], [15], [16]. energyfunctionisanNP-hardproblem[3],thereexista of W e e ne m rg a y ke m t i w n o im c i o z n a t t r i i o b n uti a o l n g s or t it o h i m m s p . ro O v u e r th fi e rs e t ffi c c o ie n n tr c i y - number of powerful algorithms which compute the exact solution for a particular family of energy functions in  bution is a method which works by reusing results polynomial time. For instance, max-product (min-sum)  from previous problem instances, providing a simpler belief propagation exactly minimizes energy functions  alternative to the recent work of [2] on dynamic en- definedovergraphswithnoloops[7].Similarly,certain e w rg hi y ch mi s n i i m m p i l z i a fi t e i s on t . h O e u e r n s e e r c g o y nd m c i o ni nt m r i i z bu ti ti o o n n p is ro a bl m e e m tho by d submodularenergyfunctionscanbeminimizedbysolv- reducingthenumberofvariablesinthe a energfunctio ing an st-mincut problem [8], [9], [10], [11].  y n. Efficientalgorithmshavealsobeenproposedforfunc- o F f ur t t h h e er, op it ti c m a a n l a v l a s l o ue b s e o u f se t d he to re s m p a e i e n d i - n u g p v t a h r e ia i b n l f e e s r . en W ce tionswhichdonotfallundertheaboveclasses[3], alsodemonstratetheapplicabiliofthesemethodsfor e [12], [13]. Expansion and swap move making algorithms,  tain higher  ty sequential tree-reweighted message passing, and belief  cer order energy functions [1]. ar methods for solv- Recycling Solutions: Our first method is inspired propagation are examples of popul  by the dynamic computation paradigm [2], [15], [16]. It • K. Alahari and P. H. S. Torr are with the Department of Computing, improves the performance of the α -expansion algorithm Oxford Brookes University, Oxford, U.K. by reusing results from previous problem instances. The • E P -m K a o i h l: li s i e s e w ht i t th p:// M c i m cr s o . s b o r f o t ok R es e . s a e c a . r u c k h /r C es a e m ar b c r h i / d v g i e s . iongroup idea of dynamic computation has been used in the recent . work of [15], [16] on minimizing submodular energy This work was supported by the EPSRC research grants EP/C006631/1(P) functions. In particular, [16] showed how flow can be a u n n d der G t R h / e T2 P 1790/01(P), t th w e or ISTP x ro ce g l r l a en m ce m , e IS of T- t 2 h 0 e 07 E -2 ur 1 o 6 p 8 e 8 a 6 n .P C . o H m . m S. unity, reused in maxflow algorithms, and [15] showed how isinreceipt A o S f C R A oy L a 2 l N S e ociety k W of ol E fsonResearchMeritAward. Torr cuts (or previous labelling) can be reused. However,