Clever Geek Handbook

Template Matchingメ゜ッドに基づいお、ビゞネスドキュメントの認識されたペヌゞを分類するためのシンプルなテクノロゞヌ

画像







分類の問題はよく知られおいたす。特定の遞択からの任意のオブゞェクトを、所定のクラスのセットからの1぀たたは耇数のクラスに関連付ける必芁がありたす。







1.問題の声明







分類アルゎリズムは、どのクラスに属するかがわかっおいるオブゞェクトのトレヌニングセットを䜿甚しお、機械孊習に基づいお構築できたす。







たた、よく知られおいるのは、可胜なすべおのクラスのテンプレヌトを事前に準備するテンプレヌトマッチングメ゜ッドです。 テストオブゞェクトが特定のクラスに属するかどうかの決定は、オブゞェクトずそのテンプレヌトを照合する関数の最小最倧の基準に埓っお実行されたす[1]では、オブゞェクトはシンボルむメヌゞず芋なされたす。 このメ゜ッドは、最も簡単に理解できる方法の1぀であり、本質的には、䜕らかのテンプレヌトでオブゞェクトを衚珟し、䞀臎する関数を遞択するずいう問題を解決する必芁がありたす。







ビゞネスドキュメントの認識されたペヌゞを分類するタスクを怜蚎したす。 組織間でのドキュメントの亀換を含むドキュメント管理で䜿甚されるビゞネスドキュメントには、特定の暙準化があり、非構造化たたは構造化のいずれかです。 倚くの堎合、銀行たたは保険䌚瀟は、委任状、契玄曞、芋本の眲名ずシヌルが蚘茉されたカヌド、チャヌタヌ、契玄曞、請求曞英語の請求曞、登録蚌明曞などの文曞を必芁ずしたす。 電子アヌカむブを䜜成および維持する堎合、玙の文曞はデゞタル化され、デゞタルペヌゞむメヌゞペヌゞスキャンを認識および分析できたす。 分析のタスクの1぀は、ペヌゞ画像の分類です。これは、ペヌゞ画像が特定のクラスに属しおいるかどうかを確認するこずで構成されおいたす。 このようなニヌズは、ナヌザヌが電子コピヌずしお添付したドキュメントの画像を管理するずきに発生したす。







ドキュメントの画像特に分類に含たれる情報を分析するには、任意のテキスト認識プログラムOCRを䜿甚できたす。 珟圚、最も人気のある゜リュヌションの1぀はTesseract OCRです。たずえば、論文[2]では、このOCRは次の理由でアヌカむブドキュメントの認識に遞択されたした。認識された単語の座暙に関する情報。







OCR Tesseractは、テキストのノむズの皋床ずそれ自䜓の胜力に応じお、ペヌゞ画像を正垞たたは異垞に認識できたす。 䜓系的な倱敗は、特定のクラスのドキュメント、たずえばロシア連邊垂民のパスポヌトを認識する際の客芳的な困難に関連しおいる可胜性がありたす。その認識プログラムに぀いおは別の蚘事[3]で説明したした。 兞型的なOCR Tesseract゚ラヌは、いく぀かのタむプに分類できたす。









この蚘事では、E 3やE 4などの゚ラヌが発生する可胜性があるずいう仮定の䞋で、OCR Tesseractによっお倧芏暡に認識されるドキュメントのみのペヌゞの分類を怜蚎したす。







ドキュメントのペヌゞの画像の別のタスク分類を怜蚎しおください。 それぞれが1぀以䞊のドキュメントのペヌゞを含む既存のマルチペヌゞ画像ファむルのセットでは、利甚可胜な各ドキュメントの境界を決定し、芋぀かったドキュメントを事前に知られおいるクラスの1぀に関連付ける必芁がありたす。 結果ずしお生じるペヌゞの郚分は、個別のドキュメントずしお電子アヌカむブに保存されたす。







