JP2004030696A - 文字列抽出装置及びパターン抽出装置 - Google Patents

Abstract

【課題】　複雑な画像から文字列を抽出することを可能とし、文字色を見誤ることがなく、かつ線幅が細い線分を見落とすことがない文字列抽出装置を提供する。
【解決手段】　入力画像の連結成分を求め、連結成分の相対的位置及び太さの類似性に基づいてグループに分け、文字認識処理を行ってグループの文字認識度を求め、矩形領域の面積によって重み付けしたものの総和をグループの評価値とし、全てのグループの組み合わせについて評価値を求め、組み合わせの評価値が最も高いグループの組み合わせを文字列として抽出する。
【選択図】　　図２

Description

　本発明は文書や図面などを読み取る画像認識技術に関わり、特に、画像から見出しなどの文字列を抽出する場合に適用して好適なものである。

　文書を電子的にファイリングする場合、キーワードを文書に付与しておくことが不可欠であるが、この作業は作業者にとって極めて煩わしいものであり、この作業を自動化することは、電子ファイリングの有用性を高める上で極めて重要な課題である。

　新聞や雑誌においては、見出し部分を自動的に抽出し、文字認識してキーワードとするのが最も効率的である。なぜなら、見出しは文書の内容の特徴を豊富に含み、かつ文書の中で特定し易いからである。

　このため、キーワードを抽出する時間を短縮し、キーワードを的確に抽出する技術（例えば特開平４−２８７１６８号　ファイリングの自動キーワード抽出方法）が考案されている。

　この方法は、図や写真や表の説明文が、図や写真や表の矩形部分の上部あるいは下部にあることに着目して、そこにある文字列あるいは文字列領域を抽出し、文字認識を行い、キーワードとして登録するというものである。

　また、画像から文字列を抽出する技術（例えば、特開平８−２９３００３号　文字列抽出方法およびその方法を用いた文字列抽出装置、及びその装置を用いた文字列認識処理装置ならびに文字列認識処理システム）が考案されている。

　ここでは、画像内の全ての文字を抽出し、連続性を有する文字列毎にグループ分けし、各グループの特徴量と登録された文字列の特徴量のモデルと比較・判別し、文字列として抽出するものである。ここで、連続性とは文字列の並びのことであり、特徴量とは漢字や数字などの文字の種類と大きさのことである。

　このように、電子ファイリングの対象となる文書や図面が様々であり、画像認識技術も多様であるが、画像から抽出する文字列の例として、新聞でよく見られる背景模様のある見出しを対象とする次に示す方法が一般的によく知られている。

　まず、入力画像を縦書きか、横書きかを判定し、入力画像とその反転画像にラベリング処理を行い、同じ色の画素が連なる連結成分を求める。
　次に、各連結成分の大きさ、太さ、及び相対的位置から文字候補を見つけ出す。

　ここで、入力画像の連結成分から得られる文字候補を黒文字候補、反転画像の連結成分から得られる文字候補を白文字候補と呼ぶ。この黒文字候補と白文字候補の個数から文字の色を決定し、文字色を黒とした場合は入力画像の連結成分のみをそれ以降の処理対象とし、文字色を白とした場合は反転画像の連結成分のみをそれ以降の処理対象にする。

　次に、処理対象の連結成分をマージして文字列領域を求め、この文字列領域に含まれる連結成分で、しきい値以上の太さの連結成分を文字成分として抽出する。このしきい値は、連結成分の太さの最大値に対する一定の割合の値である。最後に、文字成分として抽出した連結成分を画像として生成し、文字認識処理によって文字列とする。

　また、見出し部分を正確に抽出するため、同一文字列に属する黒画素領域の正確な統合技術が必要となる。
　この技術に関する従来方法としては、次の方法がある。

　まず、傾き補正や枠線除去などの前処理をしてから、画像全体をラベリングし、得られた黒画素連結領域の重なりネスト統合を行う。次に、得られた黒画素連結領域から文書全体の本文文字サイズを判断し、その値をもとに各連結領域の属性判別を行う。そして、属性が文字と判断された矩形に対しては、縦または横の統合を繰り返し、文字列を確定する。
特開平４−２８７１６８号公報「ファイリングの自動キーワード抽出方法」 特開平８−２９３００３号公報「文字列抽出方法およびその方法を用いた文字列抽出装置、及びその装置を用いた文字列認識処理装置ならびに文字列認識処理システム」

　しかしながら、従来の技術では、文字抽出処理の途中の段階で文字色を決定し、一律の標準文字線幅を用いており、また、文字列領域を設定するときは１行（あるいは１列）を前提にしていた。そのため、背景模様の白黒混在、複数種類のフォント混在、カラー文書、複数行、縦横混在、およびそれらの複合体で構成される複雑な画像から文字列を抽出することが困難になるという問題があった。

　また、黒文字候補と白文字候補の個数の関係は、文字色を決定するための判断基準として信頼性が高いとは言えず、また、文字抽出処理の途中の段階で文字色を決定しているが、ここで判断を誤ると、それ以降は修復不可能であり、最後に処理する文字認識が不可能になってしまうという問題があった。

　さらに、一律の標準文字線幅を用いることは比較的線幅の細い文字成分が消失しやすい傾向にあることを意味し、最後に処理する文字認識に影響を及ぼしてしまうという問題があった。

　また、従来手法では、黒画素連結領域の重なりネスト統合を行うために、本来統合されるべきでないところが次々と統合され、結局文書全体が統合されるという深刻な失敗に陥る可能性があった。

　例えば、文書全体の傾きが補正されない場合、また枠線が完全に除去されない場合、重なりネスト統合により、文書全体が統合されることがある。
　図３０は、従来の重なりネスト統合により、文書全体が統合される例を示す図である。

　図３０（ａ）において、連結成分の外接矩形Ｋ６１〜Ｋ６５が入力画像から得られたものとする。この連結成分の外接矩形Ｋ６１〜Ｋ６５に対して、重なりネスト統合を行うと、外接矩形Ｋ６１と外接矩形Ｋ６２とが重なっているため、外接矩形Ｋ６１と外接矩形Ｋ６２とは統合され、図３０（ｂ）に示すように、外接矩形Ｋ６１と外接矩形Ｋ６２とを囲む外接矩形Ｋ６６が生成される。外接矩形Ｋ６６が生成されると、この外接矩形Ｋ６６と外接矩形Ｋ６３とが重なるため、外接矩形Ｋ６６と外接矩形Ｋ６３とが統合され、図３０（ｃ）に示すように、外接矩形Ｋ６６と外接矩形Ｋ６３とを囲む外接矩形Ｋ６７が生成される。外接矩形Ｋ６７が生成されると、この外接矩形Ｋ６７と外接矩形Ｋ６４とが重なるため、外接矩形Ｋ６７と外接矩形Ｋ６４とが統合される。同様にして、図３０（ａ）の外接矩形Ｋ６１〜Ｋ６５の全てが統合され、図３０（ｄ）に示すように、外接矩形Ｋ６１〜Ｋ６５を囲む外接矩形Ｋ６８が生成される。

　また、写真や図、テクスチャ付きの見出しがある場合には、重なりネスト統合処理の時間がかかり過ぎるという問題もある。
。

　そこで、本発明の第１の目的は、文書や図面などを読み取る画像認識技術に関わり、特に、複雑な画像から文字列を抽出することを可能とし、文字色を見誤ることがなく、かつ線幅が細い線分を見落とすことがない文字列抽出装置を提供することである。

　また、本発明の第２の目的は、部分的に重なりネスト統合を行うことが可能なパターン抽出装置を提供することである。

　本発明の文字列抽出装置は、画像から文字列を抽出する装置であって、入力した画像から画素の色に基づいて、画素の色が連なる連結成分を抽出する連結成分抽出手段と、連結成分の相対的位置、および、連結成分の全画素数に対する境界画素数の比に基づいて、連結成分を共通の文字列または文字列群を構成する可能性が高いグループに分けるグルーピング手段と、グループ毎に文字認識処理を行い、その結果の各文字の第１位認識候補の距離値の逆数の和をグループの文字認識度とする文字認識手段と、グループの文字認識度にグループが占める矩形領域の面積によって重み付けしたものをグループの評価値とし、全てのグループの組合せについてグループの評価値の和を組合せの評価値とする組合せ評価手段と、組合せの評価値が最も高いグループの組合せを文字列として抽出する文字列抽出手段と、を備えることを特徴とする。

　また、本発明の文字列抽出装置は、入力した画像が白黒２値画像の場合には、入力画像と、白黒２値を反転させた反転画像とについて、黒画素が連なる連結成分を抽出することを特徴とする。

　更に、本発明の文字列抽出装置は、グループが占める矩形領域に重なりがないグループのみを関連付け、グループが占める矩形領域に重なりがないグループの組合せを全て求めることを特徴とする。

　更にまた、本発明の記録媒体は、プログラムを記録したコンピュータ読み取り可能な記録媒体であって、コンピュータを、入力した画像から画素の色に基づいて、画素の色が連なる連結成分を抽出する連結成分抽出手段と、連結成分の相対的位置、および、連結成分の全画素数に対する境界画素数の比に基づいて、連結成分を共通の文字列または文字列群を構成する可能性が高いグループに分けるグルーピング手段と、グループ毎に文字認識処理を行い、その結果の各文字の第１位認識候補の距離値の逆数の和をグループの文字認識度とする文字認識手段と、グループの文字認識度にグループが占める矩形領域の面積によって重み付けしたものをグループの評価値とし、全てのグループの組合せについてグループの評価値の和を組合せの評価値とする組合せ評価手段と、組合せの評価値が最も高いグループの組合せを文字列として抽出する文字列抽出手段と、を備え、画像から文字列を抽出する文字列抽出装置として機能させることを特徴とする。

