Kali ini pakai bahasa Indonesia aja ya, the scientific english is still too hard for me, haha *padahal males*.
Di postingan sebelumnya saya membahas sedikit tentang homography, kali ini saya coba elaborasi sedikit ya.
Homo-what?
Pemetaan antara vektor \(\overrightarrow{p}\) menuju \(\overrightarrow{q}\) dapat dinyatakan dengan
\[\overrightarrow{q} = H \overrightarrow{p} \]
dimana \(H\) adalah matrix dengan dimensi 3x3. Pemetaan tersebut dinamakan
homography.
Intinya adalah terdapat sebuah matrix berukuran 3x3 (
homograph matrix) yang bisa memetakan dari satu titik awal ke titik akhir. Homography berguna bagi proses
image rectification (rektifikasi gambar), yakni proses koreksi spasial pada citra.
Menurut pak
David Kriegman di mata kuliah Computer Vision 1 penjelasan homography adalah sebagai berikut:
persamaan homography dapat dinyatakan sebagai
\[X_2 = HX_1\]
Jika dituliskan elemen per elemen, persamaan homography dapat kita tuliskan sebagai berikut
\[
\begin{bmatrix}
x_2 \\
y_2 \\
z_2 \\
\end{bmatrix}
=
\begin{bmatrix}
H_{11} & H_{12} & H_{13} \\
H_{21} & H_{22} & H_{23} \\
H_{31} & H_{32} & H_{33} \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
y_1 \\
z_1 \\
\end{bmatrix}
\]
Pada ruang dua dimensi tidak terdapat kordinat Z, maka nilai x dan y dapat dinyatakan sebagai \(x'_2 = x_2/z_2\) , \(y'_2 = y_2/z_2\), dan \(z = 1\). Dari justifikasi ini nilai \(x'_2\) dan \(z'_2\) dapat dinyatakan sebagai berikut
\[ x'_{2} = \frac{H_{11}x_{1} + H_{12}y_{1} + H_{13}z_{1}}{H_{31}x_{1} + H_{32}y_{1} + H_{33}z_{1}} \]
\[ y'_2 = \frac{H_{21}x_{1} + H_{22}y_{1} + H_{23}z_{1}}{H_{31}x_{1} + H_{32}y_{1} + H_{33}z_{1}} \]
atau dapat ditulis sebagai
\[ x'_{2}(H_{31}x_{1} + H_{32}y_{1} + H_{33}z_{1}) = H_{11}x_{1} + H_{12}y_{1} + H_{13}z_{1} \]
\[ y'_{2}(H_{31}x_{1} + H_{32}y_{1} + H_{33}z_{1}) = H_{21}x_{1} + H_{22}y_{1} + H_{23}z_{1} \]
dan dikelompokkan menjadi persamaan linear berikut
\[ H_{11}x_{1} + H_{12}y_{1} + H_{13}z_{1} - x'_{2}(H_{31}x_{1} + H_{32}y_{1} + H_{33}z_{1}) = 0 \]
\[ H_{21}x_{1} + H_{22}y_{1} + H_{23}z_{1} - y'_{2}(H_{31}x_{1} + H_{32}y_{1} + H_{33}z_1) = 0 \]
Persamaan tersebut dapat dinyatakan kembali sebagai berikut
\[a^T_xh = 0\]
\[a^T_yh = 0\]
dimana
\[h = (H_{11},H_{22},H_{23},H_{31},H_{32},H_{33})^T\]
\[a_x = (x_{1},y_{1},1,0,0,0,-x'_{2}x_{1},-x'_{2}y_{1},-x'_{2})^T\]
\[a_x = (0,0,0,x_{1},y_{1},1,-y'_{2}x_{1},-y'_{2}y_{1},-y'_{2})^T\]
Dengan persamaan tersebut kita dapat menyatakan persamaan linear untuk permasalahan homography sebagai:
\[Ah = 0\]
dimana
\[A = \begin{pmatrix}
a^T_x1\\
a^T_y1\\
.\\
.\\
.\\
a^T_xn\\
a^T_yn
\end{pmatrix}
\]
matriks \[A\] ini dinamakan
matriks estimasi.
Oke, kita bisa masukkin variabel-variabel tadi ke \(Ah = 0\). Terus bagaimana cara menentukan nilai H nya? Untuk menyelesaikannya kamu bisa menggunakan
Singular Value Decomposition
Singular Value Decomposition
Sejauh yang saya tangkap dari pembahasan di
MIT OCW dan
tutorial SVD dari pak Kirk Baker, inti dari SVD adalah sebuah proses untuk memecah sebuah matriks menjadi 3 matriks. Rumusan umumnya adalah sebagai berikut
\[A_{mn} = U_{mm} S_{mn} V^T_{nn}\]
Tutorial yang sangat lengkap dan jelas mengenai SVD ada di tutorialnya pak Kirk Baker. Bagi rekan-rekan yang ingin belajar lebih lengkap tentang SVD silahkan mengunjungi tutorial tersebut.
\(S\) merupakan matriks diagonal. Nilai \(S_{mn}\) yang paling kecil akan berkorespondensi dengan salah satu kolom pada matriks \(V^T\). Kolom tersebut berisi nilai-nilai \(H\) yang kita inginkan sebagai matriks homograph.
Pada penjelasan oleh pak David Kriegman disebutkan pula bahwa nilai \(V\) memiliki hubungan dengan nilai eigenvector dari \(A^TA\). Penjelasannya saya masih belum begitu paham kenapa, tapi sejauh yang saya tangkap hal ini dibuktikan dengan pendekatan
squared error. Penjelasan beliau bisa dibaca di halaman 2 dan 3.
Hubungan \(V\) dan nilai eigenvector dari \(A^TA\) tersebut memungkinkan penghitungan diringkas dengan mencari nilai eigenvalue terkecil dari eigenvector \(A^TA\) dan mengambil kolom dari \(V\) berdasarkan posisi nilai eigenvalue tersebut.
Kode implementasinya bisa kamu lihat di project The-Imp berikut.
Yang saya kerjakan
Saya pun mengimplementasikan homography tersebut ke program ekstraksi huruf-huruf. Saya pun menemukan masalah.
Seperti diketahui, rumus yang kita ketahui adalah \(X_2 = HX_1\). Jika kita menggunakan rumus ini berarti kita memetakan dari \(X_1\) ke \(X_2\), padahal pertanyaannya adalah
"saat di sebuah titik pada \(x_2\), dimanakah titik \(x_1\) yang dikalikan matriks \(H\)?"
Dari pertanyaan tersebut padahal nilai yang diketahui adalah \(H\) yang merupakan matriks homograph dan \(X_2\) yang merupakan setiap titik akhir yang diinginkan. Jika tetap dilakukan dengan rumus awal maka akan terjadi pembulatan yang akhirnya terbentuk bagian yang kosong.
 |
| garis-garis hitam karena pembulatan. Garis ini adalah bagian gambar yang tidak terpetakan. |
Berarti apa yang harus kita lakukan? Yak! Invers!
\[X_2H^{-1} = X_1\]
Saya kemudian mengimplementasikan rumus ini ke program. Matriks estimasi yang saya inputkan adalah titik kontrol pada form. Dan hasilnya cukup memuaskan *fyuuuh*. Akhirnya euy, semingguan belajar tentang homography *jadi curhat*.
Oh iya, btw saya pakai library
Apache Commons Math untuk proses matriks seperti transpose, invers, dan mencari nilai eigen. Kok gitu? Otak saya masih belum cukup professor, heheh.
Eksperimen
Oke deh. Sekarang kembali ke skripsi. Saya menginginkan untuk melakukan ekstraksi di form seperti ini.
Gambar di atas adalah contoh yang bagus untuk jenis form yang memiliki kasus kemiringan dan proyeksi.
Uji Coba 1
Di postingan sebelumnya saya sempat memberitahu saya menggunakan affine transformation berupa
shearing agar titik-titik kontrol dapat sejajar. Hasilnya
hanya dengan shearing adalah sebagai berikut
 |
| Rektifikasi hanya dengan shearing |
Seperti dilihat angka 9,8,7, 6, dan 5 cukup terpotong
Uji Coba 2
Uji coba ini
hanya menggunakan homography. Pada angka 9, 8, 7, 6, dan 5 lebih baik dan cukup terlihat.
Namun permasalahannya adalah metode homography tidak membuat titik-titik kontrol sejajar seperti yang saya harapkan. Artinya jika form terlalu miring maka tidak dapat dideteksi.
 |
| Rektifikasi hanya dengan homography |
Uji Coba 3
Percobaan kali ini menggunakan homography dan shearing. Ternyata hasilnya lebih baik, bahkan sebagian besar border hilang.
 |
| Rektifikasi dengan homography dan shearing |
Dengan metode ini form yang cukup miring pun bisa ditangani. Saya belum menghitung kemiringan berapa derajat. Seingat saya metode hanya dengan homography tidak sanggup saat kemiringan mengakibatkan titik kontrol tidak melewati titik-titik penanda kolom/baris jika ditarik garis lurus.
[UPDATE 7-Oct-2014] Uji Coba 4
Saat implementasi Homography ternyata saya salah kordinat yang dikalikan. Saya salah memasukkan koordinat x dan y, keduanya terbalik! Ternyata hanya dengan homography hasilnya sangat bagus!
 |
| Woow! Align perfectly! |
Saya mengetahui keanehan ini saat memperhatikan uji coba 3 terdapat karakter "d koreksi" terpotong (di bawah angka 7 pada gambar yang sudah diekstraksi). Karena khawatir maka saya bereksperimen dengan melakukan pemindaian menggunakan form yang penuh dengan grid.
 |
| form yang sengaja saya beri transformasi proyektif agar bisa dilihat hasil rektifikasi nya |
Berikut percobaan dengan hanya homography. Di ujung gambarnya keluar dari grid yang diinginkan
 |
| percobaan cek semua grid dengan homography |
Berikut percobaan dengan shear kemudian homography. Ternyata salah juga!
 |
| percobaan cek semua grid dengan shear kemudian homography |
Kemudian saya melakukan debugging dan menguji kembali percobaan untuk mengecek semua grid. Hasil dengan hanya menggunakan homography ternyata sangat memuaskan!!
 |
| Aku terpuaskan!!! |
Jadi kesimpulannya homography dan rektifikasi adalah sahabat terbaik. Ciye ciye.
Skripsinya
Ini kok eksperimen mulu sih? Skripsinya kapan dikerjain woy!
Ya atuhlah...
pan skripsi teh eksperimen, kumaha ih.
Jadi kemarin saya bimbingan dengan dosen pembimbing saya. Karena saya khawatir dengan program saya yang belum punya arahan yang pasti maka saya menunjukkan mockup tampilan program yang akan dibuat. Ternyata lumayan dapat banyak pencerahan, salah satunya adalah
"Kerjakan diagram dulu baru ngoding"
*uhuk*
Ini penyakit yang sudah terlalu dibiasakan. Ngoding dulu akhirnya acakadut. Berarti sekarang saya mengerjakan doktek (dokumen teknis) dulu sembari revisi bab 1.
Terus?
That's it! Mari kita lanjut ngerjain skripsi lagi. Ulalala. Ulalala. Ulala.
