Benzerlik Ölçümü

BENZERLİK ÖLÇÜMÜ

İçerik tabanli resim geriçağırım sisteminde, sistem veri tabanindaki kullanicinin istediği modele uygun ve kriterleri onceden belirlenmis butun resimleri arar. Sıralama operasyonunda genellikle belirli bir mesafedeki butun resimler yada ilk birkac resim bulunur. Benzerlik ölçümü resimlerin özellik kümesinde tanımlanan bir mesafe fonksiyonu ile yapılır. Benzerlik hesaplamalarında kullanılan algoritma genellikle mesafe fonksiyonunun istenilen özelliklerine yada özellik vektorune bağlıdır.

Birçok benzerlik ölçüm methodlarının amacı deformasyonlara izin vererek iki vector arasındaki mesafeyi minimize etmektir.Bunu yapabilmek icin öncelikle özellik vektörlerinin birimleri arasindaki alaka problemi çözülür sonra alakalı birimler arasındaki örtüşen hataların tamamının mesafesi ölçülür.

Bu konuda, BAS özellik vektorlerinin benzerlik ölçümlerinde kullanılan algoritmayı tanımlıyoruz. Özellik genişletme şekil sınırlarını diziler halinde çevirilmesiyle yapıldığı icin, sonuçta çıkan özellik vektörü dizi diye tanımlanır. Böylelikle, dizin karşılaştırma metodları BAS özelliklerinin mesafe fonksiyonu olarak kullanılabilir. BAS fonksiyonundan çıkarilmiş önerilen özellik vektörleri için iki değisik dizi karşılaştırma metodu vardır.

- Bağlı altdizi algoritmasının optimal alakası: sonsuz alfabetik bağlı karşılaştırmalar için geliştirilmiştir.
- Dinamik zaman deformasyonu: sürekli fonksiyonların zaman örneklendirilmesi ile elde edilen diziler için kullanılır.

Kaplı şekil çevrelemenin dairesel içeriği döngüsel olguyu ifade eder. Şekillerin tam açıklamasını elde etmek için, herbir şekil için, bir başlangıç noktası belirlenmelidir. Bu pratikte imkansız olduğu için, atanan hesaplama, optimal çözümü bulmak için yer almıs olan döngüsel değişimi belirler. Bu, yukardaki metodlarda, herhangibir dizini her seferinde bir birim kaydırarak yada dizi karşılaştırmasını tekrar hesaplayarak elde edilmiştir. Halbuki, bu hesaplama benzerlik ölçümlerini daha kompleks bir hale getirir ve özellikle geniş veritabanları için büyük bir yük olabilir. Bu sebeple, optimal çözümü yaklaşık olarak bulan başka verimli bir döngüsel dizin karşılaştırma algoritması geliştirdik.

- Döngüsel dizin karşılaştırma algoritması: döngüsel dizin karşılaştırmalarını daha az komplike hale getirir.

Bu konuda, bölüm 2.1 deki dizin karşılaştırma metodlarına kısa bir girişten sonra, noktasal mesafe fonksiyonu bolum 2.2 de verilmiştir. Bağıl Altdizinlerin Optimal Alakası (BAOA) ve Dinamik Zaman Deformasyonu (DZD) algoritmaları sırasıyla bolum 2.3 ve 2.4 de verilmiştir. Bölüm 2.5 te BAOA ve DZD algoritmalarının kompleksitelerini arttırma metodları ele alınıyor. Son olarak döngüsel karşılaştırma algoritması bölüm 2.6 da ele alınıyor.

2.1 Genel Olarak Dizin Karşılaştırmaları