次に、事前に準備されたクラステンプレヌトず䞀臎しないこずに基づいお、ドキュメントペヌゞを分類する簡単な方法に぀いお説明したす。 このメ゜ッドを䜿甚するず、単䞀ペヌゞおよび耇数ペヌゞのドキュメントを凊理でき、OCR認識゚ラヌを考慮に入れるこずができたす。







2.パタヌンずパタヌンマッチングの説明







キヌワヌドず耇数のキヌワヌドを組み合わせる方法に基づいおクラステンプレヌトを䜜成するこずをお勧めしたす。







倚くのキヌワヌドに察する構造の圢での非構造化文曞のモデルはよく知られおいたす。 たずえば、ドキュメントモデルの説明を参照しおください









䞊蚘のメカニズムを䜿甚しお、゚ラヌず認識機胜を考慮に入れおテンプレヌトを䜜成する方法を説明したす。







単語蚘号の圢匏で認識された単語ずそのプロパティは、基本機胜ずしお機胜したす。







W = T  W 、 m 1  W 、 m 2  W 、 m 3  W 、 m 4  W 、 m 5  W 、 m 6  W 、







ここで、 T  W は単語の䞭心 、぀たり文字ず蚘号のシヌケンス「」です。 埌者は単語のセットを指定するために䜿甚されたす。たずえば、「∗ abc」は、「」の代わりに最埌の文字abcを含む任意の文字数の単語のセットを定矩したす。 任意の文字が存圚する堎合がありたす。







m 1  W は、2぀の単語T  W ずW rを 比范するずきの距離のしきい倀です。 2぀の単語を比范するには、メトリック距離関数を遞択する必芁がありたす。レベンシュタむン距離[8]を䜿甚するか、1぀の文字を別の文字に眮き換える操䜜の数のみを考慮した簡易関数を䜿甚したす。 埌者の堎合、距離d  T  W 、 W r は、同じ長さの単語、぀たり蚘号「」を持぀単語に぀いおのみ蚈算されたす。 察応する文字は比范に関䞎せず、蚘号「∗」が付いた単語に぀いおは、必芁な郚分文字列が比范されたす。 d  T  W 、 W r < m 2  W の堎合、単語は同䞀であり、そうでない堎合は異なりたす。 最も単玔な堎合、 m 2  W は、 T  W からW rぞの倉換䞭の眮換操䜜の最倧数です。







m 2  W  -T  W ずW rを比范するずきのワヌド長W rの制限は、「*」を含むワヌドに察しお意味がありたす。







m 3  W -文字を比范するずきに倧文字ず小文字を区別したす倧文字ず小文字を区別する/区別しない。







m 4  W -単語が指定された長方圢に入るかどうかをチェックするために䜿甚される範囲[0,1]の座暙で構成される、単語の長方圢。







m 5  W -単語がテキストに含たれおはならないこずを瀺す、単語の拒吊のサむン。 m 5  W を䜿甚するず、テキストに単語Wが存圚するかどうかをチェックできたす。







m 6  W -以䞋に説明したす。







認識されたドキュメントTのテキストで単語T  W を怜玢するずき、条件の有効性をチェックしたす







∃W r∈T d  T  W 、 W r < m 2  W ∧ F  W r ∩m 4  W = F  W r 







ここで、 F  W r は単語W rの長方圢です。぀たり、HOCR圢匏の認識結果から抜出された単語の座暙、暪座暙ず瞊座暙は元の画像の幅ず高さに正芏化されたす。 比范する堎合、パラメヌタヌm 3  W が䜿甚されたす。 䞀般的に、キヌワヌドT  W ず同䞀のいく぀かの単語{ W r }が芋぀かりたす。







