Bir bilgisayar mühendisi için programlama dili, öğrendiklerini sınadığı, deneyler yaptığı bir laboratuardır ve mühendisler deneylerini, kestiremedikleri sonuçları gözlemlemek için değil, öngördükleri sonuçları doğrulamak için yapar...

Temel Bileşen Analizi İle Yüz Tanıma

Pek çok alanda başarılı uygulamaları bulunan temel bileşen analizi yöntemi ve yöntemin yüz tanıma probleminin çözümünde uygulanışı.

Daha önce, duyguları yüz görüntüsünden tanıyabilen bir program yazmıştım. Programı yazarken, aslında görüntülerin gerçek zamanlı olarak işlenebilmesini sağlayacak bir çekirdek hazırlamış oldum. Bugünlerde amacım bu çekirdek üzerine bir yüz tanıma sistemi inşa etmek. İşin teorisini anlamam bu sefer biraz zaman aldığı için kodlamaya geç başladım. [ Programın tamamlanmış hali: Gerçek Zamanlı Yüz Tanıma Sistemi ]

Yüz tanıma sistemlerinde değişik yöntemler kullanılabiliyor. Bunlar arasında en çok temel bileşen analizi ilgimi çekti. Temel bileşen analizinin kullanıldığı bir sürü alan var ve bu yöntem yüz tanıma problemine de oldukça hızlı bir çözüm sunuyor.

Temel Bileşen Analizinin (PCA, Principal Component Analysis) Amacı

Yüz tanıma problemi gibi kısa sürede çok fazla veri ile baş etmek zorunda olduğumuz problemlerde verinin boyutunu, niteleyiciliğini koruyarak azaltabilir miyiz? İşlemek zorunda olduğumuz veri yığınlarındaki her veri, nitelemekle yükümlü olduğu nesne/olay için gerçekten "olmazsa olmaz" mı? Bir veri yığınındaki gereksiz verileri süzmek mümkün mü?...

Temel bileşen analizinin amacı doğrusal ilişkiler içeren çok sayıda veriden, birbirinden bağımsız az sayıda veri elde etmek. (Eğer veriler doğrusal ilişkiler içermiyorsa temel bileşen analizi pek işe yaramaz. Analizin doğrusal olmayan versiyonu için NLPCA kullanılabilir.) Burada kilit nokta, veri boyutunun düşürülebilmesi için doğrusal olarak ilişkili verilerin ayıklanmaya çalışılması. Bu sayede boyut düşürülürken, verilerin tanımlayıcı olma niteliği de korunuyor. Yöntem, bu yönüyle bir veri sıkıştırma yöntemi olarak da kullanılabiliyor.

Temel bileşen analizinde aslında bir doğrusal dönüşümün izini sürüyoruz. Analizin sonunda öyle bir dönüşüm buluyoruz ki, veri kümemizi dönüşümün götürdüğü yeni uzaya düşürdüğümüzde, ilk eksene düşen verilerin varyansı olası en büyük değerinde olurken, diğer eksenlere düşen verilerin varyansı ise sıralı olarak azalıyor. İlk sıralardaki eksenlere düşen verilerin varyansları büyük olduğu için bu veriler birbirlerinden daha bağımsız ve bu nedenle veri kümesinin temsilindeki rolleri diğerlerinden daha önemli. Son sıralardaki eksenler ise, üzerilerine düşürülen veriler birbiriyle fazlaca ilişkili olduğundan, "vazgeçilmez" olmaktan çıkıyor. Bunların bir kısmını atıp boyutu daha da düşürebiliyoruz. (Hiçbirini atmasak bile, dönüşümün sonunda verileri, her bir veri kümesinin veri sayısı kadar boyutu olan bir uzaydan, veri kümesi sayısı kadar boyutu olan bir uzaya taşıdığımız için boyutu zaten büyük ölçüde azaltmış oluyoruz.)

Doğrusal olarak ilişkili verilerin neden gereksiz olduğunu şöyle bir örnek ile anlamaya çalışalım:

1. 6,  15, 9,  12
2. 14, 35, 21, 28
3. 8,  20, 12, 16