　また、本発明の一態様によれば、入力画像及び前記入力画像の白黒反転画像のそれぞれから得られるパターンの認識結果のうち、互いに領域が重複しない部分を組み合わせたものを、前記入力画像からのパターンの抽出結果とするようにしている。

　このことにより、新聞などの見出し文字の中に、黒画素で構成された文字と白抜き文字とが混在している場合においても、黒文字候補と白文字候補の個数から文字の色が決定されたために、文字色が黒とされた場合は入力画像の連結成分のみがそれ以降の処理対象とされ、黒文字は正確に認識できるが、白抜き文字は認識不能となったり、文字色が白とされた場合は白黒反転画像の連結成分のみが文字認識の処理対象とされ、白抜き文字は正確に認識できるが、黒文字は認識不能となったりすることを防止することが可能となり、背景模様の白黒混在、複数種類のフォント混在、カラー文書、複数行、縦横混在、及びそれらの複合体で構成される複雑な画像から文字列を精度よく抽出することが可能となる。

　また、本発明の一態様によれば、入力画像の連結成分を抽出する連結成分抽出手段と、前記連結成分の外接矩形を生成する外接矩形生成手段と、前記外接矩形が前記入力画像に存在する頻度を前記外接矩形の面積で重み付けたヒストグラムを生成するヒストグラム生成手段と、前記ヒストグラムの最大値を示す外接矩形の大きさを前記入力画像の文字サイズと推定する文字サイズ推定手段とを備えている。

　このことにより、１つの文字が互いに分離した複数のストロークで構成され、重なりネスト統合処理を行わなかったために、各ストロークごとに生成される外接矩形がそのまま残ってしまう場合においても、１つの文字の一部から構成される外接矩形は、１つの文字全体からの構成される外接矩形よりも、サイズが小さくなることから、１つの文字の一部から構成される外接矩形の頻度の評価を低くすることが可能となり、文字サイズを推定する際に、文字の部分的な大きさが文字サイズの推定に影響することを小さくすることが可能となるため、重なりネスト統合処理を行わない場合においても、文字サイズを精度よく推定することが可能となる。

　また、本発明の一態様によれば、前記外接矩形生成手段で生成された外接矩形のグルーピングを行うグルーピング手段と、前記文字サイズ推定手段で推定された文字サイズを有する第１の外接矩形を所定の個数以上含む第２の外接矩形を抽出する枠矩形抽出手段と、前記第２の外接矩形を前記グルーピングの対象から除外する枠矩形除外手段とを備えている。

　このことにより、新聞などから見出し文字を抽出する場合において、見出し文字の近くに本文文字を囲む枠矩形が存在する場合においても、この枠矩形のみを抽出することが可能となり、見出し文字の外接矩形と区別することが可能となることから、見出し文字のみを精度良く抽出することが可能となる。

　また、本発明の一態様によれば、前記外接矩形に与えられた矩形番号を前記入力画像に設定された各座標に射影する射影手段を備え、前記枠矩形抽出手段は、前記各座標に含まれる矩形番号を前記第２の外接矩形の座標の範囲内で探索することにより、第１の外接矩形を抽出するようにしている。

　このことにより、外接矩形内に存在する他の外接矩形を容易に抽出することが可能となり、本文文字を囲む枠矩形と見出し文字とが混在している場合においても、枠矩形のみを高速に抽出することが可能となる。

　また、本発明の一態様によれば、入力画像の連結成分を抽出する連結成分抽出手段と、前記連結成分の外接矩形を生成する外接矩形生成手段と、前記外接矩形が互いに重なっている他の外接矩形の個数を算出する重なり度評価手段と、前記重なり度評価手段の算出結果に基づいて、重なりネスト統合処理を行う重なりネスト統合処理手段とを備えている。

　このことにより、重なり度の大きな外接矩形だけを対象に重なりネスト統合処理を行い、重なり度の小さな外接矩形の重なりネスト統合処理を行わないようにすることが可能となることから、外接矩形が画面全体で統合されて、見出し文字の外接矩形が消失することを防止することが可能となるとともに、重なり度の大きな図や写真の一部をより大きな矩形に吸収統合しておくことが可能となり、図や写真の一部の外接矩形がそのまま残り、見出し文字として誤って抽出されたり、見出し文字を構成するものとして誤って矩形統合されたりすることを防止することが可能となり、見出し文字と図や写真などが混在している場合においても、見出し文字の抽出を精度良く行うことが可能となる。

　また、本発明の一態様によれば、前記外接矩形に与えられた矩形番号を前記入力画像に設定された各座標に射影する射影手段と、前記各座標に含まれる矩形番号を所定の外接矩形の座標の範囲内で探索することにより、前記所定の外接矩形に重なっている他の外接矩形を抽出する重なり矩形抽出手段とを備えている。

　このことにより、互いに重なっている外接矩形を容易に抽出することが可能となり、外接矩形の重なり度を高速に算出することが可能となる。

　本発明によれば、連結成分の家族的類似性からグループ分けし、グループ毎に文字認識処理を実施し文字列らしさを付与し、整合性のある組合せのグループを抽出するので、白黒混在の背景模様、複数のフォント混在、カラー文書、複数行、縦横混在、およびそれらの複合体で構成される複雑な画像から文字列を抽出することが可能になるという効果がある。

　また、本発明の一態様によれば、抽出処理の途中では、色の決定や文字列領域の仮定を行わず、また、抽出処理の過程で一律に標準文字の線幅を決めてしまうことがないので、文字色を見誤ることがなく、かつ比較的細い線分を見落とすことがなくなり、文字列抽出の精度が向上するという効果がある。

　また、本発明の一態様によれば、入力画像及び前記入力画像の白黒反転画像のそれぞれから得られるパターンの認識結果のうち、互いに領域が重複しない部分を組み合わせたものを、前記入力画像からのパターンの抽出結果とすることにより、新聞などの見出し文字の中に、黒画素で構成された文字と白抜き文字とが混在している場合においても、黒文字候補と白文字候補の個数から文字の色を決定されて、文字色が黒とされた場合は入力画像の連結成分のみがそれ以降の処理対象とされ、黒文字は正確に認識できるが、白抜き文字は認識不能となったり、文字色が白とされた場合は白黒反転画像の連結成分のみが文字認識の処理対象とされ、白抜き文字は正確に認識できるが、黒文字は認識不能となったりすることを防止することが可能となり、背景模様の白黒混在、複数種類のフォント混在、カラー文書、複数行、縦横混在、及びそれらの複合体で構成される複雑な画像から文字列を精度よく抽出することが可能となる。

　また、本発明の一態様によれば、外接矩形の頻度をその外接矩形の面積で重み付けることにより、１つの文字が互いに分離した複数のストロークで構成され、重なりネスト処理を行わなかったために、各ストロークごとに生成される外接矩形がそのまま残ってしまう場合においても、１つの文字の一部から構成される外接矩形は、１つの文字全体からの構成される外接矩形よりも、サイズが小さくなることから、１つの文字の一部から構成される外接矩形の頻度を小さくすることが可能となり、文字サイズを推定する際に、文字の部分的な大きさが文字サイズの推定に影響することを小さくすることが可能となり、重なりネスト処理を行わない場合においても、文字サイズを精度よく推定することが可能となる。

　また、本発明の一態様によれば、枠の中に含まれている本文文字の個数を数えることにより、新聞などから見出し文字を抽出する場合において、見出し文字の近くに本文文字を囲む枠矩形が存在する場合においても、この枠矩形のみを抽出することが可能となり、見出し文字の外接矩形と区別することが可能となることから、見出し文字のみを精度良く抽出することが可能となる。

　また、本発明の一態様によれば、外接矩形に与えられた矩形番号を入力画像に設定された各座標に射影することにより、外接矩形内に存在する他の外接矩形を容易に抽出することが可能となり、本文文字を囲む枠矩形と見出し文字とが混在している場合においても、枠矩形のみを高速に抽出することが可能となる。

　また、本発明の一態様によれば、重なりネスト統合を部分的に行うことにより、重なり度の大きな外接矩形だけを対象に重なりネスト処理を行い、重なり度の小さな外接矩形の重なりネスト統合処理を行わないようにすることが可能となることから、外接矩形が画面全体で統合されて、見出し文字の外接矩形が消失することを防止することが可能となるとともに、重なり度の大きな図や写真の一部をより大きな矩形に吸収統合しておくことが可能となり、図や写真の一部の外接矩形がそのまま残り、見出し文字として誤って抽出されたり、見出し文字を構成するものとして誤って矩形統合されたりすることを防止することが可能となり、見出し文字と図や写真などが混在している場合においても、見出し文字の抽出を精度良く行うことが可能となる。

　また、本発明の一態様によれば、外接矩形に与えられた矩形番号を入力画像に設定された各座標に射影することにより、互いに重なっている外接矩形を容易に抽出することが可能となり、外接矩形の重なり度を高速に算出することが可能となる。

　以下、本発明の一実施例に係わるパターン抽出装置について、図面を参照しながら説明する。
　図１は、本発明の第１実施例に係わるパターン抽出装置の構成を示すブロック図である。