İki dizin (bağlar, vektörler, sürekli zaman fonksiyonları vb.) arasındaki karşılaştırma bu ölçümlerin değişimlerine kadar olan degerleri ölçmek için yapılan uygulamadır. Yazılı uygulamada bu problem aynı zamanda bağıl karşılaştırma olarak da nitelendirilir. Bazen herhangi iki dizindeki birimlerde dogal alaka vardır ve karşılaştırma alakalı birimlere dayanır. Bu gibi durumlarda, Minkowsky mesafeleri gibi (öklit mesafesi, şehir blok mesafesi) iyi bilinen bazı metodlar kullanılır. Halbuki, bazı durumlarda alaka cok iyi bilinmez çünkü bir yada birkaç dizin istenmeyen hatalara maruz kalmıştır veya dizinlerin uzunlukları farklıdır. O zaman, uygun alakalandırma tüm mümkün alakaların [137] optimizsyonu ile bulunur. Mesafe ve optimum analizi bulmak için yapılan optimizasyon için etkili metodlar, dizin karşılaştırmasının ana konusudur.

Dizin karşılaştırma metodlarınınmicro biyoloji, hata ve kod kontrol gibi birçok uygulama alanı vardır. Literatürde,uygulamaya bağlı olarak, çeşitli algoritmalar mevcuttur.Teori ve değişik uygulamalarda kullanılan algoritmalarla dizin karşılaştırmanın pratikleri [137] de mevcuttur.

Bu bölümde ana temayı özet bir giriş yapacağız ve temel algoritmayı vereceğiz.

2.1.1 Dizin Eşleme

İki dizin arasindaki mesafe bazı fark kümelerinden oluşur(operasyon kümesi diye de adlandırılır). Birçok uygulamada operasyon kümesi;

- aynı pozisyonda bir elemanın başka bir eleman ile yerdeğişimi

- elemanların silinmesi

- elemanların girdisi

islemleri ile sınırlandırılmışlardır.

Yukarıdaki işlemler bir dizini başka bir dizine çevirme işlemine yarar. İki dizin arasındaki mesafe bir maliyet fonksiyonu ile tanmlann toplam operasyonların minimum maliyeti olarak adlandırılır.

Sıkıştırma, genişletme ve taşıma gibi farklı operasyonlar farklı uygulamalarda kullanılabilir. Sıkıştırma ve genişletme sıkıştırma ve genişletme dizinler arasındaki bağlatıyı geliştirir.Bir dizinin iki farklı elemanının değişimi olan taşıma ise genellikle yazım hatalarıyla ilişkilidir.

Daha detaylı olarak anlatmak için, A ve B gibi iki farklı dizin tanımlayalım, A(i), i=1,2,3,…..,N ve B(j), j=1,2,3,….M. N ve M dizinlerin uzunluklarıdır. Maliyet fonksiyonlarıyla beraber operasyonlar ise;

Xxxxxxxxxxxxxxxxx(el ile yazılacak)

Değişiklikler , girdiler ve silmeler ile tanımlanabilir. Aynı şekilde girdiler ve silmeler de değişiklikler ile tanımlanabilir. Halbuki, dizin eşlemesindeki operasyonlar arası fark önemlidir çünkü her operasyon ile ilgili farklı maliyet olabilir. Bu konuda operasyonların maliyeti ve farkları mesafe fonksiyonlarıyla verilmiştir. Levenshtein farkı değiştirme, ekleme ve silme işlemlerini mümkün kılar. Bütün operasyonların maliyeti bir eşittir. Diğer bir deyişle, mesafe, iki dizin yapmak için gereken minimum silme, ekleme ve değiştirme sayısıdır. Hamming mesafesi sadece maliyeti bir olan yer değiştirmalere izin verir. Uzun ortak altdizin ise maliyeti bir olan ekleme ve silmeye izin verir.

2.1.2 Metrik Aksiyomlar

Matematikte, mesafe aşağıdaki metrik aksiyomları sağlayan d fonksiyonunu ifade eder;

1- Sıfırdan üçük olmama durumu; d(A,B) > 0
2- Sıfır olma durumu; d(A,B)=0 A=B ise
3- Simetri durumu; d(A,B)=D(B,A) Bütün A ve B değerleri için
4- Üçgen eşitsizliği; d(A,B) + d(B,C) > d(A,C) Bütün A,B ve C değerleri için

Mesafe kelimesi bu yolla ayrılmadığı halde, dizin karşılaştırma metodu bu özelliklere göre ifade edilir.Bu uygun “w” varsayımları ile yapılır.