Yukarıdaki 3 vektör bir nesneyi temsil ediyor olsun. Dikkatlice bakarsak, bu vektörlerin doğrusal olarak ilişkili olduğunu görebiliriz. Hepsi de [2, 5, 3, 4] vektörünün belli birer katı. Bu vektörlerin temsil ettiği şey her ne ise, onu bu 12 sayı ile ifade etmek yerine, her bir satırın [2, 5, 3, 4] vektörünün kaç katı olduğunu bulup, o çarpanlarla temsil etmek mümkün. Bu durumda örnekte 12 sayı ile temsil ettiğimiz şeyi sadece 3 sayı ile temsil edebiliriz; [3, 7, 4].

Temel bileşen analizinin sonunda verileri, bu örnekteki mantığa benzer bir şekilde, öz nesne olarak anılan ve doğrusal olarak birbirinden bağımsız olan vektörlerin belli katlarının toplamları olarak (bu vektörlerin doğrusal kombinasyonları olarak) ifade etmiş olacağız...

Kullanılan Temel İstatistiksel Kavramlar

İşimize yarayacak iki basit kavramla başlayalım:

Varyans, belli sayıda değerin ortalama etrafındaki dağılımını gösterir. Varyans küçükse, veriler biribiri ile ilişkili, düzgün dağılmış demektir. Varyans büyükse veriler dağınık, ve verilerin biribirleri ile ilişkileri zayıf demektir.

Kovaryans, iki değişkenin birlikte nasıl değiştiklerini gösterir. İki değişken birlikte artıyor veya birlikte azalıyorsa kovaryans sıfırdan büyük çıkar. Değişkenlerden biri artarken diğeri azalıyorsa veya biri azalırken diğeri artıyorsa kovaryans sıfırdan küçük çıkar. Değişkenler arasındaki ilişki ne kadar zayıfsa kovaryans sıfıra o kadar yakın olur.

Varyans ve kovaryans

Burada varyansın, aslında kovaryansın bir özel hali olduğunu görebilirsiniz. Kovaryansını hesapladığımız iki değişkenden biri kendisi iken, bir diğeri de kendisi ise, varyansı hesaplamış oluruz. Varyans tek boyutta, kovaryans iki boyutta hesaplanıyor.

Temel Bileşen Analizi

Temel bileşen analizini, yüz tanıma problemini ele alarak anlamaya çalışalım:

1) Elimizde eğitim için kullanacağımız KxL boyutlarında M tane yüz görüntüsü bulunuyor olsun. Her bir görüntüdeki toplam piksel sayısı KxL=N olsun.

2) Bu görüntülerin sütunlarını alt alta yerleştirerek M tane sütun vektörü elde ediyoruz. Yani aslında iki boyutlu uzayda N tane nokta ile ifade ettiğimiz her bir yüzü, N boyutlu uzayda bir tek nokta (her noktanın/yüzün N tane koordinatı var) ile ifade etmiş oluyoruz.

3) Şimdi merkezimizi, yani (0,0,...,0) noktamızı bu vektörlerin tam ortalamalarının üzerine kaydırmak için vektörlerin ortalamasını alıp her bir vektörden bu ortalamayı çıkarıyoruz. (Görüntülerde öteleme işlemini hatırlayın. Aynı mantık.) Artık vektörlerimizin başlangıç noktası, eski ortalamaları oldu. Vektörlerimizin yeni ortalamalası ise 0.

4) Bu M adet sıfır ortalamalı sütun vektörünü yan yana dizerek NxM boyutlarında bir matris elde ediyoruz. Bu matrise A diyelim.

5) A matrisini, kendisinin transpozu ile ve sonra da 1/(N-1) ile çarpıyoruz. Elde ettiğimiz matris, koordinatların tüm ikili kombinasyonlarının kovaryanslarını içeriyor. Matrisin köşegenleri, her bir koordinatın kendi ile arasındaki kovaryansı, yani aslında koordinatların varyanslarını ve diğer elemanlar da her bir koordinatın, diğer her bir koordinatla arasındaki kovaryansları taşır. Bu nedenle bu matrise kovaryans matrisi deniyor. (Matrise C(ovariance) diyelim.)