　図１において、反転画像生成手段１は、入力画像のラベルを反転した反転画像を生成する。認識手段２は、入力画像から抽出されたパターン及び反転画像生成手段１で生成された反転画像から抽出されたパターンの認識処理を行う。出力手段３は、認識手段２で認識された認識結果のうち、入力画像から抽出されたパターンの領域と反転画像生成手段１で生成された反転画像から抽出されたパターンの領域との重なりのない組み合わせを、整合性のある組み合わせとして出力する。

　このことにより、新聞などの見出し文字の中に、黒画素で構成された文字と白抜き文字とが混在している場合においても、黒画素で構成された文字と白抜き文字との両方について認識処理を行い、黒画素で構成された文字の認識結果及び白抜き文字の認識結果を組み合わせて出力することが可能となる。

　このため、黒文字候補と白文字候補の個数から文字の色が決定されて、文字色が黒とされた場合は入力画像の連結成分のみがそれ以降の処理対象とされ、黒文字は正確に認識できるが、白抜き文字は認識不能となったり、文字色が白とされた場合は白黒反転画像の連結成分のみが文字認識の処理対象とされ、白抜き文字は正確に認識できるが、黒文字は認識不能となったりすることを防止することが可能となり、背景模様の白黒混在、複数種類のフォント混在、カラー文書、複数行、縦横混在、及びそれらの複合体で構成される複雑な画像から文字列を精度よく抽出することが可能となる。

　図２は、本発明の第２実施例に係わるパターン抽出装置の構成を示すブロック図である。
　図２において、連結成分抽出手段１１は、入力画像のラベリングを行うことにより、入力画像の連結成分を抽出する。外接矩形生成手段１２は、連結成分抽出手段１１で抽出された連結成分の外接矩形を生成する。重なり度評価手段１３は、外接矩形生成手段１２で生成された外接矩形が互いに重なっている他の外接矩形の個数を算出する。重なりネスト統合処理手段１４は、重なり度評価手段１３の算出結果に基づいて、重なりネスト統合処理を行う。

　このことにより、重なりネスト統合を部分的に行うことが可能となり、重なり度の大きな外接矩形だけを対象に重なりネスト統合処理を行い、重なり度の小さな外接矩形の重なりネスト統合処理を行わないようにすることが可能となることから、外接矩形が画面全体で統合されて、見出し文字の外接矩形が消失することを防止することが可能となる。

　また、重なり度の大きな図や写真の一部をより大きな矩形に吸収統合しておくことが可能となり、図や写真の一部の外接矩形がそのまま残り、見出し文字として誤って抽出されたり、見出し文字を構成するものとして誤って矩形統合されたりすることを防止することが可能となり、見出し文字と図や写真などが混在している場合においても、見出し文字の抽出を精度良く行うことが可能となる。

図３は、本発明の一実施例に係わる情報検索装置のシステム構成を示すブロック図である。
　図３において、２１は全体的な処理を行う中央演算処理ユニット（ＣＰＵ）、２２はリードオンリメモリ（ＲＯＭ）、２３はランダムアクセスメモリ（ＲＡＭ）、２４は通信インターフェイス、２５は通信ネットワーク、２６はバス、２７は入出力インターフェイス、２８は見出し文字などの認識結果などを表示するディスプレイ、２９は見出し文字などの認識結果などを印刷するプリンタ、３０はスキャナ３１により読み取られたデータを一時的に格納するメモリ、３１は入力画像などを読み取るスキャナ、３２はキーボード、３３は記憶媒体を駆動するドライバ、３４はハードディスク、３５はＩＣメモリカード、３６は磁気テープ、３７はフレキシブルディスク、３８はＣＤ−ＲＯＭやＤＶＤ−ＲＯＭなどの光ディスクである。

　パターン抽出処理を行うプログラムなどは、ハードディスク３４、ＩＣメモリカード３５、磁気テープ３６、フレキシブルディスク３７、光ディスク３８などの記憶媒体に格納される。そして、パターン抽出処理を行うプログラムなどを、これらの記憶媒体からＲＡＭ２３に読み出すことにより、新聞や雑誌などの文書画像から見出し文字などの抽出を行うことができる。また、パターン抽出処理を行うプログラムなどを、ＲＯＭ２２に格納しておくこともできる。

　さらに、パターン抽出処理を行うプログラムなどを、通信インターフェイス２４を介して通信ネットワーク２５から取り出すこともできる。通信インターフェイス２４に接続される通信ネットワーク２５として、例えば、ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、インターネット、アナログ電話網、デジタル電話網（ＩＳＤＮ：Ｉｎｔｅｇｒａｌ　Ｓｅｒｖｉｃｅ　Ｄｉｇｉｔａｌ　Ｎｅｔｗｏｒｋ）、ＰＨＳ（パーソナルハンディシステム）や衛星通信などの無線通信網を用いることができる。

　ＣＰＵ２１は、パターン抽出処理を行うプログラムが起動されると、スキャナ３１により読み取られた入力画像にラベリングを行い、同一ラベルが付された連結成分ごとに外接矩形を生成する。そして、各外接矩形の重なり度を調べ、重なり度の大きな外接矩形同士に対して、重なりネスト統合を行う。次に、重なりネスト統合が行われた外接矩形のグルーピングを行い、そのグルーピング結果の中から見出し文字を抽出し、その抽出結果をディスプレイ２８やプリンタ２９に出力する。

　図４は、本発明の第３実施例に係わる文字列抽出装置の動作を説明する図である。
　図４（ａ）において、黒枠の中に「黒白反転」と２行に渡って書かれた黒画素文字と、「調査グ」と縦書きで書かれた白抜き文字が入力画像として入力されたものとし、この入力画像から、「黒白反転」という文字列と「調査グ」という文字列とを抽出するものとする。

　まず、入力した画像から画素の色に基づいて、画素の色が連なる連結成分を抽出する。
　入力画像がカラー画像である場合は、各色について連結成分を抽出する。図４（ａ）の入力画像は白黒２値画像であるで、白黒２値を反転させた反転画像についても、黒画素および白画素が連なる連結成分を抽出する。反転画像は図４（ａ）に示すように、入力画像の背景領域の色と文字部分の色とが反転する。

　この連結成分の抽出処理により、入力画像の黒画素の各連結成分ごとに、異なるラベルが付されるととも、反転画像の黒画素の各連結成分ごとに、異なるラベルが付される。
　次に、入力画像と反転画像のそれぞれについて、連結成分と連結成分の位置関係および連結成分と連結成分の太さの類似性から、共通の文字列または文字列群を構成する可能性が高い連結成分をグループ分けする。

　ここで、連結成分の太さの類似性とは、連結成分の全画素数に対する境界画素数の比のことであり、共通の文字列または文字列群とは、意味的に共同して同一のことがらを表現する文字列の集合のことである。

　その結果、図４（ａ）に示すように、入力画像の「黒白反転」という文字は、太さが互いに同じで、それぞれ近接して配置されているので、グループａにグルーピングされる。また、入力画像の「黒白反転」という文字を囲む枠及び「調査グ」という白抜き文字の背景部分に対応する黒画素領域は、黒画素で１つに連結しているので、グループｂにグルーピングされる。

　また、反転画像の「黒白反転」という白抜き文字の背景部分に対応する黒画素領域及び「調査グ」という文字を囲む枠は、黒画素で１つに連結しているので、グループａ１にグルーピングされる。また、反転画像の「調査グ」という文字は、太さが互いに同じで、それぞれ近接して配置されているので、グループｂ１にグルーピングされる。

　ここで、グループａは背景領域が白で比較的小さい文字のグループであり、グループｂは背景領域が黒で比較的大きめの白抜き文字であるが、この時点ではグループｂは白抜き文字とは認識できていない。グループａには白を背景に文字があるらしいこと、グループｂは全体が黒っぽいことが判る程度である。このため、グループｂの黒画素で構成される背景領域についての文字認識処理を行っても、「調査グ」という文字を認識することはできない。

　また、グループａ１は背景領域が黒で比較的小さめの白抜き文字であり、グループｂ１は背景領域が白で比較的大きい文字のグループであるが、この時点ではグループｂ１は白抜き文字とは認識できていない。グループａ１は全体が黒っぽいこと、グループｂ１には白を背景に文字があるらしいことが判る程度である。このため、グループａ１の黒画素で構成される背景領域についての文字認識処理を行っても、「黒白反転」という文字を認識することはできない。

　このようにグループ分けされると、グループ毎に文字認識処理を行う。その結果の各文字の第１位認識候補の距離値の逆数の和をグループの文字認識度とする。従って、グループの文字認識度の値が高ければ、抽出すべき文字列である可能性が高いことになる。グループの文字認識度にグループが占める矩形領域の面積によって重み付けしたものをグループの評価値とする。

　次に、全てのグループの組合せについて評価値を求め、組合せの評価値とする。グループを組合せる時には、グループが占める矩形領域に重なりがないグループのみを関連付け、グループが占める矩形領域に重なりがないグループの組合せを全て求める。

　図４（ｂ）の組合せは、グループが占める矩形領域に重なりがないグループを組合せることを説明するための図である。
　図４（ｂ）に示すように、図４（ａ）のグループａは、グループｂ１が占める矩形領域と重ならないため、グループｂ１と組み合わされる可能性があるが、グループｂ及びグループａ１とは、グループが占める矩形領域が重なるため、グループｂ及びグループａ１と組み合わされることがない。

