20.500.12556/RUL-95138 Segmentacija slik z uporabo največjega pretoka Image segmentation using maximum flow 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. 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. graf omrežje največji pretok najmanjši prerez algoritem Forda in Fulkersona segmentacija slik graph network maximum flow minimum cut Ford-Fulkerson algorithm image segmentation true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-09-15 14:49:46 2017-09-15 14:49:47 2022-08-10 02:19:28 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 20404 Krizman_Eva_-_Segmentacija_slik_z_uporabo_najvecjega_pretoka.pdf Krizman_Eva_-_Segmentacija_slik_z_uporabo_najvecjega_pretoka.pdf 1 C93112BDA32A9E422BC50696642FD6A0 148f73c3b543e455723d75c4af208629ff4508591e678f8afa3e75fc6680a9db b1e5966a-a1b3-11eb-a523-00155dcfd717 20.500.12556/rul/bff2cb10-bc62-4eb2-a596-533931b16b79 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=103703 Fakulteta za računalništvo in informatiko 0 0 0