(57)【要約】【課題】認識対象の文字を入力する仕組みに制約がなく、高精度に文字を認識できる文字認識方法等を提供する。【解決手段】文字認識装置１は、認識対象画像を入力し（Ｓ１０１）、ストローク部品への分割処理を実行し（Ｓ１０２）、ストローク部品の集合から、認識対象スカラー値に変換し（Ｓ１０３）、辞書データベース３を参照して認識対象スカラー値と一致する辞書スカラー値を検索する（Ｓ１０４）。辞書スカラー値３３は、全体構成を示すスカラー値、ストローク部品ごとの要素種別を示すスカラー値、交差ノードの数を示すスカラー値、交差ノードとストローク部品のリンクを示すスカラー値などを有する。【選択図】図４
2012185688.tif 000002
【特許請求の範囲】
【請求項１】
辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベース、を有するコンピュータが実行する文字認識方法であって、
認識対象画像を入力する入力ステップと、
前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割ステップと、
前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換ステップと、
前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定ステップと、
を含み、
前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有することを特徴とする文字認識方法。
【請求項２】
前記判定ステップは、前記第２スカラー値のみを比較することによって、前記認識対象画像の文字種別を判定する第１判定ステップ、を含むことを特徴とする請求項１に記載の文字認識方法。
【請求項３】
前記判定ステップは、前記第１判定ステップによって前記認識対象画像の文字種別が判定できない場合には、更に、前記第２スカラー値及び前記第３スカラー値のみを比較することによって、前記認識対象画像の文字種別を判定する第２判定ステップ、を含むことを特徴とする請求項２に記載の文字認識方法。
【請求項４】
前記分割ステップは、前記認識対象画像を局所的に近似する平行線の組を探索し、前記平行線の組のいずれか一方又は中間線から輪郭部品を決定し、前記輪郭部品同士の接続角度が所定の閾値以内であれば、同一の前記ストローク部品とすることを特徴とする請求項１乃至請求項３のいずれかに記載の文字認識方法。
【請求項５】
前記分割ステップは、前記認識対象画像を局所的に近似する曲線の組を探索し、前記曲線の組のいずれか一方又は中間曲線から輪郭部品を決定し、前記輪郭部品の曲率変化が所定の閾値以内であれば、前記輪郭部品全体を同一の前記ストローク部品とし、更に、前記輪郭部品同士の接続角度が所定の閾値以内であれば、同一の前記ストローク部品とすることを特徴とする請求項１乃至請求項３のいずれかに記載の文字認識方法。
【請求項６】
前記ストローク部品ごとの要素種別は、文字の閉領域を示す輪郭線である孔、文字の端部を示す点である端点を結ぶ線である単独エッジ、複数の前記孔及び／又は前記単独エッジが結ばれる点である分岐点、並びに、前記交差ノードの位置が特定されてテンプレート化されている縮退を含むことを特徴とする請求項１乃至請求項５のいずれかに記載の文字認識方法。
【請求項７】
前記スカラー値は、更に、前記端点の角度情報を示す第５スカラー値を有することを特徴とする請求項６に記載の文字認識方法。
【請求項８】
前記認識対象画像に基づいて認識対象のグラフである認識対象グラフを作成する作成ステップ、
を更に含み、
前記グラフの構成要素であるグラフ要素は、前記孔、前記端点、前記分岐点、複数の前記端点及び／又は前記分岐点を結ぶ線であるエッジ、並びに、前記孔同士の隣接関係を示す線である隣接線が定義されており、
前記作成ステップは、前記認識対象画像の隙間の埋立処理を実行し、連結領域に分離し、更に、連結領域ごとに、前記孔の探索、前記隣接線の探索、複数の前記孔を包含する包含孔の探索、前記端点の探索、前記端点から伸びる前記エッジの探索、前記分岐点の探索、前記認識対象画像の文字領域としては連結しているが、前記グラフ要素としては接続されていない非接続部のエッジ化、の順に処理を実行し、前記認識対象グラフの前記グラフ要素を設定し、
前記変換ステップは、前記認識対象グラフから前記認識対象スカラー値に変換し、
前記判定ステップは、前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定することを特徴とする請求項６に記載の文字認識方法。
【請求項９】
辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベースと、
認識対象画像を入力する入力手段と、
前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割手段と、
前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換手段と、
前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定手段と、
を具備し、
前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有することを特徴とする文字認識装置。
【請求項１０】
コンピュータを、
辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベースと、
認識対象画像を入力する入力手段と、
前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割手段と、
前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換手段と、
前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定手段と、
を具備し、
前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有する
文字認識装置として機能させるためのコンピュータ読取可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グラフ理論を応用し、文字を認識する文字認識方法等に関するものである。
【背景技術】
【０００２】
グラフ理論は、数学の一分野であり、様々な分野に応用されている。ここで、グラフとは、ノード（節点、頂点：ｎｏｄｅ）とエッジ（枝、辺：ｅｄｇｅ）の集合などによって構成される。グラフ理論では、分析対象の要素（ノード）の大きさや要素間（エッジ）の長さよりも、要素同士の繋がり方（ノードの接続態様）に着目する。
尚、グラフ理論における用語の定義は、文献によって様々ではあるが、本明細書では、非特許文献１における定義を参考にする。
【０００３】
従来から、グラフ理論を応用し、文字を認識する手法が開発されている。
例えば、特許文献１では、オンライン手書き文字認識の技術が記載されている。オンライン手書き文字認識とは、カメラなどが内蔵されているペン（デジタルペン）を用い、デジタルペンによる紙の上の運筆を検出することによって、時間の経過による筆跡の変化データを取得し、文字を認識するものである。
グラフ理論の応用箇所について着目すると、特許文献１では、筆跡の変化データに基づいてノード間の方向を算出することにより、いわゆる「有向グラフ」を定義し、文字を認識する。
【０００４】
また、例えば、特許文献２では、申込書やアンケートの選択肢欄のように、印刷されている文字列や番号（「１．配偶者」、「２．子供」など）を直接手書きによってマークさせるような場合の文字認識の技術が記載されている。すなわち、印刷文字に手書きマークが重畳しているときに、印刷文字を高精度に認識する技術が記載されている。特許文献２では、入力画像を複数の「部分入力画像」に分割し、加重方向指数ヒストグラム法を適用し、「部分入力画像」の特徴量を算出する。そして、特徴量が定義されている「部分文字画像」を複数記憶する検索テーブルを参照し、各「部分入力画像」について特徴量が類似する「部分文字画像」を検索する。
ここで、グラフ理論の応用箇所について着目すると、「部分入力画像」のうち、同一の文字種別の「部分文字画像」に類似する「部分入力画像」をノードとし、各ノードに対応する「部分文字画像」間の相対位置関係と、各ノードに対応する「部分入力画像」間の相対位置関係とが矛盾しないノード間を接続してグラフを作成し、作成したグラフから完全部分グラフである「クリーク」を文字候補として抽出する。
尚、一般に、グラフＧの部分グラフとは、そのノードが全てＶ（Ｇ）（Ｇのノード集合）に属し、そのエッジが全てＥ（Ｇ）（Ｇのエッジ集合）に属すグラフである。また、一般に、完全グラフとは、相異なる２個のノードが全て隣接している（エッジによって結ばれている）単純グラフである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−４６８２５号公報
【特許文献２】特開２００９−４３１０２号公報
【非特許文献】
【０００６】
【非特許文献１】Ｒ．Ｊ．ウィルソン著  西関隆夫・西関裕子共訳  「グラフ理論入門（原著第４版」近代科学社  ２００１年１１月初版発行
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１及び特許文献２を含めて従来技術では、十分な認識精度が達成できていない。
特に、オンライン手書き文字認識の場合、及び、手書きによって紙に記入済みの文字（特許文献１に記載するところの「オフライン文字」）をスキャナなどで読み込み、読み込んだ画像（いわゆる「ラスター画像」）内の文字を認識する場合（オフライン手書き文字認識の場合）、の両方において、高精度に文字を認識できるものはない。
【０００８】
本発明は、前述した問題点に鑑みてなされたもので、その目的とすることは、認識対象の文字を入力する仕組みに制約がなく、高精度に文字を認識できる文字認識方法等を提供することである。
【課題を解決するための手段】
【０００９】
前述した目的を達成するために第１の発明は、辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベース、を有するコンピュータが実行する文字認識方法であって、認識対象画像を入力する入力ステップと、前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割ステップと、前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換ステップと、前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定ステップと、を含み、前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有することを特徴とする文字認識方法である。
第１の発明の文字認識方法は、認識対象の文字を入力する仕組みに制約がなく、高精度に文字を認識できる。
【００１０】
第１の発明における前記判定ステップは、前記第２スカラー値のみを比較することによって、前記認識対象画像の文字種別を判定する第１判定ステップ、を含むことが望ましい。
これによって、複雑な文字であっても、一致する辞書スカラー値を特定することができ、判別結果なしの状態を回避することができる。
【００１１】
また、第１の発明における前記判定ステップは、前記第１判定ステップによって前記認識対象画像の文字種別が判定できない場合には、更に、前記第２スカラー値及び前記第３スカラー値のみを比較することによって、前記認識対象画像の文字種別を判定する第２判定ステップ、を含むことが望ましい。
第２スカラー値のみの比較によって一致する辞書スカラー値を特定できなくても、すなわち、複数の辞書スカラー値が一致した場合であっても、第２判定ステップによる判定を行うことによって、一致する辞書スカラー値を一意に特定することができる。
【００１２】
また、第１の発明における前記分割ステップは、例えば、前記認識対象画像を局所的に近似する平行線の組を探索し、前記平行線の組のいずれか一方又は中間線から輪郭部品を決定し、前記輪郭部品同士の接続角度が所定の閾値以内であれば、同一の前記ストローク部品とする。
これによって、オフライン手書き文字認識であっても、高精度に文字を認識することができる。これは、例えば、直線が多い文字に有効である。
【００１３】
また、第１の発明における前記分割ステップは、前記認識対象画像を局所的に近似する曲線の組を探索し、前記曲線の組のいずれか一方又は中間曲線から輪郭部品を決定し、前記輪郭部品の曲率変化が所定の閾値以内であれば、前記輪郭部品全体を同一の前記ストローク部品とし、更に、前記輪郭部品同士の接続角度が所定の閾値以内であれば、同一の前記ストローク部品とする。
これによって、オフライン手書き文字認識であっても、高精度に文字を認識することができる。これは、例えば、曲線が多い文字に有効である。
【００１４】
また、第１の発明における前記ストローク部品ごとの要素種別は、例えば、文字の閉領域を示す輪郭線である孔、文字の端部を示す点である端点を結ぶ線である単独エッジ、複数の前記孔及び／又は前記単独エッジが結ばれる点である分岐点、並びに、前記交差ノードの位置が特定されてテンプレート化されている縮退を含む。
これによって、各ストローク（筆跡）のグラフ形状も考慮して文字種別が判定されるので、高精度に文字を認識することができる。
【００１５】
また、第１の発明における前記スカラー値は、更に、前記端点の角度情報を示す第５スカラー値を有する。
これによって、文字の端部を示す点である端点の角度情報も考慮して文字種別が判定されるので、高精度に文字を認識することができる。
【００１６】
また、第１の発明における前記認識対象画像に基づいて認識対象のグラフである認識対象グラフを作成する作成ステップ、を更に含み、前記グラフの構成要素であるグラフ要素は、前記孔、前記端点、前記分岐点、複数の前記端点及び／又は前記分岐点を結ぶ線であるエッジ、並びに、前記孔同士の隣接関係を示す線である隣接線が定義されており、前記作成ステップは、前記認識対象画像の隙間の埋立処理を実行し、連結領域に分離し、更に、連結領域ごとに、前記孔の探索、前記隣接線の探索、複数の前記孔を包含する包含孔の探索、前記端点の探索、前記端点から伸びる前記エッジの探索、前記分岐点の探索、前記認識対象画像の文字領域としては連結しているが、前記グラフ要素としては接続されていない非接続部のエッジ化、の順に処理を実行し、前記認識対象グラフの前記グラフ要素を設定し、前記変換ステップは、前記認識対象グラフから前記認識対象スカラー値に変換し、前記判定ステップは、前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定するようにしても良い。
これによって、ストローク部品分割処理に基づく文字種別判定処理によって一致する辞書スカラー値を特定できなくても、別のアプローチによって文字種別判定処理を実行することができるので、判別結果なしの状態を回避することができる。特に、文字全体のグラフ形状を考慮して文字種別が判定されるので、ストローク部品分割処理に基づく文字種別判定処理を補完するアプローチと言える。
【００１７】
第２の発明は、辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベースと、認識対象画像を入力する入力手段と、前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割手段と、前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換手段と、前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定手段と、を具備し、前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有することを特徴とする文字認識装置である。
第２の発明の文字認識装置は、認識対象の文字を入力する仕組みに制約がなく、高精度に文字を認識できる。
【００１８】
第３の発明は、コンピュータを、辞書画像のスカラー値である辞書スカラー値を記憶する辞書データベースと、認識対象画像を入力する入力手段と、前記認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する分割手段と、前記ストローク部品の集合から、前記認識対象画像のスカラー値である認識対象スカラー値に変換する変換手段と、前記辞書データベースを参照して前記認識対象スカラー値と一致する前記辞書スカラー値を検索することによって、前記認識対象画像の文字種別を判定する判定手段と、を具備し、前記スカラー値は、全体構成を示す第１スカラー値、前記ストローク部品ごとの要素種別を示す第２スカラー値、前記ストローク部品同士が交差するノードである交差ノードの数を示す第３スカラー値、及び、前記交差ノードと前記ストローク部品のリンクを示す第４スカラー値を有する文字認識装置として機能させるためのコンピュータ読取可能なプログラムである。
第３の発明のプログラムを汎用のコンピュータにインストールすることによって、第２の発明を得ることができる。
【発明の効果】
【００１９】
本発明により、認識対象の文字を入力する仕組みに制約がなく、高精度に文字を認識できる文字認識方法等を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】文字認識装置１のハードウエア構成図
【図２】グラフ表現に用いる記号を示す図
【図３】辞書データベース３の一例
【図４】文字認識処理の流れを示すフローチャート
【図５】ストローク部品分割処理の流れを示すフローチャート
【図６】第１のストローク部品分割処理を説明する図（１）
【図７】第１のストローク部品分割処理を説明する図（２）
【図８】第２のストローク部品分割処理を説明する図（１）
【図９】第２のストローク部品分割処理を説明する図（２）
【図１０】第１のスカラー値表現の定義を示す図（１）
【図１１】第１のスカラー値表現の定義を示す図（２）
【図１２】第１のスカラー値表現の定義を示す図（３）
【図１３】第１のスカラー値表現の定義を示す図（４）
【図１４】第１のスカラー値表現の定義を示す図（５）
【図１５】第２のスカラー値表現の定義を示す図（１）
【図１６】第２のスカラー値表現の定義を示す図（２）
【図１７】第２のスカラー値表現の定義を示す図（３）
【図１８】第２のスカラー値表現の定義を示す図（４）
【図１９】第２のスカラー値表現の定義を示す図（５）
【図２０】スカラー値変換処理の流れを示すフローチャート
【図２１】スカラー値変換処理を説明する為の認識対象画像「鑑」の一例
【図２２】「鑑」のスカラー値変換処理の変換結果（１）
【図２３】「鑑」のスカラー値変換処理の変換結果（２）
【図２４】「鑑」のスカラー値変換処理の変換結果（３）
【図２５】ストローク部品分割処理に基づく文字種別判定処理の流れを示すフローチャート
【図２６】辞書データベース３ａの一例
【図２７】グラフ作成処理の流れを示すフローチャート
【図２８】「夏」のグラフ作成処理の一例（１）
【図２９】「夏」のグラフ作成処理の一例（２）
【図３０】「夏」のグラフ作成処理の一例（３）
【図３１】第３のスカラー値表現の定義を示す図（１）
【図３２】第３のスカラー値表現の定義を示す図（２）
【図３３】辞書データベース３の構築処理の流れを示すフローチャート
【図３４】端点の角度情報を説明する図
【発明を実施するための形態】
【００２１】
以下図面に基づいて、本発明の実施の形態を詳細に説明する。本発明の実施の形態は、オンライン手書き文字認識及びオフライン手書き文字認識の両方に適用することができる。
【００２２】
＜１．装置構成と用語の定義＞
最初に、図１から図３を参照しながら、装置構成と用語の定義などについて説明する。
図１は、文字認識装置１のハードウエア構成図である。尚、図１のハードウエア構成は一例であり、用途、目的に応じて様々な構成を採ることが可能である。
文字認識装置１は、制御部１１、記憶部１２、メディア入出力部１３、通信制御部１４、入力部１５、表示部１６、周辺機器Ｉ／Ｆ部１７等が、バス１８を介して接続される。
【００２３】
制御部１１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等で構成される。
【００２４】
ＣＰＵは、記憶部１２、ＲＯＭ、記録媒体等に格納されるプログラムをＲＡＭ上のワークメモリ領域に呼び出して実行し、バス１８を介して接続された各装置を駆動制御し、文字認識装置１が行う後述する処理を実現する。
ＲＯＭは、不揮発性メモリであり、コンピュータのブートプログラムやＢＩＯＳ等のプログラム、データ等を恒久的に保持している。
ＲＡＭは、揮発性メモリであり、記憶部１２、ＲＯＭ、記録媒体等からロードしたプログラム、データ等を一時的に保持するとともに、制御部１１が各種処理を行う為に使用するワークエリアを備える。
【００２５】
記憶部１２は、ＨＤＤ（ハードディスクドライブ）であり、制御部１１が実行するプログラム、プログラム実行に必要なデータ、ＯＳ（オペレーティングシステム）等が格納される。プログラムに関しては、ＯＳ（オペレーティングシステム）に相当する制御プログラムや、後述する処理をコンピュータに実行させるためのアプリケーションプログラムが格納されている。
これらの各プログラムコードは、制御部１１により必要に応じて読み出されてＲＡＭに移され、ＣＰＵに読み出されて各種の手段として実行される。
【００２６】
メディア入出力部１３（ドライブ装置）は、データの入出力を行い、例えば、ＣＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）、ＤＶＤドライブ（−ＲＯＭ、−Ｒ、−ＲＷ等）等のメディア入出力装置を有する。
通信制御部１４は、通信制御装置、通信ポート等を有し、コンピュータとネットワーク間の通信を媒介する通信インタフェースであり、ネットワークを介して、他のコンピュータ間との通信制御を行う。ネットワークは、有線、無線を問わない。
【００２７】
入力部１５は、データの入力を行い、例えば、キーボード、マウス等のポインティングデバイス、テンキー等の入力装置を有する。
入力部１５を介して、コンピュータに対して、操作指示、動作指示、データ入力等を行うことができる。
また、オンライン手書き文字認識の場合、文字認識装置１は、例えば、カメラなどが内蔵されているペン（デジタルペン）と接続される（接続形態は有線、無線を問わない。）。この場合、入力部１５は、デジタルペンによる紙の上の運筆を検出することによって、時間の経過による筆跡の変化データを取得し、制御部１１に入力する。
表示部１６は、ＣＲＴモニタ、液晶パネル等のディスプレイ装置、ディスプレイ装置と連携してコンピュータのビデオ機能を実現するための論理回路等（ビデオアダプタ等）を有する。
【００２８】
周辺機器Ｉ／Ｆ（インタフェース）部１７は、コンピュータに周辺機器を接続させるためのポートであり、周辺機器Ｉ／Ｆ部１７を介してコンピュータは周辺機器とのデータの送受信を行う。周辺機器Ｉ／Ｆ部１７は、ＵＳＢやＩＥＥＥ１３９４やＲＳ−２３２Ｃ等で構成されており、通常複数の周辺機器Ｉ／Ｆを有する。周辺機器との接続形態は有線、無線を問わない。例えば、周辺機器Ｉ／Ｆ部１７には、認識対象画像を入力する為のスキャナが接続される。この場合、制御部１１は、デジタルペンに代わりに、スキャナから認識対象画像を入力することになる。
バス１８は、各装置間の制御信号、データ信号等の授受を媒介する経路である。
【００２９】
図２は、グラフ表現に用いる記号を示す図である。本発明の実施の形態では、認識対象画像の文字や、記憶部１２に記憶させておく辞書画像の文字に対して、独自のグラフ表現を定義することにより、文字認識処理を行う。
各画像は、文字認識処理を行う前に２値画像に変換され、「文字領域」と「背景領域」に分けられているものとする。
【００３０】
図２には、グラフを構成する要素（以下、「グラフ要素」という。）として、「端点」、「エッジ」、「分岐点」、「孔」、「隣接線」、「交差ノード」を示す記号が図示されている。また、グラフ作成処理の前処理として実行される埋立処理を示す記号が図示されている。
【００３１】
「端点」は、文字の端部を示す点である。「端点」は、グラフ理論におけるノードの一態様である。
「エッジ」は、「端点」及び「分岐点」などの「ノード」同士を結ぶ線であり、グラフ理論における定義と同様である。
「分岐点」は、複数のグラフ要素が結ばれる点である。「分岐点」は、グラフ理論におけるノードの一態様である。「端点」と「分岐点」との違いとしては、「端点」が１個のグラフ要素（通常は「エッジ」）のみ接続されているのに対し、「分岐点」は複数のグラフ要素（「エッジ」とは限らない。）が接続されることである。
【００３２】
図２に示す使用例２１には、端点２１１、エッジ２１２、分岐点２１３、エッジ２１４、端点２１５が含まれている。エッジ２１２は、端点２１１と分岐点２１３を結んでいる。エッジ２１４は、分岐点２１３と端点２１５を結んでいる。
端点２１１、分岐点２１３及び端点２１５を「ノード」とみなすことにより、使用例２１は、「グラフ」となっている。
【００３３】
「孔」は、文字の閉領域を示す輪郭線である。「孔」は、グラフ理論における「ノード」の一態様である。「孔」は、記号の形状としては、グラフ理論における「ループ」（ｌｏｏｐ）に似ているが、定義は異なる。グラフ理論における「ループ」は、同じ「ノード」を結ぶ「エッジ」のことを意味するが、「孔」は、あくまでも「ノード」の一態様である。このように、本発明の実施の形態では、混乱を避けるために、「ループ」ではなく、「孔」と呼ぶことにしている。
「隣接線」は、「孔」同士の隣接関係を示し、「孔」同士を結ぶ線である。「隣接線」は、グラフ理論における「エッジ」の一態様である。
【００３４】
図２に示す使用例２２には、孔２２１、孔２２２、孔２２３、孔２２４、隣接線２２５、隣接線２２６が含まれている。隣接線２２５は、孔２２２と孔２２３が隣接関係にあることを示している。隣接線２２６は、孔２２３と孔２２４が隣接関係にあることを示している。孔２２１は、複数の「孔」、すなわち孔２２２、孔２２３及び孔２２４を包含している。以下では、このように、複数の「孔」を包含する「孔」を「包含孔」と呼ぶことにする。
【００３５】
「埋立」は、グラフ要素ではなく、後述する埋立処理を説明する為に便宜上定義する記号である。
文字のフォントには、様々な形状が存在する。つまり、同じ文字種別であっても、「明朝体」では連結している箇所が、「行書体」では連結していない。例えば、「口」という文字は、「明朝体」であれば全ての箇所が連結しているが、「行書体」（図３の文字２３１を参照）では２箇所が連結していない。これと同様に、手書きの文字には、無数の形状が存在する。
そこで、本発明の実施の形態では、グラフ作成処理の前に、非連結部分を積極的に連結させる「埋立処理」を実行する。これによって、ひいては、高精度に文字種別を判定することができる。
【００３６】
図２に示す使用例２３には、文字画像２３１と、埋立処理後画像２３２が示されている。埋立処理後画像２３２では、文字画像２３１の２箇所の隙間に相当する位置に、埋立２３３及び埋立２３４が配置され、全ての箇所が連結している。
【００３７】
「交差ノード」は、「ストローク部品」同士が交差するノードである。「交差ノード」は、グラフ理論における「ノード」の一態様である。
「ストローク部品」は、ほぼ１回分の運筆に相当する。但し、文字の画数とストローク部品数は、一致する必要はない。本発明の実施の形態では、後述するストローク部品分割処理に従って、文字画像を複数のストローク部品に分割する。
【００３８】
図３は、辞書データベース３の一例である。辞書データベース３は、文字認識装置１の記憶部１２などに記憶され、後述する文字種別の判定処理において参照される。辞書データベース３には、文字種別３１ごとに、１または複数の辞書画像３２が対応付けられている。また、辞書データベース３には、辞書画像３２ごとに、１または複数の辞書スカラー値３３が対応付けられている。
【００３９】
文字種別３１は、各文字の種別を示すデータであり、例えば、文字コードである。
辞書画像３２は、各文字のフォントの画像データである。
辞書スカラー値３３は、各辞書画像３２に対応するスカラー値である。辞書スカラー値３３は、１の辞書画像３２に基づいて、複数個記憶されていても良い。
辞書スカラー値３３は、図３に示すように、全体構成を示すスカラー値、ストローク部品ごとの要素種別を示すスカラー値、交差ノードの数を示すスカラー値、交差ノードとストローク部品のリンクを示すスカラー値などを有する。各スカラー値の詳細については後述する。
【００４０】
文字認識装置１は、辞書データベース３を記憶部１２などに記憶し、制御部１１が、文字認識処理を実行する。文字認識処理では、制御部１１が、認識対象画像を入力する。次に、制御部１１が、認識対象画像を細線化し、連続性を判定することによって、ストローク部品に分割する。次に、制御部１１が、ストローク部品の集合から、認識対象画像のスカラー値である認識対象スカラー値に変換する。そして、制御部１１が、辞書データベース３を参照して認識対象スカラー値と一致する辞書スカラー値３３を検索することによって、認識対象画像の文字種別を判定する。また、ストローク部品分割処理に基づく文字種別判定処理では辞書スカラー値３３を特定できない場合、制御部１１は、認識対象画像から、認識対象グラフを作成し、認識対象グラフを認識対象スカラー値に変換し、再度、文字種別を判定する。文字認識処理の詳細は後述する。
また、制御部１１は、辞書データベース３の構築処理を実行する。辞書データベース３の構築処理では、制御部１１が、辞書画像３２に基づいてストローク部品に分割し、ストローク部品の集合から、辞書スカラー値３３に変換し、辞書データベース３を構築する。辞書データベース３の構築処理の詳細は後述する。
【００４１】
＜２．文字認識処理の概要＞
次に、図４を参照しながら、文字認識処理の概要について説明する。図４は、文字認識処理の流れを示すフローチャートである。図４では、１個の文字画像を認識対象画像とする処理の流れを示している。
【００４２】
図４に示すように、文字認識装置１の制御部１１は、メディア入出力部１３、通信制御部１４、入力部１５、周辺機器Ｉ／Ｆ部などを介して、認識対象画像を入力する（Ｓ１０１）。ここで、オンライン手書き文字認識の場合、入力部１５は、デジタルペンによる紙の上の運筆を検出することによって、時間の経過による筆跡の変化データを取得し、制御部１１に入力する。
【００４３】
次に、制御部１１は、ストローク部品への分割処理を実行し（Ｓ１０２）、ストローク部品の集合をＲＡＭに記憶する。ストローク部品への分割処理の詳細は後述する。
次に、制御部１１は、ストローク部品の集合から、認識対象スカラー値に変換し（Ｓ１０３）、認識対象スカラー値をＲＡＭに記憶する。スカラー値変換処理の詳細は後述する。
【００４４】
次に、制御部１１は、辞書データベース３を参照して認識対象スカラー値と一致する辞書スカラー値を検索する（Ｓ１０４）。そして、制御部１１は、文字種別の判定を行う（Ｓ１０５）。ストローク部品分割処理に基づく文字種別判定処理の詳細は後述する。
一致する辞書スカラー値が特定できた場合には（Ｓ１０５の「一致」）、制御部１１は、一致する辞書スカラー値と対応付けられている文字種別を、認識対象画像の文字種別とし、処理を終了する。
一致する辞書スカラー値が特定できない場合には（Ｓ１０５の「不一致」）、制御部１１は、Ｓ１０６に進む。
【００４５】
Ｓ１０６では、制御部１１は、認識対象スカラー値の始点（要素順位が１位の要素）を変更し、変換処理を再度実行する。
ここで、要素順位について説明する。「要素」とは、認識対象画像に含まれるストローク部品又はグラフ要素を意味する。まず、最も左の要素を第１要素（始点）とする。また、水平方向の位置が同じ場合、最も上の要素を第１要素（始点）とする。そして、例えば、反時計回りなど所定の順番によって要素順位を設定していく。
始点の変更とは、例えば、反時計回りに、要素順位を１つずつ繰り上げる、又は、繰り下げることを意味する。
このように、始点を変更して変換処理を再度実行することによって、算出される認識対象スカラー値は異なるものとなる。従って、改めて文字種別の判定処理を実行することにより、辞書スカラー値３３を特定できる場合がある。
【００４６】
ここで、Ｓ１０６の技術的意義について説明する。認識対象スカラー値の始点を変更するということは、文字の位置を回転することを意味する。従って、認識対象画像に係る文字が、辞書画像３２に係る文字の位置と比較して回転している場合、始点を変更することにより、辞書スカラー値３３を特定できる。
【００４７】
始点を変更した後、制御部１１は、文字種別の判定を行い、完全に一致する辞書スカラー値３３が特定できた場合（Ｓ１０７の「一致」）、制御部１１は処理を終了する。
完全に一致する辞書スカラー値３３が特定できない場合（Ｓ１０７の「不一致」）、制御部１１はＳ１０８の処理に進む。
【００４８】
Ｓ１０８では、制御部１１は、辞書スカラー値３３の一部を変更する。Ｓ１０８における処理の対象は、認識対象スカラー値と近い辞書スカラー値３３から選択する。
【００４９】
Ｓ１０８の処理は、認識対象画像の文字領域を局所的に拡大または縮小する（拡縮する）処理である。
Ｓ１０８における拡縮処理では、端点やエッジの個数の変更など、比較的小さい拡縮を実現する。Ｓ１０８における拡縮処理では、スカラー値表現を直接変更するので、高速な処理を実現することができる。
【００５０】
拡縮処理を行った後、制御部１１は、文字種別の判定を行い、完全に一致する辞書スカラー値３３が特的できた場合（Ｓ１０９の「一致」）、制御部１１は処理を終了する。
完全に一致する辞書スカラー値３３が特定できない場合（Ｓ１０９の「不一致」）、制御部１１は、認識対象グラフの作成処理を実行し（Ｓ１１０）、Ｓ１０３から処理を繰り返す。グラフ作成処理の詳細は後述する。
以上の通り、文字認識装置１は、文字認識処理を実行する。
【００５１】
＜３．ストローク部品分割処理＞
次に、図５〜図９を参照しながら、ストローク部品分割処理について説明する。図５は、ストローク部品分割処理の流れを示すフローチャートである。図５では、後述する２通りの手法の流れを纏めて表現している。
【００５２】
以下、理解を容易にするために、図６〜図９を合わせて参照しながら、図５に示すストローク部品分割処理の流れを説明する。図６、図７は、第１のストローク部品分割処理を説明する図である。図８、図９は、第２のストローク部品分割処理を説明する図である。図６〜図９における認識対象画像の文字種別は、４桁の数字「５８１３」である。
【００５３】
文字認識装置１の制御部１１は、認識対象画像の輪郭線を抽出する（Ｓ２０１）。輪郭線を抽出する際、制御部１１は、認識対象画像に含まれる孔を積極的に探索する（必要があれば、埋立処理も行う。）。
図６（ａ）及び図８（ａ）は、Ｓ２０１の処理結果である。白の画素が、認識対象画像の輪郭線を示している。図６（ａ）及び図８（ａ）に示すように、「８」の数字には、上下に２つの孔が抽出されている。
孔を積極的に抽出する理由は、一般に、印刷されたデジタルフォントの文字であれば、元々、文字の閉領域（孔）に留意してデザインされており、手書き文字であっても、文字の閉領域（孔）に留意して筆記すると考えられる為、文字種別の判定が精度良くできると考えられるからである。
【００５４】
次に、制御部１１は、第１の手法の場合には平行線の組を探索する。第２の手法の場合には曲線の組を探索する（Ｓ２０２）。
（１）平行線の組の場合
制御部１１は、例えば、抽出された輪郭線の各点において微分値を算出し、隣り合う点の微分値が類似する（微分値の差が所定の閾値以内など。）場合には１つの近似直線とし、更に、文字領域を挟んで対向する近似直線の距離が十分に小さい（距離が所定の閾値以内など。）場合には、平行線の組とする。
また、制御部１１は、例えば、抽出された輪郭線を部分的に分割して近似直線の方程式を算出し、端点を共有する近似直線の方程式の係数が類似する（係数の差が所定の閾値以内など。）場合には１つの近似直線とし、更に、文字領域を挟んで対向する近似直線の距離が十分に小さい場合には、平行線の組とする。
【００５５】
（２）曲線の組の場合
制御部１１は、近似曲線の方程式を予め記憶しておく。近似曲線の方程式は、例えば、円、楕円、Ｎ次（Ｎ≧２）多項式などである。
制御部１１は、例えば、抽出された輪郭線の各点において微分値を算出し、隣り合う点の微分値が類似する（微分値の差が所定の閾値以内など。）場合には１つの近似曲線とし、更に、文字領域を挟んで対向する近似曲線の距離が十分に小さい（距離が所定の閾値以内など。）場合には、曲線の組とする。
また、制御部１１は、例えば、抽出された輪郭線を部分的に分割して近似曲線の方程式を算出し、端点を共有する近似曲線の方程式の係数が類似する（係数の差が所定の閾値以内など。）場合には１つの近似曲線とし、更に、文字領域を挟んで対向する近似曲線の距離が十分に小さい場合には、曲線の組とする。
【００５６】
図６（ｂ）及び図８（ｂ）は、Ｓ２０２の処理結果である。
図６（ｂ）には、平行線の組の集合が図示されている。平行線の組は、両端点を黒丸とする実線として図示されており、互いにほぼ平行な２つの直線である。
図８（ｂ）には、曲線の組の集合が図示されている。曲線の組は、両端点を黒丸とする実線として図示されており、互いにほぼ平行な２つの曲線である。
【００５７】
次に、制御部１１は、第１の手法の場合には平行線の組のいずれか一方又は中間線から輪郭部品を決定する。第２の手法の場合には曲線の組のいずれか一方又は中間線から輪郭部品を決定する（Ｓ２０３）。
制御部１１は、平行線の組に含まれる２つの直線のうち、端点を共有する他の平行線の組に含まれる直線と接続が良い方（端点同士の距離が近い方）、又は、両者の中間線を輪郭部品として決定する。
また、制御部１１は、曲線の組に含まれる２つの曲線のうち、端点を共有する他の曲線の組に含まれる曲線と接続が良い方（端点同士の距離が近い方）、又は、両者の中間線を輪郭部品として決定する。
【００５８】
図６（ｃ）及び図８（ｃ）は、Ｓ２０３の処理結果である。
図６（ｃ）には、平行線の組から決定される輪郭部品の集合が図示されている。輪郭部品は、両端点を黒の菱形とする実線として図示されている。
図８（ｃ）には、曲線の組から決定される輪郭部品の集合が図示されている。輪郭部品は、両端点を黒の菱形とする実線として図示されている。
【００５９】
次に、制御部１１は、第１の手法の場合には輪郭部品同士の接続角度が所定の閾値以内であれば、同一のストローク部品とする。第２手法の場合には輪郭部品の曲率変化が所定の閾値以内であれば、輪郭部品全体を同一のストローク部品とし、更に、輪郭部品同士の接続角度が所定の閾値以内であれば、同一のストローク部品とする（Ｓ２０４）。
【００６０】
図７（ａ）及び図９（ａ）は、Ｓ２０４における判定結果を示している。
図７（ａ）における分割線は、接続角度による判定において、異なるストローク部品として分割される境界を示している。分割線は、点線として図示されている。
図９（ａ）における分割線は、曲率変化及び接続角度による判定において、異なるストローク部品として分割される境界を示している。分割線は、点線として図示されている。
【００６１】
図７（ｂ）及び図９（ｂ）は、Ｓ２０４の処理結果である。
図７（ｂ）及び図９（ｂ）には、ストローク部品の集合が図示されている。ストローク部品は、実線又は点線として図示されている。仮に、ストローク部品を全て直線にて図示すると、ストローク部品の境界が不明瞭となってしまう。そこで、図７（ｂ）及び図９（ｂ）では、実線と点線を交互に用いることによって、ストローク部品の境界を明瞭にしている。従って、実線と点線は、本質的には同じストローク部品を意味する。
【００６２】
前述した図５〜図９は、オフライン手書き文字認識の場合を示している。
オンライン手書き文字認識の場合では、制御部１１は、デジタルペンから入力される情報によって、例えば、デジタルペンが所定の時間よりも長く紙媒体から離間した場合には、異なるストローク部品とすれば良い。
【００６３】
＜４．スカラー値変換処理＞
次に、図１０〜図２４を参照しながら、スカラー値変換処理について説明する。まず、ストローク部品の集合に対するスカラー値表現について説明する。図１０〜図１４は、第１のスカラー値表現の定義を示す図である。図１５〜図１９は、第２のスカラー値表現の定義を示す図である。
【００６４】
第１のスカラー値表現の定義は、以下の通りである。
図１０（ａ）は、全体構成のスカラー値表現の定義を示している。全体構成のスカラー値表現では、ストローク部品の数を設定する。具体的には、第１ビットから第８ビットによって、ストローク部品の数を設定する。
図１０（ｂ）は、要素種別のスカラー値表現の定義を示している。要素種別のスカラー値表現では、ストローク部品の種別及び要素順位を設定する。具体的には、第１ビットから第３２ビットによって、２ビットずつ、各ストローク部品の種別を設定する。ストローク部品種別は、（１）単独エッジ：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。ストローク部品の数は、第１６要素までに限らず、必要な数だけ、記憶領域を増やして繰り返す。
【００６５】
ここで、要素順位について説明する。まず、最も左のストローク部品を第１要素（始点）とする。また、水平方向の位置が同じ場合、最も上のストローク部品を第１要素（始点）とする。そして、例えば、反時計回りに要素順位を設定していく。
また、縮退とは、ある文字の全部又は一部の情報がテンプレート化されたものである。構成要素の部分集合が、既に登録した文字と一致するものは、縮退である可能性があると見做し、優先的に探索を行う。結果として、他の構成要素の認識がうまくいった場合、縮退であるとして認識し、うまくいかなかった場合、縮退ではないものとして認識する。
【００６６】
図１０（ｃ）は、単独エッジのスカラー値表現１の定義を示している。単独エッジのスカラー値表現１では、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
単独エッジのスカラー値表現１は、必要な数（単独エッジの数）だけ、記憶領域を増やして繰り返す。
【００６７】
図１０（ｄ）では、単独エッジのスカラー値表現２の定義を示している。単独エッジのスカラー値表現２では、単独エッジのスカラー値表現１について、第１リンク情報として、相手ストローク部品のインデックス、交差ノードのインデックスを設定する。相手ストローク部品とは、交差ノードにおける交差相手のストローク部品のことである。インデックスとは、ストローク部品や交差ノードを一意に識別する番号である。
具体的には、第１ビットから第８ビットによって、相手ストローク部品のインデックスを設定する。また、第９ビットから第１６ビットによって、交差ノードのインデックスを設定する。
単独エッジのスカラー値表現２は、必要な数（単独エッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
以下、図１０（ｄ）に示すものと同様の定義は、「第１リンク情報の定義」と表記し、重複する説明を省略する。
【００６８】
図１１（ａ）では、分岐点のスカラー値表現１の定義を示している。分岐点のスカラー値表現１では、分岐先のエッジ数、分岐先のエッジの種別及び要素順位を設定する。ここで、分岐点における元側のエッジは、要素順位順に定義していき既に定義されているエッジを意味する。また、分岐点における分岐先のエッジは、元側のエッジを除くエッジを意味する。
具体的には、第１ビットから第４ビットによって、分岐先のエッジ数を設定する。また、第５ビットから第３２ビットによって、２ビットずつ、各エッジの種別を設定する。エッジの種別（小要素種別）は、（１）端点：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。端点の場合、その下位の情報は不要となる。
【００６９】
図１１（ｂ）では、分岐点のスカラー値表現２の定義を示している。分岐点のスカラー値表現２では、元側のエッジに関して、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
分岐点のスカラー値表現２は、必要な数（元側のエッジの数）だけ、記憶領域を増やして繰り返す。
【００７０】
図１１（ｃ）では、分岐点のスカラー値表現３の定義を示している。分岐点のスカラー値表現３では、分岐点のスカラー値表現２について、第１リンク情報の定義を設定する。
分岐点のスカラー値表現３は、必要な数（元側のエッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００７１】
図１１（ｄ）では、分岐点のスカラー値表現４の定義を示している。分岐点のスカラー値表現４では、分岐先のエッジに関して、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
分岐点のスカラー値表現４は、必要な数（分岐先のエッジの数）だけ、記憶領域を増やして繰り返す。
【００７２】
図１１（ｅ）では、分岐点のスカラー値表現５の定義を示している。分岐点のスカラー値表現５では、分岐点のスカラー値表現４について、第１リンク情報の定義を設定する。
分岐点のスカラー値表現５は、必要な数（分岐先のエッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００７３】
図１２（ａ）では、孔のスカラー値表現１の定義を示している。孔のスカラー値表現１では、内部孔数、孔間接続数、内部エッジ数、外部（先の）エッジ数を設定する。
具体的には、第１ビットから第８ビットによって、内部孔数を設定する。また、第９ビットから第１６ビットによって、孔間接続数を設定する。また、第１７ビットから第２４ビットによって、内部エッジ数を設定する。また、第２５ビットから第３２ビットによって、外部（先の）エッジ数を設定する。
【００７４】
図１２（ｂ）では、孔のスカラー値表現２の定義を示している。孔のスカラー値表現２では、孔の外周上に関して、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
孔のスカラー値表現２は、必要な数（孔の数）だけ、記憶領域を増やして繰り返す。
【００７５】
図１２（ｃ）では、孔のスカラー値表現３の定義を示している。孔のスカラー値表現３では、孔のスカラー値表現２について、第１リンク情報の定義を設定する。
孔のスカラー値表現３は、必要な数（孔の外周上における交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００７６】
図１２（ｄ）では、孔のスカラー値表現４の定義を示している。孔のスカラー値表現４では、内部エッジの種別及び要素順位を設定する。具体的には、第１ビットから第３２ビットによって、２ビットずつ、各エッジの種別を設定する。エッジの種別（小要素種別）は、（１）端点：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。端点の場合、その下位の情報は不要となる。
【００７７】
図１３（ａ）では、孔のスカラー値表現５の定義を示している。孔のスカラー値表現５では、内部エッジに関して、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
孔のスカラー値表現５は、必要な数（内部エッジの数）だけ、記憶領域を増やして繰り返す。
【００７８】
図１３（ｂ）では、孔のスカラー値表現６の定義を示している。孔のスカラー値表現６では、孔のスカラー値表現５について、第１リンク情報の定義を設定する。
孔のスカラー値表現６は、必要な数（内部エッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００７９】
図１３（ｃ）では、孔のスカラー値表現７の定義を示している。孔のスカラー値表現７では、外部エッジの種別及び要素順位を設定する。具体的には、第１ビットから第３２ビットによって、２ビットずつ、各エッジの種別を設定する。エッジの種別（小要素種別）は、（１）端点：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。端点の場合、その下位の情報は不要となる。
【００８０】
図１４（ａ）では、孔のスカラー値表現８の定義を示している。孔のスカラー値表現８では、外部エッジに関して、交差ノード数、１つ目の交差ノードの位置、最後の交差ノードの位置を設定する。具体的には、第１ビットから第４ビットによって、交差ノード数を設定する。また、第５ビットによって、１つ目の交差ノードの位置（途中：０、端部：１）を設定する。また、第６ビットによって、最後の交差ノードの位置（途中：０、端部：１）を設定する。
孔のスカラー値表現８は、必要な数（外部エッジの数）だけ、記憶領域を増やして繰り返す。
【００８１】
図１４（ｂ）では、孔のスカラー値表現９の定義を示している。孔のスカラー値表現９では、孔のスカラー値表現８について、第１リンク情報の定義を設定する。
孔のスカラー値表現９は、必要な数（外部エッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００８２】
図１４（ｃ）では、縮退のスカラー値表現の定義を示している。縮退のスカラー値表現では、縮退として登録されているグラフを一意に識別するコード（以下、「縮退登録コード」という。）を設定する。
具体的には、第１ビットから第３２ビットによって、縮退登録コードを設定する。ここでの縮退登録コードは、交差ノードの位置が特定されてテンプレート化されたものである。
【００８３】
第２のスカラー値表現の定義は、以下の通りである。尚、第１のスカラー値表現の定義と一致する部分は、対応関係を示し、重複する説明を省略する。
図１５（ａ）は、交差ノード数のスカラー値表現の定義を示している。交差ノード数のスカラー値表現では、交差ノードの数を設定する。具体的には、第１ビットから第８ビットによって、交差ノードの数を設定する。
図１５（ｂ）は、全体構成のスカラー値表現の定義を示している。図１５（ｂ）は、図１０（ａ）と同様である。
図１５（ｃ）は、要素種別のスカラー値表現の定義を示している。図１５（ｃ）は、図１０（ｂ）と同様である。
【００８４】
図１５（ｄ）は、単独エッジのスカラー値表現１の定義を示している。図１５（ｄ）は、図１０（ｃ）と同様である。
図１５（ｅ）は、単独エッジのスカラー値表現２の定義を示している。単独エッジのスカラー値表現２では、単独エッジのスカラー値表現１について、第２のリンク情報として、リンクされている全ての交差ノードのインデックスを設定する。
具体的には、第１ビットから第８ビットによって、１つ目の交差ノードのインデックスを設定する。また、第９ビットから第１６ビットによって、２つ目の交差ノードのインデックスを設定する。また、第１７ビットから第２４ビットによって、３つ目の交差ノードのインデックスを設定する。また、第２５ビットから第３２ビットによって、４つ目の交差ノードのインデックスを設定する。以下、必要な数（単独エッジにリンクされている交差ノードの数）だけ、記憶領域を増やして繰り返す。
以下、図１５（ｅ）に示すものと同様の定義は、「第２のリンク情報の定義」と表記し、重複する説明を省略する。
【００８５】
図１６（ａ）は、分岐点のスカラー値表現１の定義を示している。図１６（ａ）は、図１１（ａ）と同様である。
図１６（ｂ）は、分岐点のスカラー値表現２の定義を示している。図１６（ｂ）は、図１１（ｂ）と同様である。
図１６（ｃ）は、分岐点のスカラー値表現３の定義を示している。分岐点のスカラー値表現３では、分岐点のスカラー値表現２について、第２リンク情報の定義を設定する。分岐点のスカラー値表現３は、必要な数（元側のエッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
図１６（ｄ）は、分岐点のスカラー値表現４の定義を示している。図１６（ｄ）は、図１１（ｄ）と同様である。
図１６（ｅ）は、分岐点のスカラー値表現５の定義を示している。分岐点のスカラー値表現５では、分岐点のスカラー値表現４について、第２リンク情報の定義を設定する。分岐点のスカラー値表現５は、必要な数（分岐先のエッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
【００８６】
図１７（ａ）は、孔のスカラー値表現１の定義を示している。図１７（ａ）は、図１２（ａ）と同様である。
図１７（ｂ）は、孔のスカラー値表現２の定義を示している。図１７（ｂ）は、図１２（ｂ）と同様である。
図１７（ｃ）は、孔のスカラー値表現３の定義を示している。孔のスカラー値表現３では、孔のスカラー値表現２について、第２リンク情報の定義を設定する。孔のスカラー値表現３は、必要な数（孔の外周上における交差ノードの数）だけ、記憶領域を増やして繰り返す。
図１７（ｄ）は、孔のスカラー値表現４の定義を示している。図１７（ｄ）は、図１２（ｄ）と同様である。
【００８７】
図１８（ａ）は、孔のスカラー値表現５の定義を示している。図１８（ａ）は、図１３（ａ）と同様である。
図１８（ｂ）は、孔のスカラー値表現６の定義を示している。孔のスカラー値表現６では、孔のスカラー値表現５について、第２リンク情報の定義を設定する。孔のスカラー値表現６は、必要な数（内部エッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
図１８（ｃ）は、孔のスカラー値表現７の定義を示している。図１８（ｃ）は、図１３（ｃ）と同様である。
【００８８】
図１９（ａ）は、孔のスカラー値表現８の定義を示している。図１９（ａ）は、図１４（ａ）と同様である。
図１９（ｂ）は、孔のスカラー値表現９の定義を示している。孔のスカラー値表現９では、孔のスカラー値表現８について、第２リンク情報の定義を設定する。孔のスカラー値表現９は、必要な数（外部エッジにおける交差ノードの数）だけ、記憶領域を増やして繰り返す。
図１９（ｃ）は、縮退のスカラー値表現の定義を示している。図１９（ｃ）は、図１４（ｃ）と同様である。
【００８９】
第１のスカラー値表現では、交差ノードを１つずつ分割して表現している。一方、第２のスカラー値表現では、交差ノードを、文字単位（縮退を使う場合は縮退単位）に纏めて表現している。
本発明の実施の形態では、第１のスカラー値表現及び第２のスカラー値表現の両方を適用することが可能である。
また、スカラー値表現は、第１のスカラー値表現、第２のスカラー値表現に限定されるものではなく、全体構成、ストローク部品ごとの要素種別、交差ノードの数、及び、交差ノードとストローク部品のリンクを表現できる範囲内において、適宜変更することができる。
【００９０】
第１のスカラー値表現の例では、図１０（ａ）が全体構成、図１０（ｂ）がストローク部品ごとの要素種別、並びに、図１０（ｃ）〜図１４（ｃ）が交差ノードの数及び交差ノードとストローク部品のリンクを示している。
また、第２のスカラー値表現の例では、図１５（ｂ）が全体構成、図１５（ｃ）がストローク部品ごとの要素種別、図１５（ａ）が交差ノードの数、並びに、図１５（ｄ）〜図１９（ｃ）が交差ノードとストローク部品のリンクを示している。
【００９１】
次に、スカラー値変換処理の詳細について説明する。図２０は、スカラー値変換処理の流れを示すフローチャートである。
以下、理解を容易にするために、図２１〜図２４を合わせて参照しながら、図２０に示すスカラー値変換処理の流れを説明する。図２１は、スカラー値変換処理を説明する為の認識対象画像「鑑」の一例である。図２２〜図２４は、「鑑」のスカラー値変換処理の変換結果である。
以下では、第２のスカラー値表現の定義によってスカラー値に変換する場合について説明する。尚、第１のスカラー値表現の定義によってスカラー値に変換する場合も、同様の考え方によって処理を実行することができる。
【００９２】
図２１（ａ）には、認識対象画像「鑑」が示されている。
図２０に示すように、文字認識装置１の制御部１１は、接続レベルでの分割を行う（Ｓ３０１）。接続レベルでの分割とは、画素が連結しているか否か、または、画素が連結していなくても、離間している距離が小さいか否かなどによって、認識対象画像を複数の領域に分割することである。図２１（ｂ）では、部首単位によって分割されている。また、図２１（ｃ）では、画素が連結しているか否かによって分割されている。
制御部１１は、図２１（ｂ）に示す「金」や「監」を縮退とみなし、優先的に探索を行っても良い。以下では、「金」や「監」を縮退とみなさない場合の処理について説明する。尚、縮退とみなす場合も、同様の考え方によって処理を実行することができる。
【００９３】
次に、制御部１１は、ストローク部品ごとに交差ノードを付与する（Ｓ３０２）。
図２１（ｄ）では、「全」、「臣」、「人」、「皿」の分割領域に対して、それぞれ交差ノードを付与している。尚、図２１（ｄ）では、紙面の都合上、交差ノードのインデックスを、各分割領域の範囲内において一意に識別できるように付番しているが、実際には、認識対象画像「鑑」全体として一意に識別できるように付番する。
【００９４】
図２１（ｄ）の「全」では、６個の交差ノードが付与されている。前述したように、交差ノードは、最も左の要素を第１要素（始点）とする。また、水平方向の位置が同じ場合、最も上の要素を第１要素（始点）とする。そして、例えば、反時計回りなど所定の順番によって要素順位を設定していく。
同様に、「臣」では１０個の交差ノード、「人」では１個の交差ノード、「皿」では８個の交差ノードが付与されている。
【００９５】
更に、図２１（ｅ）では、ストローク部品を分解し、ストローク部品ごとに交差ノードが付与されている。
例えば、「全」の分割領域に対しては、６個のストローク部品に分解されている。第１のストローク部品には、インデックスが「１」、「２」の２個の交差ノードが付与されている。第２のストローク部品には、インデックスが「１」、「３」、「６」の３個の交差ノードが付与されている。第３のストローク部品には、インデックスが「４」の１個の交差ノードが付与されている。第４のストローク部品には、インデックスが「５」の１個の交差ノードが付与されている。第５のストローク部品には、インデックスが「２」、「６」の２個の交差ノードが付与されている。第６のストローク部品には、インデックスが「３」、「４」、「５」の３個の交差ノードが付与されている。
【００９６】
次に、制御部１１は、交差ノード数を示すスカラー値を算出する（Ｓ３０３）。
図２２（ａ）には、交差ノード数を示すスカラー値の算出結果が示されている。２進数「１１００１」は、１０進数「２５」であるから、交差ノード数は２５個である。算出式は、６＋１０＋１＋８＝２５である。
【００９７】
次に、制御部１１は、全体構成（ストローク部品の数）を示すスカラー値を算出する（Ｓ３０４）。
図２２（ｂ）には、全体構成（ストローク部品の数）を示すスカラー値の算出結果が示されている。２進数「１１００１」は、１０進数「２５」であるから、ストローク部品の数は２５個である。算出式は、６＋１＋１＋８＋２＋１＋６＝２５である。
尚、交差ノード数とストローク部品の数の一致は、単なる偶然である。
【００９８】
次に、制御部１１は、ストローク部品の要素種別を示すスカラー値を算出する（Ｓ３０５）。
図２２（ｃ）及び（ｄ）には、ストローク部品の要素種別を示すスカラー値の算出結果が示されている。２５個のストローク部品は、全て単独エッジ（設定値が０）であるから、（ｃ）の第１ビットから第３２ビット、及び、（ｄ）の第１ビットから第１８ビットまでが、全て０となる。
【００９９】
次に、制御部１１は、交差ノードとストローク部品のリンクを示すスカラー値を算出する（Ｓ３０６）。
図２２（ｃ）及び（ｄ）には、「金」の部首（「全」、「一」、「一」の分割領域）について、交差ノードとストローク部品のリンクを示すスカラー値の算出結果が示されている。尚、「監」の部首（「臣」、「人」、「一」、「皿」の分割領域）については、「金」の部首の例から容易に理解できる為、説明を省略する。
【０１００】
図２２（ｅ）及び（ｆ）には、「全」の分割領域に含まれる第１のストローク部品の算出結果が示されている。
このストローク部品は、インデックスが「１」、「２」の２個の交差ノードが付与されている。従って、（ｅ）の第１ビットから第４ビットは「００１０」（１０進数では「２」）となる。
また、１つ目の交差ノード（インデックスが「１」）の位置は、ストローク部品の途中である。従って、（ｅ）の第５ビットは「０」（途中）となる。
また、最後の交差ノード（インデックスが「２」）の位置は、ストローク部品の端部である。従って、（ｅ）の第６ビットは「１」（端部）となる。
また、１つ目の交差ノードは、インデックスが「１」である。従って、（ｆ）の第１ビットから第８ビットは「０００００００１」（１０進数では「１」）となる。
また、２つ目の交差ノードは、インデックスが「２」である。従って、（ｆ）の第９ビットから第１６ビットは「００００００１０」（１０進数では「２」）となる。
【０１０１】
図２３（ａ）及び（ｂ）には、「全」の分割領域に含まれる第２のストローク部品の算出結果が示されている。
このストローク部品は、インデックスが「１」、「３」、「６」の３個の交差ノードが付与されている。従って、（ａ）の第１ビットから第４ビットは「００１１」（１０進数では「３」）となる。
また、１つ目の交差ノード（インデックスが「１」）の位置は、ストローク部品の端部である。従って、（ｅ）の第５ビットは「１」（端部）となる。
また、最後の交差ノード（インデックスが「６」）の位置は、ストローク部品の端部である。従って、（ｅ）の第６ビットは「１」（端部）となる。
また、１つ目の交差ノードは、インデックスが「１」である。従って、（ｆ）の第１ビットから第８ビットは「０００００００１」（１０進数では「１」）となる。
また、２つ目の交差ノードは、インデックスが「３」である。従って、（ｆ）の第９ビットから第１６ビットは「００００００１１」（１０進数では「３」）となる。
また、３つ目の交差ノードは、インデックスが「６」である。従って、（ｆ）の第１７ビットから第２４ビットは「０００００１１０」（１０進数では「６」）となる。
【０１０２】
図２３（ｃ）及び（ｄ）には、「全」の分割領域に含まれる第３のストローク部品の算出結果が示されている。
図２３（ｅ）及び（ｆ）には、「全」の分割領域に含まれる第４のストローク部品の算出結果が示されている。
図２４（ａ）及び（ｂ）には、「全」の分割領域に含まれる第５のストローク部品の算出結果が示されている。
図２４（ｃ）及び（ｄ）には、「全」の分割領域に含まれる第６のストローク部品の算出結果が示されている。
図２４（ｅ）には、１つ目の「一」の分割領域に含まれる第７のストローク部品の算出結果が示されている。
図２４（ｅ）には、２つ目の「一」の分割領域に含まれる第８のストローク部品の算出結果が示されている。
いずれも、第１のストローク部品及び第２のストローク部品と同様の考え方によって算出される。
【０１０３】
図２１〜図２４に示す例では、ストローク部品が全て単独エッジであったが、ストローク部品が分岐点、孔、縮退であっても、前述の定義に従って算出することができる。
例えば、図７（ｂ）及び図９（ｃ）に示す例（４桁の数字「５８１３」の例）であれば、「５」の一番下のストローク部品（「つ」の形状に近い軌跡を有するストローク部品）は、分岐点となる。また、「８」の２つのストローク部品は、孔となる。
【０１０４】
＜５．ストローク部品分割処理に基づく文字種別判定処理＞
次に、図２５を参照しながら、ストローク部品分割処理に基づく文字種別判定処理について説明する。図２５は、ストローク部品分割処理に基づく文字種別判定処理の流れを示すフローチャートである。
【０１０５】
図２５に示すように、文字認識装置１の制御部１１は、認識対象スカラー値の中で、ストローク部品ごとの要素種別を示すスカラー値のみを取り出し、ストローク部品ごとの要素種別の比較を行うことによって、辞書データベース３に一致する辞書スカラー値を検索する（Ｓ４０１）。
一致する辞書スカラー値を特定できる場合（Ｓ４０２のＹｅｓ）、制御部１１は、「一致」と判定し（Ｓ４０３）、処理を終了する。
一致する辞書スカラー値が特定できない場合（Ｓ４０２のＮｏ）、制御部１１は、Ｓ４０４に進む。
【０１０６】
Ｓ４０４では、制御部１１は、認識対象スカラー値の中で、ストローク部品ごとの要素種別及び交差ノードの数を示すスカラー値を取り出し、ストローク部品ごとの要素種別及び交差ノードの数の比較を行うことによって、辞書データベース３に一致する辞書スカラー値を検索する。
一致する辞書スカラー値を特定できる場合（Ｓ４０５のＹｅｓ）、制御部１１は、「一致」と判定し（Ｓ４０３）、処理を終了する。
一致する辞書スカラー値が特定できない場合（Ｓ４０５のＮｏ）、制御部１１は、Ｓ４０６に進む。
【０１０７】
Ｓ４０６では、制御部１１は、認識対象スカラー値の中で、ストローク部品ごとの要素種別、交差ノードの数、及び、交差ノードとストローク部品のリンクを示すスカラー値を取り出し、ストローク部品ごとの要素種別、交差ノードの数、及び、交差ノードとストローク部品のリンクの比較を行うことによって、辞書データベース３に一致する辞書スカラー値を検索する。
一致する辞書スカラー値を特定できる場合（Ｓ４０７のＹｅｓ）、制御部１１は、「一致」と判定し（Ｓ４０３）、処理を終了する。
一致する辞書スカラー値が特定できない場合（Ｓ４０７のＮｏ）、制御部１１は、「不一致」と判定し（Ｓ４０８）、処理を終了する。
【０１０８】
複雑な文字の場合、細部まで完全に一致する辞書スカラー値を全て登録しておくことは難しい。そこで、Ｓ４０１において、最初に、ストローク部品ごとの要素種別のみを比較することによって、画数が多く複雑な文字であっても、一致する辞書スカラー値を一意に特定することができる。
また、Ｓ４０１の比較によって一致する辞書スカラー値を特定できなくても、すなわち、複数の辞書スカラー値が一致した場合であっても、Ｓ４０４において、ストローク部品ごとの要素種別及び交差ノードの数を比較することによって、一致する辞書スカラー値を一意に特定することができる。
また、Ｓ４０４の比較によって一致する辞書スカラー値を特定できなくても、すなわち、複数の辞書スカラー値が一致した場合であっても、Ｓ４０６において、ストローク部品ごとの要素種別、交差ノードの数、及び、交差ノードとストローク部品のリンクを比較することによって、一致する辞書スカラー値を一意に特定することができる。
【０１０９】
＜６．グラフ作成処理＞
次に、図２６〜図３２を参照しながら、グラフ作成処理について説明する。文字認識装置１は、ストローク部品分割処理に基づく文字種別判定処理において、一致する辞書スカラー値が存在しなかった場合、グラフ作成処理を実行し、グラフ作成処理に基づくスカラー値変換処理及び文字種別判定処理を実行する。すなわち、文字認識装置１は、複数の手法を用いて文字種別を判定する。
【０１１０】
図２６は、辞書データベース３ａの一例である。辞書データベース３ａは、グラフ作成処理に基づく文字種別判定に用いられる。
辞書データベース３ａには、文字種別３１ごとに、１または複数の辞書画像３２が対応付けられている。また、辞書データベース３ａには、辞書画像３２ごとに、１または複数の辞書グラフ３４が対応付けられている。また、辞書データベース３ａには、辞書グラフ３４と辞書スカラー値３３ａが１対１に対応付けられている。
【０１１１】
文字種別３１は、各文字の種別を示すデータであり、例えば、文字コードである。
辞書画像３２は、各文字のフォントの画像データである。
辞書グラフ３４は、各辞書画像３２に対応するグラフである。辞書グラフ３４は、１の辞書画像３２に基づいて、複数個記憶されていても良い。辞書グラフ３４の詳細については後述する。
辞書スカラー値３３ａは、辞書グラフ３４と１対１に対応付けられるスカラー値である。但し、図２６の辞書スカラー値３３ａは、一部のみを図示している。辞書スカラー値３３ａの詳細については後述する。
【０１１２】
図２７は、グラフ作成処理の流れを示すフローチャートである。以下、理解を容易にするために、図２８から図３０を合わせて参照しながら、具体的な例とともに説明する。図２８から図３０は、「夏」のグラフ作成処理の一例である。
【０１１３】
図２７に示すように、文字認識装置１の制御部１１は、認識対象画像に存在する閾値以下の距離を有する隙間の埋立処理を実行する（Ｓ５０１）。図２８の（１）に示す認識対象文字は、全ての箇所において連結している。従って、この例では、隙間が存在せず、埋立が行われる箇所はない。
ここで、「連結」しているとは、認識対象画像における「文字領域」の画素同士がつながっていることを意味する。例えば、「４連結」の場合、注目画素の上下左右の位置のいずれかにおいて、「文字領域」の画素が存在する場合、注目画素において「連結」している。また、例えば、「８連結」の場合、注目画素の上下左右に斜め方向の４個を加えた位置のいずれかにおいて、「文字領域」の画素が存在する場合、注目画素において「連結」している。
以下では、「連結」している「文字領域」の集合を「連結領域」と呼ぶことにする。
【０１１４】
次に、制御部１１は、連結領域ごとにラベリングし、認識対象画像を分離する（Ｓ５０２）。前述の通り、図２８の（１）に示す認識対象文字は、全ての箇所において連結しているから、連結領域は１個となる。図２８の（２）では、１個の連結領域を図示している。
制御部１１は、以降の処理（Ｓ５０３〜Ｓ５０９の処理）を連結領域ごとに実行する。
【０１１５】
次に、制御部１１は、認識対象画像に含まれる小孔を探索する（Ｓ５０３）。ここで、「小孔」とは、「包含孔」と区別するための用語であり、閉領域の大きさには無関係である。また、「探索」とは、認識対象画像の文字領域を走査し、探索対象のグラフ要素（Ｓ５０３では、「小孔」）に相当する箇所（Ｓ５０３では、文字の閉領域）を特定することである。
【０１１６】
図２８の（３−１）では、グラフ要素が識別できるように、認識対象画像の文字を点線にて図示している。以降、図２９及び図３０においても、認識対象画像の文字を点線にて図示する。また、図２８の（３−２）では、グラフ要素の位置関係が識別できるように、（３−１）からグラフ要素のみを抽出して図示している。以降、図２９及び図３０においても、グラフ要素のみ抽出されている図を示す。
図２８の（３−１）及び（３−２）では、認識対象画像の上部に、横長の小孔が３個図示されている。また、認識対象画像の下部に、比較的円に近い小孔が１個図示されている。
【０１１７】
このように、本発明の実施の形態では、グラフ要素として孔を定義しておき、グラフ作成処理において、認識対象画像に含まれる小孔から探索し、認識対象グラフのグラフ要素として設定していく。これによって、ひいては、高精度に文字種別を判定することができる。
【０１１８】
次に、制御部１１は、Ｓ５０３においてグラフ要素として設定されている小孔に対して、小孔同士の隣接関係を示す隣接線を探索する（Ｓ５０４）。制御部１１は、注目している２個の小孔同士の距離が閾値以下の場合、その小孔同士が隣接しているとし、その小孔同士の隣接線を設定する。
【０１１９】
図２９の（１−１）及び（１−２）では、２個の隣接線が設定されている。具体的には、認識対象画像の上部に存在する横長の３個の小孔のうち、上から１番目の小孔と、上から２番目の小孔とに隣接線が設定されている。同様に、上から２番目の小孔と、上から３番目の小孔とに隣接線が設定されている。
一方、上から１番目の小孔と、上から３番目の小孔とは、距離が遠いことから隣接線が設定されていない。同様に、認識対象画像の下部に存在する比較的円に近い小孔（上から４番目の小孔）と、上から３番目の小孔とは、距離が遠いことから、隣接線が設定されていない。
尚、隣接線は以降の処理において設定されるグラフ要素と直接関係がないので、途中の図では図示を省略し、図３０の（３−２）にのみ図示するものとする。
【０１２０】
次に、制御部１１は、いわゆる一筆書きによって輪郭線を描くことができ、かつ可能な限り多くの小孔を包含する包含孔を探索する（Ｓ５０５）。一筆書きとは、同じ経路を１回のみ通過する筆跡である。
【０１２１】
図２９の（２−１）及び（２−２）では、１個の包含孔が設定されている。この包含孔は、上から１番目、２番目及び３番目の３個の小孔を包含している。この包含孔は、上から１番目と２番目の２個の小孔を包含するものや、上から２番目と３番目の２個の小孔を包含するものと比較して小孔の数が大きい。また、上から４番目の小孔を包含しようとすると、一筆書きによって輪郭線を描くことができない。従って、制御部１１は、図２９の（２−１）及び（２−２）に示す包含孔をグラフ要素として設定する。
【０１２２】
このように、本発明の実施の形態では、グラフ作成処理において、認識対象画像に含まれる複数の小孔を包含する包含孔を探索し、認識対象グラフのグラフ要素として設定していく。これによって、ひいては、高精度に文字種別を判定することができる。
【０１２３】
次に、制御部１１は、認識対象画像に含まれる端点を探索する（Ｓ５０６）。制御部１１は、所定のアスペクト比（縦横比）の条件に基づいて、端点の探索を行う。
【０１２４】
前述の通り、端点は、１個のグラフ要素のみ接続される。図２９の（３−１）及び（３−２）では、５個の端部が設定されている。
ここで、アスペクト比の条件について簡単に説明しておく。制御部１１は、各運筆の「筆長」を縦の長さ、「筆幅」を横の長さとしたときに、各運筆が所定のアスペクト比の条件を満たしているかどうかを判定する。例えば、「夏」の文字に含まれる「夂」のうち、左上の「ノ」の「筆長」が短く、所定のアスペクト比の条件を満たさない場合、制御部１１は、「ノ」の終点に対して、端点を設定しない。
【０１２５】
次に、制御部１１は、Ｓ５０７においてグラフ要素として設定されている端点から伸びるエッジを探索する（Ｓ５０７）。
図３０の（１−１）及び（１−２）では、５個の端点のそれぞれに対して、１本ずつのエッジ（合計５本のエッジ）が設定されている。
【０１２６】
次に、制御部１１は、Ｓ５０４、Ｓ５０５及びＳ５０７においてグラフ要素として設定されている小孔、包含孔及びエッジの交点である分岐点を探索する（Ｓ５０８）。
ここで、制御部１１は、エッジとエッジの交点よりも、エッジと孔（小孔又は包含孔）の交点を優先し、分岐点として設定する。
【０１２７】
図３０の（２−１）及び（２−２）では、４個の分岐点が設定されている。
ここで、「夏」の文字に含まれる「夂」のうち、下の２本のエッジの交点が分岐点として設定されていないのは、エッジと孔の交点が優先され、分岐点として設定されているからである。
【０１２８】
次に、制御部１１は、認識対象画像の文字領域としては連結しているが、グラフ要素としては接続されていない非接続部のエッジ化を行う（Ｓ５０９）。
図３０の（２−２）において、一点鎖線にて図示されているように、Ｓ５０８の処理が終了した時点では、３個に分かれている。元々これら３個は、１個の連結領域であるから接続する必要がある。
【０１２９】
図３０の（３−１）及び（３−２）では、新たに３個の分岐点と２個のエッジが設定されている。
隣接線を含む最終的なグラフは、図３０の（３−２）に図示する通りである。
以上により、「夏」のグラフ作成処理が終了する。
【０１３０】
図３１、図３２は、第３のスカラー値表現の定義を示す図である。第３のスカラー値表現は、グラフ作成処理によって作成される認識対象グラフから認識対象スカラー値に変換する為に用いられる。以下では、図３１、図３２を参照しながら、１例として、３２ビットのデータ列をデータ単位とする第３のスカラー値表現の定義を説明する。
【０１３１】
図３１（ａ）は、全体構成のスカラー値表現の定義を示している。全体構成のスカラー値表現では、グラフを構成し、概念的に大きな要素（例えば、連結領域である。以下、「大要素」という。）の数、種別及び要素順位を設定する。
具体的には、第１ビットから第４ビットによって、大要素数を設定する。また、第４ビットから第３２ビットによって、２ビットずつ、各大要素の種別を設定する。大要素種別は、（１）単独エッジ：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。
ここで、要素順位について説明する。まず、最も左の大要素を第１要素（始点）とする。また、水平方向の位置が同じ場合、最も上の大要素を第１要素（始点）とする。そして、例えば、反時計回りに要素順位を設定していく。
容易に分かるように、図３１（ａ）に示す定義によって表現可能なグラフは、大要素の数が１４個までとなる。
尚、単独エッジだけは、１個であっても複数個であっても、大要素としては、１個と数える。
【０１３２】
図３１（ｂ）は、単独エッジのスカラー値表現の定義を示している。単独エッジのスカラー値表現では、単独エッジの数を設定する。
具体的には、第１ビットから第４ビットによって、単独エッジの数を設定する。第５ビットから第３２ビットは未定義である。
容易に分かるように、図３１（ｂ）に示す定義によって表現可能なグラフは、単独エッジの数が１６個までとなる。
【０１３３】
図３１（ｃ）は、分岐点のスカラー値表現の定義を示している。分岐点のスカラー値表現では、接続先であって、概念的に小さな要素（以下、「小要素」という。）の数、種別及び要素順位を設定する。
具体的には、第１ビットから第４ビットによって、接続先の小要素数（但し、上位要素を除いた数とする。）を設定する。また、第５ビットから第３２ビットによって、２ビットずつ、各小要素の種別を設定する。小要素種別は、（１）端点：０、（２）分岐点：１、（３）孔：２、（４）縮退：３、の４種類である。端点の場合、その下位の情報は不要となる。
【０１３４】
図３２（ａ）は、孔のスカラー値表現の定義を示している。孔のスカラー値表現では、内部に存在する孔（以下、「内部孔」という。）の数、内部孔同士の隣接線の数、内部に存在する小要素の数（但し、孔を除く。）、外部に存在する小要素の数（但し、上位要素を除く。）を設定する。
具体的には、第１ビットから第８ビットによって、内部孔数を設定する。また、第９ビットから第１６ビットによって、内部孔同士の隣接線の数を設定する。また、第１７ビットから第２４ビットによって、内部要素数を設定する。また、第２５ビットから第３２ビットによって、外部要素数を設定する。
【０１３５】
図３２（ｂ）は、孔の内部要素に関するスカラー値表現の定義を示している。孔の内部要素に関するスカラー値表現では、内部要素の種別を設定する。
具体的には、第１ビットから第３２ビットによって、２ビットずつ、各内部要素の種別を設定する。内部要素の種別は小要素種別と同じである。
【０１３６】
図３２（ｃ）は、孔の外部要素に関するスカラー値表現の定義を示している。孔の外部要素に関するスカラー値表現では、外部要素の種別を設定する。
具体的には、第１ビットから第３２ビットによって、２ビットずつ、各外部要素の種別を設定する。外部要素の種別は小要素種別と同じである。
【０１３７】
図３２（ｄ）は、縮退のスカラー値表現の定義を示している。縮退のスカラー値表現では、縮退登録コードを設定する。
具体的には、第１ビットから第１６ビットによって、縮退登録コードを設定する。第１７ビットから第３２ビットは未定義である。
【０１３８】
文字認識装置１は、認識対象グラフから、図３１及び図３２に示す第３のスカラー値表現の定義に従って、認識対象スカラー値に変換する。スカラー値変換処理は、図２２〜図２４を参照して前述した「鑑」の例と同様の考え方によって実行することができる。
【０１３９】
＜７．辞書データベースの構築処理＞
次に、図３３を参照しながら、辞書データベースの構築処理について説明する。辞書データベースの構築処理は、図４を参照して説明した文字認識処理と同様の処理が多いことから、図４のステップを引用することによって重複する説明を省略する。
【０１４０】
文字認識装置１の制御部１１は、文字種別３１を１つ選択する（Ｓ６０１）。
次に、制御部１１は、Ｓ６０１にて選択される文字種別３１と対応する辞書画像３２を１つ選択する（Ｓ６０２）。
【０１４１】
次に、制御部１１は、Ｓ６０２にて選択される辞書画像３２に基づいて、ストローク部品への分割処理を実行する（Ｓ６０３）。Ｓ６０３におけるストローク部品への分割処理は、Ｓ１０２におけるストローク部品への分割処理と同様である。
【０１４２】
次に、制御部１１は、ストローク部品の集合から、辞書スカラー値３３に変換する（Ｓ６０４）。Ｓ６０４における辞書スカラー値３４への変換処理は、Ｓ１０３における認識対象スカラー値への変換処理と同様である。
【０１４３】
次に、制御部１１は、Ｓ６０４にて変換される辞書スカラー値３３を辞書データベース３に登録する（Ｓ６０５）。
【０１４４】
次に、制御部１１は、全ての拡縮パターンの処理が終了したかどうか確認する（Ｓ６０６）。拡縮パターンとは、例えば、埋立処理やストローク部品への分割処理に用いられる閾値変更など、様々な拡縮処理のパターンを意味する。
全ての拡縮パターンの処理が終了していない場合（Ｓ６０６のＮｏ）、制御部１１は、Ｓ６０３から処理を繰り返す。
全ての拡縮パターンの処理が終了している場合（Ｓ６０６のＹｅｓ）、制御部１１は、Ｓ６０７に進む。
【０１４５】
次に、制御部１１は、全ての辞書画像３２の処理が終了したかどうか確認する（Ｓ６０７）。
全ての辞書画像３２の処理が終了していない場合（Ｓ６０７のＮｏ）、制御部１１は、Ｓ６０２から処理を繰り返す。
全ての辞書画像３２の処理が終了している場合（Ｓ６０７のＹｅｓ）、制御部１１は、Ｓ６０８に進む。
【０１４６】
次に、制御部１１は、全ての文字種別３１の処理が終了したかどうか確認する（Ｓ６０８）。
全ての文字種別３１の処理が終了していない場合（Ｓ６０８のＮｏ）、制御部１１は、Ｓ６０１から処理を繰り返す。
全ての文字種別３１の処理が終了している場合（Ｓ６０８のＹｅｓ）、制御部１１は、処理を終了する。
以上の通り、文字認識装置１は、辞書データベース３の構築処理を実行する。また、容易に分かるように、文字認識装置１は、同様に、辞書データベース３ａの構築処理も実行することができる。
【０１４７】
＜８．変形例＞
次に、図３４を参照しながら、変形例について説明する。図３に示す例では、辞書スカラー値３３は、全体構成を示すスカラー値、ストローク部品ごとの要素種別を示すスカラー値、交差ノードの数を示すスカラー値、交差ノードとストローク部品のリンクを示すスカラー値などを有するとしたが、変形例では、更に、辞書スカラー値３３は、端点の角度情報を示すスカラー値を有する。
【０１４８】
図３４では、文字種別が「あ」の手書き文字について、グラフ要素として端点（文字の端部を示す点）のみを図示している。
変形例では、制御部１１は、端点をグラフ要素として設定すると、端点の角度情報も算出する。端点の角度情報とは、端点からストローク（筆跡）が伸びる方向を示すベクトルの角度情報である。制御部１１は、端点の角度情報として、例えば、３６０度を８分割し、ベクトルの方向が０度〜４５度の場合は「１」、ベクトルの方向が４５度〜９０度の場合は「２」、・・・、ベクトルの方向が３１５度〜３６０度の場合は「８」を設定し、スカラー値として記憶部１２に記憶する。スカラー値の記憶領域は、前述の説明と同様に定義することができる。
図３４には、端点４１〜４６に対して、それぞれ、端点からストローク（筆跡）が伸びる方向を示すベクトル５１〜５６が示されている。制御部１１は、ベクトル５１〜５６の角度情報を、端点４１〜４６の角度情報として、スカラー値表現に変換する。
そして、制御部１１は、文字種別を判定する際、端点の角度情報を示すスカラー値も比較する。
これによって、文字の端部を示す点である端点の角度情報も考慮して文字種別が判定されるので、高精度に文字を認識することができる。
【０１４９】
本発明の実施の形態では、ストローク部品への分割処理を実行し、ストローク部品の集合から認識対象スカラー値に変換し、認識対象スカラー値と一致する辞書スカラー値を特定することによって、認識対象画像の文字種別を判定する。すなわち、認識対象の文字を３次元的に捉えて、ストローク（筆跡）の数や重なりに着目することによって、文字を認識する。従って、オンライン手書き文字認識であっても、オフライン手書き文字認識であっても、高精度に文字を認識することができる。
【０１５０】
以上、添付図面を参照しながら、本発明に係る文字認識方法等の好適な実施形態について説明したが、本発明はかかる例に限定されない。当業者であれば、本願で開示した技術的思想の範疇内において、各種の変更例又は修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０１５１】
１………文字認識装置
３、３ａ………辞書データベース
３１………文字種別
３２………辞書画像
３３、３３ａ………辞書スカラー値
３４………辞書グラフ
【図１】
2012185688.tif 000003
【図２】
2012185688.tif 000004
【図３】
2012185688.tif 000005
【図４】
2012185688.tif 000006
【図５】
2012185688.tif 000007
【図６】
2012185688.tif 000008
【図７】
2012185688.tif 000009
【図８】
2012185688.tif 000010
【図９】
2012185688.tif 000011
【図１０】
2012185688.tif 000012
【図１１】
2012185688.tif 000013
【図１２】
2012185688.tif 000014
【図１３】
2012185688.tif 000015
【図１４】
2012185688.tif 000016
【図１５】
2012185688.tif 000017
【図１６】
2012185688.tif 000018
【図１７】
2012185688.tif 000019
【図１８】
2012185688.tif 000020
【図１９】
2012185688.tif 000021
【図２０】
2012185688.tif 000022
【図２１】
2012185688.tif 000023
【図２２】
2012185688.tif 000024
【図２３】
2012185688.tif 000025
【図２４】
2012185688.tif 000026
【図２５】
2012185688.tif 000027
【図２６】
2012185688.tif 000028
【図２７】
2012185688.tif 000029
【図２８】
2012185688.tif 000030
【図２９】
2012185688.tif 000031
【図３０】
2012185688.tif 000032
【図３１】
2012185688.tif 000033
【図３２】
2012185688.tif 000034
【図３３】
2012185688.tif 000035
【図３４】
2012185688.tif 000036