(57)【要約】【課題】文書画像から図表領域の検出と図表領域間の類似度の判定を、高精度かつ効率よく行える図表領域検出装置、および図表領域検出方法を提供すること。【解決手段】実施形態の図表領域検出装置は、文書を読み取るスキャナ部と、前記スキャナ部で読み取った文書画像データの画素値を２値化し、連結可能な画素領域を分割領域として抽出する分割領域抽出部と、前記分割領域が非文字列領域であるかどうか否かを判定する非文字領域判定部と、非文字領域と判定された分割領域に含まれる線素群を求め、各線素群の統計量を用いて分割領域の特徴量を算出する特徴量算出部と、前記特徴量を用いて、前記分割領域が図表領域であるか否かを判定する図表領域判定部と、２つの図表領域の特徴量の相関に基づいて図表領域内に含まれる図表の類似度を判定する図表類似度判定部と、を有する。【選択図】図２
2015099536.tif 000002
【特許請求の範囲】
【請求項１】
文書を読み取るスキャナ部と、
前記スキャナ部で読み取った文書画像データの画素値を２値化し、連結可能な画素領域を分割領域として抽出する分割領域抽出部と、
前記分割領域が非文字列領域であるかどうか否かを判定する非文字領域判定部と、
非文字領域と判定された分割領域に含まれる線素群を求め、各線素群の統計量を用いて分割領域の特徴量を算出する特徴量算出部と、
前記特徴量を用いて、前記分割領域が図表領域であるか否かを判定する図表領域判定部と、
２つの図表領域の特徴量の相関に基づいて図表領域内に含まれる図表の類似度を判定する図表類似度判定部と、
を有する図表領域検出装置。
【請求項２】
複数の前記文書に対して、各文書に含まれる前記図表領域を少なくとも前記特徴量と関連付けてデータベースに登録する特徴量テーブル保存部と、
検索画像を入力する検索画像入力部と、を更に有し、
前記特徴量算出部は、前記検索画像の特徴量を算出し、
前記図表類似度判定部は、更に前記データベースから前記検索画像の特徴量と相関の高い図表領域を検索し、その図表領域を含む文書を提示する請求項１記載の図表領域検出装置。
【請求項３】
前記特徴量に応じて前記図表領域と判定された分割領域が属するクラスタを算出する図表領域分類部を更に有し、
前記特徴量テーブル保存部は、更に前記分割領域に対するクラスタを前記データベースに保存し、
前記図表類似度判定部は、前記データベースから前記検索画像の特徴量と相関の高い図表領域を検索し、更にその図表領域が属するクラスタに含まれる文書を提示する請求項２記載の図表領域検出装置。
【請求項４】
前記特徴量は、各線素群の統計量をベクトルとして記述した特徴量ベクトルである請求項１記載の図表領域検出装置。
【請求項５】
前記相関は、２つの図表領域の特徴量ベクトル間の距離を定義する非線形ベクトル関数により算出される請求項１記載の図表領域検出装置。
【請求項６】
スキャナで読み取った文書画像データの画素値を２値化し、連結可能な画素領域を分割領域として抽出するステップと、
前記分割領域が非文字列領域であるかどうか否かを判定するステップと、
非文字領域と判定された分割領域に含まれる線素群を求め、各線素群の統計量を用いて分割領域の特徴量を算出するステップと、
前記特徴量を用いて、前記分割領域が図表領域であるか否かを判定するステップと、
２つの図表領域の特徴量の相関に基づいて図表領域内に含まれる図表の類似度を判定するステップと、
を有する図表領域検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、文書画像の内容を解析し、図表領域の検出、図表の分類・検索などを行う図形領域検出装置および図形領域検出方法に関する。
【背景技術】
【０００２】
従来、文書画像は紙の媒体を中心に扱われていたが、情報処理のハードウエア、ソフトウエアの発達に伴い、パーソナルコンピュータなどで文書画像を直接電子的に作成、処理し、紙媒体を出力せずに保存できる環境が増えてきている。また、紙ベースで作成された文書画像をスキャナなどで電子化しアーカイブとして利用することも多い。
【０００３】
これにより、大量に電子化されて保存される文書画像を簡易に検索する要望が高まっている。現在は、文書検索のキーとしてテキスト情報（いわゆるキーワード）を用いるのが主流であるが、通常文書内にはテキスト情報だけでなく、写真や図表なども含まれているため、これらを写真や図表をキーとした検索も望まれている。
【０００４】
従来、テキスト以外をキーとする文書検索方法として、例えば文書画像のマクロな構造の形状を示す特徴量を比較して類似の画像を検索する方法（特許文献１参照）が提案されている。また、画像のエッジ方向の分布の特徴の違いを用いて類似の画像を検索するＨＯＧ（Histograms of Oriented Gradients）方式（非特許文献１参照）、領域のサイズとその領域を構成する色の分布の多峰性を利用して図表領域を抽出する方法（特許文献２参照）などが提案されている。
【０００５】
非特許文献１では、画像のミクロなエッジ構造のマクロな領域での分布から画像の類似性を判定する。しかし固有のテキスチャをもたない人工的な構成の文書画像では判定精度、効率の両面で必ずしも適さない。また、文字間の空白部の形状の特徴から類似の画像を検出するため、行間をもつテキスト文書の類似判定には向いているが、いろいろな図形要素が不規則な位置に構成される図表の類似判定には適していない。
【０００６】
また、特許文献１は文書画像を構成する文字間の空白部の形状の特徴から類似の画像を検出する。行間をもつテキスト文書の類似判定には向いているが、いろいろな図形要素が不規則な位置に構成される図表の類似判定には適していない。
【０００７】
特許文献２は、領域のサイズや限られた種類の色しか使われてないという情報を利用し、図表領域かどうかを判定するが、処理演算が煩雑であるという問題がある。また、この方法では図表か否かの判定しかできず、図表の類似度判定や分類などの処理を行うには別の方法を用いる必要がある。上記文献以外にも多くの画像の類似判定の方式が提案されているが、図表画像の類似度を判定する有効な方式は提案されていないという問題がある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−２０８８８号公報
【特許文献２】特開２００７−３３６０００号公報
【非特許文献１】「動的な背景の中から人物だけを検出する画像認識技術」東芝レビューVol65,No6,pp60-61
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明が解決しようとする課題は、上記問題などを解決し、文書画像から図表領域の検出と図表領域間の類似度の判定を高精度かつ効率よく行える図表領域検出装置、および図表領域検出方法を提供することである。
【課題を解決するための手段】
【００１０】
上記課題を達成するために、実施形態の図表領域検出装置は、文書を読み取るスキャナ部と、前記スキャナ部で読み取った文書画像データの画素値を２値化し、連結可能な画素領域を分割領域として抽出する分割領域抽出部と、前記分割領域が非文字列領域であるかどうか否かを判定する非文字領域判定部と、非文字領域と判定された分割領域に含まれる線素群を求め、各線素群の統計量を用いて分割領域の特徴量を算出する特徴量算出部と、前記特徴量を用いて、前記分割領域が図表領域であるか否かを判定する図表領域判定部と、２つの図表領域の特徴量の相関に基づいて図表領域内に含まれる図表の類似度を判定する図表類似度判定部と、を有する。
【００１１】
また、実施形態の図表領域検出方法は、スキャナで読み取った文書画像データの画素値を２値化し、連結可能な画素領域を分割領域として抽出するステップと、前記分割領域が非文字列領域であるかどうか否かを判定するステップと、非文字領域と判定された分割領域に含まれる線素群を求め、各線素群の統計量を用いて分割領域の特徴量を算出するステップと、前記特徴量を用いて、前記分割領域が図表領域であるか否かを判定するステップと、２つの図表領域の特徴量の相関に基づいて図表領域内に含まれる図表の類似度を判定するステップと、を有する。
【図面の簡単な説明】
【００１２】
【図１】本実施形態における図表領域検出装置の全体ブロック図。
【図２】同実施形態における図表領域検出装置の機能ブロック図。
【図３】同実施形態におけるデータベースへの図表登録処理を示すフローチャート図。
【図４】同実施形態における文書画像の例。
【図５】同実施形態における文書画像に対する分割領域抽出例。
【図６】同実施形態における特徴量ベクトルの算出を示すフローチャート図。
【図７】同実施形態における特徴量ベクトルで形成される特徴量空間の説明図。
【図８】同実施形態における図表特徴量テーブルの例。
【図９】同実施形態における検索処理を示すフローチャート図。
【発明を実施するための形態】
【００１３】
本発明の図形領域検出装置および検出方法は、例えば、コンピュータを内蔵する装置にインストールまたは組み込んで使用するための図表検索ソフトウエア（またはファームウエア）、およびこの図表検索ソフトウエアをインストールしたコンピュータ装置、および文書を電子記録メディアあるいはマイクロフィルムに保存するドキュメントアーカイブ装置などを含んでいる。また、図表検索ソフトウエアで構成される機能の一部をハードウエアで実現してもよい。以下、実施形態について図１から図９を参照しながら詳細に説明する。
【００１４】
本実施形態に係る図表領域検出装置の全体ブロック図を図１に示す。図表領域検出装置１は、一般的なノイマン型計算機と同様のハードウエア構成であり、ＣＰＵ１１、メモリ１２、ＨＤＤ（Hard Disk Drive）１３、スキャナ１４、コンソール１５、ＮＩＣ（Network Interface Card）１６よりなり、これらがシステムバス１７を介して接続されている。
【００１５】
また、システムバス１７はＮＩＣ１６を介して外部のネットワーク１８に接続し、外部のＰＣ（Personal Computer）端末１９から図表領域検出装置１を制御できる。またスキャナ１４は、図表領域検出装置１の外部に直接接続、または任意のネットワークを介して接続されていてもよい。
【００１６】
ここで図表領域検出装置１の機能は、原則として図１に示すハードウエア構成とソフトウエアによって形成されるものとする。すなわち、図表領域検出ソフトウエアをメモリ１２上に展開し、ＣＰＵ１１上で実行することで図２の機能ブロックが形成される。図２の機能ブロックの説明については後述する。また、文書画像から抽出した図表領域はデータベースを構成するが、このデータベースおよびその管理情報は、ＨＤＤ１３に格納されるものとする。機能ブロックの処理に応じて必要な文書画像や処理情報がメモリ１２にロードされて各種図表処理に用いられる。
【００１７】
また、電源起動時のプログラムの起動やメンテナンスなどは管理者がコンソール１５を介して行う。ユーザからのデータベースへの図表登録や検索・閲覧は、通常外部のユーザのＰＣ端末１９より外部のネットワーク１８、ＮＩＣ１６を介して行われるが、直接コンソール１５からの操作も可能である。その場合はスキャナ１４より文書画像を読み込んでデータベースへの登録することもできる。
【００１８】
図２は、機能ブロックの構成図である。本実施形態の図表領域検出装置１は、文書画像を読み込むためのスキャナ部２１、類似図表を検索するためキー画像を入力するための検索画像入力部２２、スキャナ部２１で読み取った文書画像に対して、テキスト領域、図形領域などの処理領域に分割するために、この分割可能な処理領域（以下、分割領域と称する）を抽出する分割領域抽出部２３、抽出した分割領域が文字領域か非文字領域かを判定する非文字領域判定部２４、非文字領域に対して図表の特徴を示す特徴量を算出する特徴量算出部２５、図表の特徴量に応じて図表領域か非図表領域（例えば写真など）かを判定する図表領域判定部２６、図表領域の特徴量から図表をクラスタに分類する図表領域分類部２７、文書画像の図表領域を特徴量やクラスタと関連づけてデータベースに保存する特徴量テーブル保存部２８、検索画像入力部２２から入力されたキー画像に対して特徴量テーブル保存部２８から類似度の高い図表を判定し検索する図表類似度判定部２９の機能ブロックを有している。
【００１９】
スキャナ部２１は、紙ベースの文書画像であればハードウエア（スキャナ機器）で画素値を読み取ってもよいし、ＮＩＣ１６を経由して取得した電子文書画像であれば、ソフトウエアで画素値を読み取ってもよい。また検索画像入力部２２も同様であり、スキャナ機器で読み取ってもよいし、電子文書画像に対してソフトウエアで読み取ってもよい。また、検索のキー画像は、検索したい図表そのものだけでなく、文書全体を読み取っても構わない。特徴量テーブル保存部２８のデータベースは、ＨＤＤ１３に保存される。
【００２０】
図表領域検出装置１は、大きく分けて２つの処理動作があり、多数の文書画像の図表をデータベースに登録する登録処理と、このデータベースからキー画像に類似する図表を含む文書を検索する検索処理がある。
【００２１】
（登録処理）
まず、登録処理について説明する。図３は、データベースへの図表登録処理を示すフローチャート図である。
【００２２】
ステップＳＴ３０１では、文書画像に対して分割領域の抽出を行う。まず、登録したい文書画像をスキャナ部２１で読み取る。文書画像がＲＧＢ成分などで表されるカラー画像を含む場合は、文書全体をモノクロ画像に変換する。このモノクロ画像を所定の閾値で２値化し、閾値より輝度の低い（すなわち暗い画素）を黒画素、輝度の高い画素を白画素とする。ここで表記上は黒画素の画素値は「１」、白画素の画素値は「０」とする。
【００２３】
次に、黒画素で互いに隣接する画素を連結することで連結領域を抽出する。ここでは説明の便宜上、この連結領域を単位領域と呼ぶことにする。さらに互いに近くにある単位領域同士を互いに結合して１つの連結領域とする。この操作を連結領域または単位領域同士で繰り返し、それ以上結合できなくなった時点の連結領域を最終的な領域とし、この連結領域を分割領域と定義する。
【００２４】
ステップＳＴ３０２では、ステップＳＴ３０１で抽出した分割領域それぞれが文字列領域であるか、非文字領域であるかの判定を行う。それぞれの分割領域についてそこに含まれる単位領域のサイズや配置を調べ、その領域が文字列領域であるかどうかを判定する。
【００２５】
例えば、単位領域のサイズが所定閾値以下であり、それらが複数の直線上に配置されている時、それぞれの単位領域は文字である可能性が高いため文字列領域と判定する。それ以外の場合は非文字列領域と判定する等である。通常、文字列領域は行構成または列構成となる文字列より構成される領域である。一方非文字列領域は図表や写真などの領域となる。
【００２６】
図４に示す文書画像より分割領域を抽出した結果の例を図５示す。図４の文書画像４１は本文やタイトルよりなる文字列、図表、顔写真よりなっている。図５で破線の矩形枠で囲まれた部分が抽出された領域を示す。この例では４つの領域５１〜５４が抽出される。
【００２７】
符号５１、５２が文字列領域、符号５３、５４が非文字列領域と判定される。
【００２８】
ステップＳＴ３０３では、非文字領域の特徴量を計算する。ここで図６に特徴量の計算処理のフローチャートを示す。図表領域は主に直線や曲線、文字などから成り立っており、曲線は円や楕円が多く用いられる。したがって、これらの線成分が多く含まれている領域は図表領域と考えられ、またその線成分の特徴や発生頻度の分布が近い２つの領域は類似した図表領域と考えられる。そこで、非文字領域内の縦横方向の線分、縦横以外の線分、円弧の線素および文字を抽出し、これら各線素、文字の個数や長さなどの統計量を特徴量として計算する。
【００２９】
（ステップＳＴ６０１）まず、該当分割領域の注目画素の座標を（ｘ，ｙ）とし、その２値化画像値をＰ１（ｘ，ｙ）とする。この該当領域内の注目画素に対し式（１）で示すエッジ抽出処理を行い、その結果をエッジ画像Ｐ２（ｘ，ｙ）とする。
【数１】
2015099536.tif 000003
【００３０】
ただし、^ は排他的論理和、|  は論理和演算を表す。
【００３１】
このエッジ抽出処理では、注目画素の座標（ｘ，ｙ）の上下左右に隣接する周囲４画素をみて、４画素のいずかが注目画素と異なる値ならばエッジ画素、４画素ともすべて注目画素と同じ値であれば非エッジ画素と判定する。便宜上エッジ画素は黒画素（画素値１）、非エッジ画素は白画素（画素値０）と呼ぶことにし、式（１）上の画素値Ｐ２（ｘ，ｙ）はそれぞれ１，０とみなすこととする。このエッジ抽出処理の目的は、図表上の塗りつぶし領域でも境界が線分や円弧の形状であれば線分として抽出するためである。
【００３２】
（ステップＳＴ６０２）つぎに、線分の抽出を行う。ここでは線分の抽出にＨｏｕｇｈ変換を用いる。すなわち、エッジ画像の黒画素の点すなわちＰ２（ｘ，ｙ）＝１となる（ｘ，ｙ）に位置する画素ついて、式（２）の関数Ｒ（θ）を定義し、０≦θ＜πの範囲を動くθについてθ−ｒ空間上の座標（θ，Ｒ（θ））の点にプロットし、これを領域内のすべての黒画素について重ね合わせ、その結果をＱ（θ，ｒ）とする。
【数２】
2015099536.tif 000004
【００３３】
ただし、δはデルタ関数である。
【００３４】
画像上で傾きθ、原点からの距離がｒである直線 ｘｃｏｓθ+ ｙｓｉｎθ＝ｒ 上の点は、θ−ｒ空間上ではすべて（θ，ｒ）を通る。このため、このような直線またはその一部の線分が画像上に存在すればＱ（θ，ｒ）は座標点（θ，ｒ）でピークをとる。したがってＱ（θ，ｒ）の極大点は該当領域内の線分に対応する。
【００３５】
（ステップＳＴ６０３）ここでは線分の分類を行うために、所定の基準により極大点を選別する。選別基準としてはピークの値が所定以上であること、近傍の他の極大点が所定距離以上離れていること、などを用いる。選別した極大点の（θ，ｒ）の組を（θｋ，ｒｋ）とする（１≦ｋ≦Ｎ、Ｎは選別された極大点の個数）。そして選別された各極大点について対応する領域内の線分を求める。θｋ，ｒｋの値より直線の式を求める。線分・線素はこの直線の一部となるので、求めた直線の式とエッジ画像の連結する黒画素の点より線分の端点を求める。そしてこの線分の長さ、傾き角度、中心位置を求める。ここで線分の長さが所定閾値以下の場合は線素ではないと判定する。これは短い線素はノイズや文字の一部などの可能性が高いためである。
【００３６】
つぎに傾き角度と線分の長さの値により、縦横線分かそれ以外の線分かに分類する。すなわち、傾き角度が０またはπ／２にほぼ等しくかつ、長さが所定の閾値より大きい場合には縦横線とし、それ以外の場合は縦横以外の線とする。一般的な図表では、表の罫線やグラフの軸、囲み枠などは縦横線で形成されているが、それ以外の傾きを有する線分の場合は、縦横線と異なった意味合いをもっている場合が多いので、縦横線と縦横線以外とは異なる分類とする。
【００３７】
（ステップＳＴ６０４）抽出されたすべての線分について上記の処理が完了したら、該当領域全体に対するすべての縦横線についての特徴量を求める。これは、すべての縦横線について縦線の本数、横線の本数、長さの平均値、分散、中心位置のｘ座標、ｙ座標の平均値および分散の計８つの値を計算する。
【００３８】
（ステップＳＴ６０５）つぎに縦横以外の線の特徴量を求める。該当領域全体に対するすべて縦横以外の線について、その本数、長さの平均値、分散、中心位置のｘ座標、ｙ座標の平均値および分散の７つの値を計算する。
【００３９】
なお、本実施形態ではエッジ画像のみから線分を抽出しているが、ある程度の太さの線分ではエッジ画像は線分の両側に２本生じてしまう可能性がある。この場合、Ｈｏｕｇｈ変換で極大ピークがぼけたりする場合や、近傍に２個のピークが生じる場合などにより正しく線分を抽出できない可能性がある。このため、エッジ処理画像だけでなくエッジ抽出前の２値化画像にも同様にＨｏｕｇｈ変換以降の同様の処理をかけて線分を求め、これも抽出線分に含めればよい。
【００４０】
（ステップＳＴ６０６）つぎに円弧の抽出を行う。円弧の抽出には式（３）に示す一般化Ｈｏｕｇｈ変換を用いる。式（３）に基づき、Ｑ２（ｕ，ｖ，ｒ）を計算する。すなわち、エッジ画像の黒画素Ｐ２（ｘ，ｙ）＝１に対してｕ，ｖを変化させてｕ，ｖ，ｒ＝Ｒ（ｕ，ｖ）を３軸とする３次元空間上にプロットし、すべての黒画素について重ね合わせる。Ｑ２（ｕ，ｖ，ｒ）が極大となれば、（ｕ，ｖ）を中心とする半径ｒの円成分があることになる。
【００４１】
ステップＳＴ６０２の線分抽出と同様に所定の条件で極大点を選別し、得られたｕ，ｖ，ｒの組に対応する円を求め、円上に重なる連結する黒画素が円弧となる。得られた円弧に対して、円弧の中心角、半径、円の中心の座標を求める。また、本実施形態では円についてのみ記述したが、楕円などの他の図形についても一般化Ｈｏｕｇｈ変換により同様な処理が行える。
【数３】
2015099536.tif 000005
【００４２】
（ステップＳＴ６０７）該当領域内のすべての円弧について、円弧の中心角、半径、円の中心の座標の値を求めた後、線分の場合と同様にこれらの統計量を計算する。すなわち、円弧の個数、円弧中心角の平均値、分散、半径の平均値、分散、中心位置のｘ座標およびｙ座標の平均値および分散の９つの値を計算する。
【００４３】
（ステップＳＴ６０８）つぎに文字の抽出を行う。ステップＳＴ３０１での文字抽出と同様な手順によって非文字領域内に存在する文字情報を抽出する。
【００４４】
（ステップＳＴ６０９）そして、それぞれの文字について中心位置とサイズを求めた後、すべての文字についてその個数、中心位置のｘ座標、ｙ座標の平均値および分散、ｘ方向およびｙ方向のサイズの平均値および分散の計９つの値を計算する。
【００４５】
（ステップＳＴ６１０）以上の処理により、該当領域のそれぞれについて縦横線で８、縦横以外の線で７、円弧で９、文字で９の計３３の値の組が求まる。これらの値の組をこの領域の線素特徴量ベクトルｔと定義する。本実施形態では線素特徴量ベクトルｔは３３次元のベクトルとなる。以下、線素特徴量ベクトルを特徴量ベクトルと称する。
【００４６】
図３に戻り、ステップＳＴ３０４では、図表領域の判定を行う。ここでは非文字領域に対してステップＳＴ３０３で得られた特徴量ベクトルを用いて、この領域が図表領域であるかそれ以外の領域、例えば写真領域であるかの判定を行う。ここでは特徴量ベクトルtを変数とする判定関数ｆ（ｔ）の正負により判定する。
【００４７】
図７は、特徴量ベクトルで形成される特徴量空間の説明図である。紙面での説明の便宜上、多次元の特徴量ベクトル（本実施形態では３３次元）を２次元で表現する。外枠７０１が特徴量空間を表し、破線が図表判別境界線７０２、すなわち判定関数ｆ（ｔ）＝０となる線を表している。図表判別境界線７０２の左側のｆ（ｔ）＞０となる領域が図表領域を表し、図表判別境界線７０２の右側のｆ（ｔ）＜０となる領域が非図表領域を表している。
【００４８】
また、×印は特徴量ベクトルの特徴量空間上の位置を表す。例えば、ある非文字領域の線素特徴ベクトルｔ１の位置が図の７１１とするとｆ（ｔ１）＞０となり、この分割領域は図表領域と判定される。特徴量ベクトルｔ２が図の７１２にある場合は、ｆ（ｔ２）＜０となるためこの領域は図表領域ではないと判定される。
【００４９】
判定関数ｆ（ｔ）はその特徴量の意味合いを考慮し、手動で作成してもよいし、事前に複数の図表領域と非図表領域のサンプルを用意しておき、機械学習により決定してもよい。例えば、機械学習方式としてはＳＶＭ（サポートベクタマシン）が適当である。
【００５０】
ステップＳＴ３０５では、図表領域の分類を行う。上述の特徴量ベクトルを用いて図表領域をクラスタリングする。データベース内の図表はその類似性にしたがい複数のクラスタのいずれかに分類されており、分類結果は後述する特徴量テーブルに記録される。原理的には、新たに抽出された図表領域も含めデータベース上にあるすべての図表領域について、その特徴量ベクトルが近いもの同士が同じクラスタになるように分類する。分類方法としてはＫ平均法を用いることができる。
【００５１】
ここで図７の特徴量空間の説明図を用いてクラスタの例を示す。３つのクラスタ７２１、７２２、７１３が点線の閉曲線で示されている。特徴量ベクトルの特徴量空間上の位置（×印）が同じ閉曲線に含まれる場合に同じクラスタに属すると定義する。
【００５２】
ただし、新たな文書画像の登録ごとにクラスタリングをやり直すのは計算量が大きく効率が良くない。このため最初のクラスタリングの後、所定の時間間隔で間欠的に行う方法も考えられる。この場合、通常の登録時はすでに登録されている図表領域データのうち、登録する図表と最小の類似度となる図表領域データを探し、この類似度最小となる図表データの属するクラスタをあらたに登録する図表のクラスタとすればよい。これにより、クラスタリングの計算量を低減することができる。最小類似度の図表データの探索については検索処理の項で説明するが、この場合は図表類似度判定部２９と連携して処理を行う。
【００５３】
ステップＳＴ３０６では図表特徴量テーブルへの登録を行う。まずステップＳＴ３０４で図表領域と判定された領域にデータベース内でユニークなＩＤを割当てる。これを図表ＩＤと定義する。そして図表ＩＤ、図表の含まれる文書（文書ＩＤ）や文書上のページ内位置情報、領域サイズ、ステップＳＴ３０３で計算した特徴量ベクトル、ステップＳＴ３０５求めたクラスタ情報などを１レコードとして図表特徴量テーブルに追加する。
【００５４】
ここで図８に図表特徴量テーブルの例を示す。図表特徴量テーブルはデータベース上のすべての文書に含まれるすべての図表領域に対して、図表ＩＤ、その図表を含む文書のＩＤ、図表の含まれるページ、ページ上の図表領域の位置、サイズ、特徴量ベクトル、特徴量ベクトルが属するクラスタ番号などを記述したものである。なお、図８では、非線形ベクトル関数の項が追加されているが、非線形ベクトル関数については検索処理の項で後述する。
【００５５】
例えば１行目のレコードについては、図表ＩＤ１００１の図表が、文書ＩＤ２００１の文書の１ページ目に含まれており、その領域の左上の位置の座標は（１００，１２０）で領域のサイズは横４００、縦３００画素であり、この領域の特徴量は１０，３，４，…（４番目以降は表示を省略）であることを示している。
【００５６】
同様に２，３行目のレコードは、文書ＩＤ２００５の文書の１ページと２ページにそれぞれ図表ＩＤ１００２、図表１００３の図表があり、それらの図表の位置、サイズ、特徴量が格納されている。また４、５、６行目では文書ＩＤ２００６の４ページに図表ＩＤが１００４、１００５、１００６の３枚の図表があることを示している。以上のステップＳＴ３０１〜ＳＴ３０６により登録処理が終了する。
【００５７】
以上述べた登録処理は、線素の特性に基づいた特徴量ベクトルにより、図表であるか否かの判定、および図表のクラスタリングを行っている。すなわち、図表の主要な構成要素である線素の性質を用いている。このため、「縦横線分のみよりなる棒グラフ」、「縦横以外の線から構成される折れ線グラフ」、「円弧成分の多い円グラフの違い」、「長い縦横線よりなる罫線が多く含まれる表と、短い線よりなるグラフの違い」などを判別することが可能であり、図表に対して高精度な判定や分類を行うことができる。
【００５８】
また、図表には多数の線素が含まれるが、これらのすべての特性を個々に特徴量として持つと特徴量の次元が膨大になる。また図表により線素の数が異なるが、線素の数が非常に多い図表の場合、固定長のデータ構造では限られた線素の情報しか扱えない場合もある。この場合、図表領域全体の特性を表現することが難しくなる。本実施形態では特徴量そのものではなく、線素全体の平均値などの統計量を用いるため特徴量の次元数を小さくできる。このため、図表判定の計算量を小さくできる。また、同じ特徴量を用いて、図表領域か否かの判定と、後述する類似度の判定を行えるため、特徴量の計算量を少なくできる。従って本実施形態では、高精度かつ高速な登録処理を行うことができる。
【００５９】
（検索処理）
図９に検索処理のフローチャートを示す。ここではデータベースに登録されている文書から類似図表を持つ文書を検索するフローについて説明する。
【００６０】
ステップＳＴ９０１では検索のためのキー画像（検索キーとなる図表画像）の入力を行う。類似図表検索の場合、ユーザは、ＰＣ端末１９よりキー画像を図表領域検出装置１に送信する。そして図表領域検出装置１の検索画像入力部２２にキー画像が入力される。キー画像がビットマップ画像の場合はそのまま読込み、ページ記述言語で記述されている文書の場合は、ＲＩＰ処理（Raster Image Processor）などを通してビットマップ画像に展開する。なおこの時、ページ記述言語のファイルも保存しておくことが好ましい。
【００６１】
ステップＳＴ９０２〜ＳＴ９０３では、領域抽出、文字領域の判定を行う。このステップは登録処理のステップＳＴ３０１とステップＳＴ３０２と同様であるため詳細説明を省略する。またキー画像については図表と分かっていることが多いため、図表と分かっている場合には、このステップは省略してもよい。
【００６２】
ステップＳＴ９０４〜ＳＴ９０５では、特徴量ベクトルの算出、図表領域判定を行う。これらの処理も登録処理のステップＳＴ３０３、ステップＳＴ３０４と同じ処理であるので詳細説明を省略する。
【００６３】
ステップＳＴ９０６では特徴量テーブルを参照し、図表の類似度検索を行う。ここではステップＳＴ９０４で計算したキー画像の特徴量ベクトルと、特徴量テーブル保存部２８に格納されるデータベースを参照して、類似の図表画像を検索する。具体的にはデータベースに登録されているすべての図表の特徴量ベクトルとキー画像の特徴量ベクトルの距離Ｌを計算し、その距離Ｌが最小となる画像を類似画像とする。または、キー画像の特徴量ベクトルがどのクラスタに属するかを最初に判定し、そのクラスタ内のすべての図表の特徴量ベクトルとキー画像の特徴量ベクトルの距離Ｌが最小となる画像を求めてもよい。この場合、クラスタ中心位置からの距離などによりクラスタを定義しておくとよい。
【００６４】
通常、図表間の類似度と特徴量ベクトル間の単純なユークリッド距離は一般的に相関が低いので、ここでは特徴量ベクトルｔ１、ｔ２の距離Ｌは式（４）を用いて計算する。
【数４】
2015099536.tif 000006
【００６５】
ここで、φ（ｔ）は、特徴量ベクトル空間内の距離を定義する関数で、一般的には非線形ベクトル関数となる。例えば、多数の特徴量ベクトルの組ｔｎ、ｔｍ（ｎ、ｍは整数）に対して、両者の相関が十分判別できるような距離Ｌｎｍを定義し、すべてのｎ、ｍに対してφ（ｔｎ）とφ（ｔｍ）のユークリッド距離が距離Ｌｎｍに近くなるようなφ（ｔ）を実験的に求める。また、多数の特徴量ベクトルの組ｔｎ、ｔｍに対して主成分分析を行い、特徴量ベクトルｔを一旦相関の高いベクトル変数に変換してからφ（ｔ）を求めてもよい。また図８に示すように、この非線形ベクトル関数を特徴量テーブルに加えてもよい。特徴量ベクトルに対して非線形ベクトル関数を予め計算しておくことにより、検索処理を早くすることが可能である。
【００６６】
ステップＳＴ９０７では類似度の近い図表を含む文書画像をＰＣ端末１９に送信する。ステップＳＴ９０６で検索された類似度の近い図表の図表ＩＤから、その図表を含まれる文書ＩＤを、特徴量テーブルを参照して求める。そして文書ＩＤにリンクした文書をユーザのＰＣ端末１９に送信する。文書そのものを送信してもよいが、リンクアドレスや図表のサムネイルなどを送信することが好ましい。これにより、ユーザは所望の検索結果を得られる。
【００６７】
また、ユーザが複数の文書を要求する場合は類似度の高い図表を複数選び、類似度の高い順に提示してもよい。また、特徴量テーブルより同じクラスタに含まれる図表を探し、これらの図表を含むすべての文書を提示してもよい。
【００６８】
以上述べたように、本実施形態の検索処理は、登録処理で述べた効果に加え、特徴量ベクトル空間内の距離Ｌを定義する関数を用いることにより、類似図表の相関を高精度に判定できる。従って高精度かつ高速な検索処理を行うことができる。
【００６９】
本実施形態によれば、図表の主要な構成要素の線素の特性に基づいた特徴量を用いて、図表か否かの判定と図表の類似度を計算するため、高精度な判定を行うことができる。また、特徴量として複数の線素の特性の統計量を用いるため、特徴量の次元数を小さくできるため、判定の計算量を小さくできる。さらに、同じ特徴量を用いて、図表領域か否かの判定と類似度の判定を行えるため、特徴量計算の計算量を少なくできるという効果を奏する。これにより、高精度で、計算量が小さい高効率な図表の判定処理を実現することができる。
【００７０】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。例えば、本実施形態では、カラー文書画像の場合には一旦モノクロ画像に変換したが、図表の色に特徴を持たせる場合には、カラー毎に特徴量を算出してもよい。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７１】
１…図表領域検出装置、
２１…スキャナ部、
２２…検索画像入力部、
２３…分割領域抽出部、
２４…非文字領域判定部、
２５…特徴量算出部、
２６…図表領域判定部、
２７…図表領域分類部、
２８…特徴量テーブル保存部、
２９…図表類似度判定部。
【図１】
2015099536.tif 000007
【図２】
2015099536.tif 000008
【図３】
2015099536.tif 000009
【図４】
2015099536.tif 000010
【図５】
2015099536.tif 000011
【図６】
2015099536.tif 000012
【図７】
2015099536.tif 000013
【図８】
2015099536.tif 000014
【図９】
2015099536.tif 000015