VESøKALIK FOTOöRAFLARIN

Yorumlar

Transkript

VESøKALIK FOTOöRAFLARIN
EGE ÜNøVERSøTESø FEN BøLøMLERø ENSTøTÜSÜ
(YÜKSEK LøSANS TEZø)
VESøKALIK FOTOöRAFLARIN SINIFLANDIRILMASI øÇøN
ÖZELLøK ÖLÇÜTLERø ÜZERøNE KIYASLAMALI BøR
ÇALIùMA
Sinem ASLAN
Uluslararası Bilgisayar Anabilim Dalı
Bilim Dalı Kodu : 619.02.04
Sunuú Tarihi : 08.08.2007
Tez Danıúmanı : Prof. Dr. Turhan Tunalı
BORNOVA - øZMøR
III
Sinem ASLAN tarafından YÜKSEK LøSANS TEZø olarak sunulan
“Vesikalık Foto÷rafların Sınıflandırılması øçin Özellik Ölçütleri
Üzerine Kıyaslamalı Bir Çalıúma” baúlıklı bu çalıúma E.Ü. Fen
Bilimleri Enstitüsü E÷itim ve Ö÷retim Yönergesi’nin ilgili hükümleri
uyarınca tarafımızdan de÷erlendirilerek savunmaya de÷er bulunmuú ve
08.08.2007 tarihinde yapılan tez savunma sınavında aday
oybirli÷i/oyçoklu÷u ile baúarılı bulunmuútur.
ømza:
Jüri Üyeleri:
Jüri Baúkanı : Prof. Dr. Turhan Tunalı
.......................
Raportör Üye: Yrd. Doç. Dr. Cengiz Güngör
.......................
Üye
.......................
: Yrd. Doç. Dr. Aylin Kantarcı
V
ÖZET
VESøKALIK FOTOöRAFLARIN SINIFLANDIRILMASI øÇøN
ÖZELLøK ÖLÇÜTLERø ÜZERøNE KIYASLAMALI BøR
ÇALIùMA
ASLAN, Sinem
Yüksek Lisans Tezi, Uluslararası Bilgisayar Enstitüsü
Tez Yöneticisi: Prof. Dr. Turhan TUNALI
A÷ustos 2007, 96 sayfa
Günümüzde, özellikle internet kullanımının yaygınlaúması ile, geniú
boyuttaki çokluortam veritabanlarının etkili bir úekilde yönetilmesi önem
kazanmıútır. Bu sebeple, etkili bir çokluortam yönetimi için çeúitli,
çokluortam verilerinden öznitelik çıkartma, veritabanı indeksleme ve
çokluortam verisi sınıflandırma uygulamaları geliútirilmiútir.
Bu tez çalıúmasında, literatürde yüz tanıma probleminin çözümü
için kullanımına sıkça yer verilmiú olan Baúlıca Bileúenler Çözümlemesi
ve Do÷rusal Ayrıútırma Çözümlemesi öznitelik çıkartma yöntemleri,
etkin bir indeksleme yapısı kullanan MUVIS çoklu ortam indeksleme
sistemine entegre edilmiú ve vesikalık foto÷raflardan oluúan bir resim
veritabanı üzerinde bu yöntemler ile, MUVIS sisteminde mevcut olan
Gabor Filtresi öznitelik çıkartma yönteminin sınıflandırma performansı
karúılaútırılmıútır.
Anahtar sözcükler: MUVIS, Baúlıca Bileúenler Çözümlemesi, Do÷rusal
Ayrıútırma Çözümlemesi, Hiyerarúik Hücresel A÷aç, yüz resimlerinin
sınıflandırılması
VII
ABSTRACT
A COMPARATIVE STUDY OF FEATURE METRICS FOR
CLASSIFICATION OF HUMAN PASSPORT PHOTOS
ASLAN, Sinem
MSc. in International Computer Institute
Supervisor: Prof. Dr. Turhan TUNALI
August 2007, 96 pages
Due to widespread use of the Internet, efficient management of
multimedia databases has attracted many researchers. Variety of
techniques including database indexing, classification and feature
extraction are developed.
In this thesis, Principal Component Analysis (PCA) and Linear
Discriminant Analysis (LDA) methods that have been widely used for
face recognition problem in literature, are integrated to MUVIS, a
multimedia indexing and classification system with an effective indexing
structure. PCA and LDA are integrated into MUVIS and their
classification performance on a human passport photo database is
compared with that of Gabor Filter that already exists in MUVIS.
Keywords: MUVIS, Principal Component Analysis, Linear Discriminant
Analysis, Hierarchical Cellular Tree, classification of face photographs
VIII
IX
TEùEKKÜR
Tez çalıúmamın, engin akademik tecrübesi ve yönlendirmeleri ile
úekillenmesini ve zenginleúmesini sa÷layan saygıde÷er hocam Prof. Dr.
Turhan Tunalı’ya, özverisi, katkıları ve bu çalıúma ile akademik hayata
bir adım atmamı sa÷ladı÷ı için çok teúekkür ederim.
Tez çalıúmam sırasında, MUVIS sistemi ile ilgili sorularımı
cevapsız bırakmayan MUVIS takımı üyesi Sayın Serkan Kıranyaz’a,
takıldı÷ım ve çıkıú noktası göremedi÷im durumlarda, bana yeni
tavsiyelerde bulunarak fikir veren ve ilerlememe yardım eden Sayın
Yard. Doç. Dr. Muhammed Cinsdikici’ye teúekkürü bir borç bilirim.
Zor anlarımda deste÷ini esirgemeyen sevgili mesai arkadaúlarıma
ve kız kardeúime teúekkürlerimi sunarım.
Bu çalıúmayı, her türlü özveriyi göstererek bana güzel bir çalıúma
ortamı sa÷layan sevgili annem ve babama adıyorum.
X
XI
øÇøNDEKøLER
Sayfa
ÖZET........................................................................................................ V
ABSTRACT ...........................................................................................VII
TEùEKKÜR ............................................................................................ IX
øÇøNDEKøLER........................................................................................ XI
ùEKøLLER DøZøNø.............................................................................. XIII
ÇøZELGELER DøZøNø ..........................................................................XV
KISALTMALAR ................................................................................. XVI
1
GøRøù ................................................................................................ 1
2
øLGøLø ÇALIùMALAR .................................................................... 4
2.1
MUVIS ...................................................................................... 4
2.2
Yüz Tanıma ............................................................................... 5
2.2.1
Bütünsel-tabanlı yöntemler ............................................... 6
2.2.1.1 Renk histogramları: ....................................................... 6
2.2.1.2 Baúlıca Bileúenler Çözümlemesi (BBÇ ): ..................... 9
2.2.1.3 Do÷rusal Ayrıútırma Çözümlemesi (DAÇ):................ 12
2.2.2
Özelli÷e-dayalı yöntemler ............................................... 15
2.2.2.1 Gabor filtresi: .............................................................. 15
2.2.3
Karma yöntemler............................................................. 17
2.3
øndeksleme ve Sınıflandırma................................................... 18
2.3.1
Uzaysal Eriúim Yöntemleri (UEY) ................................. 18
2.3.2
Metriksel Eriúim Yöntemleri (MEY) .............................. 19
2.3.3
Hiyerarúik Hücresel A÷aç (HHA) ................................... 22
2.3.3.1 Hücre yapısı: ............................................................... 22
2.3.3.2 Seviye yapısı: .............................................................. 24
2.3.3.3 HHA iúlemleri: ............................................................ 26
2.3.3.4 HHA indeksleme: ........................................................ 27
3
MUVIS øLE YÜZ TANIMA........................................................... 31
3.1
Baúlıca Bileúenler Çözümlemesi ............................................. 31
3.1.1
Yöntem ............................................................................ 31
3.1.2
Özyüz uzayının MUVIS’de kullanımı ............................ 35
3.2
Do÷rusal Ayrıútırma Çözümlemesi ......................................... 37
3.2.1
Yöntem ............................................................................ 37
3.2.2
Ayrıútırma uzayının MUVIS’de kullanımı ..................... 39
4
PERFORMANS ÖLÇÜTLERø ....................................................... 40
XII
4.1
Kullanılan Yüz Resimleri Veritabanı ......................................40
4.2
Kullanılan HHA Parametre De÷erleri......................................41
4.3
Her Hücredeki Kiúi Yo÷unlu÷u Testi ......................................42
4.4
9+1 Testi ..................................................................................43
4.5
Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı ........................44
4.6
Kırkar Resimlik On Devir Testi...............................................45
4.7
Sınıflandırma Baúarımı Testi ...................................................47
4.8
BBÇ Duyarlık Testi .................................................................48
5
TEST SONUÇLARI ........................................................................53
5.1
Hücrelerdeki Kiúi Yo÷unlu÷u Testi.........................................53
5.2
9+1Testi ...................................................................................55
5.3
Bir Kiúinin Resim Da÷ılımı .....................................................59
5.4
Kırkar Resimlik On Devir Testi...............................................62
5.5
Sınıflandırma Baúarımı Testi ...................................................71
6
SONUÇ............................................................................................74
KAYNAKLAR DøZøNø...........................................................................77
EKLER.....................................................................................................83
Ek 1 MUVIS ........................................................................................84
Temel MUVIS Uygulamaları ..............................................................84
DbsEditor .........................................................................................85
MBrowser ........................................................................................86
MUVIS’de Görsel Öznitelik Çıkarımı.................................................87
FeX iskeleti ......................................................................................88
FeX veri yapıları ..............................................................................89
Modüllerdeki kullanıcı arayüzü fonksiyonları.................................89
MUVIS’de öznitelik çıkartma iúlemleri ..........................................90
Resim öznitelik dosya formatı .........................................................92
Ek 2 Türkçe - øngilizce Terimler Sözlü÷ü ...........................................94
ÖZGEÇMøù .............................................................................................96
XIII
ùEKøLLER DøZøNø
Sayfa
ùekil 2.1 Yüz resminden yüz vektörü oluúturma ...................................... 9
ùekil 2.2 Yüz uzayı ................................................................................. 10
ùekil 2.3 Boyut Küçültme ....................................................................... 11
ùekil 2.4 Alt uzaya yansıma .................................................................... 12
ùekil 2.5 M-A÷aç durumları.................................................................... 21
ùekil 2.6 HHA Seviye yapısı................................................................... 24
ùekil 2.7 C1 ve C2 hücrelerine birleútirme iúlemi uygulanması ............. 29
ùekil 4.1 Kullanılan yüz resimleri veritabanından bir kesit .................... 41
ùekil 4.2 Örnek her hücredeki kiúi yo÷unlu÷u test sonucu ..................... 42
ùekil 4.3 Örnek 9+1 test sonucu.............................................................. 43
ùekil 4.4 Örnek kiúiye ait resimlerin hücrelere da÷ılımı test sonucu...... 44
ùekil 4.5 Örnek kırkar resimlik on devir test grafi÷i............................... 46
ùekil 4.6 Örnek sınıflandırma baúarımı test grafi÷i ................................ 48
ùekil 4.7 Girdi Resmi .............................................................................. 49
ùekil 4.8 Özuzay oluúturulurken kullanılan veritabanındaki resim sayısı:
400 , kullanılan özvektör sayısı: 400....................................................... 49
ùekil 4.9 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 10 , kullanılan özvektör sayısı: 10 , (b) kullanılan veritabanındaki
resim sayısı: 400 , kullanılan özvektör sayısı: 10.................................... 50
XIV
ùekil 4.10 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 80 , kullanılan özvektör sayısı: 80 , (b) kullanılan veritabanındaki
resim sayısı: 400 , kullanılan özvektör sayısı: 80 ....................................50
ùekil 4.11 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 120 , kullanılan özvektör sayısı: 120 , (b) kullanılan
veritabanındaki resim sayısı: 400 , kullanılan özvektör sayısı: 120 ........51
ùekil 4.12 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 240 , kullanılan özvektör sayısı: 240 , (b) kullanılan
veritabanındaki resim sayısı: 400 , kullanılan özvektör sayısı:240 .........51
ùekil 5.1 Her hücredeki kiúi yo÷unlu÷u test sonucu................................54
ùekil 5.2 9+1 Test sonucu (a) 120 Özvektörlük yüz uzayı kullanan
BBÇ, (b) Gabor filtresi, (c) 240 Özvektörlük yüz uzayı kullanan
BBÇ, (d)DAÇ ..........................................................................................57
ùekil 5.3 9+1 Ara Aúamaları....................................................................59
ùekil 5.4 Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı Test Sonucu
(a) 52’nin üzerinde de÷erler alan noktaları da içeren grafi÷in genel
görüntüsü, (b) 52’nin altındaki de÷erler için yakınlaútırılmıú (a) grafi÷i 61
ùekil 5.5 Kırkar Resimlik On Devir Test Sonucu ...................................70
ùekil 5.6 Sınıflandırma Baúarımı Test Sonucu........................................73
Ek 1 ùekil 1 MUVIS iskeletinin genel yapısı ..........................................84
Ek 1 ùekil 2 MUVIS DbsEditor Uygulaması ..........................................85
Ek 1 ùekil 3 MUVIS Mbrowser Uygulaması ..........................................86
Ek 1 ùekil 4 MUVIS uygulamaları ile FeX modül etkileúimi .................88
XV
ÇøZELGELER DøZøNø
Sayfa
Tablo 4.1 HHA oluútururken kullanılan parametreler ............................ 42
Tablo 5.1 Öznitelik Çıkartma Yöntemleri øçin Sınıflandırma Baúarımı
Test Sonuçları.......................................................................................... 72
Ek 1 Tablo 1.Örnek resim öznitelik dosyası formatı .............................. 93
XVI
KISALTMALAR
BBÇ
DAÇ
EB-Çekirdek
FAÇ
HHA
MEY
MÖA
TUT
UEY
: Baúlıca Bileúenler Çözümlemesi
: Do÷rusal Ayrıútırma Çözümlemesi
: En Benzer Çekirdek
: Fisher Ayrıútırma Çözümlemesi
: Hiyerarúik Hücresel A÷aç
: Metriksel Eriúim Yöntemleri
: Minimum Örten A÷aç
: Tampere University of Technology
: Uzaysal Eriúim Yöntemleri
1
1 GøRøù
Günümüzde özellikle internet kullanımının yaygınlaúmasından
sonra fazla miktardaki çoklu ortam verisinin kullanımının
kolaylaútırılmasına ve dolayısıyla çoklu ortam veritabanlarının etkili bir
úekilde indekslenmesi ve saklanmasına olan ihtiyaç artmıútır. Bu yüzden,
akademik çevrelerce çeúitli çalıúmalar yapılarak, bu probleme çözüm
aranmıútır.
øndeksleme üzerine gerçekleútirilmiú olan bu çalıúmalar uzaysal ve
metriksel eriúim tabanlı olmak üzere ikiye ayrılabilir. Uzaysal eriúim
tabanlı yöntemler, nesnelerin temsilleri olan úekilleri çok boyutlu uzayda
etkili bir úekilde saklamayı amaçlarken, metriksel indeksleme yöntemleri
indeksleme için metrik özellikleri gösteren benzerlik uzaklı÷ı
fonksiyonuna gereksinim duydu÷u için bu metri÷in hesaplanma süresini
kısaltarak etkinli÷i arttırmayı amaçlar.
Bu tez çalıúmasında kullanılan, MUVIS (TUT Muvis Xt Projesi,
internet eriúimi) takımı tarafından geliútirilen, bir metriksel eriúim
yöntemi olan Hiyerarúik Hücresel A÷aç (HHA), dinamik, hücre tabanlı
ve hiyerarúik olarak tasarlanmıú olan bir indeksleme yöntemi olmakla
birlikte, etkili bir sınıflandırma imkanı sunmaktadır. Bununla birlikte,
veritabanı elemanlarına uygulanması istenen herhangi bir çoklu ortam
öznitelik çıkartma yöntemi, MUVIS’in DbsEditor adlı modülüne entegre
edilerek kullanılabilmektedir.
MUVIS sisteminin sahip oldu÷u bu özellik, onu çeúitli öznitelik
çıkartma yöntemlerinin çalıútırılarak, sınıflandırma üzerindeki etkisinin
gözlenebilece÷i mükemmel bir iskelet sistem haline getirmektedir. Bu
sebeple, bu tez çalıúmasında, çeúitli öznitelik çıkartma yöntemlerinin
sınıflandırma üzerine etkisi araútırılırken bu sistem tercih edilmiútir.
Bu sistemin üzerinde sınıflandırma etkisi incelenen resim çeúidi ise
yüz resimleri olmuútur. Bir kiúiye ait yüz özellikleri onu di÷erlerinden
farklı ve eúsiz kılan önemli ayırt edici özelliklerinden birisidir ve bu
sebeple özellikle güvenlik alanında olmak üzere yüz tanıma
uygulamalarının kullanımı son yıllarda oldukça yaygınlaúmıútır.
Kullanılan yüz tanıma uygulamalarına verilebilecek olan bir örnek,
güvenlik merkezlerinde suçlu tanıma sistemlerinde, daha önceden suç
sicili bulunan kiúilerin yüz kaydı tutuldu÷unda, suç iúleme sonucu
yakalanan bir kiúinin yüz resmi çekilerek bu kayıtlar arasında yer alıp
2
almadı÷ı araútırılarak o kiúiye ait suç siciline ulaúılması olabilir. Bu
senaryoda, suçlu tanıma sisteminde kayıtlı olan suçlulara ait yüz
resimlerinin etkili bir úekilde saklanması ihtiyacı, özellikle resim sayısı
arttıkça fazlalaúır. Bu probleme bir çözüm, belli formattaki yüz
resimlerinden oluúan veritabanından etkili yöntemler ile yüzün
karakteristik özelliklerini taúıyan öznitelik vektörleri çıkartılarak, bu
resimlerin etkili bir yöntemle indekslenmesini sa÷lamak olabilir. Bu
indeksleme sonucunda, bir kiúiye ait tüm resimler aynı ortamda
toparlanabilirse, sonraki aramalarda o kiúinin tüm resimlerine ulaúım
daha kolay ve masrafsız olacaktır.
Bu tez çalıúmasında, bu senaryodan yola çıkılarak, pasaport
foto÷rafı formatında resimler içeren bir veritabanındaki yüz resimlerinin
etkili bir úekilde sınıflandırılması amaçlanmaktadır. MUVIS takımının
daha önce gerçekleútirmiú oldu÷u resimlerden Gabor filtresi ile öznitelik
çıkartma yöntemi, literatürde yüz tanıma problemi üzerine yapılan
çalıúmalarda sıkça yer almaktadır. Bu çalıúmada, yüz tanıma problemi
için yaygın bir úekilde kullanılmıú olan di÷er iki yöntem olan Baúlıca
Bileúenler Çözümlemesi (BBÇ) ve Do÷rusal Ayrıútırma Çözümlemesi
(DAÇ), MUVIS sistemine entegre edilerek Gabor filtresinin
sınıflandırma baúarımı üzerine çıkmak hedeflenmiútir.
Buna ek olarak, yüz resimleri üzerinde çalıúılırken kullanılan
öznitelik çıkartma yöntemlerinin sınıflandırma üzerindeki etkisini ortaya
koyan çeúitli performans ölçütleri geliútirilmiútir. Bu ölçütler ile, ilgili
öznitelik çıkartma yöntemi kullanılarak HHA ile gerçekleútirilen
indekslemeden sonra oluúan a÷acın, bir hücresinde bir kiúiye ait
resimlerin bulunma yo÷unlu÷unu ortaya koymak amaçlanmaktadır.
Bölüm 2’de öncelikle, literatürde yüz tanıma problemi için
gerçekleútirilmiú baúlıca yöntemler hakkında bilgi verilerek, kullanılmıú
olan temel kavramlar açıklanacaktır. Bunun sonrasında, çoklu ortam
indeksleme üzerine gerçekleútirilmiú olan çalıúmalar tanıtılarak, bu tez
çalıúmasında kullanılmıú olan indeksleme yöntemi hakkında detaylı bilgi
verilecektir.
Bölüm 3’de tez kapsamı dahilinde gerçekleútirilmiú olan çalıúmalar
açıklanacaktır. Bu bölümde uygulanan öznitelik çıkartma yöntemlerinin
algoritmik detaylarına yer verilecektir.
Bölüm 4’de sınıflandırma baúarımını ortaya koymak üzere
geliútirilmiú olan performans ölçütleri örnek test sonuçları ve yorumlarına
yer verilerek tanıtılacaktır.
3
Son olarak Bölüm 5’de, sonuç ve tartıúma yer alacak ve bu tezde
elde edilen sonuçlar kullanılarak bundan sonra yapılabilecek çalıúmalar
önerilecektir.
4
2 øLGøLø ÇALIùMALAR
Bu bölümde, bu tez çalıúmasında kullanılan çoklu-ortam
indeksleme ve eriúim sistemi olan MUVIS tanıtılarak, bu platformda
gerçekleútirilmiú olup yüz resimleri veritabanına uygulanabilecek olan
resim öznitelik çıkartma yöntemleri ile literatürde yer alan yüz tanıma
yöntemleri hakkında bilgi verilmiútir. Yüz tanıma probleminin çözümüne
yönelik yöntemler ile ilgili bilgi verildikten sonra, çok sayıda yüz
resminden oluúan veritabanında resimlere etkin bir úekilde eriúim imkanı
sa÷layabilecek indeksleme yöntemleri açıklanarak, bu çalıúmada
kullanılmıú olan sistemin sahip oldu÷u indeksleme yapısı ayrıntılı bir
úekilde incelenecektir.
2.1 MUVIS
MUVIS,
90lı
yılların
sonlarında,
Tampere
Teknoloji
Üniversitesinde, geniú resim veritabanlarının, renk, doku ve úekil gibi
görsel ve anlamsal öznitelikler kullanarak indekslenmesini ve eriúimini
sa÷layan bir Java uygulaması olarak geliútirilmiútir (Kiranyaz, 2005).
Baúlangıçta geliútirilmiú olan bu sistem temel alınarak, ses/video klipleri
ve resimlerin yakalanması, kaydedilmesi, farklı öznitelikler ile
indekslenmesi, sorgu yoluyla ve veritabanı taranarak eriúilmesi gibi
eklentiler ile daha geniú kullanımlı yeni bir uygulama çatısı elde
edilmiútir.
MUVIS, öznitelik (feature) çıkarma algoritmalarının entegre
edilerek sisteme kazandırılmasını sa÷lar ve böylece yeni öznitelik
çıkarma yöntemlerinin geliútirilmesi ve test edilmesi için bir deneme
platformuna sahip olunur. Etkin bir çoklu-ortam indeskleme yöntemi
kullanan MUVIS’in yeni öznitelik yöntemleri kullanmada sa÷ladı÷ı bu
kolaylık tez çalıúmasında bu sistemi tercih etmemize sebep olmuútur.
Bu uygulama platformu, Windows iúletim sistemi için tasarlanmıú
olan üç temel uygulama içermektedir (Kiranyaz, 2005):
AVDatabase: Gerçek zamanlı video / ses veritabanı yaratıcısı
DbsEditor: Veritabanı düzenleme uygulaması
5
MBrowser: Eriúim ve tarama uygulaması
Bu tez çalıúmasında, DbsEditor ve MBrowser modülleri
kullanılmıútır. MUVIS modüllerinin genel yapısı ve MUVIS’e öznitelik
çıkartma yöntemlerini ekleme iúlemlerinin ayrıntıları EK 1’de verilmiútir
2.2
Yüz Tanıma
Kiúinin sahip oldu÷u yüz özellikleri, onu di÷erlerinden farklı ve
eúsiz kılan çok önemli ayırd edici özelliklerinden birisidir. Bu sebeple,
baúlangıçta askeri uygulamalarda, kiúinin kimli÷inde oluúabilecek
úüpheleri tamamen ortadan kaldırmak için kullanılan yüz tanıma
teknolojileri, günümüzde güvenli÷in öneminin hızla artması dolayısıyla
geniú kullanım alanı bulacak teknolojilerden biri olacaktır.
Yüz tanıma uygulamaları, güvenlik tedbirlerinin sa÷lanmak
istendi÷i bir ortamda alınan video görüntülerindeki insan yüzlerinin
otomatik
olarak
algılanması
ve
takip
edilmesi
úeklinde
gerçekleútirilebilece÷i gibi, boyutu gittikçe artacak bir veritabanında
belirli úartlarda çekilmiú pasaport foto÷rafı formatındaki insan yüzü
foto÷raflarının, benzer formata getirilmiú ilgili yüz foto÷rafları ile
karúılaútırılması úeklinde de gerçekleútirilebilmektedir.
Bir otomatik yüz tanıma sistemi, yukarıda bahsedilen uygulama
alanlarında kullanılırken, foto÷raftaki yüz bölgesinin tespit edilmesi,
ıúıklandırma farklılıklarından veya gürültüden kaynaklanan yanılmaları
engellemeye yönelik öniúlemler ve sonuçta elde edilen yüz bölgesi ile
kimlik tespiti yapma olmak üzere üç temel iúlem gerçekleútirir (Hesher,
2003).
Bu tez çalıúmasında, yüz bölgeleri çıkartılmıú foto÷raflar
kullanılaca÷ı için ilk iúlem üzerinde durulmamıútır. Bahsedilen üçüncü
iúlemin gerçekleútirilmesi aúamasında yüz resimlerinden bazı yöntemler
ile yüz bölgesinin karakteristik özelliklerini ifade eden öznitelikler
çıkarılmaktadır ve yüz resimleri arasındaki benzerlik araútırması
yapılırken bu öznitelikler kullanılmaktadır.
6
Herhangi bir resim veritabanının elemanlarından çıkartılan
öznitelikler, genel öznitelikler ve alana özel öznitelikler olarak iki sınıfa
ayrılabilir (Rui, Huang ve Chang, 1999). Genel öznitelikler, renk, doku
ve úekil özniteliklerini kapsarken, alana özel öznitelikler insan yüzleri ve
parmak izleri tanıma gibi uygulama-ba÷ımlıdır.
Ayrıca, bir Otomatik Yüz Tanıma (Automatic Face Recognition)
sisteminin en önemli bileúenlerinden birisi olan yüz bölgesinden
öznitelikler çıkarılması iúlemi üzerinde çalıúılırken üç temel yaklaúım
kullanılmaktadır (Zhao et al., 2003):
i.
Bütünsel-tabanlı (Holistic-based) Yöntemler
ii.
Özelli÷e Dayalı (Feature-based) Yöntemler
iii.
Karma (Hybrid) Yöntemler
Bu bölümde yüz bölgesi çıkartılmıú resimlerden, resim
indekslemeye ve yüz tanımaya temel oluúturacak olan genel ve alana özel
öznitelik çıkarma yöntemleri, yukarıdaki üç temel yaklaúım esas alınarak
açıklanacaktır.
2.2.1 Bütünsel-tabanlı yöntemler
Bu tip yöntemler kullanılırken, bir yüz tanıma sistemine, yüz
bölgesi bilgisinin tamamı bir vektör haline getirilerek verilir. Bu bölümde
yüz tanımada kullanılan baúlıca bütünsel-tabanlı yöntemler hakkında
bilgi verilecektir.
2.2.1.1 Renk histogramları:
Renk histogramları, oluúturulması ve kullanımı basit bir yöntem
oldu÷u için resim tanımada sıkça kullanılmıútır. Yüz tanımada ise renk
histogramları genellikle, baúka tipdeki öznitelikler ile birlikte, do÷rulu÷u
geliútirmek amacıyla kullanılmaktadır (Marcel ve Bengio, 2002 ), (Nastar
ve Mitschke, 1998).
7
En sık kullanılan renk özniteli÷i gösterim yöntemi renk
histogramlarıdır. Bir M resmindeki renkleri n adet renk içeren ayrık renk
uzayına eúlersek, H(M) renk histogramı, her hc j elemanı, M resmindeki
c j renginin piksel sayısını belirten ( hc1 , hc2 ,..., hcn ) vektöründen oluúur. M
resminin N piksel taúıdı÷ını düúünürsek
n
¦h
ci
N olur.
i 1
Renk indeksleme üzerine yapılan ilk çalıúmalarda L1 -metri÷i
kullanılmaktaydı (Swain ve Ballard, 1991). H ve I renk histogramları
arasındaki L1 uzaklı÷ı (2.1)’deki gibi tanımlanmaktadır.
n
d L1 ( H , I )
¦| h
ci
i ci |
( 2.1)
i 1
Bu metrik ile, birbirine benzer renk histogramlarına sahip olan tüm
resimlere ulaúılamıyordu, çünkü bu metrik bölmeler (bin) arasındaki renk
benzerli÷ini dikkate almıyordu.
(Niblack ve Barber, 1993) tarafından 1993’ de geliútirilen L2
metri÷i renk histogramlarında bulunan binler arasındaki renk benzerli÷ini
dikkate almaktadır. Bu metrik “Öklid Uzaklı÷ı (Euclidean Distance)”
olarak da bilinir ve (2.2)’deki gibi ifade edilir.
n
d L21 ( H , I )
¦ (h
dl
idl ) 2
(2.2)
l 1
Ço÷u renk histogramının da÷ınık yapılı ve dolayısıyla gürültüye
karúı oldukça hassas olması üzerine (Stricker ve Orengo,1995) tarafından
kümülatif renk histogramları kullanılması önerilmiútir. Bir M resminin
~ ~
~
~
kümülatif renk histogramı olan H ( M ) hc1 , hc2 ,..., hcn , H(M) terimleri
cinsinden (2.3)’deki gibi tanımlanır.
~
hc j ¦ hcl
(2.3)
cl d c j
Bu histogramlar arasındaki benzerlik (2.4), (2.5) ve (2.6)’ dan birisi
kullanılarak belirlenmektedir (Stricker ve Orengo,1995):
8
~ ~
d L1 ( H , I )
n
~
¦| h
cj
~
ic j |
(2.4)
j 1
n
~ ~
¦ (hc j ic j )
~ ~
d L2 ( H , I )
2
(2.5)
j 1
~
~
maks | hc j ic j |
~ ~
d Lf ( H , I )
1d j d n
(2.6)
Kümülatif renk histogramları kullanmak do÷rulu÷u arttırmıútır,
fakat bunlar çok büyük boyutlu vektörler oldukları için bellek ihtiyacı
artmıú ve eriúim hızı yavaúlamıútır. Kümülatif renk histogramları,
momentleri ile temsil edili÷inde maliyet sorunu çözülür. j. resim
pikselindeki i. renk kanalının de÷eri pij olmak üzere, (Stricker ve
Orengo,1995) bu amaç için (2.7), (2.8) ve (2.9) ile gösterilen histogram
özelliklerinin kullanılabilece÷ini belirtmiútir:
Birinci Moment: Resmin ortalama rengi
1
N
Ei
N
¦p
(2.7)
ij
j 1
økinci Moment: Her kanalın varyansı
Vi
(
1
N
N
¦( p
ij
Ei ) 2 )1/ 2
(2.8)
j 1
Üçüncü Moment: Her kanalın çarpıklı÷ı (skewness)
si
(
1
N
N
¦( p
ij
Ei )3 )1/ 3
(2.9)
j 1
1 d l , k d 3 iken wkl t 0 kullanıcının belirledi÷i a÷ırlık katsayıları
olmak üzere r renk kanalına sahip, sırayla E i ve Fi birinci momenti, V i
9
ve 9 i ikinci momenti, s i ve t i üçüncü momenti olan iki resmin H ve I
renk da÷ılımları arasındaki benzerlik (2.10)’daki gibi tanımlanabilir
(Stricker ve Orengo,1995):
r
d mom ( H , I )
¦w
i1
| Ei Fi | wi 2 | V i 9 i | wi 3 | si ti |
(2.10)
i 1
2.2.1.2 Baúlıca Bileúenler Çözümlemesi (BBÇ ):
Yüz resimlerinin küçük-boyutlu uzayda karakterize edilmesi fikri
ilk olarak (Sirovich ve Kirby, 1987) tarafından önerilmiútir. Daha sonra
(Turk ve Pentland, 1991), Karhunen-Loéve veya istatistikte Baúlıca
Bileúenler Çözümlemesi (Principal Component Analysis) olarak da
bilinen özuzay yansıması kullanarak bir yüz tanıma çalıúması
gerçekleútirmiútir.
Geniúli÷i g, uzunlu÷u u olan bir yüz resmi, bileúen sayısı g u u olan
bir vektör úeklinde ifade edilebilmektedir. Resmin her piksel de÷eri,
vektörün bir bileúeni ile gösterilmektedir. Bu vektör oluúturulurken ùekil
2.1’de gösterilen yöntem izlenir. Yüz resminin her satır piksel bilgisi
birbiri ardına eklenerek ilgili vektör elde edilmiú olur.
ùekil 2.1 Yüz resminden yüz vektörü oluúturma
Elde edilen bu yüz vektörü, g u u piksel büyüklü÷ündeki tüm
resimlerin yer aldı÷ı “resim uzayına (image space)” aittir. Tüm yüz
resimlerindeki göz, a÷ız, burun sayısının eúit olması ve bu özelliklerin
10
benzer yerlerde yer alması sebebiyle tüm yüz vektörleri bu resim
uzayında ùekil 2.2’de gösterildi÷i gibi çok küçük bir bölgeyi iúgal eder.
ùekil 2.2 Yüz uzayı
Bu sebeple, yüz tanımlanırken resim uzayının tamamını kullanmak
yerine, yüzleri daha iyi tanımlayabilen bir alt uzay kullanmak daha uygun
olur. øúte bu alt uzaya “yüz uzayı (face space)” ve bu uzayın sahip oldu÷u
temel vektörlere baúlıca bileúenler adı verilmektedir. Yüz uzayının
boyutu, resim uzayınınkinden çok daha küçüktür.
BBÇ’nin amacı, bir kümenin veya uzayın boyutunu, yeni
eksenlerin kümenin modelini daha iyi tanımlamasını sa÷layacak úekilde
küçültmektir. Burada küme modelini, veritabanında bilgisine önceden
sahip olunan e÷itim kümesi resimleri oluúturmaktadır ve yüz uzayının
eksenleri veya özvektörler ortogonal ve veri noktaları arasındaki de÷iúimi
maksimize edecek úekilde olacaktır.
11
1
2
2
1
1
ùekil 2.3 Boyut Küçültme
Örne÷in ùekil 2.3’deki birinci baúlıca bileúen, iki veri grubunun bu
do÷ru çevresinde birbiriyle iliúkisini göstermektedir. økinci baúlıca
bileúen, veri noktaları arasındaki daha az öneme sahip de÷iúimin yönünü
ortaya koymaktadır.
Özvektörler oluúturulduktan sonra özde÷erleri büyükten küçü÷e
olacak úekilde sıralanırsa, özvektörlerin veriyi modellemedeki önem
sırası elde edilir ve daha az öneme sahip özvektörler kullanımdan
çıkarılabilir. Bu durumda, özde÷erler küçükse, küçük bir miktar bilgi
kaybı olur. Bazı özvektörler kullanımdan çıkarıldı÷ında, veri toplulu÷u
daha az boyutla ifade edilir duruma gelecektir. Bu yöntemin bu özelli÷i,
resim sıkıútırmada kullanılmasına olanak sa÷lamıútır.
Bir yüz resminin, özvektörlerin oluúturdu÷u “Yüz Uzayı” olarak
adlandırılan alt uzaya yansıtılması o resmin en önemli özelliklerini
taúıyan daha küçük boyutlu bir gösteriminin elde edilmesini
sa÷layacaktır.
Veritabanındaki her resim, oluúturulan yüz uzayına yansıtıldı÷ında
her resim için bir a÷ırlık vektörü elde edilir. Her resmin sahip oldu÷u bu
a÷ırlık vektörü, o resmin öznitelik vektörü olarak kullanılır.
Bir yüz resmi, bu úekilde bulunan kendisine ait a÷ırlık vektörü
de÷erleriyle çarpılıp toplandı÷ında yeniden oluúturulabilir. Bu durum
elektrik mühendisli÷inin temel konularından biri olan “Fourier
Analizine” benzer. Fourier Analizine göre bir sinyal farklı frekanslardaki
sinosoidlerin belirli a÷ırlıklarla çarpılıp toplanması sonucu elde
edilebilmektedir.
12
2.2.1.3 Do÷rusal Ayrıútırma Çözümlemesi (DAÇ):
Fisher Ayrıútırma Çözümlemesi (FAÇ) olarak da adlandırılan
Do÷rusal Ayrıútırma Çözümlemesi (Linear Discriminant Analysis), daha
küçük boyutda yeni bir alt uzay oluútururken, aynı türdeki veri
noktalarını biraraya toplayan ve farklı türdeki veri noktalarını birbirinden
ayıran do÷ruları bulmaya çalıúır (Gutierrez-Osuna, internet eriúimi).
BBÇ
DAÇ
ùekil 2.4 Alt uzaya yansıma
Bir sınıfta, bir kiúiye ait farklı ıúık úartlarında veya yüz
mimiklerinde çekilmiú yüz resimleri bulunmaktadır. Resimler N (N:
resimdeki piksel sayısı) boyutlu uzaydan, M - 1 (M: veritabanındaki
farklı sınıf sayısı) boyutlu uzaya yansıtılır. Özyüzler yönteminden farkı,
alt uzayın hesaplanma úeklidir.
Fisher Ayrıútırma Çözümlemesi, yüz resimlerinde farklı ıúık
úartlarında gerçekleútirilmiú çekimlerden kaynaklanan aydınlanma
farklılıklarının yüz tanıma üzerindeki etkisini azaltma amacıyla
(Belhumeur et. al, 1997) tarafından önerilmiútir.
DAÇ’de, sınıflar arasındaki ayrıútırma analizini, Sınıflar-arası
( S SA ) ve Sınıf-içi ( S Sø ) Yayılım Matrisleri kullanılarak formülarize edilir.
Sınıf-içi Yayılım Matrisi (Within Class Scatter Matrix), tüm
sınıfların, kendi ortalamaları etrafındaki yayılımını göstermektedir. x bir
yüz vektörünü, (2.11) ile formülarize edilen mi i. sınıfın satır piksel
13
ni i. sınıftaki resim sayısını, C
veritabanındaki sınıfları ve C i i. sınıfı göstermek üzere Sınıf-içi Yayılım
Matrisi (2.12) ve (2.13)’de gösterildi÷i gibi hesaplanır:
ortalamalarını içeren vektörü,
(mi
Si
1
ni
¦ x)
(2.11)
xCi
( x mi )( x mi ) T
(2.12)
C
S Sø
¦S
(2.13)
i
i 1
Di÷er yandan, Sınıflar-arası Yayılım Matrisi (Between Class
Scatter Matrix), sınıf ortalamalarının, tüm veritabanı ortalaması
etrafındaki yayılımını göstermektedir. N sınıf sayısını ve (2.14)’de
verilen m veritabanındaki resimlerin satır piksel ortalamalarını içeren
vektörü gösterecek úekilde Sınıflar-arası Yayılım Matrisi de (2.15)’de
gösterildi÷i gibi hesaplanır:
(m
1
N
N
¦m )
(2.14)
i
i 1
C
S SA
¦ n (m
i
i
m)(mi m) T
(2.15)
i 1
Sınıfları birbirinden ayrıútırma kriterini formülleútirebilmek için bu
matrislerin birer sayıya dönüútürülebilmesi gerekmektedir (Fukunaga,
1990). Bu sayı, Sınıflar-arası Yayılım Matrisi büyüdükçe ve Sınıf-içi
Yayılım Matrisi küçüldükçe maksimum de÷erine ulaúır ve dolayısıyla en
do÷ru ayrıútırma bilgisine sahip olunur.
Bu ayrıútırma kriterinin hesaplanıúı üzerine çeúitli çalıúmalar
yapılmıútır. Literatürde kullanılan baúlıca ayrıútırma kriteri Fisher
yöntemi olmuútur. Bu bölümde bu yöntem ayrıntılı bir úekilde
incelenecektir. Kullanılmıú olan di÷er yöntemler hakkındaki detaylı
bilgiye, (Sebestyen, 1962) ve (Fukunaga, 1990) incelenerek ulaúılabilir.
14
DAÇ ile yapılmak istenen, daha önce de bahsedildi÷i gibi veri
noktalarından aynı sınıftakileri biraraya toplayan ve farklı sınıftakileri
birbirinden ayrıútıran alt uzayı baúka bir deyiúle w yansıma vektörlerini
bulmaktır. Sonuç olarak x yüz vektörlerinin, y ayrıútırma do÷ruları ile
gösterilmesini sa÷layacak bir W yansıma matrisi bulunmak
istenmektedir:
yi
T
WTX
wi xi Ÿ Y
Yüz vektörleri için (2.11), (2.13), (2.14) ve (2.15)’de mi sınıf
ortalamalarının, m veritabanı ortalamasının ve S SA ve S Sø matrislerinin
nasıl hesaplanaca÷ı açıklanmıútı. Buna benzer úekilde, hesaplanan alt
uzaya yansıma iúlemi yapıldıktan sonra elde edilen ayrıútırma do÷ruları
~ veritabanı ortalaması (2.16), (2.17)’de ve
~ sınıf ortalamaları, m
için m
i
yayılım matrisleri (2.18) ve (2.19)’de tanımlanır.
~
m
i
~
m
~
S SI
1
¦ y
N i ywi
1
¦ y
N yi
(2.16)
(2.17)
C
¦ ¦ ( y m~ )( y m~ )
i
T
i
(2.18)
i 1 ywi
~
S SA
C
¦ N (m~
i
i
~ )(m
~ m
~)T
m
i
(2.19)
i 1
~
~
(2.18) ve (2.19)’da, S SI W T S SI W ve S SA
tanımlanabilir (Gutierrez-Osuna, internet eriúimi).
W T S SAW úeklinde
Yansıma iúleminden sonra, Sınıflar-arası Yayılım Matrisinin
Sınıf-içi Yayılım Matrisine oranı bir sabit olamayaca÷ı için, (2.20)’de
gösterildi÷i gibi yayılım matrislerinin determinantı kullanılabilir.
15
J (W )
~
S SA
~
S SI
| W T S SAW |
| W T S SI W |
(2.20)
(2.21)’deki Genelleútirilmiú Özde÷er Problemi (Generalized
Eigenvalue Problem) çözüldü÷ünde elde edilen en büyük özde÷ere sahip
özvektörler W matrisinin sütunlarını oluúturmaktadır.
­| W T S W | ½
arg maks ® T SA ¾ Ÿ ( S SA Oi S SI ) wi
¯ | W S SI W | ¿
0
(2.21)
2.2.2 Özelli÷e-dayalı yöntemler
Bu tip yöntemler kullanılırken, bir yüz tanıma sistemine, gözler,
burun, a÷ız gibi yerel yüz bölgeleri bilgisi etkili bir úekilde ifade edilerek
girdi olarak verilir. Bu bölümde yüz tanımada kullanılan baúlıca özelli÷edayalı yöntemler hakkında bilgi verilecektir.
2.2.2.1 Gabor filtresi:
2-Boyutlu Gabor dalgacık (wavelet) gösterimi üzerine önde gelen
çalıúmalar (Daugman,1980) tarafından gerçekleútirilmiútir. Gabor
fonksiyonları ile, yüz resmi üzerindeki göz, a÷ız, burun sınırları gibi yüze
dair önemli bölgelerin yanı sıra ben, gamze, yara izi gibi bölgeler de
güçlendirilerek ön plana çıkarılır. Dolayısıyla; bu güçlendirilmiú noktalar
ile her yüz resmi için bir özellik haritası çıkartılabilir ve her yüz resmi
kendi karakteristik özellikleri ile temsil edilmiú olur.
Memelilerin birincil görsel korteksinde bulunan hücre tepkilerini
modelleyen Gabor dalgacıkları, μ ve v Gabor çekirdeklerinin (kernel)
yönünü ve büyüklü÷ünü, ||.|| norm iúlemini göstermek ve z=(x,y) olmak
üzere (2.22)’deki gibi tanımlanır (Liu ve Wechsler, 2001).
16
<P , v ( z )
|| k P ,v || 2
V
2
e
||k P , v ||2 || z ||2
2V 2
2
V
ª ik z
«e P , v e 2
«¬
(2.22)’deki, k P ,v dalga vektörü, k P ,v
IP
º
»
»¼
kv e
(2.22)
iI P
úeklinde tanımlanır.
SP / 8 ve k maks maksimum frekans, f freakans uzayında çekirdekler
arasındaki aralık çarpanı olmak üzere, kv
k maks / f v olur.
(2.22) ile tüm Gabor çekirdekleri, ana dalgacık olarak
isimlendirilen bir filtreden, k P ,v dalga vektörü etrafında ölçeklendirilerek
ve döndürülerek üretilebilir.
Yüz resmi tanımada, Gabor dalgacıkları genellikle beú farklı
v  {0,....,4} ölçek (scale) ve sekiz farklı yön (orientatiton)
P  {0,....,7} ile kullanılmaktadır.
Bir resmin Gabor dalgacık gösterimini bulmak için, o resmin bu
Gabor çekirdekleri ile konvolüsyon iúleminden geçirilmesi gerekir. I(x, y)
bir resmin gri seviyeli da÷ılımı ise, z=(x, y), ve konvolüsyon
operatörünü göstermek üzere, I resminin ve bir <P ,v Gabor çekirde÷inin
konvolüsyonu (2.23)’deki gibi tanımlanır:
OP ,v ( z )
I ( z ) <P ,v ( z )
(2.23)
Bu iúlemin çıktısı olan OP ,v ( z ) farklı konumda, ölçekte ve
yöndeki öznitelikleri içermektedir ve bu özniteliklerin hepsi X öznitelik
vektörünü elde etmek için kullanılır. Öznitelik vektörü oluúturulmadan
önce, uzay boyutunu azaltmak için her OP ,v ( z ) bir U çarpanı ile
örneklenir. Beú ölçek ve sekiz yönlü gabor çekirde÷i kullanılarak elde
edilen X ( U ) Gabor öznitelik vektörü, T transpoz iúlemini göstermek
üzere, (2.24)’deki gibi tanımlanır:
X (U )
T
(O0( ,U0) O0( ,U1)
T
T
... O4( ,U7) ) T
(2.24)
17
2.2.3 Karma yöntemler
Bu yöntemler yüz tanıma problemine çözüm ararken, bütünsel
yöntemler ile özelli÷e dayalı yöntemleri birlikte kullanır. Bütünsel
yöntemler ve özelli÷e dayalı yöntemlerin her birinden daha fazla bilgiye
sahip olunaca÷ı için, bu yöntemlerin do÷rulu÷u daha yüksek olan
sonuçlar vermesi beklenebilir.
Bu yöntemlere bir örnek olarak (Pentland et al., 1994)’ın
gerçekleútirmiú oldu÷u, özyüzler ile birlikte öza÷ız, özgözler ve özburun
gibi yerel öznitelikleri kullanan modüler özyüzler yöntemi verilebilir. Bu
çalıúmada gerçekleútirilen testlerde, küçük boyutlu uzaylarda, yerel
özniteliklerin, özyüzlerden daha iyi sonuç verdi÷i görülmüútür. Bu iki
yüz tanıma yöntemi birleútirildi÷inde ise çok az bir geliúme elde
edilmiútir. Bu testler, özellik çıkarmaya dayalı yöntemlerin, girdi
resimleri arasında büyük de÷iúiklikler oldu÷u durumlarda daha kullanıúlı
olaca÷ı sonucunu vermektedir.
ùimdiye kadar geliútirilmiú olan otomatik yüz tanıma sistemleri ile
kıyaslanamayacak derecede baúarılı tanıma gerçekleútiren insan beyni,
yüz tanıma iúlemini gerçekleútirirken, bütünsel ve özelli÷e dayalı
karúılaútırma yöntemlerinin her ikisini birlikte kullanmaktadır. Karma
yöntemlerin çıkıú noktası insan beyninin bu özelli÷ini modellemek
olmuútur (Zhao et al., 2003).
Bütünsel karúılaútırma tabanlı yaklaúımlar tanıma iúlemini hızlı bir
úekilde gerçekleútirirken, bu yöntemlerin sa÷ladı÷ı ayrıútırma bilgisi çok
geniú veritabanları için yeterince zengin olmayabilir ve bu yetersizlik
yerel özellik yöntemleri kullanılarak tamamlanabilir. Ancak, bu tipte bir
birleúik sistemin gerçekleútirilmesi için önce cevaplanması gereken bazı
sorular bulunmaktadır. Bunlardan ilk akla geleni, bütünsel ve özelli÷e
dayalı karúılaútırma yöntemlerinin hangi a÷ırlıklarda uygulanaca÷ıdır.
Ayrıca özniteliklerin nasıl belirlenece÷i ve nasıl kullanılaca÷ı konusu,
üzerinde araútırma yapılmaya hala açık olan konulardır (Zhao et al.,
2003).
18
2.3 øndeksleme ve Sınıflandırma
Günümüzde geniú boyutlu çokluortam veritabanlarının kullanım
alanı oldukça artmıútır ve bu durum, bellek kullanımı ve veritabanı
elemanlarına eriúim hızı açısından etkin kullanım imkanı sa÷layacak
veritabanı yönetim yapılarına ihtiyaç do÷urmuútur.
Geçmiúte, bir resim veritabanında, bir resme eriúmek için Örnek ile
Sorgu (Query by Example) yöntemi ile benzerlik hesabı yapılmaktaydı
(Kiranyaz ve Gabbouj, 2007). Veritabanı boyutu büyüdükçe bu yöntemin
kullanımı, maliyeti çok fazla arttırdı÷ı için sorgu süresini azaltarak eriúim
hızını arttıran indeksleme yöntemlerine ihtiyaç duyulmuútur. Bu
yöntemler ile veritabanı elemanlarından, kendi karakteristik özelliklerini
gösteren öznitelik vektörleri çıkartılarak bu vektörler belli bir indeksleme
yönteminin kurallarına göre bilgisayar diskinde saklanmaktadır veya
veritabanı elemanlarına eriúim bu vektörler kullanılarak indeksleme
yönteminin sahip oldu÷u belli kurallar ile sa÷lanmaktadır.
Geliútirilmiú olan indeksleme yöntemleri, Uzaysal Eriúim
Yöntemleri (Spatial Access Methods) ve Metriksel Eriúim Yöntemleri
(Metric Access Methods) olmak üzere iki ana grupta toplanabilir.
2.3.1 Uzaysal Eriúim Yöntemleri (UEY)
UEY, çeúitli nesnelerin temsilleri olan geometrik úekilleri çok
boyutlu uzayda saklayan indeks yapılarıdır. (Gaede ve Günther, 1998)
UEY ile ilgili oldukça iyi bir kaynaktır ve detaylı bilgi için incelenebilir.
UEY’nin ilk örnekleri KD ve R-A÷aç yapılarıdır. KD-A÷aç, özellik
vektörlerinin da÷ılımından ba÷ımsız olarak, özellik uzayını önceden
tanımlanmıú olan hiper düzlemlere ayıran uzay-parçalama yöntemleri
kullanır (Bentley, 1975). R-A÷aç yapısında ise özellik uzayı veritabanı
elemanlarının da÷ılımına ba÷lı olarak parçalara ayrılır (Guttman, 1984).
R -A÷aç, R-A÷açdan farklı olarak, bir nesneyi gerekti÷inde birden
fazla dala ekleyerek, üstüste çakıúmayı engellemeye çalıúır.
R*-a÷aç yapısı “yeniden eklemeye zorlama” olarak isimlendirilen
bir kural ile çalıúarak, R ve R -A÷aca göre daha iyi bir performans elde
19
etmektedir (Sellis , Roussopoulos ve Faloutsos, 1987). (Lin et al., 1994)
açılıp büyütülen vektörler olarak isimlendirilebilen TV-A÷aç yöntemini
önermiútir. Bu vektörler, sorgu iúlemi için sadece yüksek varyanslı
boyutların önemli oldu÷u varsayılarak, dinamik olarak kısaltılabilir.
(Berchtold et al, 2000) büyük boyutlu veriyi indekslemek üzere
tasarlanmıú olan X-A÷acı önermiútir. X-A÷aç, yeni bir klasör düzenlemesi
kullanır ve böylece TV-A÷aç ve R*-A÷açdan çok daha iyi performans
verir. Bunlar haricinde, literatürde önerilmiú olan di÷er UEY-A÷aç
yöntemleri, SR-A÷aç (Katayama ve Satoh, 1997), S²-A÷aç (Wang ve
Perng, 2001), Hibrit-A÷aç (Chakrabarti ve Mehrotra, 1999), A-A÷açdır
(Sakurai et. al., 2000). Özellikle geniú boyutlu çokluortam veritabanları
için UEY’nin bazı dezavantajları bulunmaktadır. Bir çokluortam
veritabanı birden fazla özellik çeúidine (ses, görüntü, vs...) sahip
olabilirken, UEY bir tek özellik uzayı üzerinde çalıúır. Bu yöntemler, az
boyutlu özellik uzayında nispeten iyi sonuçlar verirken, çok boyutlu
özellik uzayında “boyutluluk sorunu (curse of dimensionality)” yüzünden
iyi sonuçlar vermez (Kıranyaz, 2005).
2.3.2 Metriksel Eriúim Yöntemleri (MEY)
Bu yöntemler, indeksleme için sadece simetri, negatif-olmama ve
üçgen eúitsizli÷i kurallarına uyan bir benzerlik uzaklı÷ı fonksiyonuna
gereksinim duyar. Bu sayede, bir çoklu-ortam veritabanı çeúitli alt özellik
kümeleri içerebilen birkaç özellik çeúidine sahip olabilir.
Önerilmiú olan MEY’lerden bazıları vp-a÷aç (Yianilos, 1993),
mvp-a÷aç (Bozkaya ve Ozsoyoglu, 1997), GNAT (Brin, 1995)’ dır.
ùimdiye kadar bahsedilen MEY’lerin bazı eksik yanları bulunmaktadır.
UEY’lerin tersine, bu metrik a÷açları, disk sayfası eriúim maliyeti sorunu
ile ilgilenmemiú, sadece benzerlik uzaklı÷ı hesaplama sayısını azaltmak
üzere tasarlanmıútır. Bu yöntemlerin dezavantajı, statik yapıda olmaları,
yani a÷aç yapısının sadece bir kere oluúturularak yeni eleman eklemeye
imkan vermemesidir. Ayrıca a÷açlar yukarıdan aúa÷ıya do÷ru
oluúturulaca÷ı için, a÷acın dengeli olup olmayaca÷ı konusunda garanti
verilememektedir. Bu sorunlara çözüm getirmek amacıyla (Ciaccia et al.,
1997) M-A÷aç yapısını önermiútir. M-A÷aç, aúa÷ıdan yukarı do÷ru
oluúturulan dengeli ve dinamik bir a÷açtır. Dü÷üm büyüklü÷ü sabit bir
20
sayıdır (M) ve bu yüzden a÷aç uzunlu÷u M’e ve veritabanı büyüklü÷üne
ba÷lıdır. M-a÷acın bir di÷er çeúidi M+ -A÷açdır (Zhou ve Wang, 2003).
M-A÷açda maksimum sabit bir M sayısı büyüklü÷üne sahip
olabilecek olan dü÷ümler ile çalıúılması zorunlulu yüzünden, performans,
bu parametrenin veritabanı büyüklü÷üne göre düzgün seçilmesine ba÷lı
olmaktadır.
M-A÷açda hücre içerisindeki elamanların benzerlik durumları
gözetilmeksizin, sadece, hücre büyüklü÷ü M de÷erine ulaúıldı÷ı an hücre
bölünmesi iúlemi gerçekleútirilmektedir. Bölünme iúlemi için, M-A÷aç
öncelikle uygun çekirdek elemanlarını bulmaya çalıúır ve daha sonra bu
eleman çevresinde yeni hücreler oluúturur.
M-A÷aç, yeni eleman ekleme sırasında “EB-Çekirdek (MSNucleus)” hücre araması kullanılır ve elemanların eklenmesi sırası agacın
oluúma úeklini de÷iútirebilir.
M-A÷aç ve türevlerinde kullanılan bu “EB-Çekirdek” arama
yöntemi, yeni bir eleman eklenirken, yukarıdan aúa÷ıya do÷ru taranan
a÷acın, eklenen elemana en yakın çekirdek elemanının en do÷ru alt-a÷acı
gösterece÷ini varsayar.
M-A÷aç durumları:
d ( ) benzerlik hesaplayan fonksiyon, O eklenecek eleman, O Ni , i.
hücrenin çekirde÷i ve r (ONi ) bu çekirde÷e sahip olan hücrenin yarıçapı ve
Ci , i. hücreyi göstermek üzere, M-A÷aç’da en üstteki seviyeden aúa÷ıya
do÷ru uygun hücre aranırken ùekil 2.5’de gösterilen iki durumla
karúılaúılır. Dikkat edilirse, her iki durumdada bir alt seviyedeki en yakın
çekirdek elemanı do÷ru bir úekilde tespit edilememektedir.
21
ùekil 2.5 M-A÷aç durumları
Durum 1:
d (O, O Ni ) d r (ONi )Ci için hiçbir hücre çekirde÷i bulunamazsa, bir
i
i
alt seviyede, en küçük ' i d (O, ON ) r (ON )Ci de÷erini sa÷layan C
hücresine eklenir.
Durum 2:
d (O, ONi ) d r (ONi )Ci sa÷layan bir hücre çekirde÷i varsa, bir
alt seviyede bunun oluúturdu÷u alt-a÷aç taranır. Bu úartı sa÷layan birden
fazla hücre çekirde÷i elemanının bulunması durumunda O’nun en yakın
oldu÷u hücre çekirde÷inin alt a÷acı taranır, sonuç olarak en yakın hücre
çekirde÷ine sahip hücreye eklenir.
M-A÷açta, hücre çekirde÷i herhangi bir hücre iúleminden sonra
güncellenmez. Bu da a÷aç yapısında bozulmalara sebep olabilir. Bu
durum bir sonraki bölümde açıklanacak olan MUVIS’de kullanılan
Hiyerarúik Hücresel A÷aç yapısında düzeltilmiútir.
Ayrıca, bir hücre bölünmesi sonrasında, yeni oluúan hücre
çekirdekleri bir üst seviyede, her zaman eski hücre çekirde÷inin yerini
alırken, HHA’da durum böyle olmaz. HHA’da bir hücre bölündü÷ünde,
bölünen hücrenin çekirde÷i bir üst seviyeden silinir ve ortaya çıkan iki
yeni hücre çekirde÷i bir üst seviyede eski hücre çekirde÷inden ba÷ımsız
olarak en uygun hücreye yerleútirilir.
22
2.3.3 Hiyerarúik Hücresel A÷aç (HHA)
Hiyerarúik Hücresel A÷aç (Hierarchical Cellular Tree), (Kıranyaz,
2005) tarafından geniú çoklu-ortam veritabanları için tasarlanmıú olan,
dinamik, hücre-tabanlı ve hiyerarúik olarak yapılanmıú bir indeksleme
yöntemidir. Elemanlar, birbirlerine olan uzaklıklarına ba÷lı olarak
birbirinden ayrılırken, benzerlik yakınlıklarına göre hücreler içerisinde
saklanır. Aynı zamanda, HHA, eleman ekleme, silme, bölünme...vs gibi
iúlemlerin dıúardan de÷il, bazı kurallar ile her seviye içinde kontrol
edildi÷i, kendi kendini yöneten bir indeksleme yöntemidir ve bir seviyede
gerçekleúen iúlemlerin sonuçları di÷er seviyeler üzerinde bazı baúka
iúlemlerin baúlamasına sebep olabilir. Bu tetiklenen iúlemlerin her biri,
bir yukarıdaki seviyede gerçekleúece÷i ve bir HHA gövdesinin sınırlı
sayıda seviyesi bulundu÷u için, bu iúlemler tanımsız bir süre boyunca
devam etmez.
2.3.3.1 Hücre yapısı:
Hücre (cell), benzer veritabanı elemanlarının saklandı÷ı temel
yapıdır. Her hücre içerisinde, dü÷ümlerini hücre içerisindeki elemanların
oluúturdu÷u Minimum Örten A÷aç (Minimum Spanning Tree), MÖA,
yapısı bulunmaktadır. MÖA dallarının a÷ırlı÷ını, hücre elemanlarının
özellik vektörleri arasındaki Normalize edilmiú Öklit Uzaklı÷ı oluúturur.
MÖA’nın di÷er tamamen ba÷lı çizgelerden farkı dal a÷ırlıklarının her
birinin minimize edilmiú olmasıdır. Fakat bu, tüm yolların minimize
edildi÷i anlamına gelmez. MÖA, çizgeyi ba÷lamak için gerekli olan
minimum sayıda dal kümesidir ve hiç dönüú içermez.
HHA’da kullanılmıú olan MÖA algoritması dinamiktir.
Dolayısıyla, hücre içerisindeki elemanların birbirine olan uzaklıklarının
önceden bilinmesine gerek yoktur (Kıranyaz, 2005). Hücre içerisindeki
bu uzaklık istatistikleri esas olarak hücre yo÷unluk özelli÷ini çıkarmak
için kullanılır. Hücre içerisinde herhangi bir elemanın sadece belli bir
elemana olan uzaklı÷ı yerine di÷er tüm elemanlara olan uzaklı÷ı dikkate
alındı÷ı için daha gerçekci bir hücre yo÷unlu÷u özelli÷i elde edilir. Hücre
yo÷unluk özelli÷i, herhangi bir anda hücre içerisinde mitoz iúleminin
gerçekleútirilip gerçekleútirilmeyece÷i kararında kullanılabilir. E÷er
mitoz iúleminin gerçekleútirilebilece÷i onayı alınırsa, bölünmenin
23
nereden yapılaca÷ına MÖA kullanılarak karar verilir ve en büyük a÷ırlı÷a
sahip olan dal kırılır. MÖA ayrıca hücre çekirde÷inin belirlenmesinde rol
oynar.
Hücre çekirde÷i (cell nucleus), hücrede kendisine en fazla sayıda
dal ba÷lanmıú olan elemandır. Dolayısıyla hücre çekirde÷i için, “hücre
içerisindeki elemanların ço÷unun kendisine en yakın mesafede
bulundu÷u tek elemandır” tanımı yapılabilir. Hücre çekirde÷i, ait oldu÷u
hücreyi bir üst seviyede temsil eder. Her hücre iúleminden sonra hücre
çekirde÷i bilgisi dinamik olarak güncellenir ve bu iúlem, MÖA sayesinde
herhangi bir hesaplama maliyeti olmaksızın gerçekleútirilir. Hücrede
sadece bir eleman varsa, bu eleman hücre çekirde÷i olarak kabul edilir.
HHA’da hücre büyüklü÷ü esnek tutulmuútur, yani hücre
büyüklü÷ünün bir üst sınırı yoktur. Ancak hücre büyüklü÷ü, miktarı a÷aç
oluúturulurken kullanıcı tarafından belirlenen bir olgunluk seviyesi
(maturity level) de÷erine eriúmeden, hücre bölünmesine izin verilmez.
Böyle bir koúul konulmasaydı, hücre içerisindeki elemanlar ve MÖA
yapısından yeterli istatistiksel bilgi alınamayaca÷ı için hücrenin
bölünmeye hazır olup olmadı÷ı konusunda güvenilir bir bilgi elde
edilemezdi.
Hücre yo÷unlu÷u (cell compactness) özelli÷i, hücre içerisindeki
elemanlar için sınıflandırmanın ne kadar do÷ru yapıldı÷ı hakkında fikir
verir. Hücrenin yo÷unluk özelli÷i hakkında bir model oluúturan f
fonksiyonu, P C ve V C hücre içerisindeki Minimum Örten A÷aç dal
a÷ırlıklarının ortalamasını ve standart sapmasını, rC hücre çekirde÷inden
hücre içerisindeki en uzak elemana olan mesafeyi, wC dal uzunlu÷unu ve
N C hücre içerisindeki eleman sayısını temsil etmek üzere (2.25)’deki
gibi gösterilir:
CFC
f ( P C , V C , rC , maksimum ( wC ), N C ) t 0
(2.25)
(2.25)’de, CFC hücrenin yo÷unluk özelli÷idir. Dolayısıyla, eleman
eklendikce N C artarken, di÷er istatistiksel parametreler minimize
edilerek iyi bir yo÷unluk de÷eri elde edilebilir. En ideal durumda yani
hücre içerisindeki tüm elemanların birbirinin aynısı iken en iyi derecede
yo÷unluk elde edilir. Limitde CFC = 0 olur.
24
Hücre bölünmesinin (cell mitosis) gerçekleúmesi için hücrenin
olgunluk seviyesine ulaúması ( N C ! N M ) ve hücre yo÷unlu÷unun,
hücrenin bulundu÷u seviyenin yo÷unluk eúi÷inden büyük olması gerekir
(CFC ! CThr L ) . Bu iki koúul, hücre içerisinde gerçekleútirilen her
iúlemden (eleman ekleme, eleman silme, ...vs) sonra kontrol edilir. Bu
úartlar sa÷landı÷ında hücre bölünür ve hücre çekirde÷inin belirlenmesi,
yeni hücreler içerisindeki Minimum Örten A÷aç yapısı, seviye yo÷unluk
eúi÷i gibi bilgiler güncellenir. Hücre bölünmesi en büyük a÷ırlı÷a sahip
olan dalın kırılmasıyla gerçekleútirilir.
2.3.3.2 Seviye yapısı:
ùekil 2.6 HHA Seviye yapısı
25
ùekil 2.6’da görüldü÷ü gibi, Hücresel A÷aç, bir veya daha fazla
sayıda seviyenin (level) oluúturdu÷u hiyerarúik bir yapıya sahiptir ve bu
seviyeler, içerisinde benzer veritabanı elemanları bulunan bir veya daha
fazla sayıda hücre içermektedir. En üstteki seviye sadece bir hücre içerir
ve bu hücre bölündü÷ünde, bu seviyenin üzerinde yeni bir seviye
oluúturulur. Daha öncede belirtildi÷i gibi bir seviyedeki her hücrenin
çekirde÷i, bir üstteki seviyede yer alarak o hücreyi temsil eder.
Hiyerarúik Hücresel A÷aç gövdesini oluúturan seviyeler, kendisi
üzerinde gerçekleúen tüm iúlemlerin kaydını (bölünme iúlemi sayısı,
hücrelerin yo÷unlu÷u, ...vs) tutar ve her seviye sahip oldu÷u hücrelerin
yo÷unlu÷unu dinamik olarak en büyük de÷ere ulaútırmaya çalıúır. Bu, her
zaman düzgün bir úekilde sa÷lanamayabilir, yani yeni eklenen elemanlar
hücredekilere benzemeyebilir ve bu benzer olmayan elemanların
hücrelere eklenmesi, seviyenin ortalama yo÷unlu÷unda kötüleúmeye
sebep olur. Bunun sonucu olarak bir seviye, bir yandan, yeni eklenen
elemanların, o seviye yo÷unlu÷una etkisini analiz ederken, di÷er yandan,
gelecek zamanda yo÷unlu÷u geliútiren bir trend oluúturmak için gerekli
yönetimi sa÷lamalıdır. Bu amaçla, her seviye, de÷eri kullanıcı tarafından
girilen bir zaman periyodunda sahip oldu÷u olgun hücrelerin yo÷unluk
de÷erini esas alarak, yo÷unluk eúi÷i (compactness threashold) de÷erini
günceller. Bu güncelleme (2.26)’da verilen fonksiyon ile gerçekleútirilir
(Kiranyaz ve Gabbouj, 2007):
CThrL
1
Medyan(CFC | C  S M )
k0
(2.26)
(2.26)’da, S M Hiyerarúik Hücresel A÷aç gövdesinde bulunan
olgun hücreler kümesini ve k 0 , en son hesaplanan CThrL ’dan itibaren
gerçekleútirilen eklemeler için hedeflenen yo÷unluk e÷ilim çarpanını
(compactness trend factor) göstermektedir.
k 0 1 iken, gelecek eklemeler için hiçbir yo÷unluk geliútirme
hedeflenmeyerek, mevcut yo÷unluk seviyesinin bozulmadan kalmasını
sa÷layacak bir e÷ilim oluúturulmuú olur. Di÷er yandan, k 0 o f iken,
hücreler olgunlu÷a ulaútı÷ı an bölünme gerçekleúecektir.
26
2.3.3.3 HHA iúlemleri:
Eleman ekleme, eleman silme ve hücre bölünmesi baúlıca HHA
iúlemleridir. Hücre bölünmesi di÷er iki iúlem gerçekleútirildi÷inde iúlemsonrası kontrolü (post-processing) sonucu gerçekleúebilir.
Eleman ekleme:
HHA eleman ekleme algoritması, elemanı uygun hücreye eklemek
için, HHA’da en tepeden hedeflenen seviyeye sırayla inerek arama yapan
Öncelikli Hücre Arama (Pre-emptive Cell Search) yöntemini uygular.
Uygun hücre bulundu÷unda eleman bu hücreye eklenir ve iúlem-sonrası
kontrolleri gerçekleútirilir. Bu iúlem sonrası kontrolleri, hücre yo÷unlu÷u,
hücre çekirde÷i bilgisi ve hücrenin bölünmeye u÷rayıp u÷ramayaca÷ı
kontrolleridir. Elemanın eklendi÷i hücrenin olgunluk seviyesi ve
yo÷unluk bilgisi kontrol edilerek bölünüp bölünmeyece÷i kararı verilir.
E÷er hücre bölünmeye u÷rayacaksa, oluúan yeni iki hücre için yeni
yo÷unluk de÷erleri ve hücre çekirdekleri belirlenir. Bunun sonrasında, bir
üst seviyedeki eski hücre çekirde÷i silinir ve bu seviyeye iki yeni hücre
çekirde÷i yerleútirilir. E÷er hücre bölünmesi gerçekleúmezse, hücre
çekirde÷i bilgisi güncellenir.
Üzerinde durulması gereken önemli bir konu, yeni eleman eklerken
uygun hücreyi bulmak için uygulanan “Öncelikli Hücre Arama”
algoritmasıdır (Kiranyaz, 2005). Bu algortima, M-A÷açda kullanılan EBÇekirdek algoritmasının karúılaútı÷ı durumlarda úu úekilde hareket eder:
d ( ) benzerlik hesaplayan fonksiyon, O eklenecek eleman, O Ni , i.
hücrenin çekirde÷i ve r (O Ni ) bu çekirde÷e sahip olan hücrenin yarıçapı
ve Ci , i. hücreyi göstermek üzere (ùekil 2.5):
Durum 1:
d (O, O Ni ) d r (O Ni )C i için hiçbir hücre çekirde÷i bulunamazsa
(eklenmek istenen eleman bir hücrenin kapsama alanı içerisinde
bulunamıyorsa), bir alt seviyede, eklenecek elemana en yakın elemana
sahip
olan
hücrelerin
hücre
çekirdekleri
27
(' i d (O, O Ni ) r (O Ni ) d d min C i )
benzerli÷e bakılır.
alınır
ve
bunlarla
arasındaki
Durum 2:
d (O, O Ni ) d r (O Ni )C i sa÷layan bir veya birden fazla hücre
çekirde÷i varsa, bir alt seviyede bu hücre çekirdeklerinin ait oldu÷u
hücrelere bakılır ve eklenecek elemana en yakın elemana sahip olan
hücrelerin hücre çekirdekleri alınır ve bunlarla arasındaki benzerli÷e
bakılır.
Karúılaúılan bu iki durumda, HHA’nın kullandı÷ı Öncelikli Hücre
Arama algoritması, M-A÷acın kullandı÷ı EB-Çekirdek algoritmasından
farklı olarak, yeni bir eleman eklerken, o eleman ile bir seviyedeki
hücrelerin sahip oldu÷u hücre çekirdekleri arasında en yakın oldu÷u
hücre çekirdeklerinin bir alt seviyede ait oldu÷u hücrenin hücre
çekirde÷ine de÷il hücre içerisindeki herhangi bir elemana olan yakınlı÷ını
araútırır.
Bu yöntemle, hedef seviyenin bir üzerindeki seviyede iúlem son
bulur ve en benzer olan hücre çekirde÷i ve eklenecek hücre elde edilir.
Öncelikli Hücre Arama algoritması esas alınarak yeni eleman eklemenin
gerçekleútirilmesi daha iyi bir hücre yo÷unluk özelli÷ine sahip
olunmasına olanak tanır.
Yapılan testler sonucunda bu arama algoritmasının iyi sonuç
verdi÷i görülmüútür, ancak hesaplama maliyeti özellikle alt seviyelerde
artmaktadır. Bu yüzden özellikle geniú veritabanları için kullanılmak
üzere hibrit hücre arama algoritması oluúturulmuútur. Bu yönteme göre,
en üst seviyeden itibaren, kullanıcı tarafından girilen seviyeye kadar
Öncelikli Hücre Arama algoritması uygulanırken, geri kalan seviyelerde,
yeni eklenen elemanın sadece hücre çekirdeklerine olan benzerli÷iyle
ilgilenen EB-Çekirdek algoritması uygulanmaktadır.
2.3.3.4 HHA indeksleme:
HHA indeksleme için birbirinden ba÷ımsız iki iúlem
uygulanmaktadır. Bu iúlemlerden ilki, HHA gövdesinin oluúturulması,
28
ikincisi ise bunun üzerinde kullanıcı iste÷ine ba÷lı olarak uygulanan
periyodik uygunluk denetimi (fitness check) iúlemidir.
1. HHA gövdesinin oluúturulması:
Veritabanında ilk kez indeksleme yapılırken elemanlar teker teker
eklenerek HHA oluúturulur. Veritabanı elemanları HHA ile daha önceden
indekslenmiú ise, önce mevcut HHA yüklenir ve daha sonra yeni gelen
elemanlar ile a÷aç güncellenir.
2. HHA uygunluk denetimi:
Uygunluk Denetimi (Fitness check), indeksleme iúlemi sırasında
veya sonrasında periyodik olarak iste÷e ba÷lı gerçekleútirilen bir
iúlemdir. MUVIS’de HHA oluúturulmadan önce kullanıcıdan uygunluk
denetimi periyodunun girilmesi istenir. Bu iúlem, HHA gövdesi
oluúturulurken, kontrolün olmadı÷ı eleman ekleme sırasından
kaynaklanabilen bozulmayı minimize etmeye çalıúır. Uygunluk denetimi,
iki birbirinden ayrı iúlem ile gerçekleútirilir:
i. Aykırı eleman denetimi:
Bu iúlemin amacı, bir veya az sayıda eleman içeren gereksiz azınlık
hücrelerini silerek “boyutluluk sorununu (curse of dimensionality)”
minimize etmektir. HHA oluúturulurken ilk basamaklarda bazı elemanlar
bu azınlık hücrelerini oluúturabilirler ve ileri basamaklarda bu azınlık
hücrelerdeki elemanlar için daha uygun hücreler oluúabilir.
Burada amaç, bu tipteki hücreleri ortadan kaldırmak ve bunların
sahip oldu÷u elemanları olgun hücrelerin kabul edebilece÷ini düúünerek
sisteme geri kazandırmaktır. Fakat, bu elemanlar seviye üzerindeki en
uygun hücreye eklendikten sonra, bu durum hücrenin yo÷unluk de÷erini
önemli ölçüde kötüleútirirse hücre yeniden bölünebilir ve eklenen eleman
bu hücrenin bölünmesiyle oluúan iki yeni hücreden birinde yer alabilir.
Bu durum, o ana kadar, o elemanlar için baúka hiçbir uygun hücre
bulunamadı÷ını gösteren aykırı bir durumdur ve artık o elemanların
azınlık bir hücrede kalmalarına izin verilir.
Bu iúlem en üst seviye dıúındaki tüm seviyelerde yukarıdan aúa÷ıya
do÷ru gerçekleútirilerek olgun hücre oranının arttırılması sa÷lanır.
29
øúlemin bu yönde gerçekleútirilmesinin sebebi, bir seviyeye eleman
ekleme gerçekleútirilirken, öncelikli arama iúlemi bu seviyenin
üzerindeki seviyelerde gerçekleúti÷i için, öncelikle üst seviyelerde aykırı
eleman denetimi (outliers check) iúleminin gerçekleútirilmesinin daha alt
seviyelerde uygulanan uygunluk denetimi iúleminin performansını
arttırmasıdır.
ii. (Olgun) Hücre birleútirme:
Belirli bir eleman ekleme sırasının olmamasının bir baúka sonucu
da, HHA gövdesi oluúumunun ilk basamaklarında hücrelerin hatalı
bölünmesidir. Bu gibi durumlar özellikle, HHA oluúumunun ilk
basamaklarında eklenecek olan elemanların kendisine benzer olan di÷er
elemanlar mevcut de÷ilken, yeterli iyilikte yo÷unluk sa÷layamaması
sonucu veya baúlangıçta farklı bir grup elemanın hücreye eklenmiú
olması ve yeterli iyilikte yo÷unluk sa÷lanması için hücre bölünmesine
gereksinim duyulması sonucu oluúur.
ùekil 2.7 C1 ve C 2 hücrelerine birleútirme iúlemi uygulanması
ùekil 2.7’de görüldü÷ü gibi baúlangıçta hücre bölünmesi ile iki
hücrenin oluúumu yo÷unluk açısından bir gereklilik iken, yeni elemanlar
eklendi÷inde iki hücre birleútirilerek hala iyi bir yo÷unluk de÷eri veren
tek bir hücre oluúturulabilir. Hücre birleútirme iúlemi, her hücrenin MÖA
dal bilgisi kullanılarak üst seviyelerde eleman araútırması gerektirir. Alt
30
seviyede birleútirmeyi gerçekleútirmek için, bu seviyede uygun hücreleri
araútırmak yerine, üst seviyedeki en yakın uzaklıktaki elemanlar
de÷erlendirilir.
Üst seviyede hücre yarıçapları rC1 ve rC2 olan iki eleman arasındaki
dal a÷ırlı÷ı d olsun. Bu durumda d d| rC1 rC2 | ise, bir hücre di÷erinin
elemanlarını kapsayaca÷ı için birleútirme do÷rudan gerçekleútirilebilir.
Genelleútirme açısından, k > 1 , d d k . | rC1 rC2 | gibi bir ifade de
kullanılabilir. E÷er birleútirilen hücre, seviyesinin gerektirdi÷i yo÷unluk
de÷erini sa÷layamıyorsa, birleútirme iúleminden sonra gerçekleútirilen
iúlem-sonrası kontrolleri sırasında bölünmeye u÷rayacaktır. E÷er böyle
bir durum gerçekleúmezse iúlem-sonrası kontrolleri sırasında eski
hücreler ve bunların çekirdekleri HHA gövdesinden silinir ve yeni hücre
ile çekirde÷i eklenir.
31
3 MUVIS øLE YÜZ TANIMA
Bu bölümde tez çalıúması kapsamında MUVIS’e uygulanmıú olan
öznitelik çıkartma yöntemlerinin detayları verilecektir.
3.1 Baúlıca Bileúenler Çözümlemesi
MUVIS’de yüz resimlerinden Baúlıca Bileúenler Çözümlemesi ile
öznitelik çıkartma iúlemi gerçekleútirilirken Matlab 6.0 ve MS Visual
Studio C++ 6.0 ortamı ile Intel OpenCV 1.0 görüntü iúleme kütüphanesi
ve matris iúlemlerinin hızlı bir úekilde gerçekleútirilmesini sa÷layan Intel
IPP 5.2 kütüphanesi kullanılmıútır.
Matlab, kullanılacak özvektör adedinin en uygun sayıda alınmasını
sa÷lamak için ilgili testlerin gerçekleútirildi÷i ortam olarak kullanılmıútır.
Baúlıca Bileúenler Çözümlemesinin uygulaması gerçekleútirilirken,
resim veritabanında ilk durumda belli bir miktar yüz resmine sahip
olundu÷u varsayımı yapılmıútır ve bilgisine sahip olundu÷u varsayılan bu
resimlerin oluúturdu÷u e÷itim kümesinin öznitelik vektörleri
çıkarıltılarak, baúlangıçta bir miktar ayırtedici veriye sahip olunur.
MUVIS ile veritabanına eklenen her resimden, BBÇ’nin çalıúma prensibi
dahilinde e÷itim kümesi esas alınarak öznitelik vektörü çıkartıldıktan
sonra bu resim e÷itim kümesinin bir elemanı olarak yerini alır.
Bundan sonraki alt bölümde, kullanılmıú olan algoritmanın
detayları, izlenen adımlar do÷rultusunda verilecektir.
3.1.1 Yöntem
i. M adet yüz resminden oluúan e÷itim kümesindeki 112 u 92 piksel
boyutundaki her yüz resmi, Bölüm 2.2.1.2’ de anlatıldı÷ı gibi
10304 u 1 boyutunda bir vektöre dönüútürülür. E÷itim
kümesindeki i. yüz resmi, *i ile gösterilen yüz vektörüne
dönüútürüldükten sonra, her sütununu bir yüz vektörünün
32
oluúturdu÷u 10304 u M
matrisi elde edilir.
boyutlu
S
>*1
*2
... *M @ veri
ii. Iúıklandırma úartları ve arka plandan kaynaklanan hatayı azaltmak
için yüz resimlerinde normalizasyon iúlemi gerçekleútirilir. Bunun
için S matrisini oluúturan her yüz vektöründen kendi ortalaması
çıkarılır ve standart sapmasına bölünür.
1
M
* satır ortalaması
¦
i 1 i
M
hesaplanır ve her *i vektöründen bu ortalama vektörü çıkarılarak,
10304 u M boyutlu ) i *i < matrisi elde edilir. Bu iúlemle
birlikte, S matrisini oluúturan her yüzün veritabanı ortalamasına
göre gösterdi÷i farklılık elde edilmiú olur.
iii. S matrisinin, 10304 u 1 boyutlu <
iv. Elde
edilen
A
>)1) 2 ....) M @
veri
matrisinin
1
M
T
)i)i
AAT kovaryans matrisi hesaplanarak, veri
¦
i 1
M
da÷ılımını en iyi ifade eden M adet ortonormal ei vektörü
ek
bulunmak
istenmektedir.
Burada
bir
vektörü
C
elT ek
G lk
­1, l k
®
¯0, l z k
ortonormallik koúulunu sa÷layacak ve
2
1
M
T
(
e
)
)
de÷erini maksimum yapacak úekilde
¦
k
n
M n1
seçilecektir. Bulunmak istenen e1 , e2 , ..., e M vektörleri, C
kovaryans matrisinin özvektörleri ve O1 , O 2 , ..., O M de÷erleri
de özde÷erleridir. Dikkat edilicek olursa, C matrisi, 112 u 92
boyutlu resimlerden oluúan bu e÷itim kümesi için, 10304 2
boyutunda olmaktadır. Belirtilen resim boyutları için bu
büyüklükte bir matrisin özvektörlerinin hesaplanması oldukça
zordur. Bu yüzden bu özvektörlerin hesabını kolaylaútıran bir
yönteme ihtiyaç duyulmaktadır (Turk ve Pentland, 1991). Bir
resim uzayındaki veri noktalarının sayısı, uzayın boyutundan çok
küçük ise (Kullandı÷ımız veritabanı için: M << 10304), bazı
özvektörlere ait özde÷erler sıfır de÷erinde olaca÷ı için, uzay
boyutu (10304) kadar özvektör yerine sadece (M - 1) adet anlamlı
özvektör elde edilebilmektedir ve öncelikle M u M boyutlu
matris için özvektör hesabı yapıldıktan sonra, ) i vektörlerinin
Ok
33
uygun do÷rusal birleúimleri alınırsa, 10304 boyutlu uzayda
özvektör hesabı yapılmıú olur.
Bu iki yöntem arasındaki iliúki úu úekilde gösterilebilir
(Turk, 2001): C matrisinin Cei Oi ei olacak úekilde ei
özvektörleri ve Oi
özde÷erleri ile L
özvektörleri ve P i
iliúkilendirilebilir:
Leˆi
özde÷erleri (3.1) ve (3.2)’deki gibi
P i eˆi
AT Aeˆi
AT A matrisinin êi
(3.1)
P i eˆi
(3.2)
Her iki taraf A ile çarpılırsa:
AAT Aeˆi
CAeˆi
Cei
P i Aeˆi
P i ( Aeˆi )
O i ei
(3.3)
(3.4)
(3.5)
(3.3), (3.4) ve (3.5)’de görüldü÷ü gibi C matrisinin
özvektör (eigenvector) ve özde÷erleri (eigenvalue) ei ( Aeˆi ) ve
Oi P i úeklinde hesaplanabilmektedir. Baúka bir deyiúle, büyük
boyutlu C matrisinin özvektörleri, çok daha küçük boyutlu olan L
matrisinin özvektörlerinin A matrisi ile önçarpımı sonucu
bulunabilmetedir. Aynı zamanda C matrisinin sıfırdan farklı
özde÷erleri L matrisinin özde÷erlerine eúittir. Sonuç olarak
M u M boyutlu L AT A matrisinin özde÷erleri ve özvektörleri
hesaplanır ve özde÷erleri büyükten küçü÷e do÷ru olacak úekilde
özvektörleri sıralanır. Sıralama iúleminin amacı, özde÷erler,
Bölüm 2.2.1.2’de belirtildi÷i gibi özvektörlerin veriyi
modellemedeki önemini gösterdi÷i için, hesaplanan özvektörlerin
önem sırasını elde etmektir.
v. Bu aúamada verilmesi gereken önemli bir karar kaç adet özvektör
kullanılaca÷ıdır. En uygun yüz uzayını oluúturmak için seçilmesi
gereken özvektörlerin hangilerinin olması gerekti÷i konusunda
çeúitli çalıúmalar gerçekleútirilmiútir (Tjahyadi et al., 2004). Bu
çalıúmada özvektörler özde÷erlerine göre sıralandıktan sonra ilk
hangi
özvektörlerin
seçilece÷ine
(Kirby,
2000)’
da
gerçekleútirilmiú olan enerji oranı esas alınarak karar verilmiútir.
34
Bu yöntem, enerji belli bir eúik de÷erinin üzerinde olacak úekilde
minimum sayıda özvektör seçilmesini sa÷lamaktadır. Genellikle
eúik de÷eri 0.9 alınmaktadır. Bu yönteme göre, (3.6)’da
gösterildi÷i gibi i. özvektörün enerjisi ( Ei ), ilk i özde÷erin
toplamının, tüm özde÷erlerin toplamına oranına eúittir.
i
¦P
Ei
j
j 1
(3.6)
M
¦P
j
j 1
Bu tez çalıúmasında k de÷erine karar verilirken, Bölüm
4.8’de bahsedilecek olan Duyarlık Analizinden yararlanılmıútır.
vi. iv. ve v. adımlarda bahsedildi÷i gibi L matrisinin özvektör ve
özde÷erleri tespit edilerek ilk k özvektör elde edildikten sonra
özvektörler üzerinde normalizasyon iúlemi uygulanır. Bu iúlem
sırasında her özvektör, (3.7)’de gösterildi÷i gibi tüm
elemanlarının kareleri toplamının kareköküne bölünür.
eˆi
eˆi
(3.7)
M
¦ (eˆ
ij
)
2
j i
vii. L matrisinden hesaplanmıú olan ê özvektörleri, M adet resimden
oluúan e÷itim kümesi elemanlarının, C matrisinin e özvektörlerini
oluútururken
hangi
oranlarda
do÷rusal
birleúim
M
gerçekleútireceklerini belirler. Dolayısıyla, ei
¦ eˆ )
ij
j
i = 1, 2,
j 1
…, k iúlemi gerçekleútirilerek C matrisine ait e özvektörleri elde
edilir.
viii. Elde edilen e özvektörlerine vi. adımda bahsedilen normalizasyon
iúlemi uygulanır. øúte bu k özvektörün oluúturdu÷u “yüz uzayı”,
üzerine ilgili resimler yansıtılarak a÷ırlık vektörleri hesaplanacak
olan öznitelik uzayıdır ve bu uzayın boyutu kullandı÷ımız
veritabanı resimleri için 10304 u k olmaktadır ve uygulama
sırasında bu yüz uzayı e1 , e2 , ..., e M özvektörlerinin
sütunlarını oluúturdu÷u E matrisi ile gösterilmektedir. Öznitelik
uzayını oluúturan özvektörler görüntülenmek istendi÷inde ortaya
35
çıkan görüntü hayalet yüz úeklindedir ve bu yüzden bu görüntüler,
“özyüzler” olarak da isimlendirilmektedir.
ix. Elde edilen yüz uzayına bir yüz resmi yansıtıldı÷ında, o yüz resmi
için k u 1 boyutunda bir a÷ırlık vektörü elde edilmektedir. Her
a÷ırlık vektörü ait oldu÷u resim için ayırt edicidir ve o resim için
öznitelik vektörü olarak kullanılarak tanıma iúleminde yerini alır.
Ayrıca bir resim, yüz uzayı kullanılarak yeniden oluúturulabilir.
Bunun için yeniden oluúturulmak istenen 112 u 92 boyutlu resim
vektör haline getirilip, ii. aúamada bahsedildi÷i gibi
normalizasyon iúleminden geçirildikten sonra, yüz uzayına
yansıması alınarak a÷ırlık vektörleri elde edilir. Yüz uzayına ait
özvektörlerin oluúturdu÷u matris ve resim için elde edilen a÷ırlık
vektörü çarpılıp, iii. adımda elde edilen < e÷itim kümesi satır
ortalaması ile toplandı÷ında girdi resmi yeniden oluúturulur.
YOGR yeniden oluúturulan girdi resmini ve NEGR normalize
edilmiú girdi resmini göstermek üzere bahsedilen iúlemler (3.8)’
deki gibi tanımlanır.
YOGR < E u ( NEGR T u E )
(3.8)
Özyüzler (eigenfaces) yönteminin bu özelli÷i, bu yöntemin
resim sıkıútırmada kullanılmasına imkan sa÷lamıútır (Sirovich ve
Kirby, 1987) (Kirby ve Sirovich, 1990). Burada dikkat edilmesi
gereken önemli bir nokta, her yüz resminin, üzerine yansıtıldı÷ı
resim uzayını oluúturan özvektörlerin, e÷itim kümesini oluúturan
resimleri temsil eden veri noktalarını, ne kadar do÷ru
gösterdi÷idir. Hesaplanmıú ve kullanılmasına karar verilmiú olan
özvektörlerin veri noktalarını temsil etmedeki gücü arttıkça,
yeniden oluúturulan resim gerçe÷ine daha benzer olmaktadır. Bu
çalıúmada bu durum üzerine farklı sayılarda özvektörlerin
oluúturdu÷u özvektör uzayları ile duyarlılık testleri yapılarak
benzerlik çalıúmalarında kullanılmak üzere özyüz uzayını
oluúturan en uygun özvektör sayısına karar verilmiútir.
3.1.2 Özyüz uzayının MUVIS’de kullanımı
Tekrar vurgulamak gerekirse, MUVIS’de gerçekleútirilmesi istenen
iúlem, veritabanı elemanlarından ilgili yöntem ile öznitelik vektörleri
36
çıkartılarak HHA ile indekslenmesinin sa÷lanmasıdır. BBÇ yöntemi,
MUVIS’e uyarlanırken, baúlangıçta k adet resim bilgisine sahip olundu÷u
varsayılarak bu resimlerin e÷itim kümesini oluúturdu÷u düúünülmüútür
ve e÷itim kümesini oluúturan bu resimler baúlangıçta HHA ile
indekslenmiútir. Varsayılan bu temel durumun sonrasında eklenen her
112 u 92 boyutlu yüz resmi, e÷itim kümesinden elde edilen yüz uzayına
yansıtılarak öznitelik vektörü elde edilmiú ve bu öznitelik vektörü ile
HHA üzerinde yerini alması sa÷lanmıútır. Bu iúlemler sonrasında
eklenmiú olan her yeni yüz resmi e÷itim kümesine eklenerek sonraki
resim ekleme iúlemlerinde yeni e÷itim kümesi üzerinden özyüz uzayı
hesaplanmıú ve her yeni resim eklemede bu iúlemler tekrarlanmıútır.
Bahsedilmiú olan baúlangıçda varsayılan temel durum elde
edilmeye çalıúılırken Intel OpenCV 1.0 kütüphanesi kullanılmıútır. Bu
çalıúmada kullanılan 400 resimden oluúan veritabanı için Bölüm 4.8’de
bahsedilen Duyarlık Analizi yapıldı÷ında k sayısının 120 ve 240 olarak
alınarak ilgili testlerin ayrı ayrı gerçekleútirilmesine karar verilmiútir.
Dolayısıyla, varsayılan temel durumu elde etmek için, ilk 120 ve 240
resim kullanılarak 120 ve 240 adet özvektörün oluúturdu÷u yüz uzayı
elde edilmiútir. Bu iúlemin sonrasında MUVIS ile aynı 120 ve 240 resim
için HHA oluúturulması öncesinde her resim meydana getirilmiú bu yüz
uzayına yansıtılarak, her resim için öznitelik vektörü elde edilmiú ve ilk
HHA oluúumunda bu öznitelik vektörleri dikkate alınmıútır. Varsayılan
temel durum için oluúturulmuú olan HHA’a eklenecek olan 121. ve 241.
resimden itibaren yüz uzayı kendisini güncellemeye baúlamaktadır. Yani,
121. ve 241. resimden itibaren her yüz resmi için mevcut yüz uzayı ile bir
öznitelik vektörü oluúturulduktan sonra, o yüz resmi e÷itim kümesine
eklenmektedir. Dolayısıyla eklenen bir sonraki resmin üzerine
yansıtılaca÷ı yüz uzayı, bir önceki resmin eklenmesiyle yenilenmiú olan
e÷itim kümesi kullanılarak oluúturulmaktadır.
Vurgulanması gereken bir baúka konu ise, HHA oluúturulmak üzere
e÷itim kümesine eklenen resimlerin, eklenme sırasının, HHA oluúumunu
etkileme úeklidir. (Kiranyaz, 2005)’de bahsedildi÷i gibi bu beklenen
durum için mevcut sistemin aldı÷ı Bölüm 2.3.3.4’de bahsedilen bazı
tedbirler vardır. Bu önlemlere ra÷men yapılan testlerde resimlerin
eklenme sırasının oluúan a÷acın yapısında bazı de÷iúikliklere sebep
oldu÷u görülmüútür. A÷aç oluúturulurken bir kiúiye ait tüm resimler
birbiri ardına eklendi÷inde daha do÷ru sınıflandırmayı sa÷layan a÷aç
oluútu÷u gözlenmiútir. Bu tez çalıúmasında yapılan testlerde en kötü
37
durum esas alınarak, farklı kiúilere ait resimler birbiri ardına verilerek
HHA oluúturulmuútur.
3.2 Do÷rusal Ayrıútırma Çözümlemesi
Bu tez çalıúmasında MUVIS’e uygulanmak istenen bir di÷er
öznitelik çıkartma yöntemi Do÷rusal Ayrıútırma Çözümlemesi olmuútur
ve bu iúlem için Matlab 6.0 ve MS Visual Studio C++ 6.0 ortamı
kullanılmıútır.
DAÇ ile Bölüm 2.2.1.3’de bahsedildi÷i gibi sınıflar arasında
ayrıútırma bilgisi elde edilir. Burada kritik soru, sınıfların ne oldu÷udur.
Bu yöntem MUVIS’e uyarlanırken kullanılan veritabanı esas alındı÷ında
bir sınıfı bir kiúiye ait resimlerin oluúturdu÷u düúünülmüútür ve HHA ile
indeksleme iúleminden geçirildikten sonra en ideal durumda bir kiúiye ait
tüm resimlerin bir hücrede yer alması beklenmektedir. Kullanılan resim
veritabanı her kiúiye ait on adet resimden oluúmaktadır ve bu çalıúmada
e÷itim kümesini her kiúiye ait ilk beú resmin oluúturdu÷u varsayılmıútır.
Sahip olunan bu sınıf bilgisi esas alınarak oluúturulan alt uzay
kullanılarak her kiúiye ait resimler için öznitelik vektörü elde edilecek ve
HHA’da yerleúti÷i konumlar incelenecektir.
Bu bölümde, Do÷rusal Ayrıútırma Çözümlemesi yöntemini
MUVIS’e uygulamak amacıyla gerçekleútirilmiú iúlemler açıklanacaktır.
3.2.1 Yöntem
i. DAÇ yöntemi uygulanırken, çok büyük boyutlu matrislerin
oluúturdu÷u alt uzaylarda çalıúmanın sebep oldu÷u bellek ihtiyacı
ve hesaplama karmaúıklı÷ının büyüklü÷ünden kurtulmak için
girdi olarak kullanılan tüm yüz resimleri yeniden boyutlandırma
iúleminden geçirilerek boyutu küçültülmektedir. Bu çalıúmada
tercih edilen yeniden boyutlandırma iúlemi birbirine komúu olan
her 4 pikselin ortalamasının kullanımıdır. Dolayısıyla 112 u 92
piksel boyutundaki her yüz resmi 56 u 46 boyutuna
indirgendikten sonra 2576 u 1 boyutunda bir vektör olarak temsil
edilmektedir.
38
ii. E÷itim kümesi oluúturulurken bir kiúiye ait ilk beú resim, i=1, 2, ...,
5 olmak üzere, *i ile gösterilen yüz vektörüne dönüútürüldükten
sonra, bu vektörler biraraya getirilerek j=1, 2, ..., 40 olmak üzere
2576 u 5 boyutlu S j * j1 * j 2 ... * j 5 matrislerini oluúturur
>
@
ve S j matrisleri de biraraya getirildi÷inde T
>S1
S2
... S 40 @
matrisi elde edilir.
iii. M=40 olmak üzere, T matrisi kullanılarak e÷itim kümesi için,
1
M
2576 u 1 boyutlu <
* satır ortalaması hesaplanır ve
¦
i 1 i
M
2576 u 2576 boyutlu TY Toplam Yayılım Matrisi (3.9)’da verilen
formül esas alınarak hesaplanır.
M
TY
5
¦¦ (*
ji
< )(* ji < ) T
(3.9)
j 1, i 1
iv. Bir sonraki iúlem Sınıf-içi Yayılım Matrisinin hesaplanmasıdır.
1 5
Bunun için her S j sınıfının 2576 u 1 boyutlu <S j
¦ * ji
5 i1
satır ortalaması hesaplanır ve (3.10)’daki formül esas alınarak
2576 u 2576 boyutlu SI Sınıf-içi Yayılım Matrisi hesaplanır:
M
SI
5
¦¦ (*
ji
<S j )(* ji <S j ) T
(3.10)
j 1, i 1
v. Toplam Yayılım Matrisinden Sınıf-øçi Yayılım Matrisi çıkarılarak
SA Sınıflararası Yayılım Matrisi elde edilir: SA = TY – SI
vi. Sınıflararası ayrıútırma bilgisine sahip olunacak olan alt uzay
SA
oluúturulurken
oranını maksimize eden özde÷erler ve
SI
özvektörlerin hesaplanması istenmektedir. Fakat SA ve SI birer
gerçek simetrik matris olmasına ra÷men SI 1 SA çarpımı gerçek
ve simetrik olmayan bir matristir. SI 1 SA çarpımının özyapısını
araútırırken (Cooley ve Lohnes, 1971) tarafından açıklanan iki
simetrik matrisin diyagonalleútirilmesini sa÷layan yöntem
kullanılacaktır. Bu yönteme göre 2576 u 2576 boyutlu
1
G
1
( SI 2 ) T u SA u ( SI 2 )
matrisi
hesaplanır.
Bu
matrisin
39
özvektörleri
SI
1
2
matrisi ile önçarpıldı÷ında
SA
SI
oranını
maksimize eden özde÷er ve özvektörlere ulaúılır.
vii. Bulunan özvektörler, özde÷erleri büyükten küçü÷e do÷ru olacak
úekilde sıralanır ve bu úekilde oluúturulmuú olan 2576 u 2576
boyutlu matris ayrıútırma bilgisi taúıyan ve üzerine resimlerin
yansıtılarak öznitelik vektörlerinin elde edilece÷i alt uzay olarak
kullanılır.
3.2.2 Ayrıútırma uzayının MUVIS’de kullanımı
Matlab ile bir üst bölümde anlatıldı÷ı gibi her kiúiye ait beú resim
kullanılarak elde edilen alt uzay üzerine, MUVIS tarafından okunan yüz
resimleri yansıtılarak her yüz resmi için bir öznitelik vektörü elde edilir
ve bunun sonrasında HHA oluúturulur. Bu öznitelik çıkartma yöntemi
için, Bölüm 4’de bahsedilecek olan performans ölçüm testleri
uygulanırken, Matlab ile her sınıfta bir kiúiye ait beú adet resim oldu÷u
varsayımı ile oluúturulan ayrıútırma alt uzayı kullanılmıútır.
40
4 PERFORMANS ÖLÇÜTLERø
Gerçekleútirilmiú olan testlerde MUVIS’in en son geliútirilmiú olan
1.8 versiyonu kullanılmıútır (TUT MUVIS Xt Projesi, internet eriúimi).
Resimler veritabanına her kiúiye ait 1 resimden oluúan 40 resimlik
gruplar halinde eklenmiútir. Sistemin kullanılan öznitelik çıkartma
yöntemi ile elde etti÷i indeksleme performansı sonucu, oluúturulan
HHA’ nın en alt seviyesindeki hücrelerin içerikleri incelenerek ortaya
koyulmuútur. HHA’ nın en alt seviyesindeki hücrelerin her birinde en
ideal durumda bir kiúiye ait tüm resimlerin bulundu÷u gerçe÷i göz
önünde
bulundurulmalıdır.
Kullanılan
performans
ölçütleri
sınıflandırmanın ne kadar baúarılı gerçekleúti÷i konusuna açıklık
getirmektedir.
Bu bölümde, geliútirilmiú olan performans ölçütleri tanıtılacaktır.
4.1 Kullanılan Yüz Resimleri Veritabanı
Gerçekleútirilen testlerde kullanılan veritabanı, Nisan.1992 ve
Nisan.1994 tarihleri arasında Olivetti Araútırma Laboratuvarında
çekilmiú olan yüz resimlerinden oluúmaktadır (AT&T Laboratuvarları,
internet eriúimi).
Bu veritabanında, 40 farklı kiúiye ait her biri 112 u 92 piksel
boyutunda olan 400 adet resim ve her kiúiye ait, farklı zamanlarda,
de÷iúik ıúık úartlarında ve yüz ifadelerinde önden çekilmiú olan 10 farklı
resim bulunmaktadır. Tüm resimler koyu renkli ve homojen bir
arkaplanda ve önden çekilmiútir. Kullanılan veritabanında bulunan
resimlerin bir örne÷i ùekil 4.1’de görülebilir.
41
ùekil 4.1 Kullanılan yüz resimleri veritabanından bir kesit
4.2 Kullanılan HHA Parametre De÷erleri
Yüz resimlerinden öznitelikler çıkartıldıktan sonra HHA
oluúturulurken, oluúturulacak a÷acın yapısını Bölüm 1.3.3’ de
bahsedildi÷i gibi etkileyen parametrelerin kullanıcı tarafından girilmesi
gerekmektedir. Bu tez çalıúması kapsamında gerçekleútirilen testlerde
aúa÷ıdaki tabloda verilen parametre de÷erleri kullanılmıútır.
42
Tablo 4.1 HHA oluútururken kullanılan parametreler
Parametre
Hücre Olgunlu÷u
Tepe Seviyedeki Hücre Büyüklü÷ü
Hücre Yo÷unluk Özelli÷i Eúi÷i
E÷ilim Çarpanı
Uygunluk Denetimi Periyodu
Hücre Yo÷unluk Özelli÷i
Güncelleme Periyodu
De÷er
11
40
0.1
100
100
4.3 Her Hücredeki Kiúi Yo÷unlu÷u Testi
Bu test ile HHA’nın en alt seviyesindeki hücrelerde kaç farklı
kiúiye ait resim bulundu÷u hakkında fikir edinilir. Oluúturulmuú olan
HHA’nın en alt seviyesindeki her hücrede bulunan resimlerin ait oldu÷u
kiúi sayısı çıkartılır ve aúa÷ıdaki örnek grafikte gösterildi÷i gibi her
hücrede hangi sayılarda farklı kiúinin bulundu÷u durumu, a÷acın alt
seviyesindeki tüm hücreler üzerinden belirlenir. Örnek verilecek olursa,
ùekil 4.2’de üç farklı kiúinin resimlerini içeren yedi adet hücre oldu÷u
anlaúılmaktadır.
Her Hücredeki Kiúi Yo÷unlu÷u Testi
Durum Sayısı
32
27
28
24
18
20
16
12
7
8
1
4
1
0
1
2
3
4
5
Hücredeki Farklı Kiúi Sayısı
ùekil 4.2 Örnek her hücredeki kiúi yo÷unlu÷u test sonucu
43
4.4 9+1 Testi
Bu testin uygulanma amacı, resimlerden çıkartılan öznitelik
vektörünün HHA üzerindeki etkisini araútırmaktır.
Kullanılan veritabanındaki 40 kiúinin her birine ait dokuzar
resimden ilgili yöntemler ile öznitelik vektörleri çıkartıldıktan sonra
HHA oluúturulur ve 40 kiúiye ait kalan birer resimden de aynı yöntemle
öznitelik vektörü çıkartıldıktan sonra HHA ile indekslenmiú olan a÷aca
eklenir. Bu iúlemin sonrasında eklenen 40 kiúiye ait birer resimden
oluúan 40 resmin HHA’nın en alt seviyesinde bulunan hücrelere
yerleúimi incelenerek do÷ru hücrelerde yer alıp almadı÷ı araútırılır.
Bu araútırma sırasında bir hücre gözlenirken, ideal durumda, hücre
içerisindeki maksimum sayıda resim içeren kiúiye ait resim sayısının,
sonradan eklenen resimleri takiben artma e÷ilimi göstermesi
beklenmektedir. ølgili öznitelik çıkartma yöntemi ile bu test
uygulandıktan sonra, ideal durumların sayısı belirlenir. ùekil 4.3’de bir
9+1 Test grafi÷i örne÷i verilmiútir.
9+1 Testi
9
Kiúi 1
8
Kiúi 2
Resim Sayısı
7
Kiúi 3
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Hücre Numarası
ùekil 4.3 Örnek 9+1 test sonucu
23
24
25
26
27
28
29
44
4.5 Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı
Bu ölçüt, ùekil 4.3’de bir örne÷i verilmiú olan, yatay eksende
verilen hücre numarasına sahip olan hücre içerisindeki, bir kiúiye ait olan
resimlerin bir sütununu oluúturdu÷u, her hücre içerisindeki resimlerin ait
oldukları kiúiye göre da÷ılımını gösteren grafik kullanılarak elde edilen
bir performans ölçütüdür.
Bahsedilen grafik, öznitelik vektörleri çıkartılan resimlerin HHA
ile indekslenmesinden sonra oluúturulur ve her hücrede bulunan her
kiúiye ait resim sayısı kaydedilir. Bu úekilde elde edilen her kiúiye ait
resim sayısının, 1’den 10’a kadar olan rakamlarda çıkma sıklı÷ı durum
sayılarını oluúturacak úekilde ùekil 4.4’de bir örne÷i verilmiú olan grafik
çizilir. Grafi÷in daha iyi anlaúılması için bir örnek vermek gerekirse, bir
kiúiye ait 10 resmin tamamının bir hücrede bulundu÷u durum sayısı ùekil
4.4 üzerinde iúaretlendi÷i gibi 31’dir.
Bir Hücrenin Bir Kiúinin x Adet
Resmini øçerdi÷i Durum Sayısı
Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı
35
31
30
25
20
15
10
7
5
4
2
0
5
2
1
2
2
0
1
2
3
4
5
6
7
8
9
10
Bir Kiúiye Ait Resim Sayısı (x)
ùekil 4.4 Örnek kiúiye ait resimlerin hücrelere da÷ılımı test sonucu
45
4.6 Kırkar Resimlik On Devir Testi
Bölüm 4.5’de açıklanan grafik kullanılarak elde edilen bir
performans ölçütüdür. Bu testte üzerinde indeksleme yapılan
veritabanındaki resim sayısı artıúının, Bölüm 4.5’de açıklanan grafi÷i
nasıl úekillendirdi÷i gözlenerek, uygulanan öznitelik çıkartma
yönteminin, bilgisine sahip olunan resim sayısı arttıkça do÷ru
sınıflandırma bilgisini ö÷renip ö÷renemedi÷i sorgulanır.
ùekil 4.5’de sınıflandırmanın en ideal úekilde gerçekleútirildi÷i
varsayımı yapıldı÷ında elde edilmesi beklenen sonuçları içeren bir test
örne÷i verilmiútir. Bu test uygulanırken, ilk önce 40 kiúinin her birine ait
ilk resimlerden ilgili yöntem ile öznitelik vektörleri çıkartılarak HHA ile
indekslenir ve a÷acın en alt seviyesindeki hücrelerin Bölüm 4.5’de
verilen grafi÷i oluúturulur. Daha sonra 40 kiúinin her birine ait ikinci
resimlerden öznitelik vektörleri çıkartılarak biraz önce oluúturulmuú
a÷aca eklenir ve aynı grafik bu ikinci devir için oluúturulur. Bu iúlemler
40 kiúinin herbirine ait üçüncü, dördüncü, beúinci, …vs resimleri
eklenerek tekrarlanır. Bu teste göre, ikinci devirden itibaren her devirde,
her kiúiye ait 40 adet resim bir önceki devirde oluúturulmuú olan a÷aca
eklenmekte ve bu resimlerin a÷acın en alt seviyesindeki hücrelere
da÷ılımı her devirde incelenmektedir.
46
Devir 6
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Devir 1
50
40
30
20
10
0
1
2
3
4
5
6
7
8
9
10
50
40
30
20
10
0
1
2
Bir Kiúiye Ait Resim Sayısı (x)
3
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
40
30
20
10
0
2
3
4
5
6
7
8
9
10
0
6
7
8
9
2
3
10
0
6
7
8
9
10
9
10
0
2
3
4
5
6
7
8
50
40
30
20
10
0
1
2
3
4
5
6
7
8
Bir Kiúiye Ait Resim Sayısı (x)
Devir 10
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
9
10
Devir 5
40
30
20
10
0
5
10
20
10
50
4
8
30
Bir Kiúiye Ait Resim Sayısı (x)
3
7
40
1
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
20
2
6
Devir 9
30
1
5
Bir Kiúiye Ait Resim Sayısı (x)
40
5
4
50
Devir 4
4
9
0
10
50
3
10
10
Bir Kiúiye Ait Resim Sayısı (x)
2
9
20
1
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
Bir Hücrenin Bir Kiúinin (x)
Adet Resmini øçerdi÷i
Durum Sayısı
20
1
10
Devir 8
30
5
9
Bir Kiúiye Ait Resim Sayısı (x)
40
4
8
30
Devir 3
3
7
40
10
50
2
6
50
Bir Kiúiye Ait Resim Sayısı (x)
1
5
Devir 7
Devir 2
50
1
4
Bir Kiúiye Ait Resim Sayısı (x)
6
7
8
Bir Kiúiye Ait Resim Sayısı (x)
9
10
50
40
30
20
10
0
1
2
3
4
5
6
7
8
Bir Kiúiye Ait Resim Sayısı (x)
ùekil 4.5 Örnek kırkar resimlik on devir test grafi÷i
47
4.7 Sınıflandırma Baúarımı Testi
Bu test ile, ilgili öznitelik çıkartma yöntemi kullanılarak
gerçekleútirilen sınıflandırmanın yüzde kaç do÷ruluk ile gerçekleútirildi÷i
ölçülmek istenmiútir.
Öncelikle 40 kiúiden her birine ait beúer adet olmak üzere 200 adet
resimden ilgili öznitelik çıkartma yöntemi ile öznitelik vektörleri
çıkartılarak HHA ile indekslenmesi sa÷lanır. 40 kiúinin di÷er beúer
resimlerinden oluúan 200 adet resimden de ilgili yöntemle öznitelik
vektörleri çıkartılarak, bunlar da oluúturulmuú olan a÷aca yerleútirilir. Bu
iúlemlerin ardından, a÷acın en alt seviyesindeki hücreler incelenerek,
sonradan eklenen 200 adet resmin do÷ru hücrelere yerleúmiú olan kısmı
belirlenir. Bu iúlem, sonradan eklenen 200 resmin her birinin, yerleúti÷i
hücre içerisinde bir kiúiye ait resim sayısını hangi rakama ulaútırdı÷ı esas
alınarak gerçekleútirilir. Bu úekilde sonradan eklenen 200 resimden do÷ru
hücrelere yerleúen resim adedinin, eklenmiú olan toplam resim adedine
yani 200’e oranı alınır. Bu oran, “Sınıflandırma Baúarımı” olarak
isimlendirilir.
ùekil 4.6’da, bu performans ölçütünün elde edilmesi için kullanılan
grafi÷e bir örnek verilmektedir.
Burada dikkat edilmesi gereken husus, a÷aca sonradan eklenen 200
resmin her birinin yerleúti÷i hücrenin do÷ru hücre oldu÷una nasıl karar
verildi÷idir. Bu noktada, a÷aca ikinci 200 resim eklenmeden önce bir
hücredeki bir kiúiye ait resim sayısı (yatay eksen ile gösterilen de÷erler)
en az beú iken, eklendikten sonra en az altıya çıkıyorsa, baúka bir deyiúle,
sonradan eklenen 200 resim içerisinde bir kiúiye ait herhangi bir resim,
aynı kiúiye ait di÷er resimlerin sayıca fazla oldu÷u hücreye yerleúiyorsa,
sonradan eklenen 200 resim içerisindeki bu bir resmin do÷ru hücreye
yerleúti÷i söylenebilir.
48
ùekil 4.6 Örnek sınıflandırma baúarımı test grafi÷i
4.8 BBÇ Duyarlık Testi
Bu test dahilinde, Matlab ortamında, de÷iúen resim sayılarından
oluúan veritabanı için özvektörler çıkarılıp, özde÷erlerine göre
sıralandıktan sonra, ilk n adet özvektör kullanılarak belli bir yüz resmi
yeniden oluúturularak özvektörlerin veri modelini göstermedeki etkinli÷i
incelenmiútir.
ùekil 4.7’deki yüz resmi girdi olarak verildi÷inde, bu resim bilgisi
vektör haline getirildikten sonra, çıkarılmıú olan özvektör uzayı üzerine
yansıtılır ve bu resim için ilgili a÷ırlık vektörü elde edilir (Yüz tanıma
iúleminde, girdi resimlerinden bu úekilde elde edilen a÷ırlık vektörleri,
veritabanı resimlerinin yüz uzayına yansıtılmasıyla elde edilmiú olan
a÷ırlık vektörleri ile kıyaslanarak girdi resimlerinin veritabanındaki
benzerleri elde edilmeye çalıúılmaktadır).
AV, resmin a÷ırlık vektörü, NEGR normalize edilmiú girdi resmi,
YU yüz uzayını oluúturan özvektörler olmak üzere (4.1)’de gösterildi÷i
gibi elde edilen bu a÷ırlık vektörü, YOGR yeniden oluúrurulan resmi, m
veritabanı ortalamasını göstermek üzere (4.2)’deki gibi kullanılarak, girdi
resmi yeniden oluúturulmaya çalıúılır.
49
AV
YOGR
NEGR u YU T
(4.1)
m YU u AV
(4.2)
De÷iúen veritabanı büyüklüklerinde, de÷iúen sayılarda özvektörler
kullanılarak bu iúlem tekrarlandı÷ında ùekil 4.7’deki girdi resmi
kullanılarak ùekil 4.8, ùekil 4.9, ùekil 4.10, ùekil 4.11, ùekil 4.12’deki
yüz resimleri oluúturulmuútur.
ùekil 4.7 Girdi Resmi
ùekil 4.8 Özuzay oluúturulurken kullanılan veritabanındaki resim sayısı:
400 , kullanılan özvektör sayısı: 400
50
(a)
(b)
ùekil 4.9 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 10 , kullanılan özvektör sayısı: 10 , (b) kullanılan veritabanındaki
resim sayısı: 400 , kullanılan özvektör sayısı: 10
(a)
(b)
ùekil 4.10 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 80 , kullanılan özvektör sayısı: 80 , (b) kullanılan veritabanındaki
resim sayısı: 400 , kullanılan özvektör sayısı: 80
51
(a)
(b)
ùekil 4.11 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 120 , kullanılan özvektör sayısı: 120 , (b) kullanılan
veritabanındaki resim sayısı: 400 , kullanılan özvektör sayısı: 120
(a)
(b)
ùekil 4.12 Özuzay oluúturulurken (a) kullanılan veritabanındaki resim
sayısı 240 , kullanılan özvektör sayısı: 240 , (b) kullanılan
veritabanındaki resim sayısı: 400 , kullanılan özvektör sayısı:240
52
Bu testler gerçekleútirilirken, Bölüm 3.1.1.v’de bahsedilen ve
(3.6)’da formülü verilen i. özvektörün enerjisi, i=10 için E10 0.9030 ,
i=80 için E 80 0.9685 , i=120 için E120 0.9781 ve i=240 için
E 240 0.9926 olmaktadır.
Bu test sonuçları de÷erlendirilirse:
i.
Veritabanındaki resim sayısı kadar özvektör kullanıldı÷ında
yeniden oluúturulan resim, girdi resmine büyük ölçüde benzerlik
göstermektedir. Bu durum, veritabanı resimlerinden elde edilen
özvektörlerin tamamının kullanımının veri modellemedeki
etkisinin ne kadar fazla oldu÷unun bir kanıtıdır.
ii.
Girdi resmi, veritabanındaki 400 resmin tamamından elde edilen
ilk 10 özvektör kullanılarak oluúturulan yüz uzayı üzerine
yansıtıldıktan
sonra
yeniden
oluúturma
iúlemi
gerçekleútirildi÷inde elde edilen yüz resminin orjinal resme
benzemedi÷i görülür. Aynı iúlemler, 80, 120, ve 240 özvektör
kullanılarak tekrarlandı÷ında elde edilen resim, orjinal resme en
fazla oranda, 240 özvektör kullanımında benzemektedir.
iii. Aynı 10, 80, 120 ve 240 özvektörlük yüz uzayları sırayla 10, 80,
120 ve 240 resimden meydana gelen e÷itim kümelerinden elde
edildi÷inde, yeniden oluúturulan yüz resimlerinde 120 ve 240
resimlik e÷itim kümeleri kullanıldı÷ında ayrıntılarının daha
belirgin ortaya çıktı÷ı görülmüútür.
Bu de÷erlendirmeler dikkate alındı÷ında, bu tez çalıúmasında
toplamda 400 adet yüz resmi üzerinde çalıúılaca÷ı göz önünde
bulunduruldu÷u zaman, en büyük özde÷erlere sahip 120 ve 240 adet
özvektör kullanılması uygun görülmüútür.
53
5 TEST SONUÇLARI
Bu bölümde, (MUVIS v1.8 kurulumu, internet eriúimi)’deki
kurulum paketi yüklenerek elde edilebilecek olan MUVIS sisteminde
hazır yüklü bulunan Gabor Filtresi öznitelik çıkartma yöntemi ile bu tez
úalıúmasında MUVIS sistemine yüklenen BBÇ ve DAÇ öznitelik
çıkartma yöntemleri kullanılarak tez çalıúması kapsamında
gerçekleútirilen testler, Bölüm 4’de açıklanan performans ölçütleri
dahilinde sunulacaktır.
Bu bölümde sonuçları açıklanacak olan testler uygulanırken, BBÇ
yöntemi için yüz uzayı hesaplaması sırasında OpenCV 1.0 kütüphanesi,
DAÇ yöntemi için ayrıútırma uzayı hesaplanması sırasında ise Matlab 6.0
ortamından yararlanılmıútır.
5.1 Hücrelerdeki Kiúi Yo÷unlu÷u Testi
Gabor filtresi, BBÇ ve DAÇ yöntemleri ile ùekil 4.1’de bir bölümü
gösterilen 400 adet yüz resminden öznitelik vektörleri çıkartıldıktan
sonra Tablo 4.1’de belirtilen parametreler ile HHA indeksleme
gerçekleútirildi÷inde, oluúan a÷acın en alt seviyesindeki hücreler
incelendi÷i zaman, bu üç yöntem için ùekil 5.1’deki Hücrelerdeki Kiúi
Yo÷unlu÷u test sonucu elde edilir.
Yüz tanıma uygulamalarında öznitelik vektörü çıkartılırken,
genellikle, 5 ölçekli ve 8 yönlü Gabor çekirdekleri kullanılmaktadır (Liu
ve Wechsler, 2001). Bu sebeple, bu tez çalıúmasında uygulanan testlerde
de Gabor filtresi kullanılırken, bu parametreler seçilmiútir.
BBÇ yöntemi uygulanırken, ùekil 5.1’de de görülebilece÷i gibi iki
farklı sayıda özvektör grubundan oluúan yüz uzayları için iki farklı sonuç
alınmıútır. Bölüm 3.1.1’de verilen yöntem izlenerek öznitelik vektörleri
çıkartılırken, öncelikle, her kiúiye ait üçer resimden oluúan 120 resim için
yüz uzayı oluúturulmuútur (Bölüm 3.1.1.v’de bahsedilen k, 120
alınmıútır.) ve 400 adet yüz resmi bu yüz uzayına yansıtılarak her yüz
resmi için bir öznitelik vektörü elde edilmiútir. Elde edilen bu öznitelik
vektörleri ile indeksleme gerçekleútirildikten sonra, bir kiúiye ait altıúar
54
resimden oluúan 240 resim için yüz uzayı oluúturularak (k=240
alınmıútır) aynı iúlemler tekrarlanmıútır.
DAÇ yöntemi uygulanırken, Bölüm 3.2’de bahsedildi÷i gibi, bir
kiúiye ait beúer resim bilgisine önceden sahip olundu÷u varsayılarak,
baúlangıçta bir sınıfta her kiúiye ait bu beú resmin varoldu÷u
düúünülmüútür. Matlab ortamında Bölüm 3.2.1’de detayları anlatılan
yöntem uygulanarak elde edilen ayrıútırma uzayına 400 adet resim
yansıtılarak bu resimler için öznitelik vektörleri elde edilir.
Her Hücredeki Kiúi Yo÷unlu÷u Testi
26
24
BBÇ (120 Özvektör)
22
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
Durum Sayısı
20
18
16
14
12
10
8
6
4
2
0
1
2
3
4
5
6
7
8
9
Hücredeki Farklı Kiúi Sayısı
ùekil 5.1 Her hücredeki kiúi yo÷unlu÷u test sonucu
ùekil 5.1’de görüldü÷ü gibi bir hücrede bulunan resimlerin ait
oldu÷u kiúi sayısı, 120 özvektörlük yüz uzayı ile çalıúan BBÇ yöntemi
kullanıldı÷ında maksimum de÷ere ulaúmaktadır. Bu durum, bir kiúiye ait
resimlerin hücrelere da÷ılırken fazlaca parçalandı÷ı anlamına gelmektedir
ve idealde bir kiúinin tüm resimlerinin mümkün oldu÷unca az sayıda
hücreye yerleúmesi beklendi÷i için, gerçekleúmesi istenen bir durum
de÷ildir. Hücrelerdeki resimlerin ait oldu÷u kiúi sayısının, 240
özvektörlük yüz uzayı ile çalıúan BBÇ yöntemi kullanıldı÷ında büyük
55
ölçüde iyileúti÷i ve Gabor filtresi ile alınan sonuca oldukça yaklaútı÷ı
görülmektedir.
ùekil 5.1’de görülebilece÷i gibi, bir hücrede sadece bir kiúiye ait
resimlerin yer almıú oldu÷u durum sayısı DAÇ yöntemi kullanıldı÷ında
maksimum de÷ere ulaúmakta ve bunu bir de÷er geriden Gabor filtresi
takip etmektedir. Grafi÷in tamamına bakıldı÷ında, DAÇ yöntemi
kullanıldı÷ında, bir hücrede iki kiúiye ait; Gabor filtresi kullanıldı÷ında
ise bir hücrede bir kiúiye ait resimlerin yer aldı÷ı durumların ço÷unlukta
oldu÷u görülmektedir. Bu durum ilk görüúte, Gabor filtresi ile daha
yüksek sınıflandırma performansı elde edildi÷i düúüncesini do÷ursa da,
grafi÷in ilerleyen de÷erlerine bakıldı÷ında DAÇ’nin Gabor filtresi
kullanımına göre daha yüksek sınıflandırma performansı verdi÷i açıkça
görülmektedir. Çünkü, grafi÷in ilerleyen de÷erlerinde, DAÇ’ın bir
hücrede 4 kiúiye ait resimlerin bulundu÷u hiçbir durum barındırmadı÷ı
görülürken, bu durum sayısı Gabor filtresi kullanıldı÷ında yediye
çıkmaktadır ve ayrıca, DAÇ yöntemi kullanıldı÷ında, beú kiúinin
resimlerini içeren sadece bir adet hücre bulunurken, Gabor filtresi
kullanıldı÷ında altı kiúinin resimlerini içeren iki hücre bulundu÷u
görülmektedir.
5.2 9+1Testi
Bu performans ölçütü ile sonuç almak için, Bölüm 4.4’de
açıklandı÷ı gibi, her kiúinin dokuzar resminden oluúan 360 adet resimden
ilgili yöntemler ile öznitelik vektörleri çıkartılıp HHA ile indekslendikten
sonra, her kúiye ait kalan birer resimden oluúan 40 adet resimden de aynı
úekilde öznitelik vektörleri çıkartılarak hücre olgunlu÷u de÷eri 11 olacak
úekilde a÷aça eklenir ve a÷aç güncellenir. Bu iúlemler dört öznitelik
çıkartma yöntemi için gerçekleútirildikten sonra, a÷acın en alt
seviyesindeki hücreler incelendi÷inde, sonradan eklenen kırk resmin
yerleúti÷i hücreler ùekil 5.2’de görülebilir. ùekilde, kırk resim
eklendikten sonra, hücre içerisinde resim adedi artan kiúiler yıldız ile
iúaretlenmiútir. Bir hücrede birden fazla yıldız iúaretinin olabildi÷i
görülmektedir. Bu durum, hücrede bulunan bazı kiúilere ait resimlerin bir
arttı÷ını göstermektedir.
56
9+1 Testi
(BBÇ 120 Özvektör)
10
Kiúi1
Kiúi 2
Kiúi 3
Kiúi 4
Kiúi 5
Kiúi 6
Kiúi 7
Kiúi 8
Kiúi 9
9
8
Resim Sayısı
7
6
5
4
3
2
1
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
Hücre Numarası
(a)
9+1 Testi
(Gabor Filtresi)
10
Resim Sayısı
8
Kiúi
Kiúi
Kiúi
Kiúi
Kiúi
Kiúi
Kiúi
1
2
3
4
5
6
7
6
4
2
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
Hücre Numarası
(b)
57
9+1 Testi
(BBÇ 240 Özvektör)
11
Kiúi 1
10
Kiúi 2
Kiúi 3
9
Kiúi 4
Kiúi 5
Resim Sayısı
8
Kiúi 6
7
6
5
4
3
2
1
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58
Hücre Numarası
(c)
9+1 Testi
(DAÇ)
11
10
9
Kiúi 1
Kiúi 2
Kiúi 3
Kiúi 4
Kiúi 5
8
Resim Sayısı
7
6
5
4
3
2
1
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
Hücre Numarası
(d)
ùekil 5.2 9+1 Test sonucu (a) 120 Özvektörlük yüz uzayı kullanan BBÇ,
(b) Gabor filtresi, (c) 240 Özvektörlük yüz uzayı kullanan BBÇ, (d)DAÇ
58
Bu test ile, ideal durumda, sonradan eklenen 40 resmin her birinin,
ait oldu÷u kiúinin resimlerinin ço÷unun bulundu÷u hücreye yerleúmesi
beklenmektedir. ùekil 5.3’de, bu performans testi için uygulanan dört
öznitelik çıkartma yönteminin verdi÷i sonuçlar birbiriyle kıyaslanmıútır.
Bu kıyaslama yapılırken, sonradan eklenen resmin (yıldız ile gösterilen
eleman) yerleúti÷i hücrede, ait oldu÷u kiúinin resminin kaç adet
bulundu÷u bilgisi esas alınmıútır.
ùekil 5.3 incelendi÷inde bu performans ölçütü için en iyi sonuçların
DAÇ yöntemi kullanıldı÷ında alındı÷ı görülmüútür. Örne÷in, ùekil
5.3.(e)’de görüldü÷ü gibi, DAÇ yöntemi kullanıldı÷ında, eklenen kırk
resmin altısı, bir hücrede aynı kiúiye ait 9 resmin bulundu÷u hücreye
yerleúerek, o hücredeki bir kiúiye ait resim sayısını 10 yaparken, Gabor
filtresi kullanıldı÷ında 40 resmin 5’inin ve 240 özvektörden oluúan yüz
uzayı ile çalıúan BBÇ yöntemi kullanıldı÷ında 2’sinin yerleúmesi ile
birlikte o hücredeki bir kiúiye ait resim sayısının 10 olması sa÷lanmıútır.
ùekil 5.3’deki grafikler incelendi÷inde, en kötü performansın 120
özvektörden oluúan yüz uzayı ile çalıúan BBÇ yöntemi kullanıldı÷ında
alındı÷ı görülür. Grafikler incelendi÷inde, dikkat çeken bir di÷er husus
ise, BBÇ yöntemi için yüz uzayını oluúturan özvektör sayısı
arttırıldı÷ında performansın yaklaúık olarak iki katına çıkmıú olmasıdır.
5+1
4
3
Eleman Sayısı
5+1
3
2
2
1
1
1
0
BBÇ 120
Özvektör
Gabor
Filtresi
BBÇ 240
Özvektör
Yöntem
(a)
DAÇ
59
7+1
6+1
4
3
3
3
2
4
5
6+1
5
Eleman Sayısı
Eleman Sayısı
6
1
1
3
7+1
3
2
2
1
1
0
0
0
BBÇ 120
Özvektör
Gabor
Filtresi
BBÇ 240
Özvektör
BBÇ 120
Özvektör
DAÇ
Gabor
Filtresi
(b)
(c)
8+1
9+1
6
8+1
4
3
3
2
2
1
Eleman Sayısı
Eleman Sayısı
6
4
3
0
DAÇ
2
2
1
BBÇ 240
Özvektör
6
5
4
0
Gabor
Filtresi
9+1
5
1
BBÇ 120
Özvektör
DAÇ
Yöntem
Yöntem
5
BBÇ 240
Özvektör
0
BBÇ 120
Özvektör
Gabor
Filtresi
Yöntem
BBÇ 240
Özvektör
DAÇ
Yöntem
(d)
(e)
ùekil 5.3 9+1 Ara Aúamaları
5.3 Bir Kiúinin Resim Da÷ılımı
Bölüm 4.5’de bahsedilen bu performans ölçütününün sonucunu
almak için, 400 adet resimden, ilgili yöntemler ile öznitelik vektörleri
çıkartıldıktan sonra Tablo 4.1’de verilen parametre de÷erleri ile HHA
indekslemesi yapılır.
60
Öznitelik vektörü çıkarma iúlemleri sırasında yine 120 ve 240
özvektörden oluúan yüz uzayı ile çalıúan BBÇ için iki ayrı sonuç
alınırken, DAÇ’de bir sınıfın bir kiúinin beú resminden oluútu÷u ve
toplamda 40 sınıf oldu÷u bilgisine sahip olundu÷u varsayılmıú ve bu bilgi
ıúı÷ında kiúilere ait di÷er beúer resmin nasıl sınıflandı÷ı bu performans
ölçütü cinsinden incelenmiútir.
HHA oluúturulduktan sonra oluúan a÷acın en alt seviyesindeki
hücreler incelendi÷inde, uygulanmıú olan dört öznitelik çıkartma yöntemi
için ùekil 5.4’deki sonuç elde edilmiútir. ùekil 5.4. (a)’da genel yapısı
verilen grafi÷in, aúa÷ı de÷erlerdeki de÷iúimlerinin daha iyi
incelenebilmesi için, (b)’de bu grafik yakınlaútırılmıútır.
ùekil 5.4. (a)’daki 120 özvektörlük yüz uzayı ile çalıúan BBÇ
kullanıldı÷ında, bir hücrede bir kiúiye ait sadece bir resmin bulundu÷u
145 durumla karúılaúıldı÷ı görülür. Bu durum, kiúilere ait di÷er dokuzar
resmin hepsinin bir hücrede bulundu÷u durum sayısı fazla olsaydı
nispeten kötü olmayan bir sonuç olarak de÷erlendirilebilirdi, fakat ùekil
5.4.(b) incelendi÷inde görülecek olan, 120 özvektörlük yüz uzayı ile
çalıúan BBÇ yöntemi kullanıldı÷ında bir kiúiye ait dokuz, sekiz, yedi ve
hatta altı resmin bir hücrede bulundu÷u sadece birer durum oldu÷u için
kötü bir sonuç olarak de÷erlendirilebilir. Yüz uzayı oluúturulurken
çalıúılan özvektör sayısı 240’a çıkartıldı÷ında, bir hücrede bir kiúiye ait
sadece bir resmin bulundu÷u durum sayısı 83 rakamına düúerek, ilk
BBÇ’ye oranla nerdeyse iki katı iyileúme sa÷landı÷ı görülür. 240
özvektör ile çalıúan yüz uzayı kullanan BBÇ’de, ùekil 5.4. (a)’da
görülebilece÷i gibi bir kiúinin sadece bir resminin bir hücrede yer aldı÷ı
durum sayısı 145’den 83’e düúerken, ùekil 5.4. (b) incelendi÷inde bir
kiúinin sekiz, dokuz ve on resminin bir hücrede bulundu÷u ikiúer durumla
karúılaúıldı÷ı görülür. Özvektör sayısı arttırılmıú yüz uzayı ile çalıúan
BBÇ kullanıldı÷ında, Gabor filtresi ile elde edilen sonuca yaklaúıldı÷ı
görülmektedir.
Öznitelik çıkartma yöntemi olarak Gabor filtresi kullanıldı÷ında,
240 özvektörlük yüz uzayı ile çalıúan BBÇ yöntemine göre bir miktar
daha iyi sonuç alınırken, en iyi sonuçlar DAÇ yöntemi uygulandı÷ında
alınmaktadır. Bir hücrede bir kiúinin 10 resminin bulundu÷u durum sayısı
Gabor filtresi uygulandı÷ında beú, DAÇ uygulandı÷ında ise altı olmakla
birlikte, bir hücrede bir kiúinin 9 resminin bulundu÷u durum sayısı Gabor
filtresi uygulandı÷ında iki, DAÇ uygulandı÷ında ise yine altı olmaktadır.
61
Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı
Bir Hücrenin Bir Kiúinin (x) Adet
Resmini øçerdi÷i Durum Sayısı
150
140
BBÇ 120 Özvektör
Gabor Filtresi
BBÇ 240 Özvektör
DAÇ
130
120
110
100
90
80
70
60
50
40
30
20
10
0
1
2
3
4
5
6
7
8
9
10
Bir Kiúiye Ait Resim Sayısı (x)
(a)
Bir Hücrenin Bir Kiúinin (x) Adet Resmini
øçerdi÷i Durum Sayısı
Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı
52
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ 120 Özvektör
Gabor Filtresi
BBÇ 240 Özvektör
DAÇ
1
2
3
4
5
6
7
8
9
10
Bir Kiúiye Ait Resim Sayısı (x)
(b)
ùekil 5.4 Bir Kiúiye Ait Resimlerin Hücrelere Da÷ılımı Test Sonucu
(a) 52’nin üzerinde de÷erler alan noktaları da içeren grafi÷in genel
görüntüsü, (b) 52’nin altındaki de÷erler için yakınlaútırılmıú (a) grafi÷i
62
5.4 Kırkar Resimlik On Devir Testi
Bu testte, Bölüm 4.6’da bahsedilen iúlemleri uygulamak için,
veritabanı resimleri gruplara ayrılır ve birinci gruptan baúlanarak her
devirde bir resim grubundan öznitelik vektörleri çıkartılarak, 1. devirde
HHA ile oluúturulmuú olan a÷aç güncellenir. Kullanılan 40 resimden
oluúan gruplarının her birinde her kiúiye ait birer resim bulunmaktadır ve
toplam 10 adet grup oluúturulmuútur. Her devirde, ilgili gruptan öznitelik
vektörleri çıkartıldıktan sonra HHA güncellenirken, Tablo 4.1’deki
parametreler her devirde, hücre olgunluk de÷eri devir sayısının bir fazlası
seçilecek úekilde kullanılır.
Bu performans ölçütünün sonucu araútırılırken, BBÇ öznitelik
çıkartma yöntemleri kullanılırken, testin uygulama úeklinde bir de÷iúiklik
yapılmıútır. BBÇ yöntemleri için, ilgili BBÇ yönteminin çalıútı÷ı yüz
uzayının oluútu÷u özvektör sayısı kadar resimden öznitelik vektörleri
çıkartılmadan testin baúlamamıú oldu÷u kabul edilir. Dolayısıyla, 120
özvektörden oluúan yüz uzayı ile çalıúan BBÇ kullanımı için, ilk
sınıflandırma devri 3’den ve 240 özvektörden oluúan yüz uzayı ile çalıúan
BBÇ kullanımı için 6’dan baúlamaktadır. Bunun sebebi, her resmin
üzerine yansımasının alınaca÷ı belli sayıdaki özvektörden oluúan yüz
uzayının elde edilebilmesi için, bu sayı kadar resimden oluúan e÷itim
kümesine ihtiyaç duymasıdır (Bkz. Bölüm 3.1.1).
63
Devir 1
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i
Durum Sayısı
40
35
Gabor Filtresi
30
DAÇ
25
20
15
10
5
0
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
Devir 2
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
40
35
Gabor Filtresi
30
DAÇ
25
20
15
10
5
0
1
2
3
4
5
6
Br Kiúiye Ait Resim Sayısı
7
8
9
10
64
Devir 3
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
45
BBÇ (120 Özvektör)
40
Gabor Filtresi
35
DAÇ
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
Devir 4
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
55
BBÇ (120 Özvektör)
50
Gabor Filtresi
45
DAÇ
40
35
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
Br Kiúiye Ait Resim Sayısı
(a) Devir 1, Devir 2, Devir 3 ve Devir 4
9
10
65
Devir 5
105
100
BBÇ (120 Özvektör)
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
95
90
Gabor Filtresi
85
DAÇ
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(b) Devir 5
B ir H ücrede B ir K iúinin (x) A det R esm ini øçerdi÷i
D urum S ayısı
Devir 5
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
DAÇ
1
2
3
4
5
6
7
Br Kiúiye Ait Resim Sayısı
(c) Yakınlaútırılmıú Devir 5
8
9
10
66
Devir 6
120
Bir Hücrede Bir Kiúinin (x) Adet Resm ini øçerdi÷i Durum
Sayısı
115
BBÇ (120 Özvektör)
110
105
Gabor Filtresi
BBÇ (240 Özvektör)
100
DAÇ
95
90
85
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(d) Devir 6
B ir H ü cred e B ir K iúin in (x) A d et R esm in i øçerd i÷ i
D u ru m S ayısı
Devir 6
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
Br Kiúiye Ait Resim Sayısı
(e) Yakınlaútırılmıú Devir 6
8
9
10
67
B ir H ü c re d e B ir K iú in in (x ) A d e t R e s m in i øç e rd i÷ i
D u ru m S a y ıs ı
Devir 7
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(f) Devir 7
B ir H ü c re d e B ir K iú in in (x ) A d e t R e s m in i øç e rd i÷ i
D u ru m S a y ıs ı
Devir 7
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
Br Kiúiye Ait Resim Sayısı
(g)Yakınlaútırılmıú Devir 7
8
9
10
68
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
Devir 8
145
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(h) Devir 8
B ir H ü c re d e B ir K iú in in (x ) A d e t R e s m in i øç e rd i÷ i
D u ru m Sa y ıs ı
Devir 8
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
Br Kiúiye Ait Resim Sayısı
(i)Yakınlaútırılmıú Devir 8
8
9
10
69
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i Durum
Sayısı
Devir 9
145
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(j) Devir 9
B ir H ü c re d e B ir K iú in in (x ) A d e t R e s m in i øç e rd i÷ i
D u ru m S a y ıs ı
Devir 9
60
58
56
54
52
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
Br Kiúiye Ait Resim Sayısı
(k)Yakınlaútırılmıú Devir 9
8
9
10
70
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷i
Durum Sayısı
Devir 10
150
145
140
135
130
125
120
115
110
105
100
95
90
85
80
75
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
8
9
10
Br Kiúiye Ait Resim Sayısı
(l) Devir 10
Bir Hücrede Bir Kiúinin (x) Adet Resmini øçerdi÷ i
Durum Sayısı
Devir 10
54
52
50
48
46
44
42
40
38
36
34
32
30
28
26
24
22
20
18
16
14
12
10
8
6
4
2
0
BBÇ (120 Özvektör)
Gabor Filtresi
BBÇ (240 Özvektör)
DAÇ
1
2
3
4
5
6
7
8
Br Kiúiye Ait Resim Sayısı
(m)Yakınlaútırılmıú Devir 10
ùekil 5.5 Kırkar Resimlik On Devir Test Sonucu
9
10
71
ùekil 5.5’deki test sonuçları incelendi÷inde, öznitelik vektörü
çıkartma yöntemi olarak, 120 özvektörden oluúan yüz uzayı ile çalıúan
BBÇ kullanıldı÷ında, her yeni devirde, bir hücrede bir kiúiye ait resim
sayısının bir oldu÷u durum sayısı üzerinde yı÷ılma gerçekleúti÷i
görülürken, 240 özvektörlük yüz uzayı ile çalıúan BBÇ kullanıldı÷ında,
aynı de÷er üzerinde her yeni devirde herhangi bir yı÷ılma
görülmemektedir. Her yeni devirde, bu de÷er üzerinde yı÷ılma olması,
yeni eklenen bir kiúiye ait her resmin o kiúiye ait di÷er resimlerin oldu÷u
hücrelerden birinde yer almak yerine, o kiúiye ait hiçbir resmin olmadı÷ı
bir hücrede yer aldı÷ı anlamına gelir ve bu istenen bir durum de÷ildir.
Her devire ait grafik detaylı incelenirse, DAÇ yöntemi
kullanımının, her devirde bir kiúiye ait devir sayısı kadar resmin aynı
hücrede yer aldı÷ı durumların sayısını en yüksek de÷erde çıkardı÷ı
görülmektedir. Bununla birlikte, 240 özvektörlük yüz uzayı ile çalıúan
BBÇ ve Gabor filtresi kullanımının birbirine benzer sonuçlar ortaya
koydukları ve bazı devirlerde DAÇ’nin performansını yakaladıkları
görülmektedir. Gabor Filtresi kullanımı, DAÇ’nin performans baúarısını
Devir 3’de yakalarken, Devir 4’de taúıyamamakta ve Devir 6’dan itibaren
DAÇ’nin performansına tekrar yaklaúmaktadır. Devir 6 ve 7’de DAÇ’ın
performansını yakalayan 240 özvektörlük yüz uzayı ile çalıúan BBÇ
kullanımı, devir sayısı 10’a yaklaútıkça DAÇ’dan bir miktar
uzaklaúmaktadır.
5.5 Sınıflandırma Baúarımı Testi
Her kiúiye ait beúer resimden oluúan 200 adet resim içeren bir resim
grubundan, ilgili yöntemlerle öznitelik vektörleri çıkartıldıktan sonra,
hücre olgunluk de÷eri 6 olacak úekilde Tablo 4.1’deki parametrelerle
HHA oluúturulmuútur. Bu iúlemin ardından, her kiúiye ait kalan beú
resimden oluúan ikinci 200 resimlik gruptan da ilgili yöntemlerle
öznitelik vektörleri çıkartılarak, bu sefer hücre olgunluk de÷eri 11 olacak
úekilde HHA güncellenir. Son durumda, a÷acın, en alt seviyesindeki
hücreler incelendi÷inde, de÷erleri Tablo 5.1’de verilen ùekil 5.6’daki
Sınıflandırma Baúarımı testi sonuç grafi÷i elde edilir.
Bu performans ölçütü için, 40 kiúinin ilk sekizer resimlerinden
oluúan 320 adet resmin, bilgisine sahip olunan resimler olarak kabul
edildi÷i ve ilgili yöntemler ile öznitelik vektörleri çıkartılarak HHA ile
72
indekslendikten sonra, her kiúiye ait kalan ikiúer resimden oluúan 80 adet
resmin aynı iúlemlerden geçirilerek oluúturulan a÷aca eklendi÷i test
sonucuna (Aslan et al., 2007) incelenerek ulaúılabilir.
Tablo 5.1 Öznitelik Çıkartma Yöntemleri øçin Sınıflandırma Baúarımı
Test Sonuçları
Yöntem &
Sonradan
Eklenen
Resim
Sayısı
BBÇ
(120 Özvektör)
108
48
15
12
8
4
2
2
1
0
1
2
3
4
5
6
7
8
9
10
Sınıflandırma
Baúarımı
Gabor Filtresi
9
200
%4.5
BBÇ
(240 Özvektör)
45
36
36
21
19
14
15
6
3
5
43
200
%21.5
DAÇ
81
32
16
18
15
15
11
6
4
2
38
200
%19
24
18
24
30
20
27
20
20
14
3
84
200
%42
Tablo 5.1’de verilen test sonuçları incelendi÷inde, öznitelik
çıkartma yöntemi olarak, 120 özvektörden oluúan yüz uzayı ile çalıúan
BBÇ kullanıldı÷ında sonradan eklenen 200 resmin 9, Gabor filtresi
kullanıldı÷ında 43, 240 özvektörden oluúan yüz uzayı ile çalıúan BBÇ
kullanıldı÷ında 38 ve DAÇ kullanıldı÷ında 84 tanesinin ait oldu÷u kiúinin
resimlerinin ço÷unlukta oldu÷u hücrelere yerleúmiú oldu÷u görülür. Bu
sayı de÷erleri ile elde edilen sınıflandırma baúarımı yüzdesi Tablo 5.1’in
son satırında verilmiútir. Bu de÷erler incelendi÷inde, en yüksek baúarımın
DAÇ ve bunu büyük bir de÷er farkıyla takip eden Gabor filtresi
kullanıldı÷ında elde edildi÷i görülmektedir. 240 özvektörden oluúan yüz
uzayı ile çalıúan BBÇ kullanıldı÷ında Gabor filtresi ile elde edilen sonuca
çok yaklaúılırken, 120 özvektörden oluúan yüz uzayı ile çalıúan BBÇ
kullanıldı÷ında oldukça kötü bir sınıflandırma baúarımı sonucu elde
edilmektedir.
73
Tablo 5.1 ve ùekil 5.6’dan incelenebilece÷i gibi, di÷er testlerde
alınan sonuçlara benzer olarak, bu test sonucunda da BBÇ kullanımı
sırasında yüz uzayı oluúturulurken çalıúılan özvektör sayısının arttırılması
performansı önemli ölçüde arttırmaktadır.
Sınıflandırma Baúarımı Testi
110
105
100
S o n ra d a n E k le n e n R e s im S a y ıs ı
95
90
BBÇ (120 Özvektör)
85
Gabor Filtresi
80
BBÇ (240 Özvektör)
75
DAÇ
70
65
60
55
50
45
40
35
30
25
20
15
10
5
0
1
2
3
4
5
6
7
8
Hücrede Bir Kiúiye Ait Resim Sayısı
ùekil 5.6 Sınıflandırma Baúarımı Test Sonucu
9
10
74
6 SONUÇ
Tez çalıúması kapsamında, Giriú bölümünde bahsedilmiú olan
senaryodan yola çıkılarak, literatürde yüz tanıma problemi için sıkça
kullanılmıú olan Baúlıca Bileúenler Çözümlemesi ve Do÷rusal Ayrıútırma
Çözümlemesi öznitelik çıkartma yöntemleri MUVIS sistemine entegre
edilerek,
pasaport
foto÷rafı
formatındaki
yüz
resimlerinin
sınıflandırılması iúlemi gerçekleútirilmiútir.
Hiyerarúik Hücresel A÷aç indeksleme yöntemini dahilinde
bulunduran MUVIS sistemi üzerine, úimdiye kadar entegre edilmiú olan
çoklu ortam öznitelik çıkartma yöntemleri arasında, yüz resimlerinin
sınıflandırılması problemine uyarlanabilecek olan “Gabor Filtresi ile
öznitelik çıkartma yöntemi” bulunmaktadır. Bu tez çalıúmasında, BBÇ ve
DAÇ yöntemleri, MUVIS’e entegre edilmiú, HHA üzerindeki
sınıflandırma performansı, Gabor Filtresi ile kıyaslanmıútır. Bu
kıyaslamaları yapabilmek için, bu tez çalıúması kapsamında performans
ölçütleri geliútirilmiútir.
Tez çalıúmasının Giriú bölümünde bahsedilmiú olan senaryo temel
alındı÷ında, bir miktar yüz resmine baúlangıçta sahip olundu÷u
düúünülmektedir. Sahip olunan bu yüz resimleri veritabanından öyle
etkin öznitelik vektörleri çıkartılmalı ve öyle etkin bir yöntemle
indekslenmelidir ki, sonuç olarak ideal durumda, bir kiúinin tüm
resimlerine aynı anda ulaúılabilmelidir. Bununla birlikte, bilgisine sahip
olunan bu veritabanına, yeni yüz resimleri eklendi÷inde, ideal durumda,
yeni eklenen bu resimler de ait oldu÷u kiúinin resimlerinin bulundu÷u
toplulu÷un içinde yer almalı ve yeni eklenen resimler ile bilgisine sahip
olunan veritabanı kendisini güncellemelidir. Bu sayede, veritabanında
bulunan kiúilere ait her yeni resim eklendi÷inde, bir kiúiye ait, sahip
olunan yüz karakteristi÷i bilgisi zenginleúerek sınıflandırma
performansını arttırmalıdır.
Gerçekleútirilen testlerde, sınıflandırma do÷rulu÷u açısından en iyi
sonuçlara DAÇ yöntemi kullanıldı÷ında, en kötü sonuçlara ise 120
özvektörden oluúan yüz uzayı ile çalıúan BBÇ yöntemi kullanıldı÷ında
sahip olunmuútur. Aynı zamanda, Gabor Filtresi kullanımı ile elde edilen
performansın, DAÇ yöntemi ile elde edilen performansa bazı testlerde
yaklaútı÷ı görülmektedir. Bununla birlikte, dikkat çeken baúka bir durum
da, BBÇ kullanımı sırasında çalıúılan yüz uzayını oluúturan özvektör
75
sayısı iki katına çıkartıldı÷ında, elde edilen performansın yaklaúık iki kat
artarak Gabor filtresi ile elde edilen performansa yaklaúmıú oldu÷udur.
Literatürde BBÇ yöntemi genellikle di÷er iki yöntem ile beraber,
boyut küçültme amacıyla kullanılmaktadır. Bu tez çalıúmasında
gerçekleútirilen testlerde de BBÇ ile 120u 1 ve 240u 1 boyutlu öznitelik
vektörleri kullanılırken, DAÇ’de resimler üzerinde boyut küçültme iúlemi
gerçekleútirilmesine ra÷men 2576u 1 boyutlu öznitelik vektörleri ile
çalıúılmıútır. BBÇ’nin bu açıdan az bellek kullanımı avantajına ra÷men
sınıflandırma do÷rulu÷u daha düúük sonuçlar vermesi, her yeni resim
eklendi÷inde, benzerlik hesabı sırasında Öklid uzaklı÷ı metri÷i kullanan
HHA indeksleme yönteminin, a÷aç dahilinde bulunan resimlerin
öznitelik vektörlerinin sonradan eklenen resimlerin karakteristik bilgisini
yeterince iyi taúıyamaması úeklinde açıklanabilir.
Esasında, uygulanan DAÇ öznitelik çıkartma yönteminin, hücre
içerisindeki eleman sayısı ve yo÷unluk de÷eri esasına göre çalıúarak
sınıflar oluúturan HHA indeksleme yönteminin sınıflandırma baúarısını,
bu derece arttırması beklenen bir durum olarak de÷erlendirilebilir, çünkü
DAÇ ile baúlangıçta, bir kiúiye ait belli miktardaki resmin bir sınıfı
oluúturdu÷u varsayımı yapılarak, bir kiúiye ait resimleri biraraya toplayan
ve farklı kiúilerin resimlerini birbirinden uzaklaútıran bir ayrıútırma uzayı
kullanılmıú ve tüm resimler bu uzay üzerine yansıtılarak, her resim için
ayrıútırma prensibini mümkün oldu÷unca çok taúıyan öznitelik vektörleri
elde edilmiútir.
Tez kapsamında gerçekleútirilen testlerde, 400 resimden vesikalık
foto÷raf formatındaki bir yüz resimleri veritabanı kullanılmıútır. Günlük
hayatta çok daha fazla sayıda resimden oluúan veritabanları ile çalıúılması
gerekece÷i düúünülürse, gelecek çalıúmalarda, daha büyük boyutlu bir
yüz resimleri veritabanı kullanılarak, ilgili öznitelik çıkartma
yöntemlerinin, HHA indeksleme yöntemi kullanılırken, bu veritabanı
üzerindeki sınıflandırma etkisi araútırılabilir. Bu noktada, BBÇ yöntemi
için performans baúarımının yüksek olması açısından, kullanılacak olan
yüz uzayının, en az kaç özvektörden oluúması gerekti÷inin, kullanıcının
kararından çıkartılarak, MUVIS sisteminin otomatik bir úekilde
hesaplayaca÷ı bir parametre olarak kullanıcıya iletmesi ve kullanıcının
özvektör sayısını seçerken, bu uyarıyı dikkate alması yararlı olacaktır.
Bu tez çalıúmasında, DAÇ yöntemi uygulanırken, baúlangıçta
bilgisine sahip olundu÷u varsayılan kiúilere ait resim sınıfları, yöntem
çalıúırken kendini güncellememektedir. Yani, baúlangıçta bir kiúiye ait 5
76
resme sahip olundu÷u kabul edilip, bir sınıfı beú resmin oluúturdu÷u 40
adet sınıfa sahip olundu÷u varsayılmıútır ve kiúilere ait baúka resimler
sisteme eklendi÷inde her sınıfın içinde yer alan resim bilgisi kendini
güncellemeyerek sabit kalmaktadır. Gelecek çalıúmalarda, DAÇ yöntemi
HHA indeksleme yapısı kullanan MUVIS sistemine uyarlanırken,
tasarım, baúlangıçta varsayılan sınıf bilgisi, HHA ile oluúan a÷acın en alt
seviyesindeki bir hücre içerisindeki resim bilgisinden oluúacak úekilde
geliútirilebilir. Bu durumda, a÷aca her yeni eleman eklendi÷inde HHA
hücre içi bilgisini güncelledi÷inde, bu sınıf bilgisinin güncellenmesine de
yansımıú olur. Bu noktada karúılaúılabilecek bir sorun, ayrıútırma uzayı
oluúturulurken her hücre bir sınıf olarak kabul edildi÷inde, hücre
içerisindeki yo÷unluk de÷eri kötüyse, bu yöntem uygulandı÷ında daha da
kötüye gidece÷idir.
77
KAYNAKLAR DøZøNø
Aslan S., Tunalı T., Cinsdikici M., 2007, Vesikalık Foto÷rafların
Sınıflandırılması øçin Özellik Ölçütleri Üzerine Kıyaslamalı Bir
Çalıúma, IEEE 15. Sinyal øúleme ve Uygulamaları Kurultayı (SIU),
IEEE Katalog Numarası: 07EX1578C, ISBN: 1-4244-0720-6,
Kongre Kütüphanesi: 2006934021, Bildiri No: 285.
Belhumeur P.N., Hespanha J.P., Kriegman D.J., 1997, Eigenfaces vs.
Fisherfaces: Recognition Using Class Specific Linear Projection,
IEEE Transactions on Pattern Analysis and Machine
Intelligence ,Vol. 19, No. 7, pp. 711-720.
Bentley J.L., 1975, Multidimensional Binary Search Trees Used for
Associative Searching, , in Proc. Of Communications of the ACM,
Vol. 18, n.9, pp. 509-517.
Berchtold S., Bohm C., Jagadish H. V., Kriegel H.P., Sander J., 2000,
Independent Quantization: An Index Compression Technique for
High-Dimensional Data Spaces, In Proc. of the 16th Int. Conf. on
Data Engineering, pp.577-588.
Bozkaya T., Ozsoyoglu Z. M., 1997, Distance-Based Indexing for HighDimensional Metric Spaces, SIGMOD Conference, pp. 357-368.
Brin S., 1995, Near Neighbor Search in Large Metric Spaces, In
Proceedings of the 21th international Conference on Very Large
Data Bases, pp. 574-584.
Chakrabarti K., Mehrotra S., 1999, The hybrid tree: An index structure
for high dimensional feature spaces, In Proc. Int. Conf. on Data
Engineering, pp. 440-447.
78
KAYNAKLAR DøZøNø (devam)
Ciaccia P., Patella M., Zezula P., 1997, M-tree: An Efficient Access
Method for Similarity Search in Metric Spaces, In Proceedings of
the 23rd international Conference on Very Large Data Bases, pp.
426-435.
Cooley W.W., Lohnes P.R., 1971, Multivariate data analysis, John
Wiley & Sons.
Daugman J. G., 1980, Two-dimensional spectral analysis of cortical
receptive field profiles, Vision Research, Vol. 20, no 10,pp. 847856
Fukunaga K., 1990, Introduction to statistical pattern recognition,
Academic Press Professional, Inc. San Diego, CA, USA.
Gaede V., Günther O., 1998, Multidimensional access methods, ACM
Comput. Surv. Vol.30, no 2 , pp. 170-231.
Guttman A., 1984,. R-trees: a dynamic index structure for spatial
searching, SIGMOD Conference, pp. 47-57.
Hesher M. C., 2003, Automated Face Tracking and Recognition, MSc.
Thesis, Florida State University.
Katayama N., Satoh S., 1997, The SR-tree: an index structure for highdimensional nearest neighbor queries, In Proceedings of the 1997
ACM SIGMOD international Conference on Management of Data.
79
KAYNAKLAR DøZøNø (devam)
Kiranyaz S, 2005, Advanced Techniques for Content-Based
Management of Multimedia Databases, PhD. Thesis at Tampere
University of Technology, Tampere, Finland.
Kiranyaz S., Gabbouj M., 2005, A Novel Multimedia Retrieval
Technique: Progressive Query (WHY WAIT?), IEEE Proceedings
Vision, Image and Signal Processing, Vol. 152, no. 3, pp. 356-366.
Kiranyaz S., Gabbouj M., 2007, Hierarchical Cellular Tree: An
Efficient Indexing Scheme for Content-based Retrieval on
Multimedia Databases, IEEE Transactions on Multimedia, Vol. 9,
no 1, pp. 102-119.
Kirby M., 2000, Geometric Data Analysis: An Empirical Approach to
Dimensionality Reduction and the Study of Patterns, John Wiley &
Sons, Inc. New York.
Kirby M., Sirovich L., 1990, Application of the Karhunen-Loeve
Procedure for the Characterization of Human Faces, IEEE
Transactions on Pattern Analysis and Machine Intelligence, Vol.
12, I.1, pp. 103-108.
Lin K., Jagadish H.V., Faloutsos C., 1994, The TV-tree: an index for
high dimensional data, Very Large Databases (VLDB) Journal,
3(4), pp. 517-543.
Liu C., Wechsler H., 2001, A Gabor Feature Classifier for Face
Recognition, ICCV, p 270.
80
KAYNAKLAR DøZøNø (devam)
Marcel S., Bengio S., 2002, Improving Face Verification Using Skin
Color Information, Proceedings of the 16th International
Conference on Pattern Recognition, ICPR, Vol. 2, pp. 11-15.
Nastar C., Mitschke M., 1998, Real-time face recognition using feature
combination, Third IEEE International Conference on Automatic
Face and Gesture Recognition, pp. 312 – 317.
Niblack W., Barber R., 1993, The QIBC project: Querying images by
content using color, texture and shape, In Storage and Retrieval for
Image and Video Databases I, SPIE Proceedings Series, Vol. 1908.
Pentland A., Moghaddam B. , Starner T., 1994, View-based and
modular eigenspaces for face recognition, IEEE Computer Society
Conference on Computer Vision and Pattern Recognition, pp. 84-91
Rui Y., Huang T. S., Chang S. F., 1999, Image Retrieval: Past, Present
and Future, Journal of Visual Communication and Image
Representation, Vol. 10, pp. 1 - 23.
Sakurai Y., Yoshikawa M., Uemura S., Kojima H., 2000, The A-tree:
An Index Structure for High-Dimensional Spaces Using Relative
Approximation, in Proc. of the 26th International Conference on
Very Large Data Bases (VLDB), pp. 516-526.
Sebestyen G.S., 1962, Decision-making processes in pattern recognition,
Macmillan New York
Sellis T. K., Roussopoulos N., Faloutsos C., 1987, The R+-Tree: A
Dynamic Index for Multi-Dimensional Objects, In Proc. of the 13th
International Conference on Very Large Data Bases, pp.507-518.
81
KAYNAKLAR DøZøNø (devam)
Sirovich I., Kirby M., 1987, Low-dimensional procedures for the
characterization of human faces, Journal Optical Soc. Of Am. A,
Vol. 2, pp. 519-524.
Stricker M. A., Orengo M., 1995, Similarity of Color Images, SPIE
Proceedings, Vol. 2420.
Swain M.J., Ballard D.H., 1991, Color Indexing, Intern. Journal of
Computer Vision, Vol 7, pp. 11-32.
Tjahyadi R., Liu W., Venkatesh S., 2004, Automatic Parameter
Selection for Eigenfaces, 6th International Conference on
Optimization Techniques and Applications (ICOTA 2004).
Turk M., 2001, A Random Walk through Eigenspace, IEICE
TRANSACTIONS on Information and Systems, Vol.E84D No.12 pp.1586-1595.
Turk M., Pentland A., 1991, Eigenfaces for Recognition, J. Cognitive
Neuroscience, Vol. 3, No. 1.
Wang H., Perng C., 2001, The S2-Tree: An Index Structure for
Subsequence Matching of Spatial Objects, In Proceedings of the 5th
Pacific-Asia Conference on Knowledge Discovery and Data
Mining.
Yianilos P. N., 1993, Data structures and algorithms for nearest neighbor
search in general metric spaces, In Proceedings of the Fourth
Annual ACM-SIAM Symposium on Discrete Algorithms.
82
KAYNAKLAR DøZøNø (devam)
Zhao W., Chellappa R., Phillips P. J., Rosenfeld A., 2003, Face
recognition: A literature survey. ACM Comput. Surv. 35, 4 , pp.
399-458.
Zhou X., Wang G., Yu J. X., Yu G., 2003, M+-tree: a new dynamical
multidimensional index for metric spaces, In Proc. of the
Fourteenth Australasian database conference on Database
technologies, pp.161-168.
øNTERNET ERøùøMø
Gutierrez-Osuna R., 2002, Lecture Notes on Fisher
Discriminants,
http://research.cs.tamu.edu/prism/lectures/pr/pr_l10.pdf
Linear
MUVIS v1.8 Kurulumu, http://muvis.cs.tut.fi/download.html
TUT MUVIS Xt Projesi, 2006, MUVIS: A System for Content-Based
Indexing
and
Retrieval
in
Multimedia
Databases,
http://muvis.cs.tut.fi/
The ORL Database of Faces, 1992-1994, AT&T Laboratories,
http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html
83
EKLER
Ek 1 MUVIS
Ek 2 Türkçe øngilizce Terimleri Sözlü÷ü
84
Ek 1 MUVIS
Temel MUVIS Uygulamaları
ùekil 1’de görüldü÷ü gibi MUVIS iskeleti, farklı görevlere sahip
olan üç temel uygulamanın çalıúmasına dayanmaktadır.
Ek 1 ùekil 1 MUVIS iskeletinin genel yapısı
AVDatabase, ses/video kliplerini yakaladıktan, kodladıktan ve
bilgisayara ba÷lı olan bir cihazdan kaydettikten sonra ses/video
veritabanı oluúturmaktan sorumludur. Bu tez çalıúmasında bu uygulama
hiç kullanılmadı÷ı için sadece genel tanımının verilmesi yeterli
görülmüútür.
85
DbsEditor’ ün temel görevi çoklu ortam indekslenmesinin
sa÷lanması iken, MBrowser çoklu ortam veritabanlarının taranması ve
sorgu yapılmasından sorumludur.
Benzerlik uzaklıkları, ilgili görsel/iúitsel öznitelik çıkartma (FeX veya
AFeX) modüllerinde gerçekleútirilen belirli fonksiyonlar ile hesaplanır.
DbsEditor
Ek 1 ùekil 2 MUVIS DbsEditor Uygulaması
86
DbsEditor, indeksleme ve veritabanları için di÷er düzenleme
iúlemlerinin gerçekleútirildi÷i yerdir. Baúlıca görevleri, resimlerden
öznitelik çıkarımının sa÷lanması ve bu öznitelikleri kullanarak veritabanı
resimlerinin HHA ile indekslenmesidir. DbsEditor’ ün tüm iúlevleri
aúa÷ıdaki gibi maddelenebilir:
i.
ii.
iii.
iv.
Herhangi bir MUVIS veritabanına yeni ses / video klibi veya
resim ekleme veya veritabanından eleman silme.
Yeni öznitelik çıkarma modüllerinin (FeX ve AFex) entegre
edilmesi ve yönetimi.
Mevcut FeX ve AFex modülleri yardımı ile bir veritabanından
yeni öznitelikler çıkarma veya veritabanında kullanılmıú olan
öznitelikleri silme.
HHA ile indeksleme gerçekleútirme.
MBrowser
Ek 1 ùekil 3 MUVIS Mbrowser Uygulaması
87
MBrowser, kullanıcıların bir MUVIS veritabanındaki herhangi bir
elemana eriúmesini sorgu yoluyla veya veritabanı tarama yoluyla
gerçekleútirir. Bir eriúim yöntemi olan Aúamalı Sorgu (Kiranyaz ve
Gabbouj, 2005), MUVIS takımı tarafından geliútirilmiú ve bu
uygulamaya eklenmiútir.
MBrowser ile veritabanı öznitelik vektörleri ve parametreleri
görüntülenmektedir. Aynı zamanda HHA ile indekslenmiú veritabanı
taranırken, hücre istatistikleri görüntülenmektedir.
MUVIS’de Görsel Öznitelik Çıkarımı
MUVIS’deki veritabanı elemanlarının öznitelik vektörleri
normalize edilmiú sayı dizileri ile gösterilir. Öznitelik çıkarma (FeX)
modüllerinin sisteme dinamik olarak entegre edilmesi için özniteliklerin
vektör gösterimi gibi ortak ve kolay desteklenebilir bir formatta
gösterilmesi gerekir. Öznitelik vektörleri, dinamik ve ba÷ımsız FeX
modülleri tarafından çıkartılır ve MUVIS’de esasen iki uygulama
tarafından kullanılır: DbsEditor ve MBrowser.
MBrowser, farklı tipteki öznitelik vektörlerini birleútirmek için
normalize edilmiú öznitelik vektörlerine gereksinim duyar. Bu amaçla,
bir öznitelik vektörünün her elemanının de÷eri, vektörün teorik olarak
maksimum de÷erine bölünür.
DbsEditor, öznitelik çıkarıma yönetiminden sorumludur ve
veritabanı elemanlarından, gerçekleútirilmiú olan herhangi bir öznitelik
çıkarma algoritması ile öznitelikler çıkartabilir veya bir veritabanından
çıkartılmıú olan öznitelikler silebilir. DbsEditor ayrıca farklı
parametrelerde birden fazla öznitelik çıkarımına imkan tanır.
DbsEditor’ün kullandı÷ı FeX modülünü MBrowser da sorgu ve benzerlik
hesabı iúlemleri için kullanır.
88
FeX iskeleti
MUVIS iskeletinde video klipler ve resimler olmak üzere baúlıca iki
görsel ortam elemanı bulunmaktadır. Resim öznitelikleri 24 bitlik RGB
çerçeve tamponundan çıkartılır. Video kliplerde ise öznitelik çıkarımı
için anahtar çerçeveler kullanılır. Bu tez çalıúmasında resim veritabanları
ile ilgilenildi÷i için, MUVIS’deki video klipleri için gerçekleútirilebilen
iúlemler üzerinde durulmamıútır.
FeX arayüzü, Fex_API.h dosyasında tanımlanmıútır ve herhangi bir
öznitelik çıkartma algoritması bu Kullanıcı arayüzü (API) baúlık
dosyasını kullanan bir DLL olarak oluúturularak sisteme entegre
edilebilir. Fex_API.h, tüm öznitelik çıkartma iúlemlerini dinamik olarak
yönetmek için gerekli olan beú farklı Kullanıcı arayüzü (API) fonksiyonu
tanımlar. Ayrıca öznitelik çıkarımının ve modül ile uygulama arasındaki
iletiúimin sa÷lanması için gerekli olan bir veri yapısı içerir. ùekil 4,
Kullanıcı arayüzü (API) fonksiyonlarını ve örnek bir Fex modulü ile
MUVIS uygulamaları arasındaki etkileúimi özetlemektedir.
Ek 1 ùekil 4 MUVIS uygulamaları ile FeX modül etkileúimi
89
FeX algoritmaları DLL olarak gerçekleútirildikten sonra uygun bir
klasörde (uygulamaların bulundu÷u klasörde veya C:\MUVIS\
klasöründe) saklanmalıdır. Bir FeX modülünün Fex_[öznitelik fourCC
kodu].dll (örn. “Fex_HSV.dll”) úeklinde isimlendirilmesi tavsiye
edilmektedir.
Bir veritabanından çıkartılmıú olan öznitelik vektörleri belirli
tipdeki dosyalarda saklanır. Resimlerden oluúan bir veritabanının, bir
FeX modülü ile çıkartılmıú olan resim özniteliklerinin tamamı, veritabanı
dosyası ile aynı klasörde bulunan tek bir dosyaya kaydedilir. Bu dosya,
[ilgili
veritabanı
ismi]_Fex.[FourCC
kodu]
(örn.
“Veritabanım_Fex.HSV”) úeklinde isimlendirilir.
FeX veri yapıları
FrameType Numaralandırma: Öznitelik çıkarımı için kullanılan çerçeve
formatlarını tanımlar. RGB 24 bit ve YUV 4:2:0 çerçeve tamponları
desteklenmektedir.
FexParam Yapısı: FeX modülü tarafından, kendisini MUVIS
uygulamasına tanıtması için yaratılır ve elemanlarına de÷erler atanır.
FrameParam Yapısı: Bir MUVIS uygulaması, FrameParam yapısında
saklanmakta olan çerçeve özniteliklerinin çıkarılması için FexExtract
fonksiyonunu ça÷ırır. Çerçevenin formatı, FeX modülü tarafından
FexParam içerisinde belirtilen formatdır.
Modüllerdeki kullanıcı arayüzü fonksiyonları
int Fex_Bind(FexParam*): MUVIS uygulaması ile FeX modülü
arasındaki tokalaúma iúlemi için kullanılır. FeX modülün FexParam
yapısına ait elemanları doldurarak kendisini uygulamaya tanıtmasını
sa÷lar. Bu fonksiyon, MUVIS uygulaması FeX modülü ile arasında
ba÷lantı kurduktan hemen sonra sadece bir kere ça÷rılır. Bir sorun
oldu÷unda fonksiyon sıfır döndürür.
int Fex_Init(double*): FeX modülünü ilklendirmek için kullanılır ve FeX
modülü, bellek ayırma, tablo yaratımı ...vs gibi ilklendirme iúlemlerini
90
gerçekleútirir. Bu fonksiyon, MUVIS uygulamasında öznitelik çıkartma
parametreleri girildikten sonra sadece bir kere ça÷rılır ve bir sorunla
karúılaúıldı÷ında sıfır döndürür.
double* Fex_Extract(FrameParam, int&): FrameParam yapısı
içerisinde iúaretlenen resim (çerçeve) tamponunun özniteliklerini
çıkartmak için kullanılır. Veritabanındaki her resim için bu fonksiyon
ça÷rılır ve her resmin çifte duyarlıklı öznitelik vektörü geri döndürülür.
Daha öncede belirtildi÷i gibi, bu vektörler dll oluúturulurken öznitelik
vektöründeki her de÷er 0.0 ve 1.0 arasında olacak úekilde normalize
edilmelidir. Bu normalizasyon iúlemi, MBrowser’da sorgu iúlemi
sırasında birden fazla özniteli÷i birleútirmek için gerekmektedir.
int Fex_Exit(FexParam*): FeX modül iúlemlerini sıfırlamak ve
sonlandırmak için kullanılır. FexParam yapısı için Fex_Bind fonksiyonu
ile ayrılmıú olan bellek alanı bu fonksiyon ile geri kazanılır. Ayrıca
Fex_Init önceden ça÷rılmıú ise bu fonksiyon FeX modülü baúka öznitelik
çıkartma iúlemleri için sıfırlar. Bu fonksiyonun, her FeX iúleminden
sonra sıfırlamanın gerçekleútirilmesi için ça÷rılabilecek iken, MUVIS
uygulamasının kapatılması sırasında en az bir kere ça÷rılması
gerekmektedir.
double Fex_GetDistance(double*, double*, int): Bu fonksiyon iki
öznitelik vektörü arasındaki benzerlik hesabının hesaplanmasında
kullanılır. Bu yüzden, iki öznitelik vektörü arasında gerçekleútirilecek
olan uygun uzaklık metri÷i bu fonksiyon içerisinde tanımlanmalıdır.
Hesaplalan iki vektör arasındaki uzaklık çifte duyarlıklı bir de÷er olarak
geri döndürülür.
MUVIS’de öznitelik çıkartma iúlemleri
Aúa÷ıdaki adımlar, DbsEditor uygulaması tarafından, herhangi bir ortam
elemanından öznitelik çıkarma amacıyla gerçekleútirilir:
i.
DbsEditor uygulaması baúlatıldı÷ında, ilgili klasörlerde FeX
modüllerini (DLL) arar ve bu modüllerin tüm fonksiyonları ile
ba÷lantı kurar. Daha sonra tokalaúma iúlemini baúlatmak amacıyla
bu modüllerin Fex_Bind fonksiyonlarını ça÷ırır. ølgili FexParam
yapıları modüller tarafından doldurulur ve böylece DbsEditor
öznitelik çıkarımı için gerekli olan tüm bilgiye sahip olur.
91
ii.
DbsEditor kullanıcı arayüzü kullanıcının çıkarılacak olan
öznitelik parametrelerini girmesini sa÷lar ve bu bilgiler kullanıcı
tarafından girildikten sonra, FeX modülü bu bilgiler ile
ilklendirmek amacıyla Fex_Init fonksiyonu ça÷rılır.
iii.
Veritabanındaki tüm resimler için, DbsEditor, FrameParam
yapısı ile birlikte Fex_Extract fonksiyonunu ça÷ırır ve bu
fonksiyon her resim için öznitelik vektörü ile vektör boyutunu
geri döndürür.
iv.
ølgili parametreler ile tüm öznitelikler çıkartıldıktan sonra, Fex
modülünü sıfırlamak için FexParam yapısı ile Fex_Exit
fonksiyonu ça÷rılır.
v.
E÷er uygulama sonlandırılmadan önce, yeni öznitelik vektörleri
çıkartılmak istenirse, (ii) ve (iv) arasındaki adımlar tekrar edilir.
vi.
DbsEditor uygulaması sonlandırıldı÷ında, Fex_Exit fonksiyonu
ça÷rılarak FexParam yapısı içerisindeki elemanlarının bellekte
iúgal etti÷i yerler geri kazanılır.
Aúa÷ıdaki adımlar, MBrowser uygulaması tarafından, herhangi bir ortam
elemanından öznitelik çıkartarak sorgu yapmak amacıyla gerçekleútirilir:
i.
MBrowser uygulaması baúlatıldı÷ında, ilgili klasörlerde FeX
modüllerini (DLL) arar ve bu modüllerin tüm fonksiyonları ile
ba÷lantı kurar. Daha sonra tokalaúma iúlemini baúlatmak amacıyla
bunların Fex_Bind fonksiyonlarını ça÷ırır. ølgili FexPram yapıları
modüller tarafında doldurulur ve böylece MBrowser öznitelik
çıkarımı için gerekli olan tüm bilgiye sahip olur.
ii.
Kullanıcı bir resim için sorgu yapmak istedi÷inde, MBrowser
ilgili parametreler ile Fex_Init fonksiyonunu ça÷ırarak FeX
modülünü ilklendirir.
92
iii.
Sorgusu yapılacak olan resim için, MBrowser FrameParam
yapısı ile birlikte Fex_Extract fonksiyonunu ça÷ırır ve bu
fonksiyon o resim için öznitelik vektörü ile vektör boyutunu geri
döndürür.
iv.
ølgili parametreler ile tüm öznitelikler çıkartıldıktan sonra, Fex
modülünü sıfırlamak için FexParam yapısı ile Fex_Exit
fonksiyonu ça÷rılır.
v.
Fex_GetDistance fonksiyonu kullanılarak, veritabanındaki tüm
elemanlar için, ilgili öznitelik vektörleri uygun veritabanı
öznitelik dosyalarından okunur ve bu vektörler ile sorgusu
yapılmakta olan resimden çıkartılmıú olan öznitelik vektörü
arasındaki benzerlik hesapları yapılır. Bu uzaklıklar sıralanır ve
bu sıraya göre sorgu sonuçları gösterilir.
vi.
Yeni bir resim sorgusu için, uygulama sonlandırılmamıú ise, (ii)
den (v) ‘e kadar olan adımlar tekrarlanır.
Resim öznitelik dosya formatı
Her resim öznitelik dosyası, veritabanındaki tüm resimler için
oluúturulur ve veritabanı dosyası ile aynı klasörde saklanır. Bir öznitelik
dosyası tüm alt-öznitelik parametrelerini ve bunlar içerisindeki ikili
veriyi saklar. Tablo 1’de örnek bir HSV resim öznitelik dosyasının içeri÷i
gösterilmektedir.
93
Ek 1 Tablo 1.Örnek resim öznitelik dosyası formatı
v 1.8
Öznitelik dosyası versiyonu
HSV 495 2 3
<öznit. FOURCC> <Resim sayısı> <altözn. sayısı.> <param. sayısı>\n
<özn_param1> <fp2> ... <fpN> <özn.
vek. boyutu>\n
16.000000
8.000000
8.000000 1024
aaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbb
ccccccccccccccccccccccc
1.000000
8.000000
32.000000 256
aaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbb
cccccccccccccccccccccccc
økili veri
økili veri
økili veri
økili veri
økili veri
økili veri
økili veri, veritabanındaki resimlerin öznitelik vektörlerini sıralı
bir biçimde içermektedir. Her ikili veri, 6 byte baúlık ve onu takip eden
öznitelik vektörünü içerir.
94
Ek 2 Türkçe - øngilizce Terimler Sözlü÷ü
aykırı eleman denetimi
Baúlıca Bileúenler Çözümlemesi
boyutluluk sorunu
bölme
Bütünsel-tabanlı
çarpıklık
çekirdek
dalgacık
Do÷rusal Ayrıútırma Çözümlemesi
EB-Çekirdek
genelleútirilmiú özde÷er problemi
Hiyerarúik Hücresel A÷aç
Hücre
hücre bölünmesi
hücre çekirde÷i
hücre yo÷unlu÷u
iúlem-sonrası kontrolü
karma
Metriksel Eriúim Yöntemleri
Minimum Örten A÷aç
resim uzayı
olgunluk seviyesi
Otomatik Yüz Tanıma
öklid uzaklı÷ı
ölçek
öncelikli hücre arama
Örnek ile Sorgu
özde÷er
Özelli÷e Dayalı
özvektör
öznitelik
özyüz
seviye
: outliers check
: Principal Component Analysis
: curse of dimensionality
: bin
: Holistic-based
: skewness
: kernel
: wavelet
: Linear Discriminant Analysis
: MS-Nucleus
: Generalized Eigenvalue Problem
: Hierarchical Cellular Tree
: cell
: cell mitosis
: cell nucleus
: cell compactness
: post-processing
: hybrid
: Metric Access Methods
: Minimum Spanning Tree
: image space
: maturity level
: Automatic Face Recognition
: Euclidean Distance
: scale
: Pre-emptive Cell Search
: Query by Example
: eigenvalue
: Feature-based
: eigenvector
: feature
: eigenface
: level
95
sınıf-içi yayılım matrisi
sınıflar-arası yayılım matrisi
uygunluk denetimi
Uzaysal Eriúim Yöntemleri
yo÷unluk eúi÷i
yo÷unluk trend çarpanı
yön
yüz uzayı
: Within Class Csatter Matrix
: Between Class Scatter Matrix
: Fitness check
: Spatial Access Methods
: compactness threashold
: compactness trend factor
: orientatiton
: face space
96
ÖZGEÇMøù
Sinem ASLAN
adres: Mansuro÷lu mahallesi 273/8 sokak Gayret Apt. No:3 D:10
Bornova/ øZMøR
tel: (0232) 3487605
e-mail: [email protected]
Kiúisel Bilgiler
E÷itim
Milliyeti
: T.C.
Do÷um Yeri / Tarihi
: Ankara / 04.05.1980
2001 -
Ege Üniversitesi
Uluslararası Bilgisayar Enstitüsü (UBE)
Bilgi Teknolojileri Ana Bilim Dalı
1995 - 1999
Ankara Üniversitesi
Mühendislik Fakültesi
Elektronik Mühendisli÷i Bölümü
øú Deneyimi
07 - 08 2000
SIEMENS A.ù.
Enformasyon ve Komünikasyon
Departmanı
Stajyer
08 - 09 2001
Türk Telekomünikasyon A.ù.
TURPAK, TTNET, AYCELL
Departmanları
Stajyer
2004 -
Ege Üniversitesi
Uluslararası Bilgisayar Enstitüsü (UBE)
Araútırma Görevlisi

Benzer belgeler