(57)【要約】【課題】高い精度で文字認識を行うことが可能な文字認識装置および文字認識方法並びに文字認識プログラムを提供する。【解決手段】グレースケール画像からそれぞれ異なる閾値に対応する複数の二値画像を生成する二値化部と、複数の二値画像からそれぞれ抽出した連結成分についての包含関係を示す成分ツリーを生成する探索部と、各連結成分について、当該連結成分からの距離が所定値以下であって、かつ、成分ツリーによって包含関係を持たない旨が示された連結成分を検出し、当該連結成分と検出した連結成分との並び順をそれぞれ設定することにより、各連結成分に対応する候補文字の並び順を網羅的に示す認識ラティスを生成する生成部と、認識ラティスによって接続が示された連結成分ごとに文字認識を行う認識部と、認識部で得られた各連結成分についての認識結果に基づいて、各候補文字列が入力画像に含まれる文字列である可能性の高さをそれぞれ評価する評価部とを備える。【選択図】      図１
2013175084.tif 000002
【特許請求の範囲】
【請求項１】
グレースケールで表現された入力画像を複数の閾値を用いてそれぞれ二値化することにより、複数の二値画像を生成する二値化部と、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出し、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成する探索部と、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成する生成部と、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を得る認識部と、
前記認識部で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する評価部と
を備えたことを特徴とする文字認識装置。
【請求項２】
請求項１に記載の文字認識装置において、
前記生成部は、
前記認識ラティスの生成に先立って、前記成分ツリーにおいて親子関係を有することが示されている連結成分の組のうち、形状が互いに類似している連結成分の組を検出し、検出した連結成分の組を一つの連結成分に縮約する縮約部を有する
ことを特徴とする文字認識装置。
【請求項３】
請求項１又は請求項２に記載の文字認識装置において、
前記生成部は、
前記認識ラティスによって接続が設定された各連結成分と当該連結成分を含む所定の大きさの領域内に含まれる別の連結成分とを結合することで新たな連結成分を生成し、生成した新たな連結成分を前記認識ラティスに追加することにより、前記認識ラティスを拡張する拡張部とを有する
ことを特徴とする文字認識装置。
【請求項４】
請求項１ないし請求項３のいずれか一項に記載の文字認識装置において、
前記生成部は、
前記成分ツリーに含まれる複数の連結成分の中から、文字を表す可能性がある連結成分を検出し、検出した連結成分を前記認識ラティスにおいて接続を設定する対象として選択する選択部を有する
ことを特徴とする文字認識装置。
【請求項５】
コンピュータが、
グレースケールで表現された入力画像を複数の閾値を用いてそれぞれ二値化することにより、複数の二値画像を生成し、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、
前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する
ことを特徴とする文字認識方法。
【請求項６】
グレースケールで表現された入力画像を複数の閾値を用いて二値化することにより、複数の二値画像を生成し、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、
前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する
処理をコンピュータに実行させることを特徴とする文字認識プログラム。  
【発明の詳細な説明】
【技術分野】
【０００１】
本件開示は、カラー画像を含む入力画像に含まれる文字列を認識する文字認識装置および文字認識方法並びに文字認識プログラムに関する。
【背景技術】
【０００２】
テロップを含むテレビジョン放送の映像をキャプチャして得られる静止画像や情景画像などのカラー画像は、様々な物体の像を含む多値画像を背景として多様な色で表現された文字を表す文字パターンの集合を含んでいる場合がある。このような画像に含まれる文字パターンの集合に対して文字認識を行うことにより、テキストを抽出する従来技術として、エッジ解析に基づく技法(特許文献１参照)とカラークラスタリングに基づく技法(特許文献２参照)とが提案されている。
【０００３】
特許文献１の技法は、入力画像から抽出したエッジの分布に基づいて、入力画像におけるテキストの範囲を特定し、特定した範囲を二値化することによって得た二値画像についての文字認識を行うことでテキスト情報を抽出する。
【０００４】
また、特許文献２の技法は、個々の画素の色を色空間にマッピングした結果についてクラスタリングを行うことで、入力画像に含まれる文字列の色に対応するクラスタを特定する。そして、各画素の色がこのクラスタに含まれるか否かを示す二値画像を生成し、この二値画像を対象とする文字認識を行うことによりテキスト情報を抽出する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４０７７０９４号
【特許文献２】特開２００９−１９９２７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところで、テロップなどで表された文字列の背景が自然画像である場合は、カメラの視野内に含まれる様々な物体の輪郭を表すエッジを含んでいる。このため、特許文献１の技法では、文字列の背景の画像が複雑な場合に、テキストが分布する領域と背景の領域とを明確に判別できない場合がある。
【０００７】
また、情景画像に含まれる各文字パターンの色は、照明の当たり方や影などの環境条件や画像圧縮処理を行った際の劣化などによる影響を受ける場合があるため、必ずしも一様ではない。また、テロップの文字列の色と同じ色が、背景の画像に含まれている場合もある。このため、特許文献２の技法では、文字パターンの一部を表す画像を、背景の一部として排除してしまったり、逆に、背景の一部を文字パターンの一部として含めてしまったりする場合がある。
【０００８】
このように、従来技術によっては、文字列が複雑な画像を背景として表された画像を対象とした場合に、高い精度で文字認識を行うことが難しかった。
【０００９】
本件開示は、高い精度で文字認識を行うことが可能な文字認識装置および文字認識方法並びに文字認識プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
一つの観点による文字認識装置は、グレースケールで表現された入力画像を複数の閾値を用いてそれぞれ二値化することにより、複数の二値画像を生成する二値化部と、前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出し、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成する探索部と、前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成する生成部と、前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を得る認識部と、前記認識部で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する評価部とを備える。
【００１１】
また、別の観点による文字認識方法は、コンピュータが、グレースケールで表現された入力画像を複数の閾値を用いて二値化することにより、複数の二値画像を生成し、前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する。
【００１２】
更に別の観点による文字認識プログラムは、グレースケールで表現された入力画像を複数の閾値を用いて二値化することにより、複数の二値画像を生成し、前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する処理をコンピュータに実行させる。  
【発明の効果】
【００１３】
本件開示の文字認識装置および文字認識方法並びに文字認識プログラムによれば、高い精度で文字認識を行うことが可能となる。
【図面の簡単な説明】
【００１４】
【図１】文字認識装置の一実施形態を示す図である。
【図２】二値画像の例を示す図である。
【図３】成分ツリーＴｒの例を示す図である。
【図４】認識ラティスＬｔの例を示す図である。
【図５】接続条件を説明する図である。
【図６】文字認識装置の別実施形態を示す図である。
【図７】成分テーブルの例を示す図である。
【図８】識別子画像の例を示す図である。
【図９】縮約された成分ツリーの例を示す図である。
【図１０】ラティステーブルの例を示す図である。
【図１１】縮約された成分ツリーＴｒから生成した認識ラティスＬｔの例を示す図である。
【図１２】入力画像と二値画像の別例を示す図である。
【図１３】文字認識装置の別実施形態を示す図である。
【図１４】結合条件を説明する図である。
【図１５】認識ラティスＬｔの拡張を説明する図である。
【図１６】文字認識装置のハードウェア構成例を示す図である。
【図１７】文字認識処理のフローチャートの一例を示す図である。
【図１８】成分ツリーを縮約する処理のフローチャートの一例を示す図である。
【図１９】ツリーノードの属性を判別する処理のフローチャートの一例を示す図である。
【図２０】代表ノードを判別する処理のフローチャートの一例を示す図（１）である。
【図２１】代表ノードを判別する処理のフローチャートの一例を示す図（２）である。
【図２２】認識ラティスの生成処理を説明する図である。
【図２３】認識ラティスを生成する処理のフローチャートの一例を示す図である。
【図２４】位置管理テーブルを作成する処理を説明する図である。
【図２５】リンクを設定する処理のフローチャートの一例を示す図である。
【図２６】認識ラティスを拡張する処理のフローチャートの一例を示す図である。
【図２７】拡張ノードを生成する処理のフローチャートの一例を示す図である。
【図２８】拡張された認識ラティスを表すラティステーブルの例を示す図である。
【図２９】パターン認識処理のフローチャートの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面に基づいて、本発明の実施形態について詳細に説明する。
図１は、文字認識装置の一実施形態を示している。図１に例示した文字認識装置１０は、グレースケールで表現された入力画像Ｐｉｎの入力を受ける。この入力画像Ｐｉｎは，例えば、グレースケール変換装置１が、カラー画像Ｐｃｔに対してグレースケール変換を行うことによって得られる明るさを複数の階調値で表した画像である。また、文字認識装置１０は、二値化部１１と、探索部１２と、生成部１４と、認識部１６と、評価部１７とを含んでいる。
【００１６】
二値化部１１は、入力画像を複数の閾値を用いて二値化することにより、ｍ枚の二値画像Ｐ１〜Ｐｍを生成する。例えば、入力画像Ｐｉｎに含まれる各画素の明るさが８ビットのデータを用いて２５６階調で表されている場合に、二値化部１１は、２５６枚の二値画像を生成してもよい。
【００１７】
図２は、二値画像の例を示している。なお、図２に示した要素のうち、図１に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。また、図２において、符号ＧＳは、グレースケールを示している。
【００１８】
図２において、符号Ｐ０，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６は、それぞれ異なる閾値ｔｈ０，ｔｈ１，ｔｈ２，ｔｈ３，ｔｈ４，ｔｈ５，ｔｈ６を用いて入力画像Ｐｉｎを二値化して得られた二値画像の例である。なお、これらの閾値ｔｈ０〜ｔｈ６は、例えば、グレースケールＧＳ上で、等間隔に設定することができる。図２の例では、閾値ｔｈ０は、最大の明るさを持つ白色に相当し、逆に、閾値ｔｈ６は、明るさが最小の黒色に相当している。また、閾値ｔｈ１，ｔｈ２，ｔｈ３，ｔｈ４，ｔｈ５のそれぞれは、順に、明るさが小さくなるように設定されている。
【００１９】
図１に例示した探索部１２は、二値化部１１で得られた二値画像Ｐ１〜Ｐｍからそれぞれ複数の黒画素が連結したパターンを連結成分として抽出する。探索部１２は、図２に例示した二値画像Ｐ０〜Ｐ６が入力された場合に、これらの二値画像Ｐ０〜Ｐ６のそれぞれから、図２に示すような連結成分を抽出する。
【００２０】
図２において、符号Ｃ０−１は、二値画像Ｐ０から抽出された連結成分を示す。なお、連結成分Ｃ０−１は、二値画像Ｐ０に含まれる全ての画素を含んでいる。また、図２において、符号Ｃ１−１，Ｃ１−２は、二値画像Ｐ１から抽出された２つの連結成分を示している。同様に、図２において、符号Ｃ２−１，Ｃ２−２，Ｃ２−３，Ｃ２−４は、二値画像Ｐ２から抽出された４つの連結成分を示している。また、図２において、符号Ｃ３−１，Ｃ３−２，Ｃ３−３，Ｃ３−４，Ｃ３−５，Ｃ３−６は、二値画像Ｐ３から抽出された６つの連結成分を示している。同様に、図２において、符号Ｃ４−１，Ｃ４−２，Ｃ４−３，Ｃ４−４，Ｃ４−５，Ｃ４−６は、二値画像Ｐ４から抽出された６つの連結成分を示している。そして、図２において、符号Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８，Ｃ５−９，Ｃ５−１０，Ｃ５−１１，Ｃ５−１２は、二値画像Ｐ５から抽出された１２個の連結成分を示している。一方、図２の例では、二値画像Ｐ６から抽出された連結成分は無い。
【００２１】
また、図１に例示した探索部１２は、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーＴｒを生成する。例えば、探索部１２は、図２に例示した各連結成分について包含関係を探索することにより、図３に示すような成分ツリーを生成する。
【００２２】
図３は、成分ツリーの例を示している。図３において、成分ツリーに含まれる各ノードを、成分ツリー内で一意のノード番号を付した丸で示した。以下の説明では、成分ツリーに含まれる各ノードをツリーノードと称する。
【００２３】
図３に示したツリーノード１は、図２に示した連結成分Ｃ０−１に対応する。また、図３に示したツリーノード２，３は、図２に示した連結成分Ｃ１−１，Ｃ１−２に対応する。同様に、図３に示したツリーノード４，５，６，７は、図２に示した連結成分Ｃ２−１，Ｃ２−２，Ｃ２−３，Ｃ２−４に対応する。また、図３に示したツリーノード８，９，１０，１１，１２，１３は、図２に示した連結成分Ｃ３−１，Ｃ３−２，Ｃ３−３，Ｃ３−４，Ｃ３−５，Ｃ３−６に対応する。同様に、図３に示したツリーノード１４，１５，１６，１７，１８，１９は、図２に示した連結成分Ｃ４−１，Ｃ４−２，Ｃ４−３，Ｃ４−４，Ｃ４−５，Ｃ４−６に対応する。また、図３に示したツリーノード２０，２１，２２，２３，２４，２５，２６，２７は、図２に示した連結成分Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８に対応する。同様に、図３に示したツリーノード２８，２９，３０，３１は、図２に示した連結成分Ｃ５−９，Ｃ５−１０，Ｃ５−１１，Ｃ５−１２に対応する。
【００２４】
図３において、成分ツリーに含まれる各ツリーノード１〜３１は、対応する連結成分が抽出された二値画像の生成に用いられた閾値を示す直線上に配置されている。例えば、二値画像Ｐ５から抽出された１２個の連結成分Ｃ５−１〜Ｃ５−１２に対応するツリーノード２０〜３１は、閾値ｔｈ５に対応する濃度値を示す破線上に配置されている。
【００２５】
図３に示した成分ツリーは、ツリーノード１をルートノードとする有向木である。この成分ツリーにおいて、各矢印で結ばれた２つのノードは、直接の包含関係を持つ親子である。例えば、ツリーノード１を始点とする矢印でツリーノード１と結ばれている２つのツリーノード２，３は、いずれも、ツリーノード１を親ノードとする子ノードである。なお、このような成分ツリーの生成手法については、例えば、Laurent Najman, Michel Couprie. Building the Component Tree in Quasi-Linear Time. IEEE Transactions on Image Processing, 2006: 3531~3539などを参照されたい。
【００２６】
図１に例示した生成部１４は、探索部１２によって生成された成分ツリーＴｒに含まれる各連結成分について、後述する接続条件を満たす別の連結成分を検出し、当該連結成分と検出した別の連結成分とを順に接続することにより、認識ラティスＬｔを生成する。例えば、生成部１４は、各連結成分に順次に注目し、入力画像Ｐｉｎにおける注目する連結成分からの距離が所定値以下である別の連結成分であって、かつ、成分ツリーＴｒによって包含関係を持たないことが示されている連結成分を検出する。そして、生成部１４は、注目する連結成分について別の連結成分を検出するごとに、注目する連結成分を始点とし、検出した連結成分を終点とする接続を設定することにより、注目する連結成分と検出した連結成分との並び順をそれぞれ設定する。上述した処理を各連結成分について実行することにより、生成部１４は、各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスＬｔを生成する。この認識ラティスは、各連結成分に対応する候補文字の並びを示す候補文字ラティスに相当する。生成部１４は、例えば、図３に示した成分ツリーＴｒに基づいて、図４に示すような認識ラティスＬｔを生成する。
【００２７】
図４は、認識ラティスＬｔの例を示している。図４の例は、連結成分Ｃ４−１，Ｃ４−２，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８に対応する各ノードについて生成部１４が設定した接続の一部を示している。なお、以下の説明において、認識ラティスＬｔに含まれる各ノードをラティスノードと称する。
【００２８】
ここで、図２に示した二値画像Ｐ０〜Ｐ６にそれぞれ含まれる各画素の位置は、入力画像Ｐｉｎに含まれる各画素の位置に相当する。したがって、生成部１４は、例えば、注目する連結成分の外接矩形の位置と他の連結成分の外接矩形の位置とを比べることにより、注目する連結成分との距離が所定の閾値よりも近い別の連結成分を検出することができる。なお、外接矩形とは、連結成分が外接する矩形である。
【００２９】
図５は、接続条件を説明する図である。なお、図５に示した要素のうち、図２に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。図５(Ａ)において、座標軸Ｘ，Ｙは、入力画像Ｐｉｎにおける各画素の位置の基準を示す。
【００３０】
なお、座標軸Ｘは、入力画像Ｐｉｎに含まれる文字列が並んでいる方向に基づいて設定することが望ましい。以下の説明では、図２に示した入力画像Ｐｉｎに対応する矩形の左上の頂点を原点とし、入力画像Ｐｉｎの左から右に向かうように座標軸Ｘを設定し、上から下に向かうように座標軸Ｙを設定した場合について説明する。
【００３１】
このような座標軸Ｘ，Ｙは、入力画像Ｐｉｎにおいて、文字列が並んでいる行方向が左右方向に相当する場合に好適である。もちろん、座標軸Ｘ，Ｙは、入力画像Ｐｉｎにおいて文字列が並んでいると想定される方向に合わせて如何様にも設定することができる。
【００３２】
また、図５において、符号Ｒｊは、ｊ番目のツリーノードに対応する連結成分の外接矩形を示し、符号Ｒｋは、ｋ番目のツリーノードに対応する連結成分の外接矩形を示す。
【００３３】
図５に示した外接矩形Ｒｊの４つの頂点のうち、最も原点に近い左上の頂点の座標を(Ｘｍｉｎｊ，Ｙｍｉｎｊ)とし、最も原点から遠い右下の頂点の座標を(Ｘｍａｘｊ，Ｙｍａｘｊ)とする。同様に、外接矩形Ｒｋの４つの頂点のうち、最も原点に近い左上の頂点の座標を(Ｘｍｉｎｋ，Ｙｍｉｎｋ)とし、最も原点から遠い右下の頂点の座標を(Ｘｍａｘｋ，Ｙｍａｘｋ)とする。
【００３４】
このような２つの外接矩形Ｒｊ，Ｒｋ間の距離は、例えば、外接矩形Ｒｊの右下の頂点から外接矩形Ｒｋの左上の頂点までの距離に基づいて評価することができる。したがって、図１に例示した生成部１４は、例えば、上述した座標値について、次の式(１)の関係が成立する場合に、外接矩形Ｒｊに対応する連結成分と外接矩形Ｒｋに対応する連結成分との距離は所定の閾値よりも近いと判断してもよい。
max(Xmink−Xmaxj，0)≦Th１  ＆  max(Ymink−Ymaxj，0)≦Th2    ・・・（１）
なお、式(１)において、閾値Ｔｈ１は、例えば、入力画像Ｐｉｎに含まれる文字列内の各文字の横幅に相当する値を設定することが望ましい。同様に、閾値Ｔｈ２は、例えば、入力画像Ｐｉｎに含まれる文字列内の各文字の高さに相当する値を設定することが望ましい。
【００３５】
また、生成部１４は、入力画像Ｐｉｎに含まれる文字列が並んでいる方向についての想定に基づいて、注目する連結成分を選択する順序や、注目する連結成分との接続を設定する連結成分の候補を制限してもよい。例えば、図２に例示した入力画像Ｐｉｎのように、認識対象の文字列が左から右に向かって配列されていることが想定される場合がある。この場合に、生成部１４は、成分ツリーＴｒに含まれる各連結成分から、対応する外接矩形の左上の頂点に対応するＸ座標が小さい順に注目する連結成分を選択することが望ましい。また、この場合に、生成部１４は、注目する連結成分に近い連結成分を検出する処理の対象を、注目する連結成分に対応する外接矩形の左上の頂点に対応するＸ座標よりもＸ座標が大きい方に配置された連結成分に限定してもよい。
【００３６】
図５(Ｂ)において、符号Ｑ１は、上述した接続条件を用いる場合に、図１に例示した生成部１４が、二値画像Ｐ４から抽出された連結成分Ｃ４−１について、近接する連結成分として検出する範囲を示している。また、符号Ｑ２は、上述した接続条件を用いる場合に、生成部１４が、二値画像Ｐ４から抽出された連結成分Ｃ４−２について、近接する連結成分として検出する範囲を示している。
【００３７】
図５(Ｂ)に示した範囲Ｑ１は、二値画像Ｐ４から抽出された連結成分Ｃ４−２，Ｃ４−３と、二値画像Ｐ５から抽出された連結成分Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８を含んでいる。
【００３８】
したがって、連結成分Ｃ４−１に注目した場合に、生成部１４は、これらの連結成分Ｃ４−２，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８を近接する連結成分として検出する。そして、これらの連結成分連結成分Ｃ４−２，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８それぞれについて、連結成分Ｃ４−１との包含関係を調べる。
【００３９】
図３に示した成分ツリーＴｒによって示されているように、連結成分Ｃ４−１は、連結成分Ｃ４−２，Ｃ４−３および連結成分Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８との間には包含関係を持たない。一方、連結成分Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４は、いずれも連結成分Ｃ４−１の子ノードであり、連結成分Ｃ４−１に直接的に包含されている。この場合に、生成部１４は、図４に示したように、連結成分Ｃ４−１に対応するラティスノードを始点とし、連結成分Ｃ４−２，Ｃ４−３，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８に対応するラティスノードに向かうリンクのみを設定する。
【００４０】
一方、図５(Ｂ)に示した範囲Ｑ２は、二値画像Ｐ４から抽出された連結成分Ｃ４−１、Ｃ４−３の一部および二値画像Ｐ５から抽出された連結成分Ｃ５−１の一部と、二値画像Ｐ５から抽出された連結成分Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６を含んでいる。
【００４１】
したがって、連結成分Ｃ４−２に注目した場合に、生成部１４は、これらの連結成分Ｃ４−１，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６を近接する連結成分として検出する。図３に示した成分ツリーＴｒを参照すれば、これらの連結成分Ｃ４−１，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６は、いずれも連結成分Ｃ４−２の子ノードではないことが分かる。この場合に、生成部１４は、図４に示したように、連結成分Ｃ４−２に対応するラティスノードを始点とし、上述した８つの連結成分Ｃ４−１，Ｃ４−３，Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６に対応するラティスノードに向かうリンクをそれぞれ設定する。
【００４２】
同様にして、生成部１４は、連結成分Ｃ５−１，Ｃ５−２，Ｃ５−３，Ｃ５−４，Ｃ５−５，Ｃ５−６，Ｃ５−７，Ｃ５−８について、式(１)に示した位置に関する条件と包含関係に関する条件を満たす連結成分との間の接続を設定していく。これにより、生成部１４は、図４に例示したように、互いに近接する連結成分であって、かつ、包含関係を持たない連結成分を網の目のように接続した認識ラティスＬｔを生成することができる。
【００４３】
このようにして得られた認識ラティスＬｔは、各二値画像から抽出された連結成分に対応する候補文字の並び順を網羅的に示している。したがって、この認識ラティスＬｔは、入力画像Ｐｉｎに含まれる文字列を表すパターンが複数の二値画像に跨って現れるような場合でも、極めて高い確度で、正解の文字列に対応する候補文字の並び順を含んでいる。
【００４４】
このようにして得られた認識ラティスＬｔによって接続が示された連結成分ごとに、図１に例示した認識部１６は、既存の文字認識技術を用いた文字認識を行う。この文字認識処理により、認識部１６は、認識処理の対象となった各連結成分について、類似する文字を示す候補文字と当該連結成分が候補文字を表す可能性の高さを示す確信度とを含む認識結果を得る。
【００４５】
評価部１７は、認識部１６で得られた各連結成分についての認識結果に基づいて、認識ラティスＬｔにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が入力画像Ｐｉｎに含まれる文字列である可能性の高さをそれぞれ評価する。評価部１７は、例えば、動的計画法(ＤＰ：Dynamic Programming)を用いて、認識ラティスＬｔによって示された各パスの評価値を算出してもよい。そして、評価部１７は、最高の評価値を得たパスに対応する候補文字列を、入力画像Ｐｉｎに含まれる文字列として出力する。
【００４６】
上述したように、図１に例示した本件開示の文字認識装置１０によれば、文字列を表すパターンが複数の二値画像に跨って現れるような場合でも、極めて高い確度で、正解の文字列に対応する候補文字の並び順を含む認識ラティスＬｔを生成することができる。そして、この認識ラティスＬｔを認識部１６及び評価部１７の処理に供することにより、高い確度で正解の文字列を取得することができる。
【００４７】
つまり、本件開示の文字認識装置１０によれば、複雑な画像を背景として複数色を用いて文字列を表したカラー画像に対して上述した認識処理を行うことにより、高い精度で文字列を抽出することが可能である。
【００４８】
ところで、図１に例示した文字認識装置１０によれば、入力画像Ｐｉｎから生成された各二値画像Ｐ１〜Ｐｍに含まれる連結成分の数によっては、生成部１４によって生成される認識ラティスＬｔで示される候補文字列の数が非常に多くなる可能性がある。
【００４９】
本件開示の文字認識装置１０による文字認識処理を高速化するためには、認識ラティスＬｔを生成するのに先立って、認識ラティスＬｔにラティスノードとして含ませる連結成分を絞りこむことが望ましい。
【００５０】
図６は、文字認識装置１０の別実施形態を示している。なお、図６に示した構成要素のうち、図１に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。図６に例示した文字認識装置１０は、認識ラティスＬｔに含めるラティスノード数を適切に絞り込むために好適な実施形態の一例である。
【００５１】
図６に例示した成分ツリーＴｒは、成分テーブル１３１と、識別子画像１３２２とを含んでいる。探索部１２は、各二値画像Ｐ１〜Ｐｍから連結成分を抽出するごとに、抽出した連結成分に関する情報を、成分テーブル１３１と識別子画像１３２とに登録することにより、成分ツリーＴｒを形成する。
【００５２】
図７は、成分テーブル１３１の一例を示している。この成分テーブル１３１は、図２に例示した二値画像Ｐ０〜Ｐ６から抽出された各連結成分に関連する情報を、この連結成分に対応する成分ツリーＴｒのツリーノードを示すノード番号に対応して保持している。
【００５３】
各ツリーノードに関連する情報は、上述したノード番号ｊと、当該ツリーノードに対応する連結成分の識別子と、この連結成分が抽出された二値画像に対応する閾値を示す濃度値とを含んでいる。また、ノード番号ｊのツリーノードに関連する情報は、対応する連結成分の外接矩形の左上の頂点の座標(Ｘｊｕ，Ｙｊｕ)および右下の頂点の座標(Ｘｊｄ，Ｙｊｄ)と、当該連結成分の面積を示す画素数Ｎｊおよび外周の長さを示す画像数Ｌｊとを含んでいる。更に、各ツリーノードに関連する情報は、当該ツリーノードを親ノードとする子ノードを示す情報として、子ノード番号及び子ノードの数を示す情報を含んでいる。また、各ツリーノードに関連する情報は、当該ツリーノードの親ノード番号とともに、当該ツリーノードの属性を示す情報として、Ｔフラグ、Ｉフラグ及びＤフラグを含んでいる。
【００５４】
ここで、各ツリーノードに対応するＴフラグは、当該ツリーノードに対応する連結成分が、文字を表す可能性を持つという属性を有しているか否かを示す。また、Ｉフラグは、当該ツリーノードに対応する連結成分が、親ノードに当たる連結成分の形状を引き継いでいるという属性を有しているか否かを示す。なお、Ｔフラグ及びＩフラグの設定及びＤフラグについては後述する。
【００５５】
なお、図７の例では、成分ツリーＴｒに含まれる各ツリーノードのうち、後述する成分ツリーＴｒの縮約処理の説明に用いるツリーノードに対応する情報を表示し、他のツリーノードに対応する情報の表示は省略している。
【００５６】
例えば、図７に示した成分テーブル１３１は、ノード番号１に対応して、図３に示した成分ツリーＴｒにおいて、このツリーノード１に対応する連結成分Ｃ０−１を示す識別子と、この連結成分Ｃ０−１の子ノードを示すノード番号２，３を含んでいる。
【００５７】
また、成分テーブル１３１は、ノード番号２に対応して、このツリーノード２に対応する連結成分Ｃ１−１を示す識別子と、この連結成分Ｃ１−１の子ノードを示すノード番号４，５，６，７及び子ノード数「４」と、親ノード番号１を含んでいる。
【００５８】
同様に、成分テーブル１３１は、ノード番号３に対応して、このツリーノード３に対応する連結成分Ｃ１−２を示す識別子と、この連結成分Ｃ１−２に子ノードがないことを示すノード番号「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１を含んでいる。
【００５９】
また、成分テーブル１３１は、ノード番号７に対応して、このツリーノード７に対応する連結成分Ｃ２−４を示す識別子と、この連結成分Ｃ２−４の子ノードを示すノード番号１３及び子ノード数「１」と、親ノード番号２を含んでいる。
【００６０】
更に、成分テーブル１３１は、ノード番号１３に対応して、このツリーノード１３に対応する連結成分Ｃ３−６を示す識別子と、この連結成分Ｃ３−６の子ノードを示すノード番号１８，１９及び子ノード数「２」と、親ノード番号７を含んでいる。
【００６１】
更に、成分テーブル１３１は、ノード番号１４に対応して、このツリーノード１４に対応する連結成分Ｃ４−１を示す識別子と、この連結成分Ｃ４−１の子ノードを示すノード番号２０，２１，２２，２３及び子ノード数「４」と、親ノード番号９を含んでいる。
【００６２】
また、成分テーブル１３１は、ノード番号１６に対応して、このツリーノード１６に対応する連結成分Ｃ４−３を示す識別子と、この連結成分Ｃ４−３の子ノードを示すノード番号２４，２５，２６，２７及び子ノード数「４」と、親ノード番号９を含んでいる。
【００６３】
更に、成分テーブル１３１は、ノード番号１７に対応して、このツリーノード１７に対応する連結成分Ｃ４−４を示す識別子と、この連結成分Ｃ４−４の子ノードを示すノード番号２８，２９及び子ノード数「２」と、親ノード番号１２を含んでいる。
【００６４】
また、成分テーブル１３１は、ノード番号１８に対応して、このツリーノード１８に対応する連結成分Ｃ４−５を示す識別子と、この連結成分Ｃ４−５の子ノードを示すノード番号３０及び子ノード数「１」と、親ノード番号１３を含んでいる。
【００６５】
同様に、成分テーブル１３１は、ノード番号１９に対応して、図３に示したツリーノード１９に対応する連結成分Ｃ４−６を示す識別子と、この連結成分Ｃ４−６の子ノードを示すノード番号３１及び子ノード数「１」と、親ノード番号１３を含んでいる。
【００６６】
一方、成分テーブル１３１は、ノード番号２１に対応して、このツリーノード２１に対応する連結成分Ｃ５−２を示す識別子と、この連結成分Ｃ５−２に子ノードがない旨の「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１４を含んでいる。
【００６７】
同様に、成分テーブル１３１は、ノード番号２２に対応して、このツリーノード２２に対応する連結成分Ｃ５−３を示す識別子と、この連結成分Ｃ５−３に子ノードがない旨の「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１４を含んでいる。
【００６８】
また、成分テーブル１３１は、ノード番号２６に対応して、このツリーノード２６に対応する連結成分Ｃ５−６を示す識別子と、この連結成分Ｃ５−６に子ノードがない旨の「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１６を含んでいる。
【００６９】
同様に、成分テーブル１３１は、ノード番号２７に対応して、このツリーノード２７に対応する連結成分Ｃ５−７を示す識別子と、この連結成分Ｃ５−７に子ノードがない旨の「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１６を含んでいる。
【００７０】
また、成分テーブル１３１は、ノード番号２８に対応して、このツリーノード２８に対応する連結成分Ｃ５−９を示す識別子と、この連結成分Ｃ５−９に子ノードがない旨の「ＮＵＬＬ」及び子ノード数「０」と、親ノード番号１７を含んでいる。
【００７１】
同様にして、探索部１２は、各二値画像から抽出した連結成分についての包含関係を探索する過程で得られた情報を、ノード番号に対応して成分テーブル１３１に格納させることにより、図３に示した成分ツリーＴｒに相当する成分テーブル１３１を生成する。
【００７２】
また、この過程で、探索部１２１は、各連結成分に含まれる画素のうち、成分テーブル１３１によって当該連結成分の子に当たることが示された連結成分に含まれない画素に対応して、当該連結成分の識別子を示す数値を保持する識別子画像１３２を生成する。
【００７３】
例えば、探索部１２は、入力画像Ｐｉｎと同等の大きさを持つ識別子画像１３２を用意しておき、小さい濃度値に対応する閾値で二値化された二値画像から順次に連結成分を抽出する。そして、探索部１２は、連結成分を抽出するごとに、当該連結成分に対応するツリーノードを示すノード番号を、この連結成分に含まれる各画素と同じアドレスを持つ識別子画像１３２の画素に格納していけばよい。つまり、大きな濃度値を持つ閾値に対応する二値画像から新たに抽出された連結成分に含まれる部分について、探索部１２は、この連結成分に対応するツリーノードを示すノード番号で識別子画像１３２の画素値を上書きしていけばよい。
【００７４】
図８は、識別子画像１３２の例を示している。図８(Ａ)は、図２に示した二値画像Ｐ０に相当する連結成分Ｃ０−１の抽出に応じて、図３に示したツリーノード１を示すノード番号１が識別子画像１３２の全画素に格納された状態を示している。また、図８(Ｂ)は、図２に示した二値画像Ｐ１に含まれる２つの連結成分Ｃ１−１，Ｃ１−２の抽出に応じて、これらに対応するツリーノード２，３を示すノード番号２，３が、識別子画像１３２に格納された状態を示している。
【００７５】
図８(Ｂ)において符号Ｃ１−１で示した部分は、連結成分Ｃ１−１の抽出に応じて、図３に示したツリーノード２を示すノード番号２によって、識別子画像１３２の画素値が書き換えられた部分を示す。同様に、図８において符号Ｃ１−２で示した部分は、連結成分Ｃ１−２の抽出に応じて、ツリーノード３を示すノード番号３によって、識別子画像１３２の画素値が書き換えられた部分を示す。なお、図８(Ｂ)に例示した識別子画像１３２において、符号Ｃ０−１で示した部分のように、上述した連結成分Ｃ１−１，Ｃ１−２の抽出に応じて画素値が書き換えられなかった部分の画素値は、上述したツリーノード１を示すノード番号１を維持している。
【００７６】
このような操作を各二値画像から抽出される連結成分について繰り返すことによって得られる識別子画像１３２によれば、成分ツリーＴｒで示される親子関係を順に辿ることにより、個々の連結成分を再生することができる。つまり、入力画像Ｐｉｎと同等のサイズの識別画像１３２により、複数の二値画像Ｐ１〜Ｐｍからそれぞれ抽出された全ての連結成分を再生するために必要な情報を保持し、認識部１６による文字認識処理に供することができる。
【００７７】
次に、上述した成分テーブル１３１に保持された情報に基づいて、認識ラティスＬｔにラティスノードとして含ませる連結成分を絞りこむ方法について説明する。このような連結成分の絞込みは、例えば、生成部１４が、認識ラティスＬｔを生成するのに先立って、成分ツリーＴｒを縮約することによって実現することができる。
【００７８】
図６に例示した生成部１４は、選択部１４１と縮約部１４２とリンク生成部１４３とを含み、選択部１４１と縮約部１４２によって成分ツリーＴｒの縮約を行い、縮約された成分ツリーＴｒをリンク生成部１４３の処理に供する。
【００７９】
選択部１４１は、成分ツリーＴｒに含まれる複数の連結成分の中から、文字を表す可能性がある連結成分を検出し、検出した連結成分を認識ラティスＬｔにおいて接続を設定する対象として選択する。また、縮約部１４２は、成分ツリーにおいて親子関係を有することが示されている連結成分の組のうち、形状が互いに類似している連結成分の組を検出し、検出した連結成分の組を一つの連結成分に縮約する。また、リンク生成部１４３は、選択部１４１及び縮約部１４２の処理によって縮約された成分ツリーＴｒに含まれる各ツリーノードをラティスノードとして、これらのラティスノードについての接続を設定する。
【００８０】
図６に例示した選択部１４１は、例えば、文字を表す連結成分が満たす形状についての条件Ｔに基づいて、各連結成分が文字を表す可能性があるか否かを判定し、この結果に基づいて、ツリーノードの取捨選択を行う。選択部１４は、例えば、条件Ｔとして、次の２つを用いることが望ましい。
(１)外接矩形の大きさが所定の範囲に含まれること
(２)連結成分の面積と外周の長さとの比が所定の範囲に含まれること
例えば、注目する連結成分の外接矩形の左上の頂点の座標(Ｘｍｉｎ，Ｙｍｉｎ)及び右下の座標(Ｘｍａｘ，Ｙｍａｘ)と、当該連結成分の面積を示す画素数Ｎ及び外周の長さを示す画素数Ｌとを用いれば、条件Ｔの(１)、(２)はそれぞれ式(２)、(３)のように表される。
Ｔｈ３≦ｍａｘ｛(Ｘｍａｘ−Ｘｍｉｎ)，(Ｙｍａｘ−Ｙｍｉｎ)｝≦Ｔｈ４  ・・・(２)
Ｎ／Ｌ≧Ｔｈ５                                                      ・・・（３）
なお、式(２)において、閾値Ｔｈ３は、文字の一部を表す要素の大きさの最小値に対応する値を設定することが望ましい。また、閾値Ｔｈ４は、１文字の横幅あるいは高さとして想定される最大値に対応する値を設定することが望ましい。また、式(３)において、閾値Ｔｈ５は、様々な文字を表すパターンについて求めた面積と外周の長さとの比の最小値に対応する値を設定することが望ましい。
【００８１】
選択部１４１は、例えば、このような条件Ｔを満たす連結成分に対応するツリーノードについて、図７に示した成分テーブル１３１のＴフラグに「１」を設定することにより、当該ツリーノードの属性の一部として、文字を表す可能性がある旨を示す。
【００８２】
例えば、図７に示した成分テーブル１３１において、各ツリーノードに対応して示されたＴフラグは、個々のツリーノードについて、選択部１４１が上述した判定を行った結果を示している。
【００８３】
つまり、選択部１４１は、図７に示すように、ノード番号７，１３，１４，１６に対応するＴフラグを「１」に設定することにより、これらのツリーノードの属性を示す情報の一部として、それぞれ文字を表す可能性がある旨を示す。同様に、選択部１４１は、図７に示すように、ノード番号１７，１８，１９、２１に対応するＴフラグを「１」に設定することにより、これらのツリーノードの属性を示す情報の一部として、それぞれ文字を表す可能性がある旨を示す。また、この成分テーブル１３１は、更に、ノード番号２２，２６，２７，２８に対応するＴフラグを「１」に設定することにより、これらのツリーノードの属性を示す情報の一部として、それぞれ文字を表す可能性がある旨を示す。
【００８４】
一方、選択部１４１は、上述した条件Ｔを満たさない連結成分に対応するＴフラグに「０」を設定することにより、当該ツリーノードの属性を示す情報の一部として、文字を表す可能性が低い旨を示す。例えば、選択部１４１は、図７に示すように、ノード番号１，２，３に対応するＴフラグに「０」を設定することにより、これらのツリーノードの属性を示す情報の一部として、文字を表す可能性が低い旨を示す。
【００８５】
同様にして、選択部１４１は、成分テーブル１３１のノード番号４，５，８，９，１０，１１に対応するＴフラグに「０」を設定することにより、これらのツリーノードの属性を示す情報の一部として、文字を表す可能性が低い旨を示す。また、選択部１４１は、成分テーブル１３１のノード番号２０，２３，２４，２７に対応するＴフラグに「０」を設定することにより、これらのツリーノードの属性を示す情報の一部として、文字を表す可能性が低い旨を示す。更に、選択部１４１は、成分テーブル１３１のノード番号２９，３０，３１に対応するＴフラグに「０」を設定することにより、これらのツリーノードの属性を示す情報の一部として、文字を表す可能性が低い旨を示す。
【００８６】
このようにして、選択部１４１は、個々の連結成分が文字を表す可能性の有無についての判定結果を、成分テーブル１３１を介してリンク生成部１４３に渡すことができる。
【００８７】
また、図６に示した縮約部１４２は、例えば、成分ツリーＴｒのルートノードから親子関係を再帰的に辿りつつ、子ノードに対応する連結成分が、親ノードに対応する連結成分の形状を引き継いでいるか否かを判定する。縮約部１４２は、例えば、親子関係を有する２つの連結成分が類似している場合に満たす条件Ｉに基づいて、上述した判定を行ってもよい。なお、縮約部１４２は、例えば、条件Ｉとして、「注目する連結成分の面積と、当該連結成分の親ノードに対応する連結成分の面積との比が所定の範囲に含まれる」を用いることが望ましい。また、縮約部１４２は、上述した選択部１４１によって上述した条件Ｔを満たすとされたツリーノードについて、条件Ｉに基づく判定を行うことが望ましい。
【００８８】
上述した条件Ｉは、例えば、注目するツリーノードｊに対応する連結成分の面積Ａｊを示す画素数Ｎｊと、この連結成分の親ノードに対応する連結成分の面積Ａｐを示す画素数Ｎｐとを用いれば、式(４)のように表すことができる。
Ｎｊ／Ｎｐ≧Ｔｈ６          ・・・(４)
なお、式(４)において、閾値Ｔｈ６は、例えば、０．５以上の値を設定することが望ましい。また、親子関係を持つ連結成分の組であって、様々な面積比を持つ連結成分について、文字認識処理を実行する実験などを行い、同一の候補文字が得られる最小の面積比を特定し、この面積比に基づいて、閾値Ｔｈ６の値を設定してもよい。
【００８９】
縮約部１４２は、上述した条件Ｔを満たすとされたツリーノードについて、親子関係を辿りつつ、この条件Ｉに基づく判定を行うことにより、親ノードと同一の候補文字が得られるような子ノードを順次に検出する。この過程において、縮約部１４２は、検出した子ノードに対応する成分テーブル１３１のＩフラグを「１」に設定する。これにより、縮約部１４２は、Ｉフラグに「１」が設定された子ノードが直列に連なった系列と、これらの子ノードのうち最もルートノードに近い子ノードの親に当たるツリーノードとを含むノードの系列を特定する。このようにして特定されたノードの系列は、文字を表す可能性を持ち、かつ、互いに類似した形状を持つ親子関係を持つノードが連なったツリーノードの系列である。
【００９０】
例えば、縮約部１４２は、上述した条件Ｉに基づいて、連結成分Ｃ３−６に対応するツリーノード１３を、親ノードであるツリーノード７に対応する連結成分Ｃ２−４の形状を引き継いでいる子ノードとして検出する。この検出結果に応じて、縮約部１４２は、図７に示すように、ノード番号１３に対応するＩフラグに「１」を設定することにより、このツリーノード１３の属性を示す情報の一部として、親ノードに対応する連結成分の形状を引き継いでいる旨を示す。つまり、縮約部１４２は、図３に示したツリーノード７からツリーノード１３に続く直列の系列を、互いに類似した形状を持つ親子関係を持つノードが連なったツリーノードの系列として特定する。同様にして、縮約部１４２は、図３に示したツリーノード６からツリーノード１２を経てツリーノード１７に至る直列の系列を、互いに類似した形状を持つ親子関係を持つノードが連なった系列として特定する。なお、図７に例示した成分テーブル１３１においては、ツリーノード６及びツリーノード１２に対応する情報の表示は省略している。
【００９１】
ところで、成分ツリーＴｒに含まれるツリーノードの中で、上述した条件Ｔを満たすツリーノードであって、条件Ｉを満たす子ノードを持たないツリーノードは、上述した系列に含まれるツリーノードが一つだけであるケースと捉えることができる。つまり、条件Ｔに基づいて、文字を表す可能性があるとされたツリーノードは、必ず、縮約部１４２が上述したようにして特定するツリーノードの系列のいずれかに含まれている。
【００９２】
そして、縮約部１４２によって特定されたツリーノードの系列に含まれる少なくとも一つのツリーノードは、単一の候補文字を導くことが明らかであるので、一つのツリーノードに縮約することが可能である。
【００９３】
縮約部１４２は、上述したようにして特定したノードの系列に含まれるツリーノードの一つを、この系列を代表するツリーノードとして選択することにより、当該系列に含まれる少なくとも一つのツリーノードを単一のツリーノードに縮約する。縮約部１４２は、例えば、特定したノードの系列に含まれる最もルートノードから遠いツリーノードを、代表ノードとして選択してもよい。また、縮約部１４２は、特定したノードの系列に含まれる最もルートノードに近いツリーノードを、代表ノードとして選択してもよいし、深さ方向に中間的な位置にあるツリーノードを代表ノードとして選択してもよい。なお、以下では、縮約部１４２が、特定したノードの系列に含まれる最もルートノードから遠いツリーノードを代表ノードとして選択する場合について説明する。
【００９４】
また、縮約部１４２は、上述したようにして特定したノードの系列に含まれる複数のツリーノードに対応するＤフラグに、選択した代表ノードを示すノード番号をそれぞれ設定することにより、これらのツリーノードを代表ノードに縮約したことを示す。つまり、各ツリーノードに対応して成分テーブル１３１に設定されるＤフラグは、当該ツリーノードが縮約される代表ノードを示している。
【００９５】
例えば、縮約部１４２は、図７に示すように、ノード番号７、１３に対応するＤフラグにノード番号「１３」をそれぞれ設定することにより、これらのツリーノード７，１３を含むノードの系列をツリーノード１３に縮約したことを示す。同様にして、縮約部１４２は、ツリーノード６からツリーノード１２を経てツリーノード１７に至るノードの系列の代表ノードとして、ルートノードから最も遠いツリーノード１７を選択する。そして、縮約部１４２は、成分テーブル１３１に含まれるノード番号６，１２，１７に対応するＤフラグに、選択した代表ノードを示すノード番号「１７」を設定することにより、ツリーノード１７が上述したノードの系列の代表ノードであることを示す。
【００９６】
なお、縮約部１４２は、成分テーブル１３１の各ノード番号に対応するＤフラグに予め初期値「−１」を設定しておいてもよい。この場合に、縮約部１４２が上述した縮約処理を行うことにより、条件Ｔを満たすツリーノードに対応して成分テーブル１３１に含まれるＤフラグは、当該ツリーノードが含まれるノードの系列の代表ノードを示すノード番号に更新される。一方、条件Ｔを満たさない連結成分に対応して成分テーブル１３１に含まれるＤフラグは、縮約部１４２の処理の完了後も、初期値「−１」を維持している。
【００９７】
したがって、図６に例示したリンク生成部１４３は、成分テーブル１３１に各ツリーノードに対応して保持されたＤフラグを参照することにより、初期値「−１」以外のノード番号の集合として縮約された成分ツリーに含まれるツリーノードを特定することができる。
【００９８】
図９は、縮約された成分ツリーＴｒの例を示している。なお、図９に示した要素のうち、図３に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【００９９】
図９において、点線で表した小さい丸印は、上述した条件Ｔを満たさない連結成分に対応しているために、認識ラティスＬｔの生成処理から除外されるツリーノードを示す。一方、図９において、太線で表した丸印は、上述した条件Ｔを満たす連結成分に対応するツリーノードを示している。
【０１００】
なお、太線で表した丸印で示したツリーノードのうち、連結成分Ｃ２−３，Ｃ３−５，Ｃ４−４に対応する３つのツリーノードに付された同一のノード番号「１７」は、これらのツリーノードがノード番号１７のツリーノードに縮約されたことを示している。同様に、連結成分Ｃ２−４，Ｃ３−６に対応する２つのツリーノードに付された同一のノード番号「１３」は、これらのツリーノードがノード番号１３のツリーノードに縮約されたことを示している。
【０１０１】
つまり、図６に例示した選択部１４１と縮約部１４２とが上述した処理を実行することにより、図３に示した３１個のツリーノードを含む成分ツリーＴｒを、図９に示したように、わずか１１個のツリーノードを含む成分ツリーＴｒに縮約することができる。
【０１０２】
上述したようにして縮約された成分ツリーＴｒは、有効な候補文字が得られる連結成分に対応するツリーノードを漏れなく含んでおり、しかも、同一の候補文字が得られる冗長な連結成分に対応する冗長なツリーノードに代えて一つのツリーノードを含んでいる。したがって、縮約された成分ツリーＴｒに含まれるツリーノードに対応するラティスノード間についてリンク生成部１４３がリンクを生成することで、認識ラティスの規模を抑制しながら、正解の候補文字列を高い確度で含む認識ラティスを生成することができる。
【０１０３】
次に、図６に例示したリンク生成部１４３が、上述した成分テーブル１３１に含まれる情報に基づいて、認識ラティスＬｔを表すラティステーブル１５を生成する処理について説明する。
【０１０４】
リンク生成部１４３は、例えば、成分テーブル１３１に各ノード番号に対応して保持されたＤフラグを参照し、初期値「−１」以外のノード番号の集合を取得する。次いで、リンク生成部１４３は、例えば、取得したノード番号に対応して成分テーブル１３１に保持された外接矩形の左上画素の座標が昇順となるように、これらのノード番号で示されるツリーノードをソートする。そして、リンク生成部１４３は、このソート結果に基づいて、図１０に示すように、ラティステーブル１５に、各ノード番号を順次に登録する。
【０１０５】
図１０は、ラティステーブル１５の一例を示している。このラティステーブル１５は、個々のラティスノードに関する情報と、ラティスノード間を接続するリンクに関する情報とを含んでいる。
【０１０６】
このラティステーブル１５において、個々のラティスノードに関する情報は、ラティスノード番号と、包含するツリーノードの個数を示すツリーノード個数と、包含するツリーノードのそれぞれを示す情報とを含んでいる。
【０１０７】
ここで、リンク生成部１４３は、成分テーブル１３１から取得したノード番号で示されるラティスノードを登録する際に、ツリーノード個数として「１」を設定し、また、包含するツリーノードに取得したノード番号を設定する。これにより、当該ラティスノードとツリーノードとが１対１で対応することを示す。なお、後述する認識ラティスの拡張処理においては、ラティスノードとして複数のツリーノードを含むラティスノードを登録する際に、ツリーノード個数に「１」以外の値を設定し、また、包含するツリーノードの欄に複数のノード番号を設定する場合がある。
【０１０８】
図１０に例示したラティステーブル１５は、ノード番号１で示されるラティスノードとして、包含するツリーノードで示されたノード番号１４のツリーノードが登録されたことを示している。
【０１０９】
同様に、ラティステーブル１５は、ノード番号２のラティスノードとして、ノード番号２１のツリーノードが登録され、また、ノード番号３のラティスノードとして、ノード番号２２のツリーノードが登録されたことを示している。
【０１１０】
更に、ラティステーブル１５は、ノード番号４のラティスノードとして、ノード番号１６のツリーノードが登録され、同様に、ノード番号５のラティスノードとして、ノード番号２６のツリーノードが登録されたことを示している。
【０１１１】
また、ラティステーブル１５は、ノード番号６のラティスノードとして、ノード番号２７のツリーノードが登録され、また、ノード番号７のラティスノードとして、ノード番号１７のツリーノードが登録されたことを示している。
【０１１２】
更に、ラティステーブル１５は、ノード番号８のラティスノードとして、ノード番号２８のツリーノードが登録され、同様に、ノード番号９で示されるラティスノードとして、ノード番号１３のツリーノードが登録されたことを示している。
【０１１３】
また、ラティステーブル１５は、ノード番号１０のラティスノードとして、ノード番号１８のツリーノードが登録され、ラティスノード番号１１のラティスノードとして、ノード番号１９のツリーノードが登録されたことを示している。
【０１１４】
また、ラティステーブル１５において、リンクに関する情報は、前側リンク個数と、前側リンクノードと、後側リンク個数と、後側リンクノードとを含んでいる。なお、以下の説明において、前側リンクとは、候補文字列において、注目するラティスノードに対応する候補文字よりも前側に位置する候補文字に対応するラティスノードから注目するラティスノードへ向かうリンクを指す。逆に、後側リンクとは、候補文字列において、注目するラティスノードから、このラティスノードに対応する候補文字よりも後ろに位置する候補文字に対応するラティスノードに向かうリンクを指す。例えば、候補文字列が左から右に並んでいる場合は、注目するラティスノードよりも左側に位置するラティスノードから注目するラティスノードに向かうリンクが前側リンクに相当し、逆向きのリンクが後側リンクに相当する。
【０１１５】
図６に例示したリンク生成部１４３は、上述したようにしてラティステーブル１５に登録したラティスノード間を接続するリンクを、図４及び図５を用いて説明したようにして設定する。
【０１１６】
例えば、リンク生成部１４３は、ノード番号順に注目するラティスノードを選択し、上述した接続条件に基づいて、注目するラティスノードに接続されるラティスノードを検出する。そして、リンク生成部１４３は、検出したラティスノードを示すノード番号を、注目するラティスノードに対応する後側リンクノードに登録するとともに、後側リンク個数に数値「１」を加算する。更に、リンク生成部１４３は、検出したラティスノードに対応する前側リンクノードに、注目するラティスノードを示すノード番号を登録するとともに、前側リンク個数に数値「１」を加算する。なお、ラティステーブル１５において、各ラティスノードに対応する前側リンク個数及び後側リンク個数は、リンク生成部１４３が処理を開始するのに先立って、初期値「０」を設定しておくことが望ましい。また、ラティステーブル１５の各ラティスノードに対応する前側リンクノードおよび後側リンクノードには、それぞれ該当するラティスノードがない旨を示す初期値「ＮＵＬＬ」を設定しておいてもよい。また、以下の説明では、ノード番号ｊのラティスノードをラティスノードｊと称し、ノード番号ｋのツリーノードを、ツリーノードｋと称する。
【０１１７】
例えば、リンク生成部１４３は、ラティスノード１に対応して登録されたツリーノード１４に対応する連結成分Ｃ４−１と、ラティスノード２〜１１に対応する連結成分のそれぞれとについて、接続条件を満たすか否かを判定する。この判定処理により、リンク生成部１４３は、ラティスノード１に接続されるラティスノードとして、連結成分Ｃ４−３，Ｃ５−６，Ｃ５−７に対応するツリーノード１６，２６，２７が登録されたラティスノード４，５，６をそれぞれ検出する。そして、リンク生成部１４３は、これらのラティスノードを示す番号４，５，６を、ラティスノード１に対応する後側リンクノードとしてラティステーブル１５に登録するとともに、後側リンク個数を「３」とする。また、リンク生成部１４３は、ラティスノード４，５，６に対応する前側リンクノードに、ラティスノード１を示す番号１を登録するとともに、前側リンク個数に数値「１」を加算する。
【０１１８】
同様にして、リンク生成部１４３が、各ラティスノードについての処理を行うことにより、図１０に示したラティステーブル１５において、ラティスノード１〜１１に対応して示したように、各ラティスノードのリンクに関する情報を生成することができる。
【０１１９】
図１０の例では、ラティステーブル１５は、ラティスノード１に対応するリンクに関する情報として、前側リンク個数「０」、前側リンクノード「ＮＵＬＬ」、後側リンク個数「３」、後側リンクノード「４，５，６」を含んでいる。
【０１２０】
同様に、ラティステーブル１５は、ラティスノード２に対応するリンクに関する情報として、前側リンク個数「０」、前側リンクノード「ＮＵＬＬ」、後側リンク個数「３」、後側リンクノード「３，４，５」を含んでいる。
【０１２１】
一方、ラティステーブル１５は、ラティスノード３に対応するリンクに関する情報として、前側リンク個数「１」、前側リンクノード「２」、後側リンク個数「３」、後側リンクノード「４，５，６」を含んでいる。
【０１２２】
また、ラティステーブル１５は、ラティスノード４に対応するリンクに関する情報として、前側リンク個数「３」、前側リンクノード「１，２，３」、後側リンク個数「２」、後側リンクノード「７，８」を含んでいる。
【０１２３】
更に、ラティステーブル１５は、ラティスノード５に対応するリンクに関する情報として、前側リンク個数「３」、前側リンクノード「１，２，３」、後側リンク個数「３」、後側リンクノード「６，７，８」を含んでいる。
【０１２４】
同様に、ラティステーブル１５は、ラティスノード６に対応するリンクに関する情報として、前側リンク個数「３」、前側リンクノード「１，３，５」、後側リンク個数「２」、後側リンクノード「７，８」を含んでいる。
【０１２５】
また、ラティステーブル１５は、ラティスノード７に対応するリンクに関する情報として、前側リンク個数「３」、前側リンクノード「４，５，６」、後側リンク個数「２」、後側リンクノード「９，１０」を含んでいる。
【０１２６】
また、ラティステーブル１５は、ラティスノード８に対応するリンクに関する情報として、前側リンク個数「３」、前側リンクノード「４，５，６」、後側リンク個数「３」、後側リンクノード「９，１０，１１」を含んでいる。
【０１２７】
更に、ラティステーブル１５は、ラティスノード９に対応するリンクに関する情報として、前側リンク個数「２」、前側リンクノード「７，８」、後側リンク個数「０」、後側リンクノード「ＮＵＬＬ」を含んでいる。
【０１２８】
また、ラティステーブル１５は、ラティスノード１０に対応するリンクに関する情報として、前側リンク個数「２」、前側リンクノード「７，８」、後側リンク個数「１」、後側リンクノード「１１」を含んでいる。
【０１２９】
そして、ラティステーブル１５は、ラティスノード１１に対応するリンクに関する情報として、前側リンク個数「２」、前側リンクノード「８，１０」、後側リンク個数「０」、後側リンクノード「ＮＵＬＬ」を含んでいる。
【０１３０】
図１０に例示したラティステーブル１５に含まれるリンクに関する情報は、図１１に示すような認識ラティスＬｔに含まれる各リンクを示している。
【０１３１】
図１１は、縮約された成分ツリーＴｒから生成した認識ラティスＬｔの例を示している。なお、図１１に示した要素のうち、図２に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０１３２】
図１１において、符号Ｌｎ１〜Ｌｎ１１は、それぞれラティスノード１〜１１を示している。また、符号Ｓ５は、図２に示した二値画像Ｐ５から抽出された連結成分に対応するラティスノードの集合を示しており、この集合Ｓ５は、ラティスノード２，３，５，６，８を含んでいる。同様に、符号Ｓ４は、図２に示した二値画像Ｐ４から抽出された連結成分に対応するラティスノードの集合を示しており、この集合Ｓ４は、ラティスノード１，４，７，１０，１１を含んでいる。また、符号Ｓ３は、図２に示した二値画像Ｐ３から抽出された連結成分に対応するラティスノードの集合を示しており、この集合Ｓ３は、ラティスノード９を含んでいる。
【０１３３】
図１１に示した認識ラティスＬｔは、それぞれ異なる閾値に対応する二値画像から抽出された連結成分のうち、有効な候補文字が認識結果として得られ、かつ認識結果として得られる候補文字が重複しない連結成分間の考えられる並び順を網羅的に示している。
【０１３４】
したがって、図６に例示した選択部１４１及び縮約部１４２を含む生成部１４によって得られた認識ラティスＬｔによって示される候補文字列は、入力画像Ｐｉｎに含まれる文字列を示す正解の候補文字列を極めて高い確度で含んでいる。
【０１３５】
故に、この認識ラティスＬｔに基づいて、認識部１６および評価部１７がそれぞれ上述した文字認識処理及び評価処理を実行することにより、入力画像Ｐｉｎに含まれる文字列を高い精度で抽出することができる。例えば、図１１に示した認識ラティスＬｔは、正解の文字列「十万本の」に含まれる各候補文字「十」、「万」、「本」、「の」にそれぞれ対応するラティスノード１，４，７，９を順に接続する候補文字列を含んでいる。なお、図１１において、太線の矢印は、正解の文字列に対応する候補文字列を示すリンクを示している。
【０１３６】
しかも、上述したように、縮約された成分ツリーＴｒから生成した認識ラティスＬｔは、全ての二値画像Ｐ１〜Ｐｍから抽出された全ての連結成分に関する認識ラティスに比べて非常に規模が小さい。したがって、縮約された成分ツリーＴｒから生成した認識ラティスＬｔを、認識部１６及び評価部１７の処理対象とすることにより、入力画像Ｐｉｎから文字列を抽出する処理に要する時間を、成分ツリーの縮約を適用しない場合に比べて短縮することが可能である。
【０１３７】
つまり、図６に例示した選択部１４１及び縮約部１４２を有する本件開示の文字認識装置１０によれば、入力画像Ｐｉｎに含まれる文字列を高い精度で、しかも、高速に抽出することが可能である。
【０１３８】
なお、本件開示の文字認識装置１０は、上述した選択部１４１と縮約部１４２とのいずれか一方を有する生成部１４を含んでもよい。いずれの場合も、正解の候補文字列を示すラティスノード及びリンクを維持しつつ、認識ラティスの規模を縮小することが可能である。
【０１３９】
ところで、認識対象の文字が漢字のように１文字が互いに連結されていない複数の部分を含んでいる文字である場合は、図１２に示すように、これらの部分がそれぞれ連結成分として抽出される場合がある。
【０１４０】
図１２は、入力画像と二値画像の別例を示している。図１２において、符号Ｇｉｎは、図２に示した入力画像Ｐｉｎとは別の入力画像を示している。また、符号Ｇ５は、入力画像Ｇｉｎを、図２に示した閾値ｔｈ５を用いて二値化して得られた二値画像を示し、符号Ｇ４は、同じく、入力画像Ｇｉｎを、図２に示した閾値ｔｈ４を用いて二値化して得られた二値画像を示す。
【０１４１】
また、図１２において、符号Ｄ５−１，Ｄ５−２，Ｄ５−３は、それぞれ二値画像Ｇ５から抽出された連結成分を示し、一方、符号Ｄ４−１，Ｄ４−２，Ｄ４−３，Ｄ４−４，Ｄ４−５は、それぞれ二値画像Ｇ４から抽出された連結成分を示す。
【０１４２】
図１２に示したように、入力画像Ｇｉｎに含まれる文字列は、一様な明るさで表現されるとは限らないため、文字を表すパターンの一部が、高い濃度値に対応する閾値で二値化された二値画像に現れない場合がある。また一方、文字列の背景の濃度と同等の閾値で二値化された二値画像においては、文字を表すパターンと背景の一部とが一体となってしまう場合もある。
【０１４３】
例えば、図１２に示した二値画像Ｇ５は、入力画像Ｇｉｎに含まれる文字「明」を表すパターンの一部に相当する連結成分Ｄ５−１と、文字「ら」を表すパターンに相当する連結成分Ｄ５−２と、文字「か」を表すパターンの一部に相当する連結成分Ｄ５−３を含んでいる。その一方、この二値画像Ｇ５には、文字「明」の日偏を表すパターンに対応する連結成分及び文字「か」を表すパターンの別の一部は含まれていない。
【０１４４】
他方、図１２に示した二値画像Ｇ４は、入力画像Ｇｉｎに含まれる文字「明」を表すパターンのうち、日偏を表す部分に相当する連結成分Ｄ４−１を含んでいる一方、旁を表す部分と背景の一部とが一体となったパターンに相当する連結成分を含んでいる。同様に、この二値画像Ｇ４は、文字「か」を表すパターンの一部と背景とが一体になったパターンに相当する連結成分Ｄ４−４と、文字「か」を表すパターンの別の一部に相当する連結成分Ｄ４−５を含んでいる。更に、この二値画像Ｇ４は、文字「ら」を表すパターンに相当する連結成分Ｄ４−３を含んでいる。
【０１４５】
以下、図１２に示したような複雑な入力画像Ｇｉｎに含まれる文字列の抽出に好適な文字認識装置１０の実施形態について説明する。
図１３は、文字認識装置１０の別実施形態を示している。なお、図１３に示した構成要素のうち、図１及び図６に示した構成要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０１４６】
図１３に例示した生成部１４は、上述した選択部１４１、縮約部１４２、リンク生成部１４３に加えて、拡張部１４４を含んでいる。この拡張部１４４は、認識ラティスＬｔによって接続が設定された各連結成分と当該連結成分を含む所定の大きさの領域内に含まれる別の連結成分とを結合することで新たな連結成分を生成する。また、この拡張部１４４は、複数の連結成分を結合することで生成した新たな連結成分を認識ラティスＬｔに追加することにより、認識ラティスＬｔを拡張する。
【０１４７】
拡張部１４４は、例えば、リンク生成部１４３によって生成された認識ラティスＬｔに含まれる各ラティスノードに対応する連結成分に順次に注目し、この連結成分を含む所定の大きさの領域内に他の各連結成分が含まれるか否かを判定する。そして、拡張部１４４は、注目する連結成分に対応する領域内に含まれると判定した他の連結成分を、注目する連結成分と結合する連結成分として検出する。拡張部１４４は、次に述べる結合条件を用いて、注目したラティスノードに対応する連結成分と他のラティスノードに対応する連結成分とが結合可能か否かを判定することが望ましい。
【０１４８】
図１４は、結合条件を説明する図である。図１４において、符号Ｒｊは、注目するラティスノードに対応する連結成分の外接矩形を示す。また、符号Ｒｐは、注目する連結成分との結合が可能か否かを判定する対象となる連結成分の外接矩形を示す。
【０１４９】
図１３に例示した拡張部１４４は、結合条件として、図１４に示した外接矩形Ｒｊと外接矩形Ｒｐとの両方を含む外接矩形Ｒｃの大きさが所定の大きさよりも小さいことを用いて、２つの連結成分が結合可能か否かを判定することが望ましい。
【０１５０】
このような結合条件は、例えば、外接矩形Ｒｃの２辺の長さＤｘ，Ｄｙと、それぞれについての上限を示す閾値Ｔｈ７，Ｔｈ８とを用いて、式(５)のように表すことができる。
Ｄｘ≦Ｔｈ７  ＆  Ｄｙ≦Ｔｈ８        ・・・(５)
なお、式(５)において、閾値Ｔｈ７及び閾値Ｔｈ８は、例えば、入力画像Ｐｉｎに含まれる個々の文字が高い確度で含まれる矩形の２辺の長さに基づいて設定することが望ましい。
【０１５１】
例えば、拡張部１４４は、式(５)で示した結合条件に基づいて、図１２に例示した二値画像Ｇ４から抽出された連結成分Ｄ４−１に結合する連結成分として、図１２に例示した二値画像Ｇ５から抽出された連結成分Ｄ５−１を検出する。このようにして検出した連結成分Ｄ４−１，Ｄ５−１を結合することにより、拡張部１４４は、新たな連結成分Ｎ１を生成する。同様にして、図１２に例示した二値画像Ｇ５から抽出された連結成分Ｄ５−２、Ｄ５−３を結合することにより、拡張部１４４は、新たな連結成分Ｎ２を生成する。また、拡張部１４４は、図１２に例示した二値画像Ｇ５から抽出された連結成分Ｄ５−３と二値画像Ｇ４から抽出された連結成分Ｄ４−５とを結合することにより、新たな連結成分Ｎ３を生成する。
【０１５２】
このようにして得られた新たな連結成分に対応するラティスノードを認識ラティスＬｔに追加することにより、拡張部１４４は、より高い確度で正しい認識結果の文字列を抽出することを可能とする拡張された認識ラティスを生成することができる。
【０１５３】
図１５は、認識ラティスＬｔの拡張を説明する図である。なお、図１５に示した要素のうち、図１２に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０１５４】
図１５(Ａ)は、図１３に例示した拡張部１４４による拡張処理を行う前の認識ラティスＬｔを示している。この認識ラティスＬｔは、二値画像Ｇ５から抽出された３つの連結成分Ｄ５−１，Ｄ５−２、Ｄ５−３に対応するラティスノードと、二値画像Ｇ４から抽出された２つの連結成分Ｄ４−１，Ｄ４−５に対応するラティスノードとを含んでいる。また、図１５(Ａ)に示した認識ラティスＬｔは、上述した５つのラティスノード間を接続するリンクを含んでいる。
【０１５５】
なお、図１５(Ａ)において、符号Ｓ５は、二値画像Ｇ５から抽出された連結成分に対応するラティスノードの集合を示し、符号Ｓ４は、二値画像Ｇ４から抽出された連結成分に対応するラティスノードの集合を示している。
【０１５６】
このような認識ラティスＬｔに対して、拡張部１４４が上述したようにして新たに生成した連結成分Ｎ１，Ｎ２，Ｎ３に対応するラティスノードを追加することにより、図１５(Ｂ)に示すような拡張された認識ラティスを生成することができる。なお、図１５(Ｂ)において、符号ＳＮは、拡張部１４４によって新たに生成された連結成分に対応するラティスノードの集合を示している。
【０１５７】
図１３に例示した拡張部１４４は、新たに生成された連結成分Ｎ１，Ｎ２，Ｎ３に対応するラティスノードの追加に伴って、これらのラティスノードにかかわる接続をそれぞれ設定することにより、認識ラティスＬｔを拡張する。
【０１５８】
図１５(Ｂ)に示した拡張後の認識ラティスＬｔは、連結成分Ｎ１に対応するラティスノードから連結成分Ｄ５−２，Ｎ２に対応するラティスノードに向かって新たに設定されたリンクを含んでいる。同様に、拡張後の認識ラティスＬｔは、連結成分Ｄ４−１，Ｄ５−１に対応するラティスノードから連結成分Ｎ２に対応するラティスノードに向かって新たに設定されたリンクを含んでいる。また、拡張後の認識ラティスＬｔは、連結成分Ｄ５−２に対応するラティスノードから連結成分Ｎ３に対応するラティスノードに向かって新たに設定されたリンクを含んでいる。更に、拡張後の認識ラティスＬｔは、連結成分Ｎ２に対応するラティスノードから連結成分Ｄ４−５に対応するラティスノードに向かって新たに設定されたリンクを含んでいる。
【０１５９】
このようにして認識ラティスＬｔを拡張することにより、正確の文字列に対応する候補文字列が認識ラティスＬｔに含まれている可能性を更に高めることができる。例えば、図１５(Ｂ)に示した拡張後の認識ラティスＬｔは、入力画像Ｇｉｎに含まれる文字列「明らか」を導く候補文字列を、連結成分Ｎ１，Ｄ５−２，Ｎ３に対応するラティスノードを順次に辿る経路として含んでいる。
【０１６０】
つまり、図１３に例示した拡張部１４４を有する生成部１４を含む文字認識装置１０によれば、複雑な画像を背景として多様な色彩を有するパターンによって表現された文字列を、高い精度で抽出することが可能である。
【０１６１】
なお、上述した拡張部１４４は、複数の連結成分を結合して得られた新たな連結成分同士を結合することにより、更に新たな連結成分を生成し、生成した連結成分に対応するラティスノードを認識ラティスに追加してもよい。このように、拡張部１４４が、連結成分の結合処理を再帰的に行うことにより、入力画像Ｐｉｎに、多数の部首が組み合わされて形成された漢字のように複雑なパターンで表された文字を含む文字列が含まれている場合においても、高い精度で文字列を抽出することが可能となる。
【０１６２】
以上に説明した本件開示の文字認識装置１０は、例えば、パーソナルコンピュータなどのコンピュータ装置を用いて実現することができる。
【０１６３】
図１６は、文字認識装置１０のハードウェア構成の一例を示している。
【０１６４】
コンピュータ装置２０は、プロセッサ２１と、メモリ２２と、ハードディスク装置（ＨＤＤ）２３と、表示装置２４と、入力装置２５と、光学ドライブ装置２６と、周辺機器インタフェース２７と、ネットワークインタフェース２８とを含んでいる。また、図１６において、文字認識装置１０は、プロセッサ２１と、メモリ２２と、ハードディスク装置２３と、周辺機器インタフェース２７とを含んでいる。図１６に例示したプロセッサ２１と、メモリ２２と、ハードディスク装置２３と、表示装置２４と、入力装置２５と、光学ドライブ装置２６と、周辺機器インタフェース２７と、ネットワークインタフェース２８とは、バスを介して互いに接続されている。また、コンピュータ装置２０は、周辺機器インタフェース２７を介して画像入力装置２に接続されている。
【０１６５】
この画像入力装置２は、文字列を含むカラー原稿を読み取ることで又はテロップを含むカラーテレビジョン放送の画像をキャプチャすることで得られるカラー画像に対して、グレースケール変換処理を行うことにより、グレースケール画像を生成する機能を有する。このようにして得られるグレースケール画像は、文字認識対象の入力画像Ｐｉｎとして、プロセッサ２１と、メモリ２２およびハードディスク装置２３と、周辺機器インタフェース２７とを含む文字認識装置１０に入力される。
【０１６６】
なお、カラー画像からグレースケール画像を生成する機能は、コンピュータ装置２０内に設けた画像処理部(図示せず)によって実現してもよい。また、プロセッサ２１が、メモリ２２あるいはハードディスク装置２３に読み込んだプログラムを実行することによって、カラー画像からグレースケール画像を生成する機能を実現してもよい。
【０１６７】
上述した光学ドライブ装置２６は、光ディスクなどのリムーバブルディスク２９を装着可能であり、装着したリムーバブルディスク２７に記録された情報の読み出しおよび記録を行う。また、コンピュータ装置２０は、ネットワークインタフェース２８を介して、ネットワークＮＷに接続されている。
【０１６８】
図１６に例示した入力装置２５は、例えば、キーボードやマウスなどである。文字認識装置１０の操作者は、入力装置２５を操作することにより、文字認識装置１０に対して、例えば、画像入力装置１に対応する白色基準情報を生成する処理を開始させる旨の指示などを入力することができる。
【０１６９】
図１６に例示したメモリ２２は、コンピュータ装置２０のオペレーティングシステムとともに、プロセッサ２１が上述した文字認識処理を実行するためのアプリケーションプログラムである文字認識プログラムを格納している。なお、上述した文字認識プログラムは、例えば、光ディスクなどのリムーバブルディスク２７に記録して頒布することができる。そして、このリムーバブルディスク２７を光学ドライブ装置２６に装着して読み込み処理を行うことにより、文字認識プログラムを、メモリ２２およびハードディスク装置２３に格納させてもよい。また、インターネットなどのネットワークに接続する通信装置(図示せず)を介して、文字認識プログラムをメモリ２２およびハードディスク装置２３に読み込ませることもできる。
【０１７０】
上述した文字認識プログラムは、入力画像Ｐｉｎを複数の閾値を用いて二値化することにより、複数の二値画像を取得する処理をプロセッサ２１に実行させるための二値化プログラムを含んでいる。また、この文字認識プログラムは、これらの二値画像から抽出した連結成分の包含関係を探索することにより、これらの連結成分に関する成分ツリーＴｒを生成する処理をプロセッサ２１に実行させるための探索処理プログラムを含んでいる。更に、この文字認識プログラムは、生成した成分ツリーＴｒに基づいて、認識ラティスＬｔを生成する処理をプロセッサ２１に実行させるためのラティス生成プログラムを含んでいる。また、この文字認識プログラムは、生成した認識ラティスＬｔに含まれる各ラティスノードに対応する連結成分についてのパターン認識処理をプロセッサ２１に実行させるためのパターン認識プログラムを含んでいる。更に、この文字認識プログラムは、パターン認識処理で得られた各候補文字の確信度に基づいて、認識ラティスＬｔで示された各候補文字列を評価する処理をプロセッサ２１に実行させるための評価処理プログラムを含んでいる。したがって、プロセッサ２１が、この文字認識プログラムを実行することにより、本件開示の文字認識方法に従って、入力画像Ｐｉｎに含まれる文字列を抽出する文字認識処理を実行することができる。
【０１７１】
また、プロセッサ２１は、メモリ２２、ハードディスク装置２３及び周辺機器インタフェース２７と協働しつつ、二値化プログラムを実行することにより、図１に例示した二値化部１１の機能を果たす。また、プロセッサ２１は、メモリ２２およびハードディスク装置２３と協働しつつ、探索処理プログラムを実行することにより、図１に例示した探索部１２の機能を果たす。同様に、プロセッサ２１は、メモリ２２およびハードディスク装置２３と協働しつつ、ラティス生成プログラムを実行することにより、図１に例示した生成部１４の機能を果たす。また、プロセッサ２１は、メモリ２２およびハードディスク装置２３と協働しつつ、パターン認識プログラムを実行することにより、図１に例示した認識部１６の機能を果たす。そして、プロセッサ２１は、メモリ２２およびハードディスク装置２３と協働しつつ、評価処理プログラムを実行することにより、図１に例示した評価部１７の機能を果たす。このように、プロセッサ２１が、メモリ２２、ハードディスク装置２３及び周辺機器インタフェース２７と協働しつつ、文字認識プログラムを実行することにより、本件開示の文字認識装置１０を実現することができる。
【０１７２】
なお、プロセッサ２１は、上述した二値化プログラムを実行する過程において、生成した複数の二値画像をメモリ２２あるいはハードディスク装置２３に格納してもよい。また、プロセッサ２１は、上述した探索処理プログラムを実行する過程において、生成した成分ツリーＴｒを表す成分テーブル１３１及び識別子画像１３２をメモリ２２あるいはハードディスク装置２３に格納してもよい。同様に、プロセッサ２１は、上述したラティス生成プログラムを実行する過程において、生成した認識ラティスＬｔを表すラティステーブル１５をメモリ２２あるいはハードディスク装置２３に格納してもよい。
【０１７３】
プロセッサ２１は、例えば、図１７に示すフローチャートに含まれる各ステップの処理を実行することにより、入力画像Ｐｉｎに含まれる文字列を抽出する。
図１７は、文字認識処理のフローチャートの一例を示している。図１７に示したステップＳ３０１〜ステップＳ３０７の各処理は、文字認識プログラムに含まれる処理の一例である。また、これらのステップＳ３０１〜ステップＳ３０７の各処理は、プロセッサ２１によって実行される。
【０１７４】
プロセッサ２１は、まず、周辺機器インタフェース２７を介して、画像入力装置２によってグレースケール変換された入力画像Ｐｉｎを受け取る(ステップＳ３０１)。次いで、プロセッサ２１は、二値化プログラムに従う処理を行うことにより、入力画像Ｐｉｎをｍ個の閾値を用いて二値化する処理を行い、各閾値に対応する二値画像Ｐ１〜Ｐｍを生成する(ステップＳ３０２)。
【０１７５】
次に、プロセッサ２１は、探索プログラムに従う処理を行うことにより、各二値画像Ｐ１〜Ｐｍに含まれる連結成分をそれぞれ抽出するとともに、抽出した各連結成分に関する親子関係を示す成分ツリーＴｒを生成する(ステップＳ３０３)。このステップＳ３０３，の処理の過程において、プロセッサ２１は、メモリ２２あるいはハードディスク装置２３に確保した記憶領域に、成分ツリーＴｒを表す情報を格納することによって成分テーブル１３１を生成する。また、このステップＳ３０３の処理の過程において、プロセッサ２１は、メモリ２２あるいはハードディスク装置２３に確保した記憶領域に対して、図８を用いて説明した処理を行うことにより、識別子画像１３２を生成する。
【０１７６】
次いで、プロセッサ２１は、ラティス生成プログラムに従う処理を行うことにより、上述したステップＳ３０４の処理で生成した成分ツリーＴｒを縮約し(ステップＳ３０４)、縮約した成分ツリーＴｒに基づいて、認識ラティスＬｔを生成する(ステップＳ３０５)。このように、ステップＳ３０５の認識ラティスＬｔの生成処理に先立って、ステップＳ３０４の成分ツリーＴｒの縮約処理を実行する手順は、より好ましい手順である。このステップＳ３０４の処理の過程において、プロセッサ２１は、メモリ２２あるいはハードディスク装置２３に保持された成分テーブル１３１に含まれる情報を後述するように操作することで、成分ツリーＴｒの縮約処理を実現する。また、プロセッサ２１は、ステップＳ３０５の処理の過程において、メモリ２２あるいはハードディスク装置２３に確保した記憶領域に、後述するようにして、認識ラティスＬｔを表す情報を格納することによってラティステーブル１５を生成する。
【０１７７】
ここで、図１８〜図２５を用いて、成分ツリーＴｒを縮約する処理及び認識ラティスＬｔを生成する処理について説明する。まず、成分ツリーＴｒを縮約する処理について説明する。
【０１７８】
図１８は、成分ツリーＴｒを縮約する処理のフローチャートの一例を示している。図１８に示したステップＳ３１１〜ステップＳ３１５の各処理は、ラティス生成プログラムに含まれる成分ツリーＴｒを縮約する手順の処理の一例であり、図１７に示したステップＳ３０４の処理に相当する。また、これらのステップＳ３１１〜ステップＳ３１５の各処理は、プロセッサ２１によって実行される。
【０１７９】
まず、プロセッサ２１は、図３に示した成分ツリーＴｒのルートノードを処理対象のツリーノードとして選択し(ステップＳ３１１)、処理対象のツリーノードの属性を判別する処理を行う(ステップＳ３１２)。プロセッサ２１は、図１９に示すように、ステップＳ３１２の処理を、成分ツリーＴｒの親子関係に従って再帰的に実行することにより、成分ツリーＴｒに含まれる各ツリーノードの属性を示すＴフラグ及びＩフラグをそれぞれ設定する。
【０１８０】
図１９は、ツリーノードの属性を判別する処理のフローチャートの一例を示している。図１９に示したステップＳ３２１〜ステップＳ３２９の各処理は、上述した成分ツリーＴｒを縮約する手順に含まれるツリーノードの属性を判別する手順の処理の一例であり、図１８に示したステップＳ３１２の処理に相当する。また、これらのステップＳ３２１〜ステップＳ３２９の各処理は、プロセッサ２１によって実行される。
【０１８１】
プロセッサ２１は、まず、処理対象のツリーノードについて、メモリ２２あるいはハードディスク装置２３に保持された成分テーブル１３１を参照することにより、当該ツリーノードに関する情報を取得する(ステップＳ３２１)。このとき、プロセッサ２１は、処理対象のツリーノードｊに対応して成分テーブル１３１に保持された外接矩形Ｒｊの頂点の座標(Ｘｊｕ，Ｙｊｕ)，（Ｘｊｄ，Ｙｊｄ）と、面積を示す画素数Ｎｊ及び外周を示す画素数Ｌｊを取得することが望ましい。また、プロセッサ２１は、ステップＳ３２１の処理で、上述した情報とともに、処理対象のツリーノードに対応して成分テーブル１３１に登録された子ノードを示す情報として、例えば、子ノード番号として登録されたノード番号の集合を取得することが望ましい。
【０１８２】
次いで、プロセッサ２１は、ステップＳ３２１で取得した処理対象のツリーノードに関する情報が、上述した式(２)、(３)で表される条件Ｔを満たすか否かを判定する(ステップＳ３２２)。
【０１８３】
このステップＳ３２２の肯定判定ルートにおいて、プロセッサ２１は、以下のステップＳ３２３〜ステップＳ３２７の処理を実行する。一方、ステップＳ３２２の否定判定ルートにおいて、プロセッサ２１は、ステップＳ３２３〜ステップＳ３２７の処理をスキップし、ステップＳ３２８の処理に進む。
【０１８４】
ステップＳ３２３の処理において、プロセッサ２１は、上述した成分テーブル１３１に対して、処理対象のツリーノードに対応するＴフラグに「１」を設定する操作を行う(ステップＳ３２３)。次いで、プロセッサ２１は、処理対象のツリーノードの親ノードについて成分テーブル１３１を参照することにより、この親ノードに関する情報を取得する(ステップＳ３２４)。このステップＳ３２４の処理で、プロセッサ２１は、処理対象のツリーノードの親ノードであるツリーノードｐに対応するＴフラグとともに、親ノードの面積を示す画素数Ｎｐを取得することが望ましい。
【０１８５】
次いで、プロセッサ２１は、ステップＳ３２４で取得した親ノードに対応するＴフラグが「１」か否かを判定する(ステップＳ３２５)。このステップＳ３２５の肯定判定ルートにおいて、プロセッサ２１は、以下のステップＳ３２６及びステップＳ３２７の処理を実行する。一方、ステップＳ３２５の否定判定ルートにおいて、プロセッサ２１は、ステップＳ３２６〜ステップＳ３２７の処理をスキップし、ステップＳ３２８の処理に進む。
【０１８６】
ステップＳ３２６の処理において、プロセッサ２１は、ステップＳ３２１で取得した画素数Ｎｊと、ステップＳ３２４で取得した画素数Ｎｐとが、上述した式(４)で示される条件Ｉを満たすか否かを判定する(ステップＳ３２６)。そして、このステップＳ３２６の肯定判定の場合に、プロセッサ２１は、上述した成分テーブル１３１に対して、処理対象のツリーノードに対応するＩフラグに「１」を設定する操作を行う(ステップＳ３２７)。一方、ステップＳ３２６の否定判定の場合に、プロセッサ２１は、ステップｓ３２７の処理をスキップして、ステップＳ３２８の処理に進む。
【０１８７】
ステップＳ３２８において、プロセッサ２１は、ステップＳ３２１で取得したノード番号の集合で示される子ノードの集合に、まだ、属性の判別処理が完了していない子ノードがあるか否かを判定する(ステップＳ３２８)。プロセッサ２１は、処理済でない子ノードがある限り、ステップＳ３２８の肯定判定ルートに従って、ステップＳ３２９とステップＳ３１２とを繰り返し実行する。つまり、プロセッサ２１は、ステップＳ３２９において、子ノードの一つを処理対象のツリーノードとして設定し、ステップＳ３１２の処理であるツリーノードの属性を判別する処理を再帰的に実行する。
【０１８８】
このようにして、成分ツリーＴｒに含まれる全てのツリーノードについて、上述したＴフラグ及びＩフラグを設定する処理が完了したときに、プロセッサ２１は、ステップＳ３２８の否定判定ルートに従ってツリーノードの属性を判別する処理を終了する。その後、プロセッサ２１は、図１８に示したステップＳ３１３の処理に進む。
【０１８９】
このステップＳ３１３において、プロセッサ２１は、再び、ルートノードを処理対象のツリーノードとして選択し、処理対象のツリーノードに対応する代表ノードを判別する処理を行う(ステップＳ３１４)。プロセッサ２１は、図２０，２１に示すように、ステップＳ３１４の処理を、成分ツリーＴｒの親子関係に従って再帰的に実行することにより、成分ツリーＴｒに含まれる各ツリーノードに対応する代表ノードを判別する。
【０１９０】
図２０、図２１は、代表ノードを判別する処理のフローチャートの一例を示している。図２０、図２１に示したステップＳ３３１〜ステップＳ３４２の各処理は、上述した成分ツリーＴｒを縮約する手順に含まれる代表ノードを判別する手順の処理の一例であり、図１８に示したステップＳ３１４の処理に相当する。また、これらのステップＳ３３１〜ステップＳ３４２の各処理は、プロセッサ２１によって実行される。
【０１９１】
まず、プロセッサ２１は、変数ＩＤ＿Ｐおよび戻り値Ｒｅｔ＿ＩＤに、初期値「−１」を設定する(ステップＳ３３１)。次いで、プロセッサ２１は、処理対象のツリーノードの子ノードであって、まだ、代表ノードを選択する処理が完了していないツリーノードがあるか否かを判定する(ステップＳ３３２)。
【０１９２】
未処理の子ノードがある場合に(ステップＳ３３２の否定判定)、プロセッサ２１は、子ノードの一つを処理対象のツリーノードとして選択し(ステップＳ３３３)、次いで、ステップＳ３１４の代表ノードか否かを判別する処理を再帰的に実行する。次いで、プロセッサ２１は、ステップＳ３３４において、子ノードを処理対象として実行したステップＳ３１４の処理で得られた戻り値Ｒｅｔ＿ＩＤの値を上述した変数ＩＤ＿Ｐに設定する。
【０１９３】
その後、プロセッサ２１は、ステップＳ３３４の処理で、この変数ＩＤ＿Ｐの値が初期値「−１」から変更されたか否かを判定する(ステップＳ３３５)。変数ＩＤ＿Ｐの値が初期値「−１」のまま維持されている場合に、プロセッサ２１は、ステップＳ３３５の否定ルートに従ってステップＳ３３２の処理に戻り、次の子ノードについての処理を開始する。
【０１９４】
一方、変数ＩＤ＿Ｐの値が変更されていた場合(ステップＳ３３５の肯定判定)と全ての子ノードについての処理が完了した場合(ステップＳ３３２の否定判定)に、プロセッサ２１は、接続端子１を介して、図２１に示したステップＳ３３６の処理に進む。このステップＳ３３６において、プロセッサ２１は、処理対象のツリーノードに対応するＩフラグに「１」が設定されているか否かを判定する。
【０１９５】
このステップＳ３３６の肯定判定ルートにおいて、プロセッサ２１は、変数ＩＤ＿Ｐの値が初期値「−１」から変更されたか否かに基づいて、子ノードについての処理によって代表ノードを示すノード番号が得られたか否かを判定する(ステップＳ３３７)。このステップＳ３３７の肯定判定の場合に、プロセッサ２１は、処理対象のツリーノードは、親ノードの形状を引き継いでいるツリーノードの系列の中間部分に位置していると判断する。この場合に、プロセッサ２１は、成分テーブル１３１に対して、処理対象のツリーノードに対応するＤフラグに変数ＩＤ＿Ｐの値を設定する操作を行うとともに、戻り値Ｒｅｔ＿ＩＤに変数ＩＤ＿Ｐの値を設定する(ステップＳ３３８)。このステップＳ３３８の処理において、変数ＩＤ＿Ｐの値は、子ノードについての処理で得られた戻り値であり、この戻り値は、代表ノードのノード番号を示している。つまり、プロセッサ２１は、このステップＳ３３８の処理を行うことにより、親ノードの形状を引き継いでいるツリーノードの系列の中間部分に位置するツリーノードに対応するＤフラグに、代表ノードのノード番号を設定する。
【０１９６】
一方、上述したステップＳ３３７の否定判定の場合に、プロセッサ２１は、処理対象のツリーノードは、親ノードの形状を引き継いでいるツリーノードの系列の中で最もルートノードから遠くに位置していると判断する。この場合に、プロセッサ２１は、成分テーブル１３１に対して、処理対象のツリーノードに対応するＤフラグに当該ツリーノードを示すノード番号を設定する操作を行うとともに、戻り値Ｒｅｔ＿ＩＤにこのノード番号を設定する(ステップＳ３３９)。
【０１９７】
一方、上述したステップＳ３３６の否定判定ルートにおいて、プロセッサ２１は、まず、処理対象のツリーノードに対応するＴフラグに「１」が設定されているか否かを判定する(ステップＳ３４０)。
【０１９８】
このステップＳ３４０の肯定判定ルートにおいて、プロセッサ２１は、変数ＩＤ＿Ｐの値が初期値「−１」から変更されたか否かに基づいて、子ノードについての処理によって代表ノードを示すノード番号が得られたか否かを判定する(ステップＳ３４１)。このステップＳ３４１の否定判定とされるツリーノードは、Ｔフラグによって文字を表す可能性があることが示されており、かつ、Ｉフラグにより、親ノードの形状を引き継いでいないことが示されたツリーノードである。ステップＳ３４１の否定判定ルートにおいて、プロセッサ２１は、ステップＳ３４２の処理を実行する。ステップＳ３４２において、プロセッサ２１は、成分テーブル１３１に対して、処理対象のツリーノードに対応するＤフラグに当該ツリーノードを示すノード番号を設定する操作を行うとともに、戻り値Ｒｅｔ＿ＩＤに初期値「−１」を設定する(ステップＳ３４２)。
【０１９９】
一方、上述したステップＳ３４１の肯定判定とされるツリーノードは、形状が類似しているツリーノードの系列の中で最もルートノードの近くに位置しているツリーノードである。ステップＳ３４１の肯定判定ルートにおいて、プロセッサ２１が、ステップＳ３４３の処理を行う場合に、変数ＩＤ＿Ｐの値には、子ノードの処理で得られた代表ノードのノード番号が設定されている。したがって、この場合のステップＳ３４３の処理で、プロセッサ２１は、成分テーブル１３１に対して、処理対象のツリーノードに対応するＤフラグに代表ノードを示す変数ＩＤ＿Ｐの値を設定する操作を行う。また、併せて、プロセッサ２１は、戻り値Ｒｅｔ＿ＩＤに初期値「−１」を設定する。
【０２００】
ところで、上述したステップＳ３４０の否定判定ルートに進む場合に処理対象となっているツリーノードは、上述したＴフラグにより、文字を表す可能性の低いことが示されたツリーノードである。また、この場合に、変数ＩＤ＿Ｐの値は初期値「−１」のまま変更されていない。したがって、ステップＳ３４０の否定判定ルートにおいて、プロセッサ２１は、ステップＳ３４３の処理として、成分テーブル１３１に対して、処理対象のツリーノードに対応するＤフラグに初期値「−１」を設定する操作を行う。プロセッサ２１が、このような操作を行うことにより、当該ツリーノードに対応する代表ノードはない旨を示すことができる。
【０２０１】
このようにして、成分ツリーＴｒのルートノードから親子関係を辿って再帰的に代表ノードを判別する処理を行うことにより、各ツリーノードに対応する代表ノードを示すＤフラグの設定を行うことができる。そして、成分ツリーＴｒに含まれる全てのツリーノードに対応するＤフラグを設定する処理が完了したときに、プロセッサ２１は、代表ノードであるか否かを判別する処理を終了し、図１７に示したステップＳ３０５の認識ラティスＬｔを生成する処理に進む。
【０２０２】
次に、図２２〜図２５を参照しつつ、コンピュータ装置２０による実行に好適な認識ラティスの生成処理について説明する。
図２２は、認識ラティスの生成処理を説明する図である。なお、図２２に示した要素のうち、図２に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０２０３】
図２２に矢印で示したＸ軸は、二値画像Ｐ３，Ｐ４，Ｐ５における各画素の位置の基準であり、図２に示した入力画像Ｐｉｎに含まれる文字列の並び方向におおよそ一致している。また、各二値画像Ｐ３，Ｐ４，Ｐ５の一方の端は、Ｘ座標「０」で示され、他方の端は、Ｘ座標「Ｘｍａｘ」で示される。
【０２０４】
なお、図２２においては、各二値画像Ｐ３，Ｐ４，Ｐ５から抽出された連結成分のうち、上述した成分ツリーＴｒの縮約処理の過程において代表ノードに対応するとされた連結成分のみを表示している。また、図２に示した二値画像Ｐ０，Ｐ１，Ｐ２，Ｐ６のそれぞれは、代表ノードに対応する連結成分を含まないため、図２２においては図示を省略している。
【０２０５】
また、図２２に示す符号Ｒｓは、後述する認識ラティスの生成処理で用いる注目範囲を示す。この注目範囲Ｒｓは、例えば、上述したＸ軸方向に、１文字の横幅程度の幅Ｘｗを持つ帯状の領域である。以下の説明では、この注目範囲Ｒｓの右端の位置をＸ座標「０」からＸ座標「Ｘｍａｘ」に向かって走査させながら、この注目範囲Ｒｓと各連結成分の位置との関係に基づいて、各連結成分に対応するラティスノード間の接続を設定する方法について説明する。
【０２０６】
図２３は、認識ラティスを生成する処理のフローチャートの一例を示している。図２３に示したステップＳ３５１〜ステップＳ３５９の各処理は、ラティス生成プログラムに含まれる認識ラティスを生成する手順を実行するための処理の一例であり、図１７に示したステップＳ３０５の処理に相当する。また、これらのステップＳ３５１〜ステップＳ３５９の各処理は、プロセッサ２１によって実行される。
【０２０７】
プロセッサ２１は、まず、メモリ２２又はハードディスク装置２３に保持された成分テーブル１３１に基づいて、リンクを設定する対象となる各ツリーノードの画像上での位置関係を管理するための位置管理テーブルを作成する(ステップＳ３５１)。このステップＳ３５１において、プロセッサ２１は、成分テーブル１３１を参照することにより、縮約後の成分ツリーに含まれるツリーノードに関する情報を取得する。また、プロセッサ２１は、成分テーブル１３１から取得した情報に基づいて、これらのツリーノードについての位置管理テーブルを作成する。
【０２０８】
図２４は、位置管理テーブルを作成する処理を説明する図である。なお、図２４に示した要素のうち、図２に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０２０９】
図２４(Ａ)は、二値画像Ｐ４に含まれる連結成分のうち、縮約後の成分ツリーに含まれるツリーノードに対応する連結成分と、これらの連結成分に対応する外接矩形とについて、Ｘ軸方向の配置を示している。
【０２１０】
図２４(Ａ)において、ツリーノード１４に対応する連結成分Ｃ４−１の外接矩形Ｒ４−１の頂点のＸ座標Ｘ１４ｕおよびＸ座標Ｘ１４ｄは、この連結成分Ｃ４−１のＸ軸方向の範囲の始点および終点を示している。同様に、ツリーノード１６に対応する連結成分Ｃ４−３の外接矩形Ｒ４−３頂点のＸ座標Ｘ１６ｕおよびＸ座標Ｘ１６ｄは、この連結成分Ｃ４−３のＸ軸方向の範囲の始点及び終点を示している。また、ツリーノード１７に対応する連結成分Ｃ４−４の外接矩形Ｒ４−４の頂点のＸ座標Ｘ１７ｕおよびＸ座標Ｘ１７ｄは、この連結成分Ｃ４−４のＸ軸方向の範囲の始点及び終点を示している。同様に、ツリーノード１８に対応する連結成分Ｃ４−５の外接矩形Ｒ４−５の頂点のＸ座標Ｘ１８ｕおよびＸ座標Ｘ１８ｄは、この連結成分Ｃ４−５のＸ軸方向の範囲の始点及び終点を示している。そして、ツリーノード１９に対応する連結成分Ｃ４−６の外接矩形Ｒ４−６の頂点のＸ座標Ｘ１９ｕおよびＸ座標Ｘ１９ｄは、この連結成分Ｃ４−６のＸ軸方向の範囲の始点及び終点を示している。
【０２１１】
したがって、プロセッサ２１は、例えば、各ツリーノードに対応して成分テーブル１３１に含まれる外接矩形の頂点の座標を示す情報に基づいて、これらのツリーノードに対応する連結成分のＸ軸方向の範囲の始点及び終点を特定することができる。そして、プロセッサ２１は、このようにして特定した始点及び終点を、図２４(Ｂ)に示すような位置管理テーブルに登録することが望ましい。
【０２１２】
図２４(Ｂ)に示した位置管理テーブルは、例えば、Ｘ座標「０」からＸ座標「Ｘｍａｘ」までの各Ｘ座標に対応して、当該Ｘ座標を範囲の始点あるいは終点とする連結成分に対応するツリーノードの集合を示す情報を含んでいる。なお、ツリーノードの集合を示す情報は、当該ツリーノードの集合に含まれるノードの個数及び各ツリーノードを示すノード番号を示す情報を含むことが望ましい。
【０２１３】
プロセッサ２１は、図２３に示したステップＳ３５１において、縮約後の成分ツリーに含まれる各ツリーノードに対応して取得した情報に基づいて、これらのツリーノードの始点及び終点を順次に登録していくことにより、位置管理テーブルを作成する。プロセッサ２１は、このようにして作成した位置管理テーブルを、メモリ２２あるいはハードディスク装置２３に格納しておくことが望ましい。
【０２１４】
このようにして位置管理テーブルの作成を完了した後に、図２３に示したステップＳ３５２において、プロセッサ２１は、図２２に示した注目範囲Ｒｓを初期位置に設定するとともに、注目リストを初期化する。なお、注目リストは、注目範囲Ｒｓに少なくとも一部が含まれている連結成分それぞれに対応するツリーノードの集合である。
【０２１５】
プロセッサ２１は、ステップＳ３５２の処理において、入力画像Ｐｉｎにおいて想定される文字列の並び方向に合わせて、注目範囲Ｒｓの初期位置を設定することが望ましい。例えば、文字列の並び方向が、左から右に向かっていることが想定される場合に、プロセッサ２１は、注目範囲Ｒｓの初期位置として、注目範囲Ｒｓの右端をＸ座標「０」に合わせて設定することが望ましい。なお、以下の説明では、注目範囲Ｒｓの右端の位置を座標Ｘｓで示し、注目範囲Ｒｓの左端の位置を座標Ｘｅで示す。なお、この座標Ｘｅは、右端の座標Ｘｒと注目範囲Ｒｓの幅Ｘｗを用いて、座標(Ｘｒ−Ｘｗ)のように表すこともできる。
【０２１６】
次いで、プロセッサ２１は、上述した座標Ｘｓ、Ｘｅに基づいて、メモリ２２又はハードディスク装置２３に格納された位置管理テーブルを参照することで、注目リストの更新に用いる情報を取得する(ステップＳ３５３)。このステップＳ３５３において、プロセッサ２１は、位置管理テーブルから、座標Ｘｓを始点とする連結成分に対応するツリーノードの個数及びノード番号の集合を、新たに注目リストに追加すべきツリーノードを示す情報として取得することが望ましい。併せて、プロセッサ２１は、位置管理テーブルから、座標Ｘｅを終点とする連結成分に対応するツリーノードの個数及びノード番号の集合を、注目リストから削除すべきツリーノードを示す情報として取得することが望ましい。
【０２１７】
次に、プロセッサ２１は、上述したステップＳ３５３で取得した座標Ｘｅを終点とする連結成分に対応するツリーノードの集合に含まれる各ツリーノードを示すノード番号を、注目リストから削除する(ステップＳ３５４)。
【０２１８】
その後、プロセッサ２１は、上述したステップＳ３５３で取得した座標Ｘｓを始点とする連結成分に対応するツリーノードの集合に含まれる各ツリーノードについて、新たなラティスノードをラティステーブル１５に登録する(ステップＳ３５５)。ステップＳ３５５において、プロセッサ２１は、例えば、新たなラティスノードそれぞれに一意のノード番号を付与する。そして、プロセッサ２１は、このノード番号に対応して、当該ノード番号が付与された新たなラティスノードに対応する情報を、メモリ２２又はハードディスク装置２３に設けられたラティステーブル１５に登録する。
【０２１９】
例えば、注目範囲Ｒｓが図２２に示した連結成分Ｃ４−１の始点に対応するＸ座標Ｘ１４ｕまで移動したときに、プロセッサ２１は、ステップＳ３５３において、この連結成分Ｃ４−１に対応するツリーノード１４を取得する。そして、プロセッサ２１は、ステップＳ３５５において、このツリーノード１４に、認識ラティスＬｔにおけるノード番号１を付与し、ノード番号１を持つ新規のラティスノードとして、ラティステーブル１５に登録する。このとき、プロセッサ２１は、ノード番号１のラティスノード１に対応する包含するツリーノードとして、上述したツリーノード１４を示すノード番号１４をラティステーブル１５に格納することにより、ラティスノード１とツリーノード１４との関係を示す。
【０２２０】
次いで、プロセッサ２１は、注目範囲内に少なくとも一部が含まれる連結成分に対応するラティスノードについてリンクを設定する処理として、図２５に示す各ステップを含む処理を実行する(ステップＳ３５６)。
【０２２１】
図２５は、リンクを設定する処理のフローチャートの一例を示している。図２５に示したステップＳ３６１〜ステップＳ３６７の各処理は、ラティス生成プログラムに含まれるリンクを設定する手順を実行するための処理の一例であり、図２３に示したステップＳ３５６の処理に相当する。また、これらのステップＳ３６１〜ステップＳ３６７の各処理は、プロセッサ２１によって実行される。
【０２２２】
まず、プロセッサ２１は、図２３のステップＳ３５３の処理で新たに注目範囲Ｒｓに入った連結成分を示す情報として取得したツリーノードの集合の中に、まだ、後述する処理の対象となっていない未処理のツリーノードがあるか否かを判定する(ステップＳ３６１)。
【０２２３】
このステップＳ３６１の肯定判定ルートにおいて、プロセッサ２１は、まず、新たに注目範囲Ｒｓに入った連結成分に対応するツリーノードの集合の中から、未処理のツリーノードを選択する(ステップＳ３６２)。次いで、プロセッサ２１は、注目リストの中に、ステップＳ３６２で選択したツリーノードに対応する新規のラティスノードへのリンク元の候補として、まだ選択されていない未選択のツリーノードがあるか否かを判定する(ステップＳ３６３)。
【０２２４】
このステップＳ３６３の肯定判定ルートにおいて、プロセッサ２１は、注目リストに含まれるツリーノードであって、未選択のツリーノードの一つを選択する(ステップＳ３６４)。次いで、プロセッサ２１は、注目リストから選択したツリーノードに対応する連結成分と上述したステップＳ３６２で選択したツリーノードに対応する連結成分とが、上述した接続条件を満たすか否かを判定する(ステップＳ３６５)。ステップＳ３６５において、プロセッサ２１は、上述した２つのツリーノードのそれぞれに対応して成分テーブル１３１に格納された外接矩形の頂点の座標が上述した式(１)で示される条件を満たすか否かを判定する。また、併せて、プロセッサ２１は、これらのツリーノードに対応して成分テーブル１３１に格納された親ノード番号に基づいて、これらのツリーノード間に親子関係があるか否かを判定する。そして、プロセッサ２１は、上述した２つのツリーノードに対応する外接矩形の頂点の座標が上述した式(１)で示される条件を満たし、かつ、これらのツリーノード間に親子関係が無い場合に、これらのツリーノードは接続条件を満たすと判断する。
【０２２５】
ステップＳ３６５の肯定判定ルートにおいて、プロセッサ２１は、注目リストから選択したツリーノードに対応する既存のラティスノードから上述した新規のラティスノードに向かうリンクを示す情報をラティステーブル１５に登録する(ステップＳ３６６)。このステップＳ３６６において、プロセッサ２１は、ラティステーブル１５に対して、上述した新規のラティスノードに対応する前側リンクノードに、注目リストから選択したツリーノードに対応する既存のラティスノードを示すノード番号を登録する操作を行う。また、この操作とともに、プロセッサ２１は、新規のラティスノードに対応する前側リンク個数を「１」加算する操作をラティステーブル１５に対して実行する。更に、プロセッサ２１は、ラティステーブル１５に対して、注目リストから選択したツリーノードに対応するラティスノードの後側リンクノードに、上述した新規のラティスノードを示すノード番号を追加する操作を行う。また、この操作とともに、プロセッサ２１は、注目リストから選択したツリーノードに対応するラティスノードの後側リンク個数を「１」加算する操作をラティステーブル１５に対して実行する。
【０２２６】
このステップＳ３６６の処理の完了後に、ステップＳ３６５の肯定判定ルートは、ステップＳ３６５の否定判定ルートと合流し、ステップＳ３６３の処理に戻る。このように、プロセッサ２１は、注目リスト内に未選択のツリーノードがある限り、ステップＳ３６３〜ステップＳ３６６の処理を繰り返す。
【０２２７】
その後、注目リスト内の全てのツリーノードに関するステップＳ３６３〜ステップＳ３６６の処理が完了したときに、プロセッサ２１は、ステップＳ３６３の否定判定ルートに従って、ステップＳ３６７の処理に進む。
【０２２８】
このステップＳ３６７において、プロセッサ２１は、ステップＳ３６２で選択したツリーノードを、注目リストに追加した後に、ステップＳ３６１の処理に戻る。このように、プロセッサ２１は、新たに注目範囲Ｒｓに入った連結成分を示すツリーノードの集合の中に未処理のツリーノードがある限り、ステップＳ３６１からステップＳ３６７の処理を繰り返す。
【０２２９】
そして、図２３のステップＳ３５５の処理で登録した新規のラティスノードの全てについての処理が完了したときに、プロセッサ２１は、ステップＳ３６１の否定判定ルートに従って、図２３に示したステップＳ３５７の処理に進む。
【０２３０】
このステップＳ３５７において、プロセッサ２１は、注目範囲Ｒｓの右端の位置を示す座標Ｘｓが上述したＸ座標の最大値「Ｘｍａｘ」に到達したか否かに基づいて、未走査の領域があるか否かを判定する。
【０２３１】
注目範囲Ｒｓの右端の位置を示す座標Ｘｓが上述したＸ座標の最大値「Ｘｍａｘ」未満である場合に、プロセッサ２１は、ステップＳ３５７の肯定判定ルートに従って、ステップＳ３５８の処理に進む。
【０２３２】
このステップＳ３５８において、プロセッサ２１は、例えば、注目範囲Ｒｓの右端の位置を示す座標Ｘｓに「１」を加算することにより、注目範囲Ｒｓを走査方向に従って移動させ、その後、ステップＳ３５３に戻る。
【０２３３】
このように、プロセッサ２１は、注目範囲Ｒｓの右端の位置を示す座標ＸｓがＸ座標の最大値「Ｘｍａｘ」に到達するまで、注目範囲Ｒｓを走査しながら、ステップＳ３５３〜ステップＳ３５７の処理を繰り返す。つまり、この注目範囲Ｒｓを走査していく過程において、プロセッサ２１は、注目範囲Ｒｓに少なくとも一部が含まれる２つの連結成分の組み合わせが上述した接続条件を満たす場合について、それぞれに対応するラティスノードを接続するリンクを設定する。このような処理を、上述した座標ＸｓがＸ座標の最大値「Ｘｍａｘ」に到達するまで繰り返すことで、プロセッサ２１は、図１１に示したような認識ラティスＬｔを表すラティステーブル１５を生成することができる。
【０２３４】
プロセッサ２１は、上述した座標ＸｓがＸ座標の最大値「Ｘｍａｘ」に等しくなったときに(ステップＳ３５７の否定判定)、注目範囲Ｒｓの走査が完了したと判断し、ステップＳ３５９の処理に進む。このステップＳ３５９において、プロセッサ２１は、図２６及び図２７に示す各ステップの処理を実行することにより、上述したようにして生成した認識ラティスＬｔを拡張する処理を行う。
【０２３５】
図２６は、認識ラティスを拡張する処理のフローチャートの一例を示している。図２６に示したステップＳ３７１〜ステップＳ３７６の各処理は、ラティス生成プログラムに含まれる認識ラティスを拡張する手順を実行するための処理の一例であり、図２３に示したステップＳ３５９の処理に相当する。また、これらのステップＳ３７１〜ステップＳ３７６の各処理は、プロセッサ２１によって実行される。
【０２３６】
まず、プロセッサ２１は、処理済みのノード数を示す変数Ｎｊに初期値「０」を設定する(ステップＳ３７１)。次いで、プロセッサ２１は、ラティステーブル１５におけるノード番号順に、ラティスノードの一つを注目ノードとして選択する(ステップＳ３７２)。
【０２３７】
次に、プロセッサ２１は、次に述べるステップＳ３７４の処理が、上述した注目ノードに対応して再帰的に実行された回数を示す変数Ｄｅｐｔｈに初期値「０」を設定する（ステップＳ３７３）。
【０２３８】
次いで、プロセッサ２１は、図２７に示す各ステップの処理を再帰的に実行することにより、上述した注目モードに対応する連結成分を含む拡張された連結成分に対応する拡張ノードを生成する(ステップＳ３７４)。
【０２３９】
図２７は、拡張ノードを生成する処理のフローチャートの一例を示している。図２７に示したステップＳ３８１〜ステップＳ３８９の各処理は、ラティス生成プログラムに含まれる拡張ノードを生成する手順を実行するための処理の一例であり、図２６に示したステップＳ３７４の処理に相当する。また、これらのステップＳ３８１〜ステップＳ３８９の各処理は、プロセッサ２１によって実行される。
【０２４０】
まず、プロセッサ２１は、ステップＳ３８１において、上述した変数Ｄｅｐｔｈに「１」を加算するとともに、図２７に示した処理における変数ｊに初期値「０」を設定する。更に、プロセッサ２１は、このステップＳ３８１においてラティステーブル１５を参照し、注目ノードに関する情報として、注目ノードが包含するツリーノードを示す情報とともに、注目ノードの前側にリンクされているラティスノードを示す情報を取得する。プロセッサ２１は、注目ノードが包含するツリーノードを示す情報として、例えば、ラティステーブル１５に注目ノードに対応して格納されている、ツリーノードを示すノード番号の集合を取得する。また、プロセッサ２１は、注目ノードの前側にリンクされているラティスノードを示す情報として、例えば、注目ノードに対応する前側リンク個数Ｎｕｍ＿Ｐとともに、前側リンクノードとして登録されたラティスノードを示すノード番号の集合を取得する。
【０２４１】
次いで、プロセッサ２１は、上述した変数ｊがステップＳ３８１で取得した前側リンク個数Ｎｕｍ＿Ｐ未満であるか否かを判定する(ステップＳ３８２)。変数ｊが前側リンク個数Ｎｕｍ＿Ｐ未満である場合に(ステップＳ３８２の肯定判定)、プロセッサ２１は、ステップＳ３８１で取得した前側リンクノードの一つを、注目ノードに結合するラティスノードの候補として選択する(ステップＳ３８３)。
【０２４２】
次に、プロセッサ２１は、選択したラティスノードと注目ノードとを結合した場合に得られる新たなラティスノードに対応する拡張された連結成分について、この拡張された連結成分に対応する拡張された外接矩形を求める(ステップＳ３８４)。このステップＳ３８４において、プロセッサ２１は、例えば、選択したラティスノードが包含する各ツリーノードに対応する外接矩形と、注目ノードが包含する各ツリーノードに対応する外接矩形との全てを包含する外接矩形として、拡張された外接矩形Ｒｃを求める。この拡張された外接矩形Ｒｃの頂点の一つの位置を示す座標のＸ成分Ｘｍｉｎは、外接矩形の集合Ｑの要素である各外接矩形の頂点の一つの位置を示す座標のＸ成分Ｘｍｉｎ＿ｋの最小値である。同様に、拡張された外接矩形Ｒｃの上述した頂点の位置を示す座標のＹ成分Ｙｍｉｎは、外接矩形の集合Ｑの要素である各外接矩形の上述した頂点の位置を示す座標のＹ成分Ｙｍｉｎ＿ｋの最小値である。また、拡張された外接矩形Ｒｃのもう一つの頂点の位置を示す座標のＸ成分Ｘｍａｘは、外接矩形の集合Ｑの要素である各外接矩形のもう一つの頂点の位置を示す座標のＸ成分Ｘｍａｘ＿ｋの最大値である。同様に、拡張された外接矩形Ｒｃの上述した頂点の位置を示す座標のＹ成分Ｙｍａｘは、外接矩形の集合Ｑの要素である各外接矩形の上述した頂点の位置を示す座標のＹ成分Ｙｍａｘ＿ｋの最大値である。なお、上述した外接矩形の集合Ｑは、選択したラティスノードが包含する各ツリーノードに対応する外接矩形と、注目ノードが包含する各ツリーノードに対応する外接矩形との全てを含む集合である。
【０２４３】
次に、プロセッサ２１は、上述したようにして求めた拡張された外接矩形Ｒｃの２辺の長さＤｘ，Ｄｙが上述した式(５)を満たすか否かに基づいて、この外接矩形Ｒｃが結合条件を満たすか否かを判定する(ステップＳ３８５)。
【０２４４】
このステップＳ３８５の肯定判定ルートにおいて、プロセッサ２１は、ステップＳ３８３で選択したラティスノードと注目ノードとを結合して得られる拡張ノードを、新規のラティスノードとしてラティステーブル１５に登録する(ステップＳ３８６)。ステップＳ３８６において、プロセッサ２１は、新規のラティスノードに対して、認識ラティスＬｔ内で一意のノード番号を付与する。また、プロセッサ２１は、この新規のラティスノードを特定する情報として、結合された２つのラティスノードに含まれるツリーノードの集合を示す情報とともに、当該ラティスノードにかかわるリンクを表す情報とをラティステーブル１５に登録する。このとき、プロセッサ２１は、ステップＳ３８３で選択したラティスノードに対応してラティステーブル１５に登録された前側リンクノードを、新規のラティスノードの前側リンクノードとしてラティステーブル１５に登録することが望ましい。また、プロセッサ２１は、注目ノードに対応してラティステーブル１５に登録された後側リンクノードを、新規のラティスノードの後側リンクノードとしてラティステーブル１５に登録することが望ましい。
【０２４５】
例えば、プロセッサ２１は、図１０に示したラティステーブル１５においてノード番号３に対応するラティスノードＬｎ３にノード番号２に対応するラティスノードＬｎ２を結合した拡張ノードとして、図２８に示すノード番号１２のラティスノードを追加する。
【０２４６】
図２８は、拡張された認識ラティスを表すラティステーブル１５の例を示している。なお、図２８に示した要素のうち、図１０に示した要素と同等のものについては、同一の符号を付して示し、その説明は省略する。
【０２４７】
プロセッサ２１は、上述した拡張ノードを追加する過程で、２つのラティスノードＬｎ２，Ｌｎ３にそれぞれ対応するツリーノード２１，２２を示す情報を、ノード番号１２に対応する包含するツリーノードとして、ラティステーブル１５に登録する。また、プロセッサ２１は、ラティスノードＬｎ２の前側リンクに関する情報と同一の情報を、ノード番号１２に対応する前側リンクに関する情報として、ラティステーブル１５に登録する。つまり、プロセッサ２１は、図２８に示したように、ノード番号１２に対応して、前側リンク個数「０」及び前側リンクノード「ＮＵＬＬ」をラティステーブル１５に格納する。更に、プロセッサ２１は、ラティスノードＬｎ３の後側リンクに関する情報と同一の情報を、ノード番号１２に対応する後側リンクに関する情報として、ラティステーブル１５に登録する。つまり、プロセッサ２１は、図２８に示したように、ノード番号１２に対応して、後側リンク個数「３」及び後側リンクノード「４，５，６」をラティステーブル１５に格納する。
【０２４８】
このようにして、図２７に示したステップＳ３８６の処理を実行した後に、プロセッサ２１は、ステップＳ３８７の処理に進む。このステップＳ３８７において、プロセッサ２１は、変数Ｄｅｐｔｈが、１つの注目ノードについて拡張ノードを生成する処理を再帰的に実行する回数について予め設定した閾値Ｔｈ＿Ｄ以下であるか否かを判定する。このステップＳ３８７の肯定判定ルートにおいて、プロセッサ２１は、上述した処理で得られた拡張ノードを新たな注目ノードとして選択し(ステップＳ３８８)、この新たな注目ノードについて拡張ノードを生成する処理を再帰的に実行する(ステップＳ３７４)。
【０２４９】
このステップＳ３７４の処理の終了後に、ステップＳ３８７の肯定判定ルートは、上述したステップＳ３８５の否定判定ルート及びステップＳ３８７の否定判定ルートと合流する。これらの各ルートの合流後に、プロセッサ２１は、上述した変数ｊに「１」を加算し(ステップＳ３８９)、ステップＳ３８２の処理に戻る。
【０２５０】
このように、プロセッサ２１は、変数ｊがステップＳ３８１の処理で取得した注目ノードに対応する前側リンク個数Ｎｕｍ＿Ｐとなるまで、ステップＳ３８３〜ステップＳ３８９の処理を繰り返す。そして、ステップＳ３８１の処理で取得した全ての前側リンクノードと注目ノードとについての処理が完了したときに(ステップＳ３８２の否定判定)、プロセッサ２１は、拡張ノードを生成する処理を終了し、図２６に示したステップＳ３７５の処理に進む。
【０２５１】
このステップＳ３７５において、プロセッサ２１は、処理済ノード数Ｎｊが拡張前のラティステーブル１５に登録されていたラティスノードの総数ＮｕｍＬ未満であるか否かを判定する。そして、このステップＳ３７５の肯定判定ルートにおいて、プロセッサ２１は、処理済ノード数Ｎｊに「１」を加算し(ステップＳ３７６)、その後、ステップＳ３７２の処理に戻る。つまり、プロセッサ２１は、処理済ノード数Ｎｊが拡張前のラティステーブル１５に登録されていたラティスノードの総数ＮｕｍＬ未満である限り、上述したステップＳ３７２〜ステップＳ３７６の処理を繰り返す。そして、拡張前のラティステーブル１５に登録されていた全てのラティスノードについての処理が完了したときに、プロセッサ２１は、ステップＳ３７５の否定判定ルートに従って、図１７に示したステップＳ３０６の処理に進む。
【０２５２】
このように、プロセッサ２１が、認識ラティスを生成する処理の過程において、認識ラティスを拡張する処理を実行することにより、複数の連結成分の組み合わせで表される候補文字に対応するラティスノードを含む認識ラティスを生成することができる。
【０２５３】
この機能は、入力画像Ｐｉｎに含まれる文字列が、漢字のように複数の連結成分の組み合わせで表される文字を含んでいる場合に、有用性が高い。また、上述したように、プロセッサは、縮約後の成分ツリーに含まれるツリーノードに対応するラティスノードについて、対応する連結成分が抽出された二値画像にかかわらず、認識ラティスを拡張する処理を行っている。したがって、図１２を用いて説明したように、文字を形成する複数の部分を表す連結成分が、異なる閾値に対応する二値画像から抽出された場合においても、拡張ノードに対応する連結成分として、上述した複数の部分の全てを含むパターンの再生が可能である。
【０２５４】
つまり、プロセッサ２１が、本件開示の文字認識プログラムに含まれるラティス生成プログラムを実行することにより、入力画像Ｐｉｎに含まれる文字列を認識するために必要十分な候補文字を与えるラティスノードを含む認識ラティスを生成することができる。更に、この認識ラティスは、これらのラティスノードについて、想定可能な接続順序を網羅したリンクを設定しているので、入力画像Ｐｉｎに含まれる文字列である可能性のある全ての候補文字列を網羅的に示すことができる。
【０２５５】
このようにして得られた認識ラティスに含まれる各ラティスノードについて、プロセッサ２１は、図１７に示したステップＳ３０６において、図２９に示す各ステップの処理を含むパターン認識処理を行うことにより、対応する候補文字を取得する。
【０２５６】
図２９は、パターン認識処理のフローチャートの一例を示している。図２９に示したステップＳ３９１〜ステップＳ３９６の各処理は、パターン認識プログラムに含まれる処理の一例であり、図１７に示したステップＳ３０６の処理に相当する。また、これらのステップＳ３９１〜ステップＳ３９６の各処理は、プロセッサ２１によって実行される。
【０２５７】
まず、プロセッサ２１は、ラティステーブル１５に登録されたラティスノードの一つを順に認識対象のラティスノードとして選択するとともに(ステップＳ３９１)、認識対象のパターンを初期化する(ステップＳ３９２)。
【０２５８】
次いで、プロセッサ２１は、ラティステーブル１５を参照することにより、認識対象のラティスノードが包含するツリーノードを示す情報として、ツリーノードを示すノード番号の集合を取得する(ステップＳ３９３)。
【０２５９】
次に、プロセッサ２１は、ステップＳ３９３で取得したノード番号の集合で示される各ツリーノードについて、成分ツリーＴｒと識別子画像１３２とに基づいて、それぞれの連結成分を再生することにより、認識対象のパターンを再生する(ステップＳ３９４)。
【０２６０】
次いで、プロセッサ２１は、ステップＳ３９４の処理で再生したパターンについて文字認識を実行することにより、認識対象のラティスノードに対応する候補文字を取得するとともに、当該候補文字に関する確信度を取得する(ステップＳ３９５)。
【０２６１】
その後、プロセッサ２１は、認識ラティスＬｔに含まれる全てのラティスノードについての処理が完了したか否かを判定する(ステップＳ３９６)。まだ、認識対象となっていないラティスノードがある場合に、プロセッサ２１は、このステップＳ３９６の否定判定ルートに従って、ステップＳ３９１の処理に戻り、新たなラティスノードを認識対象として選択する。このようにして、プロセッサ２１は、認識対象となっていないラティスノードがある限り、上述したステップＳ３９１からステップＳ３９６の処理を繰り返す。
【０２６２】
そして、全てのラティスノードに対応する候補文字の取得が完了したときに、プロセッサ２１は、ステップＳ３９６の肯定判定ルートに従って、図１７に示したステップＳ３０７の処理に進む。
【０２６３】
このステップＳ３０７において、プロセッサ２１は、評価プログラムに従う評価処理を行うことにより、上述した認識ラティスＬｔで示される各候補文字列の中から、最も確からしい候補文字列を特定し、特定した候補文字列を文字認識処理結果として出力する。このステップＳ３０７の処理において、プロセッサ２１は、例えば、上述した認識ラティスＬｔとステップＳ３０６の処理で得られた各候補文字の確信度とを用いて、動的計画法に基づく評価処理を行うことにより、最も確からしい候補文字列を特定する。
【０２６４】
上述したように、ステップＳ３０７の処理に渡される認識ラティスは、ステップＳ３０４の成分ツリーを縮約する処理と、図２６に示した認識ラティスを拡張する処理を含む、ステップＳ３０５の認識ラティスの生成処理を経て生成されている。
【０２６５】
このようにして生成された認識ラティスは、必要十分な候補文字に対応するラティスノードを含んでおり、これらのラティスノードについて設定されたリンクにより、必要十分な候補文字列を網羅的に示している。
【０２６６】
したがって、プロセッサ２１は、上述したステップＳ３０７の処理によって特定した最も確からしい候補文字列として、入力画像Ｐｉｎに含まれる文字列に対する認識結果を、高い精度で取得することができる。
【０２６７】
つまり、プロセッサ２１が、メモリ２２とハードディスク装置２３及び周辺機器インタフェース２７と協働しつつ、本件開示の文字認識プログラムを実行することにより、入力画像Ｐｉｎに含まれる文字列を高い精度で認識することが可能である。
【０２６８】
以上の説明に関して、更に、以下の各項を開示する。
(付記１)
グレースケールで表現された入力画像を複数の閾値を用いてそれぞれ二値化することにより、複数の二値画像を生成する二値化部と、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出し、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成する探索部と、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成する生成部と、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を得る認識部と、
前記認識部で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する評価部と
を備えたことを特徴とする文字認識装置。
(付記２)
付記１に記載の文字認識装置において、
前記生成部は、
前記認識ラティスの生成に先立って、前記成分ツリーにおいて親子関係を有することが示されている連結成分の組のうち、形状が互いに類似している連結成分の組を検出し、検出した連結成分の組を一つの連結成分に縮約する縮約部を有する
ことを特徴とする文字認識装置。
(付記３)
付記２に記載の文字認識装置において、
前記縮約部は、前記成分ツリーにおいて親子関係を有することが示された２つの連結成分それぞれが含む画素数の比が所定の範囲内である場合に、当該２つの連結成分の組を形状が互いに類似している親子関係を有する連結成分の組として検出する
ことを特徴とする文字認識装置。
(付記４)
付記１又は付記２に記載の文字認識装置において、
前記生成部は、
前記認識ラティスによって接続が設定された各連結成分と当該連結成分を含む所定の大きさの領域内に含まれる別の連結成分とを結合することで新たな連結成分を生成し、生成した新たな連結成分を前記認識ラティスに追加することにより、前記認識ラティスを拡張する拡張部とを有する
ことを特徴とする文字認識装置。
(付記５)
付記１ないし付記３のいずれか一項に記載の文字認識装置において、
前記生成部は、
前記成分ツリーに含まれる複数の連結成分の中から、文字を表す可能性がある連結成分を検出し、検出した連結成分を前記認識ラティスにおいて接続を設定する対象として選択する選択部を有する
ことを特徴とする文字認識装置。
(付記６)
付記５に記載の文字認識装置において、
前記選択部は、
前記連結成分が外接する矩形の大きさが所定の範囲内である連結成分を、文字を表す可能性がある連結成分として検出する
ことを特徴とする文字認識装置。
(付記７)
付記５に記載の文字認識装置において、
前記選択部は、
前記連結成分の外周の長さを示す画素数と前記連結成分が含む画素数との比が所定の範囲内である場合に、当該連結成分は文字を表す可能性がある連結成分として検出する
ことを特徴とする文字認識装置。
(付記８)
付記１ないし付記７に記載の文字認識装置において、
前記探索部によって生成される成分ツリーは、
前記各連結成分を特定する識別子に対応して、当該連結成分と当該連結成分が抽出された二値画像に対応する閾値に隣接する閾値で前記入力画像を二値化することで得られた二値画像からそれぞれ抽出された他の連結成分との包含関係を示す情報を保持する成分テーブルと、
前記各連結成分に含まれる画素のうち、前記成分テーブルによって当該連結成分に包含されることが示された連結成分に含まれない画素に対応して、当該連結成分の識別子を示す数値を保持する識別子画像とを有する
ことを特徴とする文字認識装置。
(付記９)
コンピュータが、
グレースケールで表現された入力画像を複数の閾値を用いて二値化することにより、複数の二値画像を生成し、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、
前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する
ことを特徴とする文字認識方法。
(付記１０)
付記９に記載の文字認識方法において、
コンピュータが、
前記認識ラティスを生成する処理に先立って、
前記成分ツリーにおいて親子関係を有することが示されている連結成分の組のうち、形状が互いに類似している連結成分の組を検出し、検出した連結成分の組を一つの連結成分に縮約する
ことを特徴とする文字認識方法。
(付記１１)
グレースケールで表現された入力画像を複数の閾値を用いて二値化することにより、複数の二値画像を生成し、
前記複数の二値画像からそれぞれ複数の黒画素が連結したパターンを連結成分として抽出するとともに、抽出した個々の連結成分について、他の連結成分との包含関係を探索することにより、各連結成分の包含関係を示す成分ツリーを生成し、
前記各連結成分について、前記入力画像における当該連結成分からの距離が所定値以下である別の連結成分であって、かつ、前記成分ツリーによって包含関係を持たないことが示されている連結成分を検出し、当該連結成分と前記検出した連結成分との並び順をそれぞれ設定することにより、前記各連結成分に対応する候補文字の並び順を網羅的に示すラティスである認識ラティスを生成し、
前記認識ラティスによって接続が示された連結成分ごとに文字認識を行うことにより、当該連結成分に類似する文字を示す候補文字と当該連結成分が前記候補文字を表す可能性の高さを示す確信度とを含む認識結果を取得し、
前記文字認識で得られた各連結成分についての認識結果に基づいて、前記認識ラティスにおける連結成分間の接続する順序の組み合わせで示される各候補文字列が前記入力画像に含まれる文字列である可能性の高さをそれぞれ評価する
処理をコンピュータに実行させることを特徴とする文字認識プログラム。
(付記１２)
付記１１に記載の文字認識プログラムにおいて、
前記認識ラティスを生成する処理に先立って、
前記成分ツリーにおいて親子関係を有することが示されている連結成分の組のうち、形状が互いに類似している連結成分の組を検出し、検出した連結成分の組を一つの連結成分に縮約する
処理をコンピュータに実行させることを特徴とする文字認識プログラム。
【符号の説明】
【０２６９】
１…グレースケール変換装置；２…画像入力装置；１０…文字認識装置；１１…二値化部；１２…探索部；１４…生成部；１５…ラティステーブル；１６…認識部；１７…評価部；１３１…成分テーブル；１３２…識別子画像；１４１…選択部；１４２…縮約部；１４３…リンク生成部；１４４…拡張部；２０…コンピュータ装置；２１…プロセッサ；２２…メモリ；２３…ハードディスク装置(ＨＤＤ)；２４…表示装置；２５…入力装置；２６…光学ドライブ装置；２７…周辺機器インタフェース；２８…ネットワークインタフェース；２９…リムーバブルディスクＰｉｎ…入力画像；Ｐｃｔ…カラー画像；Ｐ０，Ｐ１，Ｐ２，Ｐ３，Ｐ４，Ｐ５，Ｐ６、Ｐ１〜Ｐｍ…二値画像；Ｔｒ…成分ツリー；Ｌｔ…認識ラティス；ＮＷ…ネットワーク
【図１】
2013175084.tif 000003
【図３】
2013175084.tif 000004
【図４】
2013175084.tif 000005
【図６】
2013175084.tif 000006
【図７】
2013175084.tif 000007
【図９】
2013175084.tif 000008
【図１０】
2013175084.tif 000009
【図１１】
2013175084.tif 000010
【図１３】
2013175084.tif 000011
【図１４】
2013175084.tif 000012
【図１５】
2013175084.tif 000013
【図１６】
2013175084.tif 000014
【図１７】
2013175084.tif 000015
【図１８】
2013175084.tif 000016
【図１９】
2013175084.tif 000017
【図２０】
2013175084.tif 000018
【図２１】
2013175084.tif 000019
【図２３】
2013175084.tif 000020
【図２５】
2013175084.tif 000021
【図２６】
2013175084.tif 000022
【図２７】
2013175084.tif 000023
【図２８】
2013175084.tif 000024
【図２９】
2013175084.tif 000025
【図２】
2013175084.tif 000026
【図５】
2013175084.tif 000027
【図８】
2013175084.tif 000028
【図１２】
2013175084.tif 000029
【図２２】
2013175084.tif 000030
【図２４】
2013175084.tif 000031