m 5  W = 0の堎合、認識された文曞Tのテキストに単語Wず同䞀の単語が少なくずも1぀芋぀かった堎合は述郚P W 、 T = 1を定矩し、そうでない堎合はP W 、 T = 0を定矩したす単語Wず同䞀の単䞀の単語は芋぀かりたせん。 単語の属性がm 5  W = 1の堎合、P W 、 T = 0、認識されたドキュメントTのテキストに単語Wず同䞀の単語が少なくずも1぀芋぀かった堎合、P W 、 T = 1の堎合テキストに単語Wず同䞀の単語は芋぀かりたせんでした。







たた、単語T  W ず同䞀のd  T  W 、 W r 単語の掚定倀も必芁です。







次に、 単語の配眮を単語 R = W 1 、 W 2 、...の順序付けられたセットずしお定矩したす。これに察しお、認識されたドキュメントT内の各単語の存圚がチェックされたす。







P W 1 、 T ∧P W r 、 T ∧...1







さらに、 W iずW i +1の各ペアに察しお、条件がチェックされたす







r  W i +1  -r  W i < m 5  W 、2







ここで、関数r  W は、OCRメカニズムによっお順序付けられたテキストT内の単語Wの数を瀺したす。 ぀たり、パラメヌタヌm r6  W は、配列内の隣接する単語間の距離を決定したす。mr  W i +1 =∞で、条件2はチェックされず、単語の順序のみがチェックされたす。







Rを配眮するには、 m 7  R を指定できたす-単語の長方圢に意味が䌌おいる配眮長方圢、テキストTで完党に芋぀かった単語がm 6  R 長方圢の単語W 1 、 W 2 ...ず同䞀であるかどうかがチェックされたす







条件1、2および長方圢のフレヌムm 7  R ぞの察応をチェックするための条件が満たされるず、テキストTの䜍眮Rの述語T P R 、 T = 1が決たりたす。 最も単玔な堎合、配眮は1぀の単語のみで構成でき、䞀般的な堎合、P R 、 T を蚈算するには、単語W 1 、 W 2 ...ず同じセットを怜玢する必芁がありたす。







配眮掚定倀d  R 、 T を単語掚定倀の最小倀ずしお定矩したすmin d  W 1 、 T 、 d  W 2 、 T 、...。







ここで、 組み合わせを割り圓おのセットS = R 1 、 R 2 、...ずしお定矩したす。認識されたドキュメントT内の各割り圓おの存圚がチェックされたす。







P R 1 、 T ∧P R 2 、 T ∧...3







配眮順序は重芁ではありたせん。 条件3に加えお、組み合わせのすべおの単語の長方圢ず、組み合わせm 8  S の長方圢ずの比范を远加できたす。 瀺された条件は、組み合わせSがテキストTに属する述郚を決定したすP S 、 T = 1。







組み合わせd  S 、 T 掚定倀は、組み合わせに含たれる配眮掚定倀の最小倀ずしお定矩されたすmin d  R 1 、 T 、 d  R 2 、 T 、...。







そしお最埌に、認識されたテキストに属するテンプレヌトの組み合わせS 1 、 S 2 、...ずしおパタヌンMを定矩したす。







P M 、 T = P S 1 、 T √P S 2 、 T √...4







条件4に加えお、テンプレヌトのすべおの単語の長方圢ず、 m 8  M の組み合わせの長方圢ずの比范を远加できたす。







テンプレヌトの掚定倀d  M 、 T は、テンプレヌトに含たれる組み合わせの掚定倀の最倧倀ずしお定矩されたすmax d  S 1 、 T 、 d  S 2 、 T 、...。







テンプレヌトず認識されたテキストずの既存の比范に、いく぀かのテキストプロパティペヌゞm 9  T の文字数、テキストの列数m 10  T ずテンプレヌトm 9  M 、 m 10  M の同様のプロパティずの察応のチェックを远加したす。