6) Amacımız koordinatlar arasında doğrusal ilişki bulunmamasını sağlamaktı. Bu yüzden bizi yeni uzayımıza götürecek dönüşümün ardından, koordinatlar arasındaki ilişkiyi gösteren kovaryansların sıfır olması gerekiyor. Başka bir değişle, AAT matrisi (buna F diyelim) yeni uzaya taşındığında (yeni uzaydaki F matrisine de F' diyelim) F' matrisinin köşegenleri dışındaki elemanlar 0 olmalı. (Dönüşümden sonraki A matrisine A', kovaryans matrisine C' diyelim) Demek ki, dönüşümden sonraki C'=A'A'T/(N-1) ifadesinde A'A'T=F' matrisi köşegen olmalı. (Dönüşümü sağlayacak matris P olsun: C'=PC ve A'=PA)

7) Köşegen bir F' bulunurken öz değer ayrışımı kullanılıyor. F matrisinin öz vektörlerini sütunlar halinde yan yana dizip bir matris oluşturalım ve buna E(igen) diyelim. Sonra öz değerlerin köşegen olacağı bir matris oluşturup buna da D(iagonal) diyelim. Bu durumda F, EDET ifadesine eşittir.

8) Dönüşümden sonra, köşegen olan F'=A'A'T matrisine ihtiyacımız vardı. Dönüşümü yapalım; A'=PA ve AAT=F ifadelerini yerlerine yazalım:

F' = A'A'T = (PA)(PA)T = PAATPT = P(AAT)PT = PFPT

Dönüşümden sonraki kovaryans matrisimiz C'=PFPT/(N-1) halini aldı. Dönüşümü sağlayan P matrisini, F matrisinin öz vektörlerini satırlar halinde alt alta yazarak elde etmiş olalım. Bu durumda P, E matrsinin transpozudur. O halde EDET olan F, aynı zamanda PTDP ifadesine de eşittir. Ayrıca P ortogonal olduğu için (satırlarında yer alan vektörler birbirlerine dik) P matrisinin transpozu tersine eşittir. Bu bilgiler ışığında F matrisini yerine yazalım:

C' = PFPT/(N-1) = P(PTDP)PT/(N-1) = PP-1DPP-1/(N-1) = D/(N-1)

Görüldüğü gibi, F matrisinin öz değerlerini satırlarında barındıran P, kovaryans matrisini köşegen olacağı yeni bir uzaya taşımış oldu. Yani dönüşümü sağlayacak uygun P matrisinin nasıl oluşturulacağını bulduk. (F matrisinin öz vektörleri ile)

9) Demek ki önce F matrisinin öz vektörlerini bulmamız gerekiyor. Bir matris ile bu matrisin öz değer ve öz vektörleri arasındaki ilişki Fv=λv şeklinde gösterilir. Burada v, F matrisinin öz vektörlerini, λ ise öz değerlerini temsil etmekte. Tüm değerleri bir tarafa attıktan sonra ifade (F-λI)v=0 halini alır (I birim matris). Sistemin v=0 için bir çözümü olduğu açık. v sıfırdan farklı iken çözüm için bu sefer F-λI matrisinin determinantının 0 olması gerekiyor. det(F-λI) bize N. dereceden (F matrisimiz NxN'lik idi) bir polinom döndürür. Bu polinoma F matrisinin karakteristik polinomu deniyor. Polinomun kökleri, aradığımız λ öz değerlerinin ta kendileri. Öz değerleri bulduktan sonra, her bir öz değeri (F-λI)v=0 ifadesinde ayrı ayrı yerine yazıp, öz vektörlere ulaşıyoruz.

10) Burada biraz duralım. Çünkü bu hesaplamayı yapacak bilgisayarın ciddi bir problemi var. Elimizde 100x100'lük, 100 tane yüz görüntüsü bulunuyor olsun. Bilgisayar bunları 100 tane 10000x1 sütunlar haline getirip yan yana dizdi. Sonra 10000x100'lük bu matrisi kendi transpozu ile çarptı ve 10000x10000'lik bir kovaryans matrisi elde etti. Şimdi bu matrisin öz değerlerini ve öz vektörlerini bulması gerekiyor. Her bir elemanı dörder baytlık kayan noktalı sayılar ile temsil ettiğimizi düşünün. 100 milyon tane elemanımız var. Bu da yaklaşık 400 milyon bayta, yani yaklaşık 0.37 GB belleğe gereksinim duyduğumuzu gösteriyor. Ayrıca bu matristen 10000 tane öz değer ve öz vektör çıkarmamıza gerek yok. Amacımız boyut indirgemek değil miydi?