　一方、グループｂは、グループａ、グループａ１、あるいはグループｂ１のどのグループと組み合わせても、グループが占める矩形領域が重なるため、グループａ、グループａ１、あるいはグループｂ１のいずれのグループとも組み合わされる可能性がない。

　従って、全ての組合せから、グループａとグループｂの組合せ、グループａとグループａ１の組合せ、グループｂとグループａ１の組合せ、グループｂとグループｂ１の組合せ及びグループａ１とグループｂ１の組合せが除外され、グループａとグループｂ１の組合せだけが残る。図４（ｂ）に除外される組合せを点線で示す。実線で接続されるグループの組合せの全てについて評価値が計算される。その結果、組合せの評価値が最も高いグループの組合せを文字列として抽出する。

　図４（ｃ）は、抽出結果を示す。
　図４（ｃ）において、グループａとグループｂ１の組合せが選択され、グループａから抽出されるパターンの文字認識を行った結果、「黒白反転」という文字列が出力され、グループｂ１から抽出されるパターンの文字認識を行った結果、「調査グ」という文字列が出力される。

　ここで、もし、グループｂについての文字認識を行った場合には、グループｂは、入力画像の「黒白反転」という文字を囲む枠及び「調査グ」という白抜き文字の背景部分に対応する黒画素領域で構成されているため、「調査グ」という文字列を正しく認識することができない。

　このため、図４（ａ）の入力画像から抽出されるパターンだけを用いて、認識処理を行うと、「黒白反転」という文字列は抽出できるが、「調査グ」という文字列は抽出できなくなる。

　一方、グループａ１についての文字認識を行った場合には、グループａ１は、反転画像の「黒白反転」という白抜き文字の背景部分に対応する黒画素領域及び「調査グ」という文字を囲む枠で構成されているため、「調査グ」という文字列を正しく認識することができない。

　このため、図４（ａ）の反転画像から抽出されるパターンだけを用いて、認識処理を行うと、「調査グ」という文字列は抽出できるが、「黒白反転」という文字列は抽出できなくなる。

　これに対して、図４の実施例では、入力画像から抽出されるパターン及び反転画像から抽出されるパターンの両方を用いて文字認識を行い、「黒白反転」という文字列は入力画像から抽出し、「調査グ」という文字列は反転画像から抽出することができるので、「黒白反転」という文字列及び「調査グ」という文字列の両方とも正しく抽出するこができる。

　図５は、本発明の第３実施例に係わる文字列抽出装置の構成を示すブロック図である。
　図５において、文字列抽出装置４１は、連結成分抽出手段４２とグルーピング手段４３と文字認識手段４４と組合せ評価手段４５と文字列抽出手段４６を備えている。

　連結成分抽出手段４２では、入力した画像から画素の色に基づいて画素の色が連なる連結成分を抽出する。入力画像がカラー画像である場合は各色について連結成分を抽出し、入力画像が白黒２値画像である場合は反転画像についても黒画素および白画素が連なる連結成分を抽出する。

　グルーピング手段４３では、連結成分と連結成分の位置関係および連結成分と連結成分の太さの類似性から共通の文字列または文字列群を構成する可能性が高い連結成分をグループ分けする。

　文字認識手段４４では、グループ毎に文字認識処理を行い、グループの文字認識度を求める。組合せ評価手段４５では、グループの評価値を求め、更に組合せの評価値を求める。文字列抽出手段４６では、組合せの評価値が最も高いグループの組合せを文字列として抽出する。

　このように、図５の文字列抽出装置４１では、連結成分の類似性からグループ分けし、グループ毎に文字認識処理を実施し文字列らしさを付与し、整合性のある組合せのグループを抽出するので、黒白混在の背景模様、カラー文書などの複雑な画像から文字列を抽出することが可能になる。

　また、図５の文字列抽出装置４１および記録媒体では、抽出処理の途中では色の決定を行わず、文字列領域の仮定も行わず、また、抽出処理の過程で一律に標準文字の線幅を決定しないので、文字列抽出の精度が向上する。

　以下、本発明の第３実施例に係わる文字列抽出装置４１について図面を用いて詳細に説明する。この文字列抽出装置４１の実施例として、新聞の見出しなどの白黒２値の画像から文字列を抽出する場合を例にとる。

　図６は、本発明の第３実施例に係わる文字列抽出装置の動作を示すフローチャートである。
　図６において、まず、ステップＳ１において、画像が入力され、ステップＳ２に進む。ステップＳ２では、入力された画像に対し黒白反転の画像を生成する。続いて、入力画像と反転画像の処理を並行して行うが、入力画像の処理をする場合はステップＳ３へ、反転画像の処理をする場合はステップＳ６に進む。

　入力画像と反転画像が得られると、続いてそれぞれの連結成分を求めるためにラベリング処理を行う。ステップＳ３では、入力画像のラベリング処理を、ステップＳ６では、反転画像のラベリング処理を行う。

　入力画像と反転画像のラベリングに続いて、それぞれの連結成分をグルーピング（グループ分け）する。図６のステップＳ４では、入力画像のグルーピングを、ステップＳ７では、反転画像のグルーピングを行う。

　入力画像と反転画像のグルーピングに続いて、それぞれのグループの文字認識処理を行う。ステップＳ５では、入力画像のグループの文字認識処理を、ステップＳ８では、反転画像のグループの文字認識処理を行う。

　入力画像と反転画像のグループの文字認識処理に続いて、ステップＳ９に進む。ステップＳ９では、グループが占める矩形領域に重なりがあるグループをグループの組合せから除外し、整合性のある組合せを全て数え上げる。

　ステップＳ１０では、候補に上がった組合せの各々について、評価値に基づいて評価する。各グループの評価値は、グループの文字認識度と各グループが占める矩形領域の面積との関数であり、組合せの評価値は、整合性のある組合せについてグループの評価値を組み合わせて求める。

　続いて、ステップＳ１１に進み、ステップＳ１０において、組合せの評価値が最高の組合せのグループに対応する文字列を抽出して処理を終了する。
　図７は、本発明の一実施例に係わるラベリング処理を説明する図である。

　図７において、白抜き文字の「祭」の１文字が１から４までの番号を付けた４つの連結成分Ｒ１〜Ｒ４から構成されていることが示される。このように、同じ色の画素（図４では白画素）が連なる連結成分を番号などによって識別してゆくことをラベリングという。

　図８は、本発明の一実施例に係わるグルーピング処理を示すフローチャートである。
　図８において、まず、ステップＳ２１において、文字成分候補を選択する。ステップＳ２１では、対象連結成分の絞り込みを行う。ここでは、連結成分の外接矩形の大きさがある基準以下のものを除去し、明らかに文字成分候補となり得ないものを今後の処理の対象外にする。続いて、ステップＳ２２に進む。

　ステップＳ２２では、連結成分に対して近傍を設定する。近傍は、連結成分の外接矩形の周囲を一定の大きさで囲んだ時にできる領域とする。連結成分の近傍に一部が含まれる連結成分を近傍連結成分と呼ぶ。続いて、ステップＳ２３に進む。

　ステップＳ２３では、連結成分とその近傍連結成分とをリンクさせる。ここでリンクとは、連結成分および近傍連結成分のそれぞれが同じ文字列あるいは同じ文字列群に属するかを判断し、連結成分とその近傍連結成分とを関係付けることである。

　連結成分のリンクは、連結成分の相対的位置および太さの類似性に基づいて行われる。連結成分間の相対的位置と太さの類似性のことを連結成分の家族的類似性と呼ぶ。ステップＳ２３では、全ての連結成分および全ての近傍連結成分との家族的類似性が判断され、ステップＳ２４に進む。

　ステップＳ２４では、リンクで結ばれた連結成分および近傍連結成分をグループとして抽出する。連結成分のリンクの仕方は様々であり、例えば、連結成分Ａと連結成分Ｂと連結成分Ｃがリンクで結ばれているが、連結成分Ａと連結成分Ｃは直接結ばれていない場合がある。また、連結成分Ａから連結成分Ｂにリンクしているが、連結成分Ｂから連結成分Ａにはリンクしていない場合もある。

　このようなリンクを形成する連結成分を弧状連結の連結成分と呼ぶ。ステップＳ２４では、リンクで結ばれた弧状連結の連結成分の集合を取り出して一つのグループとする。
　図９は、本発明の一実施例に係わる連結成分と外接矩形の例を示す図である。

　図９において、カタカナの「タ」という文字が一つの連結成分であり、その外接矩形のｘ方向の長さがｄｘ、ｙ方向の長さがｄｙである。
　図１０は、本発明の一実施例に係わる対象連結成分の絞り込み方法を示すフローチャートである。

　図１０において、連結成分の外接矩形を表すｘ方向の長さｄｘのしきい値とｙ方向の長さｄｙのしきい値とを、それえぞｔｈ１乃至ｔｈ２と予め決めておく。図１０のステップＳ３１において、ｘ方向の長さｄｘとｙ方向の長さｄｙが入力されると、ステップＳ３２において、ｙ方向の長さｄｙがしきい値ｔｈ２より小さいかどうかが判定される。

