In English

Presentationsinformation     2017-03-16 (10:15)   •  2446

Talare Filip Malmberg  (CBA)
Kommentar Docent lecture (in Swedish)
Titel Minimala grafsnitt - ett kraftfullt verktyg för att lösa optimeringsproblem inom datoriserad bildanalys
Sammanfattning Många problem inom datoriserad bildanalys kan med fördel formuleras som optimeringsproblem. Man ställer då upp ett kriterium som en bra lösning på problemet förväntas uppfylla, och använder sedan en optimeringsmetod för att hitta en lösning som är så bra som möjligt enligt det givna kriteriet. I den här föreläsningen tittar vi närmare på en särskild optimeringsmetod, som baseras på beräkning av minimala grafsnitt. Metoden bygger på att man för ett givet optimeringsproblem konstruerar en graf som har den egenskapen att det minimala snittet i grafen också ger lösningen på optimeringsproblemet. Det minimala snittet kan i sin tur beräknas effektivt med välkända algoritmer. Denna metod¬ utgör ett kraftfullt verktyg för att lösa många optimeringsproblem som uppstår inom datoriserad bildanalys och kan i många fall hitta lösningar som är garanterat globalt optimala, det vill säga minst lika bra som någon annan lösning till problemet. I föreläsningen kommer jag att gå igenom definitionen av minimala grafsnitt och algoritmer för att beräkna dem, samt ge konkreta exempel på tillämpningar inom datoriserad bildanalys.