SIFT - Scale Invariant Feature Transform

Kategori: Computer Vision , 18 Şubat 2020 , JanFranco


Feature extraction için kullanışlı algoritmalardan bahsedeceğim serinin ilk yazısını yazıyorum. İnceleyeceğimiz algoritma Scale Invariant Feature Transform yani SIFT algoritması. 2004 yılında David Lowe tarafından bulunmuştur. Algoritma lisanslıdır, patentlidir. OpenCV ile kullanacağız, göreceğiz fakat projelerimizde vs. kullanmak için para ödemeliyiz :).

Feature extraction'daki en büyük problemler rotation (döndürülme), scaling (ölçek), illimunation (aydınlanma) olarak söylenebilir. Daha önce Harris Corner Detection algoritmasını anlatmıştım. O algoritma rotation invariant yani döndürülmeden bağımsızdır. Bu ne demek? Bir satranç tahtasını belli bir açıyla döndürsek bile Harris Corner Detection algoritması köşeleri yine bulabilir. Fakat ya resmi büyütürsek? O zaman da köşeleri tespit edebilir miyiz? Hayır. Bir köşeye uzaktan baktığımızda iki kenarın birbirine dik bir şekild girdiğini görebiliriz fakat o köşeye zoom yaptıkça, o köşenin bir kenar gibi olduğunu görebiliriz:

sift

Yukarıdaki resimde anlattığım şeyi direk olarak görebilirsiniz. SIFT algoritması bu problemleri ortadan kaldırabilir. Algoritmanın adımlarını görelim:

1- Scale-space Extrama Detection
2- Keypoint Localization
3- Orientation Assignment
4- Keypoint Descriptor

OpenCV dökümanlarında veya farklı tutoriallarda 5. adım olarak Keypoint Matching'i de görebiliriz ancak bu adımın algoritmayla bir alakası yoktur. Adım adım inceleyelim:

1- Scale-space Extrama Detection

Daha önce Image Pyramid tekniğini görmüştük. Bu teknik ile ilgili resmi küçülterek birkaç resim üretiyoruz. Bu ürettiğimiz resimleri de Gaussian Blurring ile blurluyoruz. Her bir blurring işleminde sigma değerinin katsayısını artırıyoruz. Aşağıda bu işlemin yapılmış halinin resmini görebilirsiniz:

sift

Bunu niye yapıyoruz? Resmin farklı ölçeklerini alarak, scaling problemini ortadan kaldırmayı hedefliyoruz. Ayrıca bir sonraki adımda Laplace'larını alacağımız resimleri blurlamak mantıklıdır. Gürültüleri temizlemeliyiz. Aynı zamanda gereksiz detayları da bu şekilde yok edebiliriz. Feature extraction için ilgili resimlerin Laplace'larını yani ikinci dereceden türevlerini alacağız. Bunu Gradient başlıklı yazımda anlatmıştım. Fakat bir resimden bir çok resim ürettik ve hepsine ayrı ayrı bu işlemi uygulamak maliyetlidir. Bunun için şöyle bir yol önerilmiş, üretilen resimleri sırasıyla birbirinden çıkart:

sift

Scale-space'teki resimleri birbirinden çıkardığımızda Laplace'ını almış gibi, o işleme yakın bir sonuç üretmiş oluruz. Bir örnek daha görelim:

sift

Bir sonraki yapılan iş ise, scale-space'ten sırasıyla üç resim alıp, piksel piksel tarayarak local maximum ve minimumları bulmak. 3 resmin ortasındaki resmi alıyoruz. 3x3'lük bir pencere düşünelim. Bu pencere piksel piksel kayacak. Merkezdeki piksel ile etrafındaki 8 piksel + üst ve alt resimlerde aynı bölgede bulunan pikseller (tolam 26 piksel) karşılaştırılacak. Bunu şu resimden daha iyi görebiliriz:

sift

Yapılmış bir örnek de görelim:

sift

2- Keypoint Localization

