ÖLÇEK VE KONUMDAN BAĞIMSIZ BİR BİÇİM TANIMA DİZGESİ ÇALIŞMASI

MeteSEVERCAN B. Uğur ATAK ODTÜ, Elektrik ve Elektronik Mühendisliği Bölümü

ÖZET

Nesnelerin, ölçek ve konumdan bağımsız olarak sınıf landırılması Biçim Tanımanın (Pattern Recognition) uygulama alanları içinde önemli bir yer kaplar. Böyle bir sınıflandırma için uygulanabilecek yöntemlerden birisi, "Fourier Direct Mellin" dönüşümünü (FD M T ) kullanarak önce tanıma dizgesinin giriş işaretlerini öl çek ve konumdan bağımsız bir şekle getirmek ve daha sonra sınıflandırmaya çalışmaktır.

Bu yazıda, yukarıda sözü edilen FD M T dönüşümünü kullanarak değişik ölçek ve konumlardaki, değişik sı nıflardaki işaretleri, gürültüsüz ve gürültülü ortamlarda sınıflandıran bir dizgeyle ilgili çalışmalar özetlenmiştir.

GİRİŞ

Biçim tanımanın birçok uygulamasında karşılaşılan önemli sorunlardan birisi aynı sınıfta tanımlanması ge reken nesnelerden gelen işaretlerin, Şekil 1'deki ör nekten de görüldüğü gibi, değişik konumlarda ve deği

Î;;;:

11;*''

Ş E K İ L l . a ) Bir giriş İşareti; Bu işaretin b) 1/2 ile ölçekleri ni İş c) 1/4 İle ölçeklerimi? ve zaman ekseninde kay mış durumları.

şik ölçeklerde olmasıdır, örneğin karakter tanımada, karakterler değişik boy ve konumlarda olabilirler. Ay nı sorun fotoğraf aracılığı ile tanıma dizgelerinde de sık sık ortaya çıkar: Fotoğrafın çekildiği yere, yük sekliğe, açıya bağlı olarak aynı nesneden değişik giriş işaretleri elde edilebilir. Radar yankı işaretlerinden gemi sınıflandırması yapılırken de gemiden birbirine yakın açılarda gelen yankılar aynı işaretin sıkışmış veya açılmış (ölçeklenmiş) bir biçimi olarak elde edi lirler.

Bu yazıda ölçekleme ve konumdan bağımsız bir sınıf landırma dizgesi üzerinde yapılan bir çalışma özetle necektir. Çalışmada tek boyutlu işaretler kullanılmış tır, ancak sonuçlar iki boyutlu işaretler için de kolay lıkla genelleştirilebilir. Y azıda sırasıyla bir biçim tanı ma dizgesinin temel ilkeleri özetlenecek, "Fourier Direct Mellin" dönüşümü tanıtılacak ve dizgenin bilgi sayar benzetim çalışmalarından özetler verilecektir.

BİÇİM TANIMA

Temel olarak bir biçim tanıma dizgesi Şekil 2'de gö rülen şu üç alt dizgeden oluşur : 1) Algılayıcı (Recep tor), 2) özelik Seçici (Feature Extractor), 3) Smıflan dırıcı (Classifier).

