İmgelerdeki Köşe Noktalarının Köşe Özellikleri Kullanarak
Transkript
İmgelerdeki Köşe Noktalarının Köşe Özellikleri Kullanarak
İmgelerdeki Köşe Noktalarının Köşe Özellikleri Kullanarak Seçilmesi Selecting Image Corner Points Using Their Corner Properties Yalın Baştanlar, Yasemin Yardımcı Enformatik Enstitüsü, Orta Doğu Teknik Üniversitesi yalinb@ii.metu.edu.tr, yardimy@ii.metu.edu.tr Özetçe Bu çalışmada, nokta eşleştirmede kullanılan köşe noktalarının daha sağlıklı seçilebilmesi için köşe özelliklerini kullanan bir yöntem geliştirilmiştir. İlk olarak, herhangi bir köşe bulma yöntemi (Harris-Stephens, Tomasi-Kanade v.b.) ve bu yöntemin köşelik ölçüsü kullanılarak geniş bir nokta kümesi elde edilir. Bu noktaların köşe açıları, doğrultuları ve kontrastları (karşıtlıkları) imge türevleri cinsinden kestirilir ve bu değerlere sahip ideal bir köşenin köşelik ölçüsü ile imgeden elde edilen köşelik ölçüsü karşılaştırılır. Eğer bu iki değer birbirine yakın ise noktanın etrafındaki bölge belirtilen köşe özelliklerine (açı, doğrultu, kontrast) sahiptir ve bu özellikler başarılı bir şekilde kestirilmiştir, dolayısıyla nokta seçilir. Bu yöntemle elde edilen köşe noktalarının eşleme için daha uygun oldukları öngörülmüştür. Ayrıca çıkarılmış olan köşe özellikleri eşleme için önbilgi olarak kullanılabilir. Abstract We developed a method to obtain corner points for healthier point matching using corner properties such as corner angle, corner orientation and contrast. A large corner point set, obtained by a common corner detector (Harris, TomasiKanade etc.) is given to our algorithm as input. Then, the corner properties are extracted for this point set in terms of image derivatives. Cornerness measure calculated from the image is compared with the one calculated using an ideal corner with the extracted properties. If they are close enough, which shows that the neighborhood of the point possess corner properties and estimations are successful, the corner is selected. It is presumed that corners selected by this method are more suitable for point matching. Moreover, extracted corner properties can be used as a priori information for matching. 1. Giriş Nokta bulma ve eşleştirme işlemi, bilgisayarla görünün pek çok alanı (nesne takibi, stereo görü, imge çakıştırma, üç boyutlu geriçatım v.b.) için önem taşır ve uzun yıllardır çeşitli köşe bulma yöntemleri geliştirilmiştir. Moravec [1] özilintiye dayalı bir nokta saptama yöntemi geliştirmiştir. Ana fikir, köşe noktası etrafında belirli bir komşuluk için her yöndeki hareketin kayda değer bir ışık yoğunluğu farkı yaratmasıdır. Förstner [2], 1986 yılında, ‘özilinti matrisi’ olarak bilinen, x ve y yönündeki imge türevlerinin çarpımlarından oluşan matrisi köşe bulmak için kullanmıştır. Harris ve Stephens [3], bu matrisin determinantını ve izini kullanarak farklı bir ‘köşelik ölçüsü’ yaratmışlardır. Tomasi ve Kanade [4] otokorelasyon matrisinin özdeğerlerini direkt köşelik ölçüsü olarak almışlardır. Kitchen ve Rosenfeld [5] köşelik ölçüsünü yerel gradyan değeri ve kenar çizgisi boyunca gradyan yönündeki değişim değerinin çarpımı olarak belirlemiştir. Yakın zamanda, imge gradyanı tabanlı köşe bulma yöntemlerinin köşelik ölçülerini [6] ve sonuçlarını [7] karşılaştıran çalışmalar yapılmıştır. Farklı olarak, bölgeyi morfolojik açıdan inceleyerek köşe biçimli şekilleri yakalayan [8-9] veya köşeleri parametrik modellerle ifade eden ve bu parametrelere uygunluğuna göre seçim yapan [10-11] köşe bulma yöntemleri de kullanılmaktadır. Chabat ve diğerleri [12] köşe noktalarını belirli yönlerde isotropik olmayan parlaklık örüntüleri olarak tanımlamışlar ve köşelerin doğrultularını da saptamışlardır. Shen ve Wang [13] tarafından önerilen yöntemde köşe açısı ve doğrultusu hesaplanabilmektedir. Bu yöntemde, nokta etrafında eşmerkezli genişleyen çemberler tanımlanmış ve köşenin içinde/dışında kalan yaylar kestirilmiştir. Rosin’in önceden saptanmış olan köşelerin özelliklerini çıkaran yöntemi [14] parlaklık değerlerinin standart momentine dayanır ve köşe açısı, doğrultusu, kontrastı, köşe noktası yuvarlaklığı ve köşe sınırının eğriliğini kestirmek için kullanılmıştır. Vincent ve Laganiere [15] önplan/arkaplan bölütlemesine dayalı bir yöntem geliştirmişlerdir. Açısı ve doğrultusu değişen bir köşe modeli ile imgeden çıkarılan önplan arasında bir benzeşim ölçüsü kullanılarak köşenin açısı ve doğrultusu kestirilmiştir. Ayrıca aralarında ilgin dönüşüm olduğu farz edilen iki görüntü üzerinde saptanan köşe özelliklerinin nokta eşleştirme amaçlı kullanımı da araştırılmıştır. İmge gradyanı tabanlı köşe bulma teknikleri oldukça popüler olmalarına rağmen köşe açısında, doğrultusunda ve kontrast değerindeki değişimlere karşı yeterince gürbüz değildir. Bu durum 2. Bölüm’de açıklanmıştır. Sunduğumuz yöntem ile bu zayıflıklar giderilmekte, verilen noktaların köşe özellikleri çıkarılmakta ve bu özellikleri doğrulanan köşe noktaları seçilmektedir. Önerdiğimiz algoritmayı Harris-Stephens [3] ve Tomasi-Kanade [4] yöntemleri ile bulunan noktalar üzerinde uyguladık. Ancak köşelik ölçüsü kullanan başka yöntemlerle de uygulanabilir. Bizim yaptığımız gibi imge gradyanı tabanlı bir yöntemle uygulandığı takdirde köşe özelliklerini kestirmek için kullandığımız türevler zaten hesaplanmış olacağından ekstra işlem yükü fazla olmayacaktır. 2. İmge Gradyanı Tabanlı Köşe Seçimi İmge gradyanı tabanlı köşe bulma tekniklerinin çoğu Denklem 1’deki özilinti matrisini kullanırlar. Bu matris, incelenen noktanın etrafında belirli bir komşuluktaki imge gradyanlarının toplanmasından oluşur. Gauss veya benzeri dağılımlı ağırlıklandırma kullanılması yöntemin performansını artırmaktadır. Tomasi-Kanade’nin yönteminde [4], köşeler C matrisinin özdeğerleri (λ1, λ2) kullanılarak seçilir (Denklem 2). Düz bir alanda her iki özdeğer de düşük çıkar. Kenarlarda, özdeğerlerden biri düşük diğeri yüksek çıkar. Köşelerde ise her iki özdeğer de yüksek çıkar. En küçük özdeğer belirli bir eşik değerinin üzerinde ise o nokta köşe kabul edilir. I x2 C= ∑ x , y∈R I x I y λ1,2 = ∑I 2 x IxIy I y2 + ∑ I y2 ± (1) (∑ I − ∑ I ) 2 2 y 2 x + 4(∑ I x I y ) 2 2 (2) Özilinti matrisini kullanan başka bir yöntem olan HarrisStephens [3]’da ise köşelik ölçüsü şu şekildedir: M(x,y) = Det (C) - k * Trace² (C) (3) α α = 2 ⋅ V 2 ⋅ sin θ − ⋅ ∆ − 2 ⋅ V 1 ⋅ sinθ + ⋅ ∆ 2 2 α (4a) ∑ I x = −4 ⋅ V ⋅ ∆ ⋅ cosθ ⋅ sin 2 ∑I x ∑I y α = −4 ⋅ V ⋅ ∆ ⋅ sin θ ⋅ sin 2 ∑Iy I ∑ x θˆ = tan −1 C aynı matris, k ise Harris-Stephens tarafından 0.04 olarak alınan bir katsayıdır. Deneylerimizde gördük ki varolan yöntemlerle belirli bir eşik değeri ile seçilen köşe, doğrultusu değiştiği zaman elenebilmektedir (Şekil 1). Benzer biçimde aynı doğrultuda ama açısı değişen köşeler (Şekil 2) ve kontrastı değişen köşeler elenmektedir (Şekil 3). Önceki bir çalışmamızda [16], kaçırılan köşe noktalarını köşe açısı ve doğrultusuna göre eşik özdeğeri değiştirme yolu ile saptama üzerinde durulmuştu. Şekil 1: Sentetik bir imgede tespit edilen köşeler. Sağdaki karenin köşeleri farklı doğrultulara sahip olduğundan elendi. Şekil 2: Sentetik bir imgede tespit edilen köşeler. Sağdaki karenin köşeleri farklı açılara sahip olduğundan elendi. Şekil 3: Sentetik bir imgede tespit edilen köşeler. Sağdaki karenin köşeleri düşük kontrasta sahip olduğundan elendi. 3. Önerilen Yöntem 3.1. Köşe Özelliklerinin Kestirimi Bir köşe noktası verildiğinde, köşenin doğrultusunu, açısını ve kontrast değerini imge gradyanlarını kullanarak çıkarabiliriz. Şekil 4’te verilen modelde, köşenin iç ve dış bölgelerinde sabit parlaklık olduğu ve kontrastın ∆ kadar olduğu varsayılmıştır. Köşe açısı ve doğrultusu da sırasıyla α ve θ ile gösterilmektedir. Köşenin iki kenarı V=|V1|=|V2| olacak şekilde V1 and V2 vektörleridir. Koyu bölgeden açık bölgeye geçişin positif bir türev yaratacağını ve bir pikseldeki yatay yöndeki türevin I(x+1,y) – I(x-1,y) olacağını varsayarsak, x yönündeki türevler toplamı Denklem 4a’daki gibidir. Benzer şekilde y yönündeki türevler toplamı Denklem 4b ile bulunur. Türev hesaplanırken, geçilen piksel sayısı esas olduğundan yatay türev için kenarların dikey uzunluğunun, dikey türev için de kenarların yatay uzunluğunun rol oynadığı denklemlerde görülebilir. Köşe doğrultusu (θ) kestirimi ise Denklem 4a ve 4b’yi kullanan Denklem 5 ile hesaplanabilir. (4b) (5) y Dairesel komşuluk penceresi V1 Köşenin iç kısmı α θ V2 x Şekil 4: Köşe modeli Köşe doğrultusu bulunduktan sonra köşenin içindeki ve dışındaki pikselleri kullanarak kontrastı hesaplayabiliriz. Eğer köşenin iç kısmında NI tane dış kısmında NO tane piksel alınırsa ve bu piksellerin parlaklık değerlerini sırasıyla IiI (i=1..NI) ve IiO (i=1..NO) şeklinde gösterirsek kontrast kestirimi aşağıdaki gibidir: 1 ∆ˆ = I N NI ∑ I iI − i =1 1 NO NO ∑I O i (6) i =1 Köşe noktasına yakın olan pikseller kullanılmaz İlk köşe açısı kestirimi <60° ise iç bölgeden alınan pikseller Dış bölgeden alınan pikseller İlk köşe açısı kestirimi >60° ise iç bölgeden alınan pikseller Şekil 5: Kontrast kestirimde kullanılan pikseller Kontrast kestirimi için en basit yol sadece köşe doğrultusu üzerindeki pikselleri kullanmaktır, ancak daha geniş nokta kümeleri kullanılırsa kestirimin gürültüye karşı dayanıklılığı da artacaktır. Biz algoritmamızda Şekil 5’te gösterilen pikselleri kullandık ve aşağıdaki adımları uyguladık: Önce sadece Denklem 5’te bulunan köşe doğrultusundaki pikseller kullanılarak bir kontrast kestirimi yapılır ve buna karşılık gelen köşe açısı hesaplanır (Denklem 7). Kontrast kestirimi için köşenin iç bölgesinden kullanılacak pikseller, eğer bulunan köşe açısı 60°’nin altında ise köşe doğrultusunun etrafındaki 10°’lik dilimdeki, değilse 30°’lik dilimdeki piksellerdir. Dış bölgeden köşe doğrultusunun etrafındaki 120°’lik dilimdeki pikseller kullanılır. Köşe noktasının tam yeri saptanamamış olabileceğinden belirlenen noktaya çok yakın olan pikseller kullanılmaz. Belirtilen pikseller Denklem 6’da kullanılarak yeni kontrast kestirimi yapılır. Kestirilmiş özelliklere sahip ideal bir köşenin en küçük özdeğeri hesaplanır, λˆmin (αˆ ,θˆ, ∆ˆ ) . En küçük özdeğer imgeden direkt olarak hesaplanır, ( λ min ) Aradaki fark istenen yakınlık değerinden az ise ( | λˆmin − λmin | / λ̂min < c ) köşe noktası seçilir. Denklem 4’teki ifadelerden yola çıkıp kontrast kestirimi ( ∆ˆ ) de kullanılarak köşe açısı kestirimine (Denklem 7) ulaşılır. (∑ I x ) 2 + (∑ I y ) 2 = 16 ⋅ V 2 ⋅ ∆2 ⋅ sin 2 (∑ I ) + (∑ I ) 2 αˆ = 2 ⋅ sin −1 x 2 2 y 4 ⋅ V ⋅ ∆ˆ Eğer Harris-Stephens yöntemi tercih edilirse aynı adımlar Denklem 3’teki köşelik ölçüsünün köşe özellikleri cinsinden değeri, Mˆ (αˆ , θˆ, ∆ˆ ) , ve imgeden direkt hesaplanan değer, M, karşılaştırılarak uygulanır. α (7) 4. Sonuçlar 3.2. Köşelerin Seçilmesi 4.1. Sentetik İmgeler Köşe özellikleri (α, θ, ∆) ve köşelik ölçüsü (λmin veya M) arasındaki ilişki imge gradyanları cinsinden ifade edilebilir. Bunun için Denklem 2 ve 3’te kullanılan ΣIx2, ΣIy2 ve ΣIxIy değerleri, Denklem 4’te ΣIx ve ΣIy için yapıldığı gibi, köşe özellikleri cinsinden yazılır. Önerilen yöntemi test etmek için değişik açı, doğrultu ve kontrastlara sahip 132 köşe barındıran bir sentetik imge oluşturuldu. İmgede ayrıca yuvarlak kenarlı objelere de yer verildi. Yöntemimizi bu imgenin değişik tür ve miktarda gürültü eklenmiş halleri ile ve iki ayrı köşe bulma metodu ile beraber kullanarak (Tomasi-Kanade ve Harris-Stephens) denedik, ayrıntılı sonuçlar [17]’de sunulmuştur. Şekil 6a’da kullanılan sentetik imgenin bir bölümü ve Tomasi-Kanade düşük eşik değeri ile bulunan köşeler görülmektedir. Bu köşelerden bizim yöntemimiz sonucu seçilenler Şekil 6b’de verilmektedir. Köşe noktası komşuluğunun yarıçapı 12 piksel, yakınlık değeri, c, ise 0.10 olarak alınmıştır. Görüldüğü üzere önerilen yöntem ideal bir davranış göstererek sadece 132 köşeyi seçmiştir. Eğer Tomasi-Kanade eşik değeri 132 nokta kalacak şekilde yükseltilirse kalan noktalar Şekil 6c’de görülenlerdir. Kontrastı düşük olan köşeler yuvarlak nesnelerin etrafındaki noktalardan önce elenmiştir. Oysa, yuvarlak nesneler ölçek değişikliklerinden çabuk etkilendiklerinden ve parlaklık değişimlerine karşı dayanıklı olmak nokta eşleştirmeyi daha gürbüz yapacağından önerilen yöntemin seçimlerinin daha uygun olduğuna inanıyoruz. Önerdiğimiz köşe seçimi algoritmasına verilen girdi: İmge ve herhangi bir köşe bulma yöntemi ile düşük bir eşik değeri kullanılarak elde edilmiş geniş nokta kümesi, Köşe özellikleri ile kestirilen ve imgeden hesaplanan köşelik değerlerini karşılaştırmada kullanılacak yakınlık değeri (c), Nokta etrafındaki dairesel komşuluk penceresinin çapı (2V). Verilen geniş nokta kümesindeki her bir köşe noktası adayı aşağıdaki adımlar takip edilerek seçilir veya elenir. Belirlenen komşuluk penceresi için imgeden ∑Ix, ∑Iy, ∑IxIy değerleri hesaplanır, Köşe açısı, doğrultusu ve kontrast kestirimleri ( αˆ , θˆ, ∆ˆ ) yapılır. ( α̂ < 30º, α̂ > 150º ve ∆ˆ < 30/255 gri düzeyi durumlarında köşe noktası elenir.) a) b) c) Şekil 6: Sentetik imgenin bir bölümü üzerinde saptanan köşe noktaları a) Tomasi-Kanade düşük eşik değeri ile b) Önerilen yöntemle, 132 nokta c) Tomasi-Kanade eşik değeri yükseltilerek, 132 nokta 6. Teşekkür Bu çalışma bir Avrupa 6. Çerçeve projesi olan ‘3DTV’ tarafından desteklenmiştir. http://www.3dtv-research.net 7. Kaynakça [1] [2] [3] a) [4] [5] [6] [7] b) [8] Şekil 7: Gerçek imge üzerinde test, ilk kümede 113 nokta var. a) Tomasi-Kanade eşik değeri yükseltilerek elde edilen 32 nokta. b) İlk kümeden önerilen yöntem sonucu seçilen 32 nokta (yakınlık=0.15, komşuluk yarıçapı=17 piksel). 4.2. Gerçek İmgeler Önerilen yöntem yine Tomasi-Kanade yöntemi ile kullanarak gerçek bir imge üzerinde test edilmiştir (Şekil 7). Başlangıçta elde bulunan 113 noktadan her iki yöntemle 32 köşe seçilmiştir. Kameramanın bedeni etrafındaki noktaların Tomasi-Kanade ile kaçırıldığı gürülmüştür. Önerilen yöntem aday noktalar arasından etrafındaki bölge belirtilen köşe özelliklerine sahip olanları, diğer bir değişle ‘doğal köşeleri’ seçmektedir. Eğer daha ufak bir komşuluk kullanılırsa, kameranın objektifindeki noktalar gibi köşe özelliklerini daha küçük alanda gösteren köşeler seçilebilir. [9] [10] [11] [12] [13] [14] 5. Değerlendirme Bu çalışmada, köşe noktalarının daha sağlıklı seçilebilmesi için köşe özelliklerini kullanan bir yöntem geliştirilmiştir. Geliştirilen yöntemin sonuçları hem sentetik hem de gerçek imgeler için yaygın kullanılan iki köşe bulma yönteminin (Tomasi-Kanade ve Harris-Stephens) sonuçları ile karşılaştırılmıştır. Önerilen yöntem köşeleri sahip oldukları açı, doğrultu ve kontrasttan bağımsız bir şekilde seçerek sentetik imgelerde ideal davranış göstermiştir. Gerçek imgelerde de etrafındaki bölge belirtilen köşe özelliklerine sahip olan noktaları, diğer bir değişle ‘doğal köşeleri’ seçmektedir. Ayrıca çıkarılmış olan köşe özellikleri eşleme için önbilgi olarak kullanılabilir. [15] [16] [17] H.P. Moravec, “Towards Automatic Visual Obstacle Avoidance (short version)”, Proceedings of the 5th International Joint Conference on Artificial Intelligence, MIT, Cambridge, Ağustos 1977, p. 584. W. Förstner, “A Feature Based Correspondence Algorithm for Image Matching”, International Archives of Photogrammetry and Remote Sensing, vol. 26, 1986, p.150-166. C.G. Harris, M. Stephens, “A Combined Corner and Edge Detector”, Proc. of Fourth Alley Vision Conference, Manchester, 1988, p.182-192. C. Tomasi, T. Kanade, Shape and Motion from Image Streams: a Factorization Method Part 3: Detection and Tracking of Point Features, Carnegie Mellon University Technical Report, CMU-CS-91-132, Nisan 1991. L. Kitchen, A. Rosenfeld, Gray Level Corner Detection, Technical Report of Computer Center 887, University of Maryland, April 1980. C.S. Kenney, M. Zuliani, B.S. Manjunath, “An Axiomatic Approach to Corner Detection”, Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2005. F. Mokhtarian, F. Mohanna, “A Performance Evaluation of Corner Detectors using Consistency and Accuracy Measures”, Computer Vision and Image Understanding, vol. 102, Nisan 2006, p. 81-94. S.M. Smith, M. Brady, “SUSAN - A New Approach to Low Level Image Processing”, Int. Journal of Computer Vision, vol. (1) 23, 1997, p. 45-78. M. Trajkovic, M. Hedley, “Fast Corner Detection”. Image and Vision Computing, vol. 16, 1998, p. 75-87. S. Baker, S.K. Nayar, H. Murase, “Parametric Feature Detection”, Int. Journal of Computer Vision, vol. 27, 1998, p. 27-50. T. Blaszka, R. Deriche, Recovering and Characterizing Image Features Using an Efficient Model Based Approach, Technical Report RR-2422, INRIA, 1994. E. Chabat, G.Z. Yang, D.M. Hansell, “A Corner Orientation Detector”, Image and Vision Computing, vol. (10) 17, 1999, p.761-769. F. Shen, H. Wang, “Real Time Gray Level Corner Detector”, Proc. of 6th Int. Conference on Control, Automation, Robotics, and Vision (ICARCV) 2000. P. Rosin, “Measuring Corner Properties”, Computer Vision and Image Understanding, vol. 73, Şubat 1999, p. 291-307. E. Vincent, R. Laganiere, “Detecting and Matching Feature Points”, Journal of Visual Communication and Image Representation, vol. 16, Şubat 2005, p. 38-54. H.L. Ipek, Y. Yardimci, “Improved Eigenvalue Corner Detection Technique”, Proc. of SPIE Int. Soc. of Opt. Eng. 5429, 2004. Y. Bastanlar, Y. Yardimci, “Corner Validation based on Extracted Corner Properties”, Computer Vision and Image Understanding Dergisi’ne değerlendirmek üzere gönderilmiştir, Kasım 2006.