BAB 8 PENCOCOKAN TEMPLATE Anggun Fitrian Isnawati, 06244-S2 TE Sulistyaningsih, 05912-S2 TE Rintania Elliyati Nuryaningsih, 06245-S2 TE Jurusan Teknik Elektro Teknologi Informasi FT UGM, Yogyakarta
8.1 PENDAHULUAN Pada bab-bab sebelumnya, tugas dan perhatian utama menunjuk pada pola yang tidak dikenal ke salah satu kelas yang mungkin. Permasalahan yang akan selalu ada dalam bab ini adalah sifat yang sedikit berbeda. Anggap saja bahwa satu set referensi pola (template) disediakan bagi kita dan kita harus memutuskan mana salah satu dari pola referensi ini yang tak dikenal (pola pengujian) yang paling cocok. Template ini memungkinkan objek tertentu berada dalam sebuah tempat atau dapat berbentuk string pola, seperti halnya kata pembentuk surat dalam teks tertulis atau kata-kata atau frasa dalam teks lisan. Biasanya, beberapa masalah timbul dalam pengenalan suara, dalam otomasi penggunaan visi robot, dalam estimasi gerakan untuk pengkodean video, dan dalam sistem temu kembali (retrieval) database citra, dan lain sebagainya. Langkah pertama yang mungkin dilakukan untuk pendekatan tugas tersebut adalah untuk menentukan ukuran atau biaya pengukuran “jarak” atau “kesamaan” antara pola referensi (yang dikenal) dan pola pengujian (yang tidak dikenal), supaya dapat dilakukan operasi pencocokan atau yang dikenal sebagai pencocokan template. Kita tahu sekarang bahwa setiap pola diekspresikan dalam bentuk vektor atau matriks dengan elemen himpunan dari fitur-fitur yang dipilih. Lalu mengapa tidak digunakan salah satu dari ukuran jarak yang sudah diketahui, yaitu, norma Euclidean atau Frobenius, dan melakukan operasi pencocokan berdasarkan jarak minimum? Pemikiran selanjutnya lebih mengungkapkan bahwa sebuah pendekatan langsung tidak cukup dan dibutuhkan sesuatu yang lebih. Inilah poin penting yang membuat pencocokan template berbeda dan juga menarik. Untuk memahami dengan lebih baik, marilah kita mempertimbangkan masalah pencocokan teks tertulis, yaitu bahwa, untuk mengidentifikasi satu dari satu set kata-kata yang tertulis adalah kata, misalnya, “beauty”. Namun, karena kesalahan dalam sensor pembacaan pola pengujian tertentu muncul, misalnya seperti “beety” atau “beaut”. Dalam tugas pengenalan suara, jika kata tertentu yang diucapkan oleh pembicara yang sama beberapa kali, maka akan diucapkan berbeda setiap kali. Kadang-kadang akan diucapkan dengan cepat dan pola yang dihasilkan akan berdurasi singkat, kadang-kadang diucapkan dengan lambat sehingga pola yang dihasilkan akan berdurasi lebih lama. Namun dalam semua kasus itu, kata yang diucapkan adalah “sama” oleh orang yang sama. Dalam penerapan analisis, obyek yang diidentifikasi mungkin berada dalam gambar tertentu namun lokasi dalam gambar tidak diketahui. Dalam sistem temu kembali database citra berbasis konten, query biasanya termasuk bentuk sebuah objek. Bagaimanapun, bentuk yang diberikan oleh pengguna, seringnya, tidak sama persis dengan bentuk benda yang berada dalam database citra. Tujuan utama bab ini adalah untuk menentukan pengukuran yang mengakomodasi karakteristik yang berbeda untuk setiap kategori dari masalah ini. Kita akan mulai dengan permasalahan pencocokan pola string dan akan menuju ke analisis tempat dan kemudian ke masalah pengenalan bentuk. Tugas-tugas, meskipun memiliki tujuan yang sama, membutuhkan alat yang berbeda karena perbedaan alami. 8.2 PENGUKURAN BERDASARKAN TEKNIK PENCARIAN JALUR OPTIMAL Pertama-tama kita fokuskan pada kategori pencocokan template, dimana pola-pola yang terlibat terdiri dari string simbol teridentifikasi atau vektor fitur (pola string). Disini, setiap
referensi dan pola pengujian direpresentasikan sebagai urutan (string) dari parameter yang diukur dan salah satunya harus menentukan urutan referensi dari pola pengujian mana yang paling cocok. Biarkan r(i), i = 1,2,. . . , I, dan t(j), j = 1,2,. . . , J, menjadi urutan vektor fitur masing-masing untuk pasangan tertentu dari referensi dan pola pengujian, dimana pada umumnya I ≠ J. Tujuannya adalah untuk mengembangkan ukuran jarak yang tepat antara dua urutan tersebut. Untuk tujuan ini, dibentuk grid dua dimensi dengan elemen dari dua urutan tersebut sebagai titik pada masing-masing sumbu, yaitu string acuan pada absis (sumbu-i) dan satu titik lagi pada ordinat (sumbu-j). Gambar 8.1 adalah contoh untuk I = 6, J = 5. Setiap titik dari grid (node) menandai korespondensi antara masing-masing elemen dari dua urutan. Sebagai contoh node (3,2) memetakan unsur r (3) ke t (2). Setiap node (i, j) dari grid tersebut terkait dengan biaya, yang merupakan fungsi terdefinisi dengan tepat d (i, j) yang mengukur “jarak” antara elemen masing- masing dari string, t (j) dan r (i). Jalur A yang melalui grid dari node awal (i0, j0) ke node yang terakhir (if, jf) adalah set order dari node, dalam bentuk:
Setiap jalur terkait dengan biaya keseluruhan D didefinisikan sebagai:
dimana K adalah jumlah node di sepanjang jalur. Untuk contoh Gambar 8.1, K = 8.
Gambar 8.1 Setiap titik di sepanjang jalur menandai korespondensi antara masing-masing elemen dari pola pengujian dan referensi.
Biaya keseluruhan sampai dengan node (ik, jk) dinotasikan dengan D (ik, jk) dan dengan konvensi kita asumsikan D (0, 0) = 0 serta d (0, 0) = 0. Jalur dikatakan lengkap jika:
Jarak antara kedua urutan didefinisikan sebagai D minimal dari semua jalur yang mungkin. Pada saat yang sama, jalur biaya minimum menyelesaikan korespondensi pasangan yang optimal antara elemen-elemen dari dua urutan, dimana hal ini merupakan bagian penting, karena dua urutan ini memiliki panjang yang berbeda. Dengan kata lain, prosedur jalur optimal membuat alignment atau warping dari elemen string pengpengujianan ke elemenelemen string referensi, sesuai dengan nilai pencocokan terbaik. Sebelum kita berbicara tentang prosedur optimasi, kita harus mengetahui bahwa ada beberapa variasi dari skema ini. Misalnya, seseorang tidak mungkin memaksakan kendala tertentu memiliki jalur yang lengkap tetapi mungkin dapat mengadopsi lebih lunak kendala-kendala yang dikenal sebagai kendala-kendala titik akhir (end point constrain). Selain itu, orang bisa mengaitkan biaya tidak hanya dengan setiap node tetapi juga dengan masing-masing transisi antar node, membuat transisi lebih mahal daripada yang lain. Dalam beberapa kasus, biaya di sebuah node (ik, jk) juga tergantung pada transisi spesifik, yaitu, dari yang node (ik-1, jk-1) maka node (ik, jk) tercapai. Dengan demikian, biaya d sekarang dari bentuk d (ik, jk│ik-1, jk-1) dan biaya jalur keseluruhan adalah:
Pada beberapa kasus, biaya jalur keseluruhan didefinisikan sebagai perkalian product:
Akhirnya, ada beberapa kasus dimana d dipilih sehingga dibutuhkan biaya maksimal bukannya minimal. Jelas bahwa pada semua variasi kondisi awal yang tepat harus diadopsi. Kita kembali ke masalah optimasi itu sendiri. Untuk memperoleh jalur terbaik, harus dicari semua kemungkinan yang ada dari kombinasi jalur. Namun, ini adalah prosedur komputasi yang mahal. Algoritma pemrograman dinamis berdasarkan prinsip Bellman merupakan alat yang kuat yang akan diadopsi untuk mengurangi kompleksitas komputasi. 8.2.1 Prinsip Optimalisasi Bellman dan Pemrograman Dinamis Biarkan jalur optimal antara node awal (i0, j0) dan node akhir (if, jf) dinotasikan sebagai:
Jika (i, j) adalah note pertengahan antara (i0, j0) dan (if, jf), kita akan menunjukkan kendala jalur optimal melalui (i, j ) sebagai:
Prinsip Bellman menyatakan bahwa [Bell 57]
dimana Ө menunjukkan rangkaian jalur. Dengan kata lain, prinsip Bellman menyatakan bahwa jalur optimal secara keseluruhan dari (i0, j0) ke (if, jf) melalui (i, j) adalah rangkaian jalur optimal dari (i0, j0) ke (i, j) dan jalur optimal dari (i, j) ke (if, jf). Konsekuensi dari prinsip ini adalah bahwa sekali kita berada di (i, j) melalui jalur optimal, maka untuk mencapai (if, jf) secara optimal kita hanya perlu mencari jalur optimal dari (i, j) ke (if, jf). Kita dapat menyatakan ini dengan cara yang akan berguna bagi kita di kemudian hari. Asumsikan bahwa kita berangkat dari (i0, j0) dan biarkan node ke-k dari jalur menjadi (ik, jk). Tujuannya adalah untuk menghitung biaya minimum yang dibutuhkan untuk mencapai node berikutnya. Transisi ke (ik, jk) harus diambil dari salah satu node yang mungkin yang diperbolehkan untuk berada di posisi ke-(k–1) dari jalur (yaitu node (ik-1, jk-1)). Hal ini penting dilakukan. Untuk setiap node dari grid, kita asumsikan bahwa ada satu set predecessor (pendahulu) yang diperbolehkan, yang didefinisikan sebagai kendala lokal (local constrain). Prinsip Bellman mengarah pada:
Memang, biaya minimal keseluruhan untuk mencapai node (ik, jk) merupakan biaya minimum sampai ke node (ik-1, jk-1) ditambah dengan biaya tambahan transisi dari (ik-1, jk-1) ke (ik, jk). Selanjutnya, pencarian minimum dibatasi hanya dalam set pendahulu yang diperbolehkan untuk node (ik, jk). Prosedur ini dilakukan pada semua node dari grid. Namun, dalam banyak kasus tidak semua node dari grid terlibat, dan pencarian jalur yang optimal terjadi antara subset dari grid tersebut, yang didefinisikan melalui apa yang disebut sebagai kendala global. Algoritma yang dihasilkan dikenal sebagai pemrograman dinamis. Persamaan (8.1) harus dimodifikasi sesuai biaya D yang diberikan dalam bentuk perkalian dan / atau jika maksimalisasi diperlukan. Kita fokus pada tugas pencocokan pola string dan melihat bagaimana persamaan rekursif (8.1) digunakan untuk membangun jalur lengkap yang optimal. Gambar 8.2 mengilustrasikan prosedur. Himpunan node yang terlibat dalam optimisasi (kendala global) ditandai sebagai titik gelap, dan kendala lokal, mendefinisikan transisi yang diperbolehkan diantara node-node ini, yang ditunjukkan pada gambar dengan garis tipis. Setelah diputuskan untuk mencari jalur lengkap dan asumsi D (0,0) = 0, biaya masing-masing D (il, j1) untuk semua node diperbolehkan yang terlibat dalam langkah k = 1 dihitung melalui (8,1) (dalam kasus ini hanya ada dua node yang diperbolehkan, (1,1) dan (1,2)). Selanjutnya, biaya dari (tiga) node pada langkah k = 2 dihitung dan prosedur ini diulang sampai kita mencapai node terakhir (I, J). Urutan transisi menuju D minimum (I, J) dari node terakhir menentukan jalur biaya minimum, dinotasikan dengan garis tebal. Korespondensi node optimal, antara pola referensi dan pola pengujian, kemudian dapat terurai dengan cara menarik kembali jalur yang optimal. Pada contoh gambar 8.2, masing-masing langkah k dari rekursi hanya melibatkan node-node dengan koordinat absis yang sama, yang mencerminkan kendala lokal yang diadopsi. Umumnya, hal ini tidak diperlukan dan topologi yang terlibat lebih dapat digunakan. Namun, filosofi pencarian minimum tetap sama. Dalam sekuel, kita akan menerapkan prosedur di dua wilayah aplikasi populer yang berbeda.
8.2.2 Jarak Edit Pada bagian ini terkait dengan pola yang terdiri dari set order simbol. Misalnya, jika simbol ini merupakan huruf, maka polanya adalah kata-kata dari teks tertulis. Masalah-masalah akan muncul dalam pengeditan otomatis dan aplikasi mendapatkan teks kembali. Contoh lain dari string simbol terjadi dalam pengenalan pola struktural.
Gambar 8.2 Jalur optimal yang dibangun dengan pencarian diantara semua jalur yang diperbolehkan, sebagaimana yang didefinisikan oleh kendala lokal dan global Setelah simbol dari pola (pengujian) telah diidentifikasi, misalnya, melalui perangkat pembaca, tugas selanjutnya adalah mengenali pola, mencari yang paling cocok terhadap satu set pola referensi. Ukuran yang akan diadopsi untuk prosedur pencocokan seharusnya memperhitungkan kesalahan yang muncul, yang mungkin terjadi selama tahap identifikasi simbol. Simbol yang teridentifikasi dengan salah (misalnya, “befuty” bukan “beauty”) Penyisipan kesalahan (misalnya, “bearuty”) Penghapusan kesalahan (misalnya, “beuty”) Jelas, kombinasi dari kesalahan ini juga mungkin terjadi. Untuk prosedur pencocokan kita akan mengadopsi filosofi di balik apa yang disebut sebagai variational similarity. Dengan kata lain, kesamaan diantara dua pola yang didasarkan pada “biaya” terkait dengan mengkonversi satu pola ke pola yang lain. Jika pola tersebut mempunyai panjang yang sama, maka biaya secara langsung berhubungan dengan jumlah simbol yang harus diubah sehingga dihasilkan pola yang lain. Yang lebih menarik lagi ketika dua pola tidak mempunyai panjang yang sama. Dalam kasus ini, simbol harus dihapus maupun disisipkan pada tempat-tempat tertentu dari string pengujian. Lokasi dimana penghapusan atau penyisipan dilakukan mengisyaratkan sebuah kesejajaran optimal (warping) di antara simbol dari dua pola. Jarak
edit [Dome 64, Leven 66] antara dua pola string A dan B, dinotasikan D (A, B), didefinisikan sebagai jumlah total minimum dari perubahan C, penyisipan I, dan penghapusan R yang dibutuhkan untuk mengubah pola A menjadi pola B,
dimana j berjalan di atas semua kombinasi yang mungkin dari variasi simbol untuk mendapatkan B dari A. Untuk menguraikan sedikit, perlu diketahui bahwa ada lebih dari satu cara untuk mengubah, katakanlah, “beuty” ke “beauty”. Sebagai contoh, dapat disisipkan “a” setelah “e” atau mengubah “u” ke “a” dan kemudian menyisipkan “u”. Kita akan menggunakan metodologi pemrograman dinamis untuk menghitung nilai minimum yang diperlukan dalam (8.2). Untuk tujuan ini, kita membentuk grid dengan menempatkan simbol dari pola referensi ke dalam sumbu absis dan pola pengujian ke dalam sumbu ordinat. Gambar 8.3 menunjukkan prosedur melalui empat contoh. Seperti yang telah ditunjukkan sebelumnya, langkah pertama pada prosedur pencarian jalur optimal melalui teknik pemrograman dinamis adalah untuk menyatakan kendala transisi node yang ditentukan oleh masalah. Untuk kasus ini, diadopsi beberapa kendala berikut. Biaya D (0, 0) dari node (0, 0) adalah nol. Dicari sebuah jalur lengkap. Setiap node (i, j) dapat dicapai hanya melalui tiga pendahulunya yang diperbolehkan, yaitu,
sebagaimana diindikasikan pada bagian bawah Gambar 8.3. Biaya yang terkait dengan tiga transisi di atas adalah: 1. Transisi Diagonal:
Artinya, biaya transisi akan bernilai nol jika simbol yang sesuai dengan node (i, j) adalah sama dan akan bernilai satu jika berbeda, sehingga perubahan simbol telah terjadi. 2. Transisi horisontal dan vertikal
Yang dimaksud dengan transisi horisontal adalah bahwa transisi dimana mereka berusaha menyelaraskan dua string dengan menyisipkan sebuah simbol; lihat Gambar 8.3a. Jadi, mereka menambah biaya, karena menyiratkan ketidakcocokan lokal. Demikian pula, transisi vertikal menambah biaya karena menyiratkan penghapusan, Gambar 8.3c.
Gambar 8.3 Komputasi dari jarak edit dengan (a) penyisipan, (b) perubahan, (c) penghapusan, dan (d) persamaan. Kendala lokal ditunjukkan pada pojok kanan bawah. Adanya kendala-kendala dan jarak (8.2) pada prosedur pemrograman dinamis menghasilkan algoritma berikut: Algoritma untuk Komputasi Jarak Edit D (0,0) = 0 For I = 1 to I D (i, 0) = D (i-1,0) + 1 End { For } For j = 1 to J D (0, j) = D (0, j-1) + 1 End { For }
For i = 1 to I For j = 1 to J *c1 = D (i-1, j-1) + d (i, j│i-1, j-1) *c2 = D (i-1, j) + 1 *c3 = D (i, j-1) + 1 *D (i, j) = min (c1, c2, c3) End { For } End { For } D (A,B) = D (I,J) Dengan kata lain, pertama-tama kita menghitung biaya minimum untuk mencapai setiap node dari grid, dimulai dari (0.0), dan jalur optimal (lengkap) selanjutnya akan dibangun. Gambar 8.3 menunjukkan masing-masing jalur biaya minimum dan jarak Edit yang dihasilkan untuk setiap kasus. Pastikan bahwa jalur lain yang dicontohkan pada Gambar 8.3 menghasilkan biaya yang lebih tinggi. Sebuah generalisasi dari jarak Edit memungkinkan untuk menggabung, membelah dan mensubstitusi dua-huruf dalam konteks pengenalan tulisan tangan yang diberikan dalam [Seni 96]. 8.2.3 Pembelokan Waktu Dinamis dalam Pengenalan Suara Pada bagian ini, kami menyoroti penerapan teknik pemrograman dinamis dalam pengenalan suara. Kami akan fokus pada bentuk yang lebih sederhana dari tugas, yang dikenal sebagai pengenalan kata terisolasi atau diskrit (isolated word recognition/ IWR). Artinya, kita akan mengasumsikan bahwa teks lisan terdiri dari kata-kata diskrit, terisolasi dengan baik dengan periode diam yang cukup. Dalam tugas ini, cukup mudah untuk memutuskan dimana, kapan, satu kata selesai dan dimana satu kata dimulai. Ini bukanlah, bagaimanapun, kasus pada sistem pengenalan suara kontinyu (continuous speech recognition/ CSR) yang lebih kompleks, dimana pembicara berbicara dengan cara alami dan batas-batas temporal antara kata-kata tidak terdefinisikan dengan baik. Dalam kasus terakhir, diperlukan skema yang lebih rumit (misalnya [Silv 90, Desh 99. Neg 99]). Ketika kata-kata diucapkan oleh pembicara tunggal dan tujuan dari sistem pengenalan ini adalah untuk mengenali kata-kata yang diucapkan oleh orang tersebut, maka tugas pengenalan dikenal sebagai pengenalan bergantung pada pembicara (speaker-dependent recognition). Tugas yang lebih kompleks lagi adalah pengenalan yang tidak bergantung pada pembicara (speaker-independent recognition). Dalam kasus terakhir, sistem harus dilatih menggunakan sejumlah pembicara dan sistem harus mampu menggeneralisasi dan mengenali kata-kata yang diucapkan oleh orang-orang di luar populasi pelatihan. Pada dasarnya, setiap sistem IWR merupakan seperangkat pola referensi yang dikenal dan sebuah ukuran jarak (ingat catatan kaki dalam Bagian 8.2). Pengenalan dari pola pengujian yang tidak diketahui dicapai dengan pencarian pencocokan terbaik antara pola pengujian dan pola referensi masing-masing, berdasarkan ukuran yang diadopsi.
Gambar 8.4 Plot (a) urutan waktu sesuai dengan kata "love" dan (b) besarnya DFT, dalam dB, untuk salah satu frame-nya. Gambar 8.4a dan 8.5a menunjukkan plot dari dua urutan waktu akibat sampling dari kata “love”, kata yang diucapkan dua kali oleh pembicara yang sama. Sampel diambil pada output mikrofon di tingkat sampling 22050 Hz. Meskipun sulit untuk menggambarkan perbedaan, ini dapat segera terlihat. Selain itu, dua kata yang diucapkan merupakan durasi yang berbeda. Tanda panah menunjukkan (kira-kira) interval di mana segmen diucapkan kebohongan. Interval luar panah sesuai dengan periode diam. Secara khusus, urutan pada Gambar 8.5a adalah panjang 0,4 detik, dan urutan pada Gambar 8.4a adalah panjang 0,45 detik. Selain itu,
Gambar 8.5 Plot waktu urutan yang dihasilkan dari kata-kata (a)”love” dan (b) “kiss” yang diucapkan oleh pembicara yang sama. penting untuk mengatakan bahwa ini bukan hasil dari skala waktu linear sederhana. Sebaliknya, pemetaan nonlinier yang tinggi sangat diperlukan untuk mendapatkan pencocokan antara dua kata-kata yang “sama” yang diucapkan oleh orang yang sama. Sebagai perbandingan, Gambar 8.5b menunjukkan plot urutan waktu berhubungan dengan kata lain, “kiss”, yang dituturkan oleh pembicara yang sama. Kami akan mempergunakan teknik pemrograman dinamis untuk mengungkap pemetaan nonlinier (warping) yang dibutuhkan untuk mencapai pencocokan yang optimal antara pola pengujian dan pola referensi. Untuk tujuan ini, kita harus terlebih dahulu mengungkapkan kata-kata yang diucapkan sebagai rangkaian (string) dari vektor fitur yang sesuai, r (i), i = 1,..., I , untuk pola referensi dan t (j), j = 1,. . . , J, untuk pola pengujian. Jelas, ada lebih dari satu cara untuk memilih vektor fitur. Kami akan fokus pada fitur transformasi Fourier.
Gambar 8.6 Frame overlap berturutan untuk perhitungan vektor fitur DFT Setiap urutan waktu yang terlibat dibagi ke dalam frame waktu overlap berturut-turut. Dalam kasus ini, setiap frame dipilih menjadi tf = 512 panjang sampel dan overlap antara frame yang berurutan untuk t0 = 100 sampel, seperti terlihat pada Gambar 8.6. Jumlah frame yang dihasilkan untuk segmen bicara yang ditunjukkan pada Gambar 8.4a adalah I = 24, dan untuk dua yang lain masing-masing adalah J = 21 (Gambar 8.5a) dan J = 23 (Gambar 8.5b). Kami berasumsi bahwa yang lebih awal adalah pola referensi dan dua terakhir adalah pola pengujian. Dengan xi(n), n = 0,..., 511, menjadi sampel untuk frame ke-i dari pola referensi, dengan i = 1, ...., I. DFT yang sesuai diberikan sebagai:
Gambar 8.4b menunjukkan besarnya koefisien DFT untuk salah satu dari frame I dari pola referensi. Plot adalah salah satu tipikal untuk segmen bicara. Magnitud dari koefisien DFT yang lebih tinggi sangat kecil dengan sedikit kontribusi untuk sinyal. Hal ini membenarkan penggunaan koefisien DFT l pertama sebagai fitur, dimana biasanya l << tf. Dalam kasus ini nilai l = 50 dianggap cukup. Dengan demikian, urutan vektor menjadi:
Vektor fitur t (j), untuk masing-masing pola pengujian, dibentuk dalam cara yang sama. Pemilihan koefisien DFT sebagai fitur hanyalah salah satu dari berbagai kemungkinan yang telah diusulkan dan digunakan selama bertahun-tahun. Alternatif lainnya termasuk parameter dari pemodelan AR dari segmen bicara, koefisien ceptral (kebalikan DFT dari logaritma magnitud koefisien DFT), dan sebagainya (misalnya, [Davi 80, Dell 931]). Setelah menyelesaikan preprocessing dan seleksi fitur, referensi dan pengujian pola dinyatakan sebagai (derajat) urutan vektor fitur r (i) dan t (j). Tujuannya jadi menghitung yang paling cocok antara frame dari pola pengujian dan pola referensi. Artinya, pola pengujian akan diregangkan dalam waktu (satu frame pengujian disesuaikan dengan lebih dari satu frame pola referensi) atau dikompresi dalam waktu (lebih dari satu frame pengujian disesuaikan dengan satu frame pola referensi). Ini deretan yang optimal dari vektor di dua pola string yang akan berlangsung melalui prosedur pemrograman dinamis. Untuk tujuan ini, pertama
kita menemukan vektor dari string acuan di sepanjang absis tersebut dan dari pola pengujian sepanjang ordinat tersebut. Kemudian, berikut ini harus ditentukan: Kendala Global Kendala Lokal Kendala Titik Akhir Biaya d untuk transisi Berbagai asumsi bisa diadopsi untuk masing-masing, yang mengarah ke hasil yang berbeda dengan manfaat relatif. Dalam sekuel, kita akan fokus pada beberapa kasus yang banyak digunakan secara luas. Kendala Titik Akhir. Dalam contoh kita kita akan mencari jalur lengkap yang optimal yang dimulai pada (0, 0) dan berakhir di (I, J) dan transisi pertama adalah node (1, 1). Dengan demikian, secara implisit diasumsikan bahwa titik akhir segmen bicara (misal r(l), t(1) dan r(I), t(J)) cocok ke tingkat yang tepat. Ini bisa menjadi hasil vektor (masing-masing) dari periode diam sebelum dan sesudah segmen bicara. Sebuah variasi yang sederhana dari hasil jalur kendala lengkap jika akhir titik jalur tidak ditentukan apriori dan diasumsikan berada dalam jarak Є dari titik (1, 1) dan (I, J), dan diserahkan kepada algoritma pengoptimalan untuk menemukannya. Kendala Global. Kendala global mendefinisikan wilayah node yang mencari jalur yang optimal. Node luar wilayah ini tidak dicari. Pada dasarnya, kendala global menentukan keseluruhan peregangan atau kompresi yang diperbolehkan untuk prosedur pencocokan. Sebagai contoh ditunjukkan pada Gambar 8.7. Mereka dikenal sebagai kendala Itakura dan menerapkan faktor maksimal 2 untuk setiap ekspansi atau kompresi pengujian sehubungan dengan pola referensi. Yang diijinkan node kemudian berada di dalam jajaran genjang yang ditunjukkan pada Gambar 8.7 oleh garis lurus. Garis putus-putus sesuai dengan kendala global yang sama saat titik akhir kendala, disebutkan sebelumnya, yang diadopsi. Perhatikan dari gambar, jalur di seberang atau kompres jajaran genjang atau memperluas frame yang sesuai interval dengan faktor 2, dan ini adalah faktor maksimum yang mungkin tercapai. Ini biasanya kendala wajar, dan pada saat yang sama mengurangi jumlah node yang akan dicari untuk jalur yang optimal secara substansial. Jika I ≈ J, maka tidak sulit untuk menunjukkan bahwa jumlah titik grid untuk dicari berkurang sekitar sepertiga (1/3).
Gambar 8.7 Kendala Global Itakura. Faktor kompresi/ekspansi maksimum adalah 2, dan menentukan kemiringan segmen garis batas. Kendala lokal. Kendala ini mendefinisikan set pendahulu dan yang diijinkan transisi ke node grid tertentu. Pada dasarnya, mereka memberi batasan untuk tingkat maksimum ekspansi/kompresi transisi berurutan dapat mencapai. Dengan sifatnya bahwa setiap kendala lokal harus memenuhi monotonisitas. Artinya,
Dengan kata lain, semua pendahulu dari node terletak ke kiri dan selatannya. Ini menjamin bahwa pengoperasian pencocokan mengikuti evolusi waktu alami dan menghindari sesuatu yang membingungkan, misalnya, kata "from" dengan kata "form". Dua contoh jalur nonmonotonic diperlihatkan pada Gambar 8.8. Satu set kendala lokal, yang dikenal sebagai kendala Itakura [Itak 75], ditampilkan pada Gambar 8.9. Tingkat ekspansi(kompresi) maksimum dicapai melalui jalur lokal diukur oleh kemiringan yang terkait, yang didefinisikan sebagai rasio maksimum dari perubahan total Δi, dalam arah ke-i, untuk perubahan total Δj, dalam arah ke-j, lebih dari jalur lokal. Kemiringan untuk kendala Itakura adalah 2, dan merupakan hasil dari (berulang) transisi dari tipe (i-1, j-2) untuk (i, j). Karakteristik penting lain dari kendala Itakura adalah bahwa transisi horisontal diperbolehkan, namun tidak secara berturut-turut, dan ini ditunjukkan oleh panah menyeberang. Jadi, kendala Itakura tidak memperbolehkan jalur panjang horisontal, sesuai dengan kemiringan ∞. Akhirnya, kendala ini memungkinkan jalur untuk melewati paling banyak satu vektor fitur dalam pola pengujian.
Gambar 8.8 Contoh jalur nonmonotonic. Jalur tersebut tidak diperbolehkan dan tidak dianggap dalam pencarian optimal. string, yaitu, satu di posisi j-1 dari sumbu ordinat, dan jalur melompat dari (i-1, j-2) ke (i, j). Sebaliknya, vektor fitur dalam string referensi tidak dilewati dan semua mengambil bagian dalam jalur yang optimal. Kendala tersebut dikenal sebagai asimetris. Sejumlah kendala lokal alternatif juga telah disarankan dan digunakan dalam praktek. Gambar 8.10 menunjukkan empat jenis kendala dipertimbangkan oleh Sakoe dan Chiba [Sako 78]. Untuk tipe dalam Gambar 8.10a tidak ada batasan pada tingkat ekspansi/kompresi, karena transisi horisontal atau vertikal yang berurutan dapat terjadi,
Gambar 8.9 Kendala Itakura lokal. Dua transisi horisontal yang berurutan tidak diperbolehkan.
Gambar 8.10 Kendala lokal Sakoe dan Chiba sampai salah satu berada di luar kawasan yang ditetapkan oleh kendala global. Sebaliknya, di Gambar 8.10b transisi horisontal (vertikal) diperbolehkan hanya setelah transisi diagonal dan di Gambar 8.10d setelah dua transisi diagonal berturut-turut. Dalam Gambar 8.10c, paling banyak dua berturut-turut transisi horisontal (vertikal) diperbolehkan hanya setelah satu transisi diagonal. Kemiringan untuk setiap kendala dalam Gambar 8.10a, b, c dan d masingmasing adalah ∞, 2, 3, dan 3/2, (Permasalahan 8.2). Untuk lebih rinci dari topik tersebut pembaca yang tertarik dapat berkonsultasi [Dell 93, Silv 90, Myer 80]. Biaya. Umumnya menggunakan biaya, yang akan kami adopsi disini, adalah jarak Euclidean antara r (ik) dan t (jk), sesuai dengan node (ik, jk), yaitu,
Dalam hal ini, kami mengasumsikan bahwa tidak ada biaya yang berkaitan dengan transisi ke node tertentu, dan biaya tergantung sepenuhnya pada vektor fitur yang sesuai dengan masingmasing node. Biaya lain-lain juga telah disarankan dan digunakan [Gray 76, Gray 80]. Barubaru ini ([Pikr 02], [Pikr 03]) menggunakan biaya yang dihitung untuk kesalahan yang paling sering terjadi (misalnya, gaya pemain yang berbeda) dalam konteks pengenalan musik. Akhirnya, harus dinyatakan bahwa sering kali dilakukan sebuah normalisasi dari biaya keseluruhan D. Hal ini untuk mengkompensasi perbedaan pada panjang jalur, menawarkan kesempatan yang “sama” untuk mereka semua. Sebuah pilihan yang logis adalah dengan membagi biaya keseluruhan D dengan panjang setiap jalur [Myer 80].
Keseluruhan biaya yang dihasilkan untuk dua pola pengujian pada Gambar 8.5, melawan pola referensi dari Gambar 8.4, dengan menggunakan kendala Itakura, masingmasing adalah D=11,473 dan D=25,155. Dengan demikian, biaya keseluruhan untuk kata “love” lebih rendah daripada biaya keseluruhan untuk kata "kiss", dan prosedur kami telah mengakui kata yang diucapkan benar. Biaya normalisasi keseluruhan yang dihasilkan setelah membagi dengan jumlah node di sepanjang jalur masing-masing adalah 0,221 dan 0,559. 8.3 UKURAN BERDASARKAN KORELASI Tugas utama yang akan dibahas pada bagian ini dapat diringkas sebagai berikut: "Diberikan blok data rekaman, cari apakah sebuah pola (referensi) spesifik dikenal terkandung dalam blok dan dimana lokasinya". Jenis aplikasi ini ditemukan dalam analisis tempat, ketika kita ingin mencari benda tertentu di gambar. Masalah tersebut muncul dalam banyak aplikasi, seperti deteksi target, visi robot, dan pengkodean video. Sebagai contoh, dalam pengkodean video langkah utama adalah dari estimasi gerak, yaitu, proses menemukan piksel yang sesuai (diantaranya, objek yang sama-sama pindah) di antara frame gambar berturut-turut pada waktu yang berbeda. Langkah ini kemudian diikuti oleh tahap kompensasi gerak, yang mengkompensasi untuk perpindahan objek bergerak dari satu frame ke frame yang lain. Tahap berikutnya kemudian mengkodekan perbedaan frame:
dimana r (i, j, t) adalah tingkat abu-abu pixel dari frame gambar pada waktu t dan r (i-m, t-n, t-1) nilai-nilai pixel yang sesuai di lokasi ruang i-m, j-n dari frame sebelumnya pada waktu t1. Dengan cara ini, kita mengkodekan hanya information baru yang terkandung pada frame terakhir, untuk menghindari redundansi. Asumsikan bahwa kita diberi pola referensi yang dinyatakan sebagai sebuah M x N array gambar r (i, j), i = 0,..., M-1, j = 0,..., N-1, dan I x J array gambar t (i, j), i = 0,..., I-1, j = 0, ... , J-1, di mana M ≤ I, N ≤ J. Tujuannya adalah untuk mengembangkan ukuran untuk mendeteksi sebuah M x N subimage N dalam t(i, j) yang paling cocok pola referensi r (i, j). Untuk tujuan ini, gambar referensi r (i, j) adalah ditumpangkan pada gambar pengujian dan diterjemahkan ke semua posisi yang mungkin (m,n) di dalamnya. Untuk setiap titik (m,n), tidak cocok antara r (i. j) dan M x N subimage t (i, j) dihitung menurut:
Pencocokan template dilakukan dengan pencarian lokasi (m,n) untuk D (m,n) minimum. Mari kita bentuk komputasi ini menjadi bentuk yang lebih menarik. Persamaan (8.4) adalah setara dengan:
Peubah acak yang kedua adalah konstanta untuk pola referensi yang diberikan. Dengan asumsi bahwa yang pertama tidak merubah banyak pada gambar, yaitu, tidak ada banyak variasi dari tingkat piksel abu-abu di atas gambar pengujian, nilai minimum D (m, n) telah tercapai ketika:
bernilai maksimum untuk semua lokasi yang mungkin (m, n). Kuantitas c (m,n) tidak dihitung melainkan dari urutan cross-korelasi antara t (i, j) dan r (i, j) yang dihitung pada titik (m,n). Dalam kasus yang asumsi tingkat variasi abu-abu kecil tidak valid, ukuran ini sangat sensitif terhadap variasi tingkat keabuan dalam t(i, j). Dalam kasus seperti koefisien cross korelasi, didefinisikan sebagai:
adalah ukuran yang lebih tepat. Di sini cN (m,n) adalah versi normal c (m, n) dan variasi pada t(i, j) cenderung untuk pembatalan. Perlu diingat kembali ketidaksamaan Cauchy-Schwarz :
Kesamaan terjadi jika dan hanya jika:
dengan α menjadi konstanta yang berubah-ubah. Oleh karena itu, cN (m,n), selalu kurang dari satu dan mencapai nilai maksimum satu hanya jika subimage (pengujian) adalah sama (dalam faktor skala) sebagai pola referensi. Dalam diskusi kami sejauh ini, kami telah mengasumsikan bahwa pola referensi hanya diterjemahkan dalam t (i, j) dan tidak ada rotasi atau penskalaan yang terlibat. Dalam aplikasi seperti pengkodean video, hal ini adalah asumsi yang valid dan telah diadopsi di standar pengkodean video [Bhas 95]. Namun, hal ini tidak selalu terjadi dan teknik harus dimodifikasi. Salah satu cara adalah untuk menggambarkan referensi dan pengujian subimage dalam hal saat invarian dan mengukur kesamaan dengan menggunakan korelasi yang melibatkan peristiwa-peristiwa ini [Hall 79] (Permasalahan 8.4). Rotasi dan teknik skala invarian lainnya, menggunakan kombinasi transformasi Fourier dan Mellin, seperti yang digambarkan dalam [Scha 89]. Teknik ini mencoba untuk mengeksploitasi translasi invarian dari magnitude transformasi Fourier (sudah dibahas dalam Bab 7) dan skala invarian transformasi Mellin ([Ravi 95], Permasalahan 8.5). Jalur lain, yang tentu saja permintaan sumber daya komputasi yang tinggi, adalah memiliki satu set referensi template yang menyimpang (misalnya, diputar dan diskalakan) untuk menutup segala kemungkinan. Korelasi yang cocok kemudian akan mengungkapkan manakah yang paling cocok antara pola pengujian dan salah satu referensi template. Sebuah teknik komputasi yang lebih menarik menggunakan transformasi Karhunen-Lobve [Ueno 97]. Ide utamanya adalah bahwa template yang diputar sangat berkorelasi, dan masing-masingnya dapat didekati dengan proyeksinya ke sebuah dimensi ruang eigen yang lebih rendah, dengan menggunakan eigenvector yang
paling signifikan dari matriks korelasinya. Pencocokan pola yang tidak diketahui dengan template dari orientasi yang tepat dilakukan di dalam ruang dimensi yang lebih rendah, yang mengarah pada simpanan komputasi yang besar. Contoh 8.1. Citra t (i, j) pada Gambar 8.11a berisi dua benda, obeng dan palu. Yang terakhir adalah objek yang kita ingin cari pada citra. Citra referensi akan ditampilkan di sudut kanan atas Gambar 8.11a. Daerah bertitik menunjukkan posisi umum(n, m) citra referensi bila ditumpangkan pada citra yang diuji. Gambar 8.11b menunjukkan cross-correlation c (m, n) antara kedua citra. Kami telah amati bahwa maksimum (hitam) terjadi pada posisi (13, 66), yaitu, dimana palu terletak di t (i, j).
Gambar 8.11 Contoh dari (a) referensi dan citra pengujian dan (b) korelasi antara keduanya. Pertimbangan Komputasional Dalam beberapa kasus, lebih efisien untuk menghitung cross-correlation dengan menggunakan transformasi Fourier. Ingatlah bahwa dalam domain frekuensi (8.6) dapat ditulis sebagai
dimana T(k,l), R(k,l) merupakan transformasi DFT dari t (i, j) dan r (i, j), masingmasing, dengan notasi “*”yang menunjukkan konjugasi kompleks. Tentu saja, untuk menuliskan (8.8) kedua citra memiliki ukuran yang sama. Jika tidak, kasus biasanya, sejumlah nol harus ditambahkan untuk memperpanjang citra yang berukuran lebih kecil. c(m, n) diperoleh melalui invers DFT dari C(k, I). Dengan mempertimbangkan efisiensi komputasi FFT, prosedur ini dapat mengakibatkan penghematan ketergantungan, tentu saja, pada ukuran relatif dari M, N dan I, J. Sebuah beban komputasi utama dalam pencocokan berbasis korelasi template adalah pencarian atas piksel t (i, j) untuk mencari korelasi maksimum. Biasanya, pencarian dibatasi dalam kotak [p-, p] x [-p, p] yang berpusat pada titik (x, y) di t (i, j). Sebagai contoh, dalam video coding, jika blok M x N yang berpusat pada posisi (x,y) dalam frame waktu t - 1, maka frame saat ini yang dicari dalam (x±p, y±p). Nilai p tergantung pada aplikasi. Untuk siaran TV, p = 15 telah mencukupi. Untuk acara olahraga (dengan pergerakan tinggi) lebih tepat menggunakan p = 63. Dengan demikian, pencarian lengkap untuk maksimum dari c(m, n), didefinisikan dalam (8.6), akan membutuhkan sejumlah penambahan dan perkalian yang proporsional dengan
(2p+1)2 M N. Hal ini menyebabkan penambahan sejumlah besar operasi. Dengan demikian, dalam prakteknya, teknik pencarian heuristic suboptimal biasanya digunakan, walaupun hal ini tidak menjamin mencari maksimal, tetapi mengurangi jumlah operasi yang diperlukan secara substansial. Ada dua arah utama. Salah satunya adalah untuk mengurangi poin pencarian dan yang lainnya adalah untuk mengurangi ukuran citra yang terlibat. Pencarian Logaritmis Dua-Dimensi Pencarian logaritmis Gambar 8.12 menunjukkan bahwa area pencarian persegi [-p,p] x [-p,p] untuk kasus p = 7. Pusat persegi diasumsikan pada titik (0, 0). Perhitungan crosscorrelation pertama kali dilakukan pada pusat serta delapan titik yang terletak perimeter di dalam daerah [-p/2, p/ 2] x [-p/2, p/2] (p/2 dibulatkan ke suatu integer). Titik-titik ini ditandai dengan bujursangkar. Jarak antara titik-titik ini dl = 4 pixel, yaitu dimana dl = 2k-1 dan k = [log2 p], dimana R.1 menunjukkan pembulatan ke integer pertama yang lebih besar. Untuk p = 7, k = 3 dan dl = 4. Kami akan menunjukkan prosedur melalui contoh. Mari kita berasumsi bahwa nilai cross-correlation terbesar dihasilkan pada posisi (-4, 0) (persegi berbayang). Kemudian kita anggap ini titik sebagai pusat persegi panjang ukuran [-p/4,p/4]x[-p/4,p/4] ([-2,2] x [-2,2] dalam kasus ini) dan menghitung korelasi pada delapan poin pada garis keliling tersebut.
Gambar 8.12 Pencarian logaritmis untuk menemukan titik cross-correlation maksimum. Titik-titik ini dinotasikan dengan lingkaran dan jarak antar titik kini d2 = dl/2(2). Proses ini diulang dan kemudian perhitungan dilakukan pada delapan titik (berlian) pada garis keliling persegi panjang ukuran [-1, 1] x [-1,1] yang berpusat di titik optimum (dari langkah sebelumnya) lingkaran berbayang. Jarak antara titik-titik berlian adalah d3 = 1. Berlian berbayang yang sesuai dengan titik dengan cross-correlation maksimum dan proses kemudian dihentikan. Jumlah komputasi sekarang telah direduksi menjadi MN(8k+1) operasi, hal ini merupakan penghematan besar dibandingkan dengan pencarian lengkap.
Varian dari pencarian logaritmis dua dimensi adalah dengan mencari i dan j yang arahnya independen. Titik yang koordinatnya merupakan nilai terbaik yang dihasilkan oleh i dan j menjadi asal baru dari sistem koordinat, dan pencarian diulangi dalam i baru, arah j, dengan jarak yang lebih kecil d. Proses ini diulang sampai jaraknya menjadi satu. Pencarian Hirarkis Teknik ini dikembangkan dari konsep multiresolusi pada Bab 6. Mari kita ambil contoh lagi.
Langkah 1: Sebuah blok referensi, katakanlah, 16 x 16 diberikan dan daerah pencarian diasumsikan merupakan persegi [-p, p]x [-p, p], berpusat pada titik (x, y) pada citra pengujian. Kita lihat versi citra level 0. Kedua blok referensi dan citra pengujian ditapis low- pass dan di-subsample dengan 2, sehingga memberikan hasil pada level 1 versinya. Jumlah total pixel dalam versi level 1 telah dikurangi oleh 4. Versi level 1 pada gilirannya ditapis low-pass dan disub-sampel, hingga versi level 2. Secara umum, proses ini dapat dilanjutkan. Langkah 2: Pada level 2 pencarian untuk maksimum berlangsung dengan 4 x 4 versi low-pass blok referensi. Area pencarian pada level 2 versi low-pass dari citra pengujian merupakan persegi panjang [-p/4, p/4] x[-p/4, p/4] yang berpusat di (x/4, y/4). Baik pencarian penuh atau logaritmisk dapat digunakan. Ambil (x1, y1) merupakan koordinat optimal, sehubungan dengan (x/4, y/4). Langkah 3: Pada level 1, pencarian maksimal dilakukan dengan menggunakan menyesuaikan blok referensi versi 8 x 8. Daerah pencarian, dalam versi 1 tingkat citra pengujian, merupakan persegi panjang dengan ukuran [- 1,1 ] x [-1,1] yang berpusat di (x/2 + 2x1, y/2 + 2yl), yaitu total sembilan piksel. Hal ini karena delapan pixel di perimeter daerah ini tidak dilibatkan pada level 2, terkait dengan subsampling (lihat Gambar 6.16 dari Bab 6). Titik pusat juga harus dimasukkan untuk dapat diperoleh perbandingan yang adil di level ini untuk mencari maksimal. Ambil maksimum terjadi pada (x2, y2) dengan (x/2, y/2). Langkah 4: Pada level 0 pencarian dilakukan dengan menggunakan template referensi asli, di dalam area dengan ukuran [-1,1]x[-1,1] yang berpusat di (x+2x2, y+2y2) pada citra pengujian. Lokasi maksimum ini merupakan yang terakhir dan proses dihentikan.
Penghematan komputasi dengan metode ini tergantung pada jumlah level, serta jenis pencarian yang diadopsi pada tingkat tertinggi (Permasalahan 8.5). Secara umum, metode hirarkis sangat efisien dari sudut pandang komputasi. Hal ini diperoleh dengan mengorbankan kebutuhan memori yang meningkat, karena berbagai versi citra yang harus disimpan. Salah satu kelemahan metode ini adalah bahwa jika benda-benda kecil hadir dalam template, mereka mungkin menghilang pada citra dengan resolusi terendah karena subsampling tersebut. Selanjutnya, metode ini tidak dapat menjamin untuk menemukan kecocokan global terbaik. Dalam [Alkh 01] sebuah filosofi alternatif yang disarankan menghasilkan kecocokan global terbaik. Penghematan komputasi yang dicapai dengan pemangkasan jumlah calon kecocokan terbaik pada suatu level, dengan menggunakan hasil pada tingkat yang lebih tinggi dan nilai ambang batas terpilih yang lebih tepat. Metode Sequential Sejumlah teknik lainnya juga telah disarankan. Sebagai contoh, metode pencarian sequential dengan menghitung varian dari (8.4) secara langsung. Secara khusus, tentukan
Dengan demikian, kesalahan dihitung di daerah jendela yang lebih kecil dan secara berurutan meningkat, untuk p, q = 1,2,. . . dan p ≤ M, q ≤ N. Perhitungan berhenti ketika Dpq (m, n) menjadi lebih besar daripada ambang batas yang telah ditentukan. Kemudian perhitungan mulai dari arah yang berbeda (m, n). Dari sinilah penghematan dicapai, karena untuk posisi yang buruk hanya membutuhkan sejumlah kecil perhitungan. 8.4 MODEL TEMPLATE YANG DAPAT DI DEFORMASI Pada bagian sebelumnya kita dianggap sebagai masalah mencari pola referensi yang dikenal (template) dalam citra pengujian. Kita berasumsi bahwa template dan objek, yang berada dalam citra, adalah identik. Satu-satunya perbedaan yang diperbolehkan untuk masuk ke dalam diskusi kita yang dikenakan oleh orientasi yang berbeda dan/ atau scaling. Namun, ada banyak masalah di mana kita tahu sebuah priori yang template-nya tersedia dan objek yang kita cari dalam citra tersebut tidak mungkin terlihat sama persis. Hal ini mungkin karena kondisi pencitraan yang berbeda-beda, keadaan macet (oklusi), dan segmentasi citra yang tidak sempurna. Selanjutnya, dalam suatu sistem basisdata berbasis isi pengambilan citra, pengguna dapat memberikan sketsa bentuk objek yang akan diambil pada sistem. Jelas, sketsa tidak akan sama persis dengan objek yang berhubungan dalam database citra. Tujuan kami dalam bagian ini adalah untuk memungkinkan prosedur pencocokan template untuk menjelaskan penyimpangan antara template referensi dan pola pengujian yang sesuai pada citra. Dalam diskusi kita, kita akan mengasumsikan bahwa template referensi yang tersedia dalam bentuk larik citra yang berisi informasi batas citra obyek (kontur). Artinya, kita akan fokus pada informasi bentuk saja. Ekstensi menggabungkan informasi lebih lanjut, misalnya, tekstur, juga mungkin. Mari kita tunjukkan referensi array template citra sebagai r (i, j). Hal ini juga dikenal sebagai prototipe. Ide dasar dibalik prosedur deformable template matching sederhana: merusak prototipe dan memproduksi varian cacat yang diubah tersebut. Dari sudut pandang matematis sebuah deformasi terdiri dari penerapan sebuah parameter transformasi Tξ pada r(i,j) untuk menghasilkan T versi terdeformasi Tξ ([r (i, j)]. Nilai-nilai yang berbeda dari parameter vektor ξ mengacu pada versi yang berbeda. Dari kumpulan varian prototype yang terdeformasi bisa dihasilkan, akan ada satu pasangan yang “terbaik” sesuai dengan pola pengujian. Kebaikan kecocokan diukur dengan biaya, yang akan kita sebut sebagai pencocokan energi Em (ξ). Jelas, tujuannya adalah untuk memilih ξ (sehingga Em(ξ)) adalah minimum. Namun, hal ini tidaklah cukup. Jika, misalnya, set parameter optimal adalah sedemikian rupa sehingga sesuai template terdeformasi telah berubah bentuk sedemikian rupa sehingga sedikit menyisakan kemiripan dengan prototipe asli, maka metode tersebut akan tidak bermakna. Jadi, satu lagi istilah yang harus diperhitungkan dalam proses optimisasi. Hal ini adalah mengukur biaya ”deformasi” yang prototipe perlukan untuk menjalani agar sesuai dengan pola pengujian. Kita akan sebut istilah biaya ini sebagai deformasi energi Ed (ξ). Kemudian parameter vektor yang optimal dihitung, sehingga
Dengan kata lain, orang bisa berpikir dari kurva batas prototipe dibuat dengan karet. Kemudian dengan bantuan pensil kita merusak bentuk kurva karet untuk mencocokan dengan pola pengujian. Semakin kita merusak bentuk bentuk prototipe, semakin tinggi pula energi yang kita harus keluarkan untuk itu. Energi, dihitung dengan Ed (ξ), tergantung pada bentuk
prototipe. Artinya, itu adalah properti intrinsik prototipe dan hal ini adalah alasan bahwa hal itu juga dikenal sebagai energi internal. Istilah lain energi, Em (ξ), tergantung pada data input (citra pengujian) dan kita biasa menyebutnya sebagai eksternal energi. Parameter vektor yang optimal ξ dipilih sehingga tawar-menawar terbaik antara kedua istilah energi tercapai. Kadangkala, faktor pembobotan C digunakan untuk memberikan preferensi untuk salah satu dari dua syarat dan ξ dihitung sehingga
Oleh karena itu, untuk menerapkan prosedur di atas dalam satu praktek harus memiliki pembuangan bahan sebagai berikut:
Sebuah prototipe Sebuah prosedur transformasi untuk merusak prototipe Jangka waktu dua fungsi energi
Pemilihan Prototipe Hal ini seharusnya dipilih dengan cermat sehingga merupakan perwakilan (khas) dari berbagai instansi di mana obyek ini diharapkan muncul dalam praktek. Di satu sisi, prototipe harus menyandikan karakteristik “bentuk utama” yang sesuai “kelas bentuk”. Transformasi Deformasi Ini terdiri dari satu set operasi parametrik. Ambil (x, y) menjadi koordinat (kontinu) sebuah titik dalam sebuah citra 2D. Tanpa kehilangan keumuman, kita anggap bahwa citra didefinisikan dalam persegi [0,1]x[0,1]. Kemudian setiap titik (x,y) adalah dipetakan menggunakan suatu fungsi pemetaan kontinyu, sebagai
Untuk array citra diskrit sebuah langkah kuantisasi diperlukan setelah transformasi. Fungsi yang berbeda dapat digunakan untuk melakukan pemetaan di atas. Sebuah set yang telah berhasil digunakan dalam praktek adalah ([Amit 91])
Gambar 8.13 (a) Suatu pola referensi, (b) kontur yang digunakan sebagai prototipe, dan (c), (d), (e) tiga dari varian yang cacat.
untuk nilai terpilih yang tepat dari M, N. Konstanta normalisasi αMN dapat diambil sebagai
Fungsi dasar lain bisa juga digunakan, seperti splines atau wavelet. Gambar 8.13 menunjukkan prototipe untuk sebuah objek dan tiga versi cacat yang diperoleh untuk kasus paling sederhana dari model transformasi dalam (8.13)-(8.16),yaitu M = N = 1. Energi Internal Ini harus minimum untuk tanpa deformasi, yaitu untuk ξ = 0. Sebuah pilihan yang masuk akal, berkaitan dengan fungsi transformasi dipertimbangkan di atas, adalah
Energi Eksternal Di sini sekali lagi beberapa pilihan yang mungkin, mengukur kebaikan kesesuaian antara pola pengujian dan masing-masing varian template cacat. Sebagai contoh, untuk posisi tertentu, orientasi, dan skala template cacat, istilah energi ini dapat diukur dalam hal jarak setiap titik
di kontur template terdeformasi dari titik terdekat dalam kontur citra pengujian, I. Salah satu cara untuk mencapai tujuan ini adalah melalui fungsi energi sebagai berikut:
dimana θ adalah parameter vektor yang menentukan posisi, orientasi, dan skala dan Nd jumlah piksel kontur dari template yang cacat, dan
Dimana ρ konstan dan (δi, δj) adalah perpindahan dari piksel (i, j) dari template terdeformasi dari titik terdekat pada citra pengujian. Pada [Jain 96] arah informasi juga dimasukkan ke dalam biaya. Keterangan Satu dapat tiba di (8,10) dengan cara yang lebih sistematis melalui argumen probabilistik, yaitu, dengan berusaha untuk memaksimalkan kepadatan aposteriori probabilitas (ξ,θ) diberikan array citra pengujian, yaitu,
dimana aturan Bayes sudah bekerja. Dalam kerangka ini, (8,17) menghasilkan jika kita menganggap bahwa berbagai parameter adalah statistik independen dan , terdistribusi normal, misalnya, p (ξ) = N (0, σ2). Varian yang lebih tinggi dari σ2 lebih lebar dari kisaran nilai-nilai yang terjadi dengan probabilitas tinggi. Untuk mendapatkan (8,18) - (8.19) model
diadopsi, di mana a adalah konstan ternormalisasi [Jain 96]. Biaya dalam (8.10) adalah fungsi nonlinier dan meminimalkan yang dapat dicapai melalui skema optimasi nonlinier. Selain kompleksitas, utama menggambar-kembali adalah bahaya di mana-mana bahwa algoritma akan terjebak dalam minimum lokal. Dalam [Jain 96] sebuah prosedur telah disampaikan bahwa membangun dengan metodologi turunan gradien (Lampiran C) Idenya adalah untuk mengadopsi pendekatan multi resolusi iteratif dan menggunakan nilai ρ yang lebih besar dalam (8.19) untuk level kasar dan nilai yang lebih kecil untuk yang lebih halus. Prosedur ini tampaknya membantu algoritma untuk menghindari minimum lokal, dengan biaya komputasi yang terjangkau. Metodologi yang kita dijelaskan dalam bagian ini mnerupakan milik kelas yang lebih umum dari teknik deformable template matching, yang dibangun di sekitar prototipe yang tersedia. Ini bukan hanya jalur yang tersedia. Kelas lain dari model yang terdeformasi berasal dari deskripsi analitik dari bentuk prototipe, dengan menggunakan satu set parameter bentuk geometris, misalnya, elips atau kurva parabola. Untuk mempelajari isu-isu yang lebih dalam pembaca bisa merujuk pada artikel review [Jain 98, McIn 96, Cheu 02] dan referensi di dalamnya. [Widr 73, Fisc
73] tampaknya merupakan upaya pertama memperkenalkan konsep model deformable dalam visi komputer. Dalam konteks pengenalan pola, diberikan pola pengujian yang tidak diketahui, kita berusaha untuk melihat yang mana dari dari satu set prototipe yang berbeda yang dikenal oleh pencocokan terbaik. Untuk masing-masing prototipe, cacat varian terbaik dipilih berdasarkan pada biaya energi minimum. Prototipe yang menang adalah yang terbaik adalah yang cacat hasil varian dalam keseluruhan biaya energi minimum.