Genellikle yukarıdaki aksiyomları sağlayan fonksiyonların kullanılması istense de, konuşma tanımlanması ve yazım düzeltimi gibi konularda istisnalar vardır. Şekillerin özellik kümesinde tanımlanan metrik mesafe fonksiyonu insan görsel sistemi ile uyuşmalı olmayabilir. Örneğin; simetri herzaman istenmez. İnsan görüşü herzaman A şeklini B’ye ve B şeklini A’ya eşit bir şekilde benzer bulmaz. Genellikle B prototipinin değişiği olan A daha benzer bulunur. Dahası, parçalı eşlemenin benzerlik çlçümü üçgen eşitsizliğine uymaz.

2.1.3 Temel Algoritma

Dizinler arasındaki mesafenin hesaplanmasındaki amaç bir dizini diğerine çeviren operasyonların toplam maliyetini minimize etmektir. Minimizasyon problemi dinamik programlama yaklaşımı ile çözülebilir.

Bu amaçla, dizinler arasındaki parçalı mesafeleri akümüle eden minimum mesafe tablosu oluşturulur. Öncelikle A(1)….A(i) ve B(1)…B(j) minimum mesafe eşlemisini D(i,j) olarak tanımlayalım. A(0) ve B(0) boş dizinlerinin başlangıç degerleri D(0,0) ve dizinler arasındaki toplam mesafe D(N,M) olur. Olay D(0,0) feğerinden başlar. Bu (0,0) hücresi için giriş sağlar. Eğer devam eder ve daha büyük I ve j değerleri için D(i,j) mesafesini bulursak, souçta istenilen mesafe olan D(N,M) ‘e ulaşırız. (i,j) hücresinin tekrarlanma ilişkisi üç belirleyici hücreye göre belirlenir; (i-1,j), (i-1,j-1), ve (i,j-1). Hesaplama şöyle yapılır;


Xxxxxxxxxxxxxxxxxxx (2.1)


Yukarıdaki terimlerin anlamlar ise; ilk terim A(i)’ yi eşlemesiz ırakır ve siler, ikinci terim A(i)’ yi B(j) ile değiştirir ve üçüncü terim ise B(j)’ nin A’ dan hiçbir karakter ile eşlemeden geçmesini sağlar.

D(N,M)’ nin hesaplanması I ve j üzerinde iterasyonu gerektirir, dolayısıyla, zamanda ve uzayda algoritmanın kompleksitesinin O(N,M) olduğunu görmek kolaydır.


2.2 Nokta Mesafe Fonksiyonu


BAS özellik vektörlerinin benzerlik ölçümlerinde kullanılan algoritma alakalı vektorlerdeki noktalardan olan mesafeler etrafında odaklanmıştır. Iki BAS özellik vektörünün karşılaştırılması her iki vektorlardeki ilgili noktaların karşılaştırılması ile yapılır. Nokta mesafe fonksiyonu olarak mutlak değer mesafesi kullanırız.Bu mesafe ölçüler arasındaki ortalama mesafedir. Verilen iki BAS vektörü R(q) ve R(t), sırasıyla her iki vektördeki noktaların arasındaki mutlak değer mesafesi;

Xxxxxxxxxxxxxxxxxxxx (2.2)

Burada M şiekil sınırlandırılmasında kullanılan BAS momentidir.
Öklit mesafesi gibi diğer mesafe fonksiyonları kullanmak da mümkündür. Fakat, karekök hesaplaması kompleksiteyi arttırırken benzerlik ölçüm uygulamasını geliştirmez.


2.3 Bağıl Dizinlerin Optimal İlgisi


BAS vektörleri için kullanılan bir diğer benzerlik ölçüm algoritması da bağıl dizinlerin optimal ilgisi (OCS) dir.OCS problemi klasik uzun ortak altdizin ve yaklaşık bağıl eşleme probleminden çıkmıştır. Eşleme ise tam eşleme yada sonlu alfabenin uygun alakasıdır.

OCS problemi aşağıdaki değerlerle tanımlanır;

- Alfabe: Alfabe bütün karakterlei barındıran sonsuz küme N dir.
- Ceza:
Xxxxxxx
- İlgi fonksiyonu: xxxxxxxxx (2.3)
Xxxxxxxxx (2.4)