　ステップＳ３２において、ｙ方向の長さｄｙがしきい値ｔｈ２より小さければ、ステップＳ３３に進み、ｙ方向の長さｄｙがしきい値ｔｈ２より小さくなければ、ステップＳ３６に進む。ステップＳ３３において、ｘ方向の長さｄｘがしきい値ｔｈ１より大きく、しきい値ｔｈ２より小さければ、ステップＳ３５に進み、ｘ方向の長さｄｘがしきい値ｔｈ１以下であるか、しきい値ｔｈ２以上であれば、ステップＳ３４に進む。

　ステップＳ３４において、ｙ方向の長さｄｙがしきい値ｔｈ１より大きければ、ステップＳ３５に進み、ｙ方向の長さｄｙがしきい値ｔｈ１より大きくなければ、ステップＳ３６に進む。

　ステップＳ３５においては、当該の連結成分を文字成分候補となり得るものとし、ステップＳ３６においては、当該の連結成分を今後の処理の対象外にして処理を終了する。
　図１１は、本発明の一実施例に係わる連結成分近傍を説明する図である。

　図１１において、近傍は連結成分の外接矩形の周囲を一定の大きさで囲んだ時にできる領域である。
　ここで、一定の大きさとは、図１１に示すように、縦書きの場合は横方向の両側にそれぞれ横方向サイズ×（１／６）、縦方向の上下に縦方向サイズ×（３／４）の領域とする。横書きの場合も近傍の定義は同じである。

　図１１では、「京」という文字に着目して、「京」の近傍を設定した場合、「京」の近傍には、「東」という文字と「に」という文字がかかっているので、「京」という文字の近傍連結成分が「東」という文字と「に」という文字であることが判る。図１１の「東京に今秋」の背景領域の半分には大小の網点が配置されており、「京」の文字は○印を付けた部分で接触しているように見えるため、「京」の１文字が一つの連結成分と見なされる。

　なお、図１１で「京」の文字が○印を付けた部分で接触していないとすると、「京」は「なべぶた」とそれ以外の２つの連結成分からなり、それぞれの連結成分の近傍について、それぞれのサイズについて近傍連結成分が調べられる。

　図１２は、本発明の一実施例に係わる連結成分の家族的類似性を説明する図である。
　図１２において、連結成分の家族的類似性は連結成分間の相対的な位置関係と連結成分の平均的太さの差に依存して定まる。ここで、平均的太さは、連結成分の全画素数に対する境界画素数の比、すなわち（境界画素数／全画素数）で表される。

　図１２に示す連結成分Ａと連結成分Ａの近傍連結成分Ｂの位置関係をｄおよびｎｘ、連結成分Ａと近傍連結成分Ｂの平均的太さをそれぞれｔａとｔｂとすると、連結成分Ａに対する近傍連結成分Ｂの家族的類似性は、以下の式で表される。

　連結成分Ａに対する近傍連結成分Ｂの家族的類似性
　＝ｄ／ｎｘ＋０．１×ｍａｘ（ｔａ，ｔｂ）／ｍｉｎ（ｔａ，ｔｂ）
　ここで、ｄは、近傍連結成分Ｂのｘ方向の成分ｎｘが連結成分Ａからはみ出た部分の長さを表す。

　図１２に示す連結成分Ａに対する近傍連結成分Ｂの家族的類似性も、連結成分Ｂに対する連結成分Ｃの家族的類似性も同程度に高いので、それぞれの連結成分Ａ，Ｂ，Ｃは同じ文字列に属すると判断される。ここでは、連結成分Ｂに対する連結成分Ｃの家族的類似性は太さの成分についてのみ考慮される。

　図１３は、本発明の一実施例に係わるグループの文字認識度の算出方法を説明する図である。
　図１３において、グループの文字認識度はグループごとに文字認識処理を行い、その結果の各文字の第１位認識候補の距離値の逆数の和で表される。文字の距離値が小さいことは文字の認識度が高いことを意味する。

　図１３に示すように、例えば、「東京に今秋」という文字列をグループＡ、グループＡの各文字「東」、「京」、「に」、「今」、「秋」の第１位認識候補の距離値をそれぞれｄ１，ｄ２，ｄ３，ｄ４，ｄ５とすると、グループＡの文字認識度Ｒａは、以下の式で表される。

　Ｒａ＝１／ｄ１＋１／ｄ２＋１／ｄ３＋１／ｄ４＋１／ｄ５
　なお、図１３の「東京の今秋」という文字列の背景領域にある「網点模様」は完全に「点」であれば、対象連結成分の絞り込みで対象外とされる可能性が高いが、仮に、点と点が接続された「網目模様」であるとすると、グループＢとして分類され、グループＢも、「網目模様」の反転画像のグループも、文字認識度は０であることが予想される。また、このグループＢの「網目模様」は、「東京の今秋」という文字列からなるグループＡと重なっているため、グループＢがグループＡと組み合わされて出力されることはない。

　図１４は、本発明の一実施例に係わる連合グラフとクリークを示す図である。
　図１４において、グループが占める矩形領域に重なりがないグループのみを関連付け、グループが占める矩形領域に重なりがないグループの組合せを全て求めるために、連合グラフとクリークの概念を用いている。

　すなわち、整合性のある組合せを数え上げるために連合グラフを作成し、完全グラフであるクリークを全て求めることで、グループが占める矩形領域に重なりがあるグループをグループの組合せから除外することができる。

　図１４の連合グラフは、グループをノードとして、グループが占める矩形領域が互いに重ならないグループに相当するノード同士を、パス（実線）で接続して作成したものである。連合グラフにおいて、矩形領域に重なりがあるグループに相当するノード同士はパスで接続されない。

　クリークは整合性あるノードの組合せを表す。クリークは連合グラフから複数作成され、それぞれのクリークは全てのノードがパスで結ばれる完全グラフである。連合グラフからクリークを求めることで整合性のあるグループの組合せを全て数え上げることができる。

　図１３ところで仮に設定したグループＢの「網目模様」とグループＡの「東京に今秋」について、グループＡとグループＢとが個別に認識されても、グループＡとグループＢとの組合せとして成立しないのはこのためである。

　こうして整合性のあるグループについての組合せの評価値を求めることが可能になり、評価の結果、例えば、背景領域にある網目模様や、汚れなどが除外されることになる。
　例えば、図１４において、ノードＮ１〜Ｎ８からなる連合グラフが作成されたものとすると、各ノードから他の全てのノードにパスがででいる完全グラフを求める。例えば、ノードＮ１は、ノードＮ１から他の全てのノードＮ２〜Ｎ８にパスがでているので、ノードＮ１は、クリークのノードとなり、ノードＮ２は、ノードＮ２からノードＮ８にパスがでていないので、ノードＮ２は、クリークのノードから除外され、ノードＮ３は、ノードＮ３から他の全てのノードＮ１、Ｎ２、Ｎ４〜Ｎ８にパスがでているので、ノードＮ３は、クリークのノードとなり、ノードＮ４は、ノードＮ４から他の全てのノードＮ１２〜Ｎ３、Ｎ５〜Ｎ８にパスがでているので、ノードＮ４は、クリークのノードとなり、ノードＮ５は、ノードＮ５から他の全てのノードＮ１〜Ｎ４、Ｎ６〜Ｎ８にパスがでているので、ノードＮ５は、クリークのノードとなり、ノードＮ６は、ノードＮ６からノードＮ８にパスがでていないので、ノードＮ６は、クリークのノードから除外され、ノードＮ７は、ノードＮ７から他の全てのノードＮ１〜Ｎ６、Ｎ８にパスがでているので、ノードＮ７は、クリークのノードとなり、ノードＮ８は、ノードＮ８から他の全てのノードＮ１〜Ｎ７にパスがでているので、ノードＮ８は、クリークのノードとなる。

　この結果、ノードＮ１、Ｎ３、Ｎ４、Ｎ５、Ｎ７、Ｎ８からなるクリークを抽出することができる。連合グラフからクリークを抽出することにより、矩形領域が互いに重ならないグループのみを効率的に抽出することができる。

　図１５は、本発明の一実施例に係わる連結成分の重なりのないグループの抽出方法を示すフローチャートである。
　図１５において、各グループについて、他の全てのグループに対し関連付けられるかどうかの判断を行い（ステップＳ４１）、連合グラフを生成する（ステップＳ４２）。次に、連合グラフからクリークを抽出し（ステップＳ４３）、入力画像から抽出されるグループと反転画像から抽出されるグループの組み合わせのうち、整合性のある組み合わせを確定する（ステップＳ４４）。

　図１６は、本発明の一実施例に係わる連結成分同士のリンク付けの方法を説明する図である。
　図１６（ａ）において、「水道メーター」という背景が黒色の白抜き文字と「談合解明」という黒画素文字が入力されたものとし、「談」という文字の一部の連結成分Ｒ１１とリンク付けられる連結成分を抽出するものとする。

　この場合、図１６（ｂ）に示すように、連結成分Ｒ１１の外接矩形Ｇ１が生成され、この外接矩形Ｇ１の周囲に連結成分の近傍Ｂ１が設定される。連結成分の近傍Ｂ１が設定されると、図１６（ｃ）に示すように、連結成分の近傍Ｂ１にかかる近傍連結成分Ｒ１２〜Ｒ２０が抽出される。近傍連結成分Ｒ１２〜Ｒ２０が抽出されると、図１６（ｄ）に示すように、連結成分Ｒ１１と近傍連結成分Ｒ１２〜Ｒ２０との家族的類似性が調べられる。ここで、近傍連結成分Ｒ１２は連結成分Ｒ１１と太さが大きく異なるので、近傍連結成分Ｒ１２は連結成分Ｒ１１とのリンク付けの対象から除外され、近傍連結成分Ｒ１２を除いた近傍連結成分Ｒ１３〜Ｒ２０が連結成分Ｒ１１とリンク付けられる。

