Interactive object extraction using probabilistic graphical models
Olasılıksal grafik modeller kullanarak etkileşimli nesne çıkarma
- Tez No: 389437
- Danışmanlar: DOÇ. DR. İLKER BAYRAM
- Tez Türü: Yüksek Lisans
- Konular: Mühendislik Bilimleri, Engineering Sciences
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Bölümü
- Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 75
Özet
Son yıllarda, olasılıksal grafik modeller, enerji fonksiyonlarının en küçük degerlerini ˘ bulmakta kullanılan en-iyileme yöntemleri arasında yerini almaya ba¸slamı¸stır. Bu tezde, renkli imgelerde kullanıcı etkile¸simiyle, olasılıksal grafik modellerin, ilgilenilen nesnenin elde edilebilmesi için, yani imgenin nesne ve arkaplan olmak üzere iki sınıflı gösteriminin elde edilmesi anlatılmaktadır. Kullanıcı etkile¸simi, kullanıcının imgedeki bazı pikselleri nesne veya arkaplan olarak i¸saretlemesi sonucu nesneye veya arkaplana ait sınırlı ipuçlarının elde edilmesini açıklamak için kullanılmaktadır. Bu yöntemde ilgilenilen nesne(ler) birden fazla ve birbirlerinden ayrı olabilmektedir. Kullanıcı etkile¸simli nesne çıkarımı konusunu, otomatik nesne çıkarımı methodlarının hiçbir zaman tam olarak mükemmel olamayacagı temeline dayanarak ortaya çıkmı¸stır. ˘ Bu nedenle bu tezdeki amaç, Boykov ve Kolmogorov tarafından önerilen graf kesim yakla¸sımı kullanılarak Android i¸sletim sistemine sahip akıllı telefonlar üzerinde genel amaçlı bir nesne çıkarım uygulamasının gerçekte¸stirilmesidir. Bu uygulamada, kullanıcı, ilgilendigi nesnelere ve arkaplana ait az sayıda pixeli i¸saretlemektedir. ˘ Sonrasında uygulama, kullanıcı tarafından saglanan nesne/arkaplana ait bu ipuçlarını ˘ kullanarak nesneleri çıkarmaktadır. Bu amaçla ilk olarak Markov Random Fields (MRF) temelli nesnenin bölgesel (regional) ve sınırlarına göre bir amaç fonksiyonu tanımlanmaktadır. Ardından, amaç fonksiyonuna ait en iyi çözüm Maximum a Posteriori (MAP) kestirim yöntemi ile bulunmaktadır. Eger amaç fonksiyonu ˘ MRF kurallarınca dogru tanımlandıpı takdirde bulunan çözüm, tüm çözüm kümesi ˘ içerisindeki en iyi çözüm olacakdır. ˙Ilk olarak P'yi 2 boyutlu imgemize ait pikseller, N'i de bu imgedeki tüm sıralanmamı¸s piksel kom¸suluklarını {p,q} olarak ve X = X1, ··· , Xp, ··· , X|P| nesne'yi '1', arkaplanı '0' olarak tutan bir ikili imge olarak dü¸sünülürse, (Xp ∈ {1, 0}), MRF-MAP temelinde amaç fonksiyonumuz; E (X) = λ ·R(X) +B(X) ve R(X) = ∑ p∈P Rp (Xp) B(X) = ∑ {p, q}∈N B{p, q} · δ{Xp, Xq} olarak tanımlanmaktadır. Formüldeki λ ≥ 0 olmak üzere, bölgesel özellikler terimi olan R(X) ile sınır özelliklerine ait terim B(X) arasındaki görece (bagıl) önemlili ˘ gi˘ belirleyen parametredir. δ parametresi ise Kroneker delta olmak üzere ise; δ(Xp, Xq) = 1 if Xp 6= Xq 0 diger durumlarda ˘ Bu amaç fonksiyonuna göre, bölgesel özellik terimi R(Xp), herhangi bir piksele nesne (Rp (nesne))veya arkaplan (Rp (arkaplan)) olarak atanan sınıfa göre bireysel cezalandırma terimi olarak tanımlanmaktadır. (Rp (·)) uygulamamızda p pikselinin nesne/background histogramına göre hesaplanmaktadır. Sınır özellik terimi B(X) ise X ikili nesne/arkaplan imgesinin sınır olarak hesaplanan yerleri ile ilgilidir. B{p, q} ≥ 0 katsayısı p ve q pikselleri arasındaki süreksizligi˘ cezalandırması olarak tanımlanmı¸s ve bu katsayı büyük oldugu durumlar ˘ p ve q piksel degerlerinin (intensity) birbirine benzer, sıfıra yakın oldu ˘ gu durumda da bu piksel ˘ degerleri arasındaki farkın büyük oldu ˘ gu sonucu çıkmaktadır. ˘ Bu denklemlerin çözümü ise, en-iyileme teorisindeki maksimum akı¸s minimum kesi¸sim teoremlerinden (max-flow min-cut) olan Boykov ve Kolmogorov'a ait graf kesi¸sim yöntemi ile gerçekletirilmektedir. Bu yöntemi diger yöntemlerden ayıran en ˘ önemli özelliklerden birisi, matematiksel olarak izlenebilir bir yöntem degildir ve en ˘ kötü durum karma¸sıklıgı standart yöntemlerden daha kötüdür, fakat ˘ ço ˘gu durumda en iyi hız ve performansa sahiptir. Yöntem geni¸sleme, akı¸s-arttırma ve evlat-edinme olmak üzere üç a¸samadan meydana gelmektedir. Geni¸sleme a¸saması, iki dinamik arama agacının geni¸sle¸sletilmesi ile ˘ ba¸slar. Ba¸slangıçta dinamik arama agaçları sadece kullanıcı tarafından belirlenen ˘ nesne ve arkaplan dügümlerinden (node) olu¸smaktadır. Sonrasında, her adımda, bu ˘ arama agaçları çevrelerindeki herhangi bir arama a ˘ gacına ait olmayan graf dü ˘ gümlerini ˘ kendilerine ekleyerek büyümeye çalı¸smaktadırlar. Bu a¸sama kar¸sı agaçtan bir dü ˘ güm˘ ile kar¸sıla¸sılana kadar devam etmektedir, eger kar¸sıla¸sma gerçekle¸sirse geni¸sleme ˘ i¸slemini keserek akı¸s-arttırma a¸samasına geçilir. Akı¸s-arttırma, nesne ve arkaplan arasında bulunan yol üzerindeki en küçük graf kenarının bulunması ve bu degerin toplam akı¸sa eklenmesi ile tamamlanmaktadır. ˘ Akı¸s arttırma iki arama agacının kesi¸sme noktaları ile en küçük graf kenarının farklı ˘ olması durumunda iki agaca da ait olmayan“yetim dü ˘ güm”olarak adlandırılan yeni ˘ dügümlerin ortaya çıkmasına neden olmaktadır. Evlat-edinme a¸saması da bu durumda ˘ devreye girmektedir. Eger akı¸s-arttırma a¸samasında yetim dü ˘ gümler ortaya çıkmı¸ssa, ˘ bu a¸sama da bu dügümlere yeni arama a ˘ gacı bulunur veya serbest bırakılır. ˘ Akıllı telefon uygulaması, amaç fonksiyonunu grap temelli bir yakla¸sım ile çözerek, en iyi çözüme ait ikili nesne/arkaplan imgesini elde etmektedir. Uygulama, kullanıcı ile etkile¸simi saglayan grafik arayüz katmanı ve ilgili algoritmaların oldu ˘ gu katman olmak ˘ üzere, temel olarak iki yazılım katmanından olu¸smaktadır. Arayüz katmanı, Android i¸sletim sistemin yazılım geli¸stiricilere sagladı ˘ gı Java tabanlı sistem fonksiyonları ˘ kullanılarak gerçeklenmi¸stir. Algoritma katmanı ise, uygulamanın ihtiyaç duydugu hız ˘ ve performans nedeniyle, sadece C++ ve standard ¸sablon kütüphaneleri kullanılarak geli¸stirilmi¸stir. Algoritma katmanı, gerekli C++ derleyicisinin oldugu herhangi bir ˘ i¸sletim sisteminde, hiçbir degi¸sikli ˘ ge gerek olmadan derlenebilmektedir. (Windows ˘ 7, Ubuntu 12.04 ve Android isletim sistemlerinde çalı¸stırılmı¸stır). Bu iki yazılım katmanı arasındaki baglantı ise JNI (Java Native Interface) kullanılarak sa ˘ glanmı¸stır. ˘ JNI, C/C++ gibi temel programlama dillerinin Java ortamında kullanılmasını saglayan ˘ bir arayüzdür. Bu arayüz ile uygulamamız Java kodu ile yazılmı¸s arayüzden dogrudan ˘ C++ fonksiyon çagrıları yapabilmektedir. ˘ Algoritma katmanı temel olarak graf-olu¸sturma ve grafı çözme olmak üzere, iki dizi (threads) ve arayüz katmanından gelen belirsiz zamanlı çagrılardan olu¸smaktadır. ˘ Belirsiz zamanlı çagrılar kullanıcının nesne/arkaplana ait pikselleri seçti ˘ gi zamanlardır ˘ ve algoritma katmanındaki graf olu¸sturma a¸samasına katkısı yoktur. Dolayısıyla, graf olu¸sturma dizisi, kullanıcı nesne ve arkaplana ait pikselleri belirlerken grafın olu¸sturulmasından sorumludur, graf-çözme dizisi de grafın çözümlenmesi görevinden sorumludur. ˙Iki farklı dizi yapılmasındaki amaç, kullanıcı için gerekli zaman diliminde, kullanıcının sagladı ˘ gı bilgilerden ba ˘ gımsız olan hesaplamaların ˘ bitirilmesidir, böylece uygulamanın yakla¸sık %40'lık zaman kazancı saglanmasına ˘ olanak tanımaktadır. Bu amaçla tezde, bu konunun detayları anlatılmakta ve elde edilen sonuçlar yorumlanmaktadır.
Özet (Çeviri)
In this thesis, we present a comprehensive study of combining probability theory and graph theory (referred to as probabilistic graphical models) in interactive object extraction, with respect to both defining an objective function and finding the optimal solution. A two dimensional RGB image is divided into“object”and“background”regions using the graphical model. A graph is formed by connecting all pairs of neighboring image pixels to define an energy function in a context of Maximum A Posteriori based Markov Random Field estimation in terms of likelihood and a priori models. Certain pixels marked by a user indicate a priori identified as object or background seeds providing necessary clues about the image content. On the other hand, the likelihood is also calculated using these seeds. Our aim is to find the globally optimal solution to cut the edges in the graph so that the object seeds are completely separated from the background seeds. The obtained solution gives the best balance of boundary and region properties satisfying the user seeds. The topology of our model is unrestricted and both object and background regions can consist of several isolated parts. An object boundary can be anywhere but it has to separate the object seeds from the background seeds. These seeds can be loosely positioned inside the object and background regions. The framework is quite stable and normally produces the same results regardless of particular seed positioning within the same image object. In addition, the globally optimal solution can be very efficiently recomputed when the user adds or removes any seeds. This allows the user to get any desired object/background results quickly via very intuitive interactions. We implemented an software application for Android-based smartphones in order to assess the effectiveness of the model in the real world. The application is a fast and generic implementation to perform interactive object extraction for color images. It was implemented in two parts; the user interaction (Graphical User Interface, GUI) depends on Android Software Development Kit, SKD (based on Java) and the algorithm's main implementation was written based on native C++ with standard template library because of portability. The algorithm part can be compiled in any platform without any porting effort. We tested it in Microsoft Windows 7, Ubuntu 12.04 LTS. In addition, some experimental results are presented in the related chapters. Results were obtained for different parameter values, overall time and image complexities.
Benzer Tezler
- Geodezik mesafe tabanlı etkileşimli resim bölümlemesi
Geodesic distance based interactive image segmentation
ORKUN ÖZTÜRK
Yüksek Lisans
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TANSEL ÖZYER
- Abdominal image segmentation and visualization using hierarchical neural networks
Hiyerarşik sinir ağları ile abdominal görüntü bölütleme ve üç boyutlu görüntüleme
MUSTAFA ALPER SELVER
Doktora
İngilizce
2010
Elektrik ve Elektronik MühendisliğiDokuz Eylül ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. CÜNEYT GÜZELİŞ
- Hücresel sinir ağı sistemleri kullanarak hareketli nesnelerin görüntü işleme uygulamaları
Image processing applications of moving objects using cellular neural network systems
EMEL ARSLAN
Doktora
Türkçe
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SABRİ ARIK
- Mevkisel ve anlamsal göreceli nitelikler yardımıyla görüntü tanıma
Visual recognition via spatially and semantic relative attributes
EMRAH ERGÜL
Doktora
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKocaeli ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SARP ERTÜRK
DOÇ. DR. NAFİZ ARICA
- Değişken rezolüzyonlu görüntü örnekleyici
Multi resolution image sampler
RIZA CAN TARCAN
Yüksek Lisans
Türkçe
1991
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiY.DOÇ.DR. M. SAİT TÜRKÖZ