Şu önemli bilgiler bilgisayarı bu dertten kurtarıyor:
N>M iken kare olmayan NxM'lik bir A matrisi ile oluşturulan AxAT ve ATxA matrislerinin öz değerleri ve öz vektörleri aynıdır. Farkeden tek şey şu; ilk çarpımdan hesaplanacak N tane öz vektörün en az (N-1)-M tanesi sıfır çıkar. İkinci çarpımdan hesaplanacak öz vektörlerinse (M tane) en az 1'i sıfırdır. Yani özetle öz değerleri ve öz vektörleri hangi çarpımdan hesaplarsak hesaplayalım, elde edeceğimiz sıfırdan farklı öz değer ve öz vektör sayısı en çok küçük boyutun 1 eksiği kadar olacak.

Bu sayede A matrisini kendi transpozu ile çarpmak yerine, A matrisinin transpozunu A ile çarpıp, çok daha küçük bir matristen, F matrisinin öz değer ve öz vektörlerini bulabiliyoruz. Tabi bu değerleri bulduktan sonra vektörleri NxNlik uzaya geri göndermeyi ve sonrasında normalize etmeyi unutmuyoruz. İşlem için gerekli bellek miktarını ve işlem süresini yeniden değerlendirecek olursak; yeni kovaryans matrisimiz artık 10000x10000'lik değil 100x100'lük. 10000 eleman nerede, 100 milyon eleman nerede. Tek kazancımız bu değil. Büyük matris üzerinden hesaplama yaparsak elde edeceğimiz 10000 öz vektörün (10000-1)-100=9899 tanesi 0 olacaktı. Bunları boşuna hesaplamış olacak ve direkt eleyecektik...

11) NxN'lik matris yerine MxM'lik matrisi ele alarak hesapladığımız her biri Mx1 boyutlarında olan M-1 tane sıfırdan farklı öz vektörü, Nx1 boyutlarındaki uzaya geri taşımak için bu vektörleri NxM boyutlarında olan A matrisi ile (A solda olacak şekilde) çarparız ve Nx1'lik M-1 tane yeni vektör elde ederiz. (Sıfır olan öz vektörü de dahil ediyoruz; toplam M tane öz vektör) Bu öz vektörler bizim öz görüntülerimiz. Bu arada F matrisimiz simetrik olduğu için, bulduğumuz tüm öz vektörler birbirlerine dik. (Öyle olmasaydı öz vektörlerin yeni uzayda birer eksen olmaları mümkün olmazdı.)

12) Öz değerleri ve öz vektörleri de hesapladık. 8. adımın sonunda dönüşümü sağlayacak P matrisinin, öz vektörlerin satırlar halinde dizilmesi ile elde edilebileceğini bulmuştuk. Yani P hazır. Şimdi P matrisindeki satırların sıralamasını değiştireceğiz.

Hesapladığımız öz değerler yeni uzayımızda her bir eksenin varyansını temsil etmekte. (Köşegenlere düşen elemanların varyanslar olduğu söylemiştik.) Öz vektörler de yeni uzayımızın eksenleri ve tabi ki hepsi birbirine dik. Artık bizim için önemli olan, varyansların yüksek olması, yani yeni uzayda her bir eksene düşecek değerlerin birbiri ile mümkün olduğu kadar ilişkisiz olması. (Amacımız değişmedi, sadece kovaryansı değil, artık varyansı kullanıyoruz). Bu nedenle öz değerleri, karşılık gelen öz vektörlerle birlikte büyükten küçüğe doğru sıralamamız gerekiyor. Böylece, yeni uzayımızda en yüksek varyansa sahip olunmasını sağlayacak ekseni başa almış oluyoruz. En baştaki eksenimiz bizim 1. temel bileşenimiz ve diğerleri önem sırası azalarak bizim diğer temel bileşenlerimiz oluyor.

13) P matrisinde son satırlardaki öz vektörlerin bir kısmını atarak uzayımızın boyutunu düşürmemiz mümkün. Çünkü artık sonlarda kalan öz vektörlerin ifade ettiği eksenler veri kümesinin temsili için "olmazsa olmaz" değil.

