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