Deteksi Marker untuk Aplikasi Augmented RealityDiposkan oleh Corn den Otter pada 2 April 2010Tag (s): Hobbyprojecten , Artikel , Open Source , Desktop [Update] Kami menerima banyak komentar meminta untuk kode sumber. Pada saat ini kami sangat sibuk, jadi sayangnya kita tidak punya waktu untuk bersih-bersih kode deteksi penanda.Karena ini telah terjadi untuk beberapa waktu sekarang, kita telah meng-upload kode (di bawah GPL). Anda bebas untuk mendownload kode dalam file zip di akhir posting blog ini. Kode ini hanya prototipe: hampir tidak dioptimalkan dan membutuhkan banyak bersih-up (dan manajemen memori yang lebih baik ;-)). Yang mengatakan: itu milikmu untuk bermain-main dengan. Good luck dengan itu dan menikmati [/ update]! Pada Infi kita memiliki sesuatu yang mirip dengan 20 Persen Faktor Google. Jika Anda memiliki gagasan besar atau sesuatu yang Anda ingin tahu lebih banyak tentang, Anda dapat menghabiskan waktu di sana selama jam kerja. Subjek saat ini kami sedang tertarik adalah augmented reality. Kami ( Corn dan Reinder ) mulai dengan mencari kerangka AR yang ada dan menemukan satu proyek open source yang menarik: ARToolkit (ditambah) . Toolkit ini ditulis dalam C / C + + tapi juga porting ke flashdisk en digunakan dalam demo AR yang dapat Anda temukan di internet. Sayangnya, algoritma yang digunakan untuk mendeteksi penanda dalam toolkit ini memiliki beberapa kelemahan:

y y y

Hal ini tidak terlalu cepat. Hal ini tidak sangat baik dalam mendeteksi penanda memiliki tepi atau sudut (parsial) tersumbat. Hal ini didasarkan pada algoritma thresholding, dan karenanya tidak melakukan sangat baik di bawah kondisi yang berubah atau tidak homogen petir.

Ada beberapa penerus dari ARToolkit, menggunakan algoritma deteksi tepi berbasis (sepertiARTag dan Studierstube Tracker ) tetapi ini adalah sumber tertutup perpustakaan. 'Deteksi Marker untuk Aplikasi Augmented Reality' Pada tahun 2008, Martin Hirzer menulis [1] , sebuah artikel yang menjelaskan keunggulan berdasarkan penanda-algoritma deteksi. Kami memutuskan untuk mengimplementasikan algoritma ini di C + +. Saat ini kode kita hanya prototipe. Akhirnya (setelah pembersihan a) kita akan open source implementasi kami dan / atau menyumbangkannya ke basis kode ARToolkit. Dalam posting blog ini kita menjelaskan algoritma diimplementasikan. [Update] Pada akhir posting ini Anda dapat menemukan video dari deteksi penanda dalam tindakan.

AlgoritmaLangkah 1: Bagilah gambar di daerah

Pertama gambar dibagi dalam daerah kecil 40x40 pixel dan masing-masing daerah dibagi menjadi garis scan horizontal dan vertikal 5 pixel terpisah. Para 3 langkah selanjutnya dijalankan terpisah di daerah-daerah yang meningkatkan kinerja secara dramatis.

Langkah 2: Mendeteksi edgels di daerahKemudian turunan dari Gaussian convolved pada setiap garis scan untuk memperkirakan komponen intensitas dari gradien sepanjang scanline tersebut.

Ini turunan Gaussian digunakan untuk mendeteksi tepi hitam / putih pada gambar. Turunan Gaussian berdasarkan convolving gambar dengan filter dihargai kecil, dipisahkan, dan integer dalam arah horisontal dan vertikal dan karena itu relatif murah dalam hal perhitungan. Maxima lokal sepanjang scanlines kuat dari ambang tertentu (untuk semua tiga jalur warna!) Dianggap edgels. Kernel Gaussian derivatif yang digunakan, diberikan oleh:

[-3 -5 0 5 3] A *Jika edgel terdeteksi, operator Sobel digunakan untuk menentukan orientasi edgel tersebut.Operator sobel diberikan oleh:

Orientasi tersebut kemudian disimpan dengan edgel tersebut. Pada gambar di atas, titik-titik hijau edgels berorientasi horisontal dan yang biru adalah edgels berorientasi vertikal.

Langkah 3: Cari segmen di daerahSetelah deteksi edgels, algoritma RANSAC-kerapu digunakan untuk membangun segmen garis di setiap daerah [2] .

