(57)【要約】【課題】相互に接触した文字を正しく認識する構成を提供することを目的とする。【解決手段】文字列を読み取って得た線図を複数の部分に分割し、分割された線図の複数の部分を組み合わせ、複数の候補の文字列を得、複数の候補の文字列から一の文字列を選択する構成であって、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含め、あるいは隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含めるようにした。【選択図】図９
2009199102.tif 000002
【特許請求の範囲】
【請求項１】
文字認識プログラムであって、
コンピュータを、
文字列の記入されている帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割手段と、
前記分割手段により分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得手段と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択手段として機能させるためのプログラムであって、
前記候補文字列取得手段は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の手段と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の手段とのうちの少なくとも一の手段を有する構成とされてなるプログラム。
【請求項２】
前記候補文字列取得手段における前記第１の手段は、隣接する文字間の接触に係る文字線につき、当該接触に係る文字線が前記隣接する文字のうちの一の文字に属する場合と、他の文字に属する場合と、前記一の文字及び他の文字の双方に属する場合とを夫々含む候補の文字列を、前記複数の候補の文字列に含める構成とされてなる請求項１に記載のプログラム。
【請求項３】
前記候補文字列取得手段は、前記線図を複数の部分に分割した各々の部分を、隣り合うノード間のリンクに対応させ、任意のノード間に含まれる部分パターンを統合したパターンが一文字となる場合、対応するノード間にリンクを生成して前記統合パターンを対応させ、当該リンクを相互に接続することで、前記複数の候補の文字列の各々に対応するパスを生成するパス生成手段を有し、
前記文字列選択手段は、前記パスを構成する前記リンクの各々につき、対応する前記線図の部分の文字認識に要される認識コストをその重みとして設定する文字認識コスト設定手段と、
前記各リンクの重みをパス毎に合計して得られた認識コスト合計が最小となる一のパスを、前記一の文字列に係るパスとして選択するパス選択手段とを有し
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線に対応するリンクとして直列的に接続された２個のリンクを設け、一のリンクは当該接触に係る文字線を有し、他のリンクは一のリンクと同じ当該接触に係る文字線を有する構成とされ、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線に対応するリンクとして当該接触に係る文字線に並列的に接続された２個のリンクを設け、且つ、当該２個のリンクのうち、一のリンクは当該接触に係る文字線を有し、他のリンクは迂回のためのリンクで空白パターンを有するとされてなる
請求項１又は２に記載のプログラム。
【請求項４】
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線が、当該文字列が延在する方向に略直交する方向に沿って延在する場合に適用され、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線が、当該文字列が延在する方向と略同一の方向に沿って延在する場合に適用されてなる
請求項１乃至３のうちの何れか一項に記載のプログラム。
【請求項５】
文字認識装置であって、
文字列の記入されている帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割手段と、
前記分割手段により分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得手段と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択手段とを有し、
前記候補文字列取得手段は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の手段と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の手段とのうちの少なくとも一の手段を有する構成とされてなる文字認識装置。
【請求項６】
文字認識方法であって、
文字列の記入されている帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割段階と、
前記分割段階で分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得段階と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択段階とを有し、
前記候補文字列取得段階は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の段階と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の段階とのうちの少なくとも一の段階を有する構成とされてなる文字認識方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は文字認識プログラム、文字認識装置及び文字認識方法に関する。
【背景技術】
【０００２】
例えば図１に示されるような手書き数字をＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）等の利用により、自動認識する場合を考える。
【０００３】
図２はこの場合において、例えば候補文字ラティスの手法を使用した場合の例を示す。
【０００４】
この場合図２（ａ）に示される如く、相互に接触した数字よりなる手書き文字が、図２（ｂ）、（ｃ）、（ｄ）に示される経過を経て分離され、文字認識がなされる。
【０００５】
ここでこの場合、図３（ａ）乃至（ｄ）に示される例や図４（ａ）乃至（ｃ）に示される例の如く、相互に接触した数字よりなる手書き文字を自動認識する際に誤認識を生じる場合が想定される。
【特許文献１】特開平０７−１９２０９４号公報
【特許文献２】特開平０８−２０２８２２号公報
【特許文献３】特許第３７９８１７９号
【非特許文献１】村瀬、新谷、若原、小高, “言語情報を利用した手書き文字列からの文字切り出しと認識”, 電子情報通信学会論文誌, Vol.J69-D, No.9, pp.1292-1301 (1986)
【非特許文献２】H. Fujisawa, Y. Nakano and K. Kurino,“SegmentationMethods for Character Recognition: From Segmentation to Document StructureAnalysis”,Proc. IEEE, Vol.80, No.7, pp.1079-1092 (1992)、1087ページの図
【非特許文献３】アルゴリズム辞典、共立出版社、第４５５乃至４５６頁「Ｄｉｊｋｓｔｒａ法(賛嘆法)」、５６３頁「動的計画法」
【発明の開示】
【発明が解決しようとする課題】
【０００６】
文字認識の精度を向上し得る文字認識プログラム、文字認識装置及び文字認識方法を提供することを課題とする。
【課題を解決するための手段】
【０００７】
文字認識プログラム、文字認識装置及び文字認識方法において、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の手段による処理、あるいは隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを選択対象の候補の文字列に含める第２の手段による処理のうちの少なくとも何れかの処理を実施するようにした。
【０００８】
その結果、文字認識の際の選択対象の候補の文字列に、隣接する文字間の接触に係る文字線が複製され、当該複製に係る文字線がその要素として含められる。あるいは、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とが選択対象の候補の文字列に含められる。もって文字認識の精度を向上し得る。
【発明の効果】
【０００９】
文字認識の精度を向上し得る文字認識プログラム、文字認識装置及び文字認識方法を提供するができる。
【発明を実施するための最良の形態】
【００１０】
以下実施例につき、詳細に説明する。
【００１１】
当該実施例では、文字認識を行う場合、紛らわしいケースの可能性を考慮し、後述する文字間の続き線のような不要な文字線を除去する処理、あるいは後述する文字間の辺接触を分離する処理を、候補文字ラティス内において表現する。その結果、周知の動的計画法等の最短パス探索の手法を、そのような処理に対しても、統一的に適用できる。即ち、認識対象の文字列全体の整合性を考慮した上で最適なパスを決定できるようになる。
【００１２】
ここで上記パスとは、候補文字ラティスに含まれる複数の経路を意味し、複数の候補の文字列の各々に対応する経路を意味する。
【００１３】
以下に実施例による具体的な手順を説明する。
【００１４】
（ｉ）認識対象の文字列において相互に隣接する２文字間が辺接触の状態で接触している際の、当該接触に係る文字線を構成する文字線の候補を取得する。そして当該文字線の候補を候補文字ラティスにおいて２重登録する。
【００１５】
その結果、候補文字ラティス上で、当該文字線の候補を、前記相互に隣接する２文字のうちの左の文字に含める場合、右の文字に含める場合及び、前記２文字の双方に含める場合の計３通りの可能性を考慮することができる。尚ここで文字線とは、認識対象の文字列に含まれる文字を構成する線（但し後述の如く、説明の便宜上、続き線も文字線と称する）を意味する。そして当該候補文字ラティスに基づき、動的計画法等の最短探索の手法を適用して最も確からしいパス、すなわち複数の候補の文字列のうちの一の文字列を決定する。その結果、このようにして決定された一の文字列が認識対象の文字列そのものである確率、すなわち認識結果が正しくなる可能性を高めることができる。
【００１６】
すなわち、認識対象の文字列上で隣接する２文字間で相互に文字線が重なって２文字が相互に接触している場合（すなわち辺接触の状態）でも、当該２文字を正しく切り分けることが可能となる。
【００１７】
また、このように認識対象の文字列上で隣接する２文字間で相互に文字線が重なって２文字が相互に接触している場合とは異なる場合として以下の場合が想定される。すなわち、認識対象の文字列上で隣接する２文字間で、そのうちの一の文字に含まれる文字線が、他の文字に対し、2箇所で接触した状態で2文字が相互に接触する場合である。
【００１８】
外観上は前者の場合と後者の場合とが区別しにくい傾向にあるが、上記の2重登録により、両者の区別がしやすくなる。
【００１９】
以下当該2重登録の処理（以下「辺接触候補処理」と称する）につき、図5，図６とともに具体例を挙げて説明する。
【００２０】
図５（ａ）の左側には、図５（ａ）の右側に示される如くの、「０３」の手書き文字を認識する場合に得られた候補文字ラティスの例を示す。
【００２１】
まず図示の候補文字ラティスを例に挙げ、候補文字ラティスの作成について説明する。
【００２２】
候補文字ラティスにおいて、その最左端の黒丸（以下これらの黒丸をノードと称し、最左端のノードを開始ノードと称する）から最右端のノード（以下終了ノードと称する）へ至る経路が上記パスである。例えば図５（ａ）の例の場合、同図の候補文字ラティスの構成から明らかなように、開始ノードから発し、終了ノードに至る経路が複数存在する。これは、当該候補文字ラティスには複数のパスが含まれていることを意味し、すなわち当該複数のパスに夫々対応する複数の文字列の候補（すなわち候補の文字列）が含まれていることを意味する。
【００２３】
また上記複数のパスの各々はリンクをその構成要素とする。リンクとは、パスがノードを含まない場合には当該パスそのものがリンクである。パスがノードを含む場合、当該ノードが連結する、パスの構成要素がリンクである。
【００２４】
ここで以下、このような候補文字ラティスに含まれるパスの各々を構成する各リンクを示す際、当該リンクに付された番号（後述する）で示すものとする。例えば図５（ａ）の候補文字ラティス中、最上段のリンクには番号０（９８）が付されているので、当該リンクをリンク０（９８）と称する。
【００２５】
ここでリンク０（９８）は、上記手書き文字「０３」を、当該２文字「０」、「３」が接触した一文字として認識する場合（すなわち誤った認識の場合）の、候補の文字列に対応するパスを構成するリンクである。
【００２６】
上記各リンクに付された番号について以下に説明する。当該番号のうち、最初の一桁が認識結果の文字を示す。また後続の括弧内の数値は当該認識に要するコスト（すなわち認識コスト）を示し、当該認識コストが低いほど当該認識結果が確からしいことを意味する。最上段のリンク０（９８）の例では、上記の如く２文字が接触して一文字として認識され、その認識結果が「０」であり、その場合の認識コストが９８である。
【００２７】
同様に図示の如く、当該最上段のリンク０（９８）のすぐ下のリンク０（０２）及びその右側に連結した中段のリンク３（０５）が他のパスを構成している。当該パスは、上記手書き文字「０３」を、当該２文字「０」、「３」を分離し、正しく２文字として認識する場合の、候補の文字列に対応するパスである。このパスは後述する如く、当該手書き文字「０３」が正しく分離され、「０３」の正しい認識に対応するパスである。ここでは２文字が相互に接触した当該接触に係る文字線が、正しく当該文字（０）の一部を構成する文字線として判断された場合のパスである。ここで上記接触に係る文字線とは、左の文字「０」を構成する、右側に垂直に延在する部分の文字線である。すなわちこのパスに係る認識結果は「０」、「３」であり、認識コストは０２＋０５＝０７である。
【００２８】
同様に中段のリンク０（３１）、及びその右下に連結しているリンク８（９７）が更に他のパスを構成する。このパスは、上記手書き文字「０３」を、２文字と認識するパスである。しかしながらこの場合、上記の場合と異なり、２文字が相互に接触した接触に係る文字線が右の文字「３」の一部を構成する文字線と判断された場合のパスである。すなわち上記の如く本来は左の文字「０」の右側の垂直に延在する部分の文字線が、右の文字を構成する文字線と誤って認識された場合のパスである。このパスに係る認識結果は「０」、「８」であり、認識コストは３１＋９７＝１２８である。上記正しい場合の認識コスト０７（すなわち、７）に比し、明らかに認識コストが高く、確からしさが低いことが示されている。
【００２９】
同様に下段のリンク０（０２）、及びその右上に連結しているリンク８（９７）が更に他のパスを構成する。このパスは、上記手書き文字「０３」を、２文字と認識するパスである。しかしながらこの場合、上記の場合と異なり、２文字が相互に接触した当該接触に係る文字線が両文字「０」、「３」の各々の一部を構成する文字線として判断された場合のパスである。すなわち上記の如く、本来は左の文字「０」の右側の垂直に延在する部分の文字線が、左右両文字の各々に属するものとして判断された場合のパスである。したがってこのパスは誤った認識に対応するパスである。すなわちこのパスに係る認識結果は「０」、「８」であり、認識コストは０２＋９７＝９８である。この場合も上記正しい場合の認識コスト７に比し、明らかに認識コストが高く、確からしさが低いことが示されている。
【００３０】
候補文字ラティスを使用した文字認識では、このように、読み取った手書き文字を構成する線図の構成から、当該手書き文字に対する複数の候補の文字列を取得する。そして当該夫々の候補の文字列を当該候補文字ラティスを構成するパスに夫々対応させる。その上で、各パスの確からしさ、すなわち該当する複数の候補の文字列の確からしさを上記認識コストにより評価する。この評価は、後述の如く、各リンクに重み付けを行うこと実現される。そしてその評価の結果に基づき、一のパス、すなわち一の候補の文字列を選択する。ここで一のパスを選択するために、上記最短パス探索の手法を利用することができる。当該選択された候補の文字列が当該読み取った手書き文字の認識結果として得られる。
【００３１】
上記実施例の方法によれば、上記の如く、図５（ａ）の例のように２文字が接触しているような場合であっても、実際の文字の可能性として想定される全ての場合に対応するパスを候補文字ラティスに含めることができる。すなわち図５（ａ）の例の場合、両文字の相互接触に係る文字線がいずれかの文字に属する場合の各々に対応するパス、すなわち上記リンク０（０２）、３（０５）のパス及び上記リンク０（３１）、８（９７）のパスが候補文字ラティスに含まれている。更に、当該文字線が両文字の各々に属する場合に対応するパス、すなわち上記リンク０（０２）、８（９７）のパスが含まれている。その結果、正しいパスが確実に候補文字ラティスに含まれるようになり、もって文字認識の精度を効果的に向上できる。
【００３２】
このように本実施例による方法では、２文字が接触しているような場合に、実際の文字の可能性として想定される全ての場合、すなわち以下の計３通りの場合のそれぞれに対応するパスを候補文字ラティスに含めることができる。すなわち（１）両文字の相互接触に係る文字線が左側の文字に属する場合、（２）右側の文字に属する場合、及び（３）両文字の各々に属する場合（すなわち辺接触の場合）の計３通りの場合である。このように計３通りの場合のそれぞれに対応するパスを候補文字ラティスに含めることが可能となる理由を以下に説明する。
【００３３】
すなわち、図５（ａ）の例で説明すると、両文字の相互接触に係る文字線に対応するリンクとして、直列的に連結する２本のリンク１（０９）を候補文字ラティスに含める。その結果、上記２文字が接触しているような場合に、実際の文字の可能性として想定される３通りの場合のそれぞれに対応するパスを含めることが可能となる。
【００３４】
より具体的には、図５（ａ）の候補文字ラティス中、上記両文字の相互接触に係る文字線に対応する、直列的に連結する２本のリンク１（０９）の両端のノード及び当該相互連結に係るノードの計３個のノードが得られる。そしてこれら３個のノードのうち、左側のノードを通るパスが、上記（２）の場合、すなわち上記両文字の相互接触に係る文字線が右側の文字に属する場合に対応する。同様に上記３個のノードのうち、中央のノードを通るパスが、上記（３）の場合、すなわち上記両文字の相互接触に係る文字線が両文字の各々に属する場合に対応する。同様に上記３個のノードのうち、右側のノードを通るパスが、上記（１）の場合、すなわち上記両文字の相互接触に係る文字線が左側の文字に属する場合（すなわち正しいパス）に対応する。
【００３５】
図５（ｂ）は他の手書き文字列の例であり、図５（ａ）の例の場合同様、両文字の相互接触に係る文字線に対応するリンクとして、直列的に連結する２本のリンク１（０８）が候補文字ラティスに含められている。その結果図５（ａ）の例の場合同様、２文字が接触している場合に実際の文字の可能性として想定される３通りの場合のそれぞれに対応するパスを候補文字ラティスに含めることが可能となる。
【００３６】
図６は上述の本実施例の方法における辺接触候補処理の処理フローを示す。
【００３７】
すなわち、図６中、当該処理は、ステップＳ１（パターン分割）で、読み取られた文字画像から得られた線図に基づき、当該線図を複数の断片に分割する。図５（ａ）の例の場合、当該処理は、読み取られた「０３」の手書き文字の線図を、図５（ａ）の候補文字列ラティスを構成するリンク０（０２）、３（０５）、０（３１）、８（９７）、１（０９）の夫々に付されている文字線の如くの、各断片に分割する。
【００３８】
なお前記線図は、例えば文字列の記入されている帳票をスキャン・撮影することにより得られたものである。
【００３９】
次にステップＳ２（辺接触候補判定）にて、上記の如く、当該処理は、２文字の相互接触の当該接触に係る文字線が両文字の各々に重複して属する場合が想定され得るか否かを判定する。この場合の判定方法は図１５とともに後述する。
【００４０】
当該処理はこの判定の結果（ステップＳ３），２文字の相互接触の当該接触に係る文字線が両文字の各々に重複して属する場合が想定され得ると判定されるとステップＳ４に進み、そうでない場合にはステップＳ４をスキップして直接ステップＳ５に進む。
【００４１】
ステップＳ４では、当該処理は、当該２文字の相互接触の当該接触に係る文字線を２重登録する。すなわち上記図５（ａ）の例では、当該処理は、２文字の相互接触の当該接触に係る文字線に対応するリンク１（０９）を２本直列的に接続して候補文字ラティスに含める。
【００４２】
ステップＳ５では、当該処理は、このようにして生成した候補文字ラティスにつき、当該候補文字ラティスに含まれる各リンクに対し、対応する文字認識結果を得る。上記図５（ａ）の例の場合、上記各リンクに付された番号のうち最初の一桁の番号が当該文字認識結果である。
【００４３】
次にステップＳ６では、当該処理は、上記各リンクに対し、上記文字認識に要した認識コストを計算する。
【００４４】
最後にステップＳ７では、当該処理は、最短パス探索の手法等により、ステップＳ６で算出した各リンクの認識コストに基づき、当該候補文字ラティスに含まれるパスのうち、最も確からしいパスを決定し、対応する候補の文字列を文字認識結果として得る。
【００４５】
（ｉｉ）また本実施例では、続き線候補処理を併せて行ってもよい。当該続き線候補処理につき、以下に説明する。
【００４６】
認識対象の文字列において相互に隣接する２文字間が続き線（後述）を介して接触している場合が想定される際の、当該接触に係る文字線を構成する文字線の候補を取得する。そして当該文字線の候補に対応するリンクを候補文字ラティスにおいて迂回するようなリンクを付加する。そして当該付加されたリンクに空白画像（以下これをＮＵＬＬ画像とも称する）を対応させる。NULL画像の認識文字種はφ（NULL）であり、認識コストｄは実験により適切に定めることができる。その結果、続き線の除去を、動的計画法などによる最短パス探索法を使う候補文字ラティスの手法の枠組み内で実現できる。更に、該当する文字線が続き線なのか、あるいは、これと区別しにくい横文字線（後述）なのか、についての判定も、認識対象の文字列を構成する他の文字線に対する処理と共通の枠組み内で処理可能である。
【００４７】
上記続き線及び横文字線につき、図４とともに説明する。
【００４８】
図４（ａ）は２個の数字よりなる文字列「００」の手書き文字を示す。同図に示す如く、当該手書き文字には、両文字「００」の間の上部に両文字間を接触するように水平に延在する文字線が存在する。当該文字線が上記続き線である。すなわち文字「００」の一部を構成するものではなく、手書きの過程で筆記具が用紙上を滑ることで描かれた線である。したがって当該続き線は文字認識においては除去されるべきものである。なお上記の如く続き線は文字を構成するものではないが、説明の便宜上、文字線として説明する
図４（ｂ）は２個の数字よりなる文字列「５０」の手書き文字を示す。同図に示す如く、当該手書き文字において、両文字「５０」のうちの数字「５」の最上部を構成する水平に延在する文字線の右端が次の数字「０」の上端に接触している。当該文字線が上記横文字線である。当該横文字線は手書きの過程において最初の数字「５」から次の数字「０」の筆記に移る際、そのまま筆記具が用紙上から離間しなかったため、次の数字「０」と接触したものである。当該横文字線は上記続き線と異なり最初の文字「５」の一部を構成する文字線であるため、文字認識において考慮されるべきものである。しかしながら上記の如く外形上は上記続き線との区別が困難なため、誤って除去され誤認識の要因となる場合が想定される。
【００４９】
図７はこの続き線候補処理において、続き線の候補の文字線に対しＮＵＬＬ画像を対応させたリンクを付加する際の候補文字ラティスの例を示す。
【００５０】
図７（ａ）の左側は、図４（ｂ）の例の手書き文字列「５０」に対して得られた候補文字ラティスの例を示す。当該候補文字ラティス中、中段中央のリンク３（９９）が続き線の候補である、水平方向に延在する文字線に対応するリンクである。同図に示す如く、当該リンク３（９９）を迂回するようにＮＵＬＬ画像に対応するリンクφ（ｄ）が設けられる。ここでＮＵＬＬ画像は上記の如く空白画像である。その結果、当該ＮＵＬＬ画像に対応するリンクφ（ｄ）を有するパスでは、当該リンクは単に迂回のためのリンクにすぎない。当該候補文字ラティスには、当該続き線の候補のリンク３（９９）を有するパスと、これを迂回するＮＵＬＬ画像のリンクφ（ｄ）を有するパスとの２本のパスが含まれる。その結果、当該続き線の候補が上記続き線である場合（すなわち図４（ａ）の例の場合）と、横文字線である場合（図４（ｂ）の例の場合）との２つの場合につき、上記動的計画法による最短パス探索の手法に一律に組み込んで処理することができる。その結果当該２つの場合が正しく評価され、誤認識の可能性を効果的に低減できる。
【００５１】
例えば図７（ａ）の例の場合、上記の如くリンク３（９９）が対応する続き線の候補は実際には数字「５」の構成要素たる文字線であり、上記横文字線である。上記候補文字ラティスによれば上記の如く当該続き線の候補が続き線である場合と横文字線である場合とに対し、一律に評価される。その結果、ＮＵＬＬ画像のリンクφ（ｄ）を有するパスより、続き線の候補のリンク３（９９）を有するパスの方が合計の認識コストが小さくなれば、当該続き線の候補のリンク３（９９）を有するパスが選ばれる可能性が高まる。すなわち図７（ａ）の右側に示す如く、当該文字列が正しく「５０」と認識される可能性が高まる。そして、そのような結果が得られるよう、上記の如く、ＮＵＬＬ画像の認識コストｄを実験等により得ることができる。
【００５２】
図７（ｂ）の左側は、認識対象の文字列が、図４（ｂ）と同様の「００」の例に対して得られた候補文字ラティスの例を示す。図７（ｂ）の例の場合、上記の如く、リンク３（９９）が対応する続き線の候補は当該文字列を構成する２個の数字「００」間を接触している続き線としての文字線である。当該候補文字ラティスによれば上記の如く当該続き線の候補が実際に続き線である場合と横文字線である場合とに対し、一律に評価される。その結果、ＮＵＬＬ画像のリンクφ（ｄ）を有するパスの方が、続き線の候補のリンク３（９９）を有するパスの方より合計の認識コストが小さくなれば、当該ＮＵＬＬ画像φ（ｄ）を有するパスが選ばれる可能性が高まる。当該パスでは、ＮＵＬＬ画像のリンクφ（ｄ）により続き線の候補のリンク３（９９）が迂回され、もって当該続き線の候補の文字線が除去される。したがって当該パスが選ばれると図７（ｂ）の右側に示す如く、当該文字列が正しく「００」と認識される可能性が高まる。そして、そのような結果が得られるよう、上記の如く、ＮＵＬＬ画像の認識コストｄを実験等により得ることができる。
【００５３】
上記本実施例における続き線候補処理の処理フローを図８に示す。
【００５４】
すなわち、図８中、ステップＳ１１乃至Ｓ１７は、夫々上述の図６のフローチャートにおけるステップＳ１乃至Ｓ７に対応する。それらのうち、ステップＳ１２乃至Ｓ１４がステップＳ２乃至Ｓ４と異なる以外、ステップＳ１１，Ｓ１５乃至Ｓ１７は、夫々図６のステップＳ１，Ｓ５乃至Ｓ７と同一である。したがって異なるステップＳ１２乃至Ｓ１４についてのみ説明し、他のステップに対する重複する説明を省略する。
【００５５】
ステップＳ１２（続き線候補判定）にて、当該処理は、上記の如く、２文字の相互接触の当該接触に係る文字線が続き線である場合が想定され得るか否かを判定する。この場合の判定方法は図１６とともに後述する。
【００５６】
この判定の結果（ステップＳ１３），２文字の相互接触の当該接触に係る文字線が続き線である場合が想定され得ると判定されると、当該処理は、ステップＳ１４に進み、そうでない場合にはステップＳ４をスキップして直接ステップＳ１５に進む。
【００５７】
ステップＳ１４では、当該処理は、認識対象の文字列中、隣接する２文字の相互接触の当該接触に係る文字線、すなわち続き線の候補の文字列に対し、これを迂回する、ＮＵＬＬ画像に対応させたリンク、すなわち上記リンクφ（ｄ）を生成する。すなわち当該処理は、上記図７（ａ）の例では、２文字の相互接触の当該接触に係る文字線に対応するリンク３（９９）に並列的に接続するリンクとして上記ＮＵＬＬ画像に対応させたリンクを設け、候補文字ラティスに含める。
【００５８】
尚、図６及び図８とともに上述した各処理は、図２０に示される如くの構成を有するコンピュータを使用することで実現可能である。すなわち後述の如く、当該コンピュータのＣＰＵに当該処理を実行させるためのプログラムを準備し、更に、文字画像を読み取るためのスキャナ（図示を省略）を当該コンピュータに接続する。そしてスキャナにより読み取られた読取画像に基づき、上記ＣＰＵが上記プログラムに記載された命令を順次実行することで、図６あるいは図８の処理を実行する。ここでスキャナで得られた文字画像に基づいて線図を得るための処理として、周知のＯＣＲの技術を利用することができる。
【００５９】
すなわち当該実施例では、光学的画像入力手段により帳票画像等から、特に文字枠が無い領域に自由に記入された画像データ中の文字を認識する文字認識装置において、候補文字ラティス生成部を備える。当該候補文字ラティス生成部では、図５及び６とともに上述の如く、重なっている可能性のある文字線あるいは文字線の一部（すなわち辺接触に係る文字線あるいはその一部）につき、予め辺接触の候補か否かを判定する。そして前記辺接触の候補と判定された文字線あるいは文字線の一部のパターン（すなわち線図）を前記ラティスにおいて２重登録する。そして文字認識によって前記ラティスのノード間のリンクに認識コスト（スコア）によって重みが付与される。当該重みに基づき、動的計画法によって最短距離のパス（スコアの場合は最長距離のパス）を求める。その結果、動的計画法を使った候補文字ラティスの手法の枠組み内で全体の整合性を考えて辺接触に係る隣接文字間の当該辺接触の分離が実現可能となる。
【００６０】
また当該実施例は、光学的画像入力手段により帳票画像等から、特に文字枠が無い領域に自由に記入された画像データ中の文字を認識する文字認識装置において、候補文字ラティス生成部を備える。当該候補文字ラティス生成部では、図７及び８とともに上述の如く、続き線の可能性のある文字線候補を予め続き線の候補か否か判定し、前記続き線の候補と判定された文字線に対応するパターン（すなわち線図）を前記ラティスのノード間のリンクとして登録する。その際、当該ノード間に前記リンクを迂回するようなリンクを設定し、そこにNULL画像を登録する。その結果、動的計画法を使った候補文字ラティスの手法の枠組み内で全体の整合性を考慮し、文字認識に不要な続き線の除去を実現可能となる。
【００６１】
本実施例にて実施可能な処理として、候補文字ラティスにおいて辺接触の候補の文字線を２重登録して含める処理（第１の手段による処理と称する）につき、図５及び６とともに述べた。更に、図７及び８とともに、候補文字ラティスにおいて続き線の候補に対し、これを迂回するリンクを登録して含める処理（第２の手段による処理と称する）を述べた。実施例においては、これら第１の手段による処理と第２の手段による処理のうち、その一方の処理のみを実施するようにしてもよい。また実施例において、これら第１の手段による処理と第２の手段による処理の両方の処理を併せて実施するようにしてもよい。
【００６２】
また上記第２の手段による処理において、前記候補文字ラティス中、続き線の候補が登録されているノード間のリンクを迂回するように設置されたノード間のNULL画像に対応する重みは、実験により適切に設定することができる。
【００６３】
以下上記実施例の構成につき、更に詳細に説明する。
【００６４】
図９は本実施例による文字認識装置の全体構成を示す。
【００６５】
当該文字認識装置１０は、帳票等をスキャナなどで取り込んで電子データ化し、白黒の２値画像に変換し、更に文字列を切り出して当該文字列に含まれる各文字線間の接触状態を示す接触パターンを判定する。これらの処理は既存の技術を利用して実現することができる。
【００６６】
本実施例では、上記接触パターンが得られた場合、文字を１文字ずつに切り出して認識する処理を行う。
【００６７】
当該文字認識装置１０は大略、候補文字ラティス生成部１６及び最短パス探索部１７を有する。候補文字ラティス作成部１６は更に、細線化部１１、グラフ化部１２、点接触・続き線候補判定部１３、辺接触判定部１４、及び候補文字ラティス作成部１５を有する。
【００６８】
細線化部１１は、入力された２値の接触パターンを、既存の手法で線幅が１（画素）の細線化パターンに変換する。グラフ化部１２は、以下に詳しく述べるように、前記細線化パターンから、頂点、辺を抽出し、頂点と辺の隣接、接続関係を求めることにより、当該細線化パターン（すなわち線図）をグラフで表現する。
【００６９】
点接触・続き線候補判定部１３、辺接触判定部１４は、当該グラフの辺から、それぞれ、点接触の候補の辺、続き線の候補の辺、辺接触の候補の辺を判定する。候補文字ラティス作成部１５は、当該グラフを辺の部分集合に分割し、それぞれのルールに従って候補文字ラティスに登録する。そして候補文字ラティス作成部１５は、認識文字候補のパターンを生成可能なノード間をリンクで結び、ノード間に設定された辺の部分集合から認識文字候補のパターンを生成する。
【００７０】
更に、候補文字ラティス生成部１５は、このようにして既存の技術を利用して生成した当該認識文字候補のパターンに対し実際に文字認識を実行する。そして候補文字ラティス生成部１５は、文字認識結果の相違度からリンクの重みを決定する。以上によって生成された候補文字ラティスに対し、最短パス探索部１７が、動的計画法やダイクストラ法などのよく知られた方法によって最短パスを求めることで、最終的な文字認識結果を得る。
【００７１】
次に上記グラフ化部１２の処理につき、詳細に説明する。
【００７２】
グラフ化部１２は、細線化部１１で得られた、読取画像が細線化された細線化パターン（すなわち線図）を、既存の手法を使ってグラフで表現する。
【００７３】
図１０はグラフ化部１２の内部構成を示す。図１１はグラフ化部１２による処理のフローチャートを示す。
【００７４】
図１０に示す如く、グラフ化部１２は頂点抽出部２２，辺抽出部２３，２次の頂点追加部２１及び頂点隣接行列計算部２５を含む。
【００７５】
上記の如くスキャナ等により読み取られた認識対象の文字列の画像（すなわち読取画像）のパターンが上記細線化部１１で細線化され、細線化パターンが得られる（図１１中ステップＳ３１）。頂点抽出部２２は、当該細線化パターンの各画素の８近傍領域をチェックし、あらかじめ各次数の頂点抽出用に用意してある３×３サイズのマスクパターン（図１３参照）と一致しているか否かを調べる（ステップＳ３２）。一致している場合はその画素をそのマスクパターンの示す次数の頂点として記録する（ステップＳ３３）。ここで頂点の次数とは、頂点に接続する辺の数を意味する。このように抽出した頂点の位置、座標は頂点情報ファイルに保存する。
【００７６】
辺抽出部２３は、これら各頂点に対し、カウンタを用意し、これを０で初期化しておく。まず、そのカウンタの値が辺の次数より小さい任意の頂点を一つ選択し、その頂点のカウンタを１インクリメントする（ステップＳ３４）。その頂点を開始頂点とし、そこから、別の頂点に到達するまで細線化パターン上の黒画素を追跡していく（ステップＳ３５）。それを終了頂点と呼ぶ。終了頂点のカウンタを１インクリメントする（ステップＳ３６）。
【００７７】
追跡した黒画素の座標、開始頂点の番号、終了頂点の番号が辺情報として保存する（ステップＳ３７）。全ての頂点のカウンタがその次数に等しくなる（ステップＳ３８のＹｅｓ）まで、このような辺の抽出を続行する。
【００７８】
細線化パターン上で、ある頂点からスタートして別の頂点に到達するまで黒画素を追跡することで辺を求める。辺の番号、頂点間の黒画素の位置座標の軌跡、辺に接続する頂点番号を辺情報ファイルに保存しておく。
【００７９】
更に、２次の頂点追加部２４は、全頂点のペアをチェックし、頂点間を結ぶ辺の数が複数の場合（ステップＳ３９のＹｅｓ）は、最も短い辺以外の辺に、２次の頂点を追加する（ステップＳ４０）。その結果新たに辺が生成されるため、頂点情報ファイル、辺の情報ファイルを書き換える（ステップＳ４１）。
【００８０】
頂点隣接行列計算部２５は、このようにして求められた辺情報から頂点隣接行列を計算する。ここで頂点隣接行列とは、頂点間が辺で結ばれている場合は１、結ばれていない場合は０をその要素の値とする行列である。
【００８１】
図１２は、図９，図１０に示す細線化部１１及びグラフ化部１２の各構成部２２乃至２５が出力するデータを概念的に示す。
【００８２】
図１２（ａ）は、スキャナによって読み取られた読取画像の例を示す。同図（ｂ）は細線化部１１で細線化された細線化パターン（すなわち線図）の例を示す。同図（ｃ）は頂点抽出部２２により頂点ｖ１，ｖ２が抽出された様子を示す。同図（ｄ）は辺抽出部２３により辺ｅ１，ｅ２，ｅ３が抽出された様子を示す。同図（ｅ）は２次の頂点追加部２４により２次の頂点ｅ４，ｅ５及びこれに伴う２次の辺ｖ３，ｖ４が追加された様子を示す。同図（ｆ）は頂点隣接行列計算部２５で得られた頂点隣接行列の例を示す。
【００８３】
また図１３は上記マスクパターンのうち、次数１と３の頂点を抽出するためのマスクパターンの一部を例として示す。同図中、１は黒画素、０は白画素を、夫々表す。
【００８４】
図１３（ａ）は次数１の頂点抽出用マスクパターンの例を示す。同図（ｂ）は次数３の頂点抽出用マスクパターンの例を示す。
【００８５】
図１４は最終的に得られた辺情報ファイル及び頂点情報ファイルのそれぞれの例を示す。同図（ａ）は頂点情報ファイルの例を示し、同図（ｂ）は辺情報ファイルの例を示す。
【００８６】
次に図９に示す辺接触候補判定部１４の辺接触候補判定処理につき、図１５を参照しながら詳細に説明する。図１５（ａ）は、上記した図１２（ａ），（ｂ），（ｃ）と同様の図である。
【００８７】
上記接触パターンにおける、隣接する文字の文字線の辺接触の候補を次のように決定する。
【００８８】
（ｉ）全てのグラフの辺をチェックし、条件に合わない辺を除くことで候補の絞り込みを行う。辺接触の場合、例えば対応するグラフの辺は次のような条件を満たすため、それ以外の辺を辺接触の候補から除く。
（条件１）当該辺に接続する各頂点の次数が３以上(Ｔ字、十字)のもの。
（条件２）当該辺の傾きが閾値以上（垂直・斜め）、例えば、幅に対する高さの１以上のもの。すなわち当該辺が、当該文字列の延在方向に対し、略垂直なもの。
【００８９】
図１５（ａ）の例の場合、これら条件１，条件２に合致する辺はｅ１のみである。したがって辺ｅ１が辺接触の候補として得られる。すなわち、当該辺ｅ１は、頂点ｖ１，ｖ２を有し、頂点ｖ１、ｖ２の各々はＴ字の接触を有するためその次数は３であり、条件１を満たす。また辺ｅ１は略垂直に延在するため、幅に対する高さの比が１以上となり、条件２も満たす。他の辺ｅ２乃至ｅ５はこれらの条件を満たさない。例えば図１５（ａ）中、辺ｅ２は、その頂点ｖ２の次数が２であるため、条件１を満たさない。
【００９０】
（ｉｉ）更に、当該グラフの各辺に対し、頂点隣接行列を使って当該辺接触の候補の辺とそれに接続する頂点とを複製し、隣接する辺を適切に分けることで、グラフが２つに分離するか否かを判定する。
【００９１】
図１５（ｂ）は、上記辺接触の候補の辺ｅ1と、それに接続する頂点ｖ1，ｖ2とを複製した様子を示す。このような辺と頂点の複製は具体的には以下の通りに行う。
【００９２】
図１５（ｂ）の例では、同図の中央に示す如く、グラフの頂点隣接行列において、複製対象である辺ｅ１に接続する頂点ｖ１，ｖ２に対応する行１，２及び列１，２の隣に、それぞれ新たな行１’、２’及び列１’、２’を挿入する。
【００９３】
次に、このようにして複製した頂点ｖ１’、ｖ２’に接続している、複製した辺以外の辺の、もう一方の頂点のｘ座標（すなわち当該文字列が延在する方向に沿う座標軸上の座標）を相互に比較し、それらの辺を複製後のいずれかの頂点に接続するよう決定する。図１５（ｂ）の例では、辺ｅ１に接続する頂点ｖ１には辺ｅ２とｅ３が接続している。この場合、辺ｅ２とｅ３のもう一方の頂点であるｖ３とｖ４のｘ座標をそれぞれｘ３，ｘ４とし、ｖ１のｘ座標をｘ１としたとき、ｘ３＜ｘ１であるためｅ２はｖ１´との接続を切り左方の複製辺ｅ１にのみ隣接させ、ｘ４＞ｘ１であるためｅ４はｖ1との接続を切り、右方の複製辺にｅ１´のみに隣接させる。即ち、頂点隣接行列においてｖ４、ｖ１´間の行列要素を１、ｖ４、ｖ１間の行列要素を０、ｖ３、ｖ１間の行列要素を１、ｖ３、ｖ１´間の行列要素を０とする。対象の辺ｅ１及び当該辺ｅ１に接続する頂点ｖ１，ｖ２以外の辺及び頂点同士の隣接関係はそのままで保持する。このようにして対象の辺ｅ１を複製して新たな辺ｅ１’を生成する際の、新たな頂点隣接行列の例を図１５（ｂ）の中央に示す。
【００９４】
次にこのようにして得られた頂点隣接行列の行及び列を適切に入れ替えた場合、行列がブロック対角となるか否かを判定する。図１５（ｂ）の右側に、頂点隣接行列の行及び列を適切に入れ替えた結果当該行列がブロック対角となった様子を示す。このように頂点隣接行列がブロック対角となった場合には、上記辺の複製によってグラフが２つのサブグラフｇ１，ｇ２に分離するとみなす。それぞれのブロックに対応する頂点が、それぞれの部分グラフの持つ頂点に対応する。
【００９５】
このようにして、図１５（ｂ）の左側に示す如く、図１５（ａ）の中央に示されるグラフが、２つのサブグラフｇ１，ｇ２に分離される。そして、辺接触の候補の辺ｅ１が複製され、これら２つのサブグラフｇ１，ｇ２の各々に属する文字線として登録され、含められる。すなわち当該辺接触の候補の辺ｅ１が２重登録される（すなわち図６のステップＳ４）。
【００９６】
次に図９に示される点接触・続き線候補判定部１３の処理につき図１６とともに詳述する。
【００９７】
以下の手順で続き線の候補を決定し、パターン（すなわち線図）を分離する。
（ｉ）上述の方法で、細線化された読取画像の細線化パターンをグラフ化し、上記同様の頂点隣接行列を求める。その頂点隣接行列を使って、グラフ理論の手法により、当該頂点隣接行列から、辺の切断集合基底行列を求める。ここで辺の切断集合基底行列とは、その各行が切断集合を表し、当該切断集合の成分が１となる番号に対応する辺を要素としてもつ行列である。ここで切断集合とは、当該切断集合の要素の辺を当該グラフから除くと、当該グラフが２つに分離するものをいう。図１６（ａ）の右側に示す頂点隣接行列の例の場合、図１６（ｂ）の右側に示す切断基底集合行列が得られる。例えば当該切断基底集合行列に含まれる切断集合番号１の切断集合基底行列は、その要素数が１であり、対応する要素として辺番号１の辺ｅ１を要素として持つ。この切断集合は、その要素である当該辺ｅ１を除くことにより、図１６（ｂ）の左側に示すように、図１６（ａ）の中央に示される元のグラフを２つの部分グラフに分ける切断集合である。同様に切断集合番号３の当該切断集合基底行列は、その要素数が２であり、対応する要素として辺番号２，４の辺e２，ｅ４を要素として持つ。この切断集合は、その要素である当該辺e２，ｅ４を除くことにより、図１６（ａ）の中央に示される元のグラフを、辺ｅ３の部分グラフと、辺ｅ１，ｅ５，ｅ６，ｅ７の部分グラフとに分ける切断集合である。
【００９８】
ここで求めたい続き線の候補はこれら切断集合に含まれる。
（ｉｉ）続き線の候補の辺を求めるため、上記各切断集合基底に対し、次のようなルールで候補の絞込みを行なう。まず、点接触の候補の辺を求める。
（条件１）要素数が１の切断集合に属する辺。
（条件２）当該辺の傾きが閾値以下（水平）、例えば、辺の幅に対する高さの比が１以下のもの。すなわち当該文字列に沿う方向に略平行な辺。
【００９９】
このようにして絞り込まれた点接触の候補の辺に対し、更に以下のルールを満たす辺を続き線の候補の辺として得る。
（条件３）当該辺の重心のｙ座標（すなわち当該文字列が延在する方向に直交する座標軸上の座標）が、パターン（すなわち線図全体、以下同様）の高さの閾値以下の位置にあるもの、例えば、当該辺の重心がパターンの高さの１／３以下のもの。なおこの場合、座標の原点は左上に設けており、上記閾値以下、あるいは１／３以下とは、閾値より上側、あるいはパターンの上側の１／３以内に位置することを意味する。
（条件４）当該辺の長さが閾値以上であるもの、例えば、当該辺の長さがパターンの高さの１／２以上のもの。
【０１００】
図１６（ａ）の例では、切断集合番号１の切断集合基底行列のみが候補として残り、対応する辺ｅ１が続き線の候補の辺と判定される。すなわち、当該切断集合基底行列は上記の如くその要素数が１である（条件１）。また、図１６（ａ）の中央のグラフから明らかなように、当該辺ｅ１は略水平方向に延在しており、辺の幅に対する高さの比が１以下である（条件２）。また同グラフから明らかなように、当該辺ｅ１はパターン全体の上方に位置しており、その重心のｙ座標はパターンの上側の１／３以内である（条件３）。また当該辺ｅ１の長さは、パターンの高さの１／２以上である（条件４）。したがって全ての条件が満たされる。また図１６（ｂ）右側の当該切断集合基底行列のうち、その要素数が１であるのは上記切断集合番号が１の、辺ｅ１に係るもののみである。
【０１０１】
次に、図９に示される候補文字ラティス作成部１５の処理につき、詳述する。
【０１０２】
前述の方法で全ての辺接触の候補の辺、点接触の候補の辺及び続き線の候補の辺を求めた後、候補文字ラティス作成部１５は、以下のように候補文字ラティスを作成する。
（ｉ）全ての辺接触の候補の辺、点接触の候補の辺及び続き線の候補の辺を、各々ひとつの辺よりなる部分集合とし、それぞれの外接矩形のx座標の昇順に並べる。ここでは、それらが計n個有ったとする。
（ｉｉ）前述のグラフを、図１７（ｅ）に示す如く、上記辺接触の候補の辺、点接触の候補の辺及び続き線の候補の辺と、それらに挟まれた部分、即ち、計2n+1個の辺の部分集合に分割する。
（ｉｉｉ）このようにして得られた2n+1個の辺の部分集合を、順に、隣り合うノード間のリンクとして登録する。ただし、辺の部分集合が辺接触の候補の辺に対応する場合は、次の隣り合うノード間のリンクとして、同じ辺の集合を２重登録する。すなわち当該辺に対応するリンクとして、直列的に接続する２本のリンクを設ける。辺の部分集合が、続き線の候補の辺に対応する場合は、それが対応するノード間に、そのリンクを迂回するようなリンクを設け、辺の集合としてφ（空集合）を対応させる。すなわち当該辺のリンクに並列的に接続するＮＵＬＬ画像にリンクを設ける。
（ｉｖ）開始ノードをs(s>0, s<n+1), 終了ノードをt(t>s, t<n+1)として開始ノードと終了ノード間との間をリンクで結び、それらのノード間に存在する辺の集合を合体させた辺の集合を各リンクに対応させる。ただし、辺の集合のサイズが一定条件を満たさないものについてはリンクを生成しない。すなわち、辺の集合の外接矩形の高さに対する幅の比が閾値以上となる場合には、当該辺の集合に対しリンクを生成しない。
（ｖ）各々の辺の集合から、パターンを復元する。例えば、辺情報から細線化パターンを作成し、この細線化パターンを、推定される文字幅の半分だけ膨張させる等の処理により、パターン（すなわち上記読取画像の状態のパターン）を復元する。
（ｖｉ）このようにして復元された全てのパターンに対し、既存の手法で文字認識を実行し、得られた認識文字種（すなわち認識結果の文字）とそれらの認識文字種に対する相違度そのもの、或いは相違度によって定義される認識コストを、対応するノード間のリンクの重みとして設定する。
【０１０３】
図１７（ａ）はスキャナで読み込まれた認識対象の原パターンを示す。同図（ｂ）は当該原パターンから得られたグラフを示す。同図（ｃ）、（ｄ）は、それぞれ、上記の如くに求められた続き線の候補の辺ｅ５、辺接触の候補の辺ｅ１１により、グラフが分割された様子を示す。同図（ｅ）は、全グラフが、辺の部分集合へ分割された様子を示す。同図（ｆ）は、上記の如くに作成された候補文字ラティスを示す。候補文字ラティス、頂点情報、辺情報は、実際には図１８に例として示される如くの構造体の形態で格納される。
【０１０４】
次に図９に示される最短パス探索部１７の処理について述べる。
【０１０５】
このようにして作成された候補文字ラティスから、動的計画法、ダイクストラ法などの一般的手法によって、最短距離を持つパスを探索する。その結果、最終的な文字の認識結果を得る。図１７の例の場合、最短パスを探索した結果、最短パスは図１７（ｆ）の候補文字ラティス上で、
ノード１→ノード２→ノード５→ノード７
のパスが得られる。ここでノードは上記の如く候補文字ラティスにおいて黒丸で示され、その番号は左から順に１，２，．．．と振られる。また図１９は、対応する読取画像（同図（ａ））と、前記最短パスに対応する認識結果の文字コード（すなわち数字「０３９」、同図（ｂ））とを示す。
【０１０６】
図２０は上述の実施例における文字認識装置１０をコンピュータで実現する場合について説明するための、コンピュータの構成例を示すブロック図である。
【０１０７】
図２０に示すごとく、同コンピュータ５００は、与えられたプログラムを構成する命令を実行することによって様々な動作を実行するためのＣＰＵ５０１と、キーボード、マウス等よりなりユーザが操作内容又はデータを入力するための操作部５０２とを有する。また同コンピュータ５００は、ユーザにＣＰＵ５０１による処理経過、処理結果等を表示するＣＲＴ、液晶表示器等よりなる表示部５０３を有する。また同コンピュータ５００は、ＲＯＭ、ＲＡＭ等よりなりＣＰＵ５０４が実行するプログラム、データ等を記憶したり作業領域として使用されるメモリ５０４を有する。また同コンピュータ５００は，プログラム、データ等を格納するハードディスク装置５０５を有する。また同コンピュータ５００は、ＣＤ−ＲＯＭ５０７を媒介として外部からプログラムをロードしたりデータをロードするためのＣＤ−ＲＯＭドライブ５０６を有する。また同コンピュータ５００は、インターネット、ＬＡＮ等の通信網５０９を介して外部サーバからプログラムをダウンロード等するためのモデム５０８を有する。
【０１０８】
同コンピュータ５００はＣＤ−ＲＯＭ５０７を媒介として、あるいは通信ネットワーク５０９を媒介として、上述の文字認識装置１０が実行する各処理をＣＰＵ５０１に実行させるための命令よりなるプログラムをロードあるいはダウンロードする。そしてこれをハードディスク装置５０５にインストールし、適宜メモリ５０４にロードしてＣＰＵ５０１が実行する。その結果、同コンピュータ５００により文字認識装置１０が実現される。
【０１０９】
以上の実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
文字認識プログラムであって、
コンピュータを、
文字列の記入されている帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割手段と、
前記分割手段により分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得手段と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択手段として機能させるためのプログラムであって、
前記候補文字列取得手段は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の手段と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の手段とのうちの少なくとも一の手段を有する構成とされてなるプログラム。
（付記２）
前記候補文字列取得手段における前記第１の手段は、隣接する文字間の接触に係る文字線につき、当該接触に係る文字線が前記隣接する文字のうちの一の文字に属する場合と、他の文字に属する場合と、前記一の文字及び他の文字の双方に属する場合とを夫々含む候補の文字列を、前記複数の候補の文字列に含める構成とされてなる付記１に記載のプログラム。
（付記３）
前記候補文字列取得手段は、前記線図を複数の部分に分割した各々の部分を、隣り合うノード間のリンクに対応させ、任意のノード間に含まれる部分パターンを統合したパターンが一文字となる場合、対応するノード間にリンクを生成して前記統合パターンを対応させ、当該リンクを相互に接続することで、前記複数の候補の文字列の各々に対応するパスを生成するパス生成手段を有し、
前記文字列選択手段は、前記パスを構成する前記リンクの各々につき、対応する前記線図の部分の文字認識に要される認識コストをその重みとして設定する文字認識コスト設定手段と、
前記各リンクの重みをパス毎に合計して得られた認識コスト合計が最小となる一のパスを、前記一の文字列に係るパスとして選択するパス選択手段とを有し
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線に対応するリンクとして直列的に接続された２個のリンクを設け、一のリンクは当該接触に係る文字線を有し、他のリンクは一のリンクと同じ当該接触に係る文字線を有する構成とされ、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線に対応するリンクとして当該接触に係る文字線に並列的に接続された２個のリンクを設け、且つ、当該２個のリンクのうち、一のリンクは当該接触に係る文字線を有し、他のリンクは迂回のためのリンクで空白パターンを有するとされてなる
付記１又は２に記載のプログラム。
（付記４）
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線が、当該文字列が延在する方向に略直交する方向に沿って延在する場合に適用され、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線が、当該文字列が延在する方向と略同一の方向に沿って延在する場合に適用されてなる
付記１乃至３のうちの何れか一項に記載のプログラム。
（付記５）
文字認識装置であって、
文字列が記入されている帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割手段と、
前記分割手段により分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得手段と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択手段とを有し、
前記候補文字列取得手段は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の手段と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の手段とのうちの少なくとも一の手段を有する構成とされてなる文字認識装置。
（付記６）
前記候補文字列取得手段における前記第１の手段は、隣接する文字間の接触に係る文字線につき、当該接触に係る文字線が前記隣接する文字のうちの一の文字に属する場合と、他の文字に属する場合と、前記一の文字及び他の文字の双方に属する場合とを夫々含む候補の文字列を、前記複数の候補の文字列に含める構成とされてなる付記５に記載の文字認識装置。
（付記７）
前記候補文字列取得手段は、前記線図の複数の部分にリンクを対応させ、当該リンクを相互に接続することで、前記複数の候補の文字列の各々に対応するパスを生成するパス生成手段を有し、
前記文字列選択手段は、前記パスを構成する前記リンクの各々につき、対応する前記線図の部分の文字認識に要される認識コストをその重みとして設定する文字認識コスト設定手段と、
前記各リンクの重みをパス毎に合計して得られた認識コスト合計が最小となる一のパスを、前記一の文字列に係るパスとして選択するパス選択手段とを有し
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線に対応するリンクとして直列的に接続された２個のリンクを設ける構成とされ、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線に対応するリンクとして当該接触に係る文字線に並列的に接続された２個のリンクを設け、且つ、当該２個のリンクのうち、一のリンクは当該接触に係る文字線を有し、他のリンクは迂回のためのリンクとされてなる
付記５または６に記載の文字認識装置。
（付記８）
前記候補文字列取得手段における前記第１の手段は、前記接触に係る文字線が、当該文字列が延在する方向に略直交する方向に沿って延在する場合に適用され、
前記候補文字列取得手段における前記第２の手段は、前記接触に係る文字線が、当該文字列が延在する方向と略同一の方向に沿って延在する場合に適用されてなる
付記５乃至７のうちの何れかに記載の文字認識装置。
（付記９）
文字認識方法であって、
文字列が記入された帳票から得られた線図に基づいて、当該線図を複数の部分に分割する分割段階と、
前記分割段階で分割された前記線図の複数の部分を組み合わせることにより、当該線図に係る前記文字列に対する複数の候補の文字列を得る候補文字列取得段階と、
前記複数の候補の文字列の中から一の文字列を選択する文字列選択段階とを有し、
前記候補文字列取得段階は、隣接する文字間の接触に係る文字線を複製した上で当該複製に係る文字線を候補の文字列の要素に含める第１の段階と、隣接する文字間の接触に係る文字線を除去した候補の文字列と当該文字線を含めた候補の文字列とを前記複数の候補の文字列に含める第２の段階とのうちの少なくとも一の段階を有する構成とされてなる文字認識方法。
（付記１０）
前記候補文字列取得段階における前記第１の段階では、隣接する文字間の接触に係る文字線につき、当該接触に係る文字線が前記隣接する文字のうちの一の文字に属する場合と、他の文字に属する場合と、前記一の文字及び他の文字の双方に属する場合とを夫々含む候補の文字列を、前記複数の候補の文字列に含める構成とされてなる付記９に記載の文字認識方法。
（付記１１）
前記候補文字列取得段階は、前記線図の複数の部分にリンクを対応させ、当該リンクを相互に接続することで、前記複数の候補の文字列の各々に対応するパスを生成するパス生成段階を有し、
前記文字列選択段階は、前記パスを構成する前記リンクの各々につき、対応する前記線図の部分の文字認識に要される認識コストをその重みとして設定する文字認識コスト設定段階と、
前記各リンクの重みをパス毎に合計して得られた認識コスト合計が最小となる一のパスを、前記一の文字列に係るパスとして選択するパス選択段階とを有し
前記候補文字列取得段階における前記第１の段階では、前記接触に係る文字線に対応するリンクとして直列的に接続された２個のリンクを設ける構成とされ、
前記候補文字列取得段階における前記第２の段階では、前記接触に係る文字線に対応するリンクとして当該接触に係る文字線に並列的に接続された２個のリンクを設け、且つ、当該２個のリンクのうち、一のリンクは当該接触に係る文字線を有し、他のリンクは迂回のためのリンクとされてなる
付記９または１０に記載の文字認識方法。
（付記１２）
前記候補文字列取得段階における前記第１の段階は、前記接触に係る文字線が、当該文字列が延在する方向に略直交する方向に沿って延在する場合に適用され、
前記候補文字列取得段階における前記第２の段階は、前記接触に係る文字線が、当該文字列が延在する方向と略同一の方向に沿って延在する場合に適用されてなる
付記９乃至１１のうちの何れかに記載の文字認識方法。
【図面の簡単な説明】
【０１１０】
【図１】手書き数字列の一例を示す図である。
【図２】候補文字ラティスを説明するための図である。
【図３】相互に接触した手書き数字の文字認識について説明するための図（その１）である。
【図４】相互に接触した手書き数字の文字認識について説明するための図（その２）である。
【図５】実施例の作用効果を説明するための図（その１）である。
【図６】辺接触候補処理の動作フローチャートである。
【図７】実施例の作用効果を説明するための図（その２）である。
【図８】続き線候補処理の動作フローチャートである。
【図９】文字認識装置の構成を説明するためのブロック図である。
【図１０】図９に示されるグラフ化部の構成を説明するためのブロック図である。
【図１１】グラフ化部の処理フローチャートである。
【図１２】グラフ化部の処理を説明するための図である。
【図１３】頂点抽出用マスクパターンを説明するための図である。
【図１４】頂点情報ファイル及び辺情報ファイルの各々の一例を説明するための図である。
【図１５】辺接触の候補の文字線を得る処理について説明するための図である。
【図１６】続き線の候補の文字線を得る処理について説明するための図である。
【図１７】候補文字ラティスの作成について説明するための図である。
【図１８】辺、頂点、ラティスを表す構造体の例について説明するための図である。
【図１９】図１７の例に対する最短パス探索結果について説明するための図である。
【図２０】コンピュータのハードウェアブロック図である。
【符号の説明】
【０１１１】
１０  文字認識装置
１６  候補文字ラティス生成部
１３  点接触・続き線候補判定部
１４  線接触候補判定部
１５  候補文字ラティス作成部
１７  最短パス探索部
【図１】
2009199102.tif 000003
【図２】
2009199102.tif 000004
【図３】
2009199102.tif 000005
【図４】
2009199102.tif 000006
【図５】
2009199102.tif 000007
【図６】
2009199102.tif 000008
【図７】
2009199102.tif 000009
【図８】
2009199102.tif 000010
【図９】
2009199102.tif 000011
【図１０】
2009199102.tif 000012
【図１１】
2009199102.tif 000013
【図１２】
2009199102.tif 000014
【図１３】
2009199102.tif 000015
【図１４】
2009199102.tif 000016
【図１５】
2009199102.tif 000017
【図１６】
2009199102.tif 000018
【図１７】
2009199102.tif 000019
【図１８】
2009199102.tif 000020
【図１９】
2009199102.tif 000021
【図２０】
2009199102.tif 000022