(57)【要約】【課題】ドットからなる文字・図形、かすれた文字・図形、分断された文字・図形でも認識可能な文字・図形の認識方法を提供する。【解決手段】画像から抽出した骨格線を単純形状である近似線の集合として近似する。ターゲットデータ抽出過程（Ｓ２）は、距離が近く１単位として扱う近似線群をターゲットクラスタとして抽出する。形状類似度算出過程（Ｓ３）では、文字・図形の標準になる形状の近似線群からなるマスタクラスタとターゲットクラスタとの形状の類似度を評価する。形状類似度算出過程（Ｓ３）では、ターゲットクラスタについて設定した外接矩形に対してマスタクラスタについて設定した外接矩形の位置を合わせた後、ターゲットクラスタとマスタクラスタとに含まれる骨格線同士の距離から形状類似度を求め、形状類似度の高いマスタクラスタを着目するターゲットクラスタのカテゴリに対応付ける。【選択図】        図１
2005182660.tif 000002
【特許請求の範囲】
【請求項１】
認識対象として入力された文字・図形の画像から文字・図形の骨格線を抽出し、次に骨格線を単純形状である近似線の集合として近似するとともに、連続している近似線を１つの近似線群に加え、かつ連続していない各一対の近似線間の距離を評価することにより当該近似線群の近傍にある近似線も当該近似線群に加えて、１単位として扱う近似線群をターゲットクラスタとして抽出するターゲットデータ抽出過程と、文字・図形の標準になる形状の骨格線を近似線の集合として近似した近似線群からなるマスタクラスタと前記ターゲットクラスタとの形状の類似度を評価する形状類似度算出過程とを有し、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データを含んでおり、形状類似度算出過程では、ターゲットクラスタについて設定した外接矩形に対してマスタクラスタについて設定した外接矩形の位置を合わせた後に、ターゲットクラスタとマスタクラスタとに含まれる骨格線同士の距離から形状類似度を求め、形状類似度の高いマスタクラスタを着目するターゲットクラスタのカテゴリに対応付けることを特徴とする文字・図形の認識方法。
【請求項２】
前記近似線として、直線と楕円弧とを用いることを特徴とする請求項１記載の文字・図形の認識方法。
【請求項３】
前記形状類似度算出過程において、ターゲットクラスタについて設定した外接矩形とマスタクラスタについて設定した外接矩形との高さ寸法および幅寸法の寸法比を求めることにより、ターゲットクラスタに含まれる高さ方向および幅方向における文字・図形の個数を推定し、ターゲットクラスタについて設定した外接矩形に対して、推定した個数に対応した位置ごとにマスタクラスタについて設定した外接矩形を位置合わせし、各位置で形状類似度を求めることを特徴とする請求項１または請求項２記載の文字・図形の認識方法。
【請求項４】
前記マスタクラスタおよび前記ターゲットクラスタとにおいて、近似線の接続されていない孤立点と、近似線の開放端である端点と、２本の近似線を一直線上で接続する線接続点と、２本の近似線を１８０度以内の角度で接続する屈曲点と、３本以上の近似線を接続する分岐点との少なくとも１種類をノードに用い、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データのほかにノードの位置を特定するノードデータを含んでおり、前記形状類似度算出過程において、前記骨格線同士の距離を求める前に、前記マスタクラスタの各ノードの種類と当該ノードから規定の距離範囲内に存在する前記ターゲットクラスタの各ノードの種類とを判断し、マスタクラスタに含まれるノードの少なくとも１個がターゲットクラスタのノードの種類と一致しない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないことを特徴とする請求項１ないし請求項３のいずれか１項に記載の文字・図形の認識方法。
【請求項５】
前記マスタクラスタおよび前記ターゲットクラスタとにおいて、近似線の接続されていない孤立点と、近似線の開放端である端点と、２本の近似線を一直線上で接続する線接続点と、２本の近似線を１８０度以内の角度で接続する屈曲点と、３本以上の近似線を接続する分岐点との少なくとも１種類をノードに用い、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データのほかにノードの位置を特定するノードデータを含んでおり、前記形状類似度算出過程において、前記骨格線同士の距離を求める前に、前記ターゲットクラスタの各ノードごとに周囲の近似線の近似線データと周囲のノードのノードデータとを用いることにより、前記マスタクラスタの各ノードから規定の距離範囲内に存在するターゲットクラスタのノードの種類のベイズ確率を求め、マスタクラスタのノードの種類とターゲットクラスタのノードの種類との類似度であるノード類似度をベイズ確率を用いて求め、、マスタクラスタに含まれるノードの少なくとも１個に対応するターゲットクラスタのノードのノード類似度が規定の閾値以上でない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないことを特徴とする請求項１ないし請求項３のいずれか１項に記載の文字・図形の認識方法。
【請求項６】
前記形状類似度算出過程において、前記形状類似度は、前記マスタクラスタに含まれる近似線から前記ターゲットクラスタに含まれる近似線までの距離が規定の距離内である近似線の総延長がマスタクラスタに含まれる近似線の総延長に占める割合と、前記距離から前記距離内である近似線間の平均距離を減算した値を前記距離で除算することにより得られる近似線間の接近程度の評価値とを乗じた値に比例することを特徴とする請求項１ないし請求項５のいずれか１項に記載の文字・図形の認識方法。
【請求項７】
前記形状類似度算出過程において、前記外接矩形を用いてターゲットクラスタにマスタクラスタの位置を合わせた後に、マスタクラスタに含まれる近似線をターゲットクラスタに含まれる近似線に重ねるように位置と回転とスケールと線形歪との少なくとも１要素を変換する変換式のパラメータを最小自乗法により求め、当該変換の適用後に形状類似度を求めることを特徴とする請求項１ないし請求項６のいずれか１項に記載の文字・図形の認識方法。
【請求項８】
認識対象として入力された文字・図形が複数個であり、かつ個数および配列が既知である場合に、前記形状類似度算出過程において、異なる２個以上の外接矩形から１個ずつの角位置を代表点として選択するとともに、マスタクラスタの代表点の位置をターゲットクラスタの代表点の位置に重ねることにより外接矩形の位置を合わせることを特徴とする請求項１記載の文字・図形の認識方法。
【請求項９】
認識対象として入力された文字・図形が複数個であり、かつ個数および配列が既知である場合に、前記形状類似度算出過程において、各ターゲットクラスタについてそれぞれ面積が最小になるように回転位置を調節した外接矩形を求め、当該外接矩形の角を一つの軸上に写像したときに角の度数が最大になる軸の角度を用いてターゲットクラスタの角度を検出し、当該角度でマスタクラスタを回転させることにより外接矩形の位置を合わせることを特徴とする請求項１記載の文字・図形の認識方法。
【請求項１０】
前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から既知である文字・図形の内側向きの明度の変化方向の一直線上を探索して得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする請求項１ないし請求項９のいずれか１項に記載の文字・図形の認識方法。
【請求項１１】
前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から既知である文字・図形の内側向きの明度の変化方向の一直線上を探索して規定の距離範囲内において得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする請求項１ないし請求項９のいずれか１項に記載の文字・図形の認識方法。
【請求項１２】
前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から明度の変化方向における両向きの一直線上を探索して規定の距離範囲内において得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする請求項１ないし請求項９のいずれか１項に記載の文字・図形の認識方法。
【請求項１３】
前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上の画素の周囲における明度の変化方向を求め、明度の勾配が最大である２方向のうちの少なくとも一方に輪郭線を膨張させる膨張処理を行い、異なる２方向から膨張してきた画素が衝突する画素を骨格線上の画素とすることを特徴とする請求項１ないし請求項９のいずれか１項に記載の文字・図形の認識方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対象物に印刷したり刻印したりした文字・図形をＴＶカメラやスキャナのような画像入力装置で読み取り、画像入力装置で得た画像に画像処理を施すことによって文字・図形を認識する文字・図形の認識方法に関するものである。
【背景技術】
【０００２】
従来から、文字・図形（「文字・図形」とは、キャラクタジェネレータで生成できるような、文字や図形を意味しており、以下では単に「文字」と呼ぶ）をＴＶカメラやスキャナのような画像入力装置で読み取り、画像入力装置で得た画像に画像処理を施すことによって文字を認識する技術が種々提案されている。文字を認識する技術は、あらかじめ指定されたカテゴリに対応付けるパターン認識の技術であるから、カテゴリの対応付けが容易になるような文字の構造の記述、文字の変形に対する補正、対象物に表記された文字を１文字ずつ切り出すセグメンテーションなどの技術が必要になる。
【０００３】
たとえば、手書き文字のように複雑に変形する文字を認識するために、文字の構造を以下の形で記述することが提案されている（たとえば、特許文献１、特許文献２参照）。特許文献１、２に記載の技術では、文字の画像を細線化して分岐点あるいは交差点を特異点として抽出し、特異点の周囲の構造を、「Ｘ」のような交差、「Ｋ」のような接触、「Ｔ」のような分岐の３種類に分類することによって、特異点で接続される線を複数のストロークに分割し、さらに、プリミティブと呼ぶ単調曲線の連結構造であるプリミティブ系列を用いて各ストロークを表し、プリミティブ系列と特異点との組により、文字の構造を記述している。ストロークは文字を手書きする際のひとつながりの部分（一筆で書く部分にほぼ一致する）に相当し、プリミティブとは、２次元画像内においてｘ、ｙ座標が単調に変化する単調曲線を意味している。また、プリミティブの連結構造は、２つのプリミティブを連結することにより形成される凸の方向と、連結点の回りでのプリミティブの右手系での配置順序とで表され、プリミティブ系列は１つのストロークを構成するプリミティブの連結構造の集合になる。
【０００４】
また、特許文献１、２では、文字の変形に対する補正のために、バウンディングボックス（文字を囲む最小の直立長方形）を用い、バウンディングボックスの縦横比を変更せずに長い方の辺を単位長にするようにスケールを正規化し、さらにアフィン変換による補正を行う技術も開示されている。
【０００５】
すなわち、特許文献１、２に記載の技術では、入力画像について文字のセグメンテーションを行った後に、細線化してプリミティブ系列と特異点とで表される構造を解析し、次に入力画像から切り出した部分画像とモデルとの構造についてのマッチングによりカテゴリの候補を抽出し、さらに部分画像を正規化してモデルとの距離計算を行い類似度を評価することで、部分画像をモデルの文字のカテゴリに対応付けている。このように、文字の構造的情報と定量的情報とを用いることによりロバストなパターン認識が可能になっている。
【０００６】
ところで、特許文献１、２にはセグメンテーションの技術については、とくに説明されていないが、セグメンテーションの技術としては、入力された文字列画像を細線化して得られる骨格線図形を単純弧や単純閉曲線を用いて部分曲線に分割した後、部分曲線における分岐点あるいは交差点の有無と部分曲線の横幅と文字列の高さとを用いて、文字の接触の可能性を推定する技術が提案されている（たとえば、特許文献３参照）。また、特許文献３には、骨格線図形を分割して得られた部分曲線を組合せることにより生成される文字列について特許文献１、２と同様の技術を用いて文字を認識し、認識結果の組合せのうち文字として認識された部分図形をノードとするネットワークを構成し、ネットワークから最適経路を選択することにより、ノードの認識文字の組合せを出力する技術も開示されている。さらに、文字数が既知である場合には、ネットワークから文字数と一致するノード数の経路から最適経路を選択することも記載されている。
【特許文献１】特開平７−２１３１７号公報
【特許文献２】特許第３１８３９４９号公報
【特許文献３】特開平６−７６１１４号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところで、上述した特許文献１、２に記載の技術では、文字の構造的情報を用いて入力画像のカテゴリを絞り込んではいるものの、構造的情報として線図形の分岐点と交差点を基準に用いており、文字を構成する線が連続していることが前提になっている。このことは、特許文献３に記載の技術においても同様である。
【０００８】
したがって、対象物に印刷したり刻印したりした文字のように変形の比較的少ない文字であっても、食品の賞味期限や消費期限の表示などにおいて広く用いられているドット文字、印刷装置の不具合などに起因して生じるかすれた文字（以下、「かすれ文字」という）、文字を構成する連続すべき線が不連続に分断した文字（以下、「分断文字」という）などでは、文字の構造的情報を正確に抽出することができず、特許文献１〜３に記載された技術を採用したとしても、文字を正確に認識することができない可能性がある。
【０００９】
本発明は上記事由に鑑みて為されたものであり、その目的は、ドット文字、かすれ文字、分断文字であっても認識することが可能な文字・図形の認識方法を提供することにある。
【課題を解決するための手段】
【００１０】
請求項１の発明は、認識対象として入力された文字・図形の画像から文字・図形の骨格線を抽出し、次に骨格線を単純形状である近似線の集合として近似するとともに、連続している近似線を１つの近似線群に加え、かつ連続していない各一対の近似線間の距離を評価することにより当該近似線群の近傍にある近似線も当該近似線群に加えて、１単位として扱う近似線群をターゲットクラスタとして抽出するターゲットデータ抽出過程と、文字・図形の標準になる形状の骨格線を近似線の集合として近似した近似線群からなるマスタクラスタと前記ターゲットクラスタとの形状の類似度を評価する形状類似度算出過程とを有し、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データを含んでおり、形状類似度算出過程では、ターゲットクラスタについて設定した外接矩形に対してマスタクラスタについて設定した外接矩形の位置を合わせた後に、ターゲットクラスタとマスタクラスタとに含まれる骨格線同士の距離から形状類似度を求め、形状類似度の高いマスタクラスタを着目するターゲットクラスタのカテゴリに対応付けることを特徴とする。
【００１１】
この方法によれば、認識対象となる文字・図形および認識対象に照合する文字・図形を単純形状の近似線の集合であるターゲットクラスタおよびマスタクラスタとして表現しておき、認識対象として入力された文字・図形の画像については近似線の距離を評価することによって１単位として扱う近似線群をターゲットクラスタとしているから、たとえばドットにより表現されている文字・図形、かすれた文字・図形、分断された文字・図形であってもターゲットクラスタの１単位として扱うことが可能になり、従来方法では認識できなかったこれらの文字・図形の認識が可能になる。また、ターゲットクラスタについて設定した外接矩形に対してマスタクラスタについて設定した外接矩形の位置を合わせて形状類似度を求めるから、通常のパターンマッチングのようにテンプレートを１画素ずつずらして照合する場合に比較すると、画像内において照合を行う領域が制限されることになり、従来構成に比較して処理負荷を大幅に低減させることができ、結果的に高速な処理が期待できる。
【００１２】
請求項２の発明は、請求項１の発明において、前記近似線として、直線と楕円弧とを用いることを特徴とする。
【００１３】
この方法によれば、ベジェ曲線やスプライン曲線のような複雑な曲線を用いずに、直線と楕円弧とを文字・図形の近似線に用いているから、近似線を表現するためのパラメータがベジェ曲線やスプライン曲線に比べて少なくなって近似線を表現するためのデータ量を低減することができる上に、マスタクラスタとターゲットクラスタとから形状類似度を算出する演算のような照合処理における処理負荷を軽減でき、結果的に高速な処理が期待できる。
【００１４】
請求項３の発明は、請求項１または請求項２の発明において、前記形状類似度算出過程において、ターゲットクラスタについて設定した外接矩形とマスタクラスタについて設定した外接矩形との高さ寸法および幅寸法の寸法比を求めることにより、ターゲットクラスタに含まれる高さ方向および幅方向における文字・図形の個数を推定し、ターゲットクラスタについて設定した外接矩形に対して、推定した個数に対応した位置ごとにマスタクラスタについて設定した外接矩形を位置合わせし、各位置で形状類似度を求めることを特徴とする。
【００１５】
この方法によれば、ターゲットクラスタに複数個の文字・図形が含まれている場合でも、マスタクラスタにおける文字・図形の単位ごとに切り出して形状類似度を求めることができる。すなわち、ターゲットクラスタとして融合した近似線の集合は、ドットで構成された文字・図形、かすれた文字・図形、分断された文字・図形を１文字として扱うことができるものの複数文字を結合している場合もあるのに対して、本方法によりターゲットクラスタに含まれる文字・図形の個数を評価することができ、ターゲットクラスタに複数個の文字・図形が含まれるときには１個ずつ切り分けることが可能になる。
【００１６】
請求項４の発明は、請求項１ないし請求項３の発明において、前記マスタクラスタおよび前記ターゲットクラスタとにおいて、近似線の接続されていない孤立点と、近似線の開放端である端点と、２本の近似線を一直線上で接続する線接続点と、２本の近似線を１８０度以内の角度で接続する屈曲点と、３本以上の近似線を接続する分岐点との少なくとも１種類をノードに用い、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データのほかにノードの位置を特定するノードデータを含んでおり、前記形状類似度算出過程において、前記骨格線同士の距離を求める前に、前記マスタクラスタの各ノードの種類と当該ノードから規定の距離範囲内に存在する前記ターゲットクラスタの各ノードの種類とを判断し、マスタクラスタに含まれるノードの少なくとも１個がターゲットクラスタのノードの種類と一致しない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないことを特徴とする。
【００１７】
この方法によれば、ターゲットクラスタとマスタクラスタとにおいてノードの種類が一致していないときには文字・図形のトポロジが異なっていると判断して形状類似度を求めないようにしているから、一致する可能性のないマスタクラスタとの形状類似度の演算を回避する前処理を行うことになり、処理負荷を大幅に軽減することができる。
【００１８】
請求項５の発明は、請求項１ないし請求項３の発明において、前記マスタクラスタおよび前記ターゲットクラスタとにおいて、近似線の接続されていない孤立点と、近似線の開放端である端点と、２本の近似線を一直線上で接続する線接続点と、２本の近似線を１８０度以内の角度で接続する屈曲点と、３本以上の近似線を接続する分岐点との少なくとも１種類をノードに用い、マスタクラスタおよびターゲットクラスタは、近似線の位置および形状を特定する近似線データのほかにノードの位置を特定するノードデータを含んでおり、前記形状類似度算出過程において、前記骨格線同士の距離を求める前に、前記ターゲットクラスタの各ノードごとに周囲の近似線の近似線データと周囲のノードのノードデータとを用いることにより、前記マスタクラスタの各ノードから規定の距離範囲内に存在するターゲットクラスタのノードの種類のベイズ確率を求め、マスタクラスタのノードの種類とターゲットクラスタのノードの種類との類似度であるノード類似度をベイズ確率を用いて求め、、マスタクラスタに含まれるノードの少なくとも１個に対応するターゲットクラスタのノードのノード類似度が規定の閾値以上でない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないことを特徴とする。
【００１９】
この方法によれば、ノードの種類をベイズ確率で表すことにより、骨格線を抽出する際に文字・図形のトポロジが変化した場合であっても、元の文字・図形におけるノードの種類を比較的信頼性よく求めることができる。このようにして求めたノードの種類を用いることによって、請求項５の方法と同様に、ターゲットクラスタとマスタクラスタとにおいてノードの種類が一致していないときには文字・図形のトポロジが異なっていると判断して形状類似度を求めないことで、一致する可能性のないマスタクラスタとの形状類似度の演算を回避する前処理を行うことになり、処理負荷を大幅に軽減することができる。
【００２０】
請求項６の発明では、請求項１ないし請求項５の発明において、前記形状類似度算出過程において、前記形状類似度は、前記マスタクラスタに含まれる近似線から前記ターゲットクラスタに含まれる近似線までの距離が規定の距離内である近似線の総延長がマスタクラスタに含まれる近似線の総延長に占める割合と、前記距離から前記距離内である近似線間の平均距離を減算した値を前記距離で除算することにより得られる近似線間の接近程度の評価値とを乗じた値に比例することを特徴とする。
【００２１】
この方法によれば、ターゲットクラスタとマスタクラスタとの近似線間の距離が近く、かつ近似線間が近接している部分がマスタクラスタの近似線の全長に対して占める割合が多いほど形状類似度が高いと評価するから、類似している形状を適切に評価することができる。また、文字・図形にノイズが重畳している場合でも骨格線の部分についてのみ類似性を評価することができる。
【００２２】
請求項７の発明は、請求項１ないし請求項６の発明において、前記形状類似度算出過程において、前記外接矩形を用いてターゲットクラスタにマスタクラスタの位置を合わせた後に、マスタクラスタに含まれる近似線をターゲットクラスタに含まれる近似線に重ねるように位置と回転とスケールと線形歪との少なくとも１要素を変換する変換式のパラメータを最小自乗法により求め、当該変換の適用後に形状類似度を求めることを特徴とする。
【００２３】
この方法によれば、ターゲットクラスタとマスタクラスタとに含まれる文字・図形の骨格線において、位置がずれていたり、互いに回転していたり、スケールが異なっていたり、マスタクラスタに対してターゲットクラスタに線形歪が生じていたりする場合でも、両者が一致するように補正することができ、外接矩形の位置を合わせるだけでは吸収できない誤差分を少なくし、文字・図形のカテゴリの対応付けの精度を高めることができる。言い換えると、斜体などの変形した文字・図形と変形していない文字・図形とに対して、同じマスタクラスタを用いてカテゴリの対応付けが可能になる。
【００２４】
請求項８の発明は、請求項１の発明において、認識対象として入力された文字・図形が複数個であり、かつ個数および配列が既知である場合に、前記形状類似度算出過程において、異なる２個以上の外接矩形から１個ずつの角位置を代表点として選択するとともに、マスタクラスタの代表点の位置をターゲットクラスタの代表点の位置に重ねることにより外接矩形の位置を合わせることを特徴とする。
【００２５】
この方法によれば、認識対象が複数個の文字・図形を含むときに、ターゲットクラスタにおける文字・図形の配列を利用し比較的離れた位置の複数点でマスタクラスタの位置を合わせるから、マスタクラスタの外接矩形の位置をターゲットクラスタの外接矩形の位置に精度よく合わせることができる。とくに、代表点の距離を大きくとれば、ターゲットクラスタの回転角度を正確に検出することができ、このことによってマスタクラスタの位置合わせをより精度よく行うことが可能になる。
【００２６】
請求項９の発明は、請求項１の発明において、認識対象として入力された文字・図形が複数個であり、かつ個数および配列が既知である場合に、前記形状類似度算出過程において、各ターゲットクラスタについてそれぞれ面積が最小になるように回転位置を調節した外接矩形を求め、当該外接矩形の角を一つの軸上に写像したときに角の度数が最大になる軸の角度を用いてターゲットクラスタの角度を検出し、当該角度でマスタクラスタを回転させることにより外接矩形の位置を合わせることを特徴とする。
【００２７】
この方法によれば、面積が最小になるように外接矩形を設定するから、文字・図形が正立している方向に合致した外接矩形を設定することができる上に、複数個のターゲットクラスタの外接矩形における角を１つの軸上に写像したときの度数に基づいて、外接矩形の角度を検出するから、比較的簡単な処理ながら文字列の傾きを正確に求めることができる。
【００２８】
請求項１０の発明は、請求項１ないし請求項９の発明において、前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から既知である文字・図形の内側向きの明度の変化方向の一直線上を探索して得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする。
【００２９】
この方法によれば、濃淡画像から求めた輪郭線を用いて骨格線を抽出するから、認識対象として入力された画像に明度のむらがある場合のように２値化すると文字・図形の情報が正常に抽出できなくなるような場合であっても、正しい骨格線を抽出することができる。
【００３０】
請求項１１の発明は、請求項１ないし請求項９の発明において、前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から既知である文字・図形の内側向きの明度の変化方向の一直線上を探索して規定の距離範囲内において得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする。
【００３１】
この方法によれば、濃淡画像から求めた輪郭線を用いて骨格線を抽出するから、認識対象として入力された画像に明度のむらがある場合のように２値化すると文字・図形の情報が正常に抽出できなくなるような場合であっても、正しい骨格線を抽出することができる。しかも、規定の距離範囲（つまり、規定の幅範囲）の線図形だけを選んで骨格線を抽出するから、文字・図形とは考えられない広幅の領域からは骨格線を抽出することがなく、骨格線を正確に抽出することができる。
【００３２】
請求項１２の発明は、請求項１ないし請求項９の発明において、前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上から選択した起点エッジ点の周囲における明度の変化方向を求め、起点エッジ点から明度の変化方向における両向きの一直線上を探索して規定の距離範囲内において得られる輪郭線上の他の画素を終点エッジ点として求め、起点エッジ点と終点エッジ点との中点を骨格線上の画素とすることを特徴とする。
【００３３】
この方法によれば、濃淡画像から求めた輪郭線を用いて骨格線を抽出するから、認識対象として入力された画像に明度のむらがある場合のように２値化すると文字・図形の情報が正常に抽出できなくなるような場合であっても、正しい骨格線を抽出することができる。しかも、輪郭線の両側に骨格線を探索するから、白文字か黒文字かにかかわらず骨格線を抽出することができる。
【００３４】
請求項１３の発明は、請求項１ないし請求項９の発明において、前記骨格線を抽出するにあたり、濃淡画像を用いて文字・図形の輪郭線を抽出し、輪郭線上の画素の周囲における明度の変化方向を求め、明度の勾配が最大である２方向のうちの少なくとも一方に輪郭線を膨張させる膨張処理を行い、異なる２方向から膨張してきた画素が衝突する画素を骨格線上の画素とすることを特徴とする。
【００３５】
この方法によれば、濃淡画像から求めた輪郭線上の画素を膨張させて骨格線を抽出するから連続した骨格線を抽出することができる。すなわち、請求項１０〜１２のように輪郭線から選択した起点エッジ点を選択する場合には、得られる骨格線は不連続になるから補間処理が必要になるが、膨張処理で骨格線を求めることにより補間することなく連続した骨格線が得られる。しかも、認識対象として入力された画像に明度のむらがある場合のように２値化すると文字・図形の情報が正常に抽出できなくなるような場合であっても、正しい骨格線を抽出することができる
【発明の効果】
【００３６】
本発明によれば、認識対象となる文字・図形および認識対象に照合する文字・図形を単純形状の近似線の集合であるターゲットクラスタおよびマスタクラスタとして表現しておき、認識対象として入力された文字・図形の画像については近似線の距離を評価することによって１単位として扱う近似線群をターゲットクラスタとしているから、たとえばドットにより表現されている文字・図形、かすれた文字・図形、分断された文字・図形であってもターゲットクラスタの１単位として扱うことが可能になり、従来方法では認識できなかったこれらの文字・図形の認識が可能になるという利点がある。また、ターゲットクラスタについて設定した外接矩形に対してマスタクラスタについて設定した外接矩形の位置を合わせて形状類似度を求めるから、通常のパターンマッチングのようにテンプレートを１画素ずつずらして照合する場合に比較すると、画像内において照合を行う領域が制限されることになり、従来構成に比較して処理負荷を大幅に低減させることができ、結果的に高速な処理が期待できるという利点がある。
【発明を実施するための最良の形態】
【００３７】
本実施形態に用いる装置の一例を図２に示す。図示例では、シート状あるいは立体形状の対象物１１の画像を入力する画像入力装置としてＴＶカメラ１２を備える。対象物１１には、文字（従来構成と同様に文字・図形を意味する）が印字あるいは刻印（対象物１１の表面がエンボス状に陥没あるいは隆起）され、ＴＶカメラ１２では文字を含む画像を撮像する。本実施形態は、主として印字あるいは刻印による文字の認識を行うものであり、手書き文字の認識については想定していない。ＴＶカメラ１２で撮像されたアナログ信号の画像は、デジタル画像生成装置１３に入力されてデジタル信号に変換され、デジタル画像生成装置１３からは画素値が濃度値である濃淡画像が生成される。この濃淡画像は記憶装置１４に格納され、記憶装置１４に格納された濃淡画像に対して画像処理装置１５において以下に説明する画像処理が施される。
【００３８】
画像処理装置１５において行う画像処理の基本的な処理手順は、図１に示す通りであって、まずマスタデータ生成登録過程（Ｓ１）においては、文字の認識を行う対象物１１に表記される全文字について、標準になる形状を有した文字を撮像し、文字を含む画像から文字の属性を抽出するとともに文字に属性を対応付けたマスタデータを登録する。マスタデータが登録されるとマスタデータとの照合による文字の認識が可能になるから、まずターゲットデータ抽出過程（Ｓ２）において、文字の認識を行う対象物１１を撮像し、この画像からマスタデータと比較すべき文字の属性をターゲットデータとして抽出する。従来の技術では、ターゲットデータを抽出する前処理としてセグメンテーションを行い、セグメンテーションにより１文字ずつに切り分けているが、本実施形態ではターゲットデータ抽出過程においてはセグメンテーションを行わず、ドット文字、分断文字、不連続部分を含む文字などに対してターゲットデータ抽出過程においてひとまとまりに扱うことで、１文字よりも小さい単位に分割されることを抑制している。つまり、分離された部分同士の距離が規定した閾値以内であれば、分離された部分同士を１つの単位として扱う。このような単位を以下ではクラスタと呼ぶ。ターゲットデータから抽出したクラスタはターゲットクラスタと呼び、ターゲットクラスタは大抵の場合において１文字以上を含み、複数文字を含む場合もある。また、マスタデータでのクラスタは１文字単位であって、マスタデータのクラスタはマスタクラスタと呼ぶ。
【００３９】
マスタデータ生成登録過程においてマスタデータが登録され、ターゲットデータ抽出過程においてターゲットクラスタに区分されたターゲットデータが得られると、ターゲットクラスタにマスタクラスタを照合する形状類似度算出過程（Ｓ３）が実施される。形状類似度算出過程においては、ターゲットクラスタにマスタクラスタの位置を合わせ、ターゲットクラスタとマスタクラスタとの類似度が算出される。ターゲットクラスタとマスタクラスタとの位置合わせには、ターゲットクラスタとマスタクラスタとのそれぞれに設定した外接矩形同士の位置を合わせる。ただし、ターゲットクラスタは複数文字を含む場合があるから、マスタクラスタとターゲットクラスタとの高さ寸法と幅寸法とのそれぞれの寸法比を用いてターゲットクラスタに含まれる文字数を推定し、推定した文字数に応じてターゲットクラスタ内でマスタクラスタを移動させ、それぞれの位置で形状類似度を求める。この処理により複数文字を含むターゲットクラスタにおける文字の切り分けがなされる。なお、上述した各過程は適宜のプログラムをコンピュータで実行することにより実現される。このように、マスタクラスタとターゲットクラスタとの外接矩形の位置を合わせて形状類似度を求めることにより、画像内においてテンプレートを１画素ずつずらして照合する場合に比較すると、照合すべき領域が大幅に少なくなり、処理負荷を軽減することができる。
【００４０】
以下では、上述した個々の過程における処理手順を具体的に説明する。
【００４１】
マスタデータ生成登録過程では、認識対象として標準になる形状を有した文字を印字したシート状の対象物１１、すなわち図３に示すようなマスタシート１１ａをＴＶカメラ１２により撮像する。マスタシート１１ａは、認識対象となる文字を印字したものであって、図示例では「０」〜「９」の数字と「Ａ」「Ｂ」「Ｃ」「Ｒ」のアルファベットとを認識対象にしており、認識対象となる全文字を１枚のマスタシート１１ａに適宜の間隔で配列してある。ただし、マスタシート１１ａは１枚に限らず、複数毎のマスタシート１１ａを順に撮像するようにしてもよい。マスタシート１１ａを撮像した画像からは、以下の手順で各文字の構造に関する特徴量を属性に持つ単位図形であるクラスタ（以下、「マスタクラスタ」と呼ぶ）が生成される。マスタクラスタには属性としてのマスタデータが対応付けられる。
【００４２】
マスタデータ生成登録過程では、図２に示すように、マスタシート１１ａの画像について１文字単位の領域を指定する（Ｓ１１）。領域の指定は、マスタシート１１ａの画像をＣＲＴのようなディスプレイ装置の画面上に表示し、マウスのようなポインティングデバイスを用いてオペレータが手作業で行う。すなわち、マスタデータを作成する際には、オペレータの指示により１文字の範囲を画像処理装置１５に認識させる。１文字単位の領域を指定した後、各領域ごとに濃度値を適宜の閾値で２値化し（Ｓ１２）、２値画像から骨格線を抽出する（Ｓ１３）。骨格線の抽出には、Hilditch法のような周知の技術を用いる。図３に示したマスタシート１１ａにおいて下段右端の「Ｒ」の画像から骨格線を抽出すると図５のような２値の骨格線画像が得られる。
【００４３】
１文字単位の骨格線が抽出されると、各文字単位の骨格線について特徴量としてのマスタデータが抽出される。マスタデータの作成にあたっては、まず、骨格線画像において１文字単位の領域内をラスタ走査し、骨格線から端点と分岐点（交差点を含む）とをノードとして抽出する（Ｓ１４）。たとえば、図５（ａ）の骨格線画像についてノードを抽出すると、図５（ｂ）のように、端点ｔ１，ｔ２と分岐点ｊ１，ｊ２とが抽出される。ノードの抽出後には、各ノード間を結ぶ線要素を抽出する（Ｓ１５）。すなわち、各端点ｔ１，ｔ２と各分岐点ｊ１，ｊ２とをそれぞれ始点として他の端点ｔ１，ｔ２または他の分岐点ｊ１，ｊ２に到達するまで線の追跡を行い（Ｓ１５ｂ）、線要素ｅ１〜ｅ４を抽出して記録する（Ｓ１５ｃ）。線要素ｅ１〜ｅ４は、一端が開いている場合には、他の端点ｔ１，ｔ２または分岐点ｊ１，ｊ２に到達するまでの追跡経路を１つの線要素とし（たとえば、線要素ｅ３，ｅ４）、両端が閉じている場合は始点となった端点ｔ１，ｔ２または分岐点ｊ１，ｊ２に到達するまでの追跡経路を１つの線要素とする（たとえば、線要素ｅ１，ｅ２）。追跡を終了したノードが端点ｔ１，ｔ２であれば追跡を終了し、追跡を行っていない端点ｔ１，ｔ２から追跡を行い、また、追跡を終了したノードが分岐点ｊ１，ｊ２であれば、当該分岐点ｔ１，ｔ２からさらに追跡する（Ｓ１５ａ，Ｓ１５ｄ）。
【００４４】
上述のようにして線要素ｅ１〜ｅ４が抽出されると、各線要素ｅ１〜ｅ４を単純形状（直線、楕円のような幾何形状）である「近似線」の集合として近似する。ここでは、単純形状として簡単な数式で表される近似線を用いる。また、近似線としては、直線と楕円の一部（以下、「楕円弧」と呼ぶ）との２種類を用いる。このように近似線として直線と楕円弧とを用いることによって、ベジェ曲線やスプライン曲線を用いる場合に比較して近似線の表現のためのパラメータを少なくすることができ、種々演算に対する処理負荷も小さくなる。図５（ｂ）に示す形状では、線要素ｅ１は、「Ｒ」の文字の左上角を形成する２本の直線と、上辺の直線の右端から分岐点ｊ２までの１本の楕円弧とで近似することができる。つまり、図５（ｃ）のように、線要素ｅ１を２本の直線である近似線ｌ１，ｌ２と１本の楕円弧である近似線ｌ３とで近似し、直線である２本の近似線ｌ１，ｌ２を接続する屈曲点ｃ１と、直線である一方の近似線ｌ２に楕円弧である他方の近似線ｌ３と接続する線接続点ｄ１とをノードとして導入する。線要素ｅ２〜ｅ４は直線であるから、そのまま近似線ｌ４〜ｌ６に用いる。
【００４５】
本発明におけるクラスタは各文字単位の骨格線からなる図形であって、クラスタの構造は、近似線ｌ１〜ｌ６とノード（端点ｔ１，ｔ２、分岐点ｊ１，ｊ２、屈曲点ｃ１、線接続点ｄ１）との属性で表される。すなわち、「Ｒ」の文字に関するマスタクラスタｍｃは、６本の近似線ｌ１〜ｌ６と６個のノード（端点ｔ１，ｔ２、分岐点ｊ１，ｊ２、屈曲点ｃ１、線接続点ｄ１）との組からなる図形であって、マスタクラスタｍｃには、１つのノード（たとえば、左上のノードである屈曲点ｃ１）を基準にした相対座標を用いて表した各ノードの座標および各近似線ｌ１〜ｌ６のパラメータが対応付けられる。楕円弧の近似線ｌ３が存在する場合には楕円の中心もノードに含まれ、また領域内に孤立点（たとえば、「ｉ」の文字の上の点）が含まれる場合には孤立点もノードになる。ノードの座標はノードの識別符号（ノード名）に対応付けられ、また近似線のパラメータは近似線の識別符号（近似線名）に対応付けられる。さらに、ノード名にはノードに接続される近似線の近似線名が対応付けられる。たとえば、図５（ｃ）に示す分岐点ｊ１には、ノードである分岐点ｊ１に接続されている近似線ｌ１，ｌ４，ｌ５が対応付けられる。また、近似線名には近似線の両端のノード名が対応付けられる。たとえば、図５（ｃ）に示す近似線ｌ２には、近似線ｌ２の両端のノードである屈曲点ｃ１と線接続点ｄ１とが対応付けられる。上述した近似線のパラメータとは、近似線がαｘ＋βｙ−１＝０で表される直線であるときには係数α、βを意味し、近似線がａｘ２＋ｂｙ２＋ｃｘｙ＋ｄｘ＋ｅｙ−１＝０で表される楕円弧であるときには係数ａ〜ｅを意味する。
【００４６】
以上説明したように、マスタクラスタｍｃには、｛ノード名（ノードの座標、ノードに接続される近似線名）、近似線名（近似線のパラメータ、近似線の両端のノード名）｝の情報が対応付けられる。以下では、ノード名（ノードの座標、ノードに接続される近似線名）を「ノードデータ」と呼び、近似線名（近似線のパラメータ、近似線の両端のノード名）を「近似線データ」と呼び、マスタクラスタｍｃに対応付けたノードデータと近似線データとの組をマスタデータと呼ぶ。図６は図２に示したマスタシート１１ａに表記した文字から生成したマスタクラスタｍｃ１〜ｍｃ１４におけるノード（白丸）を示している。なお、図６では楕円の中心のノードは省略している。
【００４７】
上述のようにして、図４のステップＳ１５で得られた線要素ｅ１〜ｅ４を直線と楕円弧とで近似するとともに、必要に応じて屈曲点、線接続点、孤立点、楕円の中心を抽出し（Ｓ１６）、さらにノードデータおよび近似線データの組からなるクラスタを生成し、このクラスタをマスタクラスタとし、マスタクラスタに対応するマスタデータを登録する（Ｓ１７）。上述の処理は各文字単位で行い、マスタシート１１ａを撮像して得たすべての文字についてマスタクラスタを生成し、マスタデータを登録すれば（Ｓ１８）、マスタデータ生成登録過程を終了する。
【００４８】
以上説明したように、骨格線からノードと近似線とを抽出し、上述したノードデータおよび近似線データの組をマスタデータに用いているから、比較的少ないデータ量で文字の構造を記述することができ、しかも近似線が数式で表されているから、後述する形状類似度算出過程において回転とスケールと変形とに関する補正を行う際に、近似線のパラメータを補正するだけで対応でき、個々の画素に対して補正を行う必要がなく処理が簡単になる。
【００４９】
次に、認識対象の文字からクラスタを抽出するとともにマスタデータと照合するターゲットデータを抽出するターゲットデータ抽出過程について説明する。ターゲットデータ抽出過程では、認識対象である文字を印字したシート状の対象物１１、すなわち図７に示すようなターゲットシート１１ｂをＴＶカメラ１２により撮像する。図示例では、ターゲットシート１１ｂに、「０３  ０６  ２５」と「３Ａ８７Ｂ」の各文字列が上下２段に表記されている。また、上段の左側３文字である「０３０」はかすれ文字かつ左右に２分された分断文字になっている。すなわち、これらの３文字は、マスタシート１１ａにおいては、いずれも連続した線からなる１要素を持つ文字であるが、ターゲットシート１１ｂでは連続すべき部分が不連続に分断されており、２要素の文字になっている。さらに、上段の中央の２文字である「０６」は接触した文字（以下、「接触文字」という）になっている。すなわち、これらの文字は、２文字であるが、接触によって１文字と誤認される可能性を有している。
【００５０】
ターゲット抽出過程においては、オペレータが１文字の範囲を指定する手作業はなく、図８に示すように、ＴＶカメラ１２で撮像した画像の全体を２値化し（Ｓ２１）、この２値画像から骨格線を抽出する（Ｓ２２）。この骨格線画像に対して、マスタデータ生成登録過程と同様に、端点および分岐点を抽出し（Ｓ２３）、さらに同様の手順（Ｓ２４ａ〜Ｓ２４ｄ）により線要素を抽出する（Ｓ２４）。また、線要素を直線および楕円弧で近似した近似線を抽出し、さらに屈曲点、孤立点、楕円の中心を含むノードを抽出する（Ｓ２５）。すなわち、クラスタの要素となるノードおよび近似線を、セグメンテーションを行うことなく抽出する。図７に示したターゲットシート１１ｂに対しては、図９（ａ）のようにノード（白丸で表している）と近似線とを抽出することができる。マスタデータと同様に、ノードには座標および近似線名が対応付けられ、近似線にはパラメータおよびノード名が対応付けられる。つまり、ノードデータおよび近似線データが生成される。
【００５１】
ただし、図７に示したターゲットシート１１ｂに表記された文字には、かすれ文字、分断文字、接触文字が含まれているから、上述のようにして得られたノードデータおよび近似線データは、１文字単位ではなく、１文字が複数に分割されていたり、複数文字が１つに結合されていたりすることがある。すなわち、セグメンテーションを行っていないから、ノードデータと近似線データとの組が１文字分であることが保証されないものであり、このままマスタデータと照合しても、対応するものを見出すことができず、誤ったカテゴリに対応付けられることになる。ただし、接触文字については、後述する別の過程で各文字に分離可能であるから、ターゲットデータ抽出過程では処理対象にしない。
【００５２】
そこで、マスタデータとの照合を可能とするために、ターゲットシート１１ｂから得たノードデータおよび近似線データを用いて１つの単位として扱うノードデータおよび近似線データごとにまとめたターゲットクラスタを生成する。この処理は、図８においてステップＳ２６とステップＳ２７とで表される手順で行われる。まず、適宜に選択したノードを起点ノードとし（Ｓ２６ｂ）、起点ノードを一端とする近似線の他端のノードを検出する（Ｓ２６ｄ）。他端のノードの種類を端点と分岐点とその他に分類し（Ｓ２６ｅ）、端点であれば起点ノードに接続された別の近似線について同様の処理を行い（Ｓ２６ｃ）、分岐点であれば当該分岐点を新たな起点ノードにし（Ｓ２６ｇ）、同様の処理を行う。また、他端のノードが端点でも分岐点でもない場合には、当該ノードを新たな起点ノードにし（Ｓ２６ｆ）、当該ノードが一端に接続された近似線の他端のノードについて種類を分類する。この処理を行うと最初に選択した起点ノードに対して近似線を介して接続されているすべてのノードを抽出することができる。ただし、最初に選択した起点ノードと他のノードとの間には近似線が何本介在していてもよい。したがって、上述の処理が未処理である近似線がなくなれば（Ｓ２６ｃ）、最初に選択した起点ノードを含み１文字分とみなされるノードデータおよび近似線データの組が生成されるから、このノードデータおよび近似線データの組をクラスタ候補として一次的に記憶する（Ｓ２６ｈ）。クラスタ候補の生成および記憶の作業は画像内のすべてのノードがいずれかのクラスタ候補に含まれるようになるまで繰り返される（Ｓ２６ａ）。図９（ａ）に示すようにノードおよび近似線を抽出すると、図９（ｂ）のようにクラスタ候補ｐｃ１〜ｐｃ１４が抽出される。図９（ｂ）では各クラスタ候補ｐｃ１〜ｐｃ１４を外接矩形で囲んである。
【００５３】
上述のようにして得られるクラスタ候補ｐｃ１〜ｐｃ１４は、図９（ｂ）を見れば明らかなように、必ずしも１文字分ごとのクラスタを形成していない。そこで、図８に示すステップＳ２７では、１文字分に相当するクラスタ候補を結合する処理を行う。クラスタ候補ｐｃ１〜ｐｃ１４を結合するか否かは、各一対のクラスタ候補ｐｃ１〜ｐｃ１４に含まれるノードおよび近似線の距離によって評価する。すなわち、各クラスタ候補ｐｃ１〜ｐｃ１４から２個のクラスタ候補ｐｃ１〜ｐｃ１４を抽出し、互いに他方のクラスタ候補ｐｃ１〜ｐｃ１４に含まれるすべてのノード間の距離と近似線間の距離との最短距離を求める（Ｓ２７ｂ）。この最短距離が規定した閾値以下であるときには（Ｓ２７ｃ）、両クラスタ候補ｐｃ１〜ｐｃ１４は１つの単位として扱うべきであると判断し、両クラスタ候補ｐｃ１〜ｐｃ１４を１つのクラスタとして扱ってターゲットデータとして登録する（Ｓ２７ｅ）。また、上述した最短距離が規定した閾値よりも大きいときには、両クラスタ候補ｐｃ１〜ｐｃ１４は各別の文字と判断し、各別のクラスタとして扱ってターゲットデータを登録する（Ｓ２７ｄ）。たとえば、図９（ｂ）のクラスタ候補ｐｃ３，ｐｃ５におけるノード間の最短距離が閾値よりも小さくなるように閾値を設定することによって、両クラスタ候補ｐｃ３、ｐｃ５を、図９（ｃ）のように１つの単位として扱うことになる。ただし、クラスタ候補ｐｃ２，ｐｃ３のようにノードと近似線との距離が近い場合に、複数文字が１文字として扱われる場合があり、図９（ｃ）のように、クラスタ候補ｐｃ１〜ｐｃ４の評価により得られるターゲットクラスタｔｃ１〜ｔｃ９の一部には複数文字を含む場合が生じる。
【００５４】
上述した処理によって、クラスタ候補の結合を行うことにより、「ｉ」や「は」のように不連続に分離された部位を含む文字、食品の賞味期限ないし消費期限の印字などにおいて広く用いられているドット文字のように、１つの文字が隣接した２個以上の部分で構成されている場合であっても、１文字のクラスタにまとめることが可能になる。このことは、かすれ文字や分断文字であっても同様である。
【００５５】
次に、形状類似度算出過程では、ターゲットデータにマスタデータを照合して両者の骨格線の形状の類似度を評価することにより、ターゲットデータに含まれる各クラスタをマスタクラスタのカテゴリに対応付ける処理が行われる。つまり、マスタデータに含まれるいずれかの文字にターゲットデータを対応付けることによって、ターゲットデータに含まれる文字の認識を行う。
【００５６】
形状類似度算出過程では、図１０に示すように、ターゲットクラスタとマスタクラスタとの位置合わせを行い、ターゲットクラスタに対応するターゲットデータと、マスタクラスタに対応するマスタデータとを照合する。すなわち、ターゲットクラスタとマスタクラスタとの位置合わせの後に、ターゲットデータとマスタデータとを用いて近似線間の距離を算出し、この距離をターゲットクラスタとマスタクラスタとの形状に関する類似度の評価値に用いる。
【００５７】
マスタクラスタは１文字単位の図形であり、ターゲットクラスタは１文字単位と推定される図形であるから、ターゲットクラスタとマスタクラスタとの位置合わせには、まずターゲットクラスタとマスタクラスタとを重ねたときに、重なり面積を最大にするように位置を合わせる。そこで、ターゲットクラスタとマスタクラスタとの位置および大きさを二次元的に定義し大きさを比較するために、ターゲットクラスタおよびマスタクラスタについてそれぞれ外接矩形を求める（Ｓ３１）。ターゲットクラスタおよびマスタクラスタに対して外接矩形を設定するには、各ターゲットクラスタあるいは各マスタクラスタに含まれるすべてのノードデータおよび近似線データについて、Ｘ方向とＹ方向との最大値および最小値をそれぞれ求め、（Ｘ方向の最小値、Ｙ方向の最小値）で表される座標位置を左上点とし、（Ｘ方向の最大値、Ｙ方向の最大値）で表される座標位置を右下線とする矩形を生成する。さらに、ターゲットクラスタおよびマスタクラスタについて設定された外接矩形を重ね合わせたときに、重なり面積が最大になるように位置を合わせる。この方法で位置合わせが可能になるのは、ターゲットクラスタとマスタクラスタとについて、同じ文字であれば高さおよび幅の寸法がほぼ一致し、またターゲットクラスタとマスタクラスタとの書体に大きな差異がないという条件を満たすときである。後者の条件は、工場製品において対象物１１に印刷された文字や刻印された文字であれば容易に満たすことができる。
【００５８】
もっとも、図９（ｃ）に示したように、１つのターゲットクラスタｔｃ１，ｔｃ２に複数文字（図示例では２文字）を含んでいる場合があるから、上記条件のうち前者の条件が満たされないことがある。そこで、ターゲットクラスタとマスタクラスタとの高さ寸法と幅寸法とについてそれぞれ比を求め、求めた比を高さ方向あるいは幅方向における文字数とみなす（Ｓ３２）。ただし、文字数は整数値であるから求めた比は四捨五入する。たとえば、図１１に示すように、図９（ｃ）に示したターゲットクラスタｔｃ１と、図６に示したマスタクラスタｍｃ４とを照合する場合では、ターゲットクラスタｔｃ１の幅寸法（左右寸法）がマスタクラスタｍｃ４の略２倍であるから、ターゲットクラスタｔｃ１に２文字含まれていると推定される。
【００５９】
上述のようにしてターゲットクラスタの高さ寸法および幅寸法をそれぞれマスタクラスタの高さ寸法および幅寸法で除算することにより得られた値は、着目する１つのターゲットクラスに対してマスタクラスタの位置合わせが何回必要であるかを示している。次に、ターゲットクラスタとマスタクラスタとの形状の類似度を求める（Ｓ３４）。類似度を求めるには、まずターゲットクラスタにマスタクラスタの位置を合わせる（Ｓ３４ａ）。ここで、上述のように求めた値が２以上であれば、以下のようにして形状の類似度を評価した後、ターゲットクラスタに対してマスタクラスタを１文字分だけ移動させて形状の類似度を評価する処理を繰り返す。つまり、類似度の評価はターゲットクラスタに含まれると推定される文字数分（上述した比で表される個数分）の回数だけ行われる。
【００６０】
たとえば、図１１に示す例では、「０」と「３」との文字が１つのターゲットクラスタｔｃ１に含まれており、高さ寸法はマスタクラスタｍｃ４と略等しいが、幅寸法がマスタクラスタｍｃ４の略２倍であるから、ターゲットクラスタｔｃ１のクラスタには２文字分のデータが含まれていると推定される。そこで、ターゲットクラスタｔｃ１の左半分にマスタクラスタｍｃ４を位置合わせして類似度を評価し、さらにターゲットクラスタｔｃ１の右半分にマスタクラスタｍｃ４を位置合わせして類似度を評価する。図示例ではマスタクラスタｍｃ４をターゲットクラスタｔｃ１の右半分に位置合わせしたときに類似度が高くなるから、類似度に適宜の閾値を設定しておけば、ターゲットクラスタｔｃ１を「０」の部分と「３」の部分に分割することが可能になる。
【００６１】
ところで、ターゲットクラスタは通常は１文字以上の領域になるが、１文字分のターゲットクラスタが複数個に分断されている場合もある。この場合には、上述のようにして比を求めると１より小さくなるから、比が１より小さくなったときには、着目しているターゲットクラスタの周辺において比が略整数値にならず、着目しているターゲットクラスタと結合すれば比が略整数値になるようなターゲットクラスタを探し、そのようなターゲットクラスタが存在していれば、着目しているターゲットクラスタに融合し、マスタクラスタとの照合を行う。
【００６２】
ターゲットクラスタとマスタクラスタとの形状の類似度の評価には、図１２に示すように、マスタクラスタに含まれる近似線（破線）とターゲットクラスタに含まれる近似線（二点鎖線）との各部位での距離を求め、当該距離が規定値ｄ以下である（つまり、実質的に重なっているとみなしてよい距離の）近似線の総延長Ｔ１と、ターゲットクラスタに含まれる近似線とマスタクラスタに含まれる近似線との間の距離の平均値Ｄａとを用いる。ここで、マスタクラスタに含まれる近似線の総延長をＭ１とすれば、形状類似度Ｓａを次式で表すことができる（Ｓ３４ｂ，Ｓ３４ｃ）。
Ｓａ＝（１−Ｄａ／ｄ）×（Ｔ１／Ｍ１）
上式から明らかなように、形状類似度Ｓａは、マスタクラスタに含まれる近似線とターゲットクラスタの近似線とが距離ｄ内である近接部位の平均距離の距離ｄに対する割合が小さいほど大きく（上式では距離ｄに対する平均距離Ｄａの割合を１から減じた値を接近程度の評価値に用いている）、距離ｄ内である近接部位の総延長がマスタクラスタの近似線の総延長に占める割合が大きいほど大きくなる。また、形状類似度Ｓａの値は、文字を構成する近似線の数や長さにかかわらず、０〜１の間の値をとるように正規化されるから、異なる文字に対しても統一された基準で認識結果の判断が可能になる。ここに、着目するターゲットクラスタに対して各マスタクラスタごとに上述の処理を繰り返すことにより得られる形状類似度Ｓａのうち値（スコア）が最大になるものを求める（Ｓ３３、Ｓ３５〜Ｓ３８）。
【００６３】
上述のようにして形状類似度Ｓａを求めることにより、ターゲットクラスタ内に文字を構成する線以外の線（すなわち、マスタクラスタにはない線）が含まれていたとしても、通常は近似線の距離同士の距離が大きくなり、形状類似度Ｓａに影響を与えないから、文字にノイズが重畳しているような場合であっても、文字の欠落や文字違いは的確に判断できる。もっとも、たとえば、光学式文字読取装置（ＯＣＲ）などに用いる場合に、「Ｃ」と「Ｏ」、あるいは「３」と「８」とのように図形的に見ると他の文字の一部になっている場合には、形状類似度Ｓａが比較的大きくなり正しい判断ができない場合がある。このような場合には、ターゲットクラスタ近似線の総延長Ｔａに対する距離ｄ以下の近似線の総延長Ｔ１を上式に乗じた下式を用いるとよい。
Ｓａ＝（１−Ｄａ／ｄ）×（Ｔ１／Ｍ１）×（Ｔ１／Ｔａ）
ところで、上述の手順では、ターゲットクラスタとマスタクラスタとの形状の類似度を求めるために、近似線同士の距離を算出する必要があるから、近似線が数式で表されているとは言え、比較的複雑な計算を必要とし、マスタクラスタの種類が少ない場合には処理負荷が大幅に増加することはないが、光学式文字読取装置のように、マスタクラスタの種類が多く類似度を求める対象が多い場合には処理負荷が非常に大きくなると考えられる。そこで、図１０のステップＳ３４ａにおいて外接矩形を用いた位置合わせを行った後、ステップＳ３４ｂに移行せずに、前処理としてターゲットクラスタとマスタクラスタとのノードの類似度を評価する。すなわち、マスタクラスタに含まれるノード数をＭｎ、マスタクラスタに含まれるノードから距離ｄ以内に存在するターゲットクラスタのノード数をＴｎ、当該ターゲットクラスタのノードとマスタクラスタに含まれるノードとの距離の平均値をＤｎとして、下式で表されるノード類似度Ｓｄを求め、ノード類似度Ｓｄが規定した閾値以下であるときには、当該マスタクラスタについては形状類似度Ｓａを求める処理を行わないようにする。
Ｓｄ＝（１−Ｄｎ／ｄ）×（Ｔｎ／Ｍｎ）
ノード類似度Ｓｄを求める際に用いる距離Ｄｎの平均値はノード（点）間の距離であるから、近似線間の距離を求める演算に比較すると処理負荷が格段に小さくなる。しかも、あらかじめ形状類似度Ｓａの小さいマスタクラスタについては、処理負荷の大きくなる近似線間の距離の演算を回避するから、図１０に示す形状類似度算出過程の全体における処理負荷の大幅な軽減になる。
【００６４】
また、ノード類似度Ｓｄを求める際に、マスタクラスタについて回転とスケールと変形とに関するパラメータを変更して照合を行うことで、マスタクラスタとターゲットクラスタとの間の回転とスケールと変形とに関する補正を行えば、形状類似度Ｓａを求める際にターゲットクラスタにおいて文字が回転していたり、マスタクラスタとのスケールが異なっていたり、マスタクラスタに対して変形が生じていたりする場合でも正しく認識することができる。
【００６５】
なお、上述した実施形態では、ノードの種類（端点、屈曲点、分岐点、線接続点、孤立点、楕円中心）を考慮していないが、分断文字や接触文字でなければ、ターゲットクラスタに含まれる文字とマスタクラスタの文字とはトポロジに共通部分が多いはずであるから、ノード類似度Ｓｄを求める際には、マスタクラスタに含まれるノードから距離ｄ以内に存在するターゲットクラスタのノードとして同種類のノードのみに着目すれば、ノード類似度Ｓｄの信頼性を向上させることができる。つまり、形状類似度を求める前に、マスタクラスタの各ノードの種類と、当該ノードから規定の距離範囲内に存在するターゲットクラスタの各ノードの種類とを判断し、マスタクラスタに含まれるノードの少なくとも１個がターゲットクラスタのノードの種類と一致しない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないようにする。このような前処理を行うことにより、形状類似度を求める際の処理負荷が大幅に軽減される。
【００６６】
一方、分断文字や接触文字であって、ターゲットクラスタに含まれる文字とマスタクラスタの文字とのトポロジが異なる場合には、各ノードごとに、周囲の近似線（形状、長さ、方向）、周囲のノードの情報を用いることによって、ノードの種類についてベイズ確率を求め、ノードの照合の際にベイズ確率を用いてノードの種類を評価してもよい。ここに、ノードの種類に関するベイズ確率は、ノードの種類ごとの確率の合計が１００％になるように設定される確率を意味する。以下に、ベイズ確率を用いてノードの種類を推定する方法について説明する。
【００６７】
図１３（ａ）は、ターゲットクラスタに含まれるの文字「３」の一部に分断が生じ、連続すべき線の中間に端点ｔ３，ｔ４が生じ、また、分岐点の近傍に端点ｔ５と屈曲点ｃ２とが生じた例を示している。また、図１３（ｂ）は、ターゲットシート１１ｂに表記された文字「４」が太字であって、骨格線を抽出したときに、上端部の屈曲点となるべき部分にヒゲ状の骨格線が出現し、屈曲点となるべきノードが分岐点ｊ３になり、ヒゲ状の骨格線の先端に端点ｔ６が生じた例を示している。
【００６８】
いま、図１３（ａ）の例に着目すると、２個の端点ｔ３，ｔ４が接近しており、しかも端点ｔ３，ｔ４にそれぞれ接続された近似線ｌ７，ｌ８の接線方向がほぼ一致しているから、両端点ｔ３，ｔ４が連続すると、ノードが存在しないか、ノードが存在するとすればノードの種類は線接続点になると推定できる。また、端点ｔ５と屈曲点ｃ２とについては、比較的長い近似線ｌ９を接続した端点ｔ５が屈曲点ｃ２に近接しているから、端点ｔ５と屈曲点ｃ２とが連続すると、分岐点になると推定できる。ベイズ確率は、上述のような推定の結果で得られるトポロジを文字の元のトポロジとみなし、図１４に示す手順でノードの種類ごとに求められる。なお、上述のような推定には、あらかじめ推定用のルールを決めておく。
【００６９】
ノードの種類の確率を求めるカテゴリ確率計算は、図１４に示すように、まずターゲットクラスタにおいて、２つのノードの距離が規定した閾値Ｄ以内であるものを１つのグループとし（Ｓ４１）、グループの重心位置に仮ノードを設定するとともに、グループ内の各ノードに接続されている近似線の長さ寸法を計測する（Ｓ４２）。また、ノードが端点であって距離Ｄ以内にノードに接続された近似線以外の近似線が存在する場合には（Ｓ４３）、このノードを仮ノードとし、仮ノードに接続されている近似線の長さ寸法と仮ノードに近接する近似線の長さ寸法とを計測する（Ｓ４４）。
【００７０】
次に、各近似線の長さ寸法のうち規定した長さ寸法Ｌ以上の近似線の本数を求め（Ｓ４５）、１本であれば仮ノードが端点である確率を１００％とする（Ｓ４６）。また、２本であれば仮ノードが線接続点である確率をζ／２π、屈曲点である確率を１−ζ／２πとする（Ｓ４７）。さらに、３本以上であれば仮ノードが分岐点である確率を１００％とする。ここに、ζは２本の近似線の間の角度であって、右手系で０＜ζ＜２πの範囲に設定され、線接続点の確率がζ／２πと設定される。
【００７１】
仮ノードについて、端点、屈曲点、線接続点、分岐点の確率を求めた後、グループ内の各ノードについて仮ノードとの距離ｄを求める（Ｓ４９）。この距離ｄと距離Ｄとを用いて、以下のように各ノードのベイズ確率を設定する。すなわち、ノードの各種類ごとの確率を、グループ内のノードが当該種類である確率×（ｄ／Ｄ）＋仮ノードが当該種類である確率×（１−ｄ／Ｄ）という演算で求める。たとえば、孤立点の確率は、グループ内のノードが孤立点である確率×（ｄ／Ｄ）＋仮ノードが孤立点である確率×（１−ｄ／Ｄ）になる。この演算により、図１３（ａ）に示す例では、端点ｔ３，ｔ４は線接続点である確率が高くなり、ｔ５，ｃ２は分岐点である確率が高くなる。また、同様にして図１３（ｂ）に示す例では、分岐点ｊ３，端点ｔ３は屈曲点である確率が高くなる。つまり、文字の本来のトポロジが復元される。
【００７２】
上述のようにして、各ノードごとにノードの種類に関するベイズ確率を求めた場合には、ノード類似度Ｓｄは下式で求める。すなわち、マスタクラスタに含まれるノード数をＭｎ、マスタクラスタに含まれるノードから距離ｄ以内に存在するターゲットクラスタのノード数をＴｎ、当該ターゲットクラスタのノードとマスタクラスタに含まれるノードとの距離をｄｓ、マスタクラスタのノードの種類と同じ種類に属するターゲットクラスタのノードのベイズ確率をｐｓとして、ノード類似度Ｓｄを下式で表す。
Ｓｄ＝Σ［｛（１−ｄｓ／ｄ）×ｐｓ｝／Ｔｎ］×（Ｔｎ／Ｍｎ）
上式を用いてノード類似度Ｓｄを求めると、マスタクラスタとターゲットクラスタとにおいて、人には同文字と認識される形状であるにもかかわらず、トポロジが不完全にしか一致していない場合であっても、正しいノードの種類を推定することが可能になる。
【００７３】
ノード類似度を求めることによってマスタクラスタのノードから規定の距離範囲ｄｓ内に存在するターゲットクラスタのノードとのノード類似度を求めることができるから、マスタクラスタに含まれるノードの少なくとも１個に対応するターゲットクラスタのノード類似度が規定の閾値以上でない場合には、当該マスタクラスタとターゲットクラスタとの形状類似度を求めないようにする。このような前処理によって形状類似度を求める回数を大幅に低減することができ、処理負荷の軽減になる。
【００７４】
ところで、上述した形状類似度Ｓａの演算の際には、マスタクラスタおよびターゲットクラスタに関してそれぞれ設定した外接矩形の位置を合わせているが、マスタクラスタとターゲットクラスタとは各別に外接矩形を設定するから、マスタクラスタとターゲットクラスタとの外接矩形の位置を合わせても、図１５に示すように、両者に含まれる文字が完全には重ならずにずれていることがある（図１５の破線がマスタクラスタの文字、実線がターゲットクラスタの文字）。文字同士の位置のずれが大きいときには、両者の近似線同士の距離が比較的大きくなるから、形状類似度算出過程において求める形状類似度Ｓａの値（スコア）が小さくなり、形状類似度Ｓａが小さくなる可能性がある。また、上述したように、ターゲットクラスタに含まれる文字は、マスタクラスタに含まれる文字に対して回転していたり、スケールが異なっていたり、変形していたりすることがあり、このような場合にも外接矩形の位置を合わせただけでは、形状類似度Ｓａが小さくなる可能性がある。
【００７５】
このような問題を解消するには、外接矩形では大まかな位置合わせに用い、さらに外接矩形を相対的に上下左右に移動させながら形状類似度Ｓａを複数回求めることにより、形状類似度Ｓａが最大になる位置を採用することが考えられる。しかしながら、１つの文字について形状類似度Ｓａを複数回求めることが必要になるから、形状類似度Ｓａを求める回数が爆発的に増大し、処理負荷が大きくなるという問題が生じる。
【００７６】
そこで、図２３に示すように、マスタクラスタの文字の近似線上で少なくとも６点のサンプル点ｓｐ１〜ｓｐ６を設定し、各サンプル点ｓｐ１〜ｓｐ６から当該近似線の法線方向においてもっとも近い距離にあるターゲットクラスタの文字の近似線の上の対応点ｔｐ１〜ｔｐ６を求め、サンプル点ｓｐ１〜ｓｐ６の座標と対応点ｔｐ１〜ｔｐ６の座標とを数１で示すアフィン変換の変換式に適用し、マスタクラスタに含まれる文字をターゲットクラスタに含まれる文字に重ね合わせるようにアフィン変換の変換式のパラメータα１，β１，α２，β２，ｄｘ，ｄｙを最小自乗法で決定する。なお、ノードにおいては近似線の接線方向を定義できないから、サンプル点ｓｐ１〜ｓｐ６は近似線の上において適宜の間隔で設定する。以下に示す数１、数２において、Ｘ，Ｙはターゲットクラスタ上の座標を示し、ｘ，ｙはマスタクラスタ上の座標を示す。
【００７７】
【数１】
2005182660.tif 000003
【００７８】
数１に示すアフィン変換の変換式は、Ｘ軸回りおよびＹ軸回りの回転、Ｘ軸方向およびＹ軸方向の拡大縮小（スケール）、Ｘ軸方向およびＹ軸方向の位置の合計６自由度のパラメータについての座標変換であるから、数１の６個のパラメータα１，β１，α２，β２，ｄｘ，ｄｙを最小自乗法で求めることにより、回転の補正とスケールの補正と文字の位置とのほか、文字が斜体になっているような線形歪の補正も可能になる。なお、文字が斜体になっているような線形歪を考慮しないのであれば、数２のようにスケールα、回転角θ、移動量（ｄｘ，ｄｙ）の合計４自由度のヘルマート変換のパラメータを求めてもよい。ヘルマート変換を行う場合には、サンプル点は４個以上あればよい。
【００７９】
【数２】
2005182660.tif 000004
【００８０】
上述の方法において、サンプル点をマスタクラスタに含まれる近似線ごとに設定すれば、ターゲットクラスタに含まれる文字の一部分の変形にも対応することが可能である。たとえば、文字「８」について、マスタクラスタでは上下の「○」が同じ大きさに設定され、ターゲットクラスタでは上の「○」が下の「○」よりも小さいとすれば、マスタクラスタの全体のスケールの変更ではターゲットクラスタに重ね合わせることができない。このような場合に、上の「○」の近似線と下の「○」の近似線とについて、それぞれサンプル点を設定すれば、上の「○」と下の「○」とを各別に拡大縮小することが可能になる。ただし、文字を構成する近似線ごとにアフィン変換（ないしヘルマート変換）が施されることになり、異なる近似線を接続するノードが整合しなくなる（同じ位置のノードであるにもかかわらず、ノードの位置がずれる）可能性があるから、このような場合には補間処理を行ってノードの座標データを補正する必要が生じる。なお、アフィン変換（ないしヘルマート変換）による補正を行った後は、形状類似度Ｓａは当然ながら再計算することになる。
【００８１】
次に、上述のようにして求めた形状類似度Ｓａを用いてターゲットシート１１ｂを撮像した画像に含まれる文字を認識する技術について説明する。この種の文字認識には、ターゲットシート１１ｂを撮像した画像に含まれる各文字をマスタデータのカテゴリに対応付ける場合と、ターゲットシート１１ｂを撮像した画像に含まれる既知の文字が正しく表記されているか否かを検査する場合とがある。前者は文字読取装置（たとえば、ＯＣＲ）に用いる技術であって、この場合には、１つのターゲットクラスタに対して複数のマスタクラスタをそれぞれ位置合わせして形状類似度をそれぞれ求め、形状類似度のもっとも大きいマスタクラスタを、ターゲットクラスタの画像の当該位置におけるカテゴリに対応付けることができる。一方、文字の表記を検査する場合には、１つのターゲットクラスタに当該位置に表記されていなければならない文字に対応するマスタクラスタを位置合わせして形状類似度を求め、形状類似度が規定した閾値以上であるかどうかを評価することにより文字が正しく表記されているか否かを検査することができる。
【００８２】
ところで、文字の表記が正しいか否かを検査する場合であって、表記されている文字が複数個であり、かつ文字の配列が既知である場合には、以下の方法によりターゲットクラスタにマスタクラスタの位置を合わせるようにすれば位置合わせが容易になる。
【００８３】
いま、図１６に示すように、ＴＶカメラ１２で撮像する対象物１１に文字が上下２段に表記され、上段には「２００３．１０．０２」という日付を示す文字列が表記され、下段には「ＡＢ８５６０」という文字列が表記されているものとする。この種の表記は工業製品などにおいてなされており、表記された文字について、文字種、文字サイズ、文字間隔、行間隔、文字数のような文字の配列に関する情報は既知と考えられる。この場合には、まず基準となる文字列を表記した対象物１１をマスタとして、図１７に示すように、対象物１１を撮像した画像からオペレータが１文字ずつ切り出したマスタクラスタ（図１７に破線で示す外接矩形の領域がそれぞれマスタクラスタになる）にノードデータおよび近似線データを対応付けた文字列マスタを生成する。文字列マスタでは、文字の配列に関する情報も保存される。
【００８４】
上述の例では、文字列に含まれる各文字の位置は拘束されているから、文字列マスタと検査対象である文字列とに含まれる複数の文字の位置を対応付けることによって、他の文字の対応付けが可能になる。たとえば、図１８（ａ）に示す文字列マスタにおいて、異なる２文字以上（図示例では２文字）の外接矩形の角位置から１点ずつ代表点Ｐ１，Ｐ２を選択し、ターゲットクラスタについては、図１８（ｂ）〜（ｄ）に示すように、２個のターゲットクラスタを選択するすべての組合せについて、各ターゲットクラスタの角位置に文字列マスタの代表点Ｐ１，Ｐ２を重ね、文字列マスタとターゲットクラスタとの外接矩形の重なり面積が大きくなるように、文字列マスタを回転させたり、スケールを調節したり、位置を変化させたりする。つまり、文字列マスタに対してアフィン変換（ないしヘルマート変換）を施す。このようにして、文字列マスタとターゲットクラスタとにそれぞれ設定した外接矩形（文字列マスタの外接矩形を破線で示し、ターゲットクラスタの外接矩形を実線で示している）の重なり面積が最大になる位置（図１８（ｃ）の位置）を検出すれば、ターゲットクラスタと文字列マスタとを容易に照合することができる。
【００８５】
文字列マスタの代表点Ｐ１，Ｐ２は、文字列マスタに含まれる全文字を包含する外接矩形のうち対角線上に位置する２個のマスタクラスタの角部の２点を選択するのが望ましい。このように選択した代表点Ｐ１，Ｐ２は、文字列マスタに含まれる文字列クラスタから選択可能な２点のうちで最大距離になり、位置合わせの精度が高くなるからある。
【００８６】
なお、文字列マスタをターゲットクラスタに位置合わせする際に、検査対象となる文字列全体が文字列マスタに対して回転している場合には、あらかじめ回転角度を求めることによって、回転に関する補正が不要になり、文字列マスタをターゲットクラスタに位置合わせする処理が簡単になる。そこで、図１９（ａ）（ｂ）に示すように、各ターゲットクラスタについて面積が最小になる外接矩形を抽出する。つまり、外接矩形の方向を変化させると外接矩形の面積は変化するのであって、文字の縦横と外接矩形の縦横とが一致するときに外接矩形の面積が最小になると考えられる。そこで、面積が最小になる外接矩形を抽出するのである。このようにして得られた外接矩形は同じ向きを向いていると考えられるから、各ターゲットクラスタの外接矩形の角を適宜方向に写像して度数を求めると、図１９（ａ）のように写像した方向が外接矩形の各辺の方向に一致していない場合には度数の最大値が小さくなるのに対して、図１９（ｂ）のように写像した方向が外接矩形の並ぶ方向（つまり、文字の並ぶ方向）に一致する場合には度数の最大値が大きくなり、複数の明確なピークが現れることになる。したがって、図１９（ｂ）のように度数の最大値が大きく、明確なピークが現れる方向をターゲットクラスタの向きとして求めることができる。要するに、文字列マスタに対するターゲットクラスタの回転角度を知ることができ、文字列マスタをターゲットクラスタに位置合わせする処理での処理負荷が軽減される。なお、写像させる方向は、たとえば１０度間隔で変化させることによって角度の範囲の目安を得た後に、目安が得られた角度の近辺において、さらに小さい角度間隔で変化させるようにすればよい。上述のように、文字列が既知である場合には、文字を個々に認識する場合に比較すると、複数の文字の位置が拘束されていることを利用することで、さらに処理負荷を軽減することができる。
【００８７】
上述した実施形態において、Hilditch法のような技術を用いることを説明したが、背景の明度が均一でないような場合に、文字を背景から分離するための２値化に用いる閾値の設定が難しく、設定された閾値が不適当であると、文字の一部と背景とが区別できなくなるおそれがある。そこで、骨格線を以下の手順で抽出すれば、背景の明度と文字の明度との差が小さい場合でも骨格線を抽出することができる。すなわち、文字程度の幅を有する線図形では、文字を構成している線の幅方向における一方側の輪郭線と他方側の輪郭線とでは明度の変化方向（明度の勾配が最大になる方向）がほぼ逆向きになることを利用して骨格線を抽出するのであって、２値画像からではなく濃淡画像から骨格線を抽出する。
【００８８】
この方法では、まずターゲットシート１１ｂを撮像した画像に対してSobelフィルタなどのエッジ抽出フィルタを用いることにより、図２０に示すように文字の１本の線（「文字線」と呼ぶ）について、幅方向に離間した２本の輪郭線ｋ１，ｋ２を抽出することが可能である。輪郭線ｋ１，ｋ２を求めた後には輪郭線ｋ１，ｋ２上の画素から適宜に起点エッジ点Ｐｓ１，Ｐｓ２，……とするサンプル点を抽出し、起点エッジ点Ｐｓ１，Ｐｓ２，……の周囲における明度の変化方向を求める。ここでは、黒地の背景に白文字である場合を想定する。この場合、起点エッジ点Ｐｓ１，Ｐｓ２，……から文字線の内側に向かう向きは明度が大きくなる向きであるから、起点エッジ点Ｐｓ１，Ｐｓ２，……の周囲で明度の勾配が最大になる向きの一直線上を探索し文字線の反対側の輪郭線に到達した点を終点エッジ点Ｐｅ１，Ｐｅ２，……とする。ここにおいて、白地の背景に黒文字である場合には、文字線の内側に向かう向きは明度が小さくなる向きになる。要するに、起点エッジ点から終点エッジ点への探索は既知である文字の内側向きの明度の変化方向について行う。
【００８９】
起点エッジ点Ｐｓ１，Ｐｓ２，……と終点エッジ点Ｐｅ１，Ｐｅ２，……とは明度の変化によって求めており、閾値を用いて２値化するのではないから、背景と文字との間に明度差があれば検出することができる。図２０（ｂ）に示すように、上述のようにして得られた起点エッジ点Ｐｓ１，Ｐｓ２，……と終点エッジ点Ｐｅ１，Ｐｅ２，……との中点を骨格点Ｐｍ１，Ｐｍ２，……に用いることによって、２値化を行う場合に比較して背景と文字とを分離できる可能性が高くなる。また、得られた骨格点Ｐｍ１，Ｐｍ２，……の間隔が大きい（規定した閾値以上）の場合には、骨格点Ｐｍ１，Ｐｍ２，……の間を直線で結ぶ補間処理を行うことにより骨格線を連続させる。
【００９０】
ここに、起点エッジ点Ｐｓ１，Ｐｓ２，……と終点エッジ点Ｐｅ１，Ｐｅ２，……との距離範囲を制限すれば、認識する文字線の幅を制限することができる。たとえば、回路パターン上に細い線で書かれた文字を読み取るような場合には、回路パターンを文字線と誤認するのを防止することができる。
【００９１】
さらに、上述の手順は文字線の明度の変化方向が一定である場合、すなわち白地の背景に黒文字か黒地の背景に白文字かの場合を想定しているが、文字に対応する部位において白地と黒地との背景が混在しており、文字の明度が白地と黒地との背景の中間値であるような場合には、文字線の明度変化方向が部分的に変化することになり上記手順を適用することができない。
【００９２】
このような場合には、起点エッジ点Ｐｓ１，Ｐｓ２，……に対して文字線の内側の向きを明度の変化では特定できないから、起点エッジ点Ｐｓ１，Ｐｓ２，……から明度の増加する向きと減少する向きとの両方に向かって終点エッジ点Ｐｅ１，Ｐｅ２，……を探索し、起点エッジ点Ｐｓ１，Ｐｓ２，……から終点エッジ点Ｐｅ１，Ｐｅ２，……までの距離の範囲を制限しておいて骨格線を抽出することにより、文字に重なる部位で背景に明暗の関係が反転する場合や、金属のように光沢がある物体に文字が打刻されている場合のように、白地に黒文字か黒字に白抜き文字かを特定できない場合にも骨格線を正しく抽出することができる。
【００９３】
骨格線を抽出する技術としては、輪郭線の抽出後に、輪郭線を明度の変化方向（明度の勾配が最大である方向）を求め、明度の勾配が最大である２方向に輪郭線を膨張させる膨張処理を行い、異なる２方向から膨張してきた画素が衝突した画素位置を骨格線上の画素位置としてもよい。
【００９４】
なお、上述した実施形態では、基準となる文字を表記したマスタシート１１ａをＴＶカメラ１２で撮像した画像からマスタデータを生成する例を示したが、文字のフォントデータからマスタデータを生成したり、ＣＡＤなどで作成された文字データからマスタデータを生成したりすることも可能である。フォントデータやＣＡＤなどで作成した文字データを用いてマスタデータを作成すれば、画像からマスタデータを生成する場合に比較すると不要なノイズが混入せず、マスタデータの生成が容易になる。
【図面の簡単な説明】
【００９５】
【図１】本発明の実施形態の動作説明図である。
【図２】同上に用いる装置の概略構成図である。
【図３】同上に用いるマスタシートを示す図である。
【図４】同上におけるマスタデータ生成登録過程の動作説明図である。
【図５】同上の動作説明図である。
【図６】同上におけるマスタデータを示す図である。
【図７】同上に用いるターゲットシートを示す図である。
【図８】同上におけるターゲットデータ抽出過程の動作説明図である。
【図９】同上におけるターゲットクラスタの生成過程を示す動作説明図である。
【図１０】同上における形状類似度算出過程を示す動作説明図である。
【図１１】同上の動作説明図である。
【図１２】同上の動作説明図である。
【図１３】同上の動作説明図である。
【図１４】同上におけるカテゴリ確率計算過程を示す動作説明図である。
【図１５】同上の動作説明図である。
【図１６】同上の動作説明図である。
【図１７】同上に用いる文字列マスタを示す図である。
【図１８】同上の動作説明図である。
【図１９】同上の動作説明図である。
【図２０】同上の動作説明図である。
【符号の説明】
【００９６】
１１  対象物
１１ａ  マスタシート
１１ｂ  ターゲットシート
１２  ＴＶカメラ
１３  デジタル画像生成装置
１４  記憶装置
１５  画像処理装置
【図１】
2005182660.tif 000005
【図２】
2005182660.tif 000006
【図３】
2005182660.tif 000007
【図４】
2005182660.tif 000008
【図５】
2005182660.tif 000009
【図６】
2005182660.tif 000010
【図７】
2005182660.tif 000011
【図８】
2005182660.tif 000012
【図９】
2005182660.tif 000013
【図１０】
2005182660.tif 000014
【図１１】
2005182660.tif 000015
【図１２】
2005182660.tif 000016
【図１３】
2005182660.tif 000017
【図１４】
2005182660.tif 000018
【図１５】
2005182660.tif 000019
【図１６】
2005182660.tif 000020
【図１７】
2005182660.tif 000021
【図１８】
2005182660.tif 000022
【図１９】
2005182660.tif 000023
【図２０】
2005182660.tif 000024