Penggenerasian Ciri I : Transformasi Linier Octa Heriana, 05906-TE Sumarna, 06248-TE Jurusan Teknik Elektro FT UGM, Yogyakarta
6.1
PENDAHULUAN
Tujuan dari bab ini adalah penggenerasian ciri-ciri melalui transformasi linier pada cuplikan-cuplikan masukan (pengukuran). Konsep dasarnya adalah mentransformasikan (mengalih-ragamkan) sekumpulan hasil pengkuran menjadi kumpulan ciri baru. Jika transformasi tersebut dipilih yang sesuai, maka ciri-ciri domain transformasi dapat menunjukkan sifat-sifat ‘kemasan informasi’ yang tinggi dibandingkn dengan cuplikan masukan aslinya. Ini berarti bahwa sebagian besar informasi kaitan klasifikasi terperas menjadi ciri-ciri dalamjumlah yang relative kecil, sehingga mengurangi dimensi ruang ciri yang diperlukan. Alasan yang mendasari ciri-ciri berbasis transformasi tersebut adalah bahwa kesesuaian transformasi yang dipilih dapat menggali dan menghilangkan kelebihan informasi yang biasanya ada dalam sejumlah cuplikan yang diperoleh dengan piranti pengukuran. Sebagai contoh suatu citra yang dihasilkan dari suatu piranti pengukuran, misalnya piranti sinar-X atau kamera. Piksel-piksel (cuplikan masukan) pada berbagai posisi di dalam citra mempunyai korelasi berderajad besar, terkait dengan konsistensi morpologik internal citra nyata yang membedakannya dari derau (noise). Kemudian jika digunakan piksel-piksel tersebut sebagai ciri-ciri, maka akan terdapat informasi berlebihan yang berderajad besar. Secara alternatif, misalnya jika diperoleh transformasi Fourier dari suatu citra nyata, maka hal tersebut menjelaskan bahwa sebagian besar energy yang terletak pada komponen frekuensi rendah berhubungan dengan adanya korelasi tinggi antar aras keabuan (gray level) piksel-piksel tersebut. Sehingga penggunaan koefisien Fourier sebagai ciri menunjukkan suatu pilhan yang rasional, sebab energy rendah memungkinkan kehilangan informasi kecil, koefisien-koefisien frekuensi tinggi dapat diabaikan.
6.2
VEKTOR-VEKTOR BASIS DAN CITRA
Misalkan x(0), x(1), x(2), …, x(N-1) merupakan sejumlah cuplikan masukan dan x adalah suatu vector Nx1 yang sesuai, xT = [x(0), x(1), x(2), …, x(N-1)]. Diberikan suatu matrik unitary NxN yaitu A1, mendefinisikan suatu vector tertransformasi y dari x sebagai : ⎡ a 0H ⎤ ⎢ H ⎥ ⎢ a1 ⎥ H y = A x ≡ ⎢ . ⎥ x ⎢ ⎥ ⎢ . ⎥ ⎢a H ⎥ ⎣ N −1 ⎦
(6.1)
di mana “H” menyatakan suatu opersi Hermitian, yaitu konjugasi komplek dan transposisi. Dari (6.1) dan definisi matrik unitary diperoleh : N −1
x = Ay =
∑ y(i) ai
(6.2)
i =0
Kolom-kolom pada A, ai, i = 0, 1, 2, …, (N-1), disebut vector-vektor basis dari suatu transformasi. Elemenelemen y(i) dari y bukan sesuatu tetapi yang penting adalah proyeksi-proyeksi x pada vector-vektor basis tersebut. Pengambilan inner-product dari x dengan aj diperoleh : 〈 aj , x 〉 ≡ ajH x =
N −1
∑ y(i) 〈 aj , ai 〉 = i =0
N −1
∑ y(i) δ i =0
ij
= y(j)
(6.3)
Hal ini terkait dengan sifat unitary dari A, yaitu AH A = I atau 〈 aj , ai 〉 = aiH aj = δ ij . Dalam banyak persoalan, seperti pada analisis citra, sekumpulan cuplikan masukan merupakan runtun (sequence) dua dimensi X (i,j); i, j = 0, 1, 2, ..., (N-1), pendefinisian NxN matrik X alih-alih sebuah vektor. Pada kasus tersebut dapat ditentukan suatu ekivalensi N2 vektor x, sebagai contoh dengan urutan baris matrik satu sesudah yang lain (urutan lexicographic) xT = [X(0,0), ..., X(0, N-1), ..., X(N-1, 0), ..., X(N-1, N-1)] dan kemudian mentransformasikan vektor ekivalen ini. Tetapi hal ini bukan cara kerja yang paling efisien. Jumlah operasi yang diperlukan untuk N2x N2 kwadrat matrik (A) dengan N2 x1 vector x adalah dalam orde O(N4) yang menjadi penghalang pada banyak aplikasi. Kemungkinan alternatif adalah mentransformasikan matrik X melalui sekelompok matrik basis atau citra basis. Misalkan U dan V adalah matrik unitary NxN. Menentukan matrik tertransformasi Y dari X sebagai
atau
Y = UH X V
(6.4)
X = U Y VH
(6.5)
Jumlah operasinya sekarang berkurang menjadi O(N3). Persamaan (6.5) secara alternatif dapat dituliskan sebagai : X =
N −1
N −1
i =0
j =0
∑ ∑Y (i, j) ui vjH
(6.6)
di mana ui merupaka vector kolom dari U dan vj adalah vektor kolom dari V. Setiap outer product ui vjH merupakan sebuah matrik NxN
u i 0 v *jN −1 ⎤ ⎥ . . . ⎥ ≡А ij ⎥ . . . ⎥ . . u iN −1v *jN −1 ⎦⎥
⎡ u i 0 v *j 0 ⎢ . H ui vj = ⎢ ⎢ . ⎢ * ⎣⎢u iN −1v j 0
. .
dan (6.6) merupakan ekspansi dari matrik X dalam suku-suku N2 citra basis (matrik basisi). Tanda menyatakan konjugasi komplek. Jika Y menghasilkan diagonal, maka (6.6) menjadi :
*
N −1
X =
∑ Y (i, i) ui viH i =0
dan jumlah citra basis direduksi menjadi N. Interpretasi yang sama terhadap (6.3) juga mungkin. Terhadap yang terakhir tersebut, selanjutnya mendefinisikan inner product antara dua matrik sebagai : 〈 A, B 〉 ≡
N −1
N −1
m =0
n =0
∑ ∑
A*(m,n) B(m,n) .
(6.7)
Dapat ditunjukkan bahwa Y(i,j) = 〈 Аij, X 〉.
(6.8)
Sebenarnya elemen (i,j) dari matrik tertransformasi dihasilkan dari perkalian setiap elemen X dengan konjugasi dari elemen Aij yang bersesuaian dan menjumlahkannya untuk semua produk. Transformasi-transformasi jenis (6.4) juga dikenal sebagai separable. Alasannya adalah bahwa itu dapat dicari dari mereka sebagai rangkaian transformasi satu dimensi, pertama dioperasikan pada vektor kolom dan kemudian pada vektor-vektor baris. Sebagai contoh hasil perantara pada (6.4), Z = UH X, adalah ekivalen dengan N transformasi yang dikenakan pada vektor-vektor kolom dari X, dan (UH X)V = (VHZH)H adalah ekivalen dengan urutan ke dua dari N transformasi yang bekerja pada baris-baris Z. Contoh 6.1.
Diberikan citra X dan matrik tansformasi ortogonal U sebagai ⎡1 2⎤ X = ⎢ ⎥, U = ⎣ 2 3⎦
1 ⎡1 1 ⎤ ⎢ ⎥ 2 ⎣1 − 1⎦
citra tertransformasi Y = UTXU adalah Y =
1 2
⎡1 1 ⎤ ⎡1 2⎤ ⎡1 1 ⎤ ⎡ 4 − 1⎤ ⎢1 −1⎥ ⎢2 3⎥ ⎢1 −1⎥ = ⎢− 1 0 ⎥ . ⎣ ⎦⎣ ⎦⎣ ⎦ ⎣ ⎦
Citra basis yang bersesuaian adalah : A00 =
1 2
⎡1⎤ ⎢1⎥ [1 ⎣⎦
1] =
1 2
⎡1 1⎤ ⎢1 1⎥ . ⎣ ⎦
1 2
A11 =
⎡1⎤ ⎢−1⎥ [1 ⎣ ⎦
− 1] =
1 2
⎡ 1 − 1⎤ ⎢− 1 1 ⎥ . ⎣ ⎦
Dengan cara yang sama dapat diperoleh : A01 = A10T =
6.3
1 2
⎡1 − 1⎤ ⎢1 − 1⎥ . ⎣ ⎦
TRANSFORMASI KARHUNEN-LOEVE
Misalkan x adalah vektor dari cuplikan masukan. Pada kasus larik (array) citra, x dapat dibentuk dengan urutan lexicographic terhadap elemen-elemen larik. Sifat-sifat yang diinginkan dari ciri-ciri yang digenerasi adalah tak terkorelasi timbal-balik dengan maksud untuk menghindari berlebihnya informasi. Tujuan dari bagian ini adalah menggenerasi ciri-ciri yang secara optimal tak terkorelasi, yaitu E[y(i)y(j)] = 0, i ≠ j. Misalkan data nyata : y = AT x .
(6.9)
Dari definisi matrik korelasi diperoleh : Ry ≡ E[yyT] = E[AT xxT A] = AT RxA.
(6.10)
Tetapi Rx adalah matrik simetris, dan karenanya vektor-vektor eigen yang saling ortogonal. Kemudian, jika matrik A dipilih sedemikian hingga kolom-kolomnya merupakan vektor eigen ortogonal ai, i = 0, 1, 2, ..., N-1, dari Rx, maka Ry adalah diagonal Ry = AT Rx A = Λ
(6.11)
di mana Λ adalah matrik diagonal dengan elemen-elemen pada diagonalnya masing-masing nilai eigen λi, dengan i = 0, 1, 2, ..., N-1, dari Rx. Selanjutnya, pengambilan Rx positif memastikan nilai eigen-nya positif. Transformasi yang dihasilkan tersebut dikenal sebagai transformasi Karhunen-Loeve (KL). Transformasi KL sangat fundamental di dalam pengenalan pola serta dalam aplikasi pemrosesan sinyal dan citra. Sifat-sifat pentingnya meliputi : Mean square error approximation. Dari persamaan (6.2) dan (6.3) diperoleh : N −1
x =
∑ y(i) ai
dan y(i) = aiT x
(6.12)
i =0
Sekarang mendefinisikan vektor baru dalam subspace berdimensi m sebagai :
xˆ =
m−1
∑ y(i) ai i =0
(6.13)
di mana hanya m vektor-vektor basis yang dicakup. Dengan jelas, ini bukanlah sesuatu tetapi proyeksi x pada subspace dijangkau oleh m vector-vektor eigen (ortonormal) yang tercakup dalam somasi. Jika diusahakan untuk mendekati x dengan proyeksinya xˆ , hasil mean square error (MSE) diberikan oleh :
[
E x − xˆ
2
]
⎡ N −1 = E ⎢ ∑ y (i )ai ⎢⎣ i = m
2
⎤ ⎥ ⎥⎦
(6.14)
Selanjutnya memilih vektor-vektor eigen yang menghasilkan MSE minimum. Dari (6.14) dan mengingat akan sifat ortonormalitas dari vektor-vektor eigen tersebut diperoleh : 2 ⎡ N −1 ⎤ ⎡ E ⎢ ∑ y (i ) a i ⎥ = E ⎢ ∑ ⎣ i ⎣⎢ i = m ⎦⎥
∑ j
N −1
=
⎤ ( y (i ) a iT )( y ( j ) a j ) ⎥ ⎦
∑ E[ y 2 (i)] = i =m
N −1
∑a i =m
T i
E[ xx T ]ai
(6.15) (6.16)
Kombinasi ini dengan persamaan (6.14) dan pendefinisian vektor eigen, akhirnya diperoleh :
[
E x − xˆ
2
]=
N −1
∑ aiT λi ai = i =m
N −1
∑λ i =m
(6.17)
i
Jika dipilih dalam (6.13) vektor-vektor eigen yang bersesuaian dengan nilai eigen m terbesar dari matrik korelasi, maka error pada (6.17) diminimisasi, merupakan jumlah dari N-m nilai-nilai eigen terkecil. Selanjutnya dapat ditunjukkan bahwa ini juga merupakan MSE minimum, dibandingkan dengan pendekatan lain untuk x oleh vektor berdimensi m. Hal ini menjadi alasan bahwa transformasi KL juga dikenal sebagai Analisis Komponen Utama (PCA : Principal Component Analysis). Bentuk lain dari transformasi KL diperoleh jika penghitungan A dalam suku-suku vektor-vektor eigen pada matrik kovarian. Transformasi ini mendiagonaisasi matrik kovarian Σy, Σy = AT Σx A = Λ.
(6.18)
Pada umumnya keduanya berbeda dan serupa untuk vektor-vektor acak rerata nol. Dalam praktek ini biasanya kasus, sebab jika ia salah dapat mengganti setiap vektor dengan x – E[x]. Hal itu dapat ditunjukkan bahwa dalam kasus ini basis ortonormal yang dihasilkan (Σx vektor-vektor eigen aˆ i ) menjamin bahwa MSE antara x dan pendekatannya diberikan oleh :
xˆ =
m−1
∑ y(i) aˆ i + i =0
N −1
∑ E[ y(i)]aˆ i =m
i
,
y(i) ≡ aˆ iT x adalah minimum.
(6.19)
Komponen terakhir N-m tidak acak tetapi dibekukan masing-masing nilai reratanya. Optimalitas transformasi KL, terhadap pendekatan MSE, membawa ke sifat-sifat utama dari kemasan informasi dan memberikan alat untuk memilih ciri-ciri dominan m keluar dari N cuplikan pengukuran. Tetapi meskipun ini mungkin merupakan kriteria yang baik, dalam banyak kasus ia tidak perlu dibawa ke
separabilitas kelas maksimum dalam subspace berdimensi lebih rendah. Hal ini beralasan karena reduksi dimensionalitas bukan dioptimisasi terhadap separabilitas kelas. Pada Gambar 6.1, vektor-vektor ciri pada kedua kelas mengikuti distribusi Gauss dengan matrik kovarian sama. Ellip-ellip tersebut menunjukkan kurva dengan nilai pdf konstan. Vektor eigen a1 adalah yang bersesuaian dengan nilai eigen terbesar. Proyeksi pada a1 membuat kedua kelas hampir serupa. Tetapi proyeksi pada a2 menjadikan kedua kelas terpisah.
x2
a2
a1
x1
Gambar 6.1. Transformasi KL tidak selalu terbaik untuk pengenalan pola. Dalam contoh ini, proyeksi pada vektor eigen dengan nilai eigen yang lebih besar membuat kedua kelas serupa. Dengan kata lain, proyeksi pada vektor eigen yang lain menjadikan kelas-kelas tersebut terpisah.
Varian Total. Misalkan E[x] adalah nol. Jika ini bukan kasus, reratanya selalu dapat dikurangi. Misalkan y adalah KL tertransformasi vektor x. Dari masing-masing definisi diperoleh bahwa σ y2(i ) ≡ E[y2(i)] = λ i . Yaitu bahwa nilai-nilai eigen dari matrik korelasi masukan sama dengan variansi ciri-ciri tertransformasi. Kemudian pemilihan ciri-ciri itu, y(i) ≡ aiT x, bersesuaian dengan nilai-nilai eigen terbesar m yang membuat jumlah variansinya Σi λ i maksimum. Dengan kata lain, ciri-ciri m yang terpilih menahan sebagian besar varian total yang terkait dengan variable acak aslinya x(i). Tentu saja, yang terakhir itu sama dengan trace dari Rx, yang diketahui dari aljabar linier sama dengan jumlah dari nilai-nilai eigen, yakni : N −1
∑λ i =0
i
.
Dapat ditunjukkan bahwa hal tersebut merupakan sifat yang lebih umum, yaitu bahwa dari semua kemungkinan kumpulan ciri-ciri m, diperoleh melalui transformasi linier ortogonal pada x, salah satunya dihasilkan dari transformasi KL yang memiliki jumlah varian terbesar.
Entropy. Diketahui bahwa entropy suatu proses didefinisikan sebagai Hy = -E[ln py(y)] dan merupakan ukuran keacakan suatu proses. Untuk Gaussian dengan rerata nol dari proses berdimensi m multivariabel, entropy tersebut menjadi :
Hy =
1 1 1 E[yT R y−1 y] + ln R y + m ln (2π). 2 2 2
(6.20)
Tetapi E[yT R y−1 y] = E[trace {yT R y−1 y}] = E[trace { R y−1 y yT }] = trace (I) = m dengan menggunakan sifat yang telah diketahui dari aljabar linier, maka determinannya adalah ln R y = ln (λ0 λ1 λ2 ... λm-1). Pemilihan terhadap ciri-ciri m yang bersesuaian nilai eigen terbesar m akan memaksimumkan entropy proses. Hal ini diharapkan karena varian dan keacakan berhubungan langsung.
Catatan. Konsep subspace vektor eigen utama juga diekspliotasi sebagai pengklasifikasi. Pertama, rerata cuplikan dari seluruh pelatihan dikurangkan dari vektor-vektor ciri. Untuk setiap kelas, ωi, matrik korelasi Ri diestimasi dan menghitung vektor-vektor eigen utama m (bersesuaian dengan nilai-nilai eigen terbesar m). Suatu matrik Ai dibentuk menggunakan masing-masing vektor eigen sebagai kolom. Vektor ciri x yang tidak diketahui kemudian diklasifikasi ke dalam kelas ωj dengan :
ATj x > AiT x , ∀i ≠ j
(6.21)
yaitu bahwa kelas tersebut sesuai dengan norm maksimum proyeksi subspace dari x. Dari teorema Pythagoras, ini ekivalen dengan pengklasifikasian sebuah vektor dalam subspace kelas terdekat. Decision surface-nya merupakan hyperplanes jika semua subspace memiliki dimensi yang sama atau surface kuadrik dalam kasus yang lebih umum. Pengklasifikasian subspace mengintegrasi tahapan-tahapan penggenerasian atau pemilihan ciri dan rancangan klasifikasi.
Contoh 6.2. Matrik korelasi dari sebuah vektor x diberikan sebagai : 0,1 ⎤ ⎡0,3 0,1 ⎢ Rx = 0,1 0,3 − 0,1⎥ ⎢ ⎥ ⎢⎣ 0,1 − 0,1 0,3 ⎥⎦
Menghitung transformasi KL dari vektor masukan tersebut. Nilai-nilai eigen dari Rx adalah λ0 = 0,1; λ1 = λ2 = 0,4. Karena matrik Rx simetrik, maka selalu dapat disusun vektor-vektor eigen ortonormal. Untuk kasus ini dapat diperoleh :
a0 =
⎡1⎤ 1 ⎢ ⎥ − 1 , a1 = 3 ⎢ ⎥ ⎢⎣ − 1⎥⎦
⎡ 2⎤ 1 ⎢ ⎥ 1 , a2 = 6 ⎢ ⎥ ⎢⎣1⎥⎦
⎡0⎤ 1 ⎢ ⎥ 1 . 2 ⎢ ⎥ ⎢⎣ −1⎥⎦
Transformasi KL kemudian ditentukan dengan :
⎡2 / 6 ⎡ y ( 0) ⎤ ⎢ y (1) ⎥ = ⎢ 0 ⎢ ⎢ ⎥ ⎢1 / 3 ⎢⎣ y ( 2) ⎥⎦ ⎣
1 / 6 ⎤ ⎡ x (0) ⎤ ⎥ 1 / 2 − 1 / 2 ⎥ ⎢ x (1) ⎥ ⎢ ⎥ − 1 / 3 − 1 / 3 ⎥⎦ ⎢⎣ x ( 2) ⎥⎦ 1/ 6
di mana y(0), y(1) besesuaian dengan dua nilai eigen terbesar.
6.4
DEKOMPOSISI NILAI SINGULAR
Diberikan sebuah matrik X dengan rank r, akan ditunjukkan bahwa ada NxN matrik-matrik unitary U dan V sedemikian hingga : ⎡ Λ1 / 2 X = U ⎢ ⎣ O
O⎤ H ⎥V 0⎦
⎡Λ1 / 2 atau Y ≡ ⎢ ⎣ O
di mana Λ1 / 2 matrik diagonal r x r dengan elemen-elemen
O⎤ H ⎥ = U XV 0⎦
(6.22)
λi dan λ i adalah nilai-nilai eigen bukan nol r
H
dari matrik X X yang terkait. O menyatakan matrik elemen nol. Dengan kata lain, ada matrik unitary U dan V sedemikian hingga matrik tertransformasi Y adalah diagonal. Dari (6.22) dapat ditunjukkan bahwa : r −1
X =
∑ i =0
λi ui viH
(6.23)
di mana ui, vi berturut-turut merupakan kolom pertama r dari U dan V. Lebih tepatnya, ui, vi berturutturut adalah vektor-vektor eigen dari XXH dan XHX. Nilai-nilai eigen λ i dikenal sebagai nilai-nilai singular dari X dan pengekspansian menurut (6.23) sebagai dekomposisi nilai singular (SVD : singular value decomposition) dari X atau representasi spektral dari X.
Contoh 6.3. Diberikan suatu matrik X sebagai berikut. Tujuannya adalah menghitung dekomposisi nilai singularnya. ⎡6 ⎢0 X = ⎢ ⎢4 ⎢ ⎣0
6⎤ 1⎥⎥ 0⎥ ⎥ 6⎦
⎡52 36⎤ Langkah 1 : Mencari nilai-nilai eigen dan vektor-vektor eigen dari XTX = ⎢ ⎥ ⎣36 73⎦ Ini adalah λ0 = 100, λ1 = 25 dan vektor eigen yang bersesuaian adalah v0 = [0,6 ; 0,8]T; v1 = [0,8 ; -0,6]T.
Langkah 2 : Menghitung vektor-vektor eigen dari XXT. Yakni matrik 4x4 dengan rank-2. Vektor-vektor eigen yang bersesuaian dengan nilai-nilai eigen bukan nol λ0, λ1 dihitung melalui (6.26), yaitu u0 = 0,1X v0, u1 = 0,2X v1 atau masing-masing [0,84; 0,08; 0,24; 0,48]T dan [0,24; -0,12; 0,64; -0,72]T. Langkah 3 : Menghitung SVD dari X, yaitu : X = 10 [0,84; 0,08; 0,24; 0,48]T [0,6 ; 0,8] + 5 [0,24; -0,12; 0,64; -0,72]T [0,8 ; -0,6].
Jika dipertahankan suku-suku ke dua yang pertama, maka hasil pendekatannya adalah yang terbaik, dalam rasa (sense) Frobenius, pendekatan rank-1 dari X.
6.5
ANALISIS KOMPONEN INDEPENDEN
Analisis komponen utama (PCA) dilakukan dengan transformasi KL yang menghasilkan ciri-ciri y(i), i = 0, 1, 2, ..., N-1, yang tak terkorelasi timbal-balik. Solusi yang diperoleh dengan transformasi KL akan optimal ketika pereduksian dimensionalitasnya menjadi tujuan dan menginginkan minimisasi pendekatan MSE. Tetapi untuk aplikasi khusus seperti ilustrasi pada Gambar 6.1 solusi yang diperoleh jauh dari yang diharapkan. Analisis komponen independen (ICA : Independent Component Analysis) berusaha untuk mencapai lebih banyak dari pada dekorelasi sederhana terhadap data. Diberikan sejumlah cuplikan masukan x, ditentukan matrik invertibel W berukuran NxN sedemikian masukan-masukan y(i), i = 0, 1, 2, ..., N-1, dari vektor yang tertransformasi :
y = Wx
(6.34)
adalah independen timbal-balik. Tujuan dari independensi secara statistik adalah kondisi yang lebih kuat dari pada ke-tidak korelasi-an yang diperlukan oleh PCA. Kedua keadaan hanya ekivalen untuk variabel acak Gaussian. Pencarian ciri-ciri independent dari pada tak terkorelasi memberikan arti penggalian informasi yang sedikit lebih, tersembunyi di dalam statistik orde tinggi pada data. Seperti contoh Gambar 6.1 menyarankan bahwa pemaksaan pencarian dengan menggali informasi dalam statistic orde ke dua hanya menghasilkan sedikit yang menarik, untuk persoalan tersebut, arah proyeksi seperti pada a1. Tetapi a2 sudah pasti arah yang lebih menarik dari pandangan titik pemisahan kelas. Penggunaan ICA dapat membuka selubung dari statistik data orde tinggi suatu kelumit informasi yang menunjuk a2 sebagai sesuatu yang paling menarik. Selanjutnya, pencarian ciri-ciri independent secara statistik yang sejalan dengan sifat pembangun peta kognitif dunia luar di dalam otak, dengan pemrosesan data masukan dari indera. Hipotesis Barlow mengatakan bahwa hasil pemrosesan awal yang terbentuk dari detector ciri-ciri visual dapat menghasilkan proses reduksi kelebihan. Dengan kata lain, keluaran syaraf dimungkinkan secara statistik independen timbal-balik, terkondisi, tentu saja pada penerimaan pesan sensor. Dipastikan dahulu bahwa persoalan yang demikian terdefinisi dengan baik, memiliki solusi, dan dalam kondisi apa. Diasumsikan bahwa vektor data acak masukan x adalah sungguh-sungguh tergenerasi oleh kombinasi linier komponen-komponen (sumber) yang secara statistik independen dan stasioner dalam rasa (sense) yang seksama, yaitu :
x = Ay
(6.35)
Tugas berikutnya adalah di bawah kondisi yang bagaimana matrik W dapat dihitung sehingga mencakup komponen-komponen y dari persamaan (6.34) dengan penggalian informasi yang tersembunyi di dalam x. Biasanya A diketahui sebagai matrik pencampur (mixing) dan W sebagai matrik pengurai (de-mixing).
ICA Berdasarkan Cumulant Orde-Empat dan -Dua. Pendekatan ini dalam menjalankan ICA merupakan generalisasi langsung dari teknik PCA. Tansformasi KL berfokus pada statistik orde dua dan bergantung pada korelasi silang E[y(i)y(j)] menjadi nol. Ketika pada ICA bergantung pada komponen y menjadi independen secara statistik, hal ini setara dengan kebergantungan semua cross-cumulant orde tinggi menjadi nol. Disarankan untuk membatasi hingga cumulant orde empat sudah cukup untuk banyak aplikasi. Tiga yang pertama dari cumulant adalah sama dengan tiga yang pertama dari moment, yaitu
κ1(y(i)) = E[y(i)] = 0 κ2(y(i)y(j)) = E[y(i)y(j)] κ3(y(i)y(j) y(k)) = E[y(i)y(j) y(k)] dan cumulant orde empat diberikan oleh :
κ4(y(i)y(j) y(k) y(r)) = E[y(i)y(j) y(k) y(r)] - E[y(i)y(j)] E[y(k)y(r)] - E[y(i)y(k)] E[y(j)y(r)] - E[y(i)y(r)] E[y(j)y(k)] di mana telah diasumsikan pemrosesan rerata nol. Asumsi lain yang biasanya digunakan dalam praktek adalah terkait dengan kesimetrian pdf-pdf. Hal ini membuat semua cumulant orde ganjil nol. Persoalannya sekarang direduksi untuk mendapatkan matrik W sehingga orde dua korelasi silang dan orde empat cross cumulant dari variabel transformasi adalah nol. Hal ini dicapai dengan langkah-langkah berikut : Langkah 1. Mengenakan PCA pada data masukan, yakni :
yˆ = AT x
(6.36)
A adalah matrik transformasi unitary pada transformasi KL. Komponen dari vektor acak tertransformasi yˆ adalah tak terkorelasi.
Langkah 2. Menghitung matrik unitary lain Aˆ sehingga cross cumulant orde empat dari komponen vektor acak tertransformasi memenuhi
y = Aˆ T yˆ = 0.
(6.37)
Ini adalah sama dengan pencarian sebuah matrik Aˆ yang membuat jumlah kwadrat auto-cumulant orde empat maksimum, yaitu :
max Aˆ Aˆ T = I Ψ( Aˆ ) ≡
N −1
∑ i =0
κ4(y(i))2
(6.38)
Jumlah kwadrat cumulant orde empat adalah invarian terhadap transformasi linier oleh matrik unitary. Sehingga jumlah kwadrat cumulant orde empat tersebut tetap untuk yˆ , pemaksimuman jumlah kwadrat auto-cumulant y akan memaksa cross-cumulant yang bersesuaian nol. Ruas kanan (6.38) merupakan fungsi dari (a) elemen-elemen matrik Aˆ yang tidak diketahui, (b) elemen-elemen matrik A yang diketahui, dan (c) cumulant komponen acak dari vektor data masukan x, yang mana diestimasi mendahului penerapan metode tersebut. Dalam praktek, peng-nol-an cross-cumulant adalah dicapai dengan pendekatan. Hal ini disebabkan (a) data masukan tidak patuh pada model linier (6.35), (b) data masukan dikorupsi oleh derau, yang tidak akan diingat, dan (c) cumulant masukan hanya diketahui dengan pendekatan, sehingga mereka diestimasi dengan sejumlah data masukan yang tersedia. Ketika kedua langkah tersebut lengkap, vektor ciri final merupakan komponen independen (secara pendekatan) yang diberikan dengan kombinasi transformasi :
y = (A Aˆ )T x ≡ W x
(6.39)
Ketika Aˆ merupakan unitary ketakterkorelasian yang telah dicapai pada langkah pertama diwarisi oleh elemen-elemen y, yang sekarang memiliki cross-cumulant orde-empat dan –dua adalah nol.
ICA Berdasarkan Informasi Timbal-Balik (Mutual). Pendekatan berdasarkan pada peng-nol-an cross-cumulant orde-empat dan –dua, walaupun sangat luas digunakan dalam praktek, bagaimanapun juga kekurangan dalam generalitas dan juga secara eksternal memaksakan struktur dalam matrik transformasi. Alternatifnya, pendekatan yang lebih nyaman secara teori adalah estimasi W dengan minimisasi informasi timbal-balik antar variabel-variabel acak yang ditransformasi. Informasi timbal-balik I(y) antar komponen y didefinisikan sebagai : N −1
I(y) = -H(y) +
∑
H(y(i))
(6.40)
i =0
di mana H(y(i)) merupakan entropy dari y(i) yang bersesuaian, didefinisikan sebagai : H(y(i)) == -
∫
pi(y(i)) ln pi(y(i)) dy(i)
(6.41)
di mana pi(y(i)) adalah pdf kecil dari y(i). Ternyata I(y) sama dengan jarak probabilitas Kullbach-Leibler N −1
antar joint-pdf p(y) dan hasil kali dari masing-masing densitas probabilitas kecil
∏ p ( y(i)) . i
i =0
Jarak ini (informasi timbal-balik terkait I(y)) alah nol jika komponen-komponen y(i) secara statistik independen. Kombinasi (6.34), (6.40), (6.41) dan memperhatikan rumus hubungan kedua pdf yang terkait dengan x dan y (y fungsi dari x), maka : N −1
I(y) = -H(x) – ln det(W ) -
∑∫
pi(y(i)) ln pi(y(i)) dy(i)
(6.42)
i =0
di mana det(W) menyatakan determinan dari W. Elemen-elemen matrik tak diketahui W tersembunyi dalam pdf-pdf kecil dari variabel-variabel yang ditransformasi y(i). Tetapi tidak mudah untuk menyatakan dependensi ini secara eksplisit. Pendekatan yang dipakai adalah mengekspansi setiap probabilitas kecil di
sekitar pdf Gaussian g(y), mengikuti ekaspansi Edgeworth, dan memotong deret pada pendekatan yang masuk akal. Misalnya mengambil hingga suku ke dua yang pertama dari ekspansi Edgeworth, diperoleh : p(y) = g(y) (1 +
1 1 κ3(y)H3(y) + κ4(y)H4(y) 3! 4!
(6.43)
di mana Hk(y) adalah polynomial Hermit pada orde k. Untuk mendapatkan pernyataan pendekatan I(y) dalam suku-suku cumulant dari y(i) dan W, kita dapat (a) menyisipkan ke dalam (6.42) pendekatan pdf di dalam (6.43), (b) mengadopsi pendekatan ln(1+ y) ≈ y – y2, dan (c) menjalankan integrasi. Untuk kasus persamaan (6.43) dan batasan W harus unitary, maka : I (y ) ≈ C –
N −1
∑ i =0
(
1 2 1 7 1 κ 3 ( y (i )) + κ 42 ( y (i)) + κ 44 ( y (i)) - κ 32 ( y (i))κ 4 ( y (i)) ) 12 48 48 8
(6.44)
di mana C dalam sesbuah independen variabel dari W. Di bawah asumsi bahwa pdf-pdf simetris (cumulant orde tiga nol) dapat ditunjukkan maka minimisasi pernyataan pendekatan informasi timbal-balik (6.44) adalah ekivalen dengan minimisasi jumlah kwadrat cumulant orde empat. Minimisasi I(y) pada (6.44) dapat ditempuh dengan teknik menurunkan gradien, di mana ekspektasi yang tercakup (terkait dengan cumulant) digantikan dengan masing-masing nilai sesaatnya. Kembali ke persamaan (6.42) sebelum menerapkan pendekatan. Karena H(x) tidak tergantung pada W, minimisasi I(y) adalah ekivalen dengan memaksimumkan : ⎡ N −1 ⎤ J(W) = ln det(W ) + E ⎢∑ ln pi ( y (i ))⎥ ⎣ i =0 ⎦
(6.45)
Pengambilan gradien fungsi cost terhadap W menghasilkan :
∂J (W ) = W-T – E[φ(y) xT] ∂W
(6.46)
di mana ⎡ p 0' ( y (0)) p "N −1 ( y ( N − 1)) ⎤ φ(y) ≡ ⎢− ,...,− ⎥ p N −1 ( y ( N − 1)) ⎦ ⎣ p 0 ( y (0))
T
(6.47)
dan
pi' ( y(i)) ≡
dpi ( y (i )) . dy (i )
(6.48)
Jelas bahwa turunan dari densitas probabilitas kecil tergantung pada jenis pendekatan yang diadopsi dalam setiap kasus. Skema kenaikan gradien umum pada langkah iterasi ke t dapat dituliskan : W(t) = W(t – 1) + μ(t) (W -T(t – 1) - E[φ(y) xT]) W(t) = W(t – 1) + μ(t) (I – E[φ(y) yT] ) W -T(t – 1).
(6.49)
Catatan Dari gradient pada (6.46) terlihat bahwa pada titik stasioner berlaku :
∂J (W ) T W = E[I – φ(y) yT] = 0. ∂W
(6.50)
Dengan kata lain, apa yang telah dicapai dengan ICA merupakan generalisasi non linier dari PCA. Kondisi ke-tak terkorelasi-an dapat dituliskan : E[I - y yT] = 0.
(6.51)
Pembaruan persamaan (6.49) yang mencakup inversi dari transpose estimasi W yang sedang berjalan. Di samping isu kerumitan komputasi, juga tidak ada jaminan invertibilitas proses adaptasi. Penggunaan gradient alami (natural) sebagai penggan gradient pada (6.46) dihasilkan : W(t) = W(t – 1) + μ(t) (I – E[φ(y) yT] ) WT(t – 1).
(6.52)
yang tidak memuat inversi matrik dan pada saat yang sama meningkatkan konvergensi.
6.6
TRANSFORMASI FOURIER DISKRET (DFT)
Vektor basis / citra basis untuk ekspansi KL dan SVD adalah tidak tetap tetapi merupakan persoalan kebebasan dan merupakan hasil dari proses optimisasi. Hal ini menjadi alasan untuk optimalitasnya terhadap sifat-sifat dekorelasi dan kemasan informasi, tetapi dalam waktu yang bersamaan tercatat kelemahan utamanya memiliki kerumitan komputasional yang tinggi. Selanjutnya akan dibahas transformasi yang menggunakan vector/citra basis yang tetap. Suboptimalitasnya terhadap sifat dekorelasi dan kemasan informasi terkompensasi dengan tuntutan komputasionalnya yang rendah.
DFT Satu-Dimensi Diberikan cuplikan masukan N yakni x(0), x(1), x(2), ..., x(N-1), maka DFT-nya didefinisikan sebagai : y(k) =
1
N
N −1
∑ x(n) exp(− j n =0
2π kn) , N
k = 0, 1, 2, …, N-1
(6.53)
k = 0, 1, 2, …, N-1
(6.54)
dan DFT balik (inverse) sebagai :
x(n) =
1
N
N −1
∑ y(k ) exp( j k =0
2π kn) , N
di mana j ≡ − 1 . Pengumpulan semua x(n) dan y(k) bersama-sama ke dalam dua vektor Nx1 dan mendefinisikan : 2π WN = exp(-j ) (6.55) N maka (6.53), (6.54) dapat ditulisakan dalam bentuk matrik sebagai :
y = WH x,
x =Wy
(6.56)
di mana : 1 1 ⎡1 ⎢1 W W N2 1 ⎢ N . . N ⎢. ⎢ N −1 2 ( N −1) WN ⎣1 W N
WH =
⎤ ⎥ . W ⎥ ⎥ . . ( N −1)( N −1) ⎥ . WN ⎦ .
1
N −1 N
(6.57)
Hal itu tidak sulit untuk melihat bahwa W adalah matrik unitary dan simetrik W-1 = WH = W*. Vektor-vektor basis adalah kolom-kolom dari W. Sebagai contoh untuk N = 4 1 1 ⎤ ⎡1 1 ⎢1 j − 1 − j ⎥ 1 ⎢ ⎥ W = 2 ⎢1 − 1 1 − 1 ⎥ ⎢ ⎥ ⎣1 − j − 1 j ⎦ dan vektor-vektor basis tersebut adalah
1 [1, 1, 1, 1]T 2 1 w1 = [1, j, -1, -j]T 2 1 w2 = [1, -1, 1, -1]T 2 1 w3 = [1, -j, -1, j]T 2 w0 =
dan 3
x =
∑ y(i) wi. i =0
Komputasi langsung dari (6.56) memerlukan O(N2) penghitungan. Tetapi dengan mengambil keuntungan dari struktur spesifik matrik W, penghematan mendasar dalam penghitungan dimungkinkan melalui algoritma FFT yang cerdas, di mana penghitungan setiap persamaan (6.56) dalam O(Nlog2 N) operasi. DFT telah diperkenalkan sebagai jenis khusus dari transformasi unitary linier dari satu vektor ke yang lain. DFT sebagai alat ekspansi runtun x(n) ke dalam sejumlah N basis runtun hk(n) sebagi : N −1
x(n) =
∑ y(k ) hk(n) k =0
di mana
hk(n) =
1
N
exp(j
2π kn), untuk n = 0, 1, 2, ..., N-1 N
hk(n) = 0, untuk yang lainnya, dan y(k) merupakan koefisien-koefisien ekspansi. Runtun basis DFT termasuk kelompok yang lebih umum dari runtun yang diketahui ortonormal, yaitu :
∑h
〈hl(n), hk(n)〉 ≡
k
(n)hl* (n) = δ kl
(6.58)
n
di mana 〈., .〉 dikenal sebagai inner product dari runtun hk(n), hl(n). Untuk ekspansi DFT tersebut diperoleh
∑ exp (j N
kn) exp(-j
n=0
2π
N −1
1 N
=
2π
N −1
1 〈hk(n), hl(n)〉 = N
∑ exp (j N
2π kn) N
(k - l) n), k, l = 0, 1, 2, ..., N-1.
n=0
Tetapi hal itu dapat ditunjukkan dengan mudah bahwa :
1 N
N −1
2π
∑ exp (j N
(k - l) n) = 1, untuk l = k + rN, r = 0, ±1, ±2, ...
n=0
= 0, untuk yang lainnya. Sehingga :
(6.59)
〈hk(n), hl(n)〉 = δ kl .
DFT Dua-Dimensi Diberikan suatu matrik/citra NxN, maka DFT dua-dimensinya didefinisikan sebagai : Y(k, l) =
1 N
N −1
N −1
m =0
m =0
∑ ∑
X(m, n) WNkm WNln
(6.60)
Y(k, l) W N− km WN− ln .
(6.61)
dan DFT balik (inverse) adalah X(m,n) =
1 N
N −1
N −1
k =0
l =0
∑ ∑
Jelas terbaca bahwa hal itu dapat dituliskan dalam bentuk yang lebih kompak sebagai : Y = W H X WH ,
X = W Y W.
(6.62)
DFT 2-D merupakan transformasi yang dapat dipisahkan dengan citra basis wi wjT; i, j = 0, 1, 2, ..., N-1. Jelas kelihatan dari (6.62) bahwa jumlah operasi yang diperlukan untuk masing-masing komputasi adalah O(N2 log2 N), yaitu banyaknya penjumlahan dan perkalian yang diperlukan untuk komputasi DFT satudimensi 2N melalui algiritma FFT.
6.7
TRANSFORMASI KOSINUS DAN SINUS DISKRET
Diberikan cuplikan masukan N yakni x(0), x(1), x(2), ..., x(N-1), maka transformasi kosinus diskret (DCT : Discrete cosine transform) di definisikan sebagai : y(k) = α(k)
N −1
⎛ π (2n + 1)k ⎞ ⎟, 2N ⎠
k = 0, 1, 2, …, N-1
(6.63)
⎛ π (2n + 1)k ⎞ ⎟, 2N ⎠
n = 0, 1, 2, …, N-1
(6.64)
∑ x(n) cos ⎜⎝ n =0
dan invers dari DCT tersebut diberikan oleh : N −1
x(n) =
∑α (k ) y(k ) cos ⎜⎝ k =0
di mana :
α(k)
=
1 , untuk k = 0, dan N
=
2 , untuk k ≠ 0. N
Dalam bentuk vector transformasi tersebut diberikan oleh di mana elemen-elemen matrik C diberikan oleh : C(n,k) = =
1 N
y = CT x
, k = 0, 0 ≤ n ≤ N-1
2 ⎛ π (2n + 1)k ⎞ cos ⎜ ⎟ , 1 ≤ k ≤ N-1, 0 ≤ n ≤ N-1. N 2N ⎝ ⎠
Matrik C memiliki elemen-elemen riil, dan mudah dilihat bahwa ia ortogonal, C-1 = CT. DCT 2-D merupakan transformasi yang dapat dipisah dan didefinisikan sebagai : Y = CT X C,
X = C Y CT
(6.65)
Transformasi sinus diskret (DST : Discrete Sine Transform) didefinisikan melalui matrik transformasi S(k,n) =
2 ⎛ π (k + 1)(n + 1) ⎞ sin ⎜ ⎟; N +1 N +1 ⎠ ⎝
dan ia juga merupakan transformasi orthogonal.
k, n = 0, 1, 2, …, N-1
6.8
TRANSFORMASI HADAMARD
Transformasi Hadamard dan transformasi Haar memberikan keuntungan komputasi yang serius dari transformasi DFT, DCT, dan DST. Matrik unitary-nya terdiri dari ±1 dan transformasi tersebut dihitung melalui penjumlahan dan pengurangan saja, tanpa memuat perkalian. Sehingga diperoleh penghematan yang mendasar terhadap operasi yang menghabiskan waktu ketika prosesor melakukan perkalian. Matrik unitary Hadamard orde n adalah matrik NxN, N = 2n, dihasilkan dari aturan iterasi berikut : Hn = H1 ⊗ Hn-1
(6.66)
di mana: H1 =
1 ⎡1 1 ⎤ ⎢ ⎥ 2 ⎣1 − 1⎦
(6.67)
dan ⊗ menyatakan hasil kali Kronecker dari dua matrik : ⎡ A(1,1) B A⊗B = ⎢ . ⎢ ⎢⎣ A( N ,1) B
A(1, N ) B ⎤ ⎥ . . . ⎥ A( N ,2) B . A( N , N ) B ⎥⎦ A(1,2) B
.
di mana A(i,j) adalah elemen-elemen (i,j) dari A; i,j = 0, 1, 2, …, N. Kemudian sesuai dengan (6.66) dan (6.67) diperoleh : 1 1⎤ ⎡1 1 ⎢1 − 1 1 − 1⎥ 1 ⎢ ⎥ H2 = H1 ⊗ H1 = 2 ⎢1 1 − 1 − 1⎥ ⎢ ⎥ ⎣1 − 1 − 1 1 ⎦ dan untuk n = 3 H3 = H1 ⊗ H2 =
1 ⎡H 2 ⎢ 2 ⎣H 2
H2 ⎤ . − H 2 ⎥⎦
Tidak sulit untuk menunjukkan ortogonalitas dari Hn, n = 1, 2, 3, ... yaitu bahwa H n−1 = H nT = Hn. Untuk sebuah vektor x dari N cuplikan dan N = 2n pasangan transformasinya adalah
y = Hn x,
x = Hn y
(6.68)
Transformasi Hadamard 2-D ditentukan dengan : Y = H n X H n,
X = H n Y Hn .
Transformasi Hadamard memiliki keuntungan terhadap sifat pengemasan energinya sangat baik.
(6.69)
6.9
TRANSFORMASI HAAR
Titik awal pendefinisian untuk transformasi Haar adalah hk(z), yang ditentukan dalam interval tertutup [0,1]. Orde k dari fungsi diuraikan secara unik ke dalam dua bilangan integer p, q k = 2p + q – 1, di mana :
dan L = 2n.
k = 0, 1, 2, ..., L-1,
0 ≤ p ≤ n-1, 0 ≤ q ≤ 2p untuk p ≠ 0 dan q = 0 atau 1 untuk p = 0.
Tabel 6.1 merangkum masing-masing nilai pada L = 8. Fungsi Haar tersebut adalah 1
h0(z) ≡ h00(z) =
L
z ∈ [0,1]
,
(6.70)
q −1 q −1 / 2 ≤ z < 2p 2p L q 1 q −1 / 2 -2p/2, ≤ z< p = p 2 2 L = 0 untuk yang lain di dalam [0,1]. 1
hk(z) ≡ hpq(z) =
2p/2,
(6.71)
Tabel 6.1. Parameter-parameter untuk Fungsi Haar k p q
0 0 0
1 0 1
2 1 1
3 1 2
4 2 1
5 2 2
6 2 3
7 2 4
Matrik transformasi Haar orde L terdiri dari baris-baris yang dihasilkan fungsi sebelumnya yang terhitung pada titik-titik z = m/L, m = 0, 1, 2, ..., L-1. Sebagai contoh matrik transformasi 8 x 8 adalah
H =
⎡ ⎢ ⎢ ⎢ ⎢ 1 ⎢ 8 ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣
1 1 2
1 1 2
1 1
1 1
1 −1
1 −1
1 −1
− 2
− 2
0
0
0
2
2
− 2
0
0
0
0
2 0
−2 0
0 2
0 −2
0 0
0 0
0 0
0
0
0
0
2
−2
0
0
0
0
0
0
0
2
1 ⎤ − 1 ⎥⎥ 0 ⎥ ⎥ − 2⎥ 0 ⎥ ⎥ 0 ⎥ 0 ⎥ ⎥ − 2 ⎥⎦
(6.72)
Tidak sulit untuk melihat bahwa H-1 = HT, yakni H adalah ortogonal. Sifat kemasan energi dari transformasi Haar tidak sangat baik. Transformasi Haar tersebut digunakan sebagai kendaraan untuk mendapatkan dari dunia transformasi unitary hingga analisis multi-resolusi.
6.10 REVISIT PENGEMBANGAN HAAR Split (bagi) set asal dari sampel-sampel input N (N genap) x(0), x(1),...,x(N-1) menjadi dua bagian suksesif yaitu, (x(2k), x(2k+1)), k= 0, 1,..., -1, dan gunakan transformasi Haar pada L=2. Pasangan sampelsampel yang ditransformasi adalah sebagai berikut. , k=0, 1,...,
(6.73)
Yaitu, (6.74) , k=0, 1,...,
(6.75)
Dapat diinterpretasikan dengan N sampel input pada dua filter nonkausal dengan respon impuls (h1(0)=
,h1(-1)=
) dan h0(0)=
,h0(-1)=-
secara respektif. Fungsi transfernya adalah sebagai berikut. (6.76) (6.77)
Dengan kata lain, pada L=2, transformasi Haar menghitung sampel-sampel output pada kedua filter ketika diumpankan dengan input sequence x(n), n=0,1,2,...,N-1.
(a)
(b) Gambar 6.4. (a) Operasi subsampling dan (b) Interpretasi pemfilteran transformasi Haar.
(6.78)
Dengan operasi subsampling pada cabang yang lebih rendah setelah filter H0 dan H1, identitas Nobel diarahkan menjadi:
(6.79)
Gambar 6.5. Pemfilteran dua tingkat yang diikuti dengan operasi subsampling
(6.80) Dari fungsi transfer diatas dan mengambil operasi subsampling 4 (2x2), dua sampel pertama dari y1(k) diberikan dengan.
(6.81)
Kemudian di-split satu langkah berikutnya sebagai:
(a)
(b) Gambar 6.6. (a) Identitas Nobel I dan (b) equivalent bank filter dari Gambar 6.5.
Gambar 6.7. Bank filter tiga-struktur Berdasarkan Gambar 6.7, menunjukkan bahwa
(6.82)
Dan
(6.83)
Persamaan ini merupakan hasil pada baris kedua dan pertama dari transformasi Haar pada vektor input. Gambar 6.7 menunjukkan (tiga-tingkat) struktur pohon bank filter yang dibangkitkan dari H0(z) dan H1(z). Gambar 6.8 menunjukkan respon-respon frekuensi dari kedua filter tersebut.
Gambar 6.8. Magnitude dari respon frekuensi untuk dua filter Haar. H1 adalah lowpass dan H0 adalah highpass.
6.11 DISKRETE TIME WAVELET TRANSFORM (DTWT)
(a)
(b) Gambar 6.9. Respon frekuensi ideal untuk (a) low-pass dan (b) high-pass filter.
Kasus Dua Band Melihat dari kasus sederhana dua-band pada Gambar 6.4b, dimana sekarang dapat diasumsikan bahwa filter-filter bukan hanya Haar saja. Jika h0(k), h1(k) adalah respon impulse respektif, maka kemudian dapat ditulis:
Dimana y1(k) adalah output dari cabang yang lebih rendah pada Gambar 6.4b. Dengan mengumpulkan y0(k), y1(k), k=0, 1, 2,..., dalam bentuk vektor didapat:
(a)
Gambar 6.10. Tiga-struktur bank filter sintesis
Y=Tix
(6.84)
Dapat diasumsikan bahwa filter-filter itu dapat berupa nonkausal, dan merupakan juga Finite Impulse Response (FIR). Ti pada dasarnya terdiri dari dua baris, satu dengan respon impuls dari H0 dan yang lainnya dengan H1. Gambar 6.10b menunjukkan struktur kombinasi dari y0(k), y1(k), melalui filter G0, G1 untuk membentuk sequence . Simbol input dari filter-flter menunjukkan upsampling dengan M operasi, yang didefinisikan pada Gambar 6.10a. pada kasus ini M=2. Dengan kata lain ekuivalen dengan M-1 bernilai nol diantara dua sampel. Input sequence dari filter G0, G1 akan menjadi: ...0 y0(0) 0 y0(1) 0 y0(2) 0... ...0 y1(0) 0 y1(1) 0 y1(2) 0... Dan
Filter Gi diketahui sebagai filter sintesis dan koresponding Hi, dari Gambar 6.4b, sebagai filter analisis. Dengan mengumpulkan (n) bersama-sama, dapat dilihat bahwa:
Atau =T0y
(6.85)
Dengan =x dapat diberikan [Vett 92] T0 Ti = I = Ti T0
(6.86)
Dengan mengalikan Ti dengan kolom T0, persamaan ekuivalen dengan:
, i,j = 0, 1
(6.87)
Atau berdasarkan pada definisi dari inner product dalam (6.58), (hi(2k-n),gj(n-2l))=δklδij
Bisa dikatakan bahwa bank filter dua-band adalah rekunstruksi sempurna dan (n)=x(n), maka
(6.88)
Persamaan diatas dapat dilihat dari perspektif yang berbeda. Sebuah perluasan dari x(n) ke sekuen basis {g0(n-2k),g1(n-2k)}, k Є Z Dimana Z adalah himpunan dari bilangan bulat. Dari berbagai sudut pandang y0(k), y1(k) adalah masingmasing koefisien perluasan. Hal ini dikenal sebagai waktu diskrit transformasi wavelet (DTWT) dan koefisien y0(k), y1(k) sebagai waktu diskrit koefisien wavelet. Jadi, diberi rekonstruksi yang sempurna duaband Filter bank (sebagai contoh pada kondisi (6,87)) pasangan transformasi berikut didefinisikan
(6.89)
Keterangan Dua set fungsi dasar yang hi (2k - n) ≡ Øik (n), gj(n – 2l) ≡ ψjl (n) i, j = Persamaan (6.87) adalah kondisi ortogonal antara Øik (n) dan ψjl (n), yaitu,
0,
terlibat, 1 dan k,
l
yaitu Є Z
(Øik (n), ψjl (n) = δklδij dan dikenal sebagai kondisi biorthogonality. Wavelet waktu diskrit mengubah pasangan pada (6.89) adalah ekspansi biorthogonal. Urutan dasar Øik (n) dan ψjl (n) dari ekspansi tersebut adalah menyusun jumlah sampel genap sebanyak empat urutan dasar sekuen g0(n), g1 (n), h0 (-n), hl (- n), yang merupakan respon impuls sintesis dan filter analisis time-reversed. Untuk pemulihan x (n) dari koefisien wavelet waktu diskritnya, setiap koefisien yi(k) membobot dan menambahkan salinan sekuen gi(n) digeser oleh 2k. Ketika urutan Øik (n) = hi(2k - n) itu sendiri ortogonal, yaitu.
, i,
j = 0, 1 dan k, l Є Z
Kemudian gi(n) = hi(n) hl (0) hl (1) hl (2) hl (3) hl (4) hl (5) hl (6) hl (7) hl (8) hl (9)
0.4829629 0.8365163 0.2241439 -0.1294095
0.33267 0.806891 0.459877 -0.135011 -0.08544 0.03522
0.2303778 0.7148466 0.6308808 -0.0279838 -0.1870348 0.0308414 0.0328830 -0.0105974
0.1601024 0.6038293 0.7243085 0.1384281 -0.2422949 -0.0322449 0.0775715 -0.006241 5 -0.0125807 0.0033357
Artinya, filter sintesis adalah membalikkan waktu dari filter analisis yang lainnya. Seperti halnya bank filter dikenal sebagai ortogonal atau paraunitary, dan memiliki set yang sama untuk sekuen (hi saja) yang terlibat dalam kedua persamaan transformasi wavelet waktu diskrit (6.89). Sejumlah orthogonal dan rekonstruksi yang sempurna biorthogonal pasang filter telah diusulkan dalam literatur, [Daub 90, Vett 95]. Tabel 6.2 memberikan koefisien untuk empat pertama filter Daubechies ortogonal maksimal datar. Versi low-pass h1 (n) ditampilkan. Versi tinggi-pass diperoleh sebagai h0 (n) = (-l)n hl (-n +2L - l), dimana L adalah panjang dari filter. Selain kasus urutan dasar wavelet dengan nilai-nilai yang telah ditetapkan, besar upaya penelitian telah dikhususkan untuk membangun urutan seperti yang dioptimalkan untuk masalah tertentu yang menarik. Ini juga telah digunakan dalam aplikasi pengenalan pola. Misalnya, dalam [Mall 97] diusulkan untuk merancang filter bank untuk mengoptimalkan kelas kriteria diskriminan. Pendekatan yang lain diikuti pada [Szu 92] mana kombinasi linear optimal basis standar dicari untuk klasifikasi sinyal suara. Ketika menerapkan filter bank dalam praktek, filter noncausal harus menunda tepat untuk membuatnya terealisasi (Lampiran D). Hal inimenjadikan penting diperlukan untuk melibatkan unsur-unsur penundaan tertentu pada titik-titik yang berbeda, dalam rangka menjaga properti rekonstruksi sempurna dari bank analisis-sintesis (Soal 6.19). Dalam prakteknya, jumlah sampel input x (n) terbatas, yaitu, n = 0, 1,. . . ,N - 1. Jadi, untuk perhitungan (6.89), beberapa kondisi awal adalah diperlukan. Zero, periodik, atau ekstensi simetris dari data yang populer alternatif. Seperti masalah pelaksanaan serta algoritma untuk efisiensi perhitungan koefisien DTWT yang dibahas dalam [Vett 95, Bab 6].
Gambar 6.11. Tiga-struktur bank filter sintesis
Kasus Banyak Band Gambar 6.11 menunjukkan bagian sintesis sesuai dengan analisis bank pada Gambar 6.7, dan merupakan generalisasi dari konsep sintesis dua-band. Menggunakan identitas Noble yang ditunjukkan pada Gambar 6.12 (Soal 6.17), akhirnya dengan struktur yang setara dengan bagian sintesis, ditunjukkan pada Gambar 6.13. Biarkan fi(n) menjadi tanggapan impuls dari filter Fi. Sangat mudah untuk melihat kontribusi masingmasing urutan yi (k) ke output
(n) adalah
i=0, 1,...,J-2
Gambar 6.12. Bank filter sintesis struktur-pohon Gambar 6.11 menunjukkan sintesis sesuai analisis bank. Gambar 6,7, dan merupakan generalisasi dari konsep sintesis dua-band. Menggunakan Identitas Noble yang ditunjukkan pada Gambar 6.12 (Soal 6.17), Diakhiri dengan struktur ekuivalen dari bagian sintesis yang ditunjukkan pada Gambar 6.13. Biarkan fi (n) menjadi tanggapan impuls dari filter Fi. Sangat Mudah untuk Melihat bahwa masing-masing kontribusi yi (k) ke output
(n) adalah.
Identitas Nobel II
Gambar 6.13. Ekuivalen dari tiga-struktur bank filter dari Gambar 6.11 Rekonstruksi sempurna dari bank filter, yaitu,
(6.90)
Dimana (6.91)
(6.92)
Kemudian dari (6.90), (6.91), dan (6.92) kita mendapatkan Tabel 6.3.
Keterangan Karakteristik terkemuka DTWT adalah bahwa dasar urutan untuk masing-masingi tingkat adalah daya dari 2 shift sekuen yang sesuai urutan
Dari transformasi wavelet kontinyu, semua analisa (sintesis) fungsi dasar yang dihasilkan dari analisis tunggal (sintesis) fungsi sekuen dengan dilasi (skala waktu) dan pergeseran [Meye 93, Daub 90, Vett 95]. Jumlah ajaib 2, yang menentukan pergeseran kekuasaan di dasar urutan sekuen, hasil dari split berturut-turut oleh dua pada struktur pohon bank filter, yang telah didopsi untuk memperkenalkan DTWT tersebut. Bank filter tipe ini dikenal sebagai band oktaf-filter. Karakteristiknya adalah bahwa bandwidth dari masingmasing filter di bank adalah sama dalam skala logaritmik. Kadang-kadang mereka juga disebut konstan-Q bank filter untuk menekankan fakta bahwa rasio bandwidth filter dengan frekuensi masing-masing pusat konstan. Generalisasi dari DTWT dengan M integer yang lain di tempat 2 juga dapat didefinisikan dan digunakan [Stef 93]. Contoh 6.4. Transformasi Haar-Epilog Kita telah melihat bahwa transformasi Haar setara dengan analisis struktur pohon filter bank. Mari kita melihat masalah sintesis. Untuk 8 x 8 Haar mentransformasi dan setelah reshuffle baris dari matriks yang sesuai Haar, didapatkan
Atau
Y= x Dengan demikian transformasi Haar 8 x 8 memberikan empat koefisien pada resolusi terbaik tingkat 0, dua dan tingkat 1, dan satu untuk masing-masing resolusi tingkat 2 dan 3. Kemudian akan desain bank sintesis yang sesuai untuk mendapatkan x (n) dari koefisien ini. Respon impuls dari analisis filter Haar adalah
Dapat dilihat bahwa
Maka filter sintesis dapat didefinisikan sebagai
Maka
Dari ekuivalen struktur bank sintesis dari Gambar 6.13 didapat
Dan respektif respon impuls adalah
Dengan argumen yang sama
Didapat
Atau
6.12 INTERPRETASI MULTIRESOLUSI Tujuan dari bagian ini adalah untuk menyorot, tanpa menggunakan rincian matematika, aspek penting dari transformasi wavelet yang bertanggung jawab atas keberhasilannya sebagai alat dalam pengenalan pola serta berbagai aplikasi lain. Mari kita asumsikan untuk kesederhanaan bahwa dua filter di bank analisissintesis dari filter bank paraunitary yang ideal. Gambar 6.14 menunjukkan besarnya respon dari filter masing-masing dalam ekuivalen dari band oktaf filter bank struktur-pohon dari Gambar 6.13. Lebar respon frekuensi (bandwidth) yang dibelah dua untuk setiap tingkat pohon (Gambar 6.14d). Artinya, "detail" resolusi (high-pass) filter memiliki bandwidth yang lebar dan "kasar" resolusi (low-pass) filter adalah dari bandwidth sempit. Filter F3 dan F2, dua resolusi kasar, dari bandwidth yang sama. Pengamatan ini adalah benar untuk setiap band oktaf bank filter sejumlah tingkat J. Artinya, lebar Fi (z) adalah setengah dari lebar Fi - 1 (z) dan lebar dari FJ-2 dan F J - 1 adalah sama.
Gambar 6.14. Bandwidth filter dalam filter band oktaf Transformasi wavelet menyediakan sarana menganalisa sinyal input menjadi beberapa tingkat resolusi yang berbeda secara hirarkis. Ini juga dikenal sebagai analisis multiresolusi. Dengan demikian, komponen sinyal yang berbeda sesuai dengan kegiatan fisik dapat diwakili menjadi yang terbaik pada tingkat resolusi yang berbeda: kegiatan frekuensi tinggi pendek pada resolusi yang lebih baik dan panjang frekuensi rendah yang berada di tingkat resolusi tersebut. Pada bagian sintesis, sinyal dapat direkonstruksi dari komponen multiresolusinya. Lihat, sebagai contoh, Gambar 6.13. Urutan x (n) disintesis pertama oleh komponen kasar nya x3 (n) dan kemudian frekuensi lebih tinggi (rinci) komponen ditambahkan, sehingga pendekatan yang berturut-turut lebih halus. Ketika komponen dari detail terbaik, x0 (n), ditambahkan, sinyal asli diperoleh. Filosofi ini adalah inti dari sejumlah skema kompresi sinyal.
Keterangan Analisis sinyal di sejumlah komponen melalui bank filter adalah tidak baru dan kembali ke pekerjaan Gabor di tahun 1940-an. Hal tersebut terkait langsung ke Transformasi Fourier waktu pendek didefinisikan sebagai [Gabo 46 Vett 95]
(6.93)
dimana θ (n) adalah urutan jendela, yang pusatnya adalah berturut-turut pindah ke m poin yang berbeda. Jadi, setiap kali, bagian dari urutan x (n) sekitar m (tergantung lebar efektif jendela) dipilih dan ditransformasi Fourier. Hal ini dapat menunjukkan bahwa ini setara dengan menyaring sinyal x (n) dengan bank filter, masing-masing berpusat pada frekuensi yang berbeda tetapi semua dari mereka memiliki bandwidth yang sama (Soal 6.20). Ini adalah kelemahan, karena komponen sinyal frekuensi rendah dan tinggi adalah "tampak" melalui jendela dalam waktu yang sama. Apa yang sebenarnya dibutuhkan adalah jendela panjang untuk menganalisis perlahan waktu bervariasi komponen frekuensi rendah dan jendela sempit untuk mendeteksi frekuensi tinggi kegiatan waktu-pendek. Seperti kita lihat, dari sebuah band oktaf bank filter struktur-pohon, terkait dengan DTWT tersebut. Dapat dikatakan tentang transformasi wavelet dan analisis multiresolusi adalah hanya sekilas cerita dari keseluruhan, cerita yang benar-benar layak dilihat lebih lanjut, pada [Daub 90].
6.13 PAKET-PAKET WAVELET DTWT ini telah diperkenalkan melalui band filter bank-oktaf, dan koefisien wavelet hasil pada output bank, ketika masukannya diumpankan dengan sinyal yang menarik. Band oktaf filter bank dibangun berturut-turut oleh dua pita frekuensi terendah dari bank struktur-pohon (Gambar 6.7). Namun, ada banyak kasus di mana sebagian besar kegiatan tersebut tidak ada di band frekuensi rendah tapi di bagian tengah frekuensi tinggi atau spektrum. Dalam kasus, mungkin berguna untuk dapat menempatkan frekuensi bandwidth yang lebih halus dalam band dimana kegiatan tersebut terjadi. Sebagaimana akan kita lihat nanti dalam bab ini, hal ini dapat meningkatkan kekuatan diskriminatif sistem dari sudut pandang klasifikasi. Gambar 6.15a menunjukkan contoh bank filter struktur-pohon dengan membelah frekuensi halus yang terjadi pada band frekuensi tengah. Gambar 6.15b menunjukkan bandwidth yang dihasilkan untuk masingmasing filter (ideal) di bank (f-axis) dan panjang jendela masing-masing tanggapan impuls dalam domain waktu (n-sumbu). Dengan kata lain, filter 2 dan 3 memiliki setengah bandwidth dan dua kali respon impuls 4. Selain itu, mereka memiliki satu keempat bandwidth dan impuls respon empat kali lebih lama daripada 1. Sebagai perbandingan, Gambar 6.16 menunjukkan frekuensi-waktu resolusi plot untuk band-oktaf filter bank (a) dan untuk sebuah bank dengan bandwidth yang sama (b), terkait dengan DTWT dan transformasi Fourier waktu singkat, masing-masing. Setelah membebaskan diri dari band-oktafstruktur-pohon, bank filter dapat dibangun oleh berbagai strategi pertumbuhan pohon, dengan Gambar 6.15 yang hanya satu kemungkinan. Seperti halnya dengan filosofi-band oktaf, struktur-struktur pohon juga mengakibatkan satu set urutan dasar untuk perluasan sinyal diskrit [Coif 92] disebut paket wavelet.
6.14 PANDANGAN GENERALISASI DUA-DIMENSI Semua konsep yang dibahas sejauh ini dapat dipindahkan ke dalam kasus dua dimensi. Bagaimana seseorang bisa mendefinisikan subsampling di sini? Cara langsung adalah melalui filosofi "terpisah". Artinya, pertama-tama kita mengubah (filter) kolom di urutan dua dimensi dan kemudian dihasilkan baris. Ini mengarah pada subsampling yang ditunjukkan pada Gambar 6.17. Dengan kata lain, kita meninggalkan setiap baris yang lain dan setiap kolom lainnya (untuk subsampling oleh 2). Gambar 6.18 menunjukkan struktur Filter bank yang sesuai. Urutan gambar (m, n) muncul dalam filter kolom tahap 1 setelah kolom dan output masing-masing di subsampel oleh 2. gambar yang dihasilkan subsampel pada gilirannya disaring pada tahap dua, yang sebelumnya dimasukkan ke dalam filter baris demi baris.
Gambar 6.15. Struktur-pohon paket wavelet Dengan asumsi H0 menjadi filter high-pass dan H1 low-pass, empat frekuensi band yang dibentuk oleh prosedur sebelumnya diilustrasikan dalam Gambar 6.19a. Kawasan H1 H1 sesuai dengan kolom low-pass dan baris, H1 Ho untuk kolom low-pass dan baris high-pass, dan sebagainya. Gambar 6.19b menunjukkan hasil segmentasi dari domain frekuensi ketika daerah low-pass H1 H1 adalah berturut split dengan mengulangi prosedur.
Gambar 6.16. Frekuensi versus resolusi waktu untuk (a) band-oktaf dan (b) bandwidth bank filter yang sama
Gambar 6.17. Jarak subsampling 2 untuk gambar
Contoh 6.5. Gambar 6.20 menunjukkan gambar 64 x 64 dari segitiga. Tiga "baris" gambar adalah 32 x 32 gambar yang dihasilkan ketika melewati gambar segitiga melalui struktur Gambar 6.18. Dalam penyaringan kolom tahap pertama garis vertikal berjalan melalui low-pass filter H1 (tidak ada variasi di atasnya) dan garis horizontal dan diagonal melalui high-pass H0. Hal ini karena dalam penyaringan kolom ini muncul sebagai impuls di masing-masing kolom, sehingga kaya pada frekuensi tinggi. Dalam baris scanning tahap kedua garis horizontal yang akan melalui low-pass filter. penalaran serupa menjelaskan posisi berbagai bagian segitiga dalam band yang berbeda. Meskipun ini jelas merupakan contoh yang sangat sederhana, sangat instruktif. Ini menunjukkan bagaimana gambar asli dapat diperoleh dari komponen multiresolusi dan juga bagaimana karakteristik yang berbeda (arah dalam kasus ini) dari keseluruhan dapat diisolasi di band berbeda.
Gambar 6.18. Elemen dasar untuk bank filter dua dimensi
Gambar 6.19. (a) divisi domain frekuensi (b) hasil divisi suksesif low-pass
Gambar 6.20. Gambar segitiga dan versi yang terfilter
6.15 APLIKASI Pengenalan Karakter tulisan tangan Gambar 6.21 menunjukkan karakter "3" serta kontur batasnya setelah penerapan algoritma kontur melacak [Pita 92], sekarang menjadi tugas salah satu bentuk pengalan. Seperti dijelaskan secara lebih rinci dalam Bab 7, batas dapat direpresentasikan sebagai kurva parametrik tertutup dalam bidang kompleks (6.94) dengan N adalah jumlah sampel (piksel) menelusuri kontur dan x (n), y (n) yang sesuai koordinat. Titik pertama (x (0), y (0)) dari urutan dianggap sebagai asal.
Gambar 6.21. Koefisien wavelet untuk kurva batas karakter 3
Klasifikasi Tekstur
Gambar 6.22. (a) contoh gambar tekstur (b) transformasi paket wavelet
REFERENCES [Akan 93] Akansu A.N., Hadda R.A. Multiresolution Signal Decomposition, Academic Press, 1992. [Arbt 90] Arbter K., Snyder W. E., Burkhardt H., Hirzinger G “Application of affineinvariant Fourier descriptors to recognition of 3-D objects,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12(7), pp. 640-647, 1990. [Atti 92] Attick J.J. “Entropy minimization: A design principle for sensory perception,” International Journal of Neural Systems, Vol. 3, pp. 81-90, 1992. [Barl 89] Barlow H.B. “Unsupervised learning,” Neural Computation, Vol. 1, pp. 295-3 11, 1989. [Bell 00] Bell A.J. “Information theory, independent component analysis, and applications,” in Unsupervised Adaptive Filtering, Part I: Blind Source Separation (Haykin S., ed.), pp. 237-264, John Wiley & Sons, 2000. [Bovi 90] Bovic A.C., Clark M., Geisler W.S. “Multichannel texture analysis using localized spatial filters,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12fl), pp. 55-73, 1990. [Bovi 91] Bovic A.C. “Analysis of multichannel narrow-band filters for image texture segmentation,” IEEE Transactions on Signal Processing, Vol. 39(9), pp. 2025-2044, 199 I. [Brod 66] Brodatz P. Textures: A Photographic Album for Artists and Designers, Dover, New York, 1966. [Burt 83] Burt P.J., Adelson E.H. “The Laplacian pyramid as a compact image code,” IEEE Transactions on Communications, Vol. 31(4), pp. 532-540, 1983. [Camp 66] Campell E, Kulikowski J. “Orientation selectivity of the human visual system,” Journal of Physiology, Vol. 197, pp. 4 3 7 4 1 , 1966. [Camp 68] Campell E, Robson J. “Application of Fourier analysis to the visibility of gratings,” Journal of PhysiuZugy, Vol. 197, pp. 55 1-566, 1968. [Chan 93] Chang T., Kuo C.C.J. “Texture analysis and classification with tree structured wavelet transform,” IEEE Transactions on Image Processing, Vol. 2(4), pp. 429-442, 1993. [Chua 96] Chuang GC.H., Kuo C.C.J. “Wavelet descriptor of planar curves: Theory and applications,” IEEE Transactions on Image Processing, Vol. 5( l), pp. 56-71, 1996. [Coif 92] Coifman R.R., Meyer Y., Wickerhauser M.V. “Wavelet analysis and signal processing,” in Wavelets and Their Applications (Ruskai M.B. et al. eds.), pp. 153-178, Jones and Barlett, 1992.
[Como 94] Comon P. “Independent component analysis-A new concept?’ Signal Processing, Vol. 36, pp. 287-314, 1994. [Crim 82] Crimmins T.R. “A complete set of Fourier descriptors for two dimensional shapes,” IEEE Transactions on Systems, Man Cybernetics, Vol. 12(6), pp. 848-855, 1982. [Daub 90] Daubechies I. Ten Lectures on Wavelets, SIAM, Philadelphia, 1991. [Daug 85] Daugman J.G “Uncertainty relation for resolution in space, spatial frequency. and orientation optimized by two dimensional visual cortical filters,” Journal of Optical Society ofAmerica, Vol. 2, pp. 1160-1.169, 1985. [Deco 95] Deco G, Obradovic D. “Linear redundancy reduction learning,” Neural Networks, Vol. 8(5), pp. 751-755, 1995. [Diam 96] Didmantaras K.I.. Kung S.Y. Principal Componenr Neural Nefworks, John Wiley, 1996. [Doug 00] Douglas S.C., Amari S. “Natural gradient adaptation,” in Unsupervised Adaptive Filtering, Part I: Blind Source Separation (Haykin S. ed.), pp. 13-61, John Wiley & Sons, 2000. [Este 77] Esteban D., Galand C. “Application of quadrature mirror filters to split band voice coding schemes,” Proceedings of the IEEE Conference on Acoustics Speech and Signal Pmcesing, pp. 191195, May 1977. [Fie194] Field D.J. “What is the goal of sensory coding?’ Neural Computation, Vol. 6, pp. 559-601,1994. [Flan 72] Flanagan J.L. Speech Analysis, Synthesis and Perception, Springer Verlag, New York, 1972. [Gabo 46] Gabor D. “Theory of communications,” Journal of the Institute of Elec. Eng., Vol. 93, pp. 429457,1946. [Geze 00] Gezerlis V., Theodoridis, S. “An optical music recognition system for the notation of Orthodox Hellenic Byzantine music,” Proceedings of the International Conference on Pattern Recognition (ICPR), Barcelona, 2000. [Geze 02] Gezerlis V., Theodoridis S. “Optical character recognition of the Orthodox Hellenic Byzantine music,” Pattern Recognition, Vol. 35(4), pp. 895-914,2002. [Hale 95] Haley G., Manjunath B.S. “Rotation-invariant texture classification using modified Gabor filters,” IEEE International Conference on Image Processing, pp. 262-265, 1995. [Hale 99] Haley G., Manjunath B.S. “Rotation-invariant texture classification using complete space frequency model,” IEEE Transactions on Imuge Prucessing, Vol. 8(2), pp. 255-269, 1999. [Hayk 99] Haykin S. Neural Networks-A Comprehensive Foundation, 2nd edition, Prentice Hall, 1999. [Hayk 00] Haykin S. (ed.) Unsupervised Adaptive Filtering, Part I: Blind Source Separtion, John Wiley & Sons, 2000. [Hube 85] Huber P.J. “Projection pursuit,” The Annals of Statistics, Vol. 13(2), pp. 435- 47S, 1985. [Hui 96] Hui Y., Kok C.W., Nguyen T.Q. “Theory and design of shift invariant filter banks,” Proceeding of IEEE TFTS’96, June 1996. [Hyva 01] Hyvarien A., Karhunen J., Oja E. Independent Component Analysis, Wiley Interscience, 2001. [Jain 89] Jain A.K. Fundamentals of Digital Image Processing, Prentice Hall, 1989. [Jain 91] Jain A.K., Farrokhnia E “Unsupervised texture segmentation using Gabor filters,” Pattern Recognition, Vol. 24(12), pp. 1167-1 186, 1991. [Jone 87] Jones M.C., Sibson R. “What is projection pursuit?’ Journal of the Royal Statistical Society, Ser. A, Vol. 150, pp. 1-36, 1987. [Jutt 91] Jutten C., Herault J. “Blind separation of sources, Part I: An adaptive algorithm based on neuromimetic architecture,” Signal Processing, Vol. 24, pp. 1-10, 1991. [Kapo 96] Kapogiannopoulos G, Papadakis M. “Character recognition using biorthogonal discrete wavelet transform,” Proceedings of the 41st annual SPIE meeting, Vol. 2825, August 1996. [Koho 89] Kohonen T. Self-organization and Associative Memory, 3rd ed., Springer Verlag, 1989. [Lain 93] Laine A,, Fan J. “Texture classification by wavelet packet signatures,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 15( 1 I), pp. 11 86-1191, 1993.
[Lain 96] Laine A,, Fan J. “Frame representations for texture segmentation,” IEEE Transcaction on Image Processing, Vol. 5(5), pp. 771-780, 1996. [Lee 98] Lee T.-W. Independent ComponentAnalysis, Kluwer Academic Publishers, 1998. [Levi 85] Levine M.D. Vision in Man and Machine, McGraw-Hill, New York, 1985. [Lim 90] Lim J.S. Two-Dimensional Signal Processing, Prentice Hall, 1990. [Mall 89] Mallat S. “Multifrequency channel decompositions of images and wavelet models,” IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. [Mall 97] Mallet Y., Coomans D., Kautsky J., De Vel 0. “Classification using adaptive wavelets for feature extraction,” IEEE Transactionsfor Pattern Analysis and Machine Intelligence, Vol. 19(10), pp. 10581067, 1997. [Marco 95] Marco S.D., Heller P.N., Weiss J. “An M-band two dimensional translationinvariant wavelet transform and its applivations,” Proceedings of the IEEE Conference on Acoustics Speech and Signal Processing, pp. 1077-1080, 1995. 37(12), pp. 2091-2110,1989. [Meye 93] Meyer Y. Wavelets, Algorithms and Applications, SIAM, Philadelphia, 1993. [Mojs 00] Mojsilovic A,, Popovic M.V., Rackov D.M. “On the selection of an optimal wavelet basis for texture characterization,” IEEE Transactions Image Processing, Vol. 9( 12), 2000. [Nach 75] Nachmais J., Weber A. “Discrimination of simple and complex gratings,’’ Vision Research, Vol. 15, pp. 217-223, 1975. [Oja 83] Oja E. Subspace Methods for Pattern Recognition, Letchworth, U.K.: Res. Studies Press, 1983. [Papo 91] Papoulis A. Probability, Rundom Variables, and Stochastic Processes, 3rd ed., McGraw-Hill, 1991. [Pich 96] Pichler O., Teuner A., Hosticka, B. “A comparison of texture feature extraction using adaptive Gabor filtering, pyramidal and tree structured wavelet transforms.’‘ Partern Recognition, Vol. 29(5), pp. 733-742, 1996. [Pita 92] Pitas I. Digital Image Processing Algorithms, Prentice Hall, 1992. [Prak 97] Prakash M., Murty M.N. “Growing subspace pattern recognition methods and their neural network models,” IEEE Transactions on Neural Networks, Vol. 8( 1). pp. 161-168, 1997. [Proa 92] Proakis J., Manolakis D. Digital Signal Processing, 2nd ed., Macmillan, 1992. [Stef 93] Steffen P., Heller P.N., Gopinath R.A., Burms C.S. “Theory of regular M-band wavelet bases,” IEEE Tansactions on Signal Processing, Vol. 41 (1 2), pp. 3497-35 1 1, 1993. [Stra 80] Strang G Linear Algebra and its Applications, 2nd ed., Harcourt Brace Jovanovich, 1980. [Szu 92] Szu H.H., Telfer B.A., Katambe S. “Neural network adaptive wavelets for signal representation and classification,” Optical Eng., Vol. 31, pp. 1907-1916, 1992. [Turn 86] Turner M.R. “Texture discrimination by Gabor functions,” Biol. Cybern., Vol. 55, pp. 71-82, 1986. [Unse 86] Unser M. “Local linear transforms for texture measurements,” Signal Processing, Vol. 11( I), pp. 61-79, 1986. [Unse 89] Unser M., Eden M. “Multiresolution feature extraction and selection for texture segmentation,” IEEE Transations on Pattern Analysis and Machine intelligence, Vol. 11(7), pp. 717-728, 1989. [Unse 95] Unser M. ‘Texture classification and segmentation using wavelet frames,” IEEE Transactions on Image Processing, Vol. 4(11), pp. 1549-1560, 1995. [Vaid 93] Vaidyanathan P.P. Multirate Systems and Filter Banks, Prentice Hall, 1993. [Vett92] Vetterli M., Herley C. “Wavelets and filter banks: Theory and design,” IEEE Transactions on Signal Processing, Vol. 0(9), pp. 2207-2232, 1992. [Vett 95] Vetterli M., Kovacevic J. Wavelets and Subband Coding, Prentice Hall, 1995. Pata731 Watanabe S., Pakvasa N. “Subspace method in pattern recognition,” Proceedings of the International Joint Conference on Pattern Recognition, pp. 25-32, 1973. [Weld96] Weldon T., Higgins W., Dunn D. “Efficient Gabor filter design for texture segmentation,” Pattern Recognition, Vol. 29(2), pp. 2005-2025, 1996.
