(57)【特許請求の範囲】
【請求項１】
文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，
前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，
前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，
前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，
前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップと，
を有することを特徴とする濃淡値文書画像からの特徴抽出方法。
【請求項２】
文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，
前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，
前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，
前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，
前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップと，
前記第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する第６ステップと，
を有することを特徴とする濃淡値文書画像からの特徴抽出方法。
【請求項３】
文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，
前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，
前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，
前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，
前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップと，
前記第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する第６ステップと，
前記第６ステップで抽出された輪郭線を内部輪郭及び外部輪郭に分類する第７ステップと，
ベクトル・ラスター変換の手法を使って，前記内部輪郭及び外部輪郭に基づく輪郭の内部を塗りつぶすことにより２値画像を生成する第８ステップと，
を有することを特徴とする濃淡値文書画像からの特徴抽出方法。
【請求項４】
文書原稿画像を読み取って濃淡値レベルの画像データを生成する画像入力手段と，
前記画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する濃淡値情報生成手段と，
前記曲面データを記憶する記憶手段と，
前記記憶手段に記憶されている曲面データを三角形近似する三角形近似手段と，
隣接し合う近似三角形を多角形に統合する多角形統合手段と，
隣接し合う多角形の境界付近の特徴を抽出する特徴抽出手段と，
を有することを特徴とする濃淡値文書画像からの特徴抽出装置。
【請求項５】
文書原稿画像を読み取って濃淡値レベルの画像データを生成する画像入力手段と，
前記画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する濃淡値情報生成手段と，
前記曲面データを記憶する記憶手段と，
前記記憶手段に記憶されている曲面データを三角形近似する三角形近似手段と，
隣接し合う近似三角形を多角形に統合する多角形統合手段と，
隣接し合う多角形の境界付近の特徴を抽出する特徴抽出手段と，
多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する輪郭線抽出手段と，
を有することを特徴とする濃淡値文書画像からの特徴抽出装置。
【請求項６】
前記多角形統合手段は，前記三角形近似手段において得られた近似三角形に対して，放線方向を量子化しておくことにより，互いに隣接し合う近似三角形の内，同じ量子化範囲内にあるものを統合することにより多角形を構成し，
前記特徴抽出手段は，濃淡値曲面を前記多角形の集まりとして操作することを特徴とする請求項４または５記載の濃淡値文書画像からの特徴抽出装置。
【請求項７】
前記特徴抽出手段は，前記多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を水平な平面で切断したときにできる，２つの多角形と水平面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うことを特徴とする請求項４，５または６記載の濃淡値文書画像からの特徴抽出装置。
【請求項８】
前記特徴抽出手段は，前記多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を複数の垂直な平面で切断したときにできる，２つの多角形と垂直面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うことを特徴とする請求項４，５または６記載の濃淡値文書画像からの特徴抽出装置。
【請求項９】
前記輪郭線抽出手段は，隣接し合う多角形の境界線から，輪郭線の部分となっている可能性が高いものを，多角形表現された濃淡値曲面の局所的特徴を使って抽出し，グラフ理論の探索問題を使って，輪郭閉曲線を構成することを特徴とする請求項５，６，７または８記載の濃淡値文書画像からの特徴抽出装置。
【請求項１０】
前記輪郭線抽出手段によって抽出された輪郭線を，多角形境界線の特徴を用いて内部輪郭と外部輪郭とに分類することを特徴とする請求項５，６，７，８または９記載の濃淡値文書画像からの特徴抽出装置。
【請求項１１】
前記輪郭線抽出手段によって抽出された輪郭線から，ベクトル・ラスター変換の手法を使って，輪郭の内部を塗りつぶすことにより２値画像を生成することを特徴とする請求項５，６，７，８，９または１０記載の濃淡値文書画像からの特徴抽出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，濃淡値文書画像からの特徴抽出方法及び特徴抽出装置における文字，文書画像等の認識，とりわけ画質の低いもの，画像の解像度が低い文字，文書画像等の認識のための特徴抽出技術に係り，特に，スキャナ等の画像読取装置から入力された濃淡値画像から，２値化を通さずに直接，濃淡値データを用いて輪郭線特徴を抽出し，更に，抽出された輪郭線を用いて入力画像が２値画像を生成する濃淡値文書画像からの特徴抽出方法及び特徴抽出装置に関する。
【０００２】
【従来の技術】
従来の文書，文字認識方式では，スキャナ等の画像入力装置から入力された濃淡値の画像データに対して，濃淡値をある閾値で２値化することにより得られる２値画像から，各種の有効な特徴を抽出する方法が用いられてきている。
【０００３】
しかしながら，画像入力装置の光学的な作用，特に，点広がり関数の作用によって，画像入力の際に画像に様々な歪みが生ずることがＷａｎｇとＰａｖｌｉｄｉｓにより指摘されている（Ｌ．Ｗａｎｇ  ａｎｄ  Ｔ．Ｐａｖｌｉｄｉｓ，  ”Ｄｉｒｅｃｔ  Ｇｒａｙ−Ｓｃａｌｅ  Ｅｘｔｒａｃｔｉｏｎ  ｏｆ  Ｆｅａｔｕｒｅｓ  ｆｏｒ  Ｃｈａｒａｃｔｅｒ  Ｒｅｃｏｇｎｉｔｉｏｎ”，  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｔｔｅｒｎ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｃｈｉｎｅ  Ｉｎｔｅｌｌｉｇｅｎｃｅ，  ｖｏｌ．１５，  ｎｏ．１０，  ｐｐ．１０５３−１０６７，  Ｏｃｔｏｂｅｒ  １９９３）。
【０００４】
このため，機械的な処理で２値化された画像は，多くの重要な情報を失うことになり，認識における誤りや拒否が生じる重要な原因となっている。この技術課題に対し，ＷａｎｇとＰａｖｌｉｄｉｓは，認識に有効な特徴の抽出に置いては，濃淡値画像を曲面と見ることによって，曲面の構造を解析することの重要性を強調している。
【０００５】
特に，彼らは，微分幾何学的な操作を用いることによって，濃淡値曲面から様々な地形的な特徴，具体的には，濃淡値の局所的最大，最小である尾根線や谷線，そして，濃淡値がある方向から見ると最大になっているが，それと直行する方向から見れば最小になっているような鞍点などを抽出する方法を提案している。
【０００６】
この方法では，文字のストロークの骨格線が尾根線に対応するという仮定をおくことによって，濃淡値画像から，直接，２値画像の細線化で得られるようなストロークの骨格線特徴を抽出することを目的としている。
【０００７】
【発明が解決しようとする課題】
しかしながら，この従来の方法には，幾つかの問題点がある。先ず，既存の文字認識アルゴリズムでは，ストロークの骨格線を利用するものの他に，文字の輪郭線の構造的・統計的特徴を利用する有効なものが数多くある。ＷａｎｇとＰａｖｌｉｄｉｓの方法は，輪郭線を用いている認識アルゴリズムには向いておらず，これまでの輪郭線を使った認識アルゴリズムの貴重な技術的財産を生かすことができないため，汎用的な目的には向いていない。
【０００８】
更に，文字の線幅が十分に細いときには，尾根線を抽出することが可能であるが，太い線の場合には，尾根線の位置を正確に見つけることが難しくなる。また，尾根，谷，鞍点の検出には，微分操作が必要となるが，実際のディジタル画像に微分操作を施すことにはいくつかの困難がある。とりわけ，実装においては，数値解析における微分方程式の解法と同様に，数多くのパラメータ設定が必要になり，それらのパラメータ調整が難しいという問題が生じてくる。
【０００９】
また，エッジ検出，輪郭線抽出等の汎用的なアルゴリズムは数多く知られているが，文字，文書画像の場合，特に，もともとの画像が２値で，それが画像入力の際の光学的影響により濃淡値になっていること，そして，文字，記号等の文書の構成要素の輪郭は必ず閉曲線になっていることに注意する必要がある。更に，建造物の画像，航空写真のエッジ検出のように位置の正確さは必要とされず，むしろ，認識に有効な形の特徴が維持されるように輪郭線が抽出されることがより重要である。
【００１０】
更に，Ｐａｖｌｉｄｉｓ，  Ｃｈｅｎ，  Ｊｏｓｅｐｈは，解像度と各ピクセルが持つ濃淡値のレベルの数の間にはトレードオフがあり，特に，文章画像においては，解像度が高ければ，濃淡値レベルは少なくて済むのに対し，解像度が下がるにつれて，多くの濃淡値レベルが必要になることを示している（Ｔ．Ｐａｖｌｉｄｉｓ，  Ｍ．Ｃｈｅｎ，  ａｎｄ  Ｅ．Ｊｏｓｅｐｈ，  ”Ｓａｍｐｌｉｎｇ  ａｎｄ  Ｑｕａｎｔｉｚａｔｉｏｎ  ｏｆ  Ｂｉｌｅｖｅｌ  Ｓｉｇｎａｌｓ”，  Ｐａｔｔｅｎ  Ｒｅｃｏｇｎｉｔｉｏｎ    Ｌｅｔｔｅｒｓ，  ｖｏｌ．１４，  ｎｏ．７，  ｐｐ．５５９−５６２，  Ｊｕｌｙ  １９９３）。
【００１１】
また，多くの２値化方式では，ピクセルの濃淡値の統計的分布をもとにして，閾値を決定するために，データの数（空間的密度）が減少する低解像度の画像においては，統計的推論の精度が下がることが必死である。従って，低解像度の画像においても，認識に有効な特徴が抽出できるような方式が必要である。
【００１２】
本発明は，上記従来の問題点に鑑みてなされたものであって，これまでの輪郭線やストロークの骨格線等を使った認識アルゴリズムの貴重な技術的財産を生かすために，文書画像から得られた濃淡値画像データの汎用的なデータ表現方式，及びデータ構造を提案し，該データ表現方式をもとに，文字，記号等の輪郭線などの特徴を抽出するための体系的な濃淡値文書画像からの特徴抽出方法及び特徴抽出装置を提供することを目的としている。
【００１３】
即ち，本発明の目的は，線が太い文字には有効でないストロークの骨格線特徴ばかりでなく，輪郭線特徴も抽出でき，獲得した特徴を多くの認識アルゴリズムにおいて使用可能とし，また，輪郭線特徴をもとに，輪郭線を内部輪郭及び外部輪郭に分類して内部を塗りつぶして２値画像を生成可能とし，更に，提案するデータ構造を基盤にすることによって，ディジタル画像では不安定な微分操作を避け得る濃淡値文書画像からの特徴抽出方法及び特徴抽出装置を提供することである。
【００１４】
また，本発明の他の目的は，これまでの文字認識の研究から，構造的な文字認識方式とパターンマッチング方式の両方において，特に，方向特徴や凹凸特徴が有効であることが分かっており，成功している文字認識方式の多くはこれらの特徴を何らかの形で使っているものが多いが，濃淡値画像データの表現方式として方向特徴と凹凸特徴を用いることにより，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出を可能とした濃淡値文書画像からの特徴抽出方法及び特徴抽出装置を提供することである。
【００１５】
更に，本発明の他の目的は，低解像度の画像において認識に有効な特徴を抽出するため，文字等の本質的な特徴に着目することによりデータ数（空間的密度）の減少に伴う総情報量を減少させ，総情報量の中の小さい部分を占める本質的情報を拾い上げることを可能とした濃淡値文書画像からの特徴抽出方法及び特徴抽出装置を提供することである。
【００１６】
【課題を解決するための手段】
上記課題を解決するために，本発明の請求項１に係る濃淡値文書画像からの特徴抽出方法及び特徴抽出装置は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップとを具備したものである。
【００１７】
また，請求項２に係る濃淡値文書画像からの特徴抽出方法は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップと，前記第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する第６ステップとを具備したものである。
【００１８】
また，請求項３に係る濃淡値文書画像からの特徴抽出方法は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する第１ステップと，前記第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する第２ステップと，前記第２ステップにより生成された曲面データを三角形近似する第３ステップと，前記第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する第４ステップと，前記第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出する第５ステップと，前記第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する第６ステップと，前記第６ステップで抽出された輪郭線を内部輪郭及び外部輪郭に分類する第７ステップと，ベクトル・ラスター変換の手法を使って，前記内部輪郭及び外部輪郭に基づく輪郭の内部を塗りつぶすことにより２値画像を生成する第８ステップとを具備したものである。
【００１９】
また，請求項４に係る濃淡値文書画像からの特徴抽出装置は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する画像入力手段と，前記画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する濃淡値情報生成手段と，前記曲面データを記憶する記憶手段と，前記記憶手段に記憶されている曲面データを三角形近似する三角形近似手段と，隣接し合う近似三角形を多角形に統合する多角形統合手段と，隣接し合う多角形の境界付近の特徴を抽出する特徴抽出手段とを具備したものである。
【００２０】
また，請求項５に係る濃淡値文書画像からの特徴抽出装置は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する画像入力手段と，前記画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する濃淡値情報生成手段と，前記曲面データを記憶する記憶手段と，前記記憶手段に記憶されている曲面データを三角形近似する三角形近似手段と，隣接し合う近似三角形を多角形に統合する多角形統合手段と，隣接し合う多角形の境界付近の特徴を抽出する特徴抽出手段と，多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する輪郭線抽出手段とを具備したものである。
【００２１】
また，請求項６に係る濃淡値文書画像からの特徴抽出装置は，請求項４または５記載の濃淡値文書画像からの特徴抽出装置において，前記多角形統合手段は，前記三角形近似手段において得られた近似三角形に対して，放線方向を量子化しておくことにより，互いに隣接し合う近似三角形の内，同じ量子化範囲内にあるものを統合することにより多角形を構成し，前記特徴抽出手段は，濃淡値曲面を前記多角形の集まりとして操作するものである。
【００２２】
また，請求項７に係る濃淡値文書画像からの特徴抽出装置は，請求項４，５または６記載の濃淡値文書画像からの特徴抽出装置において，前記特徴抽出手段は，前記多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を水平な平面で切断したときにできる，２つの多角形と水平面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うものである。
【００２３】
また，請求項８に係る濃淡値文書画像からの特徴抽出装置は，請求項４，５または６記載の濃淡値文書画像からの特徴抽出装置において，前記特徴抽出手段は，前記多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を複数の垂直な平面で切断したときにできる，２つの多角形と垂直面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うものである。
【００２４】
また，請求項９に係る濃淡値文書画像からの特徴抽出装置は，請求項５，６，７または８記載の濃淡値文書画像からの特徴抽出装置において，前記輪郭線抽出手段は，隣接し合う多角形の境界線から，輪郭線の部分となっている可能性が高いものを，多角形表現された濃淡値曲面の局所的特徴を使って抽出し，グラフ理論の探索問題を使って，輪郭閉曲線を構成するものである。
【００２５】
また，請求項１０に係る濃淡値文書画像からの特徴抽出装置は，請求項５，６，７，８または９記載の濃淡値文書画像からの特徴抽出装置において，前記輪郭線抽出手段によって抽出された輪郭線を，多角形境界線の特徴を用いて内部輪郭と外部輪郭とに分類するものである。
【００２６】
また，請求項１１に係る濃淡値文書画像からの特徴抽出装置は，請求項５，６，７，８，９または１０記載の濃淡値文書画像からの特徴抽出装置において，前記輪郭線抽出手段によって抽出された輪郭線から，ベクトル・ラスター変換の手法を使って，輪郭の内部を塗りつぶすことにより２値画像を生成するものである。
【００２７】
【発明の実施の形態】
以下，本発明の濃淡値文書画像からの特徴抽出方法及び特徴抽出装置の概要について，並びに，本発明の濃淡値文書画像からの特徴抽出方法及び特徴抽出装置の実施形態について，順に図面を参照して詳細に説明する。
【００２８】
〔本発明の濃淡値文書画像からの特徴抽出方法及び特徴抽出装置の概要〕
本発明の請求項１に係る濃淡値文書画像からの特徴抽出方法では，図３に示す如く，第１ステップＳ３０１で文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップＳ３０２では，第１ステップＳ３０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップＳ３０３では第２ステップＳ３０２により生成された曲面データを三角形近似し，第４ステップＳ３０４では，第３ステップＳ３０３により得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，更に，第５ステップＳ３０５では第４ステップＳ３０４で得られた隣接し合う多角形の境界付近の特徴を抽出するようにしている。
【００２９】
これにより，従来の輪郭線やストロークの骨格線等を使った認識アルゴリズムの貴重な技術的財産を生かすことができ，文章画像から得られた濃淡値画像データの汎用的なデータ表現方式及びデータ構造を実現でき，該データ表現を用いることにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，更に，実際のディジタル画像では問題が多い微分操作を避けることができる。
【００３０】
また，請求項２に係る濃淡値文書画像からの特徴抽出方法では，図３に示す如く，第１ステップＳ３０１で文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップＳ３０２では，第１ステップＳ３０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップＳ３０３では第２ステップＳ３０２により生成された曲面データを三角形近似し，第４ステップＳ３０４では，第３ステップＳ３０３により得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，第５ステップＳ３０５では第４ステップＳ３０４で得られた隣接し合う多角形の境界付近の特徴を抽出し，更に，第６ステップＳ３０６では，第４及び第５ステップＳ３０４，Ｓ３０５で得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出するようにしている。
【００３１】
これにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができる。
【００３２】
また，請求項３に係る濃淡値文書画像からの特徴抽出方法では，図３に示す如く，第１ステップＳ３０１で文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップＳ３０２では，第１ステップＳ３０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップＳ３０３では第２ステップＳ３０２により生成された曲面データを三角形近似し，第４ステップＳ３０４では，第３ステップＳ３０３により得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，第５ステップＳ３０５では第４ステップＳ３０４で得られた隣接し合う多角形の境界付近の特徴を抽出し，第６ステップＳ３０６では，第４及び第５ステップＳ３０４，Ｓ３０５で得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出し，第７ステップＳ３０７では第６ステップＳ３０６で抽出された輪郭線を内部輪郭及び外部輪郭に分類し，更に，第８ステップＳ３０８では，ベクトル・ラスター変換の手法を使って，前記内部輪郭及び外部輪郭に基づく輪郭の内部を塗りつぶすことにより２値画像を生成するようにしている。
【００３３】
これにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができ，また同時に，形状の特徴を保持した２値画像を低解像度の濃淡値画像からも生成することができる。
【００３４】
また，請求項４に係る濃淡値文書画像からの特徴抽出装置では，図１に示す如く，画像入力手段１０１により文書原稿画像を読み取って濃淡値レベルの画像データを生成し，濃淡値情報生成手段１０２では，画像入力手段１０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成して，該曲面データを記憶手段１０３に記憶し，三角形近似手段１０４では，記憶手段１０３に記憶されている曲面データを三角形近似し，多角形統合手段１０５では隣接し合う近似三角形を多角形に統合し，更に特徴抽出手段１０６では，隣接し合う多角形の境界付近の特徴を抽出するようにしている。
【００３５】
これにより，従来の輪郭線やストロークの骨格線等を使った認識アルゴリズムの貴重な技術的財産を生かすことができ，文章画像から得られた濃淡値画像データの汎用的なデータ表現方式及びデータ構造を実現でき，該データ表現を用いることにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，更に，実際のディジタル画像では問題が多い微分操作を避けることができる。
【００３６】
また，請求項５に係る濃淡値文書画像からの特徴抽出装置では，図２に示す如く，画像入力手段１０１により文書原稿画像を読み取って濃淡値レベルの画像データを生成し，濃淡値情報生成手段１０２では，画像入力手段１０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成して，該曲面データを記憶手段１０３に記憶し，三角形近似手段１０４では，記憶手段１０３に記憶されている曲面データを三角形近似し，多角形統合手段１０５では隣接し合う近似三角形を多角形に統合し，特徴抽出手段１０６では隣接し合う多角形の境界付近の特徴を抽出し，更に輪郭線抽出手段２０７では，多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出するようにしている。
【００３７】
これにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができる。
【００３８】
また，請求項６に係る濃淡値文書画像からの特徴抽出装置では，多角形統合手段１０５は，三角形近似手段１０４において得られた近似三角形に対して，放線方向を量子化しておくことにより，互いに隣接し合う近似三角形の内，同じ量子化範囲内にあるものを統合することにより多角形を構成し，特徴抽出手段１０６では，濃淡値曲面を前記多角形の集まりとして操作するようにしている。
【００３９】
つまり，濃淡画像値データのデータ構造及び表現方式として方向特徴を使用し，該方向特徴に着目して濃淡値曲面を同じような放線方向を持つ多角形に分割することとしているので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出が可能となる。
【００４０】
また，請求項７に係る濃淡値文書画像からの特徴抽出装置では，特徴抽出手段１０６は，多角形統合手段１０５により構築される多角形に対して，互いに隣接する多角形の境界線付近を水平な平面で切断したときにできる，２つの多角形と水平面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うようにしている。
【００４１】
つまり，濃淡画像値データのデータ構造及び表現方式として凹凸特徴と方向特徴を使用し，濃淡値曲面から方向特徴と共に水平面に沿った局所的な凹凸特徴を獲得することとしているので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出が可能となる。また，文字等の図形の本質的な特徴である方向特徴と凹凸特徴に着目して濃淡値曲面を分割し解析することにより，コンパクトで表現能力の高いデータ表現を得ることができる。
【００４２】
また，請求項８に係る濃淡値文書画像からの特徴抽出装置では，特徴抽出手段１０６は，多角形統合手段１０５により構築される多角形に対して，互いに隣接する多角形の境界線付近を複数の垂直な平面で切断したときにできる，２つの多角形と垂直面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うようにしている。
【００４３】
つまり，濃淡画像値データのデータ構造及び表現方式として凹凸特徴と方向特徴を使用し，濃淡値曲面から方向特徴と共に垂直面に沿った局所的な凹凸特徴を獲得することとしているので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出が可能となる。また，文字等の図形の本質的な特徴である方向特徴と凹凸特徴に着目して濃淡値曲面を分割し解析することにより，コンパクトで表現能力の高いデータ表現を得ることができる。
【００４４】
また，請求項９に係る濃淡値文書画像からの特徴抽出装置では，輪郭線抽出手段２０７は，隣接し合う多角形の境界線から，輪郭線の部分となっている可能性が高いものを，多角形表現された濃淡値曲面の局所的特徴を使って抽出し，グラフ理論の探索問題を使って，輪郭閉曲線を構成するようにしている。これにより，輪郭線抽出問題をグラフ理論を用いることによって効率よく解くことができる。
【００４５】
また，請求項１０に係る濃淡値文書画像からの特徴抽出装置では，輪郭線抽出手段２０７によって抽出された輪郭線を，多角形境界線の特徴を用いて内部輪郭と外部輪郭とに分類し，更に，請求項１１に係る濃淡値文書画像からの特徴抽出装置では，輪郭線抽出手段２０７によって抽出された輪郭線から，ベクトル・ラスター変換の手法を使って，輪郭の内部を塗りつぶすことにより２値画像を生成するようにしている。
【００４６】
文字等の図形の本質的な特徴である方向特徴と凹凸特徴に着目したデータ表現をもとにしているので，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができ，また同時に，形状の特徴を保持した２値画像を低解像度の濃淡値画像からも生成することができる。
【００４７】
〔実施形態〕
図２は本発明の実施形態に係る濃淡値文書画像からの特徴抽出装置の構成図である。
【００４８】
図２において，本実施形態の濃淡値文書画像からの特徴抽出装置は，文書原稿画像を読み取って濃淡値レベルの画像データを生成する画像入力手段１０１と，画像入力手段１０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する濃淡値情報生成手段１０２と，該曲面データを記憶する記憶手段１０３と，記憶手段１０３に記憶されている曲面データを三角形近似する三角形近似手段１０４と，隣接し合う近似三角形を多角形に統合する多角形統合手段１０５と，隣接し合う多角形の境界付近の特徴を抽出する特徴抽出手段１０６と，多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する輪郭線抽出手段２０７とを備えて構成されている。
【００４９】
また，図３は，本実施形態の濃淡値文書画像からの特徴抽出装置における特徴抽出方法を説明する概略フローチャートである。以下では，本概略フローチャートに従い，図４から図１３までの説明図を参照して，特徴抽出方法を説明する。
【００５０】
先ず，第１ステップＳ３０１では，画像入力手段１０１により文書原稿画像を読み取って濃淡値レベルの画像データを生成し，文書画像を濃淡値画像データとして記憶手段１０３に記憶する。濃淡値画像データは，通常，要素が濃淡値レベルを示す整数であるような２次元配列として記憶手段１０３内に記憶されている。
【００５１】
次に，第２ステップＳ３０２では，第１ステップＳ３０１により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成する。つまり，濃淡値を高さと見なすことによって，濃淡値画像データを曲面として取り扱うものである。図４に文字の濃淡値画像データの一例を示す。
【００５２】
次に，第３ステップＳ３０３では，第２ステップＳ３０２により生成された曲面データを三角形近似する。つまり，曲面の三角形近似アルゴリズムを適用することによって，濃淡値曲面を三角形に分割するものである。
【００５３】
近似アルゴリズムとしては，例えば，Ｄｅ  Ｆｌｏｒｉａｎｉ  （Ｌ．  Ｄｅ  Ｆｌｏｒｉａｎｉ，  ”Ａ  ｐｙｒａｍｉｄａｌ  ｄａｔａ  ｓｔｒｕｃｔｕｒｅ  ｆｏｒ  ｔｒｉａｎｇｌｅ−ｂａｓｅｄ  ｓｕｒｆａｃｅ  ｄｅｓｃｒｉｐｔｉｏｎ”，  ＩＥＥＥＣｏｍｐｕｔｅｒ  Ｇｒａｐｈｉｃｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ｖｏｌ．９，  ｐｐ．６７−７８，  Ｍａｒｃｈ  １９８９）によるものを用いることができる。
【００５４】
このアルゴリズムは，近似精度を表すパラメータを１つ指定し，各分割三角形と近似される曲面との高さ方向の最大誤差がこの指定パラメータ以下になるように，ドロネー三角形分割を応用して，階層的に曲面を三角形に分割するものである。図５に，図４の濃淡値文字画像データに対する三角形分割の例を示す。
【００５５】
次に，方向特徴と凹凸特徴に着目して，この曲面の三角形近似から様々な特徴を抽出するためのデータ表現方式及びデータ構造を構築する。
【００５６】
先ず第１段階として，第４ステップＳ３０４では，第３ステップＳ３０３により得られた近似三角形の内，隣接し合う近似三角形を多角形に統合する。即ち，方向を量子化して，放線方向が同じ量子化範囲にあるような，隣接し合う三角形を多角形に統合するものである。
【００５７】
先ず，量子化方向コードを設定するために，高さ方向にｚ軸（基底ベクトルｅ３  ）をとり，ｘ，ｙ軸（基底ベクトルｅ１  ，ｅ２  ），原点Ｏをそれぞれ画像面上にとることにより，正規直交座標系Σ＝（Ｏ；ｅ１  ，ｅ２  ，ｅ３  ）を定義する。
【００５８】
ここで，方向の量子化密度を決めるパラメータＮ（但し，Ｎは正の偶数）を設定し，３次元空間内の方向を次のようにして量子化する。
【００５９】
ｘｙ平面上に原点を通るＮ本の直線Ｌｉ  （ｉ＝０，１，…，Ｎ−１）を定義する。図６はＮ＝４の場合の３次元空間内の方向の量子化を示している。直線Ｌｉ  に沿った単位ベクトルは｛ｃｏｓ（ｉ／Ｎπ），ｓｉｎ（ｉ／Ｎπ）｝で与えられる。
【００６０】
各直線Ｌｉ  （ｉ＝０，１，…，Ｎ−１）に対して，ｘｙ平面上に垂直で，直線Ｌｉ  を含むような平面Πｉ  を定義する。この平面をもとにして，原点Ｏを通るＮ個の直線の集合｛Ｌｉｊ：ｊ＝０，１，…，Ｎ−１｝を導入する。ここで，直線Ｌｉｊ（ｉ，ｊ＝０，１，…，Ｎ−１）に沿った単位ベクトルは，
ｕｉｊ，０＝  ｃｏｓ（ｉ／Ｎπ）ｃｏｓ（ｊ／Ｎπ）ｅ１  ＋ｓｉｎ（ｉ／Ｎπ）ｃｏｓ（ｊ／Ｎπ）ｅ２  −ｓｉｎ（ｊ／Ｎπ）ｅ３
で与えられる。
【００６１】
ここで，直線Ｌｉｊに沿って，単位ベクトルｕｉｊ，０と反対方向の単位ベクトルｕｉｊ，１＝  −ｕｉｊ，０をとれば，単位ベクトルｕｉｊ，０の向きに方向コード（ｉ，ｊ），ｕｉｊ，１の向きに方向コード（ｉ，Ｎ＋ｊ）をそれぞれ割り当てることによって，量子化方向コード（ｐ，ｄ）（但し，ｐ＝０，１，…，Ｎ−１；ｄ＝０，１，…，２Ｎ−１）を規定できる。また，形式的に，水平面に沿った方向コード（ｉ，０）（但し，ｉ＝０，１，…，Ｎ−１）を（Ｎ，ｉ）とも表すことにする。
【００６２】
図７には，パラメータＮ＝４のときの垂直面Πｉ  と方向コード（１，０），（１，１），…，（１，７）を，そして，図８には，パラメータＮ＝４のときの方向コード（４，０），（４，１），…，（４，７）をそれぞれ示す。
【００６３】
更に，近似分割三角形の放線方向を，量子化方向によって２Ｎ２  個の区間に分類する。ｕ＝−ｖであるような２つの単位ベクトルｕ，ｖを同一方向と見なすことにすると，各区間Ｄ（ｉ，ｊ），ｉ＝０，１，…，２Ｎ−１；ｊ＝０，１，…，Ｎ−１は，方向を規定する単位ベクトルを用いて次のように定義される。
Ｄ（ｉ，ｊ）＝｛（ｃｏｓθｃｏｓφ，ｓｉｎθｃｏｓφ，−ｓｉｎφ）：ｉ／Ｎπ＜θ＜（ｉ＋１）／Ｎπ，ｊ／Ｎπ＜φ＜（ｊ＋１）／Ｎπ｝
（ｉ＝０，１，…，２Ｎ−１；ｊ＝０，１，…，Ｎ−１）
【００６４】
定義した量子化方向区間をもとにして，放線方向が同一の区間に属し，隣接し合う三角形を多角形に統合してゆく。
【００６５】
但し，放線方向
（ｃｏｓ（ｉ／Ｎπ）ｃｏｓφ，ｓｉｎ（ｉ／Ｎπ）ｃｏｓφ，−ｓｉｎφ）
（ｉ＝０，１，…，２Ｎ−１，φは任意），
または，
（ｃｏｓθｃｏｓ（ｊ／Ｎπ），ｓｉｎθｃｏｓ（ｊ／Ｎπ），−ｓｉｎ（ｊ／Ｎπ））
（  θは任意，ｊ＝０，１，…，Ｎ−１）
の三角形は，定義した区間の境界になるので，そのような放線方向を持つ三角形については，高さ方向に微少な摂動を加えることによって，放線方向を微調整する。図９に，図５の分割三角形を統合してできる多角形分割の例を示す。
【００６６】
次に，第５ステップＳ３０５では，第４ステップＳ３０４で得られた隣接し合う多角形の境界付近の特徴を抽出する。つまり，分割近似三角形の統合により構築される多角形に対して，互いに隣接する多角形の境界線付近を水平な平面で切断したときにできる，２つの多角形と水平面の交差曲線の凹凸の特徴と方向の特徴を抽出するものである。
【００６７】
ここで，２つの隣接する多角形をａ，ｂとし，これらの２つの多角形ａ，ｂと水平面の交差曲線をＣ（ａ，ｂ）とする。図１０では，図９における多角形分割の一部を拡大したときの水平面と多角形の交差曲線を太線で示す。
【００６８】
また，多角形ａ及びｂの境界の凹凸特徴を次のようにして定義する。交差曲線Ｃ（ａ，ｂ）と，多角形ａ及びｂの境界線との交点をＰとし，Ｐａ  ，Ｐｂ  を交点Ｐに十分近い，それぞれ多角形ａ，ｂの内部にある交差曲線Ｃ（ａ，ｂ）上の点とする。ベクトルの外積ＰＰａ  ×ＰＰｂ  の符号が負ならば，多角形ａ及びｂの結合をａ→ｂと表し，正ならば，ｂ→ａというように，結合の凹凸を表す。
【００６９】
更に，水平直線Ｌｉ  （ｉ＝０，１，…，Ｎ−１）に対して，点（ｘ，ｙ，ｚ）の高さ関数
ｈｉ  （ｘ，ｙ，ｚ）＝−ｘｓｉｎ（ｉ／Ｎπ）＋ｙｃｏｓ（ｉ／Ｎπ）
の大小関係を３点Ｐ，Ｐａ  ，Ｐｂ  について比較することにより，多角形ａ及びｂの結合の方向特徴を決める。
【００７０】
もし，高さ関数ｈｉ  が点Ｐで最大であれば，多角形ａ及びｂの直線Ｌｉ  方向の水平面に沿った結合は，方向コード（ｉ，０）＝（Ｎ，ｉ）が与えられ，最小であれば，方向コード（ｉ＋Ｎ，０）＝（Ｎ，ｉ＋Ｎ）が与えられる。それ以外の場合には，高さ関数ｈｉ  が交差曲線Ｃ（ａ，ｂ）に沿って単調変化するので，方向コードは与えられない。
【００７１】
各直線Ｌｉ  方向で計算した方向コードを集めて順番に並べれば，
（（Ｎ，ｊ（１）  ），（Ｎ，ｊ（２）  ），…，（Ｎ，ｊ（ｍ）  ）
但し，ｍは与えられた方向コードの個数，
ｊ（ｋ＋１）  ≡ｊ（ｋ）  ＋１（ｍｏｄ２Ｎ  ），ｋ＝１，２，…，ｍ−１
というような数列を作ることができるので，この数列の最初と最後の要素を使って，多角形ａ及びｂの結合の凹凸特徴と方向特徴を
ａ−（ｊ（１）  ，ｊ（ｍ）  ）→ｂ
と表現することができる。
【００７２】
図１１には，図１０に示した５つの多角形Ｉ，…，Ｖに対して求めた，隣接し合う多角形間の凹凸特徴と方向特徴を，パラメータＮ＝４の場合について示す。尚，多角形ＩＩと多角形ＩＩＩ  ，多角形ＩＩＩ  と多角形ＩＶの２組については，方向特徴が与えられない。
【００７３】
また，水平面の代わりに，垂直面Πｉ  （ｉ＝０，１，…，Ｎ−１）を使って上記の操作を行えば，隣接する多角形の結合について，垂直面Πｉ  に沿った凹凸・方向特徴を求めることができる。但し，外積，高さ関数の計算の際には，基底ベクトルｅ３  がｘ軸の正の方向，単位ベクトルｕｉｊ，０がｚ軸の正の方向，ベクトルの外積ｕｉｊ，０×ｅ３  がｙ軸の正の方向になるような座標系を用いる。
【００７４】
ここまでは，文書画像から得られた濃淡値データについて，濃淡値を高さと見ることによって曲面として扱い，方向特徴及び凹凸特徴に着目したデータ表現方式とデータ構造を取り扱ってきた。以下では，このデータ表現方式とデータ構造を用いて，文字等の文書画像の構成要素の輪郭線特徴の抽出方式について述べる。
【００７５】
先ず，輪郭線とは，濃淡値曲面の勾配が急なところを辿ることによってできる閉曲線であり，大局的に見れば単一平面上にはのっていないような曲線ではあるが，局所的には水平な線分として近似できる。従って，上述した多角形による曲面のデータ表現方式とデータ構造において，局所的に共通の交差する水平面を持ち，勾配が急な多角形の境界線をつなげていって，ある基準のもとで最良となるような閉曲線を構成すれば，輪郭線を取り出すことができる。この方式をより具体的に以下で述べる。
【００７６】
先ず，多角形ａ，ｂ（ａ，ｂは互いに異なる多角形）のある境界線Ｂ（ａ，ｂ），及び多角形ｃ，ｄ（ｃ，ｄは互いに異なる多角形）のある境界線Ｂ（ｃ，ｄ）（ｂとｃは同一であってもよい）付近で，水平面に沿った凹凸特徴及び方向特徴が次の何れかの形で表されているとする。
（１）ａ−（ｊ０  ，ｊ１  ）→ｂ，ｃ−（ｊ２  ，ｊ３  ）→ｄ
（２）ａ−（ｊ０  ，ｊ１  ）→ｂ，ｄ−（ｊ２  ，ｊ３  ）→ｃ
（３）ｂ−（ｊ０  ，ｊ１  ）→ａ，ｃ−（ｊ２  ，ｊ３  ）→ｄ
（４）ｂ−（ｊ０  ，ｊ１  ）→ａ，ｄ−（ｊ２  ，ｊ３  ）→ｃ
【００７７】
更に，ｂとｃが互いに異なる多角形の場合，ｂとｃを結ぶような多角形のパス
（ｅ０  ＝ｂ，ｅ１  ，…，ｅｍ−１  ，ｅｍ  ＝ｃ）（但し，ｍ≧２）
があり，多角形ｅ１  とｅｉ＋１  （ｉ＝１，２，…，ｍ−１）の境界に対しては，水平面に沿った方向特徴が割り当てられていないと仮定する。即ち，どの水平線Ｌｉ  に関しても，多角形ｅｉ  とｅｉ＋１  と水平面の交差曲線Ｃ（ｅｉ  ，ｅｉ＋１  ）に沿って高さ関数ｈｉ  が単調変化すると仮定する。
【００７８】
ここで，多角形の列（ａ，ｂ，ｅ１  ，…，ｅｍ−１  ，ｃ，ｄ）と同時に交差するような水平面が存在する場合には，上記（１）から（４）の式に現れる４つの整数ｊ０  ，ｊ１  ，ｊ２  ，ｊ３の間に，それぞれ，次のような関係があることが数学的に証明できる：
（イ）ｊ２  −ｊ１  ≡１（ｍｏｄ２Ｎ  ），
（ロ）ｊ３  −ｊ１  ≡Ｎ（ｍｏｄ２Ｎ  ），
（ハ）ｊ２  −ｊ０  ≡Ｎ（ｍｏｄ２Ｎ  ），
（ニ）ｊ０  −ｊ３  ≡１（ｍｏｄ２Ｎ  ）
【００７９】
この性質を使えば，多角形の境界線Ｂ（ａ，ｂ）に対して，共通の交差する水平をもつような，近隣の多角形の境界線を見つけだすことができる。
【００８０】
更に，このような近隣の境界線が複数見つかることがあるが，ある基準を用いて近隣の境界線を制限することにする。
【００８１】
今，輪郭線抽出において，局所的に共通の交差する水平面をもち，勾配が急な多角形の境界線をつなげてゆくことを考えているのであるから，候補となっている境界線Ｂ（ａ，ｂ）の近隣の境界線Ｂ’の鉛直線との角度α（Ｂ’）と，その境界線Ｂ’の高さの中間値（境界線の最高点と最低点の高さ平均）と，境界線Ｂ（ａ，ｂ）の高さの中間値の差Δｚ（Ｂ（ａ，ｂ），Ｂ’）の単調増加関数ｆ（α（Ｂ’），Δｚ（Ｂ（ａ，ｂ），Ｂ’）），例えば，
ｆ（α，Δｚ）＝ｓｉｎα（Ｂ’）＋ｃΔｚ（Ｂ（ａ，ｂ），Ｂ’）
（ｃは定数）
とを小さくするものだけを，境界線Ｂ（ａ，ｂ）の近隣の境界線とすればよい。
【００８２】
例えば，境界線Ｂ（ａ，ｂ）の近隣の境界線Ｂ’について，
ｆ０  ≡ｍｉｎＢ’ｆ（α（Ｂ’），Δｚ（Ｂ（ａ，ｂ），Ｂ’））
を基準にして，ｆ０  ＋ｔ（ｔは正の定数）以内のものだけを選ぶといった基準が挙げられる。
【００８３】
まとめると，すべての隣接多角形の組（ａ，ｂ）に対して，多角形の境界線付近の水平面に沿った凹凸特徴及び方向特徴に基づく性質，そして，境界線の鉛直線との角度αと，その境界線の高さの中間値と境界線Ｂ（ａ，ｂ）の高さの中間値の差Δｚを用いた評価関数を使って，その境界線Ｂ（ａ，ｂ）と共通の交差水平面を持ち，急勾配を持つような近隣の多角形の境界線を見つけることができる。
【００８４】
更に，文字等の文書画像の構成要素の輪郭線を抽出するため，多角形境界線をノードとした重み付き有向グラフを構築する。
【００８５】
境界線Ｂ（ａ，ｂ）に対して見つけたそれぞれの近隣境界線βについて，重みを評価関数ｆ（α（β），Δｚ（Ｂ（ａ，ｂ），β））の値ｗとするような，重み付き有向リンクＢ（ａ，ｂ）−ｗ→βを設ける。また，この有向グラフにおいて，境界線Ｂ（ａ，ｂ）と境界線Ｂ（ｂ，ａ）は別々のノードとして扱う。図１２には，図１０及び図１１の例に対して，この手続きの適用結果である重み付き有向グラフを示す。
【００８６】
次に，第６ステップＳ３０６では，第４及び第５ステップＳ３０４，Ｓ３０５で得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出する。つまり，得られた重み付き有向グラフを使って，文字等の輪郭線を抽出する。
【００８７】
先ず，すべての多角形境界線の中から，勾配が最も急なものを選び出し，それに対応するノードｓを有向グラフから見つける。尚，上述のように，境界線Ｂ（ａ，ｂ）と境界線Ｂ（ｂ，ａ）は別々のノードとして扱っているが，どちらを選んでもよい。
【００８８】
ノードｓを出発点として，各ノードへの最短経路を求める。全てのノードについて最短経路が求められたら，有向グラフにおいて，ノードｓと同じ連結成分に属し，且つ，有向リンクｔ→ｓを持つようなノードｔを見つけだす。有向グラフ上でノードｓからノードｔへの経路を辿ってゆき，画像上では，有向グラフの経路上のノードに対応する多角形境界線の高さの中間値に対応する点を結び，最後に有向グラフのノードｔ，ｓに対応する境界線の高さの中間値に対応する点を結べば，閉じた輪郭線ができる。
【００８９】
また，このようなノードｔが複数あるような場合には，例えば，輪郭線の長さが最大になるようなものを選べはよい。輪郭線が決まったら，その輪郭線を構成するノードを有向グラフから除去する。
【００９０】
更に，除去されたノードに対応する多角形輪郭線を構成する多角形について，その多角形のすべての境界線に対応するノードを有向グラフから除去する。
【００９１】
そして，更新された有向グラフから，再び，残った多角形境界線の内，勾配が最も急なものに対応するノードｓを有向グラフから見つけて，新しい輪郭線が見つからなくなるまで，上記の手続きを繰り返す。図１３には，図９の多角形分割に対して上記手続により見つかった輪郭線と，外輪郭線を構成する多角形境界線を示す。
【００９２】
次に，第７ステップＳ３０７では，第６ステップＳ３０６で抽出された輪郭線を内部輪郭及び外部輪郭に分類し，更に，第８ステップＳ３０８では，ベクトル・ラスター変換の手法を使って，前記内部輪郭及び外部輪郭に基づく輪郭の内部を塗りつぶすことにより２値画像を生成する。
【００９３】
先ず，各輪郭線を内部輪郭及び外部輪郭の分類は，次のように容易に行うことができる。即ち，その輪郭線を構成する多角形境界線の最低点のｙ座標の範囲が，上記の手続きにより構成される輪郭線のｙ座標の範囲を含むならば，輪郭線の外側が，輪郭線よりも低くなっていることになっているので，その輪郭線は外側輪郭であることが分かる。また，そうでなければ，内側輪郭である。
【００９４】
このように輪郭線を内部輪郭及び外部輪郭に分類すれば，ベクトル・ラスター変換の手法を使って，輪郭線から２値画像を生成することができる。
【００９５】
【発明の効果】
以上説明したように，本発明の請求項１に係る濃淡値文書画像からの特徴抽出方法によれば，第１ステップで文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップでは，第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップでは第２ステップにより生成された曲面データを三角形近似し，第４ステップでは，第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，更に，第５ステップでは第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出することとしたので，従来の輪郭線やストロークの骨格線等を使った認識アルゴリズムの貴重な技術的財産を生かすことができ，文章画像から得られた濃淡値画像データの汎用的なデータ表現方式及びデータ構造を実現でき，該データ表現を用いることにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，更に，実際のディジタル画像では問題が多い微分操作を避け得る濃淡値文書画像からの特徴抽出方法を提供することができる。
【００９６】
また，請求項２に係る濃淡値文書画像からの特徴抽出方法によれば，第１ステップで文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップでは，第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップでは第２ステップにより生成された曲面データを三角形近似し，第４ステップでは，第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，第５ステップでは第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出し，更に，第６ステップでは，第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出することとしたので，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出し得る濃淡値文書画像からの特徴抽出方法を提供することができる。
【００９７】
また，請求項３に係る濃淡値文書画像からの特徴抽出方法によれば，第１ステップで文書原稿画像を読み取って濃淡値レベルの画像データを生成し，第２ステップでは，第１ステップにより生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成し，第３ステップでは第２ステップにより生成された曲面データを三角形近似し，第４ステップでは，第３ステップにより得られた近似三角形の内，隣接し合う近似三角形を多角形に統合し，第５ステップでは第４ステップで得られた隣接し合う多角形の境界付近の特徴を抽出し，第６ステップでは，第４及び第５ステップで得られた多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出し，第７ステップでは第６ステップで抽出された輪郭線を内部輪郭及び外部輪郭に分類し，更に，第８ステップでは，ベクトル・ラスター変換の手法を使って，前記内部輪郭及び外部輪郭に基づく輪郭の内部を塗りつぶすことにより２値画像を生成することとしたので，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができ，また同時に，形状の特徴を保持した２値画像を低解像度の濃淡値画像からも生成し得る濃淡値文書画像からの特徴抽出方法を提供することができる。
【００９８】
また，請求項４に係る濃淡値文書画像からの特徴抽出装置によれば，画像入力手段により文書原稿画像を読み取って濃淡値レベルの画像データを生成し，濃淡値情報生成手段では，画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成して，該曲面データを記憶手段に記憶し，三角形近似手段では，記憶手段に記憶されている曲面データを三角形近似し，多角形統合手段では隣接し合う近似三角形を多角形に統合し，更に特徴抽出手段では，隣接し合う多角形の境界付近の特徴を抽出することとしたので，従来の輪郭線やストロークの骨格線等を使った認識アルゴリズムの貴重な技術的財産を生かすことができ，文章画像から得られた濃淡値画像データの汎用的なデータ表現方式及びデータ構造を実現でき，該データ表現を用いることにより，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，更に，実際のディジタル画像では問題が多い微分操作を避け得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【００９９】
また，請求項５に係る濃淡値文書画像からの特徴抽出装置によれば，画像入力手段により文書原稿画像を読み取って濃淡値レベルの画像データを生成し，濃淡値情報生成手段では，画像入力手段により生成された画像データについて，濃淡値情報を高さ方向に見立てた３次元的な曲面データを生成して，該曲面データを記憶手段に記憶し，三角形近似手段では，記憶手段に記憶されている曲面データを三角形近似し，多角形統合手段では隣接し合う近似三角形を多角形に統合し，特徴抽出手段では隣接し合う多角形の境界付近の特徴を抽出し，更に輪郭線抽出手段では，多角形と隣接し合う多角形の境界付近の特徴を使って，文字，記号等の文書画像の構成要素の輪郭線を抽出することとしたので，輪郭線等の特徴抽出のための効率の良いアルゴリズムの設計が可能になり，実際のディジタル画像では問題が多い微分操作を避けることができると共に，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出し得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【０１００】
また，請求項６に係る濃淡値文書画像からの特徴抽出装置によれば，多角形統合手段は，三角形近似手段において得られた近似三角形に対して，放線方向を量子化しておくことにより，互いに隣接し合う近似三角形の内，同じ量子化範囲内にあるものを統合することにより多角形を構成し，特徴抽出手段では，濃淡値曲面を前記多角形の集まりとして操作することとしたので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出を行い得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【０１０１】
また，請求項７に係る濃淡値文書画像からの特徴抽出装置によれば，特徴抽出手段は，多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を水平な平面で切断したときにできる，２つの多角形と水平面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うこととしたので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出が可能となり，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出を行い得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【０１０２】
また，請求項８に係る濃淡値文書画像からの特徴抽出装置によれば，特徴抽出手段は，多角形統合手段により構築される多角形に対して，互いに隣接する多角形の境界線付近を複数の垂直な平面で切断したときにできる，２つの多角形と垂直面の交差曲線の凹凸の特徴と方向の特徴を抽出し，濃淡値曲面を多角形とそれらの隣接多角形間の凹凸特徴と方向の特徴として扱うこととしたので，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出が可能となり，文字，記号等の文書画像構成要素の本質的特徴を生かした特徴抽出を行い得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【０１０３】
また，請求項９に係る濃淡値文書画像からの特徴抽出装置によれば，輪郭線抽出手段は，隣接し合う多角形の境界線から，輪郭線の部分となっている可能性が高いものを，多角形表現された濃淡値曲面の局所的特徴を使って抽出し，グラフ理論の探索問題を使って，輪郭閉曲線を構成することとしたので，輪郭線抽出問題をグラフ理論を用いることによって効率よく解くことができる。
【０１０４】
また，請求項１０に係る濃淡値文書画像からの特徴抽出装置によれば，輪郭線抽出手段によって抽出された輪郭線を，多角形境界線の特徴を用いて内部輪郭と外部輪郭とに分類し，更に，請求項１１に係る濃淡値文書画像からの特徴抽出装置によれば，輪郭線抽出手段によって抽出された輪郭線から，ベクトル・ラスター変換の手法を使って，輪郭の内部を塗りつぶすことにより２値画像を生成することとし，文字等の図形の本質的な特徴である方向特徴と凹凸特徴に着目したデータ表現をもとにしているので，低解像度の画像においても，認識に有効な特徴，即ち，文字，記号等の輪郭線特徴を抽出することができ，また同時に，形状の特徴を保持した２値画像を低解像度の濃淡値画像からも生成し得る濃淡値文書画像からの特徴抽出装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】本発明の実施形態に係る濃淡値文書画像からの特徴抽出装置の構成図である。
【図３】本実施形態の濃淡値文書画像からの特徴抽出装置における特徴抽出方法を説明する概略フローチャートである。
【図４】文字の濃淡値画像データの一例を説明する説明図である。
【図５】図４の濃淡値文字画像データに対する三角形分割の例示する説明図である。
【図６】パラメータＮ＝４の場合の３次元空間内の方向の量子化を規定する直線群を例示する説明図である。
【図７】パラメータＮ＝４のときの垂直面と垂直面に沿った方向コードを例示する説明図である。
【図８】パラメータＮ＝４のときの水平面上の方向コードを例示する説明図である。
【図９】図５の分割三角形を統合してできる多角形分割を例示する説明図である。
【図１０】図９における多角形分割の一部を拡大したときの水平面と多角形の交差曲線を例示する説明図である。
【図１１】図１０に示した５つの多角形に対して求めた隣接し合う多角形間の凹凸特徴と方向特徴を例示する説明図である。
【図１２】図１０及び図１１の例に対する重み付き有向グラフを例示する説明図である。
【図１３】図９の多角形分割に対して見つかった輪郭線と外輪郭線を構成する多角形境界線を例示する説明図である。
【符号の説明】
１０１  画像入力手段
１０２  濃淡値情報生成手段
１０３  記憶手段
１０４  三角形近似手段
１０５  多角形統合手段
１０６  特徴抽出手段
２０７  輪郭線抽出手段
【図１】
0003602659.tif 000002
【図２】
0003602659.tif 000003
【図３】
0003602659.tif 000004
【図４】
0003602659.tif 000005
【図５】
0003602659.tif 000006
【図６】
0003602659.tif 000007
【図７】
0003602659.tif 000008
【図８】
0003602659.tif 000009
【図９】
0003602659.tif 000010
【図１０】
0003602659.tif 000011
【図１１】
0003602659.tif 000012
【図１２】
0003602659.tif 000013
【図１３】
0003602659.tif 000014