Get best of the week

Kapan menghentikan proses pengenalan urutan video?

Hai Habr! Hari ini kami ingin memberi tahu Anda tentang masalah yang sangat menarik yang telah kami tangani sejak awal penelitian kami tentang pengenalan dokumen dalam aliran video - masalah menemukan waktu berhenti yang optimal.



Ara. 1. Gambar bidang teks dokumen ID pada bingkai urutan video.

Seperti yang diketahui banyak orang, produk utama Smart Engines adalah sistem pengenalan dokumen identitas, Smart IDReader, yang berlaku baik pada server dan desktop, dan pada perangkat seluler. Dalam sejumlah besar kasus, pengakuan dokumen pada ponsel harus dilakukan secara offline, seringkali kita tidak dapat mengontrol kondisi dan kualitas pemotretan, dan biaya kesalahan pengenalan, terutama ketika mengenali dokumen identifikasi, sangat tinggi. Pada saat yang sama, kami memiliki keuntungan penting - kami dapat menggunakan tidak hanya satu gambar, tetapi urutan frame yang diambil (lihat Gambar 1), untuk meningkatkan akurasi pengenalan.

Saat menggunakan beberapa gambar bidang teks, dua pertanyaan penting muncul. Pertanyaan pertama adalah bagaimana menggabungkan pengamatan? Apakah layak menggabungkan frame sumber untuk mendapatkan satu gambar, "kualitas" yang lebih tinggi, atau memilih satu frame yang lebih baik (lalu di mana ada jaminan bahwa akan ada frame yang baik)? Atau, mungkin, pertama-tama kenali bidang pada setiap frame, dan kemudian pilih hasil yang paling “percaya diri” (dengan kriteria apa?), Atau gabungkan hasil pengenalan bingkai-demi-bingkai, dll. Kami mematuhi pendekatan yang terakhir (pengenalan frame-by-frame dengan kombinasi hasil antarframe), tetapi pendekatan yang optimal mungkin berbeda baik tergantung pada mesin pengenalan yang digunakan dan parameter tugas lainnya.

Pertanyaan kedua yang muncul secara independen dari yang pertama adalah kapan harus menghentikan proses observasi? Dengan kata lain, dengan kriteria apa Anda memutuskan bahwa proses penangkapan dapat dihentikan dan hasil akumulasi pada saat saat ini diakui sebagai final? Bagaimana cara membandingkan kriteria tersebut satu sama lain dan apakah ada yang optimal?

Ini tentang masalah menemukan saat menghentikan proses pengamatan yang akan dibahas dalam artikel ini.

Apa yang ingin kita capai


Mengenali string teks dalam urutan video, di mana setelah menangkap pengamatan lain, hasilnya membaik dengan satu atau lain cara, dapat dianggap sebagai algoritma Anytime - algoritma dengan hasil peningkatan berurutan, perhitungan yang dapat dihentikan kapan saja. Alat yang mudah digunakan untuk memvisualisasikan kualitas algoritma tersebut adalah " profil kinerja yang diharapkan " - grafik ketergantungan kualitas hasil, diukur dalam satu bentuk atau lainnya, pada waktu perhitungan.


Ara. 2. Profil efisiensi pengenalan garis teks dalam urutan video (lebih rendah lebih baik). Garis putus-putus hitam adalah kualitas frame-by-frame, garis solid hitam adalah hasil dari penggabungan antar bingkai. Garis oranye adalah apa yang kita inginkan dari aturan berhenti "baik".

Dalam Fig. Gambar 2 menunjukkan profil efisiensi untuk mengenali string teks - ketergantungan kesalahan rata-rata (dalam hal jarak Levenshtein dengan jawaban yang benar) pada jumlah frame yang diproses. Grafik hitam diperoleh menggunakan Tesseract v4.0.0 pada bidang teks dataset MIDV-500 . Dapat dilihat bahwa penggunaan interframe yang menggabungkan hasil pengenalan memungkinkan seseorang untuk mencapai nilai kesalahan yang jauh lebih rendah (yang, secara umum, tidak mengejutkan).

Apa yang kita inginkan dari aturan berhenti “baik”? Karena kami berharap, cukup wajar, bahwa semakin lama kami melanjutkan proses, semakin baik kami akan memiliki hasil rata-rata, akan lebih baik jika aturan berhenti pada beberapa urutan video dianggap "lebih lama", jika ada peluang untuk meminimalkan kesalahan, dan pada beberapa itu akan berhenti akan lebih awal jika hasilnya sudah bagus, atau tidak ada kesempatan untuk memperbaikinya. Karena ini, dengan kualitas rata-rata yang sama dari hasil gabungan, rata-rata, lebih sedikit frame yang diproses dapat dicapai, dan sebaliknya, dengan jumlah rata-rata frame yang sama, hasil rata-rata lebih baik. Dengan kata lain, penting untuk memahami bahwa aturan pemberhentian tidak hanya tentang meminimalkan waktu, tetapi juga tentang memaksimalkan kualitas, untuk waktu (rata-rata) yang sama.