N ve M uzunluktaki iki BAS vektörü R(q) ve R(t) arasındaki mesafe OCS algoritmasıyla hesaplanır.

Algoritma aşağıdaki gibidir;

Xxxxxx
Xxxxxxx
Xxxxxxx
Xxxxxxxx
Xxxxxxxx


2.4 Dinamik Zaman Deformasyonu


Bir başka dizin eşleme metodu ise dinamik zaman deformasyonu metodudur.Konuşma sinyali bireysel fenomenaların uzunlukları arasındaki farklar gibi değişikliklere maruz kalırlar.Eşleme uygulaması bu değişimleri bazı yerlerde sinyalleri sıkıştırarak ve bazı yerlerde genişleterek uğraşır. DZD algortiması bunu yapabilmek için; dizinlerin sıkıştırılması ve genişletilmesine imkan veren iki dizin arasındaki optimal eşlemeyi bulur.

Xxxxxxxxxxxxxxxxxxxxx (27. sayfadaki garfikler) (figure 2.1)


DZD kullanarak A ve B gibi iki dizine N ve M uzunluklarını adamak için N*M matriksi oluştururuz. Burada matriksin her (i,j) elemanı A(i) ve B(j) noktaları arasındaki mesafeyi içerir. Amaç ise çevrilen noktaların lokal mesafelerinin toplamını minimize edecek olan yolu matriks içinden bulmaktır.

- Sınır durumu: Bu deformasyon yolunun w(1)=(1,1) den başlayıp W(k)=(N,M) de bitmesini gerektirir.
- Süreklilik: deformasyon yolundaki atılabilecek adımları sınırlandırır.
Verilen w(k)=(a,b)’nn gerektirdiği w(k-1)=(c,d); a-c<1 ve b-d<1

- monotoniklik: Verilen w(k)=(a,b) ve w(k-1)=(c,d), burada ise a-c>0 ve b-d>0


DZD matriksindeki deformasyon yolu dizinler arasındaki parçalı mesafeleri akümüle eden dinamil programlama algoritması ile bulunur. Eğer D(i,j), (i,j)’ ye kadar olan global mesafe ise, (i,j) deki lokal mesafe d(i,j) ile verilir. DZD algoritması aşağıdaki eşitliği kullanır.

Xxxxxxxxxxxxxxxxxxxxxx (2.5)



Başlangıç durumu olarak verilen D(1,1)=d(A(1),B(1)), D(i,j)’ yi hesaplamak için elimizde verimli bir algoritma olmuş oluyor. Algortima D(1,1)’ den başlıyor ve kademeli olarak D(N,M)’ e kadar parçalı mesafeleri toplayarak itere ediyor. DZD algortimasının yapısı figür 2.5 ‘de verilmiştir. İki dizin A=[0,4,3,5,3,2,2,6,3] ve B=[0,3,3,5,5,2,2,6,1,0], DZD algoritması dizinlerin optimal eşlemesini bulur. Şimdiye kadar tanımlanan DZD algoritmasına göre, dizin elemanlarının sırasında değişikliğe izin verilmez ama iki dizinin elemanlarının sıkıştırılmasına ve genişletilmesine izin verilir.

Kabuki, şekil sınırı sunumunda, dizinin belli parçalarındaki sıkışma ve genişleme şeklin görsel halini değiştirir. Bu variyasyonlar şekil sınırlarının görsel olarak farklı taraflarının ayrımı bakımından anlamlı bilgi içerir. Bu sebepten, şekil durumunda, sıkıştırma ve genişletme konuşma durumuna göre daha çok anlamlıdır. Bu bizi deformasyon yolu elde etme aşamasında eşleşme işlemindeki sıkıstırma ve genişletme için metodların seçimine götürüyor. Bu da BAS fonksiyonlarının sıkıştırılması ve genişletilmesi için ceza verilmesi ile uygulanır. DZD matriksinde yatay ve dikey hareketler sabit bir ceza ile carpılır. Sonuçta açığa çıkan DZD algoritması aşağıdaki gibidir.


Xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


DZD algortimasının OCS algortimasından farkı oluşma ilişkisindedir. OCS’de, oluşma ilişkisi bağıl eşilemede silme ve eklemeyi kullanır. Diğer yandan DZD, genişletme ve sıkıştırma kullanır ve her bir operasyonun maliyeti lokal mesafedir. Fakat, DZD’ de metrik alsiyomların üçgen eşitsizliği başarısızdır.


2.5 Hesaplama Zamanının geliştirilmesi


OCS ve DTW algoritmaları N ve M uzunluklarındaki A ve B dizinleri arasındaki adanmış basit mesafeyi bulur. Hesaplama zamanı t, ve baskın terimi 3MNt dir.

M=N iken hesaplama zamanı 3(N*N)t’ ye düştüğü için algoritma zaman-quadrik diye adlandırılır.Geniş olan resim veritabanlarında hesaplama zamanında minimumu bulma ihtimali büyük bir avantaj olarak nitelendirilir.

Hesaplama zamanını geliştirmak için, bir yol ana görev “t” nin hesaplamasını düşürmektir. Diğer bir yol ise dizin karşılaştırma algoritmasının hesaplama zamanını düşürmektir. Bu, matriksin dış köşelerindeki hücreleri elemekle olur. Tabii ki, belli adamalar dikkate alınmamış oluyor fakat, birçok durumda, bunları dikkate almamak fazla birşey değiştirmez. Aslında, Dikkate alınmayan kısımlar gerçek dışı olduğu için onların elenmesi istenen birşeydir çünkü mesafeyi gerçekte ulaşılabilecek minimum değişiklikler olarak tanımlamak daha anlamlıdır.


2.6 Döngüsel Dizin Karşılaştırması


İki boyutlu bir objenin kapalı sınırı bir döngü olgusu oluşturur. Dolayısıyla, şekil sınırına daylı BAS fonksiyonu döngüsel dizin olarak düşünülür. İki BAS özelliğini adayabilmek için, başlangıç sınır noktası eşleştirilmiş olmalıdır. Bunun için her şekil için ayrı bir başlangıç noktası tanımlanmalıdır. Bu sebepten, adama hesabı, optimal çözümü bulmak için yapılan döngüsel kaydırmanın miktarını belirlemelidir.
Matematiksel olarak;

Xxxxxxxxxxxxxxxxxxxxx (2.6)


Xxxxxxxxxxxxxxxxxxxxxx (2.7)

Döngüsel dizin karşılaştırma problemini çözmenin en kolay yolu her defasında bir defa olmak üzere herhangi bir dizini kaydırmak ve eşlemyi hesaplamaktır. Bu, aşağıdaki gibi formule edilir;

Xxxxxxxxxxxxxxxxxxxx (2.8)


Döngüsel dizin karşılaştırmasına optimal çözüm bulmak içi başka yollar da vardır.Divide&Conquer Metodu ve kanal tekniğni kullanan başka yollar daha [101] ve [69] ‘da verilmiştir.

Çözümün kesin optimalitisini feda ederek, başka bir yolla problemi etkili bir şekilde ele alarak altoptimal bir çözüm de bulunabilir.

Burada [66]’ da verilen yaklaşık yaklaşımı BAS özelliklerinin döngüsel karşılaştırmasına adapte ederiz.
Döngüsel dizin karşılaştırmasına başlamak için, bütünlük açısından değerleri belirleyelim. İki dizin ele alalım. A=A(1)……A(N) ve B=B(1)…….B(M) .A dizininin M adet kolonu ve 2N adet yatay sütunu olan bir minimum mesafe tablosu olur. Gidiş yolları ilk kolonun ilk N adet giridlerinden başlar ve son kolonda farklı yerlerde biter. Mesafe tablosunda (i,j) girdisinden minimum mesafe yolunda toplam mesafe olarak D(i,j) tanımlayalım. D(i,j)’ nin değeri şöyle hesaplanır;
Xxxxxxxxxxxxxxxxx (2.9)