14) Orjinal görüntülerimizi yeni uzayımıza taşımanın zamanı geldi. 2. adımda elde ettiğimiz M tane sütun vektörünün her birinden ortalama vektörünü çıkarıp (böylece bu vektörlerin başlangıç noktasını, veritabanımızdaki görüntülerin ortalamasına çekmiş oluyoruz) P ile (P solda olacak şekilde) çarpıyoruz. Görüntü sütununa G, görüntünün yeni uzaydaki koordinatlarına G' ve veritabanındaki görüntülerin ortalamasını alarak oluşturduğumuz ortalama vektörüne O dersek, Gyi yeni uzaya taşıyacak ifade şu:

G' = P(G-O)

15) Eğer eski uzaya geri dönmek istersek, yeni koordinatları P matrisinin tersi veya transpozu ile (hatırlayalım; P matrisi ortogonaldi, dolayısıyla bu matrisin tersi transpozuna eşit) çarpıp sonuca ortalamayı eklememiz yeterli. (dönüşümün tam tersi):

G = P-1G' + O = PTG' + O

Görüntüleri yeni uzaya taşıdıktan sonra elde ettiğimiz koordinatlar (G'), aslında görüntülerin orjinallerini elde edebilmek için her bir öz görüntüyü hangi oranda toplama katacağımızı gösterir. Bu yüzden bunlara ağırlık veya katsayı da deniyor. Zaten ters dönüşümde, yeni uzaydaki koordinatlarımızın her bir öz görüntü ile tek tek çarpılmasını sağlamış oluyoruz. Başka bir değişle, her bir görüntüyü, öz görüntülerin doğrusal kombinasyonu şeklinde ifade etmiş oluyoruz:

OrjinalYuzGoruntusu = Agirlik1 * Ozyuz1 + Agirlik2 * Ozyuz2 +...+ AgirlikK * OzyuzK + OrtalamaYuz

(Şimdi olayı başta verdiğimiz basit örnek ile ilişkilendirebildik mi?)

16) Öz yüzlerimizi belirledik ve bunları yeni uzayımıza aktardık. Peki öz yüzleri elde ederken kullandığımız yüzler arasında yer almayan bir yüz görüntüsünü nasıl tanıyacağız? Tanıma işlemi göreceli olarak çok daha basit; yeni görüntüyü 14. adımda yaptığımız gibi yeni uzaya taşıyacağız. Bunun için yüz görüntüsünü sütun vektörü haline getiriyoruz ve veritabanımızdaki ortalama yüz görüntüsünü yeni yüz görüntüsünden çıkarıyoruz. Böylece bu yüz vektörünün de başlangıç noktasını, veritabanındaki yüzlerin ortalamasına kaydırmış oluyoruz. Ardından vektörü P ile çarpıp (P solda olacak şekilde) onu yeni uzayımıza taşımış oluyoruz. Elde edeceğimiz yeni koordinatları, veritabanındaki yüz görüntülerinin koordinatları ile karşılaştırıyoruz. Karşılaştırma için öklit uzaklığı kullanılıyor. (Her ikilinin farkının karesi alınıp sonuçlar toplanır ve toplamın karekökü alınır.) Tüm öklit uzaklıkları hesaplandıktan sonra, yeni görüntüye en yakın çıkan görüntünün uzaklığını bir eşik değer ile karşılaştırıyoruz. Yeni yüz ile arasında en az uzaklık bulunan yüzün uzaklığı belirlediğimiz eşik değerin altında ise, bu yüz yeni yüzle eşleşmiş olur. (Genelde 5000 civarında bir eşik seçiliyor.)...

Dikkat ettiyseniz karşılaştırma işlemini çok daha az boyutlu yeni uzayımızda yaptık. Yüz görüntüleri yeni uzayımızda artık sadece birer nokta. Yeni bir yüz görüntüsünü veritabanımızdakilerlerden biri ile eşleştirmek için yüzü yeni uzayda temsil eden noktaya en yakın noktayı tespit etmemiz yeterli oluyor...

Harici Bağlantılar

Sayfayı
Yayın tarihi: 13 Temmuz 2012 Cuma, 18:43
Anahtar kelimeler: temel bileşen analizi, yüz tanıma, pca, principal component analysis

