I detta dokument tar vi upp problemet med att minimera en stor klass av energifunktioner som uppstår i tidiga visioner. Den största begränsningen är att energifunktionens släthetsterm endast får omfatta par bildpunkter. Vi föreslår två algoritmer som använder graf skär för att beräkna ett lokalt minimum även när mycket stora rörelser är tillåtna. Den rst flytta vi anser är en --swap: för ett par etiketter ;, Detta drag utbyter etiketter mellan en godtycklig uppsättning pixlar märkta och en annan godtycklig uppsättning märkt. Vår rst algoritm genererar en märkning så att det inte finns någon swap flytta som minskar energin. Det andra draget vi anser är en -expansion: för en etikett, Detta drag tilldelar en godtycklig uppsättning pixlar etiketten. Vår andra algoritm, som kräver att släthetstermen är ett mått, genererar en märkning så att det i s n o expansion flytta som minskar energin. Dessutom ligger denna lösning inom en känd faktor för det globala minimivärdet. Vi demonstrerar experimentellt effektiviteten i vår strategi för bildrenovering, stereo och rörelse. Många tidiga synproblem kräver att uppskatta vissa rumsligt varierande mängd a s i n tensitet o r skillnad från bullriga mätningar. Sådana mängder tenderar att vara styckvis släta; de varierar smidigt på de flesta punkter, men förändras dramatiskt vid objektgränser. Varje pixel p 2 P måste tilldelas en etikett i någon uppsättning L; för rörelse eller stereo, etiketterna är skillnader, medan för bild restaurering de representerar i n tentiteter. Målet är att nd en märkning f som tilldelar varje pixel p 2 P en etikett f p 2 L, där f är både bitvis slät och överensstämmer med de observerade data. Dessa visionsproblem kan naturligt formuleras i termer av energiminimering. I denna ram söker man den märkning f som minimerar energin Ef = E slät f + E data f: Här E slät mäter i vilken utsträckning f inte är bitvis slät, medan E data mäter oenighet b e t wen f och observerade data. Många olika energifunktioner har föreslagits i litteraturen. , där i p är den observerade intensiteten av pixel p. Valet av E slät är en kritisk fråga, och många olika funktioner har föreslagits. Till exempel i standard regularisering-baserad vision 6, E slät gör f slät överallt. Detta leder till dåliga resultat vid objektgränserna. Energifunktioner som inte har detta problem kallas diskontinuitetsbevarande. Ett stort antal avbrottsbevarande energifunktioner har föreslagits se till exempel 7. Geman och Geman s seminal papper 3 gav ett B en jasian tolkning av många energifunktioner, och föreslog en diskontinuitetbevarande energifunktion baserad på Markov Random Fields MRF: s. Den stora sorten med energiminimering för tidig vision ligger i de enorma beräkningskostnaderna. Vanligtvis dessa energifunktioner har många lokala minima d.v.s., de är icke-konvexa. Ännu värre, utrymmet för möjliga märkningar har dimension jPj, som i s m a n y tusentals. Det har gjorts många försök att designa snabba algoritmer för energiminimering. Simulerad glödgning populariserades i datorseende av 3, och används ofta eftersom det kan optimera en godtycklig energifunktion. Tyvärr, minimera en godtycklig energifunktion kräver exponentiell tid, och som en följd simulerad glödgning är mycket långsam. I praktiken är glödgning inte tillräckligt delvis eftersom det vid varje steg ändrar värdet på en enda pixel. De energifunktioner som vi betraktar i detta dokument uppstår i en mängd olika sammanhang, däribland den Bayesianska märkningen av MRF:s. Vi tillåter D p
Det arbete som presenteras i REF använder graf-cut för att hitta ett lokalt minimum inom en känd faktor för det globala minimum.
Fast approximate energy minimization via graph cuts
{'venue': 'Proceedings of the Seventh IEEE International Conference on Computer Vision', 'journal': 'Proceedings of the Seventh IEEE International Conference on Computer Vision', 'mag_field_of_study': ['Computer Science']}