Otomatisasi identifikasi modifikasi dalam gambar dokumen kontrak menggunakan model N-gram

Setiap orang modern tahu bahwa Anda harus menandatangani dokumen tidak lebih awal dari yang dibacanya. Pelanggar aturan sederhana ini kadang-kadang dikejutkan oleh konsekuensi tak terduga yang dapat dihindari jika Anda memeriksa dokumen sebelum menandatangani, termasuk apa yang ditulis dalam cetakan kecil. Trik dalam kontrak dengan penyedia layanan digunakan sebagai bagian dari lelucon dan film. Misalnya, dalam film Blinded by Desiressang protagonis mengakhiri perjanjian yang sangat tidak menguntungkan dengan iblis, meskipun tidak mengetahui kondisi untuk penghentian kontrak yang dijelaskan dalam pasal 147, paragraf 3, bagian 3 dari kontrak. Situasi serupa kadang-kadang mungkin terjadi dalam kehidupan nyata dengan penyedia layanan. Di Internet, Anda dapat menemukan deskripsi kasus yang aneh ketika seorang klien bank mengubah ketentuan perjanjian yang menguntungkannya, dan ini merupakan kejutan bagi bank. Pada artikel hari ini, kita akan berbicara tentang algoritma yang sangat berguna untuk bank dan organisasi kredit lainnya, yang secara otomatis mendeteksi modifikasi yang dilakukan pada gambar dokumen kontrak. Jadi lihat di bawah kucing!

Saat ini, banyak organisasi yang menarik sejumlah besar pelanggan baru, menawarkan untuk mengunduh templat kontrak dari situs web mereka untuk persiapan sendiri. Kontrak yang dicetak, diselesaikan dan ditandatangani ditransfer untuk ditandatangani ke pihak kedua. Tentu saja, pihak kedua memeriksa kontrak yang disiapkan oleh pelanggan potensial, misalnya, memeriksa dokumen yang diserahkan secara manual. Jumlah dokumen semacam itu bisa sangat besar, oleh karena itu beberapa karyawan yang penuh perhatian terlibat dalam memeriksanya. Namun, ketika memeriksa beberapa lusin dokumen identik (dalam arti) per hari, bahkan karyawan yang rapi dapat melewatkan kesalahan. Ini menjelaskan kasus-kasus penipuan yang tidak terdeteksi selama verifikasi manual.

Kami akan berbicara tentang otomatisasi verifikasi rutin dari aliran besar dokumen kontrak yang dijelaskan di atas menggunakan teknologi pengenalan optik, yang telah menjadi subjek artikel Smart Engine di Habr lebih dari sekali (misalnya, sekali dan dua kali ).

Dokumen kontrak termasuk dalam kelas dokumen bisnis yang dibuat untuk diedarkan di beberapa manajemen kantor dan sistem manajemen dokumen. Fitur khas dari dokumen bisnis adalah keterbatasan kosakata yang digunakan dan cara itu dirancang. Ini disebabkan oleh keinginan untuk menyatukan bentuk-bentuk dokumen untuk menyederhanakan pemahaman dokumen bisnis, pertama-tama, oleh seseorang.

Templat atau bentuk dokumen dijelaskan sebelumnya dan terdiri dari teks dan bidang statis untuk memasukkan informasi. Pertimbangkan dua kelas umum templat: templat tetap dan templat fleksibel. Templat tetap tidak memungkinkan modifikasi teks statis, misalnya, ketika menggunakan format PDF. Templat fleksibel dapat digunakan untuk memungkinkan modifikasi teks statis, misalnya templat dalam format Microsoft Office. Karenanya, kami akan membedakan antara dokumen tetap dan fleksibel.

Metode yang dikenal untuk perbandingan otomatis gambar (pindai atau foto) dari dokumen yang ditandatangani dengan prototipe [1]. Mereka memeriksa kemungkinan modifikasi pada konten:

• penggantian satu atau lebih karakter dalam satu kata;
• mengganti satu kata dengan yang lain;
• Tambahkan karakter, kata, atau grup kata
• Hapus karakter, kata, atau grup kata.

Modifikasi pada desain dokumen juga dimungkinkan:

• mengubah gaya kata (ukuran, font, jenis);
• mengubah bidang dokumen kata;
• perubahan jumlah paragraf;
• ganti bidang.

Modifikasi template tetap adalah pemalsuan yang disengaja, karena tidak ada cara lain untuk menjelaskan keinginan untuk mengubah teks yang dilindungi. Modifikasi template yang fleksibel dapat berupa pemalsuan, kesalahan ketik yang tidak disengaja atau hasil dari pemformatan yang ditingkatkan.