Mari kita mencari aturan berhenti dalam bentuk berikut: setelah memproses frame berikutnya dan menerima hasil pengakuan gabungan, kami mempertimbangkan beberapa karakteristik dan memotong ambangnya - jika, katakanlah, itu di bawah ambang batas, maka kami berhenti, jika tidak kami melanjutkan. Kemudian, dengan aturan berhenti tetap, tetapi memvariasikan ambang, kami juga akan mendapatkan profil efisiensi, dengan pengecualian bahwa sumbu horizontal tidak akan berisi jumlah persis frame yang diproses, tetapi rata-rata (lihat grafik oranye pada Gambar. 2). Semakin rendah grafik ini, semakin efektif kita dapat mempertimbangkan aturan berhenti. Kita dapat menganggap profil awal dari "hasil gabungan" sebagai profil efektivitas aturan berhenti sepele - di mana kita cukup memotong jumlah frame yang diproses oleh ambang pintu.

Apa kata teori itu


Dalam statistik matematika, masalah menemukan waktu berhenti optimal sudah diketahui dan telah lama diselidiki. Mungkin tugas yang paling terkenal dari kelas ini adalah tugas pengantin pilih-pilih (dia banyak terlibat, misalnya, Boris Abramovich Berezovsky), tugas menjual rumah, dan lain-lain. Tanpa masuk ke dalam teori, mari kita secara singkat mengajukan masalah pengakuan dalam urutan video sebagai masalah berhenti optimal.

Kami menunjukkan kesalahan hasil gabungan pada nlangkah ke-5 dari proses sebagai \ epsilon (R_n). Kami berasumsi bahwa jika kami berhenti pada nlangkah ke - i, kami akan mengalami kerugian dalam bentuk berikut :, di L_n = \ epsilon (R_n) + c \ cdot nmanac- beberapa biaya relatif yang telah ditentukan untuk setiap pengamatan. Tugas menemukan waktu berhenti optimal dapat dirumuskan sebagai pencarian variabel acak N- waktu berhenti, distribusi yang tergantung pada pengamatan input (dalam beberapa literatur nilainya Ndisebut momen Markov ), dan di mana kerugian yang diharapkan diminimalkan \ mathrm {E} (L_N).

Masalah monoton


Dalam kondisi tertentu, dalam masalah seperti itu, aturan henti optimal dapat dinyatakan secara eksplisit. Contohnya adalah masalah yang disebut monoton. Kriteria untuk monotonitas masalah adalah ini: jika pada beberapa langkah nkerugian L_ntidak melebihi kerugian yang diharapkan pada langkah berikutnya, maka ini akan dilakukan pada semua langkah selanjutnya. Dengan kata lain, dari apa yang terjadi peristiwa L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {diterima} ~ n ~ \ text {frames})mengikuti bahwa peristiwa itu akan terjadi L_ {n + 1} \ le \ mathrm {E} (L_ {n + 2} | \ text {diterima} ~ n + 1 ~ \ text {frames}). Untuk masalah monoton, apa yang disebut aturan stop "rabun dekat" optimal: berhenti pada langkah pertama di mana kondisi terpenuhi L_n \ le \ mathrm {E} (L_ {n + 1} | \ text {diterima} ~ n ~ \ text {frames}).

Misalkan tugas kita monoton. Setelah menulis aturan rabun dalam hal fungsi L_nkita , kita mendapatkan bahwa kita perlu berhenti ketika kondisi berikut terpenuhi:

\ epsilon (R_n) - \ mathrm {E} (\ epsilon (R_ {n + 1}) | \ text {diterima} ~ n ~ \ text {frames}) \ le c.

Ini, tentu saja, sangat bagus, tetapi untuk menerapkan aturan seperti itu, kita harus dapat mengevaluasi dalam runtime tidak hanya "kebenaran" dari hasil saat ini, tetapi juga kebenaran yang diharapkan dari yang berikutnya, yang tidak begitu sederhana (belum lagi apa yang kita minta dengan angkuh dari tugas tersebut kesamaan). Bisakah kita entah bagaimana menerapkan aturan ini tanpa secara langsung menilai "kebenaran" hasilnya? .. Anda dapat mencoba untuk mengevaluasi sisi kiri ketidaksetaraan dari atas.

Bagaimana aturan rabun dapat digunakan?


Mari kita asumsikan bahwa fungsi \ epsilon (R_n)adalah jarak \ rho (R_n, R ^ *)dari hasil pengakuan gabungan R_nke "jawaban yang benar" R ^ *, dan seperti jarak apa pun yang menghargai dirinya sendiri, ketidaksetaraan segitiga berlaku. Jarak Levenshtein yang disebutkan di atas memenuhi ketimpangan segitiga, serta fungsi sederhana dalam bentuk "benar / salah" (jika kita menganggap bahwa \ rho (R_n, R ^ *)untuk jawaban yang benar itu nol dan untuk jawaban yang salah itu konstan). Menurut ketimpangan segitiga, sisi kiri kriteria berhenti kami tidak melebihi \ mathrm {E} (\ rho (R_n, R_ {n + 1}) | \ text {diterima} ~ n ~ \ text {frames})- jarak yang diharapkan dari hasil gabungan saat ini ke yang berikutnya.

