Image Inpainting Serisi 4: Statistics of Patch Offsets for Image Completion
Image Inpainting serisinin 4.yazısında Görüntü Tamamlama için Parça Kaydırma İstatistikleri (Statistics of Patch Offsets for Image Completion) isimli çalışmanın tanıttığı yöntemi inceleyeceğiz. Serinin ilk yazısı için sizi şöyle alalım :)
Görüntü Tamamlama için Parça Kaydırma İstatistikleri (Statistics of Patch Offsets for Image Completion)
Bu makalede yüksek kaliteli ve hızlı görüntü tamamlama için yeni bir yöntem öne sürülmüştür. Görüntü içerisindeki benzer parçalar eşleştirildiğinde bu parçaların birbirlerine olan uzaklıklarının seyrek bir dağılım gösterdiği gözlemlenmiştir ve bu dağılım Şekil 1 (c)’de gösterilmiştir. Şekil 1’deki görüntüdeki sütunlar tekrarlı bir yapıdadır ve birbirlerine olan uzaklıkları belli bir orandadır. Parçalar çoğunlukla, istatistiksel olarak birkaç belirgin tepe oluşturmakta ve benzer uzaklıklara sahip olmaktadırlar. Bu tip baskın uzaklıklar, görüntü içerisindeki desenlerin ne sıklıkla tekrarlandığını açıklarlar. Böylece eksik olan bölgenin tamamlanması için ipucu sağlarlar. Bu tip uzaklıkların lineer yapıları, dokuları ve tekrarlı nesneleri tamamlamak için ipuçları sağladıkları gözlemlenmiştir. Önceden seçilmiş bir miktar baskın uzaklıklarla (örneğin 60), eksik bölge üzerinde kaydırılmış bir yığın görüntü optimize edilerek birleştirilmiştir.
Algoritma
Bu bölümde tasarlanmış algoritmanın adımları incelenecektir. Oluşturulmuş yöntem üç adıma sahiptir: (i) benzer parçaları eşleştirmek; (ii) uzaklık istatistiklerini hesaplamak; (iii) kaydırılmış görüntüleri birleştirerek eksik bölgeyi tamamlamak.
(i) Benzer Parçaları Eşleştirmek. Öncelikle bilinen bölge üzerindeki benzer parçalar eşleştirilir ve benzer parçaların birbirlerine uzaklıkları elde edilir (Şekil 1(b)). Bilinen bölgedeki her parça P için, en benzer olduğu parça ile arasındaki uzaklık s hesaplanır:
Burada s=(u, v), uzaklığın 2 boyutlu koordinatları; x = (x, y), a parçasının pozisyonu ve P(x), x pozisyonunda merkezlenmiş parçadır. İki parça arasındaki benzerlik farklarının karelerinin toplanması ile hesaplanır. Eşik değeri τ çevredeki parçaları engellemek için kullanılır. Bu sabit önemsiz istatistiklerin önüne geçmek için oluşturulmuştur.
(ii) Uzaklık İstatistiklerini Hesaplamak. Tüm uzaklıklar s(x) olarak verildiğinde istatistikleri 2 boyutlu histogram h(u, v) kullanılarak hesaplanır:
Burada δ(.) içerisindeki argüman doğruyken 1, diğer durumlarda 0'dır. Histogramdan en yüksek K tepecik seçilir. Bunlar K baskın uzaklığa karşılık gelir. Bu makalede K = 60 olarak kullanılmıştır. Şekil 1(c) histogramdan bir örnek gösterir. Yatay yönde iki önemli tepecik vardır. Bu tepecikler tarafından verilen uzaklıklar, görüntü üzerinde desnelerin nasıl tekrarlandığını gösterir.
(iii) Kaydırılmış Görüntülerin Optimizasyonla Birleştirilmesi. K uzaklık verildiğinde, görüntü tamamlama problemi bir fotomontaj problemine dönüşür. Şekil 1(d)’de eksik bölgenin kaydırılmış gösrüntülerden oluşturulmuş bir yığınla tamamlanması gösterilmiştir. Aşağıda MRF enerji fonksiyonu optimize edilmiştir:
Burada ω sınır koşulları verilmiş bilinmeyen bölge ve (x, x’) ise bağlantılı 4 komşudur. Etiketler önceden seçilmiş aşağıdaki uzaklıkları
ifade ederken L etiketlendirme anlamına gelir. “L(x) = i” ifadesi x + si konumundaki pikselin x bölgesine kopyalandığını gösterir.
Eğer etiket geçerli ise, x + s bilinen bir pikselse, veri terimi $E_{d}$ 0 olur. Diğer durumlarda değeri +∞’dur. Pürüzsüzlük terimi Es, tutarsız görüntüleri cezalandırmak içindir. a = L(x) ve b = L(x’) iken Es şu şekilde tanımlanır:
Burada I(x) x’in RGB rengidir. I(.+s) ayarlanmış bir s değeri için kaydırılmış görüntüdür. Eğer sa ≠ sb ise x ve x’ arasında bir tutarsızlık vardır. Böylece bu tutarsızlık, iki kaydırılmış görüntü olan I(.+sa) ve I(.+sb) böyle bir tutarsızlığın yakınında oldukları için cezalandırılır. Bu pürüzsüzlük terimi temelde GraphCuts dokusu, Photomontage ya da Shift-map’te tanımlananlara benzerdir. Enerji fonksiyonu çoklu etiketli graph-cuts kullanılarak optimize edilir. Sonuç Şekil 1(e)’de gösterilmektedir.
Analiz
Bir önceki kısımda açıklanmış olan algoritma üzerinden yapılan gözlemler bu kısımda açıklanmıştır.
Uzaklık İstatistiklerinin Aralıklı Olması
Yapılmış olan en kilit gözlemlerden biri uzaklık istatistiklerinin aralıklı olmasıdır (Şekil 1(c)). Aralıklı olmaktan kasıt seyrekliktir. Bu gözlem, elle etiketlenmiş göze çarpan nesnelerden oluşan 5,000 görüntüyü içeren MSRA Belirgin Obje Veritabanı kullanılarak doğrulanmıştır. Veri kümesi üzerinden bu objeler çıkartılmış ve arkaplandaki uzaklık istatistikleri hesaplanmıştır. Bu durumda arkaplanda hala çeşitli yapılar veya daha az göze çarpan nesneler vardır. 8x8 boyutlu parçalar τ = 16, 24 ve 32 iken Eşitlik 1 ile test edilmiştir. Her görüntü için, histogram çubukları büyükten küçüğe göre sıralanmıştır. Büyüklük o çubuktaki uzaklık sayısına göre olmuştur. Histogram çubukları kümelenmiştir. Bu kümelenmiş dağılım Şekil 1(a)’da gösterilmiştir. Bu şekilde uzaklıkların aralıklı dağıldığı gözlemlenmektedir. Örneğin τ = 32 iken uzaklıkların %80'i olası tüm çubukların %7'sindedir. Kümelenmiş dağılım τ değerlerine göre (16, 24 veya 32) çok az değişmektedir (Şekil 2(a)(b)). Bu durum, aralıklı olma durumunun geniş spektrum’da τ’dan bağımsız olduğunu gösterir.
Bahsetmeye değer diğer bir şey ise Eşitlik 1'deki yakın olmayan kısıtlamanın (|s| > τ) önemli olduğudur. Doğal görüntü istatistikleri hakkında yakın zamanda yapılmış bir çalışma eksik bir parça için en iyi eşleşmenin parçanın yakınında konumlanmış olduğunu göstermektedir. τ = 0 iken (bir parça yalnızca kendisi ile eşleşebilir) yapılan denemede bu doğrulanmıştır. Uzaklık istatistiklerinin (0, 0) civarında tek bir baskın tepesi olduğu gözlemlenmiştir (Şekil 2(d)). Uzaklık dağılımı daha da aralıklı olsa da, sıfır uzaklık durumu eksik bölgedeki yapıları çıkartmak için önemsizdir.
Görüntü Tamamlama için Uzaklık İstatistikleri
Lineer yapılar uzun ve ince nesneleri (Şekil 4(a)), iki ayrı rengi ayıran sınırları (Şekil 4(b)) ve dokusal sınırları (Şekil 3(c)(d)) içerir. Bu örneklerde histogramdaki baskın uzaklığı göstermek için bir nokta kullanılır. Şekil 3’de gösterildiği gibi, lineer yapı içerisindeki bir parça kendi eşini yine bu yapı içerisinden bulabilir. Şekil 4’te gerçek örnekler üzerinden gösterildiği gibi uzaklık istatistikleri yapıda oluşturdukları tepecik serisi ile bir yön meydana getirmektedir (Şekil 3(b)). Lineer yapıyı tamamlamak için görüntüyü bu yön üzerinden kaydırmak yeterli olmaktadır (Şekil 3(c)). Oluşturulmuş bu yöntem aralıklı olmayan uzaklık dağılımına sahip olan (örneğin Şekil 4(c)) veya net bir ayrıma sahip olmayan (örneğin Şekil 4(d)) yapılar üzerinde de çalışmaktadır. Yapının bir ya da daha fazla yönde bir gidişata sahip olması yeterlidir.
Dokular uzaklık istatistikleri için belirgin desenler verebilirler. İdeal olarak, düzenli bir doku, dokunun nasıl tekrar ettiğini tanıtan düzenli bir desen üretmelidir (Şekil 5). Bu durum gerçek görüntüler üzerinde gözlenmiştir (Şekil 6). Bu uzaklıkları kullanarak doku üzerinde kaydırma ile doku tamamlanır. Diğer taraftan, düzensiz bir doku rastgele desenler üretmektedir (Şekil 7). Bu durumda algoritma Graphcut doku algoritması gibi çalışmaktadır.
Tekrarlı nesneler. Bu tip nesneler de uzaklık istatistikleri içinde belirgin desenler üretebilirler. Anlamsal içerikler üretirken bu durum yardımcı olmaktadır. Şekil 8’de gösterildiği gibi kısmen kaybolan çemberler, uzaklıklarda çemberlerin göreceli konumlarına karşılık gelen tepecikler oluştururlar. Her çember bu uzaklığa göre kaydırılarak tamamlanabilir. Şekil 9’da algoritmanın doğrulukla tamamladığı eksik bir heykel gösterilmektedir. Eşleşme tabanlı yöntemlerin(örneğin) nesnelerin nasıl tekrar ettiklerini incelemedikleri için tatmin edici olmayan sonuçlar ürettiğini (Şekil 8(e) ve Şekil 9(f)) gözlemlenmiştir.
Bu yöntem yukarıdaki durumları ayrı ayrı inceleyebilme avantajına sahiptir. Hepsini ya da bunların bir karışımını aynı çatı altında ele alabilir.
Uzaklıkların Aralıklı Olması ve Optimize Enerji Fonksiyonu
Bu yöntemde kullanılmış olan enerji fonksiyonu Shift-map yöntemine benzemektedir. Aradaki temel fark Shift-Map’in tüm olası uzaklıklara izin veriyor olmasıdır. Bundan ötürü bu yöntemdeki çözüm uzayı, Shift-Map’in çok daha küçük bir alt kümesidir. Teorik olarak Shift-map bu yönemden daha küçük bir enerjiye ulaşabilmektedir (deneyler ile gözlenmiştir). Fakat Shift-map sonuçlarında enerji daha düşük olsa da beklenmeyen bir düzensizlik oranı ve tatmin edici olmayan bir görüntü kalitesi gözlenmiştir. Şekil 10’da bu yöntemdeki uzaklık aralıklarına göre (Şekil 10(b)) ve tüm olası uzaklıklara göre (Şekil 10(c)) enerjinin optimize edilmesi gösterilmiştir. Beklendiği gibi bu çalışmadaki yöntemin enerjisi (4.6 x 10⁶) Shift-map’in enerjisine göre (1.1 x 10⁶) çok daha büyüktür. Fakat görüntü kalitesi Shift-map’ten daha iyidir.
Bu beklenmedik olay graph-cuts etiket haritaları üzerinden araştırılmıştır (Şekil 10(b)(c)). Fazla sayıda uzaklık ile, Shift-Map yönteminin bölgeye çok fazla önemsiz etiket ekleyerek enerjiyi azalttığı bulunmuştur (Şekil 10(c)).
Uyumluluk Ölçümü
Bu yöntemin ölçümü optimize etmemiş olsa da daha iyi bir uyumluluk ölçümüne sahip olduğu gözlemlenmiştir. Uyumluluk ölçümü şu şekilde tanımlanır:
Burada P, üretilmiş bölge Ω’daki parça iken ve Q ise bilinen bölge
Ω¯’daki parçadır. Bu ölçüm üretilmiş bölgedeki herhangi bir P parçasını eğer bilinen bölgedeki en iyi eşleşmiş Q parçasına benzemiyorsa cezalandırır.
Bu çalışmadaki yöntem uyumluluk ölçümünü EM (Expectation-Maximization) algoritması ile optimize etmiştir. Çözüm uzayının boyutu çok geniş ve düzensiz olduğu için, kötü yerel minimumdan sakınmak için çok ölçekli bir biçim kullanmıştır. Bu tarz bir yaklaşım ile, az sayıda uzaklık değerinin sonuç üzerinde büyük etkiye sahip olduğu gözlemlenmiştir. Ve bu ölçüt değerleri daha kaba bir halden detaylı hale gelememektedirler. Bundan ötürü, bu yöntemdeki çok ölçekli biçim çözüm uzayını sınırlamada da bir rol oynamaktadır.
Diğer taraftan asıl çalışmadaki yöntem direkt olarak uzaklıkları önceden seçmektedir. Şekil 11’de asıl çalışma ve diğer yöntemin karşılaştırılması gösterilmiştir. Asıl çalışmanın uyumluluk ölçümü daha küçüktür. Bu, asıl çalışmadaki istatistiksel tabanlı uzaklık seçiminin uyumluluk ölçümünü küçültmek için daha iyi bir yol olduğuna işaret eder. Bu durum neden asıl çalışmanın diğer çalışmadan daha yüksek kalitede sonuçlar üretmesini sağladığını kısmen açıklar.