Selanjutnya, kami menjelaskan model dan metode mencari penipuan dalam salinan dokumen bisnis yang dicetak menggunakan template tetap dan fleksibel.

Dasar untuk membandingkan gambar uji (salinan) dan gambar referensi (asli) adalah gambar kata-kata yang ditemukan dengan metode apa pun. Gambar kata diwakili oleh beberapa deskripsi (deskriptor), deskriptor yang paling jelas adalah karakter kata yang dikenali. Kata$$$W$ didefinisikan sebagaititik fitur teks $$$W=(T(W),B(W))$, di mana -$$$T(W)$ adalah inti dari titik fitur teks, yaitu urutan karakter kata yang terdiri dari karakter alfabet tertentu atau urutan keakraban dengan peringkat kesesuaian keakraban dengan karakter alfabet,$$$B(W)$ - bingkai titik fitur teks yang terdiri dari koordinat batas$$$B_{x1}(W)$ ,$$$B_{y1}(W)$ ,$$$B_{x2}(W)$ ,$$$B_{y2}(W)$ , yang dapat dinormalisasi dalam kisaran tertentu, juga$$$F(W)$ - atribut titik fitur teks (misalnya, modifikasi headset dan font).

Titik fitur teks mirip dengan titik fitur "grafik" dalam gambar, yang berarti titik yang memenuhi beberapa kondisi:

• lingkungan yang berbeda dari titik-titik di sekitarnya;
• kekebalan kebisingan;
• resistensi terhadap transformasi tertentu (misalnya, untuk affine transformasi atau penskalaan) [2].

Sifat-sifat titik tunggal adalah:

• pengulangan - titik tertentu harus berada di tempat yang sama dari objek gambar, meskipun ada perubahan dalam sudut pandang dan pencahayaan;
• distinctiveness/informativeness – ;
• locality – ;
• quantity – ;
• accuracy – , , ;
• efficiency – .

Diasumsikan bahwa titik fitur teks berbeda dari titik fitur teks di sekitarnya. Jika yang kami maksud dengan lingkungan adalah baris teks, maka sebagian besar kata dalam dokumen bisnis berbeda dari tetangga di baris. Beberapa kata identik yang ditempatkan pada baris yang sama tidak akan menjadi titik tunggal teks. Namun, jika dengan lingkungan yang kami maksudkan satu atau dua kata tetangga, maka dua kata yang identik ditempatkan pada baris yang sama dan dibedakan dengan kata tetangga adalah teks poin tunggal. Perbandingan titik tunggal dilakukan dengan menggunakan ukuran kesamaan d, yang harus mengambil nilai mendekati nol dalam hal membandingkan dua titik yang sesuai dengan satu tempat dalam gambar, dan nilai besar ketika membandingkan titik dari tempat yang berbeda dalam gambar.Perbandingan dua inti titik tunggal teks dalam tulisan ini didasarkan pada jarak Levenshtein$$$\rho_{Lev}$ [3] dan modifikasinya. Ambang$$$d(W)$ perbandingan kata$$$T(W)$ dengan kata lain dihitung terlebih dahulu. Jika$$$\rho_{Lev}(W, W_r)\lt d(W)$ , lalu kata$$$W_r$ dan teks titik fitur$$$W$ yangidentik, sebaliknya berbeda.

Deskriptor titik fitur adalah pengidentifikasi yang digunakan saat mencocokkan poin fitur. Deskriptor diharapkan tidak berubah ketika mencocokkan titik tunggal sehubungan dengan transformasi gambar.

Metode mengekstraksi titik-titik singular dari suatu gambar disebut detektor.DetektorTitik fitur teks adalah prosedur pengenalan menggunakan beberapa OCR yang mengekstrak deskripsi titik fitur dari gambar dokumen. Sifat-sifat titik fitur yang tercantum di atas berlaku untuk titik fitur teks dalam hal kemampuan OCR modern untuk mengimbangi berbagai jenis distorsi gambar. Keunikan deskriptor teks singularitas ditentukan oleh struktur dokumen (pemisahan dokumen menjadi rasi bintang - bagian, paragraf dan garis) dan sifat bahasa alami (kebetulan yang jarang dalam dokumen dua kata yang berdekatan). Berbagai hubungan antara titik-titik teks tunggal (hubungan di atas - di bawah, ke kanan - ke kiri atau jarak geometris antara frame) memungkinkan Anda untuk menggabungkan titik-titik ke dalam rasi bintang menggunakan algoritma pengelompokan.