RANSAC adalah singkatan untuk "Konsensus sampel acak". Ini adalah algoritma untuk menemukan kelompok "inliers", yaitu poin yang dapat dipasang ke dalam garis. Algoritma RANSAC singkatnya: 1. Memilih secara acak 2 poin dari daerah yang sama, yang orientasi yang kompatibel dengan garis yang menghubungkan dua titik, untuk berhipotesis baris. 2. Jumlah poin yang mendukung setiap baris dihitung. Untuk dipertimbangkan bagian dari garis titik yang harus terletak dekat dengan itu dan memiliki orientasi yang kompatibel dengan baris. 3. Langkah 1 dan 2 diulang ~ 25 kali sebelum segmen ditemukan. 4. Garis dengan dukungan yang cukup (setidaknya 4 segmen) dianggap garis terdeteksi.Langkah 1 sampai 3 diulang sampai semua baris tersebut telah ditemukan. Lebih lanjut tentang RANSAC: http://en.wikipedia.org/wiki/RANSAC . Karena kita tahu orientasi edgels dari langkah 2, kita dapat memberikan linesegments orientasi.Pada gambar di atas, segmen dibangun ditampilkan sebagai panah merah dan hijau.

Langkah 4: segmen Gabung ke barisDalam langkah ini segmen yang bergabung untuk baris.

Dua segmen digabung jika: 1. Orientasi yang kompatibel. 2. Segmen yang dekat satu sama lain. 3. Jika piksel sepanjang garis antara dua segmen berada di tepi, dengan menggunakan kriteria deteksi yang sama edgel seperti yang digunakan dalam langkah 2. Pertama semua segmen diuji di wilayah mereka sendiri dengan menggunakan algoritma ini.Ketika semua segmen yang mungkin digabung di daerah mereka sendiri, operasi yang sama diulang untuk semua segmen di seluruh gambar. Garis digabung ditampilkan sebagai panah merah / hijau pada gambar di atas.

Langkah 5: Perpanjang garis sepanjang tepiDalam langkah ini garis diperluas sepanjang tepi.

Karena kita memindai pixel hanya pada garis scan 5 pixel terpisah, itu pasti bahwa garis-garis merger tidak sesuai pada seluruh panjang dari tepi penanda. Jadi pada langkah ini kita memperluas baris piksel dideteksi oleh piksel sampai kita mendeteksi sudut: 1. Memperpanjang setiap akhir baris dan memeriksa apakah setiap pixel pada tepi, dengan menggunakan kriteria deteksi yang sama edgel seperti yang digunakan dalam langkah 2.Lakukan ini sampai kita memukul piksel yang bukan tepi. 2. Ambil piksel beberapa piksel lebih lanjut. Jika piksel ini adalah 'putih', kita mungkin memiliki menemukan sebuah sudut hitam pada penanda putih. Garis diperpanjang ditampilkan sebagai panah kuning pada gambar di atas. Pada langkah 6 dan 7 baris hanya dengan setidaknya salah satu sudut yang digunakan.

Langkah 6: Jaga baris dengan sudutJauhkan baris dengan sudut.

Langkah 7: Cari spidolAkhirnya, kami mencoba untuk menemukan semua penanda dalam gambar.

Untuk mendeteksi penanda dalam gambar, kita mencoba untuk menemukan rantai dari 3 sampai 4 baris. Rantai adalah daftar bidang di mana akhir dari salah satu baris hits awal lain.

Setelah menemukan rantai seperti itu, kita hanya ingin menyimpan rantai yang membentuk persegi panjang sebuah jam meja bijaksana. Rantai ini akan memiliki kulit hitam 'di dalam' dan mungkin spidol. Mengetahui orientasi garis, produk silang untuk setiap dua segmen garis yang berurutan dalam rantai yang digunakan untuk memeriksa kondisi ini. Setelah menemukan semua penanda, untuk penanda setiap 4 persimpangan dari garis-garis dalam rantai dianggap sudut. Menghitung posisi sudut oleh garis-persimpangan memberikan algoritma yang kuat. Bahkan jika hanya 3 baris terdeteksi dan / atau sudut yang tersumbat, penanda akan benar terdeteksi sebagian besar waktu. Pada gambar di atas, semua penanda terdeteksi ditampilkan sebagai persegi panjang merah.Perhatikan penanda benar terdeteksi di bagian bawah gambar, meskipun satu sisi sebagian tersumbat oleh pensil. Sekarang kita memiliki koordinat penanda terdeteksi. Langkah berikutnya akan mengidentifikasi penanda dan membedakan mereka dari satu sama lain dalam rangka untuk menggunakan algoritma ini dalam aplikasi augmented reality, tapi itu akan menjadi blog berikutnya :-)