Segmentacija slik z uporabo največjega pretoka

KRIŽMAN, EVA (author), Žitnik, Arjana (mentor)

V diplomski nalogi obravnavamo segmentacijo slik s pomočjo največjega pretoka. V prvem delu podrobneje predstavimo problem največjega pretoka in njemu dualen problem najmanjšega prereza. Predstavimo tudi dva alogritma za reševanje teh dveh problemov, to sta algoritem Forda in Fulkersona in Diničev algoritem. V drugem delu diplomske naloge predstavimo pojem segmentacije slik in naštejemo nekaj metod, s katerimi se segmentacija izvaja. Nekatere od njih tudi opišemo. To so pragovna metoda, metoda razvrščanja v skupine, metoda regij in segmentacija na grafih. V zadnjem poglavju si podrobno pogledamo segmentacijo na grafih. Sliko predstavimo z uteženim grafom in na temu grafu poiščemo največji pretok oziroma najmanjši prerez. S pomočjo prereza potem ločimo slikovne pike na tiste, ki pripadajo ospredju in tiste, ki pripadajo ozadju. Vse algoritme predstavimo s psevdokodo in analiziramo njihovo časovno zahtevnost. Na koncu predstavimo tudi probleme, ki se pojavljajo pri tovrstni segmentaciji.

• Language: Slovenian
• Keywords: graf, omrežje, največji pretok, najmanjši prerez, algoritem Forda in Fulkersona, segmentacija slik
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-95138
• Publication date in RUL: 15.09.2017

Secondary language

• Language: English
• Title: Image segmentation using maximum flow

Abstract

In this thesis we consider image segmentation using maximum flow. In the first part of the thesis we present in detail the maximum flow problem and its dual problem, the minimum cut problem. We describe two algorithms for solving these two problems, the Ford-Fulkerson algorithm and Dinic algorithm. In the second part of the thesis we introduce the concept of image segmentation and we list some methods that are used for image segmentation. We describe some of them: the thresholding method, clustering methods, the region-growing methods and segmentation on graphs. In the last chapter we present in more detail segmentation on graphs using maximum flow. We represent a given image with a weighted graph. Then we find maximum flow and minimum cut in this graph. Using minimum cut we can separate pixels to those that belong to the foreground and those that belong to the background. Pseudo code is given for all the algorithms used and their time complexity is analyzed. At the end of the thesis we discuss some problems that arise in this kind of segmentation.

• Keywords: graph, network, maximum flow, minimum cut, Ford-Fulkerson algorithm, image segmentation