　図１７は、本発明の一実施例に係わるクリークとなるグループとクリークとならないグループの例を示す図である。
　図１７（ａ）において、原画像の「水道メーター」という文字は、太さが互いに同じで、それぞれ近接して配置されているので、グループ１にグルーピングされる。また、原画像の「談合解明」という白抜き文字の背景部分に対応する黒画素領域は、黒画素で１つに連結しているので、グループ２にグルーピングされる。

　また、反転画像の「水道メーター」という白抜き文字の背景部分に対応する黒画素領域は、黒画素で１つに連結しているので、グループａにグルーピングされる。また、反転画像の「談合解明」という文字は、太さが互いに同じで、それぞれ近接して配置されているので、グループｂにグルーピングされる。

　次に、図１７（ｃ）に示すように、グループ１とグループｂは、グループ１が占める矩形領域とグループｂが占める矩形領域とが互いに重ならないため、クリークとみなされ、グループ１とグループｂは整合性のある組み合わせとされる。また、図１７（ｄ）に示すように、グループ１とグループａは、グループ１が占める矩形領域とグループａが占める矩形領域とが互いに重なり、クリークでないとみなされるため、グループ１とグループａは整合性のない組み合わせとされる。

　このようにして、図１７（ｂ）に示すように、グループ１は、グループｂ及びグループ２とは整合性のある組み合わせとなるが、グループａとは整合性のある組み合わせとならない。また、グループ２は、グループ１及びグループａとは整合性のある組み合わせとなるが、グループｂとは整合性のある組み合わせとならない。また、グループａは、グループ２及びグループｂとは整合性のある組み合わせとなるが、グループ１とは整合性のある組み合わせとならない。また、グループｂは、グループ１及びグループａとは整合性のある組み合わせとなるが、グループ２とは整合性のある組み合わせとならない。

　図１８は、本発明の一実施例に係わる組合せの評価値の算出方法を示す図である。
　図１８において、組合せの評価値は、整合性のある組合せについて、グループの文字認識度と各グループが占める矩形領域の面積との関数であるグループの評価値を組み合わせて求める。

　例えば、図１８の入力画像から整合性のあるグループの組合せとして、グループＡとグループＢの組合せを得たとする。グループＡが占める矩形領域の面積をＳａ、グループの文字認識度をＲａ、グループＢが占める矩形領域の面積をＳｂ、グループの文字認識度をＲｂとすると、グループＡとグループＢの組合せの評価値は、以下の式で求められる。

　組み合わせ（Ａ、Ｂ）の評価値＝ａＳａ×Ｒａ×Ｒａ＋Ｓｂ×Ｒｂ×Ｒｂ
　なお、本実施例では、黒白画像について説明したが、本実施例は黒白画像に限定されることなく、黒白画素を色の彩度、明度、濃度に置き換えることにより、広くカラー文字やカラーの背景に適用できることは勿論のことである。

　また、本実施例では、縦書き文字を例にして説明したが、縦書き文字にも縦横混在の文字列にも適用できることは勿論のことである。
　次に、本発明の第４実施例に係わるパターン抽出装置について説明する。

　本発明の第４実施例では、連結成分の重なりネスト統合を省略することにより、画像全体が統合されることを防止するととも、見出し領域を抽出する際に悪影響のもとになる図や写真の一部は、より大きな矩形に吸収統合しておくようにして、その影響を軽減する。一般に、図や写真の一部からなる矩形は、互いに重なっていることが多く、これらを見分ける目安となる。そこで、見出し矩形の互いの重なり度を計算し、あるしきい値を越えるものを図や写真の一部からなる矩形と判断し、その矩形に限り重なりネスト統合を行う。

　また、重なりネスト統合を省略した時に、正確な本文文字サイズを推定するために、連結成分の外接矩形の大きさに関するヒストグラムで、頻度及び矩形の面積によって重みづけられたものを利用する。これにより、文字の一部分がそのままカウントされ、実際の本文文字サイズよりも小さい大きさの矩形の数が最大になっても、面積の重みづけがあるので、新しいヒストグラムでは最大にならない。よって、実際の本文文字サイズよりも小さい大きさの矩形が推定文字サイズにはならない。逆に、大きな連結成分があったとしても、面積は大きいものの頻度が小さいので、実際の本文文字サイズよりも大きい大きさの矩形も推定文字サイズにはならない。

　以下、本発明の第４実施例について、白黒２値の画像の場合を例にとって説明する。
　図１９は、本発明の第４実施例に係わるパターン抽出装置の動作を示すフローチャートである。

　図１９において、まず、入力された画像に対し、ラベリング処理を施す（ステップＳ５１）。このラベリング処理により、各連結成分の外接矩形の座標情報が得られる。
　次に、本文文字サイズの推定を行う（ステップＳ５２）。この本文文字サイズの推定では、まず、連結成分の外接矩形の大きさに関するヒストグラムを作成する。ただし、このヒストグラムは、頻度及び矩形の面積によって重みづけられたものとする。具体的には、まず、ある連結成分の横幅をｄｘ、縦幅をｄｙとしたとき、その大きい方のヒトスグラムをとる。さらに、得られたヒストグラムの各値Ｈ（ｉ）に対し、
　Ｈ′（ｉ）＝Ｈ（ｉ）×Ｈ（ｉ）×ｉ×ｉ
（ただし、ｉは矩形の大きさを表す。）
という変換を施して、新しいヒストグラムＨ′を作成する。この新しいヒストグラムＨ′に関し、ヒストグラム値の最大を与えるところを本文文字サイズとする。

　図２０は、本発明の一実施例に係わる外接矩形の大きさを求めるためのヒストグラムの一例を示す図である。
　図２０（ａ）において、重なりネスト統合を行わないで、外接矩形の大きさの頻度Ｈを表すヒストグラムを生成すると、本文文字の大きさに対応するピークＰ２が発生するとともに、統合される前の文字の一部の外接矩形の大きさに対応するピークＰ１が発生する場合がある。

　このため、このヒストグラムを用いて本文文字サイズを推定すると、ピークＰ１に対応する外接矩形の大きさが本文文字サイズと推定され、本文文字サイズの大きさが誤って推定される場合がある。

　一方、図２０（ｂ）において、図２０（ａ）のヒストグラムを外接矩形の大きさで重み付けすると、外接矩形の大きさの大きいピークＰ２のヒストグラム値Ｈに比べて、外接矩形の大きさの小さいピークＰ１のヒストグラム値Ｈは小さくなる。この結果、図２０（ｂ）のヒストグラムでは、統合される前の文字の一部の外接矩形の大きさに対応するピークＰ１’の値に比べて、本文文字の大きさに対応するピークＰ２’の値を大きく評価することが可能となり、ピークＰ１’に対応する外接矩形の大きさが本文文字サイズと誤って推定されることを防止して、本文文字サイズの大きさを正しく推定することが可能となる。

　次に、本文文字矩形候補の射影テーブルの作成を行う（ステップＳ５３）。
　この射影テーブルの作成では、まず、すべての矩形の中から本文文字矩形候補を選出する。具体的には、連結成分の横幅をｄｘ、縦幅をｄｙ、本文文字サイズをｃ、しきい値をαとすると、
　｜ｍａｘ（ｄｘ，ｄｙ）−ｃ｜＜α
を満たす矩形を本文文字矩形候補とする。

　次に、全画像のｘ座標軸、及びｙ座標軸に関し、本文文字矩形候補の射影をとる。すなわち、ある本文文字矩形候補の番号をｎ、その矩形の左上点の座標を（ｘ１，ｙ１）、右下点の座標を（ｘ２，ｙ２）とした時、ｘ座標軸上でｘ１〜ｘ２までのところに、また、ｙ座標軸上でｙ１〜ｙ２までのところに、番号ｎを記録する。このようにして、本文文字矩形候補の射影テーブルを作成する。

　図２１は、本発明の一実施例に係わる矩形番号の射影方法の一例を示す図である。
　図２１において、矩形番号１〜６の外接矩形が生成されたものとすると、各矩形番号１〜６をｘｙ座標軸に射影する。例えば、ｘ座標が４〜６の点には、矩形番号１、６の外接矩形がかかっているので、ｘ座標が４〜６の点には矩形番号１、６が射影される。また、ｘ座標が７、８、１０の点には、矩形番号６の外接矩形がかかっているので、ｘ座標が７、８、１０の点には矩形番号６が射影される。また、ｘ座標が９の点には、矩形番号２、４、６の外接矩形がかかっているので、ｘ座標が９の点には矩形番号２、４、６が射影される。また、ｘ座標が１１の点には、矩形番号３、５の外接矩形がかかっているので、ｘ座標が１１の点には矩形番号３、５が射影される。ｙ座標についても同様である。

　次に、見出し矩形候補の選択を行う（ステップＳ５４）。この見出し矩形候補の選択では、見出し及び見出しを構成する文字を選択する。基本的には、本文文字のある一定倍の大きさ以上のものを、見出し矩形候補とする。

