Kami yakin bahwa hari ini tidak ada satu pun pembaca Habr yang tidak terbiasa dengan kode QR. Barcode dua dimensi ini ada di mana-mana. Adalah logis bahwa di dunia ada banyak alat yang memungkinkan untuk menambahkan kode QR ke proyek Anda dengan beberapa tingkat efisiensi. Intinya adalah bahwa efisiensi yang disebutkan ini secara langsung tergantung pada kualitas alat yang digunakan untuk mengenali kode QR. Dan inilah plug klasik: Anda dapat memecahkan masalah (sangat) dengan baik dan (sangat) mahal, atau Anda dapat secara gratis dan entah bagaimana. Apakah mungkin untuk memodifikasi gratis sehingga tetap memecahkan masalah dengan baik? Jika tertarik, lihat di bawah kucing.Mengenali kode QR dalam sebuah foto adalah tugas yang baik dari visi mesin. Pertama, dalam tugas tersebut, sebuah objek diselidiki, yang awalnya dirancang khusus untuk pengakuan "nyaman". Kedua, tugas itu sendiri dibagi menjadi beberapa subtugas independen yang dapat dimengerti: lokalisasi kode QR, orientasi kode QR dan secara langsung mendekode kode QR. Ternyata domain publik telah lama memiliki perpustakaan yang baik yang dapat menyelesaikan dua masalah terakhir: orientasi dan decoding kode QR. Satu masalah: untuk decoding berkualitas tinggi, perpustakaan seperti itu mengharapkan gambar biner yang baik secara langsung dari barcode untuk menjadi input. Sebaliknya, sedikit perhatian diberikan pada tugas pelokalan barcode dalam gambar.Dalam pengalaman kami, semakin akurat Anda melokalisasi objek pengenalan, semakin mudah untuk memilih alat pra-pemrosesan yang tepat dan, pada kenyataannya, mengenalinya. Oleh karena itu, jika Anda ingin meningkatkan kualitas pengakuan kode QR di proyek Anda, maka mulailah dengan modernisasi metode untuk melokalkan kode QR. Memang, bahkan jika Anda nantinya perlu membuat binariasi sebuah gambar, itu jauh lebih efisien (baik dari sudut pandang komputasi maupun kualitatif) untuk membuat binari suatu wilayah dengan barcode daripada keseluruhan gambar aslinya.Pada artikel ini, kami akan memberi tahu Anda cara mudah meningkatkan kualitas lokalisasi kode QR menggunakan metode pemrosesan gambar klasik, serta memberikan karakteristik numerik dari efektivitas algoritma yang diusulkan.Kita akan berbicara tentang cara asli melokalkan kode QR pada gambar, menggunakan metode Viola dan Jones yang dimodifikasi sebagai dasarnya.Catatan informasi tentang topik artikel
Di bagian ini, kami menjelaskan fitur-fitur utama dari kode QR yang digunakan untuk membangun metode pelokalan, serta deskripsi singkat dari versi asli metode Viola dan Jones.Kode QR
Kode QR (kependekan dari Quick Response Code) adalah barcode dua dimensi yang dikembangkan di Jepang pada pertengahan 90-an untuk industri otomotif. Karena kemampuan untuk membaca dengan cepat dan kapasitas yang lebih besar dibandingkan dengan barcode linear, sistem QR-code telah menjadi populer di seluruh dunia dalam berbagai bidang kehidupan.Tidak seperti barcode linier standar, yang biasanya dipindai oleh perangkat keras, kode QR sering dipindai oleh kamera. Struktur kode QR sepenuhnya dijelaskan dalam ISO / IEC 18004 (Standar ISO / IEC 18004). Untuk membangun algoritme pengenalan yang kuat untuk gambar tersebut, kode QR memiliki beberapa titik referensi yang membentuk pola fungsi: tiga kotak di sudut gambar barcode (disebut pola pencari) dan kotak sinkronisasi yang lebih kecil di seluruh gambar barcode (disebut pola pelurusan) . Poin tersebut memungkinkan Anda untuk menormalkan ukuran gambar dan orientasinya.
Ara. Struktur kode QR
Meskipun secara visual semua kode QR mirip satu sama lain, salinan kode QR yang berbeda, tergantung pada jumlah data yang disandikan, dapat memiliki tata letak elemen internal yang berbeda. Selain itu, apa yang disebut perancang kode QR sangat populer, di mana alih-alih sebagai bagian dari informasi tambahan yang menjamin pengakuan barcode berkualitas tinggi, elemen grafik pihak ketiga digunakan (logo, emblem, prasasti, dll.). Semua fitur kode QR ini harus diperhitungkan ketika membangun metode untuk pelokalan dan pengenalan kode QR.
Ara. Pilihan kode QR yang valid berbeda
Metode Viola dan Jones
Hanya malas pada Habré yang belum menulis tentang metode Viola dan Jones. Bahkan kami di blok kami melakukan ini beberapa kali (misalnya, di sini , di sini atau di sini ). Dan tetap, kami menganggap perlu untuk secara singkat, secara harfiah dalam dua paragraf, untuk mengatakan apa itu.Metode deteksi objek Viola dan Jones dikembangkan untuk mencari wajah dalam gambar secara real time. Metode ini mengurangi masalah deteksi menjadi masalah klasifikasi biner di setiap titik gambar, mis., Untuk setiap wilayah gambar persegi panjang yang diambil dengan semua jenis pergeseran dan skala, hipotesis tentang keberadaan objek yang diinginkan di wilayah tersebut diperiksa menggunakan classifier yang sudah dilatih sebelumnya.Sebagai ruang fitur, metode Viola dan Jones menggunakan fitur persegi panjang Haar, yang nilainya dihitung sebagai selisih antara jumlah kecerahan piksel dari area gambar di dalam persegi yang berdekatan. Untuk secara efektif menghitung nilai fitur Haar, gambar terintegrasi digunakan, yang juga dikenal dalam literatur di bawah istilah tabel area-dijumlahkan. Klasifikasi "lemah" biner h ( x ): Χ → {-1, + 1}, biasanya disajikan sebagai pohon pengakuan dengan satu cabang: di
mana θ dan p- nilai ambang atribut dan paritas dari classifier, masing-masing. Selanjutnya, dengan menggunakan metode pembelajaran mesin AdaBoost, classifier "kuat" dibangun sebagai superposisi linear dari pengklasifikasi "lemah" di atas. Kecepatan tinggi metode Viola dan Jones dipastikan melalui penggunaan kaskade pengklasifikasi "kuat", yang memungkinkan melokalkan wilayah gambar "kosong" (bebas objek) dalam sejumlah kecil perhitungan.Algoritma deteksi kode QR
Saat membangun metode untuk melokalkan kode QR, kami mengandalkan fitur tugas berikut. Pertama, metode yang dikembangkan harus memiliki kinerja tinggi untuk digunakan dalam sistem pengenalan yang beroperasi secara real time. Kedua, metode ini harus tahan terhadap distorsi yang diizinkan dari barcode pada gambar. Ketiga, metode ini harus memperhitungkan semua variabilitas kode QR yang ada.Seperti disebutkan di atas, kami telah memilih metode Viola dan Jones sebagai metode mendasar. Metode ini telah membuktikan dirinya dalam berbagai tugas mencari objek yang kaku, sementara metode ini memberikan kinerja yang diperlukan. Tetapi dalam versi asli, metode Viola dan Jones tidak dapat digunakan karena alasan berikut:- metode klasik Viola dan Jones menggunakan keluarga atribut Haar yang "menekankan" fitur tekstur objek, dan dalam kasus kami, meskipun kode QR terdiri dari barcels hitam dan putih, distribusinya sangat berbeda dari barcode ke barcode;
- metode klasik Viola dan Jones dirancang untuk jenis deteksi objek yang sama dalam orientasi tertentu, yang juga tidak diamati dalam tugas kita.
Agar metode Viola dan Jones dapat diterapkan untuk memecahkan masalah, kami menggunakan keluarga asli fitur batas dan classifier tingkat tinggi dalam bentuk pohon keputusan. Modifikasi pertama akan memungkinkan pemfokusan pada fitur batas objek yang dipelajari, dan bukan pada tekstur. Modifikasi kedua akan memungkinkan Anda untuk membangun classifier tunggal yang dapat mendeteksi objek variabel. Selanjutnya, kami akan memberi tahu Anda sedikit lebih banyak tentang setiap modifikasi.Tanda-tanda Gradient dari Haar.
Untuk membangun detektor kode QR yang efektif, kami menggunakan keluarga khusus fitur gradien [1]. Tanda-tanda ini adalah tanda-tanda persegi panjang Haar, dihitung di atas peta batas terarah, yang secara signifikan dapat meningkatkan kekuatan generalisasi mereka.Peta batas terarah adalah gambar modulus gradien, yang juga memperhitungkan arah kemiringan yang lebih disukai pada titik ( x , y ), yang didefinisikan sebagai diskritisasi sudut perbatasan menjadi arah horizontal, vertikal, + 45 ° dan –45 °. Untuk membangun detektor kode QR, kami menggunakan dua jenis peta batas terarah: peta batas lurus dan peta wajah diagonal.Biarkan gambar asli f ( x ,y ). Kemudian Anda dapat menghitung nilai perkiraan turunan sepanjang arah horizontal dan vertikal menggunakan operator Sobel:
Selain itu, menggunakan g x dan g y , Anda dapat menghitung arah gradien pada setiap titik gambar:
Peta garis lurus terutama terdiri dari batas horizontal dan vertikal dan dihitung sebagai berikut:
Peta perbatasan diagonal berisi terutama perbatasan di sepanjang diagonal dan dihitung sebagai berikut:
Di atas peta batas terarah yang dibangun (diagonal atau lurus), tanda Haar persegi panjang dihitung. Berbeda dengan fitur Haar klasik, fitur batas seperti itu menggeneralisasikan objek dengan baik yang mengandung sejumlah besar batas.
Ara. Ilustrasi peta batas terarah: (a) gambar asli kode QR, (b) peta garis lurus, (c) gambar kode QR yang dirotasi (d) peta batas diagonal dari kode QR yang dirotasi
Pohon penentu pengklasifikasi yang kuat
Pohon pengklasifikasi yang kuat [2] adalah sejenis pohon keputusan biner: simpul pohon adalah pengklasifikasi yang kuat, di tepi kanan yang ada subwindows yang mungkin berisi objek, dan di sebelah kiri - yang tidak dikenali sebagai objek, masing-masing. Jawaban akhir hanya diberikan di daun. Klasifikasi cascading klasik yang dijelaskan dalam karya asli Viola dan Jones, pada kenyataannya, adalah classifier pohon yang hanya berisi satu output "positif" (daun) dan banyak output "negatif".Dalam [2] ditunjukkan bahwa setiap jalur dari root ke node terendah dari classifier pohon dapat direpresentasikan sebagai kaskade di mana individu pengklasifikasi kuat masuk dengan jawaban terbalik. Berkat ini, dimungkinkan untuk membangun algoritma pembelajaran untuk classifier pohon, yang menggunakan prosedur pelatihan classifier kaskade klasik untuk mengajarkan jalur individu.Klasifikasi pohon memungkinkan Anda untuk melatih pengklasifikasi yang lebih efektif dalam hal kelengkapan untuk objek variabel dibandingkan dengan pengklasifikasi cascading klasik.Hasil percobaan
Sebagai bagian dari percobaan untuk mengevaluasi efektivitas metode pelokalan barcode yang diusulkan dalam artikel ini, satu set gambar barcode yang terdiri dari 264 gambar disiapkan. Ukuran fisik gambar adalah sekitar 1 MPix. Setiap gambar hanya mengandung satu kode QR dalam orientasi sewenang-wenang, area barcode setidaknya 10% dari total area gambar. Gambar di bawah ini menunjukkan contoh gambar dari set yang dirakit.
Ara. Contoh gambar dari kumpulan gambar barcode yang dirakit
Set gambar yang disiapkan dibagi menjadi set pelatihan dan set tes. Ukuran sampel pelatihan adalah 88 gambar, ukuran sampel uji adalah 176 gambar.Set pelatihan digunakan untuk menyiapkan contoh positif dan untuk menyiapkan contoh negatif. Karena jumlah awal contoh positif kecil, kami menggunakan teknologi augmentasi data [3]. Secara khusus, kami menerapkan rotasi di sekitar tengah barcode dengan penambahan 15⁰. Setelah augmentasi, jumlah contoh positif adalah 2.088 contoh.Dengan menggunakan contoh positif dan negatif yang sama, kami melatih tiga detektor kode QR: classifier cascading klasik dengan fitur Haar standar, classifier cascading klasik dengan fitur batas, dan classifier pohon dengan fitur batas. Penggolong kaskade pertama terdiri dari 12 level dan berisi total 58 atribut. Penggolong kaskade kedua terdiri dari 8 level dan berisi total 39 atribut. Klasifikasi pohon terlatih terdiri dari 39 simpul, berisi total 110 karakter, dan jalur maksimum dari atas ke daun adalah 9. Di bawah ini adalah diagram dari klasifikasi pohon terlatih.
Ara. Skema classifier pohon terlatih
Untuk menilai kualitas detektor kode-QR yang dibangun, kami menggunakan modul decoding barcode dari perpustakaan visi komputer openCV sumber terbuka. Pada set uji gambar yang disiapkan (yang, sebagaimana disebutkan di atas, terdiri dari 176 gambar), kami meluncurkan modul decoding tanpa preprocessing khusus, serta setelah pencarian awal untuk kode QR menggunakan detektor terlatih. Di bawah ini adalah hasil decoding barcode:Tabel tersebut menunjukkan bahwa lokalisasi awal kode QR menggunakan metode yang dijelaskan dapat secara signifikan meningkatkan kualitas decoding barcode (jumlah kesalahan decoding berkurang 44%). Selain itu, hasilnya juga menunjukkan bahwa penerapan metode Viola dan Jones asli (dengan fitur Haar klasik dan pengklasifikasi cascading) tidak efektif dalam tugas melokalkan kode QR.Sekarang mari kita lihat seberapa akurat setiap classifier melokalisasi barcode. Gambar dari kiri ke kanan menunjukkan hasil mendeteksi barcode yang sama dengan classifier cascading klasik dengan fitur Haar standar, classifier cascading klasik dengan fitur batas, dan classifier pohon dengan fitur batas. Dapat dilihat bahwa pohon-classifier memberikan akurasi pelokalan barcode terbaik dengan memperhitungkan variabilitas kode QR.
Ara. Ilustrasi pekerjaan detektor terlatih pada gambar yang sama
Kesimpulan
Saat ini, kode QR digunakan di berbagai bidang kehidupan: di industri periklanan untuk penyandian URL, di segmen negara bagian sebagai bagian dari layanan elektronik, dll. Terlepas dari distribusi barcode yang sangat tinggi, perpustakaan open source yang ada berfokus pada proses decoding, bukan masalah lokalisasi. Tetapi sejujurnya, tujuan sebenarnya dari artikel ini bukanlah untuk menjelaskan metode pelokalan kode QR yang efektif, melainkan dalam upaya untuk memberi tahu Anda, pembaca yang budiman, bagaimana, menggunakan pemikiran ilmiah dan analisis sistem, memahami cara menggunakan alat pengolah gambar digital klasik, Anda dapat perpustakaan membawa ke tingkat industri yang sebenarnya. Terimakasih atas perhatiannya.Daftar sumber yang digunakan[1] A.A. Kotov, S.A. Usilin, S.A. Gladilin, and D.P. Nikolaev, “Construction of robust features for detection and classification of objects without characteristic brightness contrasts,” Journal of information technologies and computing systems, 1, 53-60, (2014).
[2] A. Minkina, D. Nikolaev, S. Usilin, and V. Kozyrev, “Generalization of the Viola-Jones method as a decision tree of strong classifiers for real-time object recognition in video stream,” in Seventh International Conference on Machine Vision (ICMV 2014), 9445, International Society for Optics and Photonics, (2015), doi:10.1117/12.2180941.
[3] D. P. Matalov, S. A. Usilin, and V. V. Arlazarov, “Modification of the viola-jones approach for the detection of the government seal stamp of the russian federation,” in Eleventh International Conference on Machine Vision (ICMV 2018), 11041, International Society for Optics and Photonics, (2019), doi:10.1117/12.2522793.