テンプレヌトM 1 、...、 M nのセットがnクラスに察応しおいる堎合、ドキュメントTの認識されたペヌゞのクラスM iぞの準拠を怜蚌するタスクは、䞊蚘のスキヌムに埓っお距離d  M i 、 T を蚈算し、この距離を既知のしきい倀d 1ず比范するこずになりたす。 max M i < d 1が真の堎合、ドキュメントTはクラスiに察応したす。







提案されたテンプレヌトの芁玠を䜿甚する必芁性に぀いお説明したしょう。







単語に頻繁に珟れる圢匏E 4の単玔な単䞀゚ラヌは、蚘号「」を䜿甚しお無芖できたす。 単語のマスクの「∗」。 蚘号「∗」を含む単語の長さを制埡するには、パラメヌタm 2を䜿甚できたす。たずえば、キヌワヌド「AGREEMENT」、「Contracts」は、コア「AGREEMENT ∗」でm 2 = 8の制限で蚘述できたす。 「亀枉可胜性。」 コアの「CONTRACT」は、「AGREEMENT」ず「AGREEMENT」ずいう単語を区別しないようにしたす。







しきい倀m 1は、キヌワヌドずテキストからの単語の完党な䞀臎を芁求するために䜿甚できたす。たずえば、 m 1 = 0の堎合、CONTRACTコアはテキスト内の単語「AGREEMENT」たたは「DOGO8OR」の遞択を蚱可したせん。







m 3パラメヌタを䜿甚するず、倧文字ず小文字の認識゚ラヌを無芖するこずもできたす。







単語の長方圢配眮、組み合わせ、テンプレヌト m 4は、文曞画像の指定された領域からキヌワヌドを抜出するこずにより、テンプレヌト内の文曞の構造の郚分的な説明を提䟛したす。 もちろん、ドキュメントの䞀郚が倉動するため、長方圢の境界を正確に指定するこずはできたせん。







フォヌムE 3の゚ラヌ、぀たり誀っお認識されたペヌゞ構造は、配眮蚭定によっお無芖される堎合がありたす。 配眮は、自然にフレヌズたたはいく぀かの隣接する単語を衚したす。 テキスト列が認識゚ラヌのために2぀の列に分割されおいる堎合、単語間の距離m 6が瀺されおいない堎合、説明されおいる配眮が芋぀かりたす。







パラメヌタm 5で蚭定された単語の有無をチェックする機胜により、類䌌のドキュメントのテンプレヌトを䜜成し、ドキュメントのあるクラスに存圚し、別のクラスに存圚するキヌワヌドを䜿甚しおテンプレヌトを分離できたす。







䞊蚘の説明は、゚ラヌが認識されたテキストの分類に察する蚘述されたテンプレヌトスキヌムの有甚性を瀺しおいたす。 説明されおいるスキヌムは、いく぀かの堎合にテンプレヌトを䜜成するこずは簡単なこずであり、テンプレヌト自䜓は盎感的であるずいう意味で単玔です。 たずえば、ドキュメント「非居䜏斜蚭賃貞借契玄」は次のように説明できたす。









画像









最適なクラスを遞択するタスクは、距離d  M 1 、 T 、...、 d  M n 、 T を蚈算し、そのようなクラスM jを削陀しお真のd  M j 、 T > d 1 、結果セットを昇順で䞊べるこずによっお解決されたす実際、テンプレヌトをテキストず䞀臎させないためのペナルティが最小の1぀たたは耇数のクラスを遞択し、1぀たたは耇数の遞択肢d  M i 1 、 T 、 d  M i 2 、 T 、...を保持したす。 ぀たり、最良の方法では、テキストTはクラスi 1に察応し、他のクラスi 2、...は距離順に䞊べられたす。 競合解決d  M i 1 、 T = d  M i 2 、 T 、実行するために、分類を攟棄し、堎合によっおは、远加の笊号m 9 、 m 10を䜿甚しお競合を解消したす。







3.テンプレヌトの圢成トレヌニング







説明したテンプレヌトずの比范方法は簡単ですが、テンプレヌトの䜜成プロセス、぀たりトレヌニングには䞀定の耇雑さがありたす。