Algoritmanın ilk adımında peak değerleri bulmuştuk. Bu adımda ise outlier'ları, düşük ve kötü pointleri, kenarları temizlemeliyiz. Kenarları almak istemiyoruz. Bunu iki adımda yapacağız fakat hızlıca geçeceğim çünkü Harris Corner Detection'da yapılan aynı adımlar. Keypointte iki yönde gradient alıyoruz. Eğer gradientler küçükse bölge flat bir bölgedir. Eğer bir gradient büyükken diğer gradient küçükse, değişim tek taraflıdır. Yani burası bir kenardır. Eğer iki gradient da büyükse burası bir köşedir. Daha detaylı bilgi için Harris Corner Detection yazımı okuyabilirsiniz, detaylıca açıklamıştım. Burada bir threshold değer de veriliyor ve bu değerin altında kalan kısımlar, kenarlar, flat arealar komple eleniyor. Burada yapılan işlemin sonucunu da görelim:

sift

3- Orientation Assignment

Şu ana kadar önemli keypointleri elde ettik. Bu keypointler scale invariant yani ölçekten bağımsız özellik taşıyorlar. Yani resmin büyüklüğünün küçüklüğünün bir önemi yok. Bu adımda da yapacağımız işlemlerle rotation invariant yani döndürmeden bağımsız özellik kazandıracağız. Bunu nasıl yapacağız? Her bir keypoint için, etrafındaki gradyanların yönlerini ve büyüklüğünü toplayacağız. Gradyanların büyüklüğünü ve yönünü aşağıdaki formüllerle bulabiliriz:

sift

Bu kısmı da daha önce açıklamıştım, geçiyorum. Bir örnek resim görelim:

sift

Bu hesaplardan sonra sonuçları 36 parçalık bir histograma atıyoruz. Her bir parça 10 dereceyi kapsıyor. 360 derece / 36 parça = 10 derece. Yani bir gradyanın yönü 5 derece ise ilk parçaya 15 derece ise ikinci parçaya v... Örnek bir histogram görelim:

sift

Yoğunluğu %80 altında kalan parçaları eliyoruz. %80 üzerindeki parçalar ise yeni birer keypoint olarak belirleniyor.

4- Keypoint Descriptor

Şu ana kadar rotation invariant, scale invariant özellikli keypointler elde ettik. Bu adımda her bir key pointi birbirinden ayıracağız, keypointleri birbirinden ayırt edebileceğiz. Bunun için her bir keypoint üzerine, keypoint merkezde olacak şekilde 16x16 piksellik bir pencere oturtuyoruz. Bu pencereyi 4x4 boyutlu 4 pencereye bölüyoruz. Toplamda 16 penceremiz oldu. Her bir pencerede gradyanlar hesaplanıyor (büyüklük ve yön). Hesaplanan gradyanları 8 parçalık bir histogramda saklıyoruz. 360 / 8 parçadan = Her bir parçanın 45 derece olduğunu biliyoruz. Bir önceki adımda da aynı işlemi yapmıştık fakat bu işlemde ekstra olarak gradyanların uzaklığına göre sonuç değişiyor. Daha uzaktaki gradyanlar daha düşük değer sahip oluyor. Uzaklığı da Gauss function ile belirliyoruz (Normal dağılım). Bu anlattığım olayı görseller üzerinden görelim. Keypoint üstüne 16x16 boyutlu pencere oturtulması, pencerenin 16 parçaya ayrılması ve her pencerede gradyanların hesaplanması:

sift

Her bir küçük penceredeki gradyanlar 8 parçalık histograma atılıyor:

sift

Gauss fonksiyonu ile sonuçlar değişiyor:

sift

Son adımın son kısmında da bu 128 değeri normalize ediyoruz ve her biri birbirinden ayırt edilebilir, güçlü, featureları elde etmiş oluyoruz. Bir sonraki yazımda OpenCV ile uygulamasını göreceğiz.


Sonraki Yazı: SIFT Application in OpenCV
Yorumlar

Henüz bir yorum bulunmuyor.
Yorum bırakın