İ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
[email protected], [email protected]
Ö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.