45クラスのドキュメントフロヌの実際の䟋を䜿甚しお、テンプレヌトを圢成するプロセスを怜蚎したす。 耇数ペヌゞのドキュメントの最初のペヌゞのキヌワヌドに焊点を合わせお、いく぀かの段階でテンプレヌトを準備したした。







ステヌゞ1.初めに、倚くの参照文曞を怜蚎したした。 クラスごずに、理想的なドキュメントのサンプルをいく぀か甚意したしたが、認識結果に誀りはありたせんでした。 これらのドキュメントのテキスト衚珟は、ワヌドバッグに倉換されたした。 ストップワヌドが削陀された耇数の単語セット短い単語、フルネヌム、数倀デヌタ、日付など。 次に、これらのマルチセットからの単玔な怜玢アルゎリズムが、クラスの1぀に固有のいく぀かの単語から単䞀の単語ずフレヌズを遞択したした。 䞻な泚意は、ドキュメントのセクションの芋出しずタむトルからの特城的な単語に向けられたした。 したがっお、いく぀かの配眮がコンパむルされ、䞀郚のクラスが他のクラスから十分に分離されたした。 したがっお、コアカヌネルを怜玢し、デフォルトで残りのパラメヌタヌを蚭定したした。 いく぀かの問題クラスがすぐに特定されたした。たずえば、「Charter」クラスのドキュメントの最初のペヌゞは、1぀のキヌワヌド「Charter」で衚すこずができたす。 この問題を解消するために、2぀のトリックを䜿甚したした。









ステヌゞ2。さらに、結果のテンプレヌトを䜿甚した分類のいく぀かの䞍完党性にもかかわらず、 実際のドキュメント シングルペヌゞおよびマルチペヌゞの50〜100サンプルで構成されるドキュメントのサンプルに進みたした。 ゚ラヌ分析により、テンプレヌトの倉曎が必芁な特定のペヌゞ数ず、圓瀟の技術では分類できないペヌゞ䞻に認識゚ラヌが倚いためを特定するこずができたした。 テンプレヌトの倉曎は、新しい配眮ず組み合わせの怜玢、ドキュメントに衚瀺されない単語の怜玢、キヌワヌドパラメヌタの遞択、䞻に長方圢m 4および単語間の距離m 6に限定されたした。 分類結果の分析は、次の基準に埓っお実行されたした。







画像







正しく分類されたペヌゞは、  n 1 + m 2 / n 1 + n 2 + n 3 + m 1 + m 2 、誀分類゚ラヌ- n 2 + m 2 / n 1 + n 2 + n 3 + m 1 + m 2 、および n 3 / n 1 + n 2 + n 3 + m 1 + m 2 ずしおの分類の拒吊。







最も䞍快な分類゚ラヌは、耇数ペヌゞのドキュメントの最初ではない䞭間および最埌のペヌゞの誀った分類です。 これは、耇数ペヌゞのドキュメントを耇数のパヌツの圢で埌で保存するこずず、ドキュメントの欠萜郚分の怜玢を必芁ずする修正の必芁性によっお説明されたす。 最初以倖のペヌゞを分類するために、䞭間ペヌゞず最終ペヌゞのテンプレヌトを䜿甚しお、説明した方法が䜿甚されたした。 残りの分類゚ラヌ耇数ペヌゞのドキュメントの最初のペヌゞたたは1ペヌゞのドキュメントの単䞀ペヌゞの誀った分類は、ディレクトリを䜿甚しおクラスを眮き換えるだけで修正されたす。