　図２２は、本発明の一実施例に係わる見出し矩形候補の選択方法を示すフローチャートである。
　図２２において、まず、矩形の左上点の座標を（ｘ１，ｙ１）、矩形の右下点の座標を（ｘ２，ｙ２）、矩形の右下点のｘ座標ｘ２と矩形の左上点のｘ座標ｘ１との差をｄｘ、矩形の右下点のｙ座標ｙ２と矩形の左上点のｙ座標ｙ１との差をｄｙ、本文文字サイズをｍｏｊｉとする（ステップＳ７１）。

　次に、以下の条件を満たすかどうかを判断し（ステップＳ７２）、この条件を満たさない場合は、見出し矩形候補でないとして処理を終了し、この条件を満たす場合は、ステップＳ７３に進む。

　（ｄｘ＜ｍｏｊｉ×１６またはｄｙ＞ｍｏｊｉ×２）
かつ
　（ｄｘ＞ｍｏｊｉ×２またはｄｙ＜ｍｏｊｉ×１６）
　次に、以下の条件を満たすかどうかを判断し（ステップＳ７３）、この条件を満たさない場合は、見出し矩形候補でないとして処理を終了し、この条件を満たす場合は、見出し矩形候補として登録する（ステップＳ７４）。

　（ｄｘ＞ｍｏｊｉ×３／２またはｄｙ＞ｍｏｊｉ×３／２）
かつ
　（ｄｘ＞ｍｏｊｉ／３またはｄｙ＞ｍｏｊｉ／３）
　次に、枠矩形のチェックを行う（ステップＳ５５）。

　枠の全体、あるいはその一部からなる連結成分の外接矩形を枠矩形と呼ぶことにすると、枠矩形は、見出しにはなり得ないものの、大きさ及び形状からでは、枠矩形と見出し矩形との判別ができない。そこで、予め矩形全体から枠矩形を除外しなくてはならない。一般に、枠の中には本文文字が数多く含まれ、見出し矩形の中には本文文字がほとんど含まれていないため、矩形の中の本文文字矩形候補の数を調べ、枠矩形かどうかの判断をする。すなわち、注目する領域の外接矩形内に含まれる本文文字矩形候補の数を数え、ある一定の数よりも多いとき、枠、あるいは枠の一部で囲まれた領域であると判断する。ここで、本文文字矩形候補とは、外接矩形が本文文字サイズである連結黒画素領域のことを指す。なお、枠の中の本文文字の数は、文字矩形候補の射影テーブルを用いて、効率的に計算することができる。

　図２３は、本発明の一実施例に係わる枠矩形のチェック方法を説明する図である。
　図２３において、外接矩形Ｋ１〜Ｋ６が抽出され、外接矩形Ｋ１〜Ｋ５が見出し文字の矩形候補として選択されたものとする。ここで、外接矩形Ｋ１〜Ｋ４は見出し文字の外接矩形であり、外接矩形Ｋ５は、本文文字を囲む枠の外接矩形であるものとする。この場合、外接矩形Ｋ１〜Ｋ５が同一のグループにグルーピングされると、見出し文字の外接矩形のグループの中に見出し文字以外の外接矩形が属するため、見出し文字の抽出が正確にできなくなるので、外接矩形Ｋ５を見出し文字の矩形候補から除去する必要がある。

　そこで、本文文字を囲む枠の中には、本文文字が多数含まれているということに着目し、見出し文字の矩形候補として選択された外接矩形Ｋ１〜Ｋ５の中に含まれる本文文字サイズの外接矩形Ｋ６の個数を数える。

　この結果、外接矩形Ｋ５の中には、本文文字サイズの外接矩形Ｋ６が多数含まれており、外接矩形Ｋ１〜Ｋ４の中には、本文文字サイズの外接矩形が含まれていないので、本文文字サイズの外接矩形Ｋ６が多数含まれている外接矩形Ｋ５を見出し文字の矩形候補から除去することにより、見出し文字の矩形候補として外接矩形Ｋ１〜Ｋ４だけを正しく選択することが可能となる。

　次に、部分的重なりネスト統合を行う（ステップＳ５６）
　見出し矩形候補の中には、図や写真の一部からなる連結成分の外接矩形が含まれていることがあり、これらの外接矩形は他の正しい見出し矩形と統合されるなどして、悪影響のもとになる。そこで、これらの図や写真の一部からなる外接矩形は、より大きな矩形に吸収統合しておくことで、見出し矩形の抽出への悪影響を軽減しなければならない。一般に、図や写真の一部からなる矩形は、互いに重なっていることが多く、これらを見分ける目安となる。そこで、外接矩形の互いの重なり度を計算し、あるしきい値を越えるものを図や写真の一部から得られた外接矩形と判断し、その矩形に限り重なりネスト統合を行う。ここで、外接矩形の重なり度とは、外接矩形が他の外接矩形と何重に重なっているかを示す数である。

　図２４は、本発明の一実施例に係わる重なりネスト統合を説明する図である。
　図２４において、「画」という文字の連結成分を抽出した結果、２つの連結成分Ｒ１、Ｒ２が抽出され、連結成分Ｒ１の外接矩形Ｋ１１及び連結成分Ｒ２の外接矩形Ｋ１２が生成されたものとする。この外接矩形Ｋ１１、Ｋ１２に重なりネスト統合を行うと、外接矩形Ｋ１１、Ｋ１２を囲む外接矩形Ｋ１３が生成される。

　この結果、複数のストロークから構成される文字について、各ストロークごとに異なるラベルが付与された場合においても、１つの文字を構成する各ストロークを１つにまとめることができる。

　図２５は、本発明の一実施例に係わる部分的重なりネスト統合を説明する図である。
　図２５（ａ）において、外接矩形Ｋ２１〜Ｋ２６が生成されたものとする。ここで、例えば、外接矩形Ｋ２２については、外接矩形Ｋ２２は外接矩形Ｋ２１及び外接矩形Ｋ２３の２つの外接矩形と重なっているので、重なり度が２となる。また、外接矩形Ｋ２３については、外接矩形Ｋ２３は外接矩形Ｋ２２、外接矩形Ｋ２４〜Ｋ２６の４つの外接矩形と重なっているので、重なり度が４となる。

　ここで、例えば、重なり度が４以上の外接矩形だけについて、重なりネスト統合を行うものとすると、図２５（ｂ）に示すように、外接矩形Ｋ２２〜Ｋ２６を含む外接矩形Ｋ２７が生成され、外接矩形Ｋ２１と外接矩形Ｋ２７は統合されない。

　ここで、例えば、外接矩形Ｋ２１は見出し文字の外接矩形であり、外接矩形Ｋ２２〜Ｋ２６は背景の絵柄の外接矩形であるものとし、重なり度を考慮しないで重なりネスト統合を行うと、外接矩形Ｋ２１〜Ｋ２６は全て統合され、見出し文字の外接矩形が消失し、見出し文字の領域を抽出できなくなる。

　一方、重なりネスト統合を全く行わないようにすると、外接矩形Ｋ２１〜Ｋ２６はそれぞれ別個に存在し、見出し文字の背景の絵柄の外接矩形Ｋ２２〜Ｋ２６が見出し矩形候補として選択される場合が発生し、見出し文字の背景の絵柄の外接矩形Ｋ２２〜Ｋ２６が見出し矩形候補として選択される場合には、見出し文字の正確な抽出ができなくなる。

　そこで、重なりネスト統合の対象となる外接矩形Ｋ２１〜Ｋ２６を重なり度を用いて選別し、外接矩形Ｋ２２〜Ｋ２６のみを対象として重なりネスト統合を行うことにより、見出し文字の背景の絵柄の外接矩形Ｋ２２〜Ｋ２６を外接矩形Ｋ２７に吸収して、外接矩形Ｋ２２〜Ｋ２６が見出し矩形候補として選択されることを防止することが可能となるとともに、見出し文字の外接矩形Ｋ２１をそのまま残しておくことが可能となり、見出し文字の抽出精度を向上させることが可能となる。

　重なり度の具体的な計算は、以下のようにして行うことができる。
　まず、図２１に示した方法により、見出し矩形候補の射影テーブルを作成する。次に、見出し矩形候補について、１画素ずつ、ｘ座標軸の射影テーブルとｙ座標軸の射影テーブルとから見出し矩形の番号を参照することにより、重なり度を計算する。

　次に、矩形統合を行う（ステップＳ５７）。
　この矩形統合では、見出し矩形同士の統合が行われる。まず、注目する見出し矩形について近傍領域をとり、他の見出し矩形の中で一部がその近傍領域に含まれる見出し矩形を調べ上げる。そして、注目している見出し矩形が、その近傍領域内の見出し矩形と統合できるかどうかを判断する。この際、近傍領域の取り方及び統合条件は、縦書き用と横書き用の２つのケースに即した取り方及び条件で行う。

　図２６は、本発明の一実施例に係わる近傍矩形の例を示す図である。
　図２６において、外接矩形Ｋ３１〜Ｋ３６が生成されているものとし、外接矩形Ｋ３１を注目矩形として、近傍領域を設定するものとすると、外接矩形Ｋ３１の周囲の所定の範囲内に近傍領域Ｈ１が設定される。外接矩形Ｋ３１と矩形統合される外接矩形の候補として、近傍領域Ｈ１にかかる外接矩形Ｋ３２〜Ｋ３４が選択され、外接矩形Ｋ３５、Ｋ３６は、外接矩形Ｋ３１と矩形統合される外接矩形の候補から除かれる。

