(57)【要約】【課題】  抽出対象となるパターンの境界が不明確である場合においても、抽出対象となるパターンを精度良く抽出することが可能なパターン抽出装置を提供する。【解決手段】  入力画像から生成された外接矩形のうち、所定の範囲の大きさまたは位置の外接矩形を抽出し、その抽出された外接矩形から一定の範囲内に探索領域を設定し、この探索領域にかかる外接矩形に基づいて、入力画像から特定のパターンを抽出する。【選択図】図２４
2005302056.tif 000002
【特許請求の範囲】
【請求項１】
入力画像に含まれるパターンに対する外接矩形を生成する外接矩形生成手段と、
前記外接矩形生成手段で生成された外接矩形のうち、所定の範囲の大きさまたは位置の外接矩形を抽出する第１の外接矩形抽出手段と、
前記第１の外接矩形抽出手段で抽出された外接矩形から一定の範囲内の探索領域を設定する探索領域設定手段と、
前記探索領域にかかる外接矩形を前記外接矩形生成手段で生成された外接矩形の中から抽出する第２の外接矩形抽出手段と、
前記第２の外接矩形抽出手段による抽出結果に基づいて、前記入力画像から特定のパターンを抽出するパターン抽出手段とを備えることを特徴とするパターン抽出装置。
【請求項２】
前記第２の外接矩形抽出手段は、
前記外接矩形生成手段で生成された外接矩形が属する縦横の座標に対応して矩形番号を格納する矩形番号格納手段と、
前記第１の外接矩形抽出手段で抽出された外接矩形から所定の範囲内の縦横の各座標に含まれる矩形番号を抽出する矩形番号抽出手段と、
前記抽出された矩形番号のうち縦横の座標の両方に含まれるものを、前記探索領域にかかる外接矩形として抽出する近傍矩形抽出手段とを備えることを特徴とする請求項１に記載のパターン抽出装置。
【請求項３】
前記矩形番号格納手段は、外接矩形の矩形番号を座標値の順序で格納し、
前記矩形番号抽出手段は、最も小さい座標値から順に矩形番号を探索し、座標値が変化するまでの間に含まれる矩形番号をその座標に属する矩形番号として抽出することを特徴とする請求項２に記載のパターン抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパターン抽出装置に関し、特に、カラー画像から見出しなどの文字領域を抽出する場合に適用して好適なものである。
【背景技術】
【０００２】
近年、コンピュータやカラープリンタなどの周辺機器の発達と、その低価格化に伴って、カラー画像を処理する分野が広がっている。このため、カラー画像を領域分割し、カラー画像の中から特定領域だけを抽出する技術が求められている。例えば、カラー画像中の同色領域を抽出する技術が求められている。
【０００３】
この技術は、例えば、ＣＣＤカメラで撮影したカラー情景画像を処理対象の入力画像とする場合では、画像認識による果物選別や、車の監視、セキュリティーのための人物監視等、多方面で求められている。
【０００４】
また、カラー文書画像を入力画像とする場合では、画像から文書名やキーワードなどを自動抽出して、検索時に使用できるものとして期待されている。その一例として、図書館での本の分類や、管理の自動システムがあげられる。その他にも、画像をデータベースとして蓄積、共有化するグループウェアでの自動キーワードまたはファイル名付けなどに利用される。これらの情報は、膨大な量のカラー文書画像を検索するのに使用される。
【０００５】
カラー画像の中から特定領域だけを抽出する技術として、以下に述べるような方法が提案されている。
（１）ＲＧＢ色空間クラスタリング法
このＲＧＢ色空間クラスタリング法では、色分解画像の作成が行われる。すなわち、ＣＣＤカメラで撮影したＲＧＢ画像の画素についてＲＧＢ空間上でのクラスタリングを行う。そして、一つのクラスタに属する画素だけで色毎の画像を作成して、同一色の領域を抽出したり、またこの手法でできた領域を併合したりして、新たな領域を抽出するものである。
【０００６】
図４４は、従来のＲＧＢ色空間クラスタリング法を示す図である。図４４において、カラー文書画像５０１が入力されたものとすると、近い色を有するパターンを抽出して、クラスタリングを行う。例えば、パターン５０２、５０７が青系統色、パターン５０３が緑系統色、パターン５０４〜５０６が赤系統色で描かれているものとすると、青系統色のパターン５０２、５０７が属するクラスタ５０８、緑系統色のパターン５０３が属するクラスタ５０９及び赤系統色のパターン５０４〜５０６が属するクラスタ５１０がＲＧＢ空間上に生成される。
【０００７】
クラスタ５０８〜５１０が生成されると、１つのクラスタ５０８〜５１０に属する画素だけでクラスタ５０８〜５１０ごとの画像を作成する。この結果、クラスタ５０８については、パターン５０２’、５０７’で構成された色分解画像５０１ａが生成され、クラスタ５０９については、パターン５０３’で構成された色分解画像５０１ｂが生成され、クラスタ５１０については、パターン５０４’〜５０６’で構成された色分解画像５０１ｃが生成される。
【０００８】
（２）ＲＧＢ以外色空間クラスタリング法
ＲＧＢ空間で表現されたＲＧＢ画像の全ての画素をＨＳＶのような別の色空間に変換し、この色空間上で何らかのクラスタリングを行い、一つのクラスタに属する画素だけで色毎の画像を作成して同一色の領域を抽出したり、この手法でできた領域を併合したりして、新たな領域を抽出するものである。
【０００９】
なお、従来のカラー文書画像から文字領域を抽出する技術を記載した文献として、例えば非特許文献１〜４がある。
（３）領域拡張法
この領域拡張法では、隣り合う画素の色の近さだけに注目してラベリングが行われる。すなわち、ＲＧＢで表現された画素を対象に、（Ｒ，Ｇ，Ｂ）の各色要素の最大値（ｍａｘ）を求め、これにより色画素を（Ｒ／ｍａｘ，Ｇ／ｍａｘ，Ｂ／ｍａｘ）と正規化し、正規化された画像を作成する。
【００１０】
図４５は、従来の領域拡張法を示す図である。図４５において、画像中の画素Ｐ１、Ｐ２、．．．をそれぞれ色要素ＲＧＢを用いて、Ｐ１（Ｒ１，Ｇ１，Ｂ１）、Ｐ２（Ｒ２，Ｇ２，Ｂ２）、・・・で表現する（図中、丸で囲んだ数字１）。
【００１１】
次に、各色要素の最大値を求める。例えば、画素Ｐ１では、Ｒ１，Ｇ１，Ｂ１のうちの最大値をｍａｘ１とし、画素Ｐ２では、Ｒ２，Ｇ２，Ｂ２のうちの最大値をｍａｘ２とする。そして、この最大値により各色要素を正規化して、正規化された画素Ｐ１′（Ｒ１／ｍａｘ１，Ｇ１／ｍａｘ１，Ｂ１／ｍａｘ１），Ｐ２′（Ｒ２／ｍａｘ２，Ｇ２／ｍａｘ２，Ｂ２／ｍａｘ２）を作成する（図中、丸で囲んだ数字２）。
【００１２】
次に、この正規化した画素Ｐ１′，Ｐ２′に対し、隣り合う画素Ｐ１′，Ｐ２′の各色要素の差分の二乗を３要素について求め、これを累積して隣接した画素Ｐ１′，Ｐ２′間の距離ｄ＝（Ｒ１／ｍａｘ１−Ｒ２／ｍａｘ２）2 ＋（Ｇ１／ｍａｘ１−Ｇ２／ｍａｘ２）2 ＋（Ｂ１／ｍａｘ１−Ｂ２／ｍａｘ２）2 を求める（図中、丸で囲んだ数字３）。
【００１３】
このようにして得られた距離ｄが、予め決めた固定のしきい値ＴＨ０より小さい場合に、両画素Ｐ１，Ｐ２を同一色とみなして、これに同じラベルを付けるラベリングを行う。このようにして全体の画像に対してラベル付けを行った後に、同一ラベルのものを抽出して、同一の色領域を抽出する。
【００１４】
この領域拡張法は、処理する対象が画素の周辺だけであるので、ＲＧＢ色空間クラスタリング法に比べて処理時間を短くできる利点がある。なお、領域拡張法については、特開平５−２９８４４３号公報に詳しく記載されている。
【００１５】
また、色分解画像から文字領域を抽出する方法として、上記の“上羽等「等色線処理によるカラー画像からの文字領域の抽出」電子情報通信学会 ＰＲＵ９４−０９、ｐ９−１６”に記載されている方法がある。この方法では、以下の手順により、カラー画像から文字領域が抽出される。
【００１６】
・１つの色の色分解画像から連結領域の外接矩形を求める。
・外接矩形のサイズ及び形状で一定の範囲にあるものだけに絞る。
・矩形毎に隣接矩形探索範囲を設け、その内部にかかる矩形を探索し、お互いに内部にかかる関係の矩形群をグループとして抽出する。
【００１７】
・グループ内の矩形の重心の直線性がよいものだけを残す。
・グループの外接矩形を求め、その内部を対象にグループを構成する領域の色に近いパターンを抽出する。
【非特許文献１】仙田等「文字の単色性に着目したカラー画像からの文字パターン抽出法」電子情報通信学会ＰＲＵ９４−０９，ｐ１７−２４
【非特許文献２】上羽等「等色線処理によるカラー画像からの文字領域の抽出」電子情報通信学会ＰＲＵ９４−０９、ｐ９−１６
【非特許文献３】松尾等「カラー文書画像からの単色文字領域の抽出」１９９７電子情報通信学会総合大会Ｄ−１２−１９
【非特許文献４】松尾等「濃淡及び色情報による情景画像からの文字列抽出」電子情報通信学会ＰＲＵ９２−１２１、ｐ２５−３２
【発明の開示】
【発明が解決しようとする課題】
【００１８】
しかしながら、従来のカラー画像の同色領域のクラスタリング方法では、以下のような問題があった。
まず、ＲＧＢ色空間クラスタリング法でも、ＨＳＶ空間のような他の色空間クラスタリング法でも、画像全体の画素を使用してクラスタリングが行われる。このため、図４４に示すように、パターン５０２の色とパターン５０７の色とが異なっている場合においても、パターン５０２の色とパターン５０７の色とが近い場合には、抽出したいパターン５０２と別のパターン５０７とが同じクラスタ５０８に分類される可能性がある。この場合、パターン５０７の色の影響で、パターン５０２の色が本来形成するクラスタ形状が変化する。この結果、パターン５０２の色が形成するクラスタ本来の色の範囲が歪んでしまい、パターン５０２を抽出する場合に、精度のよい領域抽出ができなくなってしまう。例えば、抽出したいパターン５０２の色と近い色のパターン５０７が別の場所にあり、両者が１つのクラスタ５０８として抽出されると、クラスタ５０８が表す色は、パターン５０２の色とパターン５０７の色とが混在したものとなり、このクラスタ５０８が表す色では、パターン５０２の色の範囲及びパターン５０８の色の範囲をカバーできず、抽出結果のパターン５０２’、５０７’に穴５１１、５１２が空いたり、輪郭が綺麗に抽出されなかったりする場合がある。
【００１９】
また、ＲＧＢ色空間クラスタリング法や、ＨＳＶ空間のような他の色空間クラスタリング法では、画像全体の多数の画素を対象としたクラスタリングを行うので、クラスタリングのために必要な計算時間も大きくなる。
【００２０】
また、領域拡張法では、図４５に示すように、正規化を行うため、各画素で割り算を行うための計算量が大きくなる。また、割り算の結果を浮動小数点のデータとして全画素分保有する必要があり、処理に必要なメモリ資源が多数必要となる。また、正規化した後でも、隣り合う画素が、人間がみたとき同じように見えるものについても、隣接画素との色の近さをどう定義するかによっては、固定しきい値よりも大きくかけ離れる場合があり、領域中の穴や領域輪郭が正しく抽出できない結果となる場合がある。また、隣接画素との関係だけを見ているので、文字領域と背景領域の境界で徐々に色が変化していく場合には、文字領域が背景領域と同一ラベルになってしまう場合がある。
【００２１】
また、従来の文字領域の抽出方法では、画像全体についての色分解画像が、その画像に存在する色の数だけ生成されるので、色分解画像の生成に時間がかかるという問題がある。各色分解画像は画像全体について生成されるので、例えば、その画像からタイトルを抽出する場合に、タイトル領域以外の色の影響を受けやすく、タイトルの抽出精度が悪化するという問題がある。また、連結領域の外接矩形を求める場合、抽出した色分解画像ごとに画像全体について処理を行う必要があるため、１つのカラー画像から複数（抽出した色数分の）の縦横が同じサイズの画像が必要になり、処理に時間がかかるという問題がある。
【００２２】
また、外接矩形のグルーピングも、画像全体について生成された色分解画像ごとに行われるので、処理に時間がかかるとともに、抽出対象となる文字が異なる色分解画像にクラスタリングされると、救済できないという問題がある。
【００２３】
また、グループの構成時にお互いに探索範囲にかかる矩形だけを抽出するので、文字パターンの一部であるが、小さい部分がグループから抜け落ち易い。また、抜け落ちた部分を拾うために、グループ内の色が近いパターンの抽出を最後に行うが、この時に色が近いノイズを拾いやすいという問題がある。
【００２４】
そこで、本発明の目的は、抽出対象となるパターンの境界が不明確である場合においても、抽出対象となるパターンを精度良く抽出することが可能なパターン抽出装置を提供することである。
【課題を解決するための手段】
【００２５】
上述した課題を解決するために、本発明は、入力画像に含まれるパターンに対する外接矩形を生成する外接矩形生成手段と、前記外接矩形生成手段で生成された外接矩形のうち、所定の範囲の大きさまたは位置の外接矩形を抽出する第１の外接矩形抽出手段と、前記第１の外接矩形抽出手段で抽出された外接矩形から一定の範囲内の探索領域を設定する探索領域設定手段と、前記探索領域にかかる外接矩形を前記外接矩形生成手段で生成された外接矩形の中から抽出する第２の外接矩形抽出手段と、前記第２の外接矩形抽出手段による抽出結果に基づいて、前記入力画像から特定のパターンを抽出するパターン抽出手段とを備えることを特徴とする。
【００２６】
なお、前記第２の外接矩形抽出手段は、前記外接矩形生成手段で生成された外接矩形が属する縦横の座標に対応して矩形番号を格納する矩形番号格納手段と、前記第１の外接矩形抽出手段で抽出された外接矩形から所定の範囲内の縦横の各座標に含まれる矩形番号を抽出する矩形番号抽出手段と、前記抽出された矩形番号のうち縦横の座標の両方に含まれるものを、前記探索領域にかかる外接矩形として抽出する近傍矩形抽出手段とを備えて構成されるのが望ましい。
【００２７】
また、前記矩形番号格納手段は、外接矩形の矩形番号を座標値の順序で格納し、前記矩形番号抽出手段は、最も小さい座標値から順に矩形番号を探索し、座標値が変化するまでの間に含まれる矩形番号をその座標に属する矩形番号として抽出することが望ましい。
【発明の効果】
【００２８】
本発明によれば、入力画像に含まれるパターンに対する外接矩形のうち、探索領域を設定する時の基準となる外接矩形を所定の範囲の大きさまたは位置の外接矩形に限定することにより、入力画像から文字領域等の特定のパターンを抽出する際に、ノイズなどの細かいパターンや背景などの大きなパターンの外接矩形が、文字列を探索する際の探索領域の基準として選択されることを防止することが可能となり、文字列等の特定パターンのみの抽出を効率的に行うことが可能となる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明の実施例に係わるパターン抽出装置について図面を参照しながら説明する。
図１は、本発明の第１実施例に係わるパターン抽出装置の構成を示すブロック図である。
【００３０】
図１において、色情報算出手段１は、入力画像内のパターンについての色情報を算出する。幾何学情報算出手段２は、入力画像内のパターンについての幾何学情報を算出する。分類手段３は、色情報算出手段１で算出された色情報及び幾何学情報算出手段２でされた幾何学情報に基づいて、入力画像内のパターンの分類を行う。ここで、色情報は、例えば、色空間上でのパターンの色である。また、幾何学情報は、例えば、パターンの大きさや入力画像内での位置、または、他のパターンとの相対的な位置関係である。
【００３１】
このように、入力画像内のパターンの分類を行う際に、パターンの色情報だけでなく、パターンの幾何学情報を用いることにより、カラー入力画像内から同一色が付された見出し領域を抽出する場合などにおいて、カラー入力画像内の一部の領域に範囲を限定して、異なるラベルが付された同一色のパターンを１つのグループにまとめたり、特定の位置にあるパターンや所定の大きさのパターンのみに着目して、異なるラベルが付されたパターンを１つのグループにまとめることが可能となる。
【００３２】
この結果、見出し領域の存在する可能性の大きな範囲のみについてラベリング処理を行ったり、見出し文字とならないようなノイズなどの小さなパターンや背景などの大きなパターンを処理対象から除去したりすることが可能となり、見出し領域の抽出処理の速度を向上させることが可能となるとともに、見出し領域以外の色の影響を少なくすることが可能となることから、見出し領域の抽出精度も向上させることが可能となる。
【００３３】
図２は、本発明の第２実施例に係わるパターン抽出装置の構成を示すブロック図である。
図２において、クラスタリング手段１１は、隣接する画素同士の色情報に基づいて、入力画像内の画素のクラスタリングを行う。グルーピング手段１２は、クラスタリング手段１１で得られたクラスタ同士の色情報及び幾何学情報に基づいて、クラスタのグルーピングを行う。
【００３４】
このことにより、入力画像内の画素のクラスタリングを行う際には、自分の画素の近隣の画素と色情報を比較すればよく、入力画像内の全ての画素同士を比較する必要がなくなる。
【００３５】
この結果、入力画像内の全ての画素同士を比較すると、画素同士の色情報の比較回数が入力画像内の画素数の２乗のオーダーとなるのに対し、自分の画素の近隣の画素と比較した場合には、画素同士の色情報の比較回数を入力画像内の画素数のオーダーで済ませることが可能となり、クラスタリング処理の高速化が可能となる。
【００３６】
また、クラスタリングされたクラスタをグルーピングの際の処理対象とすることにより、同一クラスタ内に存在する画素を一体的に取り扱って処理することが可能となり、個々の画素を処理対象とする必要がなくなることから、グルーピング処理を高速に行うことが可能となる。
【００３７】
さらに、入力画像内の一部の領域に範囲を限定してクラスタのグルーピングを行ったり、ノイズしか含まれていないような小さなクラスタをグルーピング対象から除いたりすることが可能となることから、グルーピング処理のより一層の高速化を達成することが可能となり、特に、カラー画像などのようにラベル数が莫大な数となるような場合には、効果が大きい。
【００３８】
図３は、本発明の第３実施例に係わるパターン抽出装置の構成を示すブロック図である。
図３において、色差算出手段２１は、所定の色で表現された領域の隣接画素間の色差を算出する。しきい値設定手段２２は、色差算出手段２１で算出された色差に基づいてしきい値を設定する。ラベリング手段２３は、しきい値設定手段２２で設定されたしきい値に基づいて、所定の色で表現された画素に隣接する画素のラベリングを行う。
【００３９】
例えば、入力画像が網点印刷法で印刷した印刷物であり、入力画像のパターンの色が、基本となる異なる色のドットの大きさ及びそれらの組み合わせで表現されているものとする。ここで、基本となる異なる色のドットの大きさが小さいために、基本となる異なる色のドットの大きさ及びそれらの組み合わせで１つの色を表現した時に、肉眼では、各ドットごとの色の違いが識別できず、その色が単一色と見える場合でも、デバイスの読み取り解像度が各ドットごとの色の違いを判別できるほど大きい場合には、肉眼では単一色と見える領域が、デバイスにとっては単一色ではないと判断される。
【００４０】
このため、このデバイスの読み取り結果をそのまま用いて、ラベリングを行うと、肉眼では単一色と見える１つのパターンに異なったラベルが付され、このラベリング結果に基づいて抽出されたパターンを人間に提示すると、人間が１つのパターンと認識する部分に、穴が開いたり、欠けが発生したりして、パターンの抽出精度が悪化する。
【００４１】
そこで、肉眼で単一色と見える部分について、デバイスで読み取った際の色の変動を求め、その色の変動の範囲内にある画素に同一のラベルを付すことにより、肉眼で単一色と見える１つのパターンに同一のラベルを付すことが可能となり、人間が１つのパターンと認識する部分に、穴が開いたり、欠けが発生したりすることを防止することが可能となる。
【００４２】
図４は、本発明の第４実施例に係わるパターン抽出装置の構成を示すブロック図である。
図４において、第１の色情報比較手段３１は、入力画像の隣接画素間の色情報を比較する。第２の色情報比較手段３２は、第１の色情報比較手段３１で比較対象となった画素の色情報と、前記画素に隣接するラベル画像の色情報とを比較する。ラベリング手段３３は、第１の色情報比較手段３１の比較結果及び第２の色情報比較手段３２の比較結果に基づいて、ラベリングを行う。ここで、ラベル画像の色情報は、例えば、同一ラベルが付された画素の色情報の平均値である。
【００４３】
例えば、入力画像のタイトル領域の色が徐々に変化しているため、タイトルを構成する文字列と背景の境界が不明確になっているものとする。この場合に、互いに隣接する画素の色情報を比較しただけでは、互いに隣接する画素間では色が似ているために、それらの画素に同一のラベルが付され、それらの画素を順々に辿っていくと、タイトル領域内に背景のパターンが取り込まれ、タイトルとは色が明らかに異なる画素にまで同一のラベルが付されることがある。
【００４４】
ここで、互いに隣接する画素間だけについて色情報を比較するのではなく、既にラベル付けがされているパターンの色情報との比較も行って、ラベル付けを行うことにより、色が徐々に変化する場合においても、タイトル領域と背景との間の境界を検出することが可能となる。
【００４５】
図５は、本発明の一実施例に係わるパターン抽出装置のシステム構成を示すブロック図である。
図５において、４１は全体的な処理を行う中央演算処理ユニット（ＣＰＵ）、４２はリードオンリメモリ（ＲＯＭ）、４３はランダムアクセスメモリ（ＲＡＭ）、４４は通信インターフェイス、４５は通信ネットワーク、４６はバス、４７は入出力インターフェイス、４８は見出し文字などの認識結果などを表示するディスプレイ、４９は見出し文字などの認識結果などを印刷するプリンタ、５０はスキャナ５１により読み取られたデータを一時的に格納するメモリ、５１は入力画像などを読み取るスキャナ、５２はキーボード、５３は記憶媒体を駆動するドライバ、５４はハードディスク、５５はＩＣメモリカード、５６は磁気テープ、５７はフレキシブルディスク、５８はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの光ディスクである。
【００４６】
パターン抽出処理を行うプログラムなどは、ハードディスク５４、ＩＣメモリカード５５、磁気テープ５６、フレキシブルディスク５７、光ディスク５８などの記憶媒体に格納される。そして、パターン抽出処理を行うプログラムなどを、これらの記憶媒体からＲＡＭ４３に読み出すことにより、パターン抽出処理を行うことができる。また、パターン抽出処理を行うプログラムなどを、ＲＯＭ４２に格納しておくこともできる。
【００４７】
さらに、パターン抽出処理を行うプログラムなどを、通信インターフェイス４４を介して通信ネットワーク４５から取り出すこともできる。通信インターフェイス４４に接続される通信ネットワーク４５として、例えば、ＬＡＮ（ＬｏｃａｌＡｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）、インターネット、アナログ電話網、デジタル電話網（ＩＳＤＮ：ＩｎｔｅｇｒａｌＳｅｒｖｉｃｅ Ｄｉｇｉｔａｌ Ｎｅｔｗｏｒｋ）、ＰＨＳ（パーソナルハンディシステム）や衛星通信などの無線通信網を用いることができる。
【００４８】
ＣＰＵ４１は、パターン抽出処理を行うプログラムが起動されると、スキャナ５１により読み取られた入力画像のラベリングを行うしきい値を設定し、スキャナ５１により読み取られた入力画像からラベル画像を生成する。ラベル画像が生成されると、入力画像のパターンの各ラベルごとに、各パターンについての外接矩形を生成する。そして、各外接矩形内の領域の色情報及び外接矩形の幾何学情報に基づいて、各外接矩形のグルーピングを行い、このグルーピングされた外接矩形の配置状態や大きさなどを考慮して、タイトル領域などを抽出する。タイトル領域が抽出されると、このタイトル領域に含まれているパターンを入力画像から抽出されたタイトルとしてディスプレイ４８やプリンタ４９に出力したり、このタイトル領域に含まれるパターンの文字認識を行い、その認識結果に基づいて、文書の自動検索を行ったりする。
【００４９】
図６は、本発明の第５実施例に係わるパターン抽出装置の構成を示すブロック図である。
図６において、６１はカラー画像入力装置、６２は外部出力装置、６３はメモリ、６４は演算装置（ＣＰＵ）、６５は画像縮小手段、６６は可変しきい値設定手段、６７はラベリング手段である。
【００５０】
カラー画像入力装置１からカラー画像信号が入力されると、画像縮小手段６５が、例えば、画素数で１／９の縮小画像を作成する。そして、この縮小画像において、領域拡張法などの手法を用いて、多少の色差を許容するラベリングを行い、同一ラベル領域を示すラベル画像と同一ラベル領域を囲む外接矩形を求める。
【００５１】
この際、隣接画素と同一ラベルを与える色の値の差のしきい値は、領域拡張法のような固定ではなく、対象となる色により可変にする。このしきい値は、例えば、対象となる色に応じて、予め作成したテーブルを可変しきい値設定手段６６が参照することにより得られる。
【００５２】
このように、縮小画像上で求めた同一ラベル領域を探索して、その中の色を表現する（Ｒ，Ｇ，Ｂ）などの数値列の種類を全て調査して、これをこのラベルの属性として記憶する。また、この色の種類から、このラベルの代表色も求める。
【００５３】
次に、このような縮小画像で求めた外接矩形を原画像に反映させ、この矩形内部だけを走査して代表色に近い色を検出し、この画素から隣接画素に対するラベリングを行う。ただし、同一と見なす色は前記の処理により同一色と見なした色の種類である。
【００５４】
そして、原画像から求めたラベル画像の中から、対象となる業務に適した特定領域抽出を行う。例えば、大きな文字で記載されている見出しや、タイトルなどのキーワードとなる文字の領域をカラー文書から抽出する場合には、外接矩形の大きさや並びの情報を使った文字列抽出技術で、対象となる文字列領域だけを抽出すればよい。
【００５５】
図７は、本発明の第６実施例に係わるパターン抽出装置の構成を示すブロック図である。
図７において、７１はカラー画像入力装置、７２は外部出力装置、７３はメモリ、７４は演算装置である。カラー画像入力装置７１は、外部のカラー画像をＲＧＢ信号で入力するものであり、例えば、ＣＣＤカメラとか、スキャナ等である。
【００５６】
外部出力装置７２は、演算装置７４により種々の処理が行われた結果得られた処理結果を出力するものであり、例えば、ディスプレイ等で構成されている。メモリ７３は画像情報やしきい値情報を保持するものであり、カラー画像入力装置７１から入力されたカラー画像信号を保持したり、保持されたカラー画像信号を演算装置７４が処理を行うことにより得られた処理結果等を保持したりする。
【００５７】
演算装置７４は、カラー画像入力装置７１により入力されたカラー画像信号に対して縮小画像を作成したり、ラベリング処理したり、特定領域抽出処理したり等の各種処理を行うものであり、画像縮小手段７５、可変しきい値設定手段７６、ラベリング手段７７、外接矩形処理７８、原画像ラベリング手段７９、特定領域抽出手段８０等を具備する。
【００５８】
図８は、図７のカラー画像処理装置の動作を示すフローチャートである。
図８において、例えば、カラー文書のような被写体を、ＣＣＤカメラやスキャナ等の撮像装置の如きカラー画像装置７１で入力し、得られたカラー画像をメモリ７３に保存する（ステップＳ１）。
【００５９】
次に、このメモリ７３上に保存されたカラー画像を、画像縮小手段７５が固定縮小率で、あるいは、縮小後に規定の大きさになるような縮小率で縮小して、メモリ７３にセットする（ステップＳ２）。この縮小率は記録しておく。縮小方法は、例えば、図９（ａ）に示すように、１／３に縮小する場合には（Ｒ，Ｇ，Ｂ）で表現された原画像の３×３の領域を縮小画像１×１に対応させることになるが、この場合、原画像の３×３の領域内部の９ケの画素の色の（Ｒ，Ｇ，Ｂ）を１単位として、図９（ｂ）に示すヒストグラムを作成し、最頻値を対応する縮小画像の画素の値としてセットする。
【００６０】
もしも、１つで決まる最頻値がなければ、次の複数値のうちの、いずれか１つを予め定めたアルゴリズムで選出して、これを対応する縮小画像の画素の値とする。
一般的には、原画像のｎ×ｎの領域を縮小画像の１×１に対応させるような１／ｎの縮小率で縮小する場合は、原画像のｎ×ｎの領域内部にある画素の色の（Ｒ，Ｇ，Ｂ）を１単位として扱ったヒストグラムを作成し、例えば、その中間値とか最頻値を対応する縮小画像の画素の値とするものである。
【００６１】
ここで、縮小画像にセットする値は、原画像の対応するｎ×ｎの領域内部にある画素の色の平均値などのような作り出した値ではなく、あくまでも、原画像に存在する値を使用する。
【００６２】
次に、このように縮小処理した縮小画像に対し、ラベリング手段７７が色ラベリング処理、すなわち、縮小画像を対象として隣り合う画素の色が近い場合に同一ラベルを与える処理を行う（ステップＳ３）。すなわち、縮小画像に対し、その左上からラスタスキャンを行い、ラベル付けがされていない画素に注目し、この画素に今まで付けたラベル値よりも＋１したラベル値を付与する。
【００６３】
例えば、図１０（ａ）に示すように、注目画素Ｃのカラーの値を（Ｒｃ，Ｇｃ，Ｂｃ）とし、この注目画素Ｃの周りの８画素を１〜８とし、これら周りの８画素のカラーの値を（Ｒｉ，Ｇｉ，Ｂｉ）（ｉ＝１〜８）とするとき、それぞれの画素のカラーの値（Ｒｉ，Ｇｉ，Ｂｉ）値を求める。すなわち、画素１，２，．．．８についてのカラーの値（Ｒ１，Ｇ１，Ｂ１），（Ｒ２，Ｇ２，Ｂ２）・・・（Ｒ８，Ｇ８，Ｂ８）を求める。
【００６４】
そして、注目画素のカラーの値（Ｒｃ，Ｇｃ，Ｂｃ）との距離ｄｃｉ（ｉ＝１〜８）を求め、それがＲ，Ｇ，Ｂについてしきい値（Ｒｔｈ，Ｇｔｈ，Ｂｔｈ）より小さい値の場合に注目画素と同一ラベルを付ける。例えば、画素１と注目画素Ｃとの距離ｄｃｌを求める場合、Ｒ，Ｇ，Ｂの各カラー毎にそれぞれの値がしきい値Ｔｔｈ，Ｇｔｈ，Ｂｔｈ以内にあるか否かを求め、３色ともしきい値よりも小さいとき、つまり類似している場合に、Ｃと同じラベルをｉに与えるためにｄｃｉに小さな値を与える。しかし、１色の値でもしきい値以上のとき、別のラベルを付与するための大きな値（しきい値ｔｈより大きな値）を与える。この距離ｄｃｌは、下記のようにして求められる。
【００６５】
ｄｃｌ＝｜Ｒｃ−Ｒｌ｜＜Ｒｔｈ
ａｎｄ｜Ｇｃ−Ｇｌ｜＜Ｇｔｈ
ａｎｄ｜Ｂｃ−Ｂｌ｜＜Ｂｔｈ                            ・・・（１）
そして、（１）式が成立するとき、ｄｃｌ＝０として同一ラベルを与え、不成立のとき、ｄｃｌ＝１０００などのしきい値よりも大きな値を付与する。一般的には、図１０（ｂ）に示すように、以下の式で距離ｄｃｉ（ｉ＝１〜８）を示すことができる。
【００６６】
０  ｉｆ｜Ｒｃ−Ｒｉ｜＜Ｒｔｈ  ａｎｄ
｜Ｇｃ−Ｇｉ｜＜Ｇｔｈ  ａｎｄ
｜Ｂｃ−Ｂｉ｜＜Ｂｔｈ
１００００    それ以外の条件
ただし、１０００はこれに限定されるものではなく、しきい値より大きい値を示す。
【００６７】
なお、カラー毎のしきい値（Ｒｔｈ，Ｇｔｈ，Ｂｔｈ）は、ＣＣＤカメラやスキャナなどの入力装置と被写体に依存したサンプルから予め求めておいた表を用いる。しかも、注目画素の色の値（Ｒ，Ｇ，Ｂ）をキーとして、この色の値に応じて予めしきい値を定めておく。
【００６８】
例えば、図１１（ａ）に示すように、入力画像について予想される注目画素の色の値（Ｒ，Ｇ，Ｂ）の全ての組み合わせをエントリとして持つ表を引いて、色の各要素毎に、要素毎に独立して定められたしきい値（Ｒｔｈ，Ｇｔｈ，Ｂｔｈ）を求める。例えば、図１１（ａ）のテーブルでは、注目画素のカラーの値が（Ｒ１，Ｇ１，Ｂ１）のときのしきい値がＲ，Ｇ，Ｂについて、それぞれ（Ｒｔｈ１，Ｇｔｈ１，Ｂｔｈ１）であり、注目画素のカラー値が（Ｒ２，Ｇ２，Ｂ２）のときのしきい値が（Ｒｔｈ２，Ｇｔｈ２，Ｂｔｈ２）である。
【００６９】
図１１（ａ）の場合は、予めサンプルの分布から予想される注目画素の色の値をキーとして、全ての色の値の組み合わせをエントリとして持つしきい値参照表を用意しておき、注目画素の色の組み合わせにより、このしきい値参照表を参照する例を示したので、表の大きさがこれらの各色の組み合わせの分だけ必要となり、非常に大きなものとなる。
【００７０】
ここで、しきい値参照表の大容量化を防止するために、しきい値参照表のエントリには全ての（Ｒ，Ｇ，Ｂ）の組み合わせは持たずに、（Ｒ，Ｇ，Ｂ）の値でクラスタリングを行った結果の（Ｒ，Ｇ，Ｂ）の代表エントリだけを持つようなしきい値参照表を用意して、注目画素の（Ｒ，Ｇ，Ｂ）の値と代表エントリとの距離値つまり類似度を求め、最も近い代表エントリを抽出して、それをキーにして色の各要素独立のしきい値（Ｒｔｈ，Ｇｔｈ，Ｂｔｈ）を求めることもできる。
【００７１】
また、しきい値参照表の大容量化を防止するため、各色の値をＮ階層に表現したとき、例えば、Ｎ＝２５６に表現したとき、カラー値毎にそのカラーに対するしきい値を記入したしきい値参照表を各カラー毎に用意し、カラー毎にしきい値をこれらのしきい値参照表より個別に求めれば、しきい値参照表の容量は、２５６×３のエントリ数で済むので大幅に小さくすることができる。例えば、注目画素のカラー値が（Ｒ１，Ｇ２，Ｂ２）の場合、図１１（ｂ）に示すように、Ｒ１に対するしきい値としてしきい値参照表Ｒを参照して、ＤＲｔｈ１を求め、Ｇ２に対するしきい値としてしきい値参照表Ｇを参照して、Ｇｔｈ２を求め、Ｂ２に対するしきい値としてしきい値参照表Ｂを参照として、Ｂｔｈ２を求めることができる。
【００７２】
さらに、しきい値を求めるしきい値参照表の形式として、図１１（ａ）に示した全ての（Ｒ，Ｇ，Ｂ）の組み合わせではなく、図１２に示すように、カラー値について複数のグループに分け、各グループ毎にしきい値を定めることもできる。図１２は各カラー値について４階層毎に１つのしきい値を定めた例であり、Ｒ１〜Ｒ４については同じしきい値Ｒｔ１を、Ｒ５〜Ｒ８については同じしきい値Ｒｔ２・・・、同様にＧ１〜Ｇ４について同じしきい値Ｇｔ１を・・・、また、ＢＮ−３〜ＢＮについては同じしきい値ＢｔＭを定めた例である。
【００７３】
これらのしきい値参照表は、特に対象物が印刷物でスキャナ入力の場合では、印刷物の状態をモデル化したものから自動的に作ることもできる。次に、このラベル処理した縮小画像、つまりラベル画像に対しても外接矩形処理を外接矩形処理手段７８が行う（ステップＳ４）。すなわち、ステップＳ３において、縮小画像についてのラベリングの結果、同一領域は同じラベル値が付与される。そして、この同一領域について外接矩形を求める。
【００７４】
例えば、図１３（ａ）に示すように、文字領域９３〜９５と他の領域９２の色が異なっているカラー画像９１が入力された場合、図１３（ｂ）に示す縮小ラベル画像９６が生成され、縮小ラベル画像９６から外接矩形９８〜１００を求めることができる。
【００７５】
図１３（ｂ）において、矩形領域９７は図１３（ａ）に示す背景領域９２に対応し、矩形領域９８〜１００はそれぞれ図１３（ａ）に示す文字領域９３〜９５に対応する。
それから、ラベル画像において、同一ラベルとして記録されている画素を走査して、その中の色の種類を全て記録する。この記録は、各外接矩形の属性情報として記録する。また、ラベル画像で同一ラベルとして記録されている全ての画素から、各ラベルの代表色を１つ求める。この求め方は、例えば、色の種類毎に頻度分布を求め、最も頻度の高い色を代表色にするというような手法で求めることができる。この代表色情報も、外接矩形の属性情報として記録する。
【００７６】
また、このラベリング処理の結果として、ラベリング手段７７は次のような出力情報を作成する。ラベル画像として、１画素あたり２バイト情報であり、縮小画像領域の高さ及び幅のサイズ、縮小率が示される。そして、この縮小画像領域内に存在する矩形数ｎｒとその矩形情報が示される。矩形情報としては、その領域内に存在する矩形の数を示す矩形数ｎｒ、矩形番号、この矩形に内包するラベル画像のラベル番号、矩形左上座標（ｘ１，ｙ１）、矩形右下座標（ｘ２，ｙ２）、矩形内の代表色（Ｒｓ，Ｇｓ，Ｂｓ）、色の種類数ｎｃ、色の種類（Ｒ０，Ｇ０，Ｂ０）、（Ｒ１，Ｇ１，Ｂ１）・・・（Ｒｎ−１，Ｇｎ−１，Ｂｎ−１）等が出力される。
【００７７】
次に、原画像ラベリング手段７９は前記出力情報を受けて、先ず、縮小画像で作られた矩形情報の左上座標値と右下座標値をそれぞれ縮小率で割って、対応する原画像での座標を求める。縮小率が１／ｎの場合は原画像の矩形は、左上座標が（ｘ１＊ｎ，ｙ１＊ｎ）であり、右下座標が｛（ｘ２＊ｎ）−１，（ｙ２＊ｎ）−１｝である。ここで、＊は乗算を示し、右下座標は１画素戻すために−１する。
【００７８】
原画像ラベリング手段７９は、この座標で示される原画像の矩形内をラスタスキャンして、既にラベルが付いていないもので、かつ、前記代表色（Ｒｓ，Ｇｓ，Ｂｓ）に近い画素を探す。近いということは、その画素のカラー値を（Ｒｉ，Ｇｉ，Ｂｉ）とするとき、例えば、
｜Ｒｓ−Ｒｉ｜＜Ｒｔｈ
ａｎｄ
｜Ｇｓ−Ｇｉ｜＜Ｇｔｈ
ａｎｄ
｜Ｂｓ−Ｂｉ｜＜Ｂｔｈ
を満たすことである。なお、ここでのしきい値Ｒｔｈ，Ｇｔｈ，Ｂｔｈは、固定値である。
【００７９】
この条件を満足する画素を検出したら、この画素に今まで付けたラベル値＋１のラベル値を付与する。それから、この注目した画素の周囲８画素を走査して、それぞれの画素のカラー値（Ｒｉ，Ｇｉ，Ｂｉ）を求め、注目画素のカラー値（Ｒｃ，Ｇｃ，Ｂｃ）との関係が、
｜Ｒｃ−Ｒｉ｜＜Ｒｔｈ
ａｎｄ
｜Ｇｃ−Ｇｉ｜＜Ｇｔｈ
ａｎｄ
｜Ｂｃ−Ｂｉ｜＜Ｂｔｈ
を満たすときに注目画素と同一ラベルを付与する（ステップＳ５）。
【００８０】
また、この処理で同一ラベルを付与されなかった場合でも、現在注目している矩形の前記属性情報である色の種類全てと比較して同様の距離を求め、それがしきい値よりも小さい場合に、注目画素と同一ラベルを付与する。
【００８１】
このようにして、図１３（ｃ）に示すように、各矩形内９７〜１００で代表色に近い画素に注目してラベル付けすることにより、その矩形領域９７〜１００内に存在する同じカラー値により構成される画素の領域１０２〜１０５が抽出される。なお、実際のカラー文書において、画像領域が図１３（ａ）に示すように大まかではなく、背景や色文字も種々の大きさのものが混在している場合には、同一ラベル領域も、図１３（ｃ）に示したように単純なものではなく、複雑なものとなる。
【００８２】
次に、このように原画像から求めたラベル画像１０１の中から、特定領域抽出手段８０が、対象となる業務に適した特定領域抽出を行う（ステップＳ６）。例えば、カラー文書から大きな文字で記載されている見出しや、タイトル等のキーワードとなる文字の領域を抽出する場合には、予め通知された外接矩形の大きさや、並びの情報を使用した従来の文字列抽出の手法に基づき、対象となる文字列領域だけを抽出することができる。
【００８３】
例えば、抽出された矩形情報を対象として、矩形の隣接関係を求める。そして、上下または左右の矩形で座標値が近く、つまり、座標値の差がしきい値内に入り、かつ、（Ｒ，Ｇ，Ｂ）の各色差がしきい値内に入るものを文字列として抽出する。そして、これを外部出力装置７２において、例えば、表示出力する。
【００８４】
また、カラー情景画像から１つの物体を抽出する場合には、ラベル画像で隣り合う領域の代表色をＨＳＶ（色相、彩度、明度）等の情報に変換し、色相が近いものを併合処理する。これにより、陰などの影響で分割されていたものを１つの領域にまとめることができる。そして、ある程度の面積を持つ領域を物体の候補領域として出力する。
【００８５】
このように、本発明の第６実施例では、縮小画像によりある程度同じ色でまとまった領域を求め、その範囲だけを原画像で精密に抽出するようにしたので、処理時間を非常に短縮することができる。また、隣り合う画素だけを対象にして、しかも、画素の色に従ったしきい値を用いてラベリングを行うので、局所的に精密な色クラスタリングが可能となり、例えば、抽出したい領域とその背景の色が近い場合にも、別に区別することが可能となり、精度のよい領域抽出ができる。
【００８６】
また、注目画素の色に応じたしきい値を求めるとき、注目画素の色の３要素をキーとして予め用意されているテーブルを参照すればよいので、しきい値を求めるためにアクセスする計算量が少なくてよい。
【００８７】
そして、注目画素の色に応じたしきい値を求めるとき、注目画素の３要素とテーブルのエントリである色の３要素との距離値の類似度を求めて注目画素の色に最も近いエントリを抽出してそこに記録されているしきい値を求めるので、しきい値の記録されているテーブルの容量を小さくすることができる。
【００８８】
しかも、色の３要素に対する独立のしきい値を、ＣＣＤカメラとか、スキャナなどの入力機器と被写体に依存したサンプルの分布から予め求めていた表を用いて決めるので、入力機器に依存したしきい値を持つ表を作ることができるため、正確なラベル付与を行うことができる。
【００８９】
次に、本発明の一実施例に係わるラベリングの際のしきい値の設定方法について説明する。雑誌などのカラー印刷物は、グラビア等、色々な印刷方法があるが、網点印刷法で印刷されたものが、世の中には多い。網点印刷法で印刷された印刷部では、人間の目には均一色と見える領域でも、拡大してみると、カラーのモアレ模様が生じている。
【００９０】
図１４は、網点印刷におけるカラーのモアレ模様を示す図である。
図１４（ａ）において、原画像１１１内の「の」と書かれた領域は、例えば、オレンジ色の一色で描かれているが、図１４（ｂ）に示すように、「の」と書かれた領域の一部を拡大すると、その領域は、様々の色が集まって構成されている。
【００９１】
このため、隣接画素の色差（ＲＧＢの輝度差など）を固定しきい値と比較して、それらの画素に同一ラベルを与えるか否かを判断すると、適応できない場合がある。例えば、図１４の「の」と書かれた領域内の画素１１１〜１１３は、「の」と書かれた領域内のその他の画素と異なるラベルが付され、原画像１１１から「の」の文字を抽出する際に、画素１１２〜１１４の部分が欠落し、抽出精度が悪化する。
【００９２】
そこで、印刷モデルを用いて、ＲＧＢの平均輝度値とスキャナ読み取り解像度ごとの隣接画素のＲＧＢ各輝度差を予め求め、それらの結果を色差テーブルに格納しておく。そして、色差テーブルを参照しながら、各色ごとにしきい値を制御することにより、ラベリングを行う。
【００９３】
例えば、図１４の「の」と書かれた領域内において、画素１１４と画素１１５との間の色差が最大の場合、画素１１４と画素１１５との間の色差をオレンジ色の領域を抽出する際のしきい値に設定する。この結果、原画像１１１から「の」の文字を抽出する際、画素１１２〜１１４の部分についても、「の」と書かれた領域内のその他の画素と同一のラベルを付すことが可能となり、画素１１２〜１１４の部分の欠落を防止することが可能となる。
【００９４】
以下、本発明の一実施例に係わるカラー印刷モデル及びスキャナ読み込みモデルから、色の平均値、隣接画素との色差及びスキャナ読み込みの際の解像度を記述した色差テーブルの作成手法について説明する。
【００９５】
図１５は、カラーの網点印刷法で印刷された実際の印刷物を拡大して示した図である。
図１５において、網点印刷法では、シアン（水色）、マゼンタ（紫）、黄色の点状の模様が場所によって点１２１〜１２３の大きさを変えながら、メッシュ状に規則的に配置されるようになっている。
【００９６】
網点印刷を行う場合、まず、３原色（または、黒を加えた４原色）の１つの色について、ある一定の間隔のメッシュの交点に、希望する濃度になるような適当な大きさの塗りつぶし円を配置して１色を刷り上げる。次に、少し回転させた同じ間隔のメッシュを用いて、塗りつぶし円の大きさを変更して、別の色で刷り上げる。もう１つの色は、さらに回転させたメッシュを用いて、塗りつぶし円の大きさも変更して刷り上げる。このような印刷方法をとることにより、１画素ずつ見るのではなく、大局的にみる人間にとっては、綺麗な均一色と見えるようになる。
【００９７】
図１６は、網点印刷法で１つのメッシュを用いて１つの色を印刷した場合に、画素ごとに輝度値が異なる理由を説明する図である。
図１６（ａ）において、網点印刷法で１つの色を印刷する場合、印刷メッシュＭ１の格子点に配置された半径ｒ１の塗りつぶし円Ｄ１を印刷することで行われる。そして、網点印刷法で印刷される色を変える場合、塗りつぶし円Ｄ１の半径ｒ１を変化させる。このため、網点印刷法で１つの色が印刷された領域は、半径ｒ１の塗りつぶし円Ｄ１が離散的に配置された領域になる。
【００９８】
図１６（ａ）の印刷物をスキャナなどで読み取る場合、スキャナなどに固有の解像度で読み取りが行われる。このため、塗りつぶし円Ｄ１は、図１６（ｂ）に示すように、読み取りの際の解像度に対応した読み取りメッシュＭ２で区切られる画素ごとに読み取られる。ここで、塗りつぶし円Ｄ１は離散的に配置されているので、読み取りメッシュＭ２で区切られる画素に含まれる塗りつぶし円Ｄ１の面積が、全ての画素について均一にならない。この結果、図１６（ｃ）に示すように、真ん中の注目画素に対し、その周囲の８つの隣接画素Ｐ１〜Ｐ８の平均輝度が異なるようになる。
【００９９】
一方、図１６（ａ）の印刷物から同一色の領域を抽出する場合、図１６（ａ）の印刷物は網点印刷法で１つの色を表すものとして印刷されているので、図１６（ｃ）の真ん中の注目画素に対し、その周囲の８つの隣接画素Ｐ１〜Ｐ８は、注目画素と同一の色を表すものとして抽出する必要がある。このため、注目画素と各隣接画素Ｐ１〜Ｐ８との輝度差を求め、これらの輝度差の中の最大値（例えば、図１６（ｃ）の例では、注目画素と隣接画素Ｐ４との輝度差）を記録しておく。そして、入力画像から同一色の領域を抽出する場合、注目画素と隣接画素との間の輝度差の最大値をしきい値として、このしきい値以下の輝度差を有する隣接画素を注目画素と同一の色を表すものとして抽出する。
【０１００】
以下、網点印刷法を忠実に再現したスキャナ読み取モデルの構築方法について説明する。
図１７は、網点印刷法におけるスキャナ読み取りモデルを示す図である。
【０１０１】
図１７において、スキャナ読み取りモデルとして、シアン、マゼンタ、黄色の印刷メッシュＭ１１、Ｍ１２、Ｍ１３を、それぞれ回転させて重ね合わせた印刷モデルを作る。ここで、シアン、マゼンタ、黄色の色の濃さを調節する場合、印刷メッシュＭ１１、Ｍ１２、Ｍ１３の各格子点に配置される塗りつぶし円Ｄ１１、Ｄ１２、Ｄ１３の大きさを調節する。
【０１０２】
この時、一般的なスキャナ読み取りモデルのパラメータは、
・印刷メッシュＭ１１、Ｍ１２、Ｍ１３の格子間隔ｍｄ（ただし、格子間隔ｍｄは、黄色、シアン、マゼンタ共通サイズ）
・黄色メッシュＭ１１の水平線からの角度θ１１
・マゼンタメッシュＭ１２の水平線からの角度θ１２
・シアンメッシュＭ１３の水平線からの角度θ１３
・黄色の塗りつぶし円Ｄ１１の半径ｒ１１
・マゼンタの塗りつぶし円Ｄ１２の半径ｒ１２
・シアンの塗りつぶし円Ｄ１３の半径ｒ１３
であるが、本実施例では、この全てのパラメータを可変にすると煩雑すぎるので、ある程度の限定を与え、以下のように設定した。
【０１０３】
・黄色メッシュＭ１１の水平線からの角度θ１１＝１５度
・マゼンタメッシュＭ１２の水平線からの角度θ１２＝３０度
・シアンメッシュＭ１３の水平線からの角度θ１３ ＝４５度
・格子間隔ｍｄ＝２０ドット
この印刷モデルを使用して、シミュレーションを行い、黄色、マゼンタ、シアンの塗りつぶし円Ｄ１１、Ｄ１２、Ｄ１３のそれぞれの半径ｒ１１、ｒ１２、ｒ１３に影響を受ける平均ＲＧＢ値（Ｒｍ，Ｇｍ，Ｂｍ）を求める。具体的には、印刷メッシュＭ１１、Ｍ１２、Ｍ１３の格子間隔ｍｄよりもかなり大きな単位面積を考え、
Ｒｍ＝２５５−単位面積中のシアンの面積×２５５／単位面積
Ｇｍ＝２５５−単位面積中のマゼンタの面積×２５５／単位面積
Ｂｍ＝２５５−単位面積中の黄色の面積×２５５／単位面積
として求める。
【０１０４】
次に、１つの色（Ｒｍ，Ｇｍ，Ｂｍ）で均一に印刷されている画像をスキャナで読み込んだ場合のスキャナ読み込みモデルについて考える。これは、印刷メッシュＭ１１、Ｍ１２、Ｍ１３と独立な間隔ｓｄを有する読み込みメッシュＭ１４を導入し、この読み込みメッシュＭ１４内のＲＧＢの各輝度＝各色の面積を求めることに相当する。
【０１０５】
ここで、読み込みメッシュＭ１４の間隔ｓｄが、スキャナ読み込み解像度に相当する。なお、同じ平均色（Ｒｍ，Ｇｍ，Ｂｍ）の画像を読み込む場合でも、スキャナ読み込み解像度が大きい場合には、隣接画素のＲＧＢ輝度値は大きく異なり、逆にスキャナ読み込み解像度が小さい場合には、読み取った結果の画素はどの画素も平均色（Ｒｍ，Ｇｍ，Ｂｍ）に近づくため、隣接画素のＲＧＢ輝度差は０に近づくようになる。
【０１０６】
具体的な１つの読み込みメッシュＭ１４内のＲＧＢ輝度値（Ｒｃ，Ｇｃ，Ｂｃ）は、以下のようになる。
Ｒｃ＝２５５−読み込みメッシュ面積中のシアンの面積×２５５／読み込みメッシュ面積
Ｇｃ＝２５５−読み込みメッシュ面積中のマゼンタの面積×２５５／読み込みメッシュ面積
Ｂｃ＝２５５−読み込みメッシュ面積中の黄色の面積×２５５／読み込みメッシュ面積
間隔ｓｄを変えた読み込みメッシュＭ１４ごとにＲＧＢ輝度値（Ｒｃ，Ｇｃ，Ｂｃ）を求めておき、隣接画素とのＲＧＢそれぞれの輝度差を求め、その中の適当な値（例えば、最大値）を色差テーブルに記録する。
【０１０７】
この時、本来は、印刷モデルでは、印刷メッシュの交点に描かれた塗りつぶし円は、ＲＧＢ相互に重なり合うので、ＲＧＢの各輝度値によって相互に影響がでて、ＲＧＢ独立とは言えないが、このスキャナ読み込みモデルでは、単純化のために、ＲＧＢは相互に独立であるという仮説を立てた。
【０１０８】
従って、ＲＧＢ輝度値、読み込み解像度、及び隣接画素の輝度差の結果が、ＲＧＢ独立のテーブルに保存される。
図１８は、Ｒのテーブルの例を示す図である。
【０１０９】
図１８において、Ｒ輝度値を０〜２５５まで変化させた場合について、スキャナ読み込み解像度が１４〜３５のそれぞれに対し、隣接画素との輝度差の最大値を求めている。ここで、Ｒ輝度値は３間隔で記録しているが、この間隔の間の値については、補間で求めることができる。
【０１１０】
なお、図の例では、Ｒのテーブルの場合について示したが、Ｇ，Ｂのテーブルも同様である。このように、網点印刷法を模倣した印刷モデルを構築することにより、網点印刷法で生成される色をコンピュータ上で再現することが可能となり、網点印刷法で実際に印刷された印刷物を解析することなく、Ｒ，Ｇ，Ｂのテーブルを生成することが可能となる。
【０１１１】
Ｒ，Ｇ，Ｂのテーブルが与えられると、このＲ，Ｇ，Ｂのテーブルを参照することにより、入力画像から同一色の範囲を検出する際のしきい値を獲得することができる。
図１９は、本発明の第実施例に係わる色差テーブル生成装置の構成を示すブロック図である。
【０１１２】
図１９において、１１１はカラー画像入力装置、１１２は外部出力装置、１１３はメモリ、１１４は演算装置（ＣＰＵ）である。演算装置１１４には、印刷モデル生成部１１５及び色差テーブル生成部１１６が設けられ、印刷モデル生成部１１５は、図１７に示した方法により印刷モデルを構築し、網点印刷法で生成される色をコンピュータ上で再現する。色差テーブル生成部１１６は、網点印刷法を模倣した印刷モデルに対し、スキャナ読み込みモデルを構築し、図１８に示すような色差テーブルを、Ｒ，Ｇ，Ｂの各色について生成する。
【０１１３】
図２０は、本発明の第７実施例に係わるパターン抽出装置の構成を示すブロック図である。
図２０において、１３１はカラー画像入力装置、１３２は外部出力装置、１３３はメモリ、１３４は演算装置（ＣＰＵ）である。演算装置１３４には、色差テーブル１３５、色分解画像生成部１３６及び文字領域抽出部１３７が設けられている。
【０１１４】
色差テーブル１３５は、例えば、図１８に示すテーブルであり、ＲＧＢの各色ごとに、輝度値、読み込み解像度及び隣接画素の輝度差が格納されている。色分解画像生成部１３６は、入力画像の読み込み解像度及びＲＧＢ輝度値に基づいて色差テーブル１３５を検索し、入力画像の読み込み解像度及びＲＧＢ輝度値に対応した隣接画素の輝度差を取得する。そして、この隣接画素の輝度差をその隣接画素についてラベリングを行う際のしきい値とする。なお、入力画像の読み込み解像度及びＲＧＢ輝度値が異なると、隣接画素の輝度差も異なるので、入力画像のラベリングを行っている途中で、入力画像の読み込み解像度及びＲＧＢ輝度が変化した場合には、色差テーブル１３５を再度検索して、ラベリングを行う際のしきい値を更新する。
【０１１５】
注目画素の色（Ｒ，Ｇ，Ｂ）をキー情報として、色差テーブル１３５を検索し、ＲＧＢ各色の同色と見なす隣接画素とのＲＧＢ各輝度差のしきい値が画素ごとに求まると、それを注目画素の周囲の画素に適応し、Ｒ，Ｇ，Ｂの各値とも隣接画素との輝度差がしきい値以内であれば、注目画素と隣接画素に同一ラベルを与える処理を行う。
【０１１６】
このラベリング処理では、隣り合う画素だけを対象にして、しかも画素の色に従ったしきい値を用いてラベリングを行うので、局所的に精密な色クラスタリングが可能となり、ラベル画像に穴が空いたり、輪郭がスムーズでなくなったりすることを防止できる。
【０１１７】
また、カラー文書画像から均一色の文字領域を高速、高精度に抽出することが可能となる。さらに、背景と物体の色が局所的に似ていて、画像全体では他の場所にも近い色がある画像に対しては、局所的に正確に同一色領域を抽出することが可能となる。
【０１１８】
また、同一色とみなされる領域でも画素の色の値が周囲の色の値よりも多少かけ離れる場合においても、その部分が、領域内の穴や輪郭部分のデコボコとして誤って抽出されることを防止し、精度良く抽出することが可能となる。
【０１１９】
ラベル画像が生成されると、入力画像のパターンの各ラベルごとに、各パターンについての外接矩形を生成する。そして、各外接矩形内の領域の色情報及び外接矩形の幾何学情報に基づいて、各外接矩形のグルーピングを行う。
【０１２０】
文字領域抽出部１３７は、色分解画像生成部１３６でグルーピングされた外接矩形の配置状態や大きさなどを考慮して、原画像から求めたラベル画像の中から、文字列領域抽出を行う。
【０１２１】
例えば、カラー文書から大きな文字で記載されている見出しやタイトルなどのキーワードとなる文字の領域を抽出する場合、外接矩形の大きさや、外接矩形の並びの情報を使うことにより、見出しやタイトルなどのキーワードとなる文字列領域だけを抽出する。
【０１２２】
図２１は、図２０のパターン抽出装置の動作を詳細に示すフローチャートである。
図２１において、まず、画像入力処理を行う（ステップＳ１１）。この画像入力処理では、ＣＣＤカメラやスキャナなどの撮像装置でカラー画像を入力し、メモリに保存する。
【０１２３】
次に、モデル解像度推定処理を行う（ステップＳ１２）。このモデル解像度推定処理では、カラー印刷のモアレを表現した印刷モデル及びスキャナ読み込みモデルから求めた色差テーブルに登録されている平均輝度及び隣接画素の輝度差の最大値を、入力画像から得られる平均輝度及び隣接画素の輝度差の最大値と比較し、入力画像全体を通して最も適合するスキャナ読み込み解像度を求める。
【０１２４】
図２２は、本発明の一実施例に係わるモデル解像度推定処理を説明する図である。
図２２において、入力画像１４１を３×３画素づつのメッシュ１４２に分割し、分割された３×３画素ａ〜ｉの平均ＲＧＢ輝度（Ｒｍ，Ｇｍ，Ｂｍ）と隣接画素の輝度差の最大値（Ｒｄ，Ｇｄ，Ｂｄ）を入力画像１４１全体について求める。ここで、３×３画素ａ〜ｉの隣接方向は２０通りあるので、これらの２０通り隣接画素の輝度差を求め、それらの輝度差のうち最大値（Ｒｄ，Ｇｄ，Ｂｄ）を採用する。
【０１２５】
そして、この平均ＲＧＢ輝度（Ｒｍ，Ｇｍ，Ｂｍ）と隣接画素の輝度差の最大値（Ｒｄ，Ｇｄ，Ｂｄ）をキー情報として色差テーブルを検索し、色差テーブルに登録されている平均輝度及び隣接画素の輝度差の最大値と最も適合するスキャナ読み込み解像度を求める。そして、入力画像１４１から求めた隣接画素の輝度差の最大値（Ｒｄ，Ｇｄ，Ｂｄ）と、色差テーブルに登録されている最も適合するスキャナ読み込み解像度での隣接画素の輝度差の最大値との差が所定の範囲内にない場合、その３×３画素ａ〜ｉに対してリジェクト符号（−１）を返し、それ以外は、適合符号（０）を返すようにする。
【０１２６】
この処理を入力画像１４１全体について行うことにより、メッシュ１４２に分割された全ての３×３画素ａ〜ｉについて、リジェクト符号（−１）または適合符号（０）が付される。リジェクト符号（−１）または適合符号（０）が付された３×３画素ａ〜ｉのうち、適合符号（０）が付された３×３画素ａ〜ｉを対象として、これらについて求めたスキャナ読み込み解像度を平均し、この平均値を入力画像１４１全体のスキャナ読み込み解像度とする。
【０１２７】
以下、ＲＧＢ独立の処理であるので、Ｒを例にしてより具体的に説明する。
まず、Ｒテーブルの解像度値をある値に固定して、ＲテーブルのＲ輝度値をスキャンしていき、平均輝度値Ｒｍが、Ｒｉ≦Ｒｍ＜Ｒｉ＋１となるＲ輝度値ＲｉをＲテーブルから検索する。この時、Ｒ輝度値Ｒｉに対する隣接画素との輝度値の最大値がＲｄｉ、Ｒ輝度値Ｒｉ＋１に対する隣接画素との輝度値の最大値がＲｄｉ＋１であるとすると、平均輝度値Ｒｍが、Ｒ輝度値ＲｉとＲ輝度値Ｒｉ＋１との間の線形補間で表されるとして、その関係を隣接画素との輝度値の最大値にも適応して、推定される隣接画素との輝度値の最大値ｉｎｆｅｒｅｄ＿ｄｅｌｔａを求める。すなわち、
ｒｌ＝Ｒｉ−Ｒｉ
ｒｍ＝Ｒｍ−Ｒｉ
ｒｎ＝Ｒｉ＋１−Ｒｍ
ｉｎｆｅｒｅｄ＿ｄｅｌｔａ＝Ｒｒｉ＊ｒｎ／ｒｌ＋Ｒｒｉ＋１＊ｒｍ／ｒｌ
である。
【０１２８】
この推定される隣接画素との輝度値の最大値ｉｎｆｅｒｅｄ＿ｄｅｌｔａと実際に画像から求めた輝度値の最大値Ｒｄとの差ｄｅｌｔａ＿ｒを、
ｄｅｌｔａ＿ｒ＝｜Ｒｄ−ｉｎｆｅｒｅｄ＿ｄｅｌｔａ｜
として求める。これと同様の処理をＧ，Ｂでも行い、ｄｅｌｔａ＿ｇ，ｄｅｌｔａ＿ｂを求める。そして、その和ｄｅｌｔａを、
ｄｅｌｔａ＝ｄｅｌｔａ＿ｒ＋ｄｅｌｔａ＿ｇ＋ｄｅｌｔａ＿ｂ
として求める。
【０１２９】
解像度パラメータをスキャンして、このｄｅｌｔａの値が最も小さくなる解像度ｒｅｓｏｌと、その時のｄｅｌｔａの値ｄｅｌｔａ＿ｍｉｎを求め、その値ｄｅｌｔａ＿ｍｉｎが、
ｄｅｌｔａ＿ｍｉｎ＞ＴＨ＿ＳＵＢ （ＴＨ＿ＳＵＢは固定しきい値）
ならば、この３×３メッシュはモデルに適応しなかったとして、リジェクト符号（−１）を返し、それ以外は、適合符号（０）を返すようにする。そして、全入力画像の中の３×３メッシュの中で適合符号がついたメッシュだけを対象に、そのメッシュの解像度ｒｅｓｏｌを平均し、この値を入力画像の解像度ｒｅｓｏｌｕｔｉｏｎとする。
【０１３０】
ｒｅｓｏｌｕｔｉｏｎ＝（Σ適合符号のメッシュのｒｅｓｏｌ）
／適合符号のメッシュの数
なお、この解像度という言葉は、入力画像が実際にスキャナで読み込まれたときの解像度ではなく、この画像を予め用意したモデルに適合させたときのモデル上の読み取り解像度を表す。
【０１３１】
次に、色ラベリング処理を行う（ステップＳ１３）。この色ラベリング処理では、隣り合う画素の色が近い場合に同一ラベルを与え、ラベル画像と同一ラベルの連結領域の外接矩形を求める。外接矩形の情報には、外接矩形の座標値、外接矩形内の連結領域の平均色（Ｒ，Ｇ，Ｂ）、外接矩形内の連結領域のラベル番号、連結領域の面積（画素数）などを格納する。
【０１３２】
具体的には、入力画像の左上からラスタスキャンを行い、ラベル付けがされていない画素に注目する。この画素のＲＧＢ輝度値と推定解像度ｒｅｓｏｌｕｔｉｏｎを用いて色差テーブルを検索し、隣接画素との輝度値の最大値をＲＧＢそれぞれについて求める。隣接画素との輝度値の最大値が求まると、この隣接画素との輝度値の最大値を着目画素にラベル付けする際のしきい値とする。
【０１３３】
このラベリング処理の時に、１画素から始まって次第に拡張していく同一ラベル領域に対して、１画素追加する度に、ラベル領域内の平均色（Ｒ，Ｇ，Ｂ）を求める。そして、このラベル領域と同一のラベルをこのラベル領域の周囲画素に付すかどうかを判断する時に、新たにラベル付けする周囲画素の色が、既にラベル付けされたラベル領域の平均色としきい値以上に離れている場合には、隣接画素間での色差がしきい値以内にあっても、新たにラベル付けする周囲画素に、既にラベル付けされたラベル領域と異なるラベルを付すようにする。この処理により、文字領域と背景領域の境界の次第に色が変化した場合でも、正しく文字領域を抽出することが可能となる。
【０１３４】
図２３は、本発明の一実施例に係わる色ラベリング処理を説明する図である。
図２３において、画素ｅの色が黒で、この画素ｅから遠ざかるに従って、色が黒から赤に徐々に変化しているものとする。そして、画素ｅと画素ａ〜ｄ、ｆ〜ｉは、画素ｅと画素ａ〜ｄ、ｆ〜ｉの色差がしきい値以内の場合は、画素ｅと画素ａ〜ｄ、ｆ〜ｉに対して同一のラベルが付される。
【０１３５】
次に、画素ｊのラベル付けを行う場合、画素ｆと画素ｊの色差がしきい値以内かどうかが判断されるとともに、画素ａ〜ｉの色の平均値と画素ｊの色の差がしきい値以内かどうかが判断される。そして、画素ｆと画素ｊの色差がしきい値以内であっても、画素ａ〜ｉの色の平均値と画素ｊの色の差がしきい値をこえる場合は、画素ｊには画素ｆと異なるラベルが付される。
【０１３６】
ここで、画素ｅから遠ざかるに従って、色が徐々に変化している場合には、画素ｊの色と画素ｆの色は似ているけれども、画素ｊの色と画素ｅの色の違いは顕著になってくる。このため、既にラベル付けされている画素ａ〜ｉの色の平均値を画素ｊの色と比べると、画素ａ〜ｉの色の平均値には画素ｅの色の影響が反映されることから、画素ｆと画素ｊの色差に比べた場合に対し、色に差が大きくなる。
【０１３７】
この結果、色が徐々に変化している場合においても、画素ｆと画素ｊとの間で境界を区切ることが可能となり、黒の領域と赤の領域に同一のラベルが付されることを防止できる。
【０１３８】
以下、具体的な求め方を輝度値Ｒを例に取り説明する。
Ｒテーブルの解像度値を推定解像度に固定して、ＲテーブルのＲ輝度値をスキャンしていき、注目画素の輝度値Ｒが、Ｒｉ≦Ｒ＜Ｒｉ＋１となるＲ輝度値ＲｉをＲテーブルから検索する。この時、Ｒ輝度値Ｒｉに対する隣接画素との輝度値の最大値をＲｄｉ、Ｒ輝度値Ｒｉ＋１に対する隣接画素との輝度値の最大値をＲｄｉ＋１とすると、注目画素の輝度値Ｒが、ＲテーブルのＲ輝度値ＲｉとＲテーブルのＲ輝度値Ｒｉ＋１の間の線形補間で表されるとして、その関係を隣接画素との輝度値の最大値にも適応して、推定される隣接画素との輝度値の最大値ｄｅｌｔａ＿ｒを求める。すなわち、
ｒｌ＝Ｒｉ−Ｒｉ＋１
ｒｍ＝Ｒ−Ｒｉ
ｒｎ＝Ｒｉ＋１−Ｒ
ｄｅｌｔａ＿ｒ＝Ｒｒｉ＊ｒｎ／ｒｌ＋Ｒｒｉ＋１＊ｒｍ／ｒｌ
として求める。Ｇ，Ｂについても同様である。
【０１３９】
このようにして、未処理の注目画素の（Ｒ，Ｇ，Ｂ）値から隣接画素との輝度差の最大値（ｄｅｌｔａ＿ｒ，ｄｅｌｔａ＿ｇ，ｄｅｌｔａ＿ｂ）を求め、この隣接画素との輝度差の最大値（ｄｅｌｔａ＿ｒ，ｄｅｌｔａ＿ｇ，ｄｅｌｔａ＿ｂ）をラベリング時のしきい値とする。
【０１４０】
次に、この未処理の注目画素の周囲８画素を走査して、注目画素の周囲に既にラベル付けされた画素があり、その既にラベル付けされた画素のＲＧＢ輝度値（Ｒｓ，Ｇｓ，Ｂｓ）が、
｜Ｒ−Ｒｓ｜＜＝ｄｅｌｔａ＿ｒ
かつ
｜Ｇ−Ｇｓ｜＜＝ｄｅｌｔａ＿ｇ
かつ
｜Ｂ−Ｂｓ｜＜＝ｄｅｌｔａ＿ｂ
の場合に、注目画素は、その周囲画素と近い色であるので、周囲画素のラベルをカレントラベルｒｅｇｉｏｎとして保存し、注目画素のラベルとしてカレントラベルｒｅｇｉｏｎを与える。また、同時に、カレントラベルｒｅｇｉｏｎが与えられている領域の平均色（Ｒｍ，Ｇｍ，Ｂｍ）として、周囲のラベルの平均色に注目画素の色を加味した新たな平均色を求める。
【０１４１】
それ以外の場合は、カレントラベルとして、今まで付けたラベル値＋１のラベル値を設定し、注目画素のラベルにもそのラベル値を付与する。この場合でも、領域の平均色（Ｒｍ，Ｇｍ，Ｂｍ）として、注目画素のＲＧＢ値を設定する。
【０１４２】
どちらの場合でも、注目画素の座標値を処理対象座標配列に保存する。
次に、注目画素の周りに同色領域を拡張する処理を行う。この処理では、処理対象座標配列の中から、先頭の座標値を取り出し、その座標の画素を注目画素とする。注目画素のＲＧＢ輝度値からＲＧＢ各色の隣接画素の輝度値の差の推定しきい値（ｄｅｌｔａ＿ｒ，ｄｅｌｔａ＿ｇ，ｄｅｌｔａ＿ｂ）を求める。
【０１４３】
また、これまでのこの領域の平均色の（Ｒｍ，Ｇｍ，Ｂｍ）値と推定解像度から平均色の各ＲＧＢの輝度差のしきい値（ｄｅｌｔａ＿ｒｍ，ｅｌｔａ＿ｇｍ，ｅｌｔａ＿ｂｍ）を求める。
【０１４４】
次に、図１０（ａ）に示すように、注目画素の周囲８画素を走査して、注目画素の周囲の各画素の（Ｒｉ，Ｇｉ，Ｂｉ）値（ｉ＝１〜８）を求め、注目画素の（Ｒｃ，Ｇｃ，Ｂｃ）値や平均色の（Ｒｍ，Ｇｍ，Ｂｍ）値とのＲＧＢ各色の輝度差を求め、それが、
｜Ｒｉ−Ｒｃ｜＜＝ｄｅｌｔａ＿ｒ
かつ
｜Ｇｉ−Ｇｃ｜＜＝ｄｅｌｔａ＿ｇ
かつ
｜Ｂｉ−Ｂｃ｜＜＝ｄｅｌｔａ＿ｂ
｜Ｒｉ−Ｒｍ｜＜＝ｄｅｌｔａ＿ｒｍ
かつ
｜Ｇｉ−Ｇｍ｜＜＝ｄｅｌｔａ＿ｇｍ
かつ
｜Ｂｉ−Ｂｍ｜＜＝ｄｅｌｔａ＿ｂｍ
の場合に、注目画素と同一ラベルを付け、周囲画素の座標を処理対象座標配列に追加する。今処理した注目画素は、処理対象座標配列から削除する。
【０１４５】
次に、処理座標のｘ，ｙの最大値、最小値を求め、それをこのラベル領域の外接矩形として保存する。また、このラベル領域の平均色を外接矩形の属性として保存する。
この処理を処理対象配列の内容がなくなるまで続ける。
【０１４６】
ラベリングの結果、ラベル画像（同一領域は、同じラベル値が付与されている画像）と同じラベルを持つ領域を囲む外接矩形が獲得される。
また、ラベリング処理の出力情報として、以下のデータが出力される。
【０１４７】
・ラベル画像：４バイト／１画素
・外接矩形
矩形数 ：ｍａｘｃｏｕｎｔ
矩形情報：１ｂｔｂｌ
内包するラベル画像のラベル番号：ｌａｂｅｌ
矩形左上座標 ：（ｘｍｉｎ，ｙｍｉｎ）
矩形右下座標 ：（ｘｍａｘ，ｙｍａｘ）
矩形内の代表色 ：（ｒ，ｇ，ｂ）
所属するグループ番号 ：ｓｔｒｉｎｇ＿ｌａｂｅｌ
輪郭長 ：ｃｏｎｔｏｕｒ
次に、注目矩形抽出処理を行う（ステップＳ１４）。この注目矩形抽出処理では、全ての色の外接矩形を対象にして、ある事前に決めた範囲に入るサイズの外接矩形を注目矩形として抽出する。
【０１４８】
具体的には、ｘ方向長さが２３ｄｏｔ（１００ｄｐｉ時）以上、画像の幅の１／２以下、かつ、ｙ方向長さが２３ｄｏｔ（１００ｄｐｉ時）以上、画像の高さの１／２以下の外接矩形を注目矩形として抽出する。
【０１４９】
この注目矩形抽出処理により、外接矩形同士をグルーピングする際の基準となる外接矩形の大きさを限定することが可能となり、例えば、タイトル領域を抽出する場合に、タイトルとなる文字の大きさに適合した外接矩形を基準として、外接矩形同士をグルーピングすることが可能となり、ノイズや背景などのタイトルには含まれない外接矩形が基準とされて、グルーピング処理が行われることを防止することが可能となることから、不要な処理を省略して、処理速度を向上させることが可能となる。
【０１５０】
次に、注目矩形の周りの探索範囲とそこにかかる矩形抽出を行う（ステップＳ１５）。この探索範囲にかかる矩形抽出処理では、注目矩形の周囲に、あるサイズの探索範囲を設定し、その範囲にかかる矩形を抽出する。
【０１５１】
図２４は、本発明の一実施例に係わる注目矩形の周囲の探索範囲の設定方法を説明する図である。
図２４において、矩形番号１〜３０の外接矩形が抽出され、矩形番号１の外接矩形１５１を注目矩形としたものとする。そして、この外接矩形１５１の周りに探索範囲１５２が設定されたものとすると、外接矩形１５１についてのグルーピングの処理対象として、探索範囲１５２にかかる矩形番号２〜２４の外接矩形のみを選択し、探索範囲１５２にかからない矩形番号２５〜３０の外接矩形については、外接矩形１５１のグルーピングの処理対象としない。
【０１５２】
このように、外接矩形同士をグルーピングする際に、外接矩形の探索範囲を注目矩形の周りに限定することにより、所定の範囲内にまとまって存在している文字列のみを抽出することが可能となり、例えば、タイトル領域を抽出する場合に、タイトルには含まれないような離れた位置に存在する文字を考慮する必要がなくなることから、タイトル領域の抽出を効率的に行うことが可能となる。
【０１５３】
具体的には、探索範囲１５２は、注目矩形１５１の縦横の長さの内、長い方をｌｅｎとして、ｌｅｎと１００ｄｐｉで３５ｄｏｔの小さい方を注目矩形の周囲の探索範囲長ｒａｎｇｅ＿ｓｉｚｅとして求める。
【０１５４】
注目矩形の周囲ｒａｎｇｅ＿ｓｉｚｅの範囲にかかる外接矩形を高速に求めるため、以下の方法を用いる。
図２５は、本発明の一実施例に係わる注目矩形の周囲の探索範囲にかかる矩形の抽出方法を説明する図である。
【０１５５】
図２５において、矩形番号１〜４の外接矩形１６１〜１６４が抽出されたものとすると、ＸＹの各座標値に存在する矩形番号及び矩形数を求め、これらの矩形番号及び矩形数をＸＹの各座標値ごとに登録する。
【０１５６】
例えば、Ｘ座標値１〜４の位置には外接矩形１６１〜１６４が存在しないので、矩形数ｎ＝０、矩形番号＝空が登録され、Ｘ座標値５〜１３の位置には矩形番号４の外接矩形１６４が存在しているので、矩形数ｎ＝１、矩形番号＝４が登録され、Ｘ座標値１４の位置には矩形番号３の外接矩形１６３及び矩形番号４の外接矩形１６４が存在しているので、矩形数ｎ＝２、矩形番号＝３、４が登録され、Ｘ座標値１５、１６の位置には矩形番号４の外接矩形１６４が存在しているので、矩形数ｎ＝１、矩形番号＝４が登録される。以下、同様である。
【０１５７】
次に、矩形番号３の外接矩形１６３を注目矩形とし、この外接矩形１６３の周りに探索範囲１６５が設定されたものとすると、この探索範囲１６５に含まれるＸＹの各座標値を求める。そして、ＸＹの各座標値の矩形番号をＸＹそれぞれについて求め、ＸＹの両方に含まれる矩形番号を探索範囲１６５にかかる外接矩形とする。例えば、探索範囲１６５のＸ座標に含まれる外接矩形の矩形番号は２〜４、探索範囲１６５のＹ座標に含まれる外接矩形の矩形番号は１〜４であるので、ＸＹの両方に含まれる矩形番号は２〜４となる。この結果、探索範囲１６５にかかる外接矩形として、矩形番号２〜４に対応する外接矩形１６２〜１６４が得られる。
【０１５８】
具体的には、以下のａ）〜ｄ）の処理を行う。
ａ）画像全体のＸ，Ｙ軸へ矩形番号を投影する。
画像全体のＸ，Ｙ軸の１画素毎に、それに属する矩形数と矩形番号の集合を登録する。例えば、矩形番号ｉがＸ軸の（ｘ１，ｘ２）の範囲にあるとすれば、Ｘ軸のｘ１からｘ２の座標には、番号ｉが矩形番号の集合に入ることになる。同じことを全矩形について縦横座標について行う。
【０１５９】
ｂ）注目矩形の周囲にｒａｎｇｅ＿ｓｉｚｅの範囲を設定する。
ｃ）ｒａｎｇｅ＿ｓｉｚｅの範囲のＸ軸の座標毎の矩形種類を論理ＯＲして矩形番号の集合を抽出する。
【０１６０】
同様にＹ軸でも抽出する。
ｄ）Ｘ軸から求めた矩形番号の集合と、Ｙ軸から求めた矩形番号の集合を論理ＡＮＤして、この注目矩形の周囲にある矩形集合を決定する。
【０１６１】
なお、図５の矩形番号の格納方法では、画像全体に存在する全ての矩形番号を格納する容量が各座標値ごとに必要となり、記憶容量が大きくなる。そこで、上述した座標毎の矩形数及び矩形番号を高速に、かつ必要メモリを最小に求めるために、以下のような方式をとる。
【０１６２】
図２６は、本発明の一実施例に係わる注目矩形の周囲の探索範囲にかかる矩形情報の格納方法を説明する図である。
図２６（ａ）において、矩形番号１、２の外接矩形１７１、１７２が抽出されたものとし、外接矩形１７１はＸ座標が１５５〜１６５の範囲内にあり、外接矩形１７２はＸ座標が１６０〜１６３の範囲内にあるものとする。このため、図２６（ｂ）に示すように、外接矩形１７１については、Ｘ座標が１５５〜１６５の位置に矩形番号１が登録され、外接矩形１７２については、Ｘ座標が１６０〜１６３の位置に矩形番号２が登録される。
【０１６３】
次に、図２６（ｃ）に示すように、抽出された矩形番号１、２を、Ｘ座標１５５〜１６５の順序で矩形番号１、２順に並べ換え、Ｘ座標値が同じ値を示す矩形番号が幾つあるかを数えることにより、各座標値の矩形数を求めることができる。
【０１６４】
具体的には、以下のｉ）〜ｖ）の処理を行う。
ｉ）全ての矩形の横幅を合計して、その長さの数だけ矩形番号、座標の情報を持ったデータ構造を用意する。
【０１６５】
ｉｉ）矩形の座標と矩形番号を用意されたデータ構造のデータにセットする。
ｉｉｉ）このデータ構造のデータを座標値でソートする。
ｉｖ） データの座標値を順にみていき、座標値が同じものの数を座標値毎に数え、それをその座標に属する矩形数とする。また、その座標毎の矩形数分だけ矩形番号を入れる記録領域を確保する。ソートしたデータ構造を先頭からスキャンしていき、座標が同じ間は数をカウントしていき、座標値が変わったところで数を確定させ、それを保存する。
【０１６６】
ｖ）ソートしたデータ構造で、座標値が同じ物の矩形番号を上で確保した領域に格納する。これもソートしたデータ構造を先頭からスキャンしていき、座標が同じ間は、矩形番号を格納領域にセットする。
【０１６７】
次に、同色グループ抽出処理を行う（ステップＳ１６）。この同色グループ抽出では、１つの注目矩形に注目して、その注目矩形内のパターンの平均色からラベリングの時と同様にＲＧＢ各色の輝度差のしきい値を求める。注目矩形の探索範囲にかかっている外接矩形の中で、注目矩形とのＲＧＢ輝度差が、しきい値以内のものを同一グループとして抽出し、グループ情報領域に格納する。さらに、新たにグループに追加された外接矩形を基準にして同様の処理を行い、グループに追加矩形が無くなるまで繰り返し処理する。
【０１６８】
具体的には、１つの注目矩形の値（Ｒｃ，Ｇｃ，Ｂｃ）とその周囲矩形の集合の中の１つの外接矩形ｉの値（Ｒｉ，Ｇｉ，Ｂｉ）のＲＧＢ空間上の距離を以下のように定義する。
【０１６９】
ｄｉｓｔ＝｜Ｒｃ−Ｒｉ｜＋｜Ｇｃ−Ｇｉ｜＋｜Ｂｃ−Ｂｉ｜
また、注目矩形の値（Ｒｃ，Ｇｃ，Ｂｃ）と解像度ｒｅｓｏｌｕｔｉｏｎから求められるＲＧＢの各輝度差をｄｅｌｔａ＿ｒ，ｄｅｌｔａ＿ｇ，ｄｅｌｔａ＿ｂとする。注目矩形の値（Ｒｃ，Ｇｃ，Ｂｃ）とその周囲の外接矩形の集合の中の１つの外接矩形ｉの値（Ｒｉ，Ｇｉ，Ｂｉ）が以下の条件を満足するとき、注目矩形の周囲の外接矩形は、注目矩形のグループに属すると判定して、周囲の外接矩形ｉを注目矩形のグループに格納する。
【０１７０】
ｄｉｓｔ＜ＴＨ＿ＲＧＢ （ＴＨ＿ＲＧＢ＝２０）
または
（｜Ｒｃ−Ｒｉ｜＜ｄｅｌｔａ＿ｒ
かつ
｜Ｇｃ−Ｇｉ｜＜ｄｅｌｔａ＿ｇ
かつ
｜Ｂｃ−Ｂｉ｜＜ｄｅｌｔａ＿ｂ）
また、同時に、この新たにグループに加わった矩形番号を新規追加矩形領域に格納しておく。
【０１７１】
次に、新規追加矩形領域の先頭の矩形番号を取り出し、それを新たな注目矩形として、その周囲にある外接矩形を求め、上の手順を繰り返して、グループに属する外接矩形を求める。この手順をグループに新たに加わる矩形が無くなるまで繰り返す。
【０１７２】
以上の処理により、以下の抽出するグループ情報のデータ構造が得られる。
グループ内の矩形数 ：ｎｕｍ
グループを構成する矩形番号 ：ｃｈｉｌｄ
重なり矩形統合後の矩形数 ：ｏｖｅｒｌａｐ＿ｎｕｍ
重なり矩形統合後の矩形情報 ：ｏｖｅｒｌａｐ
（データタイプは、矩形情報１ｂｔｂ１型）
グループ内文字列の方向コード：ｏｒｉｅｎｔ
グループ内の文字列数 ：ｇｙｏｕ＿ｎｕｍ文字列の矩形情報 ：ｇｙｏｕ
次に、グループ内平均文字線太さ抽出処理を行う（ステップＳ１７）。このグループ内平均文字線太さ抽出処理では、グループ内の外接矩形に対応するラベル画像のパターンに対して、輪郭追跡処理を行い、輪郭長を求める。すなわち、グループに属する１つの外接矩形の矩形範囲内で、その外接矩形のラベル番号に注目して、ラベル画像上で、輪郭追跡処理を行う。抽出した輪郭の長さを、その矩形の輪郭長の属性にセットする。そして、そのパターンの面積を輪郭長で割って、文字の線の平均的な太さを求め、その値を矩形の属性として矩形情報に登録する。
【０１７３】
図２７は、本発明の一実施例に係わる文字線の太さの算出方法を説明する図である。
図２７（ａ）において、例えば、「フ」というパターンが抽出されたものとすると、「フ」というパターンに含まれる画素数を数えることにより、「フ」というパターンの面積Ｓを算出する。
【０１７４】
次に、図２７（ｂ）に示すように、「フ」というパターンの輪郭を抽出し、この輪郭長Ｌを算出する。そして、「フ」というパターンの面積Ｓを輪郭長Ｌで割って、「フ」というパターンの平均的な太さＷを求める。
【０１７５】
次に、文字線太さによる再グループ化処理を行う（ステップＳ１８）。この再グループ化処理では、グループ内の外接矩形を対象に、外接矩形の平均文字線太さを用いて、グループ化を行い、新たなグループ情報を構築する。すなわち、グループ内の外接矩形を対象にして、図２１のステップＳ１４〜Ｓ１６の処理をを繰り返す。ここで、ステップＳ１６のグループ化の時に、ステップＳ１５で使用した色情報だけでなく、推定文字線太さ（＝矩形内のパターン面積／パターンの輪郭長）も使用する。
【０１７６】
図２８は、本発明の一実施例に係わる文字線の太さによる再グルーピング処理を説明する図である。
図２８において、「グループ１」という文字列と「グループ２」という文字列が同一色で記述され、互いに近接して配置されているため、「グループ１」という文字列と「グループ２」という文字列が同一のグループ１８１にグルーピングされたものとする。
【０１７７】
ここで、「グループ１」という文字列に含まれる文字の太さと「グループ２」という文字列に含まれる文字の太さを算出し、異なる太さの文字を別々のグループに分割する。この結果、「グループ１」という文字列はグループ１８２にグルーピングされ、「グループ２」という文字列はグループ１８３にグルーピングされる。
【０１７８】
この処理により、元のグループで背景などの文字パターンと同色のものがあり、背景と文字パターンが同じグループに属していたものを、別々のグループにしたり、文字パターンだけのグループでもフォントやサイズが異なるものを別々のグループにしたりすることができる。
【０１７９】
具体的には、２つの外接矩形のうち、第１の外接矩形の推定文字線太さｔｈｉｃｋ１及び第２の外接矩形の推定文字線太さｔｈｉｃｋ２から、文字線太さの比ｔｈｉｃｋ＿ｒａｔｅを以下のように求める。
【０１８０】
ｔｈｉｃｋ＿ｒａｔｅ＝ｍａｘ（ｔｈｉｃｋ１，ｔｈｉｃｋ２）
／ｍｉｎ（ｔｈｉｃｋ１，ｔｈｉｃｋ２）
そして、図２１のステップＳ１５と同じように、以下の条件を満足した時に、２つの外接矩形を同じグループとして記録する。
【０１８１】
ｔｈｉｃｋ＿ｒａｔｅ＜ＴＨ＿ＴＨＩＣＫ＿ＲＡＴＥ
かつ
（ｄｉｓｔ＜ＴＨ＿ＲＧＢ
または
（｜Ｒｃ−Ｒｉ｜＜ｄｅｌｔａ＿ｒ
かつ
｜Ｇｃ−Ｇｉ｜＜ｄｅｌｔａ＿ｇ
かつ
｜Ｂｃ−Ｂｉ｜＜ｄｅｌｔａ＿ｂ））
ただし、ＴＨ＿ＴＨＩＣＫ＿ＲＡＴＥは、２．５と設定している。
【０１８２】
この処理を元のグループ内全ての外接矩形について行い、グループ内の新たなグルーピングを行う。
文字線太さを求める場合、パターンの輪郭を求める必要があるが、輪郭追跡を高速化するため、以下の処理を行う。
【０１８３】
図２９は、本発明の一実施例に係わる輪郭追跡における画素の探索開始点の設定方法を説明する図である。
図２９（ａ）において、画素ａ〜ｉで構成されるパターンの輪郭を求めるものとすると、ラベル画像の左上からラスタスキャンを行うことにより、画素ａが見つかる。画素ａが見つかると、画素ａに隣接する８つの画素のうち、画素ａの直前に探索された画素の次の画素ａ’を探索開始点として、画素ａに隣接する画素を時計回りに探索する。そして、画素ｅが見つかると、図２９（ｂ）に示すように、画素ｅに隣接する８つの画素のうち、画素ｅの直前に輪郭として探索された画素ａの次の画素ｅ’を探索開始点として、画素ｅに隣接する画素を時計回りに探索する。そして、画素ｉが見つかると、図２９（ｃ）に示すように、画素ｉに隣接する８つの画素のうち、画素ｉの直前に輪郭として探索された画素ｅの次の画素ｉ’を探索開始点として、画素ｉに隣接する画素を時計回りに探索する。以下、同様にして、図２９（ｄ）に示すように、画素ａ→画素ｅ→画素ｉ→画素ｈ→画素ｇ→画素ｆ→画素ｂ→画素ｃが画素ａ〜ｉで構成されるパターンの輪郭として抽出される。
【０１８４】
具体的には、以下のａ）〜ｆ）の処理が行われる。
ａ）矩形サイズの処理済みフラグを用意し、初期値として、全て未処理フラグとして０をセットする。
【０１８５】
ｂ）矩形範囲内を処理済みフラグとラベル画像で同時に左上からラスタスキャンして、画素が処理済みフラグが０で、かつラベル番号がカレント矩形のラベル番号である画素ｉを探す。輪郭長を０と設定する。
【０１８６】
ｃ）画素ｉから周囲の８画素を図３０の０から順番に時計回りに探索し、画素が処理済みフラグが０で、かつラベル番号がカレント矩形のラベル番号である画素がある場合には、その画素の方向コードＤＣを抽出する。
【０１８７】
図３０は、本発明の一実施例に係わるカレント画素からみた方向コードを示す図である。
図３０において、Ｃはカレント画素、０〜７はカレント画素からみた周囲画素で、Ｃからみた方向コードＤＣである。画素ｉから周囲の８画素を探索する場合、この順番で探索する。
【０１８８】
ｄ）輪郭を構成する次の画素として、カレント画素Ｃから検出した方向コードＤＣの画素へ移動する。この時、輪郭長としてすでに計算した輪郭長を１つだけインクリメントする。そして、移動先の画素を新たなカレント画素Ｃ′として、再びその周囲の８画素に対し、処理済みフラグが０で、かつラベル番号がカレント矩形のラベル番号である画素を探す。この時、新たなカレント画素Ｃ′の周囲の８画素を探索する開始方向コードは、前回の方向コード（ＤＣ＋５）を８で割った余りのＤＣ′から開始して、時計回りに探索する。
【０１８９】
これにより、前画素の輪郭追跡処理ですでに探索済みの画素を二重に探索するのを避け、高速な輪郭追跡処理が可能となる。
ｅ）画素移動による輪郭追跡処理を最初に発見した開始座標になるまで続け、この時の輪郭長を、この矩形内にあるラベル値のパターンの１つの輪郭の輪郭長として抽出する。
【０１９０】
ｆ）ｃ）からｆ）の処理を同じパターンの他の輪郭でも行い、全ての輪郭長を足し合わせて、最終的にこのパターンの輪郭長として抽出する。
次に、グループ内の大きな矩形削除処理を行う（ステップＳ１９）。このグループ内の大きな矩形削除処理では、ノイズ除去のため、グループ内で平均的な矩形サイズを求め、それを基準に極端に大きなサイズの矩形を削除する。
【０１９１】
図３１は、本発明の一実施例に係わるグループ内の大きな矩形削除処理を説明する図である。
図３１（ａ）において、外接矩形１９２〜２０１がグループ１９１にグルーピングされているものとすると、グループ１９１内の外接矩形１９２〜２０１の大きさを求める。そして、外接矩形１９２の大きさが外接矩形１９３〜２０１の大きさに比べてかけ離れているものとすると、図３１（ｂ）に示すように、グループ１９１から外接矩形１９２を削除し、外接矩形１９３〜２０１よりなるグループ２０２を生成する。
【０１９２】
具体的には、以下のａ）〜ｄ）の処理を行う。
ａ）グループ内の外接矩形の高さのヒストグラムを作成して、最大頻度値を示す矩形高さｆｒｅｑ＿ｈｅｉｇｈｔを以下の方法で求める。
【０１９３】
ｉ）ヒストグラムにぼかし用のウィンドウを用いてコンボリューション演算（移動和）を行い、ヒストグラムをぼかす。具体的なぼかし用ウィンドウは、例えば、「１１１１１」５画素からなる。
【０１９４】
ｉｉ）最小高さ値（具体的には、１００ｄｐｉで２３ｄｏｔ）を予め決めておき、それ以上で最大頻度を示す矩形高さｆｒｅｑ＿ｈｅｉｇｈｔを求める。
図３２は、本発明の一実施例に係わる最大頻度値を示す矩形高さの算出方法を説明する図である。
【０１９５】
図３２（ａ）において、図３１の外接矩形１９２〜２０１の高さの頻度が求まると、ぼかし用ウィンドウ２０５を用いて、図３２（ｂ）に示すように、図３２（ａ）で求まっている矩形高さの頻度の移動和を算出する。矩形高さの頻度の移動和が求まると、外接矩形１９２〜２０１の高さのうち、最大頻度を示す矩形高さｆｒｅｑ＿ｈｅｉｇｈｔを求める。
【０１９６】
ｂ）最大頻度値を示す矩形高さｆｒｅｑ＿ｈｅｉｇｈｔが最小高さ値（具体的には、１００ｄｐｉで２３ｄｏｔ）より小さいときは、最小高さ値を最大頻度値を示す矩形高さｆｒｅｑ＿ｈｅｉｇｈｔとする。
【０１９７】
ｃ）大きな矩形と判定するしきい値ｔｈ＿ｌａｒｇｅをｔｈ＿ｌａｒｇｅ＝ｆｒｅｑ＿ｈｅｉｇｈｔ＊１０とする。
ｄ）グループ内の外接矩形で縦横サイズとも、ｔｈ＿ｌａｒｇｅより小さいものだけを残して、後はノイズとしてそのグループから削除する。
【０１９８】
次に、グループ内の重なり矩形統合処理を行う（ステップＳ２０）。このグループ内の重なり矩形統合処理では、グループ内にある外接矩形の中で、重なりがある外接矩形について、それらの外接矩形を囲む矩形を新たに作り、グループ情報に新たに登録する。
【０１９９】
すなわち、グループ内の外接矩形のうち、一部でも重なりがある外接矩形同士を統合して、それらを囲む外接矩形にする。
図３３は、本発明の一実施例に係わるグループ内の重なり矩形統合処理を説明する図である。
【０２００】
図３３（ａ）において、外接矩形２１１は外接矩形２１２と重なっており、外接矩形２１２は外接矩形２１３と部分的に重なっている。この場合、外接矩形２１１〜外接矩形２１３を統合し、外接矩形２１１〜外接矩形２１４を生成する。
【０２０１】
この処理により、例えば、「画」や「関」などのように、１つの文字が互いに分離した複数のパターンからなる場合に、これらの複数のパターンを一体的に取り扱うことができ、その後の処理を効率的に行うことが可能となる。
【０２０２】
次に、グループ内文字列抽出処理を行う（ステップＳ２１）。このグループ内の文字列抽出処理では、グループ内で文字列方向を推定し、その方向に対して、文字列を抽出する。抽出した文字列の方向、座標などの情報はグループごとに保存する。
【０２０３】
図３４は、本発明の一実施例に係わるグループ内文字列抽出処理を説明する図である。
図３４（ａ）において、矩形番号１〜２９の外接矩形がグループ２２１にグルーピングされているものとすると、最も左にある矩形番号１の外接矩形から、右方向に矩形番号１の外接矩形と隣接する外接矩形があるかどうかを探す。そして、矩形番号１の外接矩形と隣接する外接矩形として、矩形番号２の外接矩形が見つかると、見つかった外接矩形に矩形番号１を伝番し、見つかった外接矩形の矩形番号２を矩形番号１に変更する。同様にして、右方向に隣接する外接矩形があるかどうかを探し、隣接する外接矩形が見つかると、左に隣接する外接矩形の矩形番号を右の外接矩形に伝番する。
【０２０４】
矩形番号１の外接矩形から右方向に隣接する外接矩形がなくなると、矩形番号１５の外接矩形から、右方向に矩形番号１５の外接矩形と隣接する外接矩形があるかどうかを探す。矩形番号１５の外接矩形と隣接する外接矩形が見つかると、見つかった外接矩形に矩形番号１５を伝番する。
【０２０５】
以上の処理により、図３４（ｂ）に示すように、矩形番号１の外接矩形に右方向に隣接する外接矩形に矩形番号１が付され、矩形番号１５の外接矩形に右方向に隣接する外接矩形に矩形番号１５が付される。矩形番号の伝番処理が終了すると、同一の矩形番号１が付された外接矩形を囲む外接矩形２２２を生成し、同一の矩形番号１５が付された外接矩形を囲む外接矩形２２３を生成する。
【０２０６】
具体的には、以下のａ）〜ｅ）の処理を行う。
ａ）グループ内の外接矩形の座標から文字列方向を推定する。
ｂ）外接矩形の上下左右の最も近くにある矩形の内向き、外向きの両方向の隣接関係を求める。
【０２０７】
ｃ）横方向の文字列の場合、左からの隣接関係のない矩形を開始矩形として、右に矩形がなくなるまで、開始矩形番号を右にある矩形に伝搬していく。縦方向も同様である。
ｄ）左からの隣接関係がなく、左への隣接関係がある矩形は、左の矩形番号を獲得して、それを右へ伝搬し、隣接関係がなくなるまで繰り返す。
【０２０８】
ｅ）ここまでの処理をグループ内全ての矩形について行った後に、同じ矩形番号がついている矩形を求め、同じ矩形番号がついている矩形の外接矩形を文字列矩形として抽出する。
【０２０９】
次に、文字列内分離文字統合処理を行う（ステップＳ２２）。この文字列内分離文字統合処理では、横書きの上下分離文字統合処理（縦書きでは、左右分離文字統合処理）を文字列矩形に適応して、分離矩形を統合した外接矩形に置き換える。ここでは、抽出された文字列内の矩形に対して文字列方向と直角の方向に矩形統合を行う。これは横書きの文字列ならば、例えば「こ」という文字の上ストロークと下ストロークをそれぞれ囲む矩形をまとめて、１つの矩形とする処理である。
【０２１０】
図３５は、本発明の一実施例に係わる文字列内分離文字統合処理を説明する図である。
図３５（ａ）において、グループ２２１内で互いに横方向に隣接する外接矩形を囲む外接矩形２２２、２２３が生成され、外接矩形２２２内には、縦方向に互いに隣接する外接矩形２２４、２２５及び縦方向に互いに隣接する外接矩形２２６、２２７が存在し、外接矩形２２３内には、縦方向に互いに隣接する外接矩形２２８、２２９及び縦方向に互いに隣接する外接矩形２３０、２３１が存在しているものとする。
【０２１１】
この場合、図３５（ｂ）に示すように、外接矩形２２２、２２３を囲む外接矩形２３２を生成して、外接矩形２２２、２２３を統合し、外接矩形２２６、２２７を囲む外接矩形２３３を生成して、外接矩形２２６、２２７を統合し、外接矩形２２８、２２９を囲む外接矩形２３４を生成して、外接矩形２２８、２２９を統合し、外接矩形２３０、２３１を囲む外接矩形２３５を生成して、外接矩形２３０、２３１を統合する。
【０２１２】
具体的には、以下のａ）〜ｃ）の処理を行う。なお、以下の例では、横文字列の場合について説明するが、縦文字列の場合についても同様である。
ａ）文字列内矩形をｘ座標で昇順にソートする。
【０２１３】
ｂ）最初の矩形をカレント矩形として、次のそれ以降の矩形がカレント矩形のｘ座標の範囲に重なる場合は統合し、カレント矩形のｘ座標の範囲も統合結果のものとする。この処理を統合する矩形がなくなるまで繰り返す。統合する矩形がなくなったら、分離統合後の矩形として保存する。
【０２１４】
ｃ）統合する矩形が無くなったら、次の矩形を新たなカレント矩形として、ｂ）及びｃ）の処理を繰り返す。
次に、グループ内の文字列サイズによる再グループ化を行う（ステップＳ２３）。グループ内の文字列サイズによる再グループ化処理では、グループ内の文字列情報から文字列方向に直角のサイズに注目して、その大きさで再グループ化を行い、その結果を新たなグループ情報に格納する。
【０２１５】
このことにより、同色グループ内で、文字サイズが異なる文字列を別グループにすることができ、同時にノイズと文字列の別グループ化も可能となる。
図３６は、本発明の一実施例に係わるグループ内の文字列サイズによる再グループ化処理を説明する図である。
【０２１６】
図３６（ａ）において、グループ２２１内で互いに横方向に隣接する外接矩形を囲む外接矩形２２２、２２３が生成されているものとすると、外接矩形２２２の高さＨ１及び外接矩形２２３の高さＨ２を算出し、外接矩形２２２の高さＨ１と外接矩形２２３の高さＨ２の差がしきい値より大きい場合は、外接矩形２２２と外接矩形２２３とを別々のグループにする。
【０２１７】
具体的には、２つの文字列矩形の高さ（横書きの場合。縦書きなら幅）の違いがしきい値より小さく、かつ、２つの文字列矩形が重複もしくは、２つの文字列矩形間の距離がしきい値より小さい場合に、この２つの文字列矩形は、同じグループに属するものとして、同じグループ番号を与える。この処理を全てのグループで行う。
【０２１８】
次に、グループ内で同じグループ番号の文字列を１つのグループとする新たなグループを作成する。この処理は、図２１のステップＳ１８で同じグループになった文字サイズの異なる文字列を別グループにする働きがある。
【０２１９】
次に、グループ内の大きな矩形再削除処理を行う（ステップＳ２４）。このグループ内の大きな矩形再削除処理では、ノイズ除去のため、グループ内で平均的な矩形サイズを求め、その矩形サイズを基準として極端に大きなサイズの矩形を再び削除する。すなわち、これまでの処理で変化したグループに対して、図２１のステップＳ１９の処理を再度行い、グループ内のノイズを削除する。
【０２２０】
次に、グループ統合処理を行う（ステップＳ２５）。このグループ統合処理では、左右または上下の近くで同色のグループを統合する。すなわち、２つのグループがほぼ同じ色で、かつ近くにあり、グループの外接矩形が並んでいる場合に、その２つの外接矩形を統合し、１つのグループとする。これは、後で行う文字矩形の並びによるグループの文字列らしさの判定を安定化させるために行う。
【０２２１】
図３７は、本発明の一実施例に係わるグループ統合処理を説明する図である。
図３７（ａ）において、グループ１の外接矩形２４１とグループ２の外接矩形２４２が互いに横に並んでいるものとすると、外接矩形２４１と外接矩形２４２の距離Ｌ１、外接矩形２４１と外接矩形２４２の上端同士の座標の差Ｅ１及び外接矩形２４１と外接矩形２４２の下端同士の座標の差Ｅ２を求める。そして、外接矩形２４１と外接矩形２４２の距離Ｌ１、外接矩形２４１と外接矩形２４２の上端同士の座標の差Ｅ１及び外接矩形２４１と外接矩形２４２の下端同士の座標の差Ｅ２が各しきい値より小さく、グループ１の代表色とグループ２の代表色の差が所定のしきい値以内にある場合、外接矩形２４１と外接矩形２４２とを統合し、外接矩形２４１及び外接矩形２４２を囲む外接矩形２４３を生成する。
【０２２２】
具体的には、２つのグループの外接矩形において、座標が近く、かつ近い距離にあり、２つの外接矩形をまとめて１つの文字列と見れそうなものを１つのグループにまとめる。統合の条件は、以下の通りである。
【０２２３】
・２つのグループの平均ＲＧＢの各ＲＧＢの輝度差がある固定しきい値より小さい。
・横並びの場合、横方向の距離が固定しきい値より小さい（縦並びの場合は、縦方向の距離が固定しきい値より小さい）。
【０２２４】
・横並びの場合、２つのグループ外接矩形の上端同士の座標の差が固定しきい値より小さく、かつ、下端同士の座標の差が固定しきい値より小さい（縦並びの場合、２つのグループ外接矩形の右端同士の座標の差が固定しきい値より小さく、かつ、左端同士の座標の差が固定しきい値より小さい）。
【０２２５】
この処理を統合するグループが無くなるまで繰り返す。
次に、矩形並びによる文字らしいグループの抽出処理を行う（ステップＳ２６）。この矩形並びによる文字らしいグループの抽出処理では、グループ内の矩形の中で、サイズまたは形など一定の条件を満足する矩形を対象に、上下端座標のどちらかが隣りの矩形と近い場合、この両者の矩形が並んでいると判定し、並びフラグをセットする。その一定条件を満足するグループ内の対象矩形の中で、並んでいる矩形の数がどの程度の割合であるかを示す、並び矩形率を求め、その並び矩形率が一定のしきい値以上のグループを文字列と見なして抽出する。
【０２２６】
図３８は、本発明の一実施例に係わる矩形並びによる文字列らしいグループの抽出処理を説明する図である。
図３８（ａ）において、外接矩形２５２〜２５６及び外接矩形２５８〜２６９が入力画像から生成され、外接矩形のグルーピングにより、外接矩形２５２〜２５６が１つのグループとされた結果、これらの外接矩形２５２〜２５６を囲む外接矩形２５１が生成され、外接矩形２５８〜２６９が１つのグループとされた結果、これらの外接矩形２５８〜２６９を囲む外接矩形２５７が生成されているものとする。
【０２２７】
次に、各グループ内の外接矩形のサイズや位置関係を調べ、横方向に並んでいる外接矩形に対して横並びフラグ１を与え、縦方向に並んでいる外接矩形に対して縦並びフラグ２を与える。この結果、外接矩形２５１内の外接矩形２５２〜２５６はランダムに並んでいるので、外接矩形２５２〜２５６には、横並びフラグ１も縦並びフラグ２も付かない。一方、外接矩形２５７内の外接矩形２５８〜２６９は横一列に並んでいるので、外接矩形２５８〜２６９には、横並びフラグ１が与えられる。
【０２２８】
外接矩形２５２〜２５６及び外接矩形２５８〜２６９についてのフラグ処理が終了すると、各グループごとにフラグが付された矩形の割合を算出し、フラグが付された矩形の割合の多いグループを文字列として抽出し、フラグが付された矩形の割合の少ないグループをノイズとして捨てる。
【０２２９】
この結果、図３８（ｂ）に示すように、外接矩形２５２〜２５６からなるグループは、外接矩形２５２〜２５６に対して、フラグが１つも付されてないので、ノイズとして捨てられ、外接矩形２５８〜２６９からなるグループは、外接矩形２５８〜２６９に対して、横並びフラグ１を与えられているので、文字列として抽出される。
【０２３０】
具体的には、以下のａ）〜ｅ）の処理を行う。
ａ）グループ内の隣接するサイズまたは形の一定条件を満足する２つの矩形の上端座標同士または下端座標同士の差がしきい値（高さのＷＩＤ＿ＲＡＴＥ（＝０．２）倍）より小さい場合、その２つの矩形に横並びフラグを与える。
【０２３１】
ここで、隣接するとは、基準矩形の幅のＷＩＤ＿ＲＡＴＥ＿ＤＩＳＴ（＝０．５）倍の周囲範囲以内に矩形があることをいう。
ｂ）グループ内の隣接するサイズまたは形の一定条件を満足する２つの矩形の左端座標同士または右端座標同士の差がしきい値（幅のＷＩＤ＿ＲＡＴＥ倍）より小さい場合、その２つの矩形に縦並びフラグを与える。
【０２３２】
ここで、隣接するとは、基準矩形の高さのＷＩＤ＿ＲＡＴＥ＿ＤＩＳＴ倍の周囲範囲以内に矩形があることをいう。
ｃ）グループ内の矩形で、横並びフラグと縦並びフラグの数の多いほうを文字列方向として採用して、その数を並んでいる矩形数とする。
【０２３３】
ｄ）グループ内の矩形の中で並んでいる矩形の比率を、「並んでいる矩形数／グループ内のサイズまたは形の一定条件を満足する矩形の総数」を算出することにより求める。
なお、対象とするグループ内矩形の条件は、グループ内の矩形の最頻値を示す高さを図３２に示した手法で求め、その３倍をｌａｒｇｅ＿ｒｅｃｔとして、矩形高さが、固定サイズ（２３ｄｏｔ，１００ｄｐｉで）より大きく、ｌａｒｇｅ＿ｒｅｃｔより小さいものとする。
【０２３４】
ｅ）並んでいる矩形の比率が一定しきい値ＮＵＭ＿ＲＡＴＥ（＝０．８）より大きい場合に、そのグループを文字列らしいグループとして残し、他をノイズとして捨てる。
なお、「・」の中点や「ー」の中棒は、文字として残すようにする。
【０２３５】
次に、ノイズグループの削除処理を行う（ステップＳ２７）。このノイズグループの削除処理では、グループ内が２つの矩形だけから構成されているグループに対して、その形状、座標からノイズと思われるグループを抽出して、そのグループを削除する。すなわち、グループ内の矩形数が２つのものについて、その２つの矩形が上下（または左右）端とも近いもので、２つの矩形が並んでいると判断される以外のグループをノイズとして削除する。
【０２３６】
図３９は、本発明の一実施例に係わるノイズグループの削除処理を説明する図である。
図３９において、２つの外接矩形２７２、２７３が１つのグループとして抽出され、この２つの外接矩形２７２、２７３を囲む外接矩形２７１が生成されているものとする。この場合、外接矩形２７２と外接矩形２７３の下端座標は揃っているが、外接矩形２７２と外接矩形２７３の上端座標は極端に異なっているので、これらの外接矩形２７２、２７３はノイズであると見なして、外接矩形２７２、２７３からなるグループを文字列らしいグループから削除する。
【０２３７】
具体的には、以下の処理を行う。
グループ内の２つの矩形の高さの平均をｈｅｉ，幅の平均をｗｉｄとする。しきい値を決める比率ＤＥＬ＿ＲＡＴＥ＝０．１として、
（｜第１の矩形の上端座標−第２の矩形の上端座標｜＜ｈｅｉ×ＤＥＬ＿ＲＡＴＥ
かつ
｜第１の矩形の下端座標−第２の矩形の下端座標｜＜ｈｅｉ×ＤＥＬ＿ＲＡＴＥ）
または
（｜第１の矩形の左端座標−第２の矩形の左端座標｜＜ｗｉｄ×ＤＥＬ＿ＲＡＴＥ
かつ｜第１の矩形の右端座標−第２の矩形の右端座標｜＜ｗｉｄ×ＤＥＬ＿ＲＡＴＥ）
を満足するグループだけ残し、後はノイズとして削除する。
【０２３８】
次に、グループ内同色パターン抽出処理を行う（ステップＳ２８）。このグループ内同色パターンの抽出では、グループの代表色をグループ内部の矩形の代表色の平均として求める。グループの内部に相当する範囲で、原画像を探索して、その色に近いパターンで、すでに文字パターンとして抽出されているもの以外ものを２値画像として抽出する。抽出したパターンに２値画像用のラベリングをかけて、連結成分の外接矩形を求め、それの大きさが一定しきい値より大きい物だけを文字パターンの一部として、グループに追加する。
【０２３９】
例えば、グループ内のパターンの平均色（ＲＧＢ）を求め、その色に近い画素をグループの外接矩形の範囲内で求め、２値画像を作成する。その中からパターン部分を除去して、残った２値画像に２値画像のラベリング処理を施し、新たな外接矩形を求める。そして、新たな外接矩形の大きさ及び形が一定のしきい値以上である場合に、新たな外接矩形内のパターンをグループに追加する。
【０２４０】
この処理により、これまでの処理で抜け落ちるが、実は文字の一部であるパターン、例えば、「ば」の濁点部分のように、文字幅情報や色ずれなどで落されたパターンを再抽出することができる。
【０２４１】
図４０は、本発明の一実施例に係わるグループ内同色パターン抽出処理を説明する図である。
図４０（ａ）において、図２１のステップＳ１１〜Ｓ２７の処理により、「クローハル化への３つの成功モデル」という文字列が入力画像から抽出され、これらの文字列を囲む外接矩形２８０が生成されているものとする。この場合、「ク」という文字の濁点及び「ハ」という文字の濁点が欠落している。
【０２４２】
ここで、「ク」という文字の濁点が欠落したのは、「ク」という文字の濁点の色と「ク」という文字の色の差がしきい値範囲内にないために、「ク」という文字の濁点が「ク」という文字と異なるグループにグルーピングされたためである。
【０２４３】
また、「ハ」という文字の濁点が欠落したのは、「ハ」という文字の濁点の色と「ハ」という文字の色の差がしきい値範囲内にないために、「ハ」という文字の濁点が「ハ」という文字と異なるグループにグルーピングされたためである。
【０２４４】
このように、ステップＳ１６の同色グループ抽出処理では、抽出対象となる文字列のうち、局所的な部分の色同士が比較されるので、抽出対象となる文字列の色が色ずれなどで局所的に変化している場合には、文字の一部が欠落したりする。
【０２４５】
そこで、「ク」という文字の濁点及び「ハ」という文字の濁点の再抽出を行う。ここで、再抽出を行う際には、既に抽出されている「クローハル化への３つの成功モデル」という文字列全体を考慮して、その代表色を求め、この代表色に近い色を有するパターンをラベル画像から抽出する。既に抽出されている文字列全体を考慮して代表色を求めることにより、その文字列の局所的な色の変化の影響が軽減され、「ク」という文字の濁点及び「ハ」という文字の濁点を抽出することが可能となる。また、再抽出を行う際には、再抽出の対象となるパターンが存在する範囲を、外接矩形２８０の範囲に限定する。この範囲の限定を行うことにより、再抽出となる文字の濁点がその範囲からはみ出ないようにして、処理対象となるパターンの範囲を狭くすることが可能となり、抽出精度を損なうことなく、処理を高速化することが可能となる。
【０２４６】
この結果、図４０（ｂ）に示すように、「ク」という文字の濁点と「ハ」という文字の濁とが正しく抽出され、「グローバル化への３つの成功モデル」という文字列を入力画像から抽出することができる。
【０２４７】
なお、この再抽出の結果、「グローバル化への３つの成功モデル」という文字列と同色のノイズが外接矩形２８０の範囲内にある場合、このノイズも一緒に抽出されるので、再抽出されたパターンのうち微小なものは、ノイズとみなして除去するようにする。
【０２４８】
具体的には、以下のａ）〜ｈ）の処理を行う。
ａ）グループ内の矩形情報に保存されている代表色情報をグループ内の矩形全てについて平均して、グループの代表色（Ｒｍ，Ｇｍ，Ｂｍ）を求める。
【０２４９】
ｂ）グループ内の矩形サイズの最頻値を幅と高さについて求め、それらをｍｆｗ，ｍｆｈとする。最頻値の幅ｍｆｗと高さｍｆｈが、最小矩形サイズのしきい値ｍｉｎｓｉｚｅ（＝２）より大きな場合には、最頻値の幅ｍｆｗと高さｍｆｈをそれぞれｍｉｎｓｉｚｅで置き換える。
【０２５０】
ｃ）グループの外接矩形を求め、その外接矩形の範囲で２値画像を作成する。２値画像は、全て０としておく。
ｄ）グループの外接矩形の範囲内で原画像の画素の色をチェックして、原画像の画素の色（Ｒ，Ｇ，Ｂ）とグループの代表色が、
｜Ｒｍ−Ｒ｜＋｜Ｇｍ−Ｇ｜＋｜Ｂｍ−Ｂ｜＜ＴＨＲ×１０ （ＴＨＲ＝１０）
を満足する画素の位置を記録し、２値画像の同じ位置の画素を１にする。
【０２５１】
ｅ）２値画像の中から、グループ内の矩形を構成する。既に抽出されているパターンを除去して、２値画像をグループの代表色に近い色であり、かつこれまでの処理で漏れていたパターンだけにする。
【０２５２】
ｆ）２値画像に対して、２値画像用のラベリングを行い、連結領域の外接矩形を求める。
ｇ）外接矩形の幅ｗ及び高さｈが、
ｗ＜ｍｆｗ／２、かつ、ｈ＜ｍｆｈ／２
を満足する矩形だけを残し、他を削除する。
【０２５３】
ｈ）残った矩形を構成する連結矩形のパターンをグループに追加する。
次に、グループの出力順位決定処理を行う（ステップＳ２９）。このグループの出力順位決定処理では、文字列を含んでいるグループが複数抽出された場合、グループの外接矩形から面積を計算して、全画像中のグループの面積の大きい順にグループをソートして、このソートした結果を出力順序とする。
【０２５４】
次に、２値パターン生成処理を行う（ステップＳ３０）。この２値パターン生成処理では、グループを構成するパターンを文字認識できるような２値画像として作成する。
具体的には、以下のａ）〜ｃ）の処理を行う。
【０２５５】
ａ）グループの外接矩形サイズの２値画像を作成し、それを全て０に設定する。
ｂ）グループ内の矩形のラベル番号を抽出し、対応する矩形領域の内部でラベル画像を探索し、そのラベル番号の画素を抽出し、２値画像上でその座標の画素を１とする。
【０２５６】
ｃ）ｂ）の処理を全ての矩形について行い、グループを構成するパターンを２値画像上に作成する。以下、以上の処理を実際のカラー画像を例にとって説明する。
図４１（ａ）は、入力された原画像の例を示す図であり、この原画像は、見出し文字３０１、３０２、絵柄３０３、本文文字３０４、枠３０５などがカラーで印刷されている。そして、この原画像から見出し文字３０１、３０２をタイトルとして抽出するものとする。なお、見出し文字３０１、３０２は、それぞれ一色で印刷されているものとする。
【０２５７】
図４１（ｂ）は、図４１（ａ）のラベル画像を示す図である。
図４１（ｂ）において、このラベル画像は、図２１のステップＳ１３の色ラベリング処理により得られたものである。この色ラベリング処理により、同色の連結領域に対して同一ラベルが付され、同一ラベルが付されたパターンの外接矩形が生成される。この時、外接矩形の個数は数千〜数万程度になる。
【０２５８】
図４１（ｃ）は、図４１（ｂ）のラベル画像から得られた注目矩形を示す図である。
図４１（ｃ）において、この注目矩形は、図２１のステップＳ１４の注目矩形抽出処理により得られたものであり、図４１（ｃ）の例では、矩形番号１〜６４の注目矩形が抽出されている。
【０２５９】
なお、ステップＳ１４の注目矩形抽出処理では、ラベル画像から得られる外接矩形のうち、所定の範囲内の大きさの外接矩形が注目矩形とされるので、図４１（ｃ）の領域３１１、３１２に本来抽出されていなければならない見出し文字３０１、３０２の外接矩形が落ちている。これは、例えば、図４１（ｃ）の領域３１２に本来抽出されていなければならない見出し文字３０２は、図４１（ａ）の「に」の文字に対応する外接矩形であるが、図４１（ｂ）のラベル画像では、「に」を構成する３つのストロークに異なるラベルが付されるので、各ストロークの外接矩形の大きさが小さくなったためである。
【０２６０】
この注目矩形抽出処理により、本文文字３０４に対応する不図示の外接矩形３１３やノイズの外接矩形や枠３０５の外接矩形などを、グルーピングの際の探索範囲の基準となる外接矩形から除去することができ、処理を高速化することが可能となる。例えば、図４１（ｂ）の状態では、外接矩形の個数が数千〜数万程度あったものが、図４１（ｃ）の状態では、外接矩形の個数が数十個に減っている。
【０２６１】
図４１（ｄ）は、グループ抽出結果を示す図である。
図４１（ｄ）において、このグループ抽出結果は、図２１のステップＳ１６の同色グループ抽出処理により得られたものであり、矩形番号が１〜２１のグループの外接矩形が生成されている。この処理により、図４１（ｂ）のラベル画像から得られた外接矩形のうち、図４１（ｃ）で設定された注目矩形から所定の範囲内にあり、代表色の色が近いものは、同一のグループにグルーピングされ、同一のグループにグルーピングされた外接矩形を囲む外接矩形が生成される。
【０２６２】
この結果、図４１（ａ）の「日経４００社経営者アンケート」という見出し文字３０１に対応したグループの外接矩形３２１が生成され、図４１（ａ）の「貿易不均衡の要因に微妙な差」という見出し文字３０２に対応したグループの外接矩形３２２が生成される。このグルーピングにより、見出し文字３０１、３０２を構成する文字列をそれぞれ１つにまとめることができる。また、図４１（ｃ）の領域３１１、３１２に本来抽出されていなければならない見出し文字３０１、３０２の外接矩形３２３、３２４も正しく抽出することが可能となる。
【０２６３】
なお、図４１（ｃ）の注目矩形から所定の範囲内に、代表色の色が近い他の外接矩形が図４１（ｂ）のラベル画像から見つからない場合は、その注目矩形はグループを作らないため、その注目矩形は消滅する。
【０２６４】
図４２（ａ）は、図４１（ｄ）のグループ抽出結果を文字線太さで再グループ化した結果を示す図である。図４２（ａ）において、この再グループは、図２１のステップＳ１８の文字線太さによる再グループ化処理により得られたものであり、矩形番号が０〜１２のグループの外接矩形が生成されている。この処理により、図４１（ａ）の「日経４００社経営者アンケート」という見出し文字３０１に対応したグループの外接矩形３３１が生成され、図４１（ａ）の「貿易不均衡の要因に微妙な差」という見出し文字３０２に対応したグループの外接矩形３３２が生成される。
【０２６５】
なお、図４１（ｄ）の外接矩形のうち、パターンの線の太さによってグループを作ることができないものは消滅する。
図４２（ｂ）は、図４２（ａ）の矩形の重なり統合後の結果を示す図である。
【０２６６】
図４２（ｂ）において、この矩形の重なり統合後の結果は、図２１のステップＳ２０のグループ内重なり矩形統合処理により得られたものであり、矩形番号が０〜１２のグループの外接矩形が生成されている。この処理では、図４１（ａ）の絵柄３０３に対応する領域３３３の外接矩形は互いに重なっているものが多く、それらの外接矩形は統合されて消滅している。この統合処理により、これ以降の処理の対象となる外接矩形の数が減るので、処理を高速化できる。
【０２６７】
図４２（ｃ）は、図４２（ｂ）の画像から矩形家並びによる文字列らしいグループを抽出した結果を示す図である。
図４２（ｃ）において、この文字列らしいグループは、図２１のステップＳ２６の矩形並びによる文字列らしいグループの抽出処理により得られたものであり、矩形番号が０、１のグループの外接矩形が抽出されている。この処理により、図４２（ｂ）の領域３４２のグループの外接矩形はランダムに並んでいるので、削除され、図４２（ｂ）の領域３４１のグループの外接矩形のみが抽出される。
【０２６８】
図４２（ｄ）は図４２（ｃ）の画像からグループ内パターンを抽出した結果を示す図である。
図４２（ｄ）において、このグループ内パターンは、図２１のステップＳ２８のグループ内同色パターン抽出処理により得られたものであり、図４２（ｃ）で得られたグループの外接矩形の領域内のパターンが抽出され、図４１（ａ）の「日経４００社経営者アンケート」という見出し文字３０１及び「貿易不均衡の要因に微妙な差」という見出し文字３０２が得られる。
【０２６９】
図４３（ａ）は、図４１（ａ）の画像から抽出されたタイトルの第１候補のパターンを示す図、図４３（ｂ）は、図４１（ａ）の画像から抽出されたタイトルの第２候補のパターンを示す図である。
【０２７０】
図４３の例では、抽出されたパターンの外接矩形４０１、４０２の面積により、図４１（ａ）の原画像から抽出されたタイトルの出力順位を決定している。この結果、図４１（ａ）の「貿易不均衡の要因に微妙な差」という見出し文字３０２がタイトルの第２候補として提示され、図４１（ａ）の「日経４００社経営者アンケート」という見出し文字３０１がタイトルの第２候補として提示される。
【図面の簡単な説明】
【０２７１】
【図１】本発明の第１実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図２】本発明の第２実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図３】本発明の第３実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図４】本発明の第４実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図５】本発明の一実施例に係わるパターン抽出装置のシステム構成を示すブロック図である。
【図６】本発明の第５実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図７】本発明の第６実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図８】図７のパターン抽出装置の動作を示すフローチャートである。
【図９】本発明の一実施例に係わる縮小画像作成方法を説明する図である。
【図１０】本発明の一実施例に係わるラベリング方法を説明する図である。
【図１１】本発明の一実施例に係わるしきい値参照テーブルの構成を示す図である。
【図１２】本発明の一実施例に係わるしきい値参照テーブルの別の構成を示す図である。
【図１３】本発明の一実施例に係わる外接矩形処理及び原画像ラベリング処理を説明する図である。
【図１４】網点印刷法によるカラー画像の表現方法を説明する図である。
【図１５】網点印刷法によるカラー画像の拡大図である。
【図１６】（ａ）は網点印刷法で均一色で印刷された領域を示す図、（ｂ）は図１６（ａ）の領域に読み取りメッシュを設定した結果を示す図、（ｃ）は各画素ごとの読み取り結果を示す図である。
【図１７】本発明の一実施例に係わる印刷モデルの生成方法を示す図である。
【図１８】本発明の一実施例に係わる色差テーブルの構成を示す図である。
【図１９】本発明の一実施例に係わる色差テーブル生成装置の構成を示すブロック図である。
【図２０】本発明の第７実施例に係わるパターン抽出装置の構成を示すブロック図である。
【図２１】図７のパターン抽出装置の動作を示すフローチャートである。
【図２２】本発明の一実施例に係わるモデル解像度推定処理を説明する図である。
【図２３】本発明の一実施例に係わる色ラベリング処理を説明する図である。
【図２４】本発明の一実施例に係わる注目矩形の周囲の探索範囲の設定方法を説明する図である。
【図２５】本発明の一実施例に係わる注目矩形の周囲の探索範囲にかかる矩形の抽出方法を説明する図である。
【図２６】本発明の一実施例に係わる注目矩形の周囲の探索範囲にかかる矩形情報の格納方法を説明する図である。
【図２７】本発明の一実施例に係わる文字線の太さの算出方法を説明する図である。
【図２８】本発明の一実施例に係わる文字線の太さによる再グルーピング処理を説明する図である。
【図２９】本発明の一実施例に係わる輪郭追跡における画素の探索開始点の設定方法を説明する図である。
【図３０】本発明の一実施例に係わるカレント画素からみた方向コードを示す図である。
【図３１】本発明の一実施例に係わるグループ内の大きな矩形削除処理を説明する図である。
【図３２】本発明の一実施例に係わる矩形高さの最大頻度値の算出方法を説明する図である。
【図３３】本発明の一実施例に係わるグループ内の重なり矩形統合処理を説明する図である。
【図３４】本発明の一実施例に係わるグループ内文字列抽出処理を説明する図である。
【図３５】本発明の一実施例に係わる文字列内分離文字統合処理を説明する図である。
【図３６】本発明の一実施例に係わるグループ内の文字列サイズによる再グループ化処理を説明する図である。
【図３７】本発明の一実施例に係わるグループ統合処理を説明する図である。
【図３８】本発明の一実施例に係わる矩形家並びによる文字列らしいグループの抽出処理を説明する図である。
【図３９】本発明の一実施例に係わるノイズグループの削除処理を説明する図である。
【図４０】本発明の一実施例に係わるグループ内同色パターン抽出処理を説明する図である。
【図４１】（ａ）は、本発明の一実施例に係わる原画像を示す図、（ｂ）は、図４１（ａ）のラベル画像を示す図、（ｃ）は、図４１（ｂ）のラベル画像に設定された注目矩形を示す図、（ｄ）はグループ抽出結果を示す図である。
【図４２】（ａ）は、図４１（ｄ）のグループ抽出結果を文字線太さで再グループ化した結果を示す図、（ｂ）は、図４２（ａ）の矩形の重なり統合後の結果を示す図、（ｃ）は、図４２（ｂ）の画像から矩形家並びによる文字列らしいグループを抽出した結果を示す図、（ｄ）は図４２（ｃ）の画像からグループ内パターンを抽出した結果を示す図である。
【図４３】（ａ）は、図４１（ａ）の画像から抽出されたタイトルの第１候補のパターンを示す図、（ｂ）は、図４１（ａ）の画像から抽出されたタイトルの第２候補のパターンを示す図である。
【図４４】従来の色分解画像の生成方法を示す図である。
【図４５】従来の領域拡張法を示す図である。
【符号の説明】
【０２７２】
１ 色情報算出手段
２ 幾何学情報算出手段
３ 分類手段
１１ クラスタリング手段
１２ グルーピング手段
２１ 色差算出手段
２２ しきい値設定手段
２３、３３、６７、７７ ラベリング手段
３１ 第１の色情報比較手段
３２ 第２の色情報比較手段
４１、６４、７４、１１４、１３４ ＣＰＵ
４２ ＲＯＭ
４３ ＲＡＭ
４４ 通信インターフェイス
４５ 通信ネットワーク
４６ バス
４７ 入出力インターフェイス
４８ ディスプレイ
４９ プリンタ
５０、６３、７３、１１３、１３３ メモリ
５１ スキャナ
５２ キーボード
５３ ドライバ
５４ ハードディスク
５５ ＩＣメモリカード
５６ 磁気テープ
５７ フレキシブルディスク
５８ 光ディスク
６１、７１、１１１、１３１ カラー画像入力装置
６２、７２、１１２、１３２ 外部出力装置
６５、７５ 画像縮小手段
６６、７６ 可変しきい値設定手段
７８ 外接矩形処理手段
７９ 原画像ラベリング手段
８０ 特定領域抽出手段
１１５ 印刷モデル生成部
１１６ 色差テーブル生成部
１３５ 色差テーブル
１３６ 色分解画像生成部
１３７ 文字領域抽出部
【図１】
2005302056.tif 000003
【図２】
2005302056.tif 000004
【図３】
2005302056.tif 000005
【図４】
2005302056.tif 000006
【図５】
2005302056.tif 000007
【図６】
2005302056.tif 000008
【図７】
2005302056.tif 000009
【図８】
2005302056.tif 000010
【図９】
2005302056.tif 000011
【図１０】
2005302056.tif 000012
【図１１】
2005302056.tif 000013
【図１２】
2005302056.tif 000014
【図１３】
2005302056.tif 000015
【図１４】
2005302056.tif 000016
【図１５】
2005302056.tif 000017
【図１６】
2005302056.tif 000018
【図１７】
2005302056.tif 000019
【図１８】
2005302056.tif 000020
【図１９】
2005302056.tif 000021
【図２０】
2005302056.tif 000022
【図２１】
2005302056.tif 000023
【図２２】
2005302056.tif 000024
【図２３】
2005302056.tif 000025
【図２４】
2005302056.tif 000026
【図２５】
2005302056.tif 000027
【図２６】
2005302056.tif 000028
【図２７】
2005302056.tif 000029
【図２８】
2005302056.tif 000030
【図２９】
2005302056.tif 000031
【図３０】
2005302056.tif 000032
【図３１】
2005302056.tif 000033
【図３２】
2005302056.tif 000034
【図３３】
2005302056.tif 000035
【図３４】
2005302056.tif 000036
【図３５】
2005302056.tif 000037
【図３６】
2005302056.tif 000038
【図３７】
2005302056.tif 000039
【図３８】
2005302056.tif 000040
【図３９】
2005302056.tif 000041
【図４０】
2005302056.tif 000042
【図４１】
2005302056.tif 000043
【図４２】
2005302056.tif 000044
【図４３】
2005302056.tif 000045
【図４４】
2005302056.tif 000046
【図４５】
2005302056.tif 000047