Yorum Gönder

 
Yorumunuzu -1. yoruma yanıt olarak gönderiyorsunuz. Yanıtlamayı iptal etmek için buraya tıklayabilirsiniz.

 

Yorumlar (7)

fatih
Yanıtla
11 Aralık 2012 Salı, 22:38
#1

mrb hüseyin bey öncelikle çok yararlı bir makale olmuş teşekkür ederim. ancak bir noktada takıldım aydınlatırsanız sevinirim. amacımız A' = PA dönüşümü yapmak. ve biz kovaryans matrisinin öz vektörlerinin transpozu ile Pyi buluyoruz. 11. madde de P ile A'yı neden A solda olacak şekilde çarpıyoruz A sağda olacak şekilde çarpmamız gerekmiyor mu??

Hüseyin Atasoy
Yanıtla
01 Şubat 2013 Cuma, 13:22
#2

Formüllerdeki harflere takılmayın; dönüşüm için atıyorum G' = FG de diyebiliriz değil mi? Bu durumda F P oluyor. A matrisi, bulduğumuz özvektörleri Nx1 boyutlarındaki uzaya döndürecek matrisin kendisi. Yani yazdığınız eşitlikteki P matrisi bizim A matrisimiz. Bizi aradığımız uzaya götürecek olan matrise P demiştik ya, o yüzden A'ya da tekrar P demedim.
Harflere ya da simgelere çok takılmayın. Matris sayısı çok olduğu için hepsine alışık olduğumuz harfleri veremedim...

Oğuzhan
Yanıtla
16 Mart 2015 Pazartesi, 21:05
#3

Merhabalar hocam. Ben  G' = P(G-O) işlemini yaptığımda G' değerleri -1 ile 1 arasında arasında değerler mi çıkması gerekiyor. Ben yukarıdaki işlemi yaptığımda G' değerleri baya büyük değerler çıkıyor.(örneğin bir yüz görüntüsü için PC1 = -8102863,2879152037 ; PC2= -634847,33059681254 ; PC3= -385599,75286153762) .Bu değerlerin normalize edilmesi mi gerekiyor hocam ? Bu konuda yardımcı olursanız sevinirim hocam. Hocam bide öz vektörler birim vektörler olduğundan bulduğumuz öz vektörleri normalize etmemiz gerekir mi ?

Hüseyin Atasoy
Yanıtla
29 Mart 2015 Pazar, 11:15
#4

Yazıda geçmiyor sanırım, bahsetmeyi unutmuşumum; eğer özvektörleri kısa yoldan bulursak onları normalize etmeyi ihmal etmememiz gerekiyor.

tamer
Yanıtla
11 Nisan 2016 Pazartesi, 18:11
#5

pca yöntemi ile face recognition bende yaptım. webcam başarısı biraz daha yüksekti ancak fotoğraflardan tanıma işlemi başarısı %40 civarı idi. Emgu cv tabanlı Diğer yöntemlerin başarı oranı dahada düşük. Eğer siz bu başarı oranını kodu geliştirerek yükseltti iseniz extra tebrik etmem için bana mail atınız. Bu konuda konuşabiliriz.

Hüseyin Atasoy
Yanıtla
11 Mayıs 2016 Çarşamba, 08:38
#6

Merhaba,
Sonucu etkileyen çok fazla parametre var. Uygun değerler bulmak gerekiyor.
OpenCV'nin yüz tanıma sınıfını kullanmadım. İşlemleri tek tek yapmak daha doğru. Öyle yaptığınız zaman daha fazla parametreye müdahale şansınız oluyor. Ayrıca son aşamada yüzleri tam olarak nasıl eşleştirdiğiniz de önemli. En yakın komşu yöntemi tek başına çok iyi sonuçlar vermeyebilir.

Mehmet Ayaz
Yanıtla
01 Haziran 2017 Perşembe, 05:33
#7

O kadar güzel ve anlaşılır anlatmışsınız ki helal olsun demekten başka birşey bulamıyorum.
Başarılı çalışmalar dilerim.

 
 
Sayfa 44 sorgu ile 0.032 saniyede oluşturuldu.
Atasoy Blog v4 © 2008-2017 Hüseyin Atasoy