　図２７は、本発明の一実施例に係わる近傍統合処理を示すフローチャートである。
　図２７において、まず、矩形集合を入力し（ステップＳ８１）、矩形間のリンク張りを行う（ステップＳ８２）。矩形間のリンク張りでは、まず、注目矩形の近傍を設定し（ステップＳ９１）、注目矩形の近傍にかかる外接矩形を抽出することにより、注目矩形の近傍矩形を決定し（ステップＳ９２）、注目矩形と近傍矩形との位置関係、文字線太さ、または各矩形内の黒画素密度などを考慮することにより、注目矩形と近傍矩形との統合可否の決定を行う。そして、注目矩形と近傍矩形とが統合可とされたものについて、リンクを張る。

　次に、リンクでつながる極大矩形集合の抽出を行い（ステップＳ８３）、極大矩形集合に属する矩形を、ステップＳ８１で入力された矩形の集合から削除し、極大矩形集合の外接矩形を矩形集合に追加する（ステップＳ８４）。

　次に、重複矩形除去を行う（ステップＳ５８）。
　この重複矩形除去では、統合された見出し矩形の中で重複をさけるため、同一の矩形の一方を棄却する。

　図２８は、本発明の一実施例に係わる重複矩形の一例を示す図である。
　図２８において、外接矩形Ｋ４１、Ｋ４２が抽出され、外接矩形Ｋ４１を注目矩形として縦統合を行う場合、外接矩形Ｋ４１の周囲に近傍領域Ｈ１１が設定される。そして、近傍領域Ｈ１１にかかる外接矩形Ｋ４２が抽出され、外接矩形Ｋ４１と外接矩形Ｋ４２との統合が可能であると判定されると、外接矩形Ｋ４１、Ｋ４２を含む外接矩形Ｋ４３が生成される。

　一方、外接矩形Ｋ４１を注目矩形として横統合を行う場合、外接矩形Ｋ４１の周囲に近傍領域Ｈ１２が設定される。そして、近傍領域Ｈ１２にかかる外接矩形Ｋ４２が抽出され、外接矩形Ｋ４１と外接矩形Ｋ４２との統合が可能であると判定されると、外接矩形Ｋ４１、Ｋ４２を含む外接矩形Ｋ４３が生成される。

　この結果、全く同一の外接矩形Ｋ４３が重複して生成されるため、一方の外接矩形Ｋ４３を棄却する。
　次に、枠矩形のチェックを行う（ステップＳ５９）。

　この枠矩形のチェックでは、得られた見出し矩形について、再び、それが枠矩形かどうかの判断を射影テーブルを用いて行い、見出し矩形の中から枠矩形を除外する。
　次に、見出し矩形の得点づけを行う（ステップＳ６０）。この見出し矩形の得点づけでは、得られた見出し矩形について、その大きさ及び形状から得点を付与する。

　図２９は、本発明の一実施例に係わる見出し矩形の得点付け方法を説明する図である。
　図２９において、外接矩形Ｋ５１が生成され、その外接矩形Ｋ５１の横方向の長さをｄｘ、縦方向の長さをｄｙとすると、この外接矩形Ｋ５１についての得点は、以下の式で与えられる。

　得点＝（１＋α×ｒａｔｉｏ）×（ｄｘ×ｄｙ）
　ｒａｔｉｏ＝ｍａｘ（ｄｘ、ｄｙ）／ｍｉｎ（ｄｘ、ｄｙ）
　ここで、αはパラメータである。

　この得点を算出することにより、見出し文字から構成されるタイトルが、１つの文書画像から複数得られた場合、それらのタイトルに優先順位を付けて出力することができる。

本発明の第１実施例に係わるパターン抽出装置の構成を示すブロック図である。 本発明の第２実施例に係わるパターン抽出装置の構成を示すブロック図である。 本発明の一実施例に係わるパターン抽出装置のシステム構成を示すブロック図である。 本発明の第３実施例に係わる文字列抽出装置の動作を説明する図である。 本発明の第３実施例に係わる文字列抽出装置の構成を示すブロック図である。 本発明の第３実施例に係わる文字列抽出装置の動作を示すフローチャートである。 本発明の一実施例に係わるラベリング処理を説明する図である。 本発明の一実施例に係わるグルーピング処理を示すフローチャートである。 本発明の一実施例に係わる連結成分と外接矩形の例を示す図である。 本発明の一実施例に係わる対象連結成分の絞り込み方法を示すフローチャートである。 本発明の一実施例に係わる連結成分近傍を説明する図である。 本発明の一実施例に係わる連結成分の家族的類似性を説明する図である。 本発明の一実施例に係わるグループの文字認識度の算出方法を説明する図である。 本発明の一実施例に係わる連合グラフとクリークを示す図である。 本発明の一実施例に係わる連結成分の重なりのないグループの抽出方法を示すフローチャートである。 本発明の一実施例に係わる連結成分同士のリンク付けの方法を説明する図である。 本発明の一実施例に係わるクリークとなるグループとクリークとならないグループの例を示す図である。 本発明の一実施例に係わる組合せの評価値の算出方法を示す図である。 本発明の第４実施例に係わるパターン抽出装置の動作を示すフローチャートである。 本発明の一実施例に係わる外接矩形の大きさを求めるためのヒストグラムの一例を示す図である。 本発明の一実施例に係わる矩形番号の射影テーブルの一例を示す図である。 本発明の一実施例に係わる見出し矩形候補の選択方法を示すフローチャートである。 本発明の一実施例に係わる枠矩形のチェック方法を説明する図である。 本発明の一実施例に係わる重なりネスト統合を説明する図である。 本発明の一実施例に係わる部分的重なりネスト統合を説明する図である。 本発明の一実施例に係わる近傍矩形の例を示す図である。 本発明の一実施例に係わる近傍統合処理を示すフローチャートである。 本発明の一実施例に係わる重複矩形の一例を示す図である。 本発明の一実施例に係わる見出し矩形の得点付け方法を説明する図である。 従来の重なりネスト統合により文書全体の矩形が統合される例を示す図である。

符号の説明

１　反転画像生成手段
　２　認識手段
　３　出力手段
　１１　連結成分抽出手段
　１２　外接矩形生成手段
　１３　重なり度評価手段
　１４　重なりネスト処理手段
２１　ＣＰＵ
　２２　ＲＯＭ
　２３　ＲＡＭ
　２４　通信インターフェース
　２５　通信ネットワーク
　２６　バス
　２７　入出力インターフェース
　２８　ディスプレイ
　２９　プリンタ
　３０　メモリ
　３１　スキャナ
　３２　キーボード
　３３　ドライバ
　３４　ハードディスク
　３５　ＩＣメモリカード
　３６　磁気テープ
　３７　フレキシブルディスク
　３８　光ディスク
　４１　文字列抽出装置
　４２　連結成分抽出手段
　４３　グルーピング手段
　４４　文字認識手段
　４５　組合せ評価手段
　４６　文字列抽出手段

Claims (7)

1. 　入力画像の連結成分を抽出する連結成分抽出手段と、
   　前記連結成分の外接矩形を生成する外接矩形生成手段と、
   　前記外接矩形の頻度を前記外接矩形の面積で重み付けたヒストグラムを生成するヒストグラム生成手段と、
   　前記ヒストグラムの最大値を示す外接矩形の大きさを、前記入力画像の文字サイズと推定する文字サイズ推定手段とを備えることを特徴とするパターン抽出装置。
2. 　前記外接矩形生成手段で生成された外接矩形のグルーピングを行うグルーピング手段と、
   　前記文字サイズ推定手段で推定された文字サイズを有する第１の外接矩形を所定の個数以上含む第２の外接矩形を抽出する枠矩形抽出手段と、
   　前記第２の外接矩形を前記グルーピングの対象から除外する枠矩形除外手段とを備えることを特徴とする請求項６に記載のパターン抽出装置。
3. 　前記外接矩形に与えられた矩形番号を前記入力画像に設定された各座標に射影する射影手段を備え、
   　前記枠矩形抽出手段は、前記各座標に含まれる矩形番号を前記第２の外接矩形の座標の範囲内で探索することにより、第１の外接矩形を抽出することを特徴とする請求項７に記載のパターン抽出装置。
4. 　入力画像の連結成分を抽出する連結成分抽出手段と、
   　前記連結成分の外接矩形を生成する外接矩形生成手段と、
   　前記外接矩形が互いに重なっている他の外接矩形の個数を算出する重なり度評価手段と、
   　前記重なり度評価手段の算出結果に基づいて、重なりネスト統合処理を行う重なりネスト統合処理手段とを備えることを特徴とするパターン抽出装置。
5. 　前記外接矩形に付与された矩形番号を、前記入力画像に設定された各座標に射影する射影手段と、
   　前記各座標に含まれる矩形番号を所定の外接矩形の座標の範囲内で探索することにより、前記所定の外接矩形に重なっている他の外接矩形を抽出する重なり矩形抽出手段とを備えることを特徴とする請求項９に記載のパターン抽出装置。
6. 　入力画像の連結成分の外接矩形の重なり度に基づいて、重なりネスト統合処理を部分的に行うことを特徴とするパターン抽出方法。
7. 　入力画像の連結成分を抽出する機能と、
   　前記連結成分の外接矩形を生成する機能と、
   　前記外接矩形が互いに重なっている他の外接矩形の個数を算出する機能と、
   　前記算出された個数に基づいて、重なりネスト統合処理を行う機能とをコンピュータに実行させるプログラムを格納したコンピュータ読み取り可能な記憶媒体。

Images