Mari kita juga membutuhkan dari algoritma kami untuk interframe yang menggabungkan hasil pengenalan, sehingga rata-rata jarak antara hasil gabungan yang berdekatan tidak meningkat dari waktu ke waktu (yaitu, kami akan mempertimbangkan urutan hasil gabungan sebagai beberapa proses "konvergen", meskipun tidak harus dengan jawaban yang benar). Kemudian jika jarak yang diharapkan dari hasil saat ini ke yang berikutnya menjadi kurang dari ambang c, dua hal dilakukan sekaligus. Pertama, kriteria berhenti berpandangan pendek terpenuhi (karena bagian kirinya dibatasi dari atas dengan jarak yang sama). Dan kedua, tugas menjadi monoton: pada langkah berikutnya, jarak yang diharapkan ke jawaban berikutnya tidak akan tumbuh, yang berarti akan terus kurang dari ambang c, dan kriteria berpandangan pendek akan terpenuhi lagi.

Ini berarti bahwa jika kita berharap bahwa jarak antara hasil gabungan yang berdekatan tidak meningkat rata-rata, maka kita perlu berhenti dengan ambang batas cutoff dari jarak yang diharapkan dari hasil saat ini ke yang berikutnya, sehingga mendekati aturan optimal. Anda perlu memahami bahwa aturan seperti itu tidak lagi optimal (karena aturan optimal "nyata" bisa berhenti lebih awal), tetapi setidaknya kita tidak akan berhenti lebih awal dari yang diperlukan.

Ada beberapa cara untuk mengevaluasi jarak yang diharapkan dari hasil gabungan saat ini ke yang berikutnya. Misalnya, jika jarak Levenshtein digunakan sebagai metrik atas hasil, maka bahkan jarak antara dua hasil terakhir tata letak adalah perkiraan yang baik. Pendekatan lain yang mungkin adalah mensimulasikan kemungkinan pengamatan berikutnya (misalnya, berdasarkan yang sudah diperoleh), melakukan kombinasi "idle" dan menghitung jarak rata-rata ke prediksi yang diperoleh.


Ara. 3. Perbandingan profil kinerja untuk beberapa aturan penghentian.

Dalam Fig. 3 menunjukkan profil kinerja untuk beberapa aturan penghentian. N_K- aturan "sepele" yang disebutkan di atas - dengan batas ambang jumlah pengamatan yang diproses. N_ {CX}danN_ {CR}- ambang batas ukuran cluster maksimum hasil frame-by-frame identik ( N_ {CX}) dan gabungan ( N_ {CR}). N- aturan yang dijelaskan dalam makalah ini, dengan perkiraan jarak yang diharapkan ke hasil selanjutnya menggunakan pemodelan dan kombinasi "idle".

Alih-alih sebuah kesimpulan


Tujuan artikel ini adalah untuk menunjukkan bahwa dalam sistem pengenalan dokumen pada kerangka urutan video ada banyak masalah menarik, tidak hanya secara langsung dari visi komputer, tetapi juga dari bidang menarik lainnya. Meskipun kami menunjukkan masalah menemukan waktu berhenti optimal hanya dalam bentuk yang paling sederhana, bagian yang paling menarik dimulai ketika, misalnya, kami ingin memperhitungkan dalam model tidak hanya jumlah frame, tetapi juga waktu eksekusi yang sebenarnya. Kami harap Anda tertarik, dan terima kasih atas perhatian Anda!

-

Publikasi disusun berdasarkan artikel Pada strategi penghentian optimal untuk pengenalan teks dalam aliran video, K. Bulatov, N. Razumnyi, VV Arlazarov, IJDAR 22, 303-314 (2019) 10.1007 / s10032-019-00333-0 .

Jika pembaca tertarik pada teori waktu berhenti optimal, khususnya, bukti optimalitas aturan rabun untuk masalah monoton, kami sangat merekomendasikan mata kuliah Pemberhentian dan Aplikasi Optimal yang diterbitkan (Thomas Ferguson, UCLA).

Beberapa sumber lain yang menarik tentang masalah ini:
Chow YS, Siegmund D. Harapan besar: Teori berhenti optimal , Houghton Mifflin, 1971, 139 p.
Berezovsky B.A., Gnedin A.V. Masalah Pilihan Terbaik , Sains, 1984, 200 hal.
Ferguson TS, Hardwick TS Menghentikan aturan untuk proofreading , Journal of Applied Probability., V. 26, N. 2, 1989, hlm. 303-313.
Ferguson TSStatistik matematika: pendekatan teori keputusan . Pers akademik, 1967, 396 hal.

More articles:


All Articles