Idealnya, OCR mengekstrak semua titik khusus teks dari gambar salin dan templat dokumen tanpa kesalahan. Ini memungkinkan Anda untuk membentuk rasi bintang, terutama garis. Perbandingan salinan dan referensi terdiri dalam membangun korespondensi yang jelas antara semua atau sebagian dari titik teks tunggal dari referensi dan satu set titik teks tertentu dari salinan. Proses membangun korespondensi antara poin atau rasi bintang poin disebut koordinasi.

Koordinasi dokumen-dokumen tetap meliputi:

• pencarian korespondensi dari setiap titik di titik referensi dalam salinan;
• mencari korespondensi dari setiap titik dalam salinan di titik-titik standar;
• mencari korespondensi dari setiap garis statis standar pada titik-titik salinan;
• mencari korespondensi dari setiap garis salinan statis pada titik-titik standar;
• verifikasi identitas gambar dari setiap pasangan gambar terkoordinasi.

Setiap inkonsistensi yang ditemukan adalah modifikasi potensial. Tentu saja, ketidakkonsistenan yang ditemukan mungkin disebabkan oleh kesalahan detektor (OCR) atau distorsi gambar dokumen. Pernyataan masalahnya adalah mencari semua modifikasi dalam salinan dokumen.

Koordinasi dokumen yang fleksibel melibatkan membangun korespondensi antara semua kata-kata dari teks statis. Namun, tidak seperti dokumen tetap, tidak ada korespondensi antara baris teks statis dari dokumen fleksibel yang diasumsikan. Dalam dokumen yang fleksibel, perubahan yang sah mungkin dilakukan yang tidak mengubah arti teks, seperti mengubah font, mengubah batas-batas garis, garis putus. Modifikasi tersebut dapat menyebabkan jeda baris pada halaman lain, sehingga perbandingan dokumen fleksibel multi-halaman harus dilakukan untuk seluruh urutan halaman.

Dalam kasus umum, tanpa pengetahuan tentang struktur dokumen, koordinasi semua kata-kata tes dan dokumen referensi diperlukan. Kelemahan pasti dari koordinasi penuh kata-kata adalah kesalahan pengenalan yang tak terhindarkan, terutama untuk foto (lihat contoh fragmen gambar teks dengan distorsi pada gambar di bawah), diartikan sebagai modifikasi. Orang yang bertanggung jawab untuk verifikasi akan dipaksa untuk menghabiskan waktu ekstra memeriksa modifikasi palsu.



Dengan koordinasi penuh dari kata-kata salinan dan asli, selain kesalahan pengakuan salah, mungkin ada perbedaan tidak signifikan lainnya. Faktanya adalah bahwa dari sudut pandang pengguna fungsional program untuk membandingkan salinan dan aslinya, tidak semua kata memiliki nilai yang sama. Faktanya, bagian dari kata-kata dari sebuah halaman dokumen, yang menentukan syarat-syarat penting kontrak, sangat berharga. Diasumsikan bahwa tugas penipu adalah membuat modifikasi sedemikian rupa sehingga, di pengadilan atau dalam proses pra-sidang, dapat menyebabkan kerusakan pada organisasi yang menandatangani kontrak dengan penipu. Berikan definisi formal yang signifikan seperti itukata-kata itu hampir tidak mungkin, mereka ditentukan oleh para ahli. Selain itu, beberapa kata menjadi signifikan dalam kombinasi dengan kata-kata tetangga. Misalnya, partikel "tidak" dalam kombinasi dengan kata "jaminan" yang berdekatan adalah signifikan. Modifikasi kata "kontrak" menjadi kata "non-kontrak" tidak signifikan, karena dalam persidangan tidak dapat membawa manfaat bagi penipu.

Dengan demikian, perumusan masalah yang lain dimungkinkan, dengan menggunakan pengetahuan tentang struktur dokumen dan penempatan kata-kata yang penting untuk verifikasi. Dalam pernyataan ini, model dokumen terdiri dari paragraf dan string teks. Setiap baris teks dan setiap paragraf diwakili oleh satu set titik tunggal teks yang urutannya unik untuk paragraf atau baris tertentu. Baris dan paragraf juga dapat berisi kata-kata yang tidak unik, yaitu, diulang atau bahkan terletak di dekatnya. Dalam kasus khusus, dimungkinkan untuk mengetahui jarak antara kata-kata unik, ditentukan oleh jumlah karakter menengah atau jarak geometris antara gambar kata.

Menggunakan model kata N-gram sederhana telah terbukti efektif. Model N-gram digunakan dalam berbagai tugas, seperti kompresi atau pengkodean teks. Dalam pemrosesan teks yang ditulis dalam bahasa alami, N-gram berguna untuk menemukan dan memperbaiki kesalahan (kami sudah menulis tentang ini sebelumnya ).