«(o

AlgtloyKc

DanOfdm

I

Boyut

A M t t ı a I &£ S m f l o n d r a I

ŞE K İ L 2. Basit bir sınıflandırma dizgesinin yapısı

Algılayıcı, giriş işareti x (t )' y i örneklenmiş ve kuanti ze edilmiş bir

dizisine dönüştürür. Görüntü işaretleri için algılayıcı nın çıkışı iki boyutlu bir [x (n, m)J dizisi olabilir.

özelik seçiminin ilk katı bire bir

X = fx(n)) Y =(y(n)} gibi bir dönüşümü gerçekleştirir. Bu dönüşümün amacı giriş dizisini sınıflandırma için daha uygun bir biçi me getirmektir. Giriş ve dönüşüm dizileri f x (n)J ve [y (n)j N öğeli birer vektör olarak düşünülebilir. Ge nellikle N oldukça büyük bir sayı olduğundan tüm öğeleri kullanarak doğrudan bir sınıflandırmaya geç mek zaman alıcı ve masraflı olduğundan verimsiz so nuçlar doğurur. "Boyut azaltıcı" kat, sınıflandırma için yeterli olabilecek M, (M < N ) , öğe belirleyerek özelik vektörü (feature vector) denilen

Z = [2lızîı...)zM}

dizisini oluşturur. Burada değinilecek Biçim Tanıma uygulamalarında özelik vektörü Z ölçek ve konumdan bağımsız olmalıdır. Bu istek dönüşüm katında gerçek leştirilir. Eğer kullanılan dönüşüm, yer değiştirme ve ölçekten bağımsız ise özelik vektörünün her öğesi için de aynı şey geçerli olmalıdır.

Biçim tanıma dizgesinin son katını smıflandırıcı dizge si oluşturur. Sınıflandırıcı, daha önceden bilinen ge nellikle istatistiksel bilgileri kullanarak giriş işaretini bu sınıflardan birisi olarak kararlaştırır. Bu çalışmada bir "enaz uzaklık sınıflandırıcı" kullanılmış olup, her sınıfı belirleyen örnek özelik vektörlerinin ortalama ları kullanılarak, S sınıf için doğrusal diskriminant iş levi denilen D, (Z), i = 1 , 2 , . . . S gibi birer işlev belir lenmiştir. Sınıflandırıcı, girişindeki herhangi bir Z özelik vektörü için bütün Dj (Z ), i = 1 , 2 , . . . S değe rini hesaplar ve eğer

Dj(Z )>D. (Z )

i. İ = 1 , 2 S

ise Z nin i'ninci sınıfa ait olduğunu belirler.

FOURİER MELLİN DÖNÜŞÜMÜ

Bilindiği gibi zaman ekseninde kaymış bir işaretin Fourier dönüşümünün mutlak değeri asıl işaretinki ile aynıdır. Bu özellikten dolayı Fourier dönüşümü ko numdan bağımsız tanımlama dizgelerinde sık sık kul lanılmaktadır. Fourier dönüşümününkine benzer bir şekilde Mellin dönüşümünün mutlak değeri de ölçek ten bağımsız bir sonuç verir.

Bu iki dönüşümün ard arda uygulanması ile Fourier Mellin ( F M ) dönüşümü adı verilen ve konum ve öl çekten bağımsızlık özelliklerinin her ikisini de taşıyan bir dönüşüm elde edilir. F—M dönüşümü değişik şekil lerde gerçekleştirilebilir. Bu çalışmada FDMT (Fourier Direct Mellin transform) diye bilinen dönüşüm kulla nılmıştır. Aşağıda kısaca bu dönüşümler tanıtılmaya çalışılacaktır.

Verilen bir g (t ) , t >0 işareti için Mellin dönüşümü

G(s) = / g ( t ) t 5 ' 1 dt

(1)

o

olarak tanımlanır (1 ). Y ukarıdaki eşitlikte t = e x dö nüşümü yapılır ve s = j c o kullanılırsa, g ( e x ) işareti nin Fourier dönüşümü

=/~g(ex)e '"xdx

(2)

elde edilir [ i ] , [2J. ( ( 2 ) bağıntısında (G ( j co) ye rine kolaylık olması için G (jco) kullanılmıştır.) Böy lece bir işaretin Mellin dönüşümü Fourier dönüşümü

kullanılarak Şekil 3'te gösterilen dizge ile bulunabilir.

g(t)

Fouritr

Metlin DdnCuümü

Mnö»ümü

60*)

ŞE K İ L 3. Mellln Dönüşümünün Fourler Dönüşümü yardımıy la bulunması

Mellin dönüşümünün ölçekten bağımsızlığı özelliği Ek 1 'de gösterilmiştir.

Hızlı Fourier dönüşümü (FFT) yordamları ile, örnek lenmiş işaretlerin Fourier dönüşümleri bilgisayarda kolaylıkla ve çok hızlı bulunabildiğinden Şekil 3'deki dizge yaygın olarak kullanılmaktadır. Yalnız burada t = ex dönüşümü kullanılması sonucunda örnekler ara sındaki uzaklıkların eşitliği kaybolduğundan Fourier dönüşümü almadan önce eşit aralıklı yeni bir örnek dizisi, enterpolasyon yapılarak bulunur. Bu yazıda sö zü edilen çalışmalarda Mellin dönüşümü FFT yardımı ile değil doğrudan DMT (Direct Mellin Transform) dönüşümü ile bulunmaktadır.

DMT ve FDMT DÖNÜŞÜMLERİ

Giriş işareti g(t)'nin T zaman aralıkları ile örneklendi ğini varsayarak, örneklenmiş işaret (gkj ={gf(k 1) T]} , k=1,2, N 1 (3)

şeklinde N öğeli bir dizi olarak gösterilebilir. Bu dizi nin doğrudan Mellin dönüşümü (DMT)

=2 [l k

(4)

şeklinde tanımlanır (1), (2). Yukarıdaki eşitlikte A^= gk ~&k+1 ve T — 1 olarak alınmıştır, s = İ wn için (4) eşitliği

1N G(jw ) = — 2 [cos(w Ink)

ıu.,k=1

+jsin(wnlnk)]Ak

(5)

şekline girer. FFT kullanılara hızlı bir şekilde buluna bilen Mellin dönüşümü (Fast Mellin Transform, FMT), DMT ile çok daha yavaş bir şekilde, fakat FMT'deki t = ex dönüşümünün getirdiği sorunlardan arınmış olarak bulunabilir. Tanımlama dizgelerinde genellikle özelik vektörünü oluşturmak için birkaç terim yeterli olduğundan DMT dönüşümü yalnızca birkaç wn teri mi için bulunur ve böylece DMT'nin FMT'ye oranla yavaş olması herhangi bir sorun yaratmaz.

gidilişinin •FDMT

ŞEK İ L 4. FDM T Dönüşümü ölçek ve konumdan bağımsız bir dönüşüm olan FDMT (Fourier Direct Mellin Transform), Fourier ve DMT dönüşümlerinin ard arda alınmasıyla Şekil 4'de görüldüğü gibi bulunabilir.

ŞEK İ L 5. a) Benzetim çalışmalarında kullanılan 5 örnek İşaretler.

b) 5 sınıf işaretin gürültülü örnekleri c) S.a'daki İşaretlerin F D M T dönüşümleri

