(57)【特許請求の範囲】
【請求項１】
少なくとも１つの候補対象を有する画像データ内のユーザが描いた囲み領域をコンピュータにより抽出する方法であって、
候補対象を表す輪郭を作成する工程と、
上記候補対象の輪郭の特徴点を算出する工程と、
上記候補対象の輪郭を上記特徴点で線分に分割する工程と、
上記線分間の遷移の平滑度を評価するための判定基準を定義する工程と、
上記判定基準を利用して上記線分間の遷移の平滑度を検査する工程と、
上記判定基準内の線分同士を連結する工程と、
上記候補対象の始点と終点との距離を評価することによって上記候補対象に開ループが発生しているかどうかを解析する工程と、
上記始点と上記終点との距離が所定の閾値よりも小さいとき、上記連結された線分をユーザが描いた囲み領域として識別する工程とを備えたユーザ描画囲み領域抽出方法。
【請求項２】
上記特徴点はｘ軸方向およびｙ軸方向のほぼ極大値または極小値で検出される高曲率の点として定義される請求項１記載のユーザ描画囲み領域抽出方法。
【請求項３】
上記遷移の平滑度を検査する工程は、
上記特徴点に対して進入する線分と退出する線分を識別し、
上記進入する線分に対する関連角度と上記退出する線分に対する関連角度を測定し、
上記両関連角度が所定の相互関係の範囲内にある場合に上記進入する線分と上記退出する線分とを結合するものである請求項１記載のユーザ描画囲み領域抽出方法。
【請求項４】
上記ユーザが描いた囲み領域を機械印刷枠と判別するために、さらに上記候補対象の輪郭の平滑度を上記機械印刷枠の平滑度を表す所定値と比較する請求項１記載のユーザ描画囲み領域抽出方法。
【請求項５】
上記開ループが発生しているかどうかを解析する工程は、
上記候補対象の始点と終点に対して円形距離関数、方形距離関数及びマンハッタン距離関数のいずれか１つを実行し、上記３つの関数のいずれかに合格した場合にのみ上記候補対象をユーザが描いた囲み領域と判定する請求項１記載のユーザ描画囲み領域抽出方法。
【請求項６】
上記円形距離関数は上記候補対象の始点がその終点から所定のラジアル距離内にあるか否かを判定するものである請求項５記載のユーザ描画囲み領域抽出方法。
【請求項７】
上記方形距離関数は上記候補対象の始点がその終点を取り巻く所定サイズの正方形の境界箱の中にあるか否かを判定するものである請求項５記載のユーザ描画囲み領域抽出方法。
【請求項８】
上記マンハッタン距離関数は上記候補対象の終点を取り巻く所定サイズの正方形の境界箱を上記終点周りに回転させ、どの回転方位でも上記候補対象の始点が上記境界箱の中に入るか否かを判定するものである請求項５記載のユーザ描画囲み領域抽出方法。
【請求項９】
上記候補対象を表す輪郭を作成する工程は、
画像データ内の連結成分を識別する工程と、
上記各連結成分に関して境界箱を算出する工程と、
上記各境界箱のサイズを解析することにより各境界箱から文字列を消去する工程と、
上記文字列の消去後に残された上記境界箱の中の黒と白の画素比を評価することにより中間調画像を消去する工程と、
上記輪郭を作成する工程の前に上記中間調画像の消去後に残された上記境界箱から少なくとも１つの候補対象を抽出する工程と、
上記候補対象の外形線を追跡して輪郭を作成する工程とをさらに備えている請求項１記載のユーザ描画囲み領域抽出方法。
【請求項１０】
上記候補対象と該候補対象に接触する文字が交差する場合に上記候補対象の形状を単純化する形態操作を実行することにより上記候補対象に接触する文字を消去する工程をさらに備えている請求項４記載のユーザ描画囲み領域抽出方法。
【請求項１１】
上記ユーザが描いた囲み領域の内側の画像を抽出する工程をさらに備えている請求項１記載のユーザ描画囲み領域抽出方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は電子文書及び画像処理に関し、特に、走査により読み込まれた文書またはビットマップ画像上でユーザが描いた囲み領域を識別してその囲み領域内の情報を光学式文字認識によりさらに解析できるようにする装置及び方法に関する。
【０００２】
【従来の技術】
コンピュータ技術の急速な進歩に伴って、ますます多くの文書が電子形式で保管されるようになっている。電子形式は情報読出しに関して全く新しい数々の問題を引き起こしている。
【０００３】
キーワード検索が容易な欧数字テキストファイルとは異なり、ビットマップ画像や走査により読み込まれた情報（走査読込み情報）を含むファイルはそれほど容易には検索を実行できない。その理由は、ビットマップ画像や走査読込み情報が、印刷された単語をコンピュータでは文字や欧文字として直接認識できない小さな白黒のあるいは他の色のドットからなる図形画像として表現しているからである。幸いにも、光学式文字認識（ＯＣＲ）ソフトウェアを採用することでこれらの文字の図形画像をコンピュータで認識可能なテキスト文字に変換できる場合が多い。しかしながら、高速のコンピュータを使用しても、その光学式文字認識による変換処理は時間のかかる処理である。多くの場合、光学式文字認識ソフトウェアを利用して走査により読み込まれた文書（走査読込み文書）の全てのビットマップ画像を変換することは全く非実用的な作業である。
【０００４】
光学式文字認識による変換処理を採用することが実用的でない場合には、ユーザが手動で各ビットマップ画像や走査読込み画像に文字構成のテキスト名やテキストラベルを付与することによって文書画像データベースに索引を付けることもできる。それにより、コンピュータがテキスト名あるいはテキストラベルを画像データと対応付けるので、後にそのテキスト名またはテキストラベルを検索することにより対応する画像データを読み出すことができる。
【０００５】
手動で適切なテキスト名やテキストラベルを入力することは手間のかかる作業であり、文書画像処理装置にキーボードや数値キーパッドを含むコンピュータハードウェアをさらに接続することを必要とする場合が多い。上記索引付けの問題を改めて見てみると、文書画像処理装置にユーザによる囲み領域を認識する技術を採り入れることを暗示している向きもある。そのような領域は、もし識別できるならば、光学式文字認識処理を局所的に行いしたがって必要最小限に抑えるために使用できることになる。その場合、ユーザが必要なキーワードの図形画像を囲み、そして装置がその囲み内の画像データに対して光学式文字認識を実行するとともに、それを後に画像データファイルと対応付けされるラベルに変換する。
【０００６】
【発明が解決しようとする課題】
上記の着想には利点があるが、残念ながら、とりわけユーザ間で手書きの質に大きなばらつきが生じるユーザの囲み領域を正確かつ繰り返し検出することは非常に困難であることがわかっている。この問題は、ユーザが描いた囲み（以後、ユーザ描画囲みとも言う）の中には別の囲み（ユーザが描いたものであれそうでないものであれ）と重なったり交差したりするものもあるという事実により、またユーザが描いた「囲み」が完全には閉じていない場合もあることからさらに複雑になっている。後者の問題はユーザが単に囲みの描画を完成させていない場合、あるいはユーザ描画囲みが画像の抜け落ちによって破断される場合に起こり得る。画像の抜け落ちは、例えば、薄くて細い囲みが描かれ低解像度のスキャナーで処理された場合に発生し得る。
【０００７】
【課題を解決するための手段】
本発明は囲みの候補を「追跡し」、追跡された形状の主要な幾何学的特徴点を識別し、識別された点を案内として代わりの囲みを作成する装置と方法によって上記の問題に対処するものである。コンピュータにより作成されたこの代わりの囲みは、完全に閉じた囲み構造を形成するので、囲み領域内に含まれる文字列を抽出するのにより高い信頼を置くことができる。
【０００８】
ユーザが完全に閉じた囲みを描いていない場合、本発明の装置は様々な端点近似アルゴリズムを用いてユーザの意図が完全に閉じた囲みを描くことなのかそうでないのかを確認することができる。
【０００９】
【発明の実施の形態】
本発明とその目的及び長所をより完全に理解するため、以下の説明と添付図面を参照する。
【００１０】
ユーザ描画囲み領域を抽出する装置及び方法は非常に様々な用途に適用可能である。図１は２つのユーザ描画囲み領域２０，２２を有する文書のページの一例を示す。なお、囲み２０は完全には閉じておらず、囲み２２は隣接する矩形の注釈と重なり合っている。文書はスキャナ、ファックス機、ディジタル複写機などの様々な装置を用いて適切にディジタル化することが可能である。ディジタル化された文書はビットマップ画像や走査読込み画像として表現される。より詳しく説明すると、この抽出装置及び方法によれば、ユーザ描画囲み領域の位置が突き止められ、囲み領域内の内容が抽出される。その内容は光学式文字認識ソフトウェアを使用してさらに処理される。ユーザ描画囲みは適切な製図器具を利用して形成することができる。
【００１１】
あるいは、文書は、例えばコンピュータ画面や文書画像化ディスプレイ上に表示された電子文書であってもよい。図２はラップトップ型コンピュータ２６の画面上に表示された電子文書を示し、そこにはディジタル化パッド３０上で描くスタイラス２８を使ってユーザ描画囲みが形成されている。
【００１２】
図２の実施形態は、文書が最初に紙の形態をとる必要が必ずしもないことを示している。また、文書は、例えば普及しているペイントブラシプログラムや写真加工プログラムのようなビットマップ画像作成ソフトウェアによって作成可能である。あるいは、文書はディジタルカメラやビデオカメラを使って入力されてもよい。説明のため、図２にコンピュータ２６に接続されたディジタルカメラ３２を示す。このカメラは目的の文書を撮影するために使用可能である。その後、ユーザがスタイラス２８を使って囲み領域を描く。
【００１３】
本発明の適用可能な用途の一部をさらに説明するため、図３に電子文書画像処理システムの一例を示す。このシステムはディスクアレイ４２等の連想型記憶媒体を有する文書画像処理サーバ４０を備えている。このサーバは適切なネットワーク通信リンク４４を介して様々な文書入力装置と表示装置に接続されている。例えば、紙文書をサーバ４０に格納可能な電子形式に変換するために、ディジタル複写機４６や平面スキャナ４８が利用可能である。ディジタル化され格納された文書画像はコンピュータワークステーション５０等の適切なワークステーション上に表示されてもよい。
【００１４】
図３に示すように、文書は対応付け索引ラベルが付与された一連のディジタル画像データのレコードとして文書画像データベース５２に保存される。本発明のユーザ描画囲み領域抽出システムは抽出された領域を用いて後にディジタル画像データを読み出すために使用する索引ラベルを作成する。この領域抽出システムのソフトウェアは該システム内の適切な処理装置により制御されてもよい。そのような処理装置には、例えば、サーバ４０や、ワークステーション５０や、複写機４６または平面スキャナ４８に関連する処理装置も含まれる。
【００１５】
図４は上記囲み領域抽出処理の現時点で好ましい実施形態を示す。
【００１６】
現時点で好ましい輪郭解析技術を図４に示す。この技術は候補対象の輪郭を識別することに基づいている。候補対象には、ユーザ描画囲み、機械印刷枠、その他ページ上の文字列以外の材料等が含まれる。特徴抽出モジュールを使って輪郭を解析することにより、アルゴリズムがユーザ描画囲みを抽出する。輪郭は様々な曲率値を有する連続する点列によって表現される。これにより、後処理解析技術によってユーザ描画囲みを機械印刷枠と区別することが可能になる。図４に示すように、アルゴリズムをさらに高速化するため、ステップ２５０で前処理を任意に実行してもよい。最初のステップ（ステップ２５２）では、対象ページ内の連結成分を見つけ出す。このステップでは、画像を線単位で走査（ライン走査）し、各画素が近傍の画素と連結している場合はそれにラベルを付ける。連結性を有する画素にラベルを付けた後、各連結成分ごとに境界箱を算出する。これらの境界箱は画像内の候補領域を抽出するために使用される。
【００１７】
次に、ステップ２５４で、文字列を表現している連結成分を消去する。これは、各境界箱のサイズを解析して所定サイズ以下の境界箱を有する連結成分を消去することによって達成される。ユーザ描画囲み候補ではなさそうな連結成分を消去することにより、以降の処理の高速化を促進することができる。しかしながら、充分な処理能力が得られない場合は、ステップ２５４を省略してもよい。
【００１８】
次に、ステップ２５６で、中間調の画像を消去する。中間調画像は大きな連結成分を構成している。アルゴリズムは該当する連結成分に関連する境界箱内の黒と白の画素比を評価することにより中間調画像を検出する。中間調画像は文字列を含む領域よりも黒画素を多く有する傾向がある。この場合も、充分な処理能力が見込めないときは、ステップ２５６で中間調画像を消去する必要はない。好ましい実施形態では、ユーザ描画囲み候補としては中間調画像を消去し、処理速度を大幅に向上させる。
【００１９】
輪郭解析技術は、該当する輪郭に接触する外側の文字が存在する場合には、実際に必要とされる以上の特徴点を作成することがある。このことは、例えば、ユーザが偶然に当該ページ上の他の文字を横切る囲みを描いた場合に起こり得る。
【００２０】
任意の前処理ステップでは、ユーザ描画囲みとその外側文字が交差する領域内の輪郭形状を単純化する形態操作を実行することによりこれらの接触文字を消去する。
【００２１】
次に、ページ上の様々な候補領域を検査することによりユーザ描画囲みを識別する。この手順の最初のステップ２５８では、候補対象の輪郭の作成を行う。これは、対象の外形線を追跡することにより達成される。
【００２２】
説明のために、２つの候補領域を有する例を示す図５を参照する。なお、これらの領域はユーザ描画囲み検出問題をより難解にするよう偶然重なり合っている。また、形状６０は囲みが完成されていないか抜け落ちあるいは他の欠陥を含んでいる隙間６１を有している。アルゴリズムはどの輪郭がユーザ描画囲みであるのかを判定する必要がある。図５には、４つの可能性、すなわち、楕円形状６０、矩形形状６２、形状６０と形状６２の重なり合う共有部分６４、そして形状６０と形状６２を組み合わせてなる合成外側境界線形状６６が存在する。
【００２３】
輪郭はコンピュータのメモリ内で順序付きの点（境界画素の座標）集合として表現される。追跡方式では、最初に始点（以前に追跡されていない境界画素）を走査により探索する。そして、対象の凸状外形線に沿って時計回りあるいは反時計回りに追跡を開始する。追跡が始点あるいは周囲にそれ以上黒画素が発見されない点に達したとき、その追跡を停止して次の始点を探索する走査処理を続行する。
【００２４】
図６は追跡ステップ２５８が図５の重なり合う対象に対して実行された結果として得られる追跡輪郭の一例を示す。なお、輪郭追跡は対象を画定する線の内周と外周をたどる小間隔の二重線として出現する。
【００２５】
次に、ステップ２５８で得られた輪郭を各輪郭に関連する特徴点を算出することによって解析する（ステップ２６０）。ステップ２５８で得られた輪郭は画像のノイズのせいで閉曲線にも破断曲線にもなり得る。特徴点は囲みと他の対象との交差点を含む高曲率の点として定義される。曲率は再標本化技術を用いて算出可能であるが、この技術はノイズがディジタル化処理の過程で発生する場合には当てにならない。観測により、特徴点はｘ軸方向およびｙ軸方向に関して、最大値と最小値の全てがそうとは限らないが、ほぼ極大値あるいは極小値で検出することが可能である。好ましい実施形態では、各輪郭の始点及び終点を特徴点として扱う。採用可能な特徴点７０ないし８６を図６に示す。
【００２６】
特徴点を識別した後、その特徴点を使って囲み領域を再構成する。それをステップ２６２で示す。要するに、ステップ２５８で作成した各輪郭を特徴点で線分に分解する。これらの線分は検査され、異なる対象に属する線分同士が分離され同じ対象に属する線分同士が連結されるように再連結される。
【００２７】
輪郭の線分を再連結する主要な判定基準は隣接する線分間の遷移の平滑度を検査することである。各輪郭線分について、その始点と終点の周囲の小領域を検査する。この両端の点はその傾き（線分に対する進入角度と退出角度）が推定できるように直線に当てはめられる。これらの推定角度は、２つの線分が同じ輪郭に属するものとして連結されるように互いに近づいているのかあるいは無関係の輪郭にそれぞれ属するように互いに交差しているのかを評価するために使用される。
【００２８】
図７は各輪郭線分を評価する方法を示す。傾きが評価されるように、始点と終点を直線に当てはめることによって検査する。図７において、角度１は進入角度であり、角度２は退出角度である。図７における輪郭線分の方向はａからｂに向かう方向である。進入角度は線分の最初の数箇所の点を１本の直線に当てはめその傾きを算出することによって推定される。同様にして、退出角度も線分の最後の数箇所の点を１本の直線に当てはめることによって推定される。これらの角度は±１８０度の範囲に入るように限定される。
【００２９】
各輪郭線分について、アルゴリズムが近傍領域にある全ての始点と終点を検査する。近傍が１つだけの場合には、アルゴリズムは、角度変化の平滑度を検査する必要はなく、２つの点を連結するだけである。近傍が複数存在する場合には、アルゴリズムは最も平滑に遷移する近傍を選択する。これを図８に示す。したがって、図８では、始点ａと終点ｂが連結されることになる。
【００３０】
図９（ａ）ないし図９（ｄ）は平滑度判定基準を満たす２本の線分を連結するいくつかの場合を示している。以下、左側の線分を線分１と称し、右側の線分を線分２と称する。線分上のドットは始点を表している。平滑特性は以下のように定義されることが最も好ましい。すなわち、
(a)  平滑度は線分１の退出角度と線分２の進入角度との差として定義される。平滑度条件を満たすと、線分２を線分１に追加する。
【００３１】
(b)  平滑度は線分１の退出角度と線分２の退出角度の反転との差として定義される。平滑度条件を満たすと、線分２を反転させた後、線分１に追加する。
【００３２】
(c)  平滑度は線分１の進入角度の反転と線分２の進入角度との差として定義される。平滑度条件を満たすと、線分１を反転させた後、線分２を線分１に追加する。
【００３３】
(d)  平滑度は線分１の進入角度と線分２の退出角度との差として定義される。平滑度条件を満たすと、線分１を線分２に追加する。
【００３４】
これらの判定基準に基づき、アルゴリズムは特徴点で分かれた輪郭線分を再連結する。図１０は再連結後の結果を示し、線分化されていた輪郭が２つの別の対象、すなわち、楕円対象９０と矩形対象９２とに形成される。
【００３５】
図４に示すように、ステップ２６４では、ステップ２６２で再構成された囲みを使用することによって、一連のテストを通してユーザ描画囲みを識別する。最初のテストは輪郭が占める面積と輪郭のサイズに基づいている。輪郭の長さが所定の閾値を超えるとともに輪郭の境界箱が所定面積を占めていれば、アルゴリズムはその輪郭をユーザ描画囲みであるとみなす。
【００３６】
しかしながら、ユーザ描画囲みと矩形枠、機械印刷円や表などの機械印刷枠とを判別するために、連結された輪郭の平滑度を検査する。平滑度を測定する１つの方法は連結された輪郭に沿って平均曲率を算出することである。平滑度が所定の閾値を超えている場合には、輪郭を機械印刷されたものとみなす。平滑度走査は以下の式で表される。
【００３７】
【式１】
0003678345.tif 000002
【００３８】
アルゴリズムは算出された特徴点から囲み領域を再構成するので、ユーザ描画囲みが小さな隙間や破断部分を含んでいても識別される。必要ならば、ユーザ描画囲み候補をさらに評価して隙間がユーザ描画囲みではないと拒否する根拠を果たすほど充分に大きいか否かを判定することができる。ステップ２６６における解析では、輪郭の始点と終点との距離を評価する。距離は様々な方法で評価可能である。
【００３９】
距離評価技術の１つは一方の端点が他方の端点から所定のラジアル距離内にあるか否かを判定することである（図１１（ａ）参照）。以後、これを円形距離関数と称する。別の距離評価技術は一方の端点の周囲に所定サイズの正方形の境界箱を画成し、他方の端点がその境界箱の中にあるか否かを判定することである（図１１（ｂ）参照）。以後、これを方形距離関数と称する。３つめの距離評価技術は一方の端点の周囲に所定サイズの正方形の境界箱を画成した後、それをその端点周りに回転させ、どの回転方位でも他方の端点が境界箱の中に入るかどうを判定することである。これは、境界箱の１隅が２つの端点間を結ぶ線上に位置する場合に起こる（図１１（ｃ）参照）。以後、これをマンハッタン距離関数と称する。
【００４０】
輪郭が上記のテストのいずれにも合格しない場合には、ユーザ描画囲みではなく開いた円弧であるとみなされる。受け入れられた囲みの図を図１２（ａ）ないし図１２（ｃ）に示し、拒否された対象を図１２（ｄ）ないし図１２（ｇ）に示す。ユーザ描画囲みが上述のように識別されると、その輪郭を取り巻く境界箱を使用して、続いて行われる光学式文字認識解析のために抽出される領域の範囲を限定する。それをステップ２６８で示す。輪郭の境界箱の内側の画像を抽出し、この抽出画像に対して任意に光学式文字認識を実行することができる。
【００４１】
図６に示すように、ユーザ描画囲みは２つのエッジを有しているので、内と外で２つの輪郭集合が作成される。アルゴリズムは２つの境界箱のうちの大きいほうを使用して領域抽出を行う。
【００４２】
文書画像処理システムでは、抽出領域を様々な形式で表示することが可能である。その１つは囲み領域を部分画像として出力する形式である。もう１つはページ全体を出力し、ユーザ囲み領域を色で強調表示する形式である。さらに別の選択肢は囲みの内側を強調表示させる形式である。その実現のためには、輪郭の隙間を閉じる必要がある。この閉塞はいくつかの方法で行われる。そのうちの２つを図１３（ａ）および図１３（ｂ）で示す。図１３（ａ）では、端点同士を直接連結することにより閉塞する。図１３（ｂ）では、一方の端点をこの端点と最小距離にある曲線上の点に連結させることにより閉塞する。
【００４３】
上記システムは、ユーザ描画領域を抽出して表示した後にさらに、光学式文字認識技術を利用して抽出領域を処理し、文書保存と読出しの目的で索引ラベルを作成することもできる。
【００４４】
本発明を現時点で好ましい実施形態に基づいて説明してきたが、特許請求の範囲で述べた本発明の精神から逸脱することなく上述の実施形態に対する一定の変更が可能であることは理解できるであろう。
【図面の簡単な説明】
【図１】ユーザ囲み領域を示す文書のページの一例を示す図。
【図２】画面上に表示されスタイラスで囲みが描かれる電子文書の一例を示す図。
【図３】本発明にかかる文書画像データベースシステムを示す図。
【図４】走査読込み文書またはビットマップ文書から囲み領域を抽出する好ましい工程を示すフローチャート。
【図５】重なり合う対象の一例を示す図。
【図６】図５の対象の輪郭と特徴点の一例を示す図。
【図７】進入角度と退出角度を示す図。
【図８】好ましい平滑度アルゴリズムによる再連結の一例を示す図。
【図９】（ａ）ないし（ｄ）は２つの線分を連結するそれぞれ異なる場合を示す図。
【図１０】図５及び図６の例を使用して特徴点を再連結した状態を示す図。
【図１１】（ａ）ないし（ｃ）は閉ループ評価関数のそれぞれ別の実施形態を示す図。
【図１２】（ａ）ないし（ｇ）は受け入れられた対象と拒否された対象の例を示す図。
【図１３】（ａ）および（ｂ）は表示のためにユーザ描画囲みの隙間を閉じる例を示す図。
【符号の説明】
２０，２２      ユーザ描画囲み領域（ユーザが描いた囲み領域）
２６      ラップトップ型コンピュータ
２８      スタイラス
３０      ディジタル化パッド
３２      ディジタルカメラ
４０      文書画像処理サーバ
４２      ディスクアレイ
４６      ディジタル複写機
４８      平面スキャナ
５０      ワークステーション
５２      文書画像データベース
６０      楕円形状
６２      矩形形状
６４      共有部分
６６      合成外側境界線形状
７０,７２,７６,７８,８０,８２,８４,８６      特徴点
９０      楕円対象
９２      矩形対象
ａ      始点
ｂ      終点
【図１】
0003678345.tif 000003
【図２】
0003678345.tif 000004
【図３】
0003678345.tif 000005
【図４】
0003678345.tif 000006
【図５】
0003678345.tif 000007
【図６】
0003678345.tif 000008
【図７】
0003678345.tif 000009
【図８】
0003678345.tif 000010
【図９】
0003678345.tif 000011
【図１０】
0003678345.tif 000012
【図１１】
0003678345.tif 000013
【図１２】
0003678345.tif 000014
【図１３】
0003678345.tif 000015