Untuk mencari kata kunci, N-gram kata digunakan dalam bentuk berikut:

$$$n_2 (w_i )=〈w_i,r_1 (w_i ) 〉$
$$$n_3 (w_i )=〈w_i,r_1 (w_i ),r_2 (w_i ) 〉$
$$$n_2 (w_i )=〈l_1 (w_i ),w_i 〉$
$$$n_3 (w_i )=〈l_1 (w_i ),w_i,r_1 (w_i ) 〉$
$$$n_4 (w_i )=〈l_1 (w_i ),w_i,r_1 (w_i ),r_2 (w_i ) 〉$
$$$n_3 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i 〉$
$$$n_4 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i,r_1 (w_i ) 〉$
$$$n_5 (w_i )=〈l_2 (w_i ),l_1 (w_i ),w_i,r_1 (w_i ),r_2 (w_i ) 〉 ,$

Dimana $$$r_k (w_i)$, $$$l_q (w_i)$kata di sebelah kanan atau kiri kata pusat $$$w_i$jarak yang diizinkan juga diketahui $$$\rho_{BT}(w_i, r_1 (w_i))$, $$$\rho_{BT}(r_1 (w_i), r_2 (w_i))$, $$$\rho_{BT}(l_1 (w_i), w_i)$, $$$\rho_{BT}(l_2 (w_i), l_1 (w_i))$antara kata yang berdekatan. Indeks$$$k$ dalam penunjukan N-gram $$$n_k (w_i)$sebut panjang N-gram.

Model paragraf terdiri dari urutan urutan N-gram
$$$n^1 (w_1), n^2 (w_2), …, n^m (w_m)$dengan tupel kata yang sudah ditentukan sebelumnya $$$n^i (w_i)$, dengan jarak antar pasangan yang diketahui $$$\{n^{j-1}(w_{j-1}), n^j(w_j)\}$. Perhatikan bahwa beberapa N-gram unik untuk paragraf, dan beberapa mungkin diulang. Untuk memastikan keunikan, N-gram dari berbagai panjang dapat digunakan: bigrams, trigram, tetragrams, dan pentagram.

Saat membuat model paragraf, N-gram dibentuk untuk memaksimalkan jumlah N-gram unik. Penggunaan N-gram dibandingkan dengan kata kunci individual memastikan keunikan untuk sebagian besar paragraf dokumen kontrak, pertama-tama, karena keterbatasan yang signifikan dari kumpulan kata dalam teks statis yang disebutkan di atas.

Masuk akal untuk melakukan pelatihan dan optimalisasi parameter pada dataset nyata. Perhatikan bahwa bahkan pada dataset nyata kita tidak akan melihat kemungkinan modifikasi, pertama-tama, karena sekresi data tersebut oleh pemilik dataset. Saya harus melakukan modifikasi dengan tangan saya sendiri.

Algoritma pencarian trigram diturunkan untuk memilih beberapa kata berturut-turut. Tentu saja, pertama Anda perlu membentuk satu set titik teks tunggal. Untuk melakukan ini, kami telah mengambil langkah-langkah berikut:

• pemrosesan halftone (perpustakaan MinImage);
• normalisasi gambar dengan sudut menggunakan metode berdasarkan fast Hough transform [4] (Smart IDReader API);
• menyoroti batas kata menggunakan operasi "erosi" dan "dilatasi" (perpustakaan MinImage);
• pengenalan karakter dalam batas-batas kata yang ditemukan (Smart IDReader API).

Paragraf ini disajikan sebagai satu garis panjang.

Perbandingan kata-kata ideal dan kata-kata yang dikenali dari suatu paragraf dilakukan dengan menggunakan jarak Levenshtein yang dimodifikasi. Algoritma perhitungan jarak Levenshtein sudah terkenal, mereka memungkinkan Anda untuk menemukan tidak hanya jumlah resep editorial, tetapi juga resep itu sendiri.

Jarak Levenshtein yang dimodifikasi digunakan. Pertama, ambang batas yang unik dipilih untuk membandingkan kata tertentu dengan kata lain. Untuk penolakan untuk mengidentifikasi pasangan kata dari jenis "SEA" = "GUNUNG" atau untuk pengidentifikasi dari jenis "IDENTIFIER196", "IDENTIFIER296", "IDENTIFIER296", "IDENTIFIER199", aturan lain diterapkan. Untuk kata-kata seperti itu segmen diindikasikan tetap tidak berubah. Yaitu, pada awal kata "IDENTIFIER ddd" sejumlah besar kesalahan diizinkan, tetapi identifikasi dilarang dengan petunjuk editorial yang ditemukan dalam 3 karakter kata terakhir.