D(i,0)’ ın değerleri, i= 1,…,N A’ nın ilk noktasından başlayıp B’ nin son noktasında biten her başlama noktası “i” ‘ den minimum mesafe tablosundaki toplam mesafe yollarıdır. Minimum D(i,0) değerli yol tablodaki minimum mesafeli yoldur.

Xxxxxxxxxxxxxxxxxxxx (sayfa 34 deki tablo)


Şimdi BAS özellikleri için döngüsel dizin karşılaştırma algoritmalarını verebiliriz. Verilen R(q) ve R(t) gibi iki BAS özelliği, döngüsel dizin karşılaştırma metodu aşağıdaki algoritmadaki gibi özetlenebilir;

Xxxxxxxxxxxxxxxxxxxxxxxxxxxxx (sayfa 35 deki tablo)

Başlangıçta, sınır koşulları i=1,…..,2N-1 ve j=1,……,M-1 idi. Sonrasında algortima oluşum ilişkisini değerlendirerek itere eder ve sonuçta I 1’den N’e kadar minimum D(i,0) bulunur. Matrik içindeki yatay ve dikey değişikliklerde sabit bir ceza ile çarptığımızı unutmayalım. Teorik olarak bu cezanın pek bir nedeni olmasa da, bu konudaki tartışmaaşağıda olduğu gibi verilir.

A ve B gibi iki dizin alalım. [66]’ da verilen algoritma Dc(A,B)=D(Z,B) ‘ yi hesaplar. Burada Z (A*A)’ nın altdizinidir. Hesaplamada minimum mesafe yolunun uzunluğu üzerinde hiçbir kontrol yoktur.dolayısıyla, Z’nin uzunluğu A’ nın uzunluğundan çok farklı olabilir. Bu, eşleme uygulamasında iki tartışmaya yol açar;

- Algoritma B’ye karşı A’ nın parçalı eşlemesini hesaplar. Halbuki, amacımız dizinler arasındaki toplam mesafeyi ölçmektir.
- Algortima optimal çözümü yaklaşık olarak bulur ve kesin döngüsel mesafe için bir alt sınır belirler. DTW algortimasında 7 olarak bulunan toplam eşleme sonucu, döngüsel dizin karşılaştırma algoritmasında 4 olarak bulunuyor.

Algortimamız yatay ve dikey hareketlerde ceza verir ve Z’nin uzunluğunu kontrol etmeye çalışır. Bu yolun diyagonal olarak gitmesini sağlar ve Z’nin uzunluğunu A’ nın uzunluğuna yaklaştırır. Bu yolla, iki dizin arasındaki tüm alakayı tahmin edebiliriz ve eşleme sonucunu stimule ederek optimal sonucu yaklaşık olarak bulabiliriz.

Ceza uygulamasının bir başka sebebi DTW durumunda yaptığımız sebep ile aynıdır. Dizinin bazı parçalarındaki sıkıştırma ve genişletme sınır şeklinin görünüşünü değiştirdiği için, deformasyon yolunu öyle ayarlamalıyız ki, sıkıştırma ve genişletme miktarı eşleme uygulamasıyla sınırlı kalsın. Bu dizinlerin sıkıştırılmasında ve genişletilmesinde ceza verilerek uygulanır.


2.7 Konunun Özeti


Bu konuda, BAS özellik vektörünün benzerlik ölçümünde kullanılan algortimaları inceledik. Özellik vektörleri için iki farklı dizin karşılaştırma metodu verildi;

- Bağıl altdizin algoritmaların optimal alakası
- Dinamik zaman deformasyonu

Kapalı şekil sınırının yapısı döngüsel olduğu için, optimal çözümü yaklaşık olarak bulan etkili döngüsel dizin karşılaştırma algortiması geliştirilmiştir.
- Döngüsel dizin karşılaştırma algoritması


Bu metodların tamamındaki amaç, iki vektor arasındaki mesafeyi deformasyona izin vererek minimize etmektir. Bunu yapmak için, ilk olarak özellik vektörlerinin elemaları arasındaki alaka problemi çözülür ve sonra mesafe, alakalı elemanlar arasındaki hataların toplamı olarak hesaplanır.