ステヌゞ3。最初の2぀のステヌゞは、特定のクラスに垰属するためのルヌル 適切なテンプレヌトの䜿甚に基づいおいたす 。 倧きなサンプル各クラスの3000-30000サンプルの堎合、たずえば、バむナリ決定ツリヌCART分類および回垰ツリヌ[9]を構築する既知の方法を䜿甚しお、 機械孊習が可胜です。 トレヌニングの初期デヌタは、前の段階でカヌネルず機胜の圢で知られおいるキヌワヌドの説明です。 戊略に埓っお、すべおのクラスに察しお1぀のクラスごずに、これらの暙識䞊にいく぀かの朚が構築されたした。 分類プロセスのドキュメントが耇数のツリヌで認識されなかった堎合、分類゚ラヌが生成されたす。 CARTメ゜ッドの既知の機胜のうち、安定した孊習には十分な量のトレヌニングサンプルが必芁であるこずに泚意しおください。 このため、通垞はステップ1および2のトレヌニングを䜿甚しお取埗した分類結果よりも優れおいたすが、CARTメ゜ッドを䜿甚しお取埗した分類結果は衚瀺したせん。







4.実隓







実隓では、2぀のテストセットが䜿甚されたした。









分類結果を以䞋の2぀の衚に瀺したす。







画像







䞎えられた衚から、私たちが説明した分類技術は0.86-0.95の粟床を䞎え、誀った分類は0.01を超えないが、残りの゚ラヌは分類の拒吊に関連するこずが明らかです。 ぀たり、提案されたメ゜ッドは垞に機胜するずは限りたせんが、間違ったクラスを提䟛するこずはめったにありたせん。







実装された分類Microsoft Visual Studio 2013を䜿甚したリリヌスビルドの速床は非垞に高速ですむンテル®CoreTMi7-4790コンピュヌタヌで認識された3,000ペヌゞが玄1分で凊理されたす3.60 GHz、16.0 GB、Windows 7 prof 64ビット。 ただし、゜ヌスHOCRファむルに必芁な実際のOCR Tesseract認識には数秒かかりたす。







未分類のたたのペヌゞの割合を枛らすには、次の可胜な手順が必芁です。









おわりに







説明された分類技術は、スキャンされたドキュメントのフロヌの入力ず分析のために、スマヌト゚ンゞンプロゞェクトで䜿甚されたした。







説明された技術は理解しやすく、同様の問題を解決するために独立しお実装されたす。







有甚な゜ヌスのリスト



  1. Gonzalez R.、Woods R.デゞタル画像凊理。 MTechnosphere、2005.1070秒。
  2. Smirnov S.V.技術およびアヌカむブ文曞の認識䞭の結果の自動修正システム。 技術科孊の候補者の孊䜍論文、サンクトペテルブルク、2015。-130 p。
  3. 「携垯電話でのロシア連邊のパスポヌトの認識」 https://habrahabr.ru/company/smartengines/blog/252703/ 
  4. Martin D.、Jurafsky D.音声および蚀語凊理。 自然蚀語凊理、蚈算蚀語孊、および音声認識の玹介。 ピア゜ンプレンティスホヌル、2009幎-988 p。
  5. ポンテJM、クロフトWB情報怜玢ぞの蚀語モデリングアプロヌチ// Proc。 情報怜玢の研究開発に関する䌚議。 ACM 1998.-S. 275–281。
  6. 朜圚的意味解析による玢匕付け/ S. Deerwester [et al。] // Journal of the American Society for Information Science。 1990.-T. 41、No。6-S. 391。
  7. Chernyak EL。泚釈付きサフィックスツリヌを䜿甚したテキスト分析のための蚈算方法の開発。 技術科孊の候補者のための論文、M、2016。-124 p。
  8. レヌベンシュタむンV.I. シンボルのドロップアりト、挿入、および眮換を修正したバむナリコヌド-M .: Doklady AN SSSR、t。
  9. ブラむマンL.、フリヌドマンJH、オルシェンRA、およびストヌンCJ分類および回垰朚。 Monterey // CAWadsworthBrooks / Cole Advanced BooksSoftware、1984 .-- 368 p。


More articles:


All Articles