Modifikasi lain adalah untuk mengimbangi penggantian OCR dari beberapa karakter dengan karakter yang sama. Secara formal ganti karakter untuk alfabet Latin$$$B8$, $$$DO$, $$$1I$ada kesalahan, namun, mengurangi harga penggantian tersebut dapat meningkatkan keakuratan identifikasi kata. Harga penggantian huruf untuk karakter dengan gaya yang sama dipilih selama pelatihan.
Berdasarkan beberapa jarak pusat dan tetangga N-gram ke analog yang dipilih, perkiraan heuristik dari pengikatan N-gram secara keseluruhan terbentuk.
Parameter model (ambang, panjang N-gram) dipilih selama pelatihan untuk meminimalkan jumlah kesalahan pengikatan N-gram dan memaksimalkan jumlah N-gram yang terikat dengan benar.

Setelah mengikat N-gram ke kata-kata paragraf, pemeriksaan berikut dapat dilakukan:

• kehadiran semua N-gram yang diharapkan;
• kehadiran semua N-gram unik dalam satu salinan;
• urutan N-gram;
• jarak antara N-gram yang berdekatan.

Kegagalan melakukan salah satu pemeriksaan berarti menemukan modifikasi pada kata kunci penting.

Metode yang dijelaskan diuji pada dataset yang terdiri dari 161 gambar dokumen jenis "Perjanjian" yang dipindai dengan resolusi 100 hingga 300 dpi. Kami menyelidiki 33 kata kunci. Beberapa kata kunci dalam gambar dataset sengaja dihapus atau dimodifikasi. 740 penghapusan dan modifikasi 140 kata dibuat. OCR Smart IDReader [5] digunakan untuk pengakuan.

Kualitas algoritma dievaluasi dengan kriteria akurasi (Presisi) dan kelengkapan (Ingat), dalam penentuan angka-angka yang digunakan:

• menemukan kata-kata yang dimodifikasi $$$tp$;
• kata yang tepat diklasifikasikan sebagai modifikasi $$$fp$;
• kata yang dimodifikasi tidak ditemukan $$$fn$;
• kata yang benar diklasifikasikan sebagai benar $$$tn$.

Hasilnya disajikan dalam tabel. Tabel menunjukkan karakteristik yang dihitung untuk beberapa ambang batas.$$$d(w_i)$ penilaian kebenaran kata dibandingkan dengan kata referensi.


Perhatikan bahwa ketika OCR Smart IDReader dikenali, semua kata yang dimodifikasi ditemukan. Kesalahan metol dikaitkan dengan kesalahan pengenalan, terutama karena cacat pemindaian (adanya area yang terlalu terang).

Sangat mudah untuk menebak bahwa metode yang dijelaskan memiliki keterbatasan terkait dengan akurasi batas kata yang membedakan. Cacat pemindaian yang ditunjukkan menyebabkan sejumlah kecil kesalahan pencarian batas kata (sekitar 1-1,5% untuk beberapa kata kunci). Untuk menghilangkan batasan ini, kami menawarkan cara tambahan untuk mencari kata-kata. Untuk beberapa N-gram yang tidak terdeteksi, subset dari kata-kata paragraf yang diakui dipilih di mana kehadiran N-gram ini diharapkan. Kesenjangan dihapus dari bagian kata yang dipilih dan serangkaian karakter dibentuk. Kata-kata N-gram digabungkan, membentuk substring untuk pencarian. Selanjutnya, kami mencari substring, misalnya, menggunakan algoritma bitup yang dimodifikasi menggunakan jarak Levenshtein yang dimodifikasi. Ini memungkinkan untuk mengurangi 2-3 kali jumlah kesalahan pemeriksaan N-gram yang terkait dengan kesalahan dalam pencarian batas kata.

Kesimpulan singkat

Kami berbicara tentang satu alat untuk mencari pemalsuan dokumen kontrak. Tentu saja, alat ini tidak sepenuhnya menyelesaikan masalah dan diperlukan pemeriksaan manual terhadap kata-kata yang diduga dimodifikasi. Metode ini memungkinkan Anda untuk secara otomatis mengotomatiskan pencarian modifikasi dan secara signifikan mengurangi jumlah pemeriksaan manual rutin. Kompleksitas mengembangkan metode yang dijelaskan adalah sulitnya memperoleh dataset nyata dengan palsu.