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

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.

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, AA^T 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, EDE^T 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 AA^T=F ifadelerini yerlerine yazalım:

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

Dönüşümden sonraki kovaryans matrisimiz C'=PFP^T/(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 EDE^T olan F, aynı zamanda P^TDP 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 AxA^T ve A^TxA 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...

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

• Face Recognition Using Eigen face Coefficients and Principal Component Analysis
• A Tutorial On Principal Component Analysis
• Eigenvalues and Eigenvectors
• Non-Square Matrices
• Principal Component Analysis I
• Principal Component Analysis II
• Principal Component Analysis III

Leave Comment

Comments (7)