sınıftan

r

B i r f ( t ) işaretinin Fourier dönüşümü

f(t) «

• F(«)

şeklinde gösterilirse, f (at) işaretinin Fourier dönüşü mü

f(at)

1 F(w/a)

olduğundan, Şekil 4'de görüldüğü gibi FFT ve DM T blokları arasında bir normalizasyon basamağı gerekli dir.

BİLGİSAYAR BENZETİM SONUÇLARI

Bilgisayar benzetiminde kullanılan dizge, beş değişik sınıfa ayrılan ve değişik konum ve ölçeklerde buluna bilen işaretlerin tanınması için kullanılmıştır. Bu işa retlerin gürültüsüz ve gürültü içindeki şekilleri ve bun ların FOMT dönüşümleri Şekil 5'de, kullanılan dizge ise Şekil 6'da gösterilmiştir.

Gıris işareti — ( V ) H F F T | JMuttok O»»r H| jNormalintyonj GiirülKI M.OH«rn}~—|ÖMTtM Itrim) L 1

Ş E K İ L 6. F D M T sınıflandırma dizgesi

Şekil 6'da görüldüğü gibi sınıflandırıcının giriş işaretle ri a) sınıflandırılmaya çalışılan giriş işaretinin FDMT dönüşümünden alınan ve özelik vektörünü oluşturan M öğe (1 <M < 1 0), b) sınıflandırma için gerekli ön bilgi olarak ortalama vektörleri Oj, i = 1 , 2 , . . . , 5'dir. Ortalama vektörleri, herhangi bir işaret sınıflandırıl maya geçilmeden önce her sınıftan alınan çeşitli ör neklerden oluşturulmuş ve bilgi belleğine yüklenmiş tir. Sınıflandırın bu önbilgiyi kullanarak gelen işareti beş sınıftan birisi olarak tanımlar.

Tanımlama dizgesinin başarımı ile ilgili sonuçlar Şekil 7'de gösterilmiştir. Şekil 7a'daki tablo her sınıftan değişik konum ve ölçekteki 10 değişik işaretin ta nımlanması sonucunda çıkarılmıştır. Buradan görül düğü gibi yaklaşık % 90'lık bir başarım 20 dB işaret gürültü olarında gerçekleşmektedir. Şekil 7.b'de ise % 90'lık bir başanm için yalnızca beş öğeli bir özelik vektörünün yeterli olduğu görülmektedir.

KARARLAŞTIRILAN SI N I F 1 2 34 5

1 10

GERÇEK 2

SINir

.

,.

10 V

Doğru tanımlama s a y ı s ı

1 2 3 4 5 6 7 8 9 10 Ö i . l i k s 7 y ı 7 ı

ŞE K İ L 7.a) SNR = 2 0 dB İçin sınıflandırma dizgesi sonuçları b) Ooğru tanımlama oranının özelik ve vektörünün öğe sayısına bağlantısı.

EK 1 Bir g (t) işaretinin ölçeklenmiş şekli h(t) = g(kt ) olsun. Bu işaretin Mellin dönüşümü

H ( ) « ) = / " h(ex)e 'wxdx

= /" g(kex)e"İwxdx

= /"

— oo

g(ex+lnk)e 'wxdx

y = x + Ink dönüşümü uygulanırsa

H(jco)=e'wlnk /" g(ey)e İwy dy

şekline girer. Y ukarıda görüldüğü gibi H (jw )'nın G (jco)'dan tek farkı integralin başındaki e ' ^ 1 " 1 * gibi doğrusal bir faz terimidir. Bu faz terimi mutlak değer alma işlemi ile ortadan kalkacağından | H(jco) | = | G ( j w ) | bulunur, böylece Mellin dönüşümünün mutlak değeri nin ölçekten bağımsızlığı gösterilmiş olur.

KAYNAKLAR (1) Zwicke, P. E., and Kiss, Imre, Jr., "A new Implementa tion of the Mellin Transform and its Application to Radar Classification of Ships", IEEE Transactions on Pattern Analysis and Machinc Intdügence, vol. PAMI 5, No. 2, March 1983.

(2) Atak, B. Uğur, "Scale and Translation Invariant Pattern Classification", Yüksek Lisans Tezi, Elektrik ve Elektro nik Müh. Böl. ODTÜ, 1984.