画像処理装置および画像処理プログラム
【課題】抽出対象のドキュメント画像と原本画像との差分に含まれる欠損部分、特に複雑な文字などに発生した途切れ部分をより正確に接続して修復可能とする。
【解決手段】ドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象の追記ドキュメント画像データと原本ドキュメント画像データとの差分を差分抽出部１１１でとって追記情報を生成し、この追記情報に含まれる欠損部分を修復する際に、欠損部分に相当する細線（リンク）を、第２の細線化部１１３で細線化して得た細線化追記ドキュメント画像から欠損線分特定部１１４で特定し（見つけ出し）、その特定した細線で欠損部分を修復する。
【解決手段】ドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象の追記ドキュメント画像データと原本ドキュメント画像データとの差分を差分抽出部１１１でとって追記情報を生成し、この追記情報に含まれる欠損部分を修復する際に、欠損部分に相当する細線（リンク）を、第２の細線化部１１３で細線化して得た細線化追記ドキュメント画像から欠損線分特定部１１４で特定し（見つけ出し）、その特定した細線で欠損部分を修復する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および画像処理プログラムに関し、特に例えば追記情報の解析処理などにおいて行われる原本ドキュメントと追記ドキュメントとの差分データに含まれる欠損部の修復処理など、様々なデータ抽出処理によって得られる欠損部を含む線画データの修復を効率的に実行する画像処理装置および画像処理プログラムに関する。
【背景技術】
【０００２】
画像処理の分野において、例えばプリンタやＦＡＸ（ファクシミリ装置）などから出力したドキュメントに、ユーザがペンや鉛筆、スタンプなどで追記した部分を抽出したり、セキュリティ文書が改竄されていないかどうかを検証したりする処理について、様々な研究、開発が行われている。
【０００３】
一般的に、このような追記抽出、改竄検証などの処理には、オリジナルのドキュメントデータと、追記等の可能性がある出力ドキュメントとを比較する処理が行われる。すなわち、追記抽出の対象となる紙ドキュメントをスキャナなどの画像読取装置でスキャンして得たスキャン画像データと、ＰＣ（パーソナルコンピュータ）やプリンタなどのサーバに蓄積されている原本画像データとの差分をとることによって追記画像データを抽出するというものである。
【０００４】
ところが、スキャン画像データと原本画像データとの差分をとる手法では、ドキュメント上に元から存在する文字や図形などの既存画像に対して、追記した文字や図形などの追記画像に重なり部分がある場合に、差分処理によって抽出した追記画像（追記情報）に既存画像との重なり部分が含まれず、当該重なり部分で途切れた画像となってしまうという問題があった。
【０００５】
そのため、従来は、スキャン画像から原本画像を差し引いて得た追記画像の途切れ部分を修復するようにしていた。具体的には、例えば、原本画像の黒画素を順次走査し、着目黒画素の周囲８画素に追記画像の黒画素があるときに、着目画素に相当する追記画像の画素を黒にするという処理を行うことによって途切れを修復するようにしていた（例えば、特許文献１参照）。
【０００６】
また、スキャン画像から原本画像を差し引く差分処理によって得た追記画像から、途切れた追記部分の輪郭を作成し、その輪郭画像から原本画像をさらに差し引くことによって接続すべき端点の座標と接続方向を検出し、さらに、その端点位置と接続方向の情報から端点同士を接続し閉曲線を構成してその内部を着色するという処理を行うことにより、途切れの発生してしまった追記画像の途切れ部分を接続（修復）するようにしていた（例えば、特許文献２参照）。
【０００７】
【特許文献１】特開平０８−０６３５４６号公報
【特許文献２】特開２００４−２１３２３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、追記画像を検出しようとするドキュメントのスキャン画像には画質の劣化、即ちかすれ具合や色合いに変化が発生してしまう可能性が高い。プリントおよび追記の後に、何回かコピーされている場合などは特に、追記部分はかすれなど画質劣化が激しいために、追記画像の抽出対象のドキュメントスキャン画像から抽出した追記部分の輪郭は、直線ではなくジグザグになる場合が多い。このため、端点および補間方向（接続方向）の特定が困難となり、上記特許文献１，２記載の手法を適用しても、完全な形で修復した追記画像を取得することは難しい。
【０００９】
また、途切れを修復して追記画像を取得する際、直線の途切れのように接続すべき端点を容易に発見できる場合は大きな問題がないが、ペンや鉛筆などの筆記具によって追記された文字など、複雑な線分を持つ追記画像における途切れ修復にあっては、接続すべき端点を正確に発見するが難しいために、上記特許文献１，２記載の手法を適用しても、正確な途切れ修復は困難である。
【００１０】
本発明は、上記課題に鑑みてなされたものであって、その目的とするところは、例えばドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象のドキュメント画像と原本画像との差分に含まれる欠損部分、特に複雑な文字などに発生した途切れ部分を、より正確に接続して修復することが可能な画像処理装置および画像処理プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明では次のような構成を採っている。すなわち、所定の画像から所定の情報を抽出する、例えば原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する。そして、この抽出した追記情報に対して細線化処理を実行するとともに、前記追記ドキュメントの画像に対して細線化処理を実行する。そして、追記ドキュメントの画像を細線化した第２の細線化画像から、抽出した追記情報を細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成し、この欠損線分画像と第１の細線化画像とを合成して修復追記抽出画像を生成する。
【００１２】
例えば、ドキュメントから追記情報を抽出する画像処理において、抽出対象の追記ドキュメント画像と原本ドキュメント画像との差分から抽出される追記情報に含まれる欠損部分を修復する際に、追記ドキュメントの画像を細線化した第２の細線化画像（細線化追記ドキュメント画像）から、抽出した追記情報を細線化した第１の細線化画像（細線化追記抽出画像）の欠損部分に相当する線分を特定することで、欠損部分に相当する線分を第２の細線化画像から見つけ出すことができる。そして、この見つけ出した線分を第１の細線化画像と合成することで、抽出した追記情報に含まれる欠損部分を修復できる。
【発明の効果】
【００１３】
本発明によれば、欠損部分に相当する線分を細線化追記ドキュメント画像から見つけ出し、その線分で欠損部分を修復することにより、どの端点とどの端点とを接続すれば良いのかが明確になるために、かすれなどスキャン画像の劣化が激しい場合でも、また漢字などの複雑な文字に発生した途切れ部分でも、より正確に接続して修復することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１５】
図１は、本発明が適用される画像情報処理システムの構成の概略を示すシステム構成図である。図１において、画像処理装置１００は本発明による画像処理装置に相当し、例えば、原本ドキュメント１０と、当該原本ドキュメント１０に対してコメントやアンダーラインなどの様々なメモ書きを含む情報（追記情報）が記入された追記ドキュメント２０とから、両ドキュメント上の画像の差分をとって追記情報を抽出する処理において、差分情報の欠損部を修復する処理を行う。
【００１６】
なお、本発明による画像処理装置１００は、差分処理のみならず、その他、様々な処理によって得られた欠損部を含む情報における当該欠損部を修復する処理全般に適用可能である。図１には、その一つの処理例である差分処理に係る画像情報処理システムを例示しているに過ぎない。
【００１７】
本適用例に係る画像情報処理システムにおいては、原本ドキュメント１０と追記ドキュメント２０とを画像読取装置、例えばスキャナ３０によって読み取り、この読み取りによって得られた原本ドキュメント画像データと追記ドキュメント画像データとを画像処理装置１００に入力する。画像処理装置１００は、原本ドキュメント画像データと追記ドキュメント画像データとから、両ドキュメント上の画像の差分をとって追記情報を抽出するとともに、抽出した追記情報に含まれる欠損部を修復する処理を行う。
【００１８】
ところで、背景技術の欄において説明したように、従来の差分抽出技術では、原本ドキュメントと追記ドキュメントとの画像の重なり部分が途切れた追記情報として抽出される問題がある。このことについて具体的に説明する。
【００１９】
例えば、図２に示すように、原本ドキュメント５１と当該原本ドキュメント５１に線分５３が追記された追記ドキュメント５２とがある場合を考える。この場合、本来追記情報は、線分５３であるにもかかわらず、原本ドキュメント５１と追記ドキュメント５２との差分をとると、追記抽出情報（差分データ）５５に示すように、原本ドキュメント５１の画像との重なり部分で途切れた線分として抽出されるために、追記情報を正しく抽出できない。
【００２０】
なお、本発明による画像処理装置１００は、図２に示す差分処理によって抽出した追記情報の修復処理だけでなく、その他の手法によって取得された様々な欠損部を含む途切れ情報の修復処理も実行することができる。
【００２１】
例えば、図３（Ａ）は、原本ドキュメントの画像を適用することなく、追記ドキュメント６１の画像のみから追記抽出情報６２を抽出する処理例を示している。例えば、追記ドキュメント６１の元画像と異なる色で追記情報が追記されている場合、この追記色情報のみを追記ドキュメント６１から抽出する処理によって、追記抽出情報６２が取得される。しかし、この場合も、原本画像との重なり部分が途切れた画像として追記情報が取得される。
【００２２】
また、図３（Ｂ）は、罫線付きドキュメント７１から罫線を除去した罫線除去情報７２を抽出する処理例を示している。このような抽出処理を行った場合、罫線部としての直線を除去することで、罫線との重なり部分が除去された情報が出力され、本来取得したい追記情報の一部が欠落してしまう。
【００２３】
本発明による画像処理装置１００は、このような途切れ部分や欠損部分を持つ追記抽出情報５５，６２，７２について、途切れ部分や欠損部分をより確実に修復して、途切れや欠損のない追記抽出情報を効率的にかつ確実に正確に生成する処理を行うことを特徴としている。
【００２４】
以下に、本発明による画像処理装置１００およびその処理プログラムについて具体的に説明する。
【００２５】
図４は、本発明による画像処理装置１００を含む画像情報処理システムのより具体的な構成例を示すブロック図である。図４において、画像データ入力部４１は、図１のスキャナ３０に相当し、原本ドキュメントの画像を読み取ることによって得られる原本ドキュメント画像データと、追記ドキュメント２０の画像を読み取ることによって得られる追記ドキュメント画像データとを本発明による画像処理装置１００に入力する。
【００２６】
なお、ここでは、原本ドキュメント画像データおよび追記ドキュメント画像データの両方をスキャナ３０で読み取ってそれらの画像データを画像処理装置１００に入力するとしているが、原本ドキュメント画像データについては、例えば、サーバから与えられる電子原本の画像データを画像処理装置１００に入力しても良く、また本画像処理装置１００内のメモリに蓄積されている電子原本の画像データを用いることも可能である。
【００２７】
画像処理装置１００は、ＣＰＵ(Central Processing Unit:中央演算装置)１０１、Ｉ／Ｏ回路１０２、ＲＯＭ１０３、ＲＡＭ１０４およびＨＤＤ（ハードディスクドライブ）装置１０５などを有し、これら構成要素がバスライン１０６を介して相互に通信可能に接続された構成となっている。
【００２８】
ＣＰＵ１０１は、演算処理を含む本画像処理装置１００全体の処理の制御を行う。Ｉ／Ｏ回路１０２は、画像データ入力部４１および画像データ出力部４２を含む周辺機器との入出力を管理する。ＲＯＭ１０３は、ＣＰＵ１０１による制御の下に実行される各種処理の処理プログラムを格納する。ＲＡＭ１０４は、当該各種処理の実行時に使用される一次記憶装置である。ＨＤＤ１０５は、ＣＰＵ１０１による制御の下に処理された画像データや、外部から取り込んだ画像データなどを記憶する。
【００２９】
画像データ出力部４１は、プリンタやディスプレイ等の出力装置とその制御手段によって構成され、画像処理装置１００での処理によって追記ドキュメントから抽出され、途切れ部分や欠損部分が修復された途切れや欠損のない追記情報（追記抽出情報）を印刷（記録）紙に印刷出力したり、あるいは、表示画面上に表示出力したりする。
【００３０】
［実施例１］
図５は、本発明の実施例１に係る画像処理装置１００Ａの機能構成例を示すブロック図である。図５に示すように、本実施例１に係る画像処理装置１００Ａは、差分抽出部１１１、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成となっている。
【００３１】
（差分抽出部）
差分抽出部１１１は、特許請求の範囲の情報抽出手段に相当し、所定の画像から所定の情報を抽出する。例えば、原本ドキュメント画像データと、原本に含まれない追記情報を含む追記ドキュメント画像データとの差分をとることにより、原本に含まれない追記情報を抽出して追記抽出画像データとして出力する。ここで、差分抽出には、周知の技術、例えば特開２００４−２１３２３０号公報や、特開２００４−３４１９１４号公報等に記載の技術を用いることができる。その差分抽出技術とは、例えば、原本ドキュメント画像データのｘ，ｙ座標位置と、追記ドキュメント画像データのｘ，ｙ座標位置との差分の有無を検出し、差分が存在する場合にのみ追記情報として抽出するというものである。
【００３２】
この差分抽出処理例について図６を参照してより具体的に説明する。図６には、原本ドキュメント２５１と追記ドキュメント２５２とから差分を抽出する処理例を示している。追記ドキュメント２５２には、元々の原本ドキュメント２５１には含まれない追記情報２５３が含まれている。
【００３３】
差分抽出部１１１は、原本ドキュメント２５１と追記ドキュメント２５２とから両画像の差分をとることによって追記情報を抽出し、その追記抽出画像データ２５４として出力する。ただし、図６から明らかなように、差分抽出によって得られる追記抽出画像データ２５４に含まれる抽出情報は、原本データとの重なり部分（図に示す原本に元々記載のある文字「ますか」との重なり部分）が途切れた不完全な追記情報である。
【００３４】
（細線化部）
第１の細線化部１１２は、差分抽出部１１１から出力される追記抽出画像データに対して細線化処理を実行する。第２の細線化部１１３は、追記ドキュメント画像データに対して細線化処理を実行する。
【００３５】
ここに、第１，第２の細線化部１１２，１１３での細線化処理とは、処理対象の画像に含まれる線分を、太い線も細い線も一律に、線分の中心を表す線幅が例えば１画素（ドット）の線に変換する処理を言う。具体的には、細線化処理では、例えば、着目画素を左上から右下へ移動させながら、その周りの画素値パターンによって着目画素の画素値を変更する。
【００３６】
図７に、第１，第２の細線化部１１２，１１３が実行する細線化処理の具体例を示す。第１の細線化部１１２は、図７（ａ）に示すように、差分抽出部１１１での差分抽出によって抽出した追記情報のみからなる追記抽出画像データ２５４に対して細線化処理を施すことにより、第１の細線化画像である細線化追記抽出画像２５５を生成し、当該細線化追記抽出画像２５５を欠損線分特定部１１４に対して出力する。この細線化処理により、細線化追記抽出画像２５５は欠損部を含む線分画像となる。
【００３７】
一方、第２の細線化部１１３は、図７（ｂ）に示すように、原本情報および追記情報の双方を含む追記ドキュメント画像データ２５６に対して細線化処理を施すことにより、第２の細線化画像である細線化追記ドキュメント２５６を生成し、当該細線化追記ドキュメント２５６を欠損線分特定部１１４に対して出力する。
【００３８】
なお、追記抽出画像データの細線化処理の前処理として、当該追記抽出画像データに対して膨張処理を施して太線化を実行し、微小な欠損部分を消滅させた後、細線化処理を実行する構成を採るようにしても良い。ここに、膨張処理（太線化処理）とは、線分などの有効画像領域を上下左右にｎ画素膨らませる処理を言う。この膨張処理により、微小な欠損部分を消滅させることが可能となる。その後、細線化処理を実行することで、比較的大きな欠損部分のみが残った細線化データを生成することができる。
【００３９】
（欠損線分特定部）
欠損線分特定部１１４は、第２の細線化部１１３が出力する細線化追記ドキュメント２５６から、第１の細線化部１１２が出力する細線化追記抽出画像２５５の欠損部分に相当する線分を特定して欠損線分画像を生成する。図５に示すように、欠損線分特定部１１４は、ノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４によって構成されている。
【００４０】
ノード位置特定部１１４１は、細線化追記抽出画像２５５における端点および細線化追記ドキュメント２５６における交点、分岐点、端点をノードとし、当該ノードの位置（座標）を特定する。具体的には、着目画素を左上から右下へ移動させながら、その周りの画素値パターンによって交点、分岐点、端点を抽出してノードとし、当該ノードの座標位置を記憶する。
【００４１】
リンク長算出部１１４２は、ノード位置特定部１１４１が特定したノードの座標位置を基に、ノードとノードとの結ぶ細線（以下、「リンク」と記述する）の長さを算出する。具体的には、各ノードからＯＮ画素（白背景における黒画素／黒背景における白画素）を１ドット（画素）ずつたどって、次のノードに到達するまでのドット数（画素数）をリンク長として算出する。
【００４２】
リンク分類部１１４３は、リンク長算出部１１４２が算出したリンク長を基に、各リンクが概ね細線化追記抽出画像２５５と重なるかどうかを検出して、重なり無しリンク集合を抽出する。例えば、全リンクを一つずつ細線化追記抽出画像２５５と重なりが無いかチェックしてゆき、重なるドットが1つでもあるリンクは、それを重なり有りと判定する。
【００４３】
最短リンク集合探索部１１４４は、リンク分類部１１４３が分類した最短リンク集合、即ち重なり無しリンク集合から、細線化追記抽出画像２５５の２端点を最短長で結ぶリンクの集合を探索して欠損線分画像とする。具体的には、細線化追記抽出画像２５５の端点から生成されたノード一つ一つについて、重なり無しリンク集合に属するリンクをつないで他の細線化追記抽出画像の端点から生成されたノードに到達するかどうかを検出し、つながるものがあればそれを最短リンク集合とする。また、複数ある場合は、リンク長の総和が小さい方を最短リンク集合とする。
【００４４】
また、別の方法として、ダイクストラ法を使うこともできる。ダイクストラ法は、カーナビ等で現在地から目的地に至る最短距離経路を求める手法として多用されており、任意のノードを起点に他の全てのノードに到達する最短距離経路、即ち最短リンク集合を一意的に求めることができる。この特性を利用し、細線化追記抽出画像２５５の端点から生成されたノードが最短距離で到達できる他の追記画像細線の端点から生成されたノードおよびその経路を一意的に求めることができる。
【００４５】
（合成部）
合成部１１５は、欠損線分特定部１１４が特定した欠損線分画像と、第１の細線化部１１２が追記抽出画像データから生成した細線化追記抽出画像との合成処理を実行して、修復追記抽出画像データとして出力する。この合成処理では、欠損線分特定部１１４の最短リンク集合探索部１１４４が探索した最短リンク集合に相当する細線化追記抽出画像２５５上の画素をＯＮ画素（画像を表示する有効画素）にする画素値変更を行う。
【００４６】
合成部１１５の処理例について、図８を参照して説明する。図８に示す細線化追記抽出画像２５５は、第１の細線化部１１２が追記抽出画像データから生成した細線化追記抽出画像データに基づく画像である。また、図８に示す欠損線分特定部１１４の出力画像２７１は、欠損線分特定部１１４が細線化追記ドキュメント２５６から特定した、細線化追記抽出画像２５５の欠損部分に相当する欠損線分によって構成される画像である。本例の場合、出力画像２７１には、５つの欠損線分ａ，ｂ，ｃ，ｄ，ｅが含まれている。
【００４７】
合成部１１５は、これら図８に示す細線化追記抽出画像２５５と欠損線分特定部１１４の出力画像２７１とを合成する処理を行う。この合成処理の結果、図８に示す修復追記抽出画像データ２８１が生成される。
【００４８】
以上説明した実施例１に係る画像処理装置１００Ａの各構成要素、即ち差分抽出部１１１、第１，第２の細線化部１１２，１１３、欠損線分特定部１１４および合成部１１５、さらには欠損線分特定部１１４を構成するノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４については、パーソナルコンピュータ（ＰＣ）のように、所定プログラムを実行することによって情報記憶処理、画像処理、演算処理等の各機能を実行するコンピュータ機器を利用してソフトウェア構成によって実現することが考えられる。ただし、ソフトウェア構成による実現に限られるものではなく、ハードウェア構成、あるいはハードウェアとソフトウェアの複合構成によって実現することも可能である。
【００４９】
ソフトウェア構成によって実現する場合、差分抽出部１１１、第１，第２の細線化部１１２，１１３、欠損線分特定部１１４および合成部１１５、さらにはノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４としてコンピュータを機能させるプログラムが本発明による画像処理プログラムとなる。
【００５０】
また、以下に説明する画像処理シーケンスにおける各ステップの処理を実行するプログラムが、本発明による画像処理プログラムであるとも言える。そして、これらの画像処理プログラムについては、あらかじめコンピュータ内にインストールしておくことが考えられる。ただし、あらかじめインストールされているのではなく、コンピュータ読み取り可能な記憶媒体に格納されて提供されるものであっても良く、または有線若しくは無線による通信手段を介して配信されるものであっても良い。
【００５１】
（欠損部の修復処理）
次に、上記構成の実施例１に係る画像処理装置１００Ａにおいて、ＣＰＵ１０１（図４参照）による制御の下に実行する、追記抽出画像の欠損部分を修復する画像処理の処理シーケンスの手順の一例について、図９および図１０のフローチャートにしたがって説明する。
【００５２】
先ず、差分抽出（差分抽出部１１１での処理に相当）によって抽出した追記情報のみからなる追記抽出画像に対して細線化処理を行って細線化追記抽出画像とし（ステップＳ１１）、次いで原本情報および追記情報の双方を含む追記ドキュメントに対して細線化処理を行って細線化追記ドキュメントとする（ステップＳ１２）。これらの細線化処理は、図５の第１，第２の細線化部１１２，１１３の処理に相当する。
【００５３】
次に、図７（ａ）から明らかなように、欠損部を多数含む線分画像である細線化追記抽出画像のノード（端点）を抽出し、抽出したノードの各々に識別子であるノードＩＤを付与するとともに、各ノードの位置（座標）を取得する（ステップＳ１３）。この時点における細線化追記抽出画像のノード数（端点数）をＮｍとする。次いで、細線化追記ドキュメントのノード（端点・交点・分岐点）を抽出し、抽出したノードの各々にノードＩＤを付与するとともに、各ノードの位置（座標）を取得する（ステップＳ１４）。細線化追記ドキュメントの全ノード数をＮｎとする。
【００５４】
次に、ノードＩＤの番号ｉをｉ＝１に設定し（ステップＳ１５）、次いで、ノード（ＩＤ＝ｉ）の分岐数Ｎｂを取得する（ステップＳ１６）。例えば、図１１に示すように、ノード（ＩＤ＝ｉ）が端点（Ａ）の場合はＮｂ＝１、分岐点（Ｂ）の場合はＮｂ＝３、交点（Ｃ）の場合はＮｂ＝４となる。ステップＳ１３〜ステップＳ１６までの各処理は、図５のノード位置特定部１１４１の処理に相当する。
【００５５】
次に、分岐数Ｎｂの番号ｊをｊ＝１に設定し（ステップＳ１７）、次いで、他のノードに到達するまでの細線をたどって２つのノード間の距離をリンク長Ｌとする（ステップＳ１８）。具体的には、あるノードからＯＮ画素を１ドット（画素）ずつたどって、他のノードに到達するまでのドット数（画素数）をリンク長Ｌとする。このステップＳ１７の処理は、図５のリンク長特定部１１４２の処理に相当する。
【００５６】
次に、両端のノードＩＤとリンク長とをリンクリストに記録し（ステップＳ１９）、次いで、分岐数Ｎｂの番号ｊをインクリメント（ｊ＝ｊ＋１）し(ステップＳ２０)、次いで、ノードＩＤの番号ｉが分岐数Ｎｂ以下（ｉ≦Ｎｂ）であるか否かを判断し（ステップＳ２１）、ｉ≦Ｎｂであれば、ステップＳ１８に戻って、ステップＳ１８〜ステップＳ２０の各処理を、ステップＳ２１でｉ＞Ｎｂと判定するまで繰り返して実行する。
【００５７】
ｉ＞Ｎｂであれば、分岐数Ｎｂの番号ｊをインクリメント（ｊ＝１＋１）し（ステップＳ２２）、次いで、ノードＩＤの番号ｉが全ノード数Ｎｎ以下（ｉ≦Ｎｎ）であるか否かを判断し（ステップＳ２３）、ｉ≦Ｎｎであれば、ステップＳ１６に戻って、ステップＳ１６〜ステップＳ２２の各処理を、ステップＳ２３でｉ＞Ｎｎと判定するまで繰り返して実行する。
【００５８】
このステップＳ１６〜ステップＳ２３までの処理ループは、リンクリストを作成するための処理ループである。ここで、リンクリストを作成する処理について、理解を容易にするために、図１２に示す簡易な線分図形を例に挙げて具体的に説明する。
【００５９】
図１２に示す簡易な線分図形では、ノードが７個（Ｎｎ＝７）存在する。これら７個のノードに対して、図の左上から右下への走査順にノードＩＤを付与する（ＩＤ＝１〜ＩＤ＝７）。ここで、ＩＤ＝１，ＩＤ＝２，ＩＤ＝４，ＩＤ＝６，ＩＤ＝７の５個のノードは端点（Ｎｂ＝１）である。ＩＤ＝３のノードは交点（Ｎｂ＝４）である。ＩＤ＝５は分岐点（Ｎｂ＝３）である。
【００６０】
これら７個のノード（ＩＤ＝１〜７）において、ＩＤ＝１のノードから順番のリンク長Ｌを求める。ここで、２つのノードにおいて、リンク長を求めるために細線をたどる際の出発側のノードをノード１、到達側のノードをノード２とする。
【００６１】
先ず、ｉ＝１のときは、Ｎｂ＝１、出発側のノード１はＩＤ＝１のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝１のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ１とする。次に、ｉ＝２のときは、Ｎｂ＝１、出発側のノード１はＩＤ＝２のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝１のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ２とする。
【００６２】
次に、ｉ＝３のときは、Ｎｂ＝４、出発側のノード１はＩＤ＝３のノードであり、当該ノードが交点であることから、４個の分岐（ｊ＝１〜４）についてリンク長Ｌを求めることになる。先ず、ｊ＝１のとき、到達側のノード２はＩＤ＝１のノードであり、ＩＤ＝３のノードからＩＤ＝１のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ１とする。ｊ＝２のとき、到達側のノード２はＩＤ＝２のノードであり、ＩＤ＝３のノードからＩＤ＝２のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ２とする。ｊ＝３のとき、到達側のノード２はＩＤ＝５のノードであり、ＩＤ＝３のノードからＩＤ＝５のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ４とする。ｊ＝４のとき、到達側のノード２はＩＤ＝４のノードであり、ＩＤ＝３のノードからＩＤ＝４のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ３とする。
【００６３】
次に、ｉ＝４のときは、出発側のノード１はＩＤ＝４のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝４のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ３とする。以降、同様にして、ｉ＝５，６，７について、出発側のノード１から到達側のノード２までの細線をたどってリンク長Ｌを求める。そして、このようにして求めたノード１，２のノードＩＤと両ノード１，２間のリンク長Ｌとからリンクリストが作成される。図１３に、上記具体例の場合に作成されるリンクリストの一例を示す。
【００６４】
ここで、図１３のリンクリストから明らかなように、上述したリンクリストの作成処理の場合には、同じ２つのノード間のリンク長が重複して求められることになる。例えば、ｉ＝３のときに、ｊ＝１で求めたＩＤ＝３のノードとＩＤ＝１のノードとの間のリンク長Ｌ１は、ｉ＝１，ｊ＝１で求めたＩＤ＝１のノードとＩＤ＝３のノードとの間のリンク長Ｌ１と同じであり、ｊ＝２で求めたＩＤ＝３のノードとＩＤ＝２のノードとの間のリンク長Ｌ２は、ｉ＝２，ｊ＝１で求めたＩＤ＝２のノードとＩＤ＝３のノードとの間のリンク長Ｌ２と同じである。また、ｉ＝４，ｊ＝１で求めたＩＤ＝４のノードとＩＤ＝３のノードとの間のリンク長Ｌ３は、ｉ＝３，ｊ＝４で求めたＩＤ＝３のノードとＩＤ＝４のノードとの間のリンク長Ｌ３と同じである。
【００６５】
このように、一度求めたノード間（リンク）のリンク長Ｌについては、同じノード間のリンク長が既に求められているか否かの判断ステップを追加して、同じノード間のリンク長について重複して求めないようにすることも可能である。このようにして、重複した処理を省略することにより、リンクリストを作成する処理の処理スピードを上げることができる。
【００６６】
追記抽出画像の欠損部分を修復する処理シーケンスに説明を戻す。以降では、図１０のフローチャートにしたがって説明する。
【００６７】
上述した処理ループによるリンクリストの作成が完了したら、当該リンクリストから重複するリンクを削除し、残った各リンクの画像とそれに相当する位置の細線化追記抽出画像とで論理積（ＡＮＤ）をとり、その論理積結果にＯＮ画素があれば、即ち細線化追記抽出画像と重なる画素（ドット）が1つでもあれば、重なり有りと判定してそのリンクをリンクリストから除外する（ステップＳ２４）。このステップＳ２４の処理は、図５のリンク分類部１１４３の処理に相当する。
【００６８】
ここで、上述したように、リンクリストの作成処理において、同じノード間のリンク長について重複して求めないようにする場合には、ステップＳ２４におけるリンクリストから重複するリンクを削除する処理は不要となる。これにより、リンクリストから重複するリンクを削除する処理を省く分だけステップＳ２４の処理を高速化できる。
【００６９】
次に、ノードＩＤの番号ｉをｉ＝１に設定し（ステップＳ２５）、次いで、ステップＳ２４で分類した最短リンク集合、即ち重なり無しリンク集合から、細線化追記抽出画像２５５の２端点を最短長で結ぶリンクの集合を探索する（ステップＳ２６）。具体的には、ノード（ＩＤ＝１）から他のノードに至る距離を近い順に求め、ノード（ＩＤ≦Ｎｍ）にぶつかったら、それに至るまでの最短リンク集合とする。このステップＳ２６の処理は、図５の最短リング集合探索部１１４４の処理に相当する。
【００７０】
次に、ステップＳ２６で探索した最短リンク集合に相当する細線化追記抽出画像上の画素をＯＮ画素（有効画素）に画素値変更を行うことで、細線化追記抽出画像と欠損線分画像とを合成する（ステップＳ２７）。次に、ノードＩＤの番号ｉをインクリメント（ｉ＝１＋１）し（ステップＳ２８）、次いで、ノードＩＤの番号ｉがステップＳ１３で取得したノード数（端点数）Ｎｍ以下（ｉ≦Ｎｍ）であるか否かを判断し（ステップＳ２９）、ｉ≦Ｎｍであれば、ステップＳ２６に戻って、ステップＳ２６〜ステップＳ２８の各処理を、ステップＳ２９でｉ＞Ｎｍと判定するまで繰り返して実行する。
【００７１】
このステップＳ２６〜ステップＳ２９までの処理ループは、細線化追記抽出画像（例えば、図７（ａ）の細線化追記抽出画像２５５）における途切れの端点間を結ぶ最短リンクの組み合わせ（最短リンク集合）を求めるための処理ループである。
【００７２】
上述したように、例えばドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象の追記ドキュメント画像と原本ドキュメント画像との差分から抽出される追記情報に含まれる欠損部分を修復する際に、欠損部分に相当する細線（リンク）を細線化追記ドキュメント画像（細線画像）から特定し（見つけ出し）、その特定した細線で欠損部分を修復する手法を採ることにより、どの端点とどの端点とを接続すれば良いのかが明確になるために、特に複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００７３】
また、追記画像の欠損部分に相当する細線化追記ドキュメント画像が複雑に分岐していて、当該欠損部分に相当する細線がどれなのか判別が難しい場合でも、細線の最短リンク集合を探索することで、最も確からしい欠損細線を見つけることができる。
【００７４】
なお、ノード位置特定部１１４１の処理において、細線化追記抽出画像（第１の細線化画像）２５５の端点をノードとするとき、当該細線化追記抽出画像２５５の端点と細線化追記ドキュメント画像（第２の細線化画像）２５６とが重ならない場合に、細線化追記抽出画像２５５の端点に相当する追記ドキュメントの画像上の画素に近接する追記ドキュメント画像２５６上の画素をノードするようにしても良い。この手法を採ることにより、細線化追記抽出画像２５５の端点付近が追記ドキュメント画像２５６とぴったり重ならず、微妙にずれる場合があっても、欠損部分を正確に修復できる。
【００７５】
なお、本実施例１では、原本ドキュメント画像データと、原本に含まれない追記情報を含む追記ドキュメント画像データとを差分抽出部１１１に入力して、当該差分抽出部１１１での差分抽出によって追記情報を抽出する画像処理装置１００Ａに適用した場合を例に挙げて説明したが、本発明は追記情報を抽出する画像処理装置１００Ａへの適用に限られるものではない。以下に、他の適用例に係る別の実施例について説明する。
【００７６】
［実施例２］
図１４は、本発明の実施例２に係る画像処理装置１００Ｂの機能構成例を示すブロック図であり、図中、図５と同等部分には同一符号を付して示している。
【００７７】
実施例１に係る画像処理装置１００Ａは、追記ドキュメント画像データと原本ドキュメント画像データとを入力とし、追記ドキュメント画像データと原本ドキュメント画像データとの差分をとって追記情報を抽出する構成を採っているのに対して、本実施例２に係る画像処理装置１００Ｂは、追記ドキュメント画像データのみを入力とし、当該追記ドキュメント画像データから直接追記情報を抽出する構成を採っている。
【００７８】
この追記ドキュメント画像データからの追記情報の直接抽出は、次の原理によって可能である。すなわち、例えば、原本の記録情報（画像情報）が全て黒色で記録され、追記情報が全て赤色で記録されている追記ドキュメントがある場合は、当該追記ドキュメントから赤色で記録された追記情報のみを抽出する色識別処理によって、追記情報の抽出が可能となる。
【００７９】
本実施例２に係る画像処理装置１００Ｂは、図５の差分抽出部１１６の代わりに追記抽出部１１６を備えており、それ以外の構成は実施例１に係る画像処理装置１００Ａの構成と同じである。すなわち、画像処理装置１００Ｂは、追記抽出部１１６、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成を採り、原本ドキュメントに含まれる文字情報などの色と追記された情報の色とが異なる場合、例えば、原本がすべて黒色の文字や線分によって記録され、追記が赤色で行われている場合に適用可能である。
【００８０】
この画像処理装置１００Ｂにおいて、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５が持つ機能は、実施例１に係る画像処理装置１００Ａの場合と同じであり、その説明については重複するので省略する。追記抽出部１１６は、追記ドキュメント画像データから、所定の色（本例では、追記情報の色である赤）を持つ情報を追記情報として抽出する。なお、追記抽出部１１６が抽出する追記情報の色情報については、ユーザが指定入力するなどの方法が考えられる。
【００８１】
この追記抽出部１１６において抽出された追記情報は、実施例１に係る画像処理装置１００Ａの差分抽出部１１１が生成する追記情報と同様に、やはり、原本に含まれる情報との重なり部分で途切れが発生する場合がある。例えば、原本に含まれる黒の文字上に追記された赤色が正確に赤とは認識されず、黒と認識される場合があり、このような重なり部分を追記抽出部１１６が追記情報として認識しない場合があるからである。
【００８２】
このような途切れ部分（欠損部分）は、実施例１に係る画像処理装置１００Ａの場合と同様に、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５における処理によって修復され、最終的に正確な追記情報からなる修復追記抽出画像データが生成される。その結果、実施例１に係る画像処理装置１００Ａの場合と同様に、スキャン画像の劣化が激しい場合でも、また複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００８３】
［実施例３］
図１５は、本発明の実施例３に係る画像処理装置１００Ｃの機能構成例を示すブロック図であり、図中、図１４と同等部分には同一符号を付して示している。
【００８４】
本実施例３に係る画像処理装置１００Ｃは、図１４の追記抽出部１１６の代わりに罫線分離部１１７を備えており、それ以外の構成は実施例１に係る画像処理装置１００Ａの構成と同じである。すなわち、画像処理装置１００Ｃは、罫線分離部１１７、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成を採り、原本ドキュメントが例えば表などの罫線情報によって構成され、その表に元々記載されている文字やユーザが後から追記した文字などを、罫線を含まない記載内容情報として抽出する場合に有効となる。
【００８５】
この画像処理装置１００Ｂにおいて、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５が持つ機能は、実施例１に係る画像処理装置１００Ａの場合と同じであり、その説明については重複するので省略する。罫線分離部１１７は、ドキュメント画像データから、罫線のみを削除することによって記載内容情報を抽出する。
【００８６】
この罫線分離部１１７において抽出された記載内容情報は、実施例１に係る画像処理装置１００Ａの差分抽出部１１１が生成する追記情報と同様に、やはり、表罫線との重なり部分で途切れが発生する場合がある。例えば、罫線上に重なって記録された記載内容情報は、罫線情報として削除され、抽出される記載内容情報に含まれなくなるからである。
【００８７】
このような途切れ部分（欠損部分）は、実施例１に係る画像処理装置１００Ａの場合と同様に、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５における処理によって修復され、最終的に正確な記載内容情報からなる修復記載内容抽出画像データが生成される。その結果、実施例１に係る画像処理装置１００Ａの場合と同様に、スキャン画像の劣化が激しい場合でも、また複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００８８】
なお、本発明は、上記実施例１〜３に係る画像処理装置１００Ａ〜１００Ｃへの適用に限られるものではなく、例えば、追記ドキュメント画像に含まれる線分の色や揺らぎなどの特徴から、印刷による情報と手書きによる情報とを判別し、手書きによる追記情報を抽出するなど、原本に含まれない追記情報を含む追記ドキュメント画像データから当該追記情報を抽出する画像処理を行う画像処理装置全般に適用可能である。
【図面の簡単な説明】
【００８９】
【図１】本発明が適用される画像情報処理システムの構成の概略を示すシステム構成図である。
【図２】原本ドキュメントと追記ドキュメントとの差分処理によって追記情報を取得する処理例についての説明図である。
【図３】追記情報を取得する他の処理例についての説明図である。
【図４】本発明による画像処理装置を含む画像情報処理システムのより具体的な構成例を示すブロック図である。
【図５】本発明の実施例１に係る画像処理装置の機能構成例を示すブロック図である。
【図６】原本ドキュメントと追記ドキュメントとから差分を抽出する処理例についての説明図である。
【図７】細線化処理の具体例についての説明図である。
【図８】合成処理の具体例についての説明図である。
【図９】追記抽出画像の欠損部分を修復する処理シーケンスの手順の一例を示すフローチャート（その１）である。
【図１０】追記抽出画像の欠損部分を修復する処理シーケンスの手順の一例を示すフローチャート（その２）である。
【図１１】ノード（ＩＤ＝ｉ）の分岐数Ｎｂについての説明図である。
【図１２】リンクリストを作成する処理についての簡易な線分図形を用いた説明図である。
【図１３】リンクリストの一例を示す図である。
【図１４】本発明の実施例２に係る画像処理装置の機能構成例を示すブロック図である。
【図１５】本発明の実施例３に係る画像処理装置の機能構成例を示すブロック図である。
【符号の説明】
【００９０】
１０…原本ドキュメント、２０…追記ドキュメント、３０…スキャナ、４１…画像データ入力部、４２…画像データ出力部、１００，１００Ａ，１００Ｂ，１００Ｃ…画像処理装置、１１１…差分抽出部、１１２…第１の細線化部、１１３…第２の細線化部、１１４…欠損線分特定部、１１５…合成部、１１６…追記抽出部、１１７…罫線分離部
【技術分野】
【０００１】
本発明は、画像処理装置および画像処理プログラムに関し、特に例えば追記情報の解析処理などにおいて行われる原本ドキュメントと追記ドキュメントとの差分データに含まれる欠損部の修復処理など、様々なデータ抽出処理によって得られる欠損部を含む線画データの修復を効率的に実行する画像処理装置および画像処理プログラムに関する。
【背景技術】
【０００２】
画像処理の分野において、例えばプリンタやＦＡＸ（ファクシミリ装置）などから出力したドキュメントに、ユーザがペンや鉛筆、スタンプなどで追記した部分を抽出したり、セキュリティ文書が改竄されていないかどうかを検証したりする処理について、様々な研究、開発が行われている。
【０００３】
一般的に、このような追記抽出、改竄検証などの処理には、オリジナルのドキュメントデータと、追記等の可能性がある出力ドキュメントとを比較する処理が行われる。すなわち、追記抽出の対象となる紙ドキュメントをスキャナなどの画像読取装置でスキャンして得たスキャン画像データと、ＰＣ（パーソナルコンピュータ）やプリンタなどのサーバに蓄積されている原本画像データとの差分をとることによって追記画像データを抽出するというものである。
【０００４】
ところが、スキャン画像データと原本画像データとの差分をとる手法では、ドキュメント上に元から存在する文字や図形などの既存画像に対して、追記した文字や図形などの追記画像に重なり部分がある場合に、差分処理によって抽出した追記画像（追記情報）に既存画像との重なり部分が含まれず、当該重なり部分で途切れた画像となってしまうという問題があった。
【０００５】
そのため、従来は、スキャン画像から原本画像を差し引いて得た追記画像の途切れ部分を修復するようにしていた。具体的には、例えば、原本画像の黒画素を順次走査し、着目黒画素の周囲８画素に追記画像の黒画素があるときに、着目画素に相当する追記画像の画素を黒にするという処理を行うことによって途切れを修復するようにしていた（例えば、特許文献１参照）。
【０００６】
また、スキャン画像から原本画像を差し引く差分処理によって得た追記画像から、途切れた追記部分の輪郭を作成し、その輪郭画像から原本画像をさらに差し引くことによって接続すべき端点の座標と接続方向を検出し、さらに、その端点位置と接続方向の情報から端点同士を接続し閉曲線を構成してその内部を着色するという処理を行うことにより、途切れの発生してしまった追記画像の途切れ部分を接続（修復）するようにしていた（例えば、特許文献２参照）。
【０００７】
【特許文献１】特開平０８−０６３５４６号公報
【特許文献２】特開２００４−２１３２３０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、追記画像を検出しようとするドキュメントのスキャン画像には画質の劣化、即ちかすれ具合や色合いに変化が発生してしまう可能性が高い。プリントおよび追記の後に、何回かコピーされている場合などは特に、追記部分はかすれなど画質劣化が激しいために、追記画像の抽出対象のドキュメントスキャン画像から抽出した追記部分の輪郭は、直線ではなくジグザグになる場合が多い。このため、端点および補間方向（接続方向）の特定が困難となり、上記特許文献１，２記載の手法を適用しても、完全な形で修復した追記画像を取得することは難しい。
【０００９】
また、途切れを修復して追記画像を取得する際、直線の途切れのように接続すべき端点を容易に発見できる場合は大きな問題がないが、ペンや鉛筆などの筆記具によって追記された文字など、複雑な線分を持つ追記画像における途切れ修復にあっては、接続すべき端点を正確に発見するが難しいために、上記特許文献１，２記載の手法を適用しても、正確な途切れ修復は困難である。
【００１０】
本発明は、上記課題に鑑みてなされたものであって、その目的とするところは、例えばドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象のドキュメント画像と原本画像との差分に含まれる欠損部分、特に複雑な文字などに発生した途切れ部分を、より正確に接続して修復することが可能な画像処理装置および画像処理プログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するために、本発明では次のような構成を採っている。すなわち、所定の画像から所定の情報を抽出する、例えば原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する。そして、この抽出した追記情報に対して細線化処理を実行するとともに、前記追記ドキュメントの画像に対して細線化処理を実行する。そして、追記ドキュメントの画像を細線化した第２の細線化画像から、抽出した追記情報を細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成し、この欠損線分画像と第１の細線化画像とを合成して修復追記抽出画像を生成する。
【００１２】
例えば、ドキュメントから追記情報を抽出する画像処理において、抽出対象の追記ドキュメント画像と原本ドキュメント画像との差分から抽出される追記情報に含まれる欠損部分を修復する際に、追記ドキュメントの画像を細線化した第２の細線化画像（細線化追記ドキュメント画像）から、抽出した追記情報を細線化した第１の細線化画像（細線化追記抽出画像）の欠損部分に相当する線分を特定することで、欠損部分に相当する線分を第２の細線化画像から見つけ出すことができる。そして、この見つけ出した線分を第１の細線化画像と合成することで、抽出した追記情報に含まれる欠損部分を修復できる。
【発明の効果】
【００１３】
本発明によれば、欠損部分に相当する線分を細線化追記ドキュメント画像から見つけ出し、その線分で欠損部分を修復することにより、どの端点とどの端点とを接続すれば良いのかが明確になるために、かすれなどスキャン画像の劣化が激しい場合でも、また漢字などの複雑な文字に発生した途切れ部分でも、より正確に接続して修復することができる。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００１５】
図１は、本発明が適用される画像情報処理システムの構成の概略を示すシステム構成図である。図１において、画像処理装置１００は本発明による画像処理装置に相当し、例えば、原本ドキュメント１０と、当該原本ドキュメント１０に対してコメントやアンダーラインなどの様々なメモ書きを含む情報（追記情報）が記入された追記ドキュメント２０とから、両ドキュメント上の画像の差分をとって追記情報を抽出する処理において、差分情報の欠損部を修復する処理を行う。
【００１６】
なお、本発明による画像処理装置１００は、差分処理のみならず、その他、様々な処理によって得られた欠損部を含む情報における当該欠損部を修復する処理全般に適用可能である。図１には、その一つの処理例である差分処理に係る画像情報処理システムを例示しているに過ぎない。
【００１７】
本適用例に係る画像情報処理システムにおいては、原本ドキュメント１０と追記ドキュメント２０とを画像読取装置、例えばスキャナ３０によって読み取り、この読み取りによって得られた原本ドキュメント画像データと追記ドキュメント画像データとを画像処理装置１００に入力する。画像処理装置１００は、原本ドキュメント画像データと追記ドキュメント画像データとから、両ドキュメント上の画像の差分をとって追記情報を抽出するとともに、抽出した追記情報に含まれる欠損部を修復する処理を行う。
【００１８】
ところで、背景技術の欄において説明したように、従来の差分抽出技術では、原本ドキュメントと追記ドキュメントとの画像の重なり部分が途切れた追記情報として抽出される問題がある。このことについて具体的に説明する。
【００１９】
例えば、図２に示すように、原本ドキュメント５１と当該原本ドキュメント５１に線分５３が追記された追記ドキュメント５２とがある場合を考える。この場合、本来追記情報は、線分５３であるにもかかわらず、原本ドキュメント５１と追記ドキュメント５２との差分をとると、追記抽出情報（差分データ）５５に示すように、原本ドキュメント５１の画像との重なり部分で途切れた線分として抽出されるために、追記情報を正しく抽出できない。
【００２０】
なお、本発明による画像処理装置１００は、図２に示す差分処理によって抽出した追記情報の修復処理だけでなく、その他の手法によって取得された様々な欠損部を含む途切れ情報の修復処理も実行することができる。
【００２１】
例えば、図３（Ａ）は、原本ドキュメントの画像を適用することなく、追記ドキュメント６１の画像のみから追記抽出情報６２を抽出する処理例を示している。例えば、追記ドキュメント６１の元画像と異なる色で追記情報が追記されている場合、この追記色情報のみを追記ドキュメント６１から抽出する処理によって、追記抽出情報６２が取得される。しかし、この場合も、原本画像との重なり部分が途切れた画像として追記情報が取得される。
【００２２】
また、図３（Ｂ）は、罫線付きドキュメント７１から罫線を除去した罫線除去情報７２を抽出する処理例を示している。このような抽出処理を行った場合、罫線部としての直線を除去することで、罫線との重なり部分が除去された情報が出力され、本来取得したい追記情報の一部が欠落してしまう。
【００２３】
本発明による画像処理装置１００は、このような途切れ部分や欠損部分を持つ追記抽出情報５５，６２，７２について、途切れ部分や欠損部分をより確実に修復して、途切れや欠損のない追記抽出情報を効率的にかつ確実に正確に生成する処理を行うことを特徴としている。
【００２４】
以下に、本発明による画像処理装置１００およびその処理プログラムについて具体的に説明する。
【００２５】
図４は、本発明による画像処理装置１００を含む画像情報処理システムのより具体的な構成例を示すブロック図である。図４において、画像データ入力部４１は、図１のスキャナ３０に相当し、原本ドキュメントの画像を読み取ることによって得られる原本ドキュメント画像データと、追記ドキュメント２０の画像を読み取ることによって得られる追記ドキュメント画像データとを本発明による画像処理装置１００に入力する。
【００２６】
なお、ここでは、原本ドキュメント画像データおよび追記ドキュメント画像データの両方をスキャナ３０で読み取ってそれらの画像データを画像処理装置１００に入力するとしているが、原本ドキュメント画像データについては、例えば、サーバから与えられる電子原本の画像データを画像処理装置１００に入力しても良く、また本画像処理装置１００内のメモリに蓄積されている電子原本の画像データを用いることも可能である。
【００２７】
画像処理装置１００は、ＣＰＵ(Central Processing Unit:中央演算装置)１０１、Ｉ／Ｏ回路１０２、ＲＯＭ１０３、ＲＡＭ１０４およびＨＤＤ（ハードディスクドライブ）装置１０５などを有し、これら構成要素がバスライン１０６を介して相互に通信可能に接続された構成となっている。
【００２８】
ＣＰＵ１０１は、演算処理を含む本画像処理装置１００全体の処理の制御を行う。Ｉ／Ｏ回路１０２は、画像データ入力部４１および画像データ出力部４２を含む周辺機器との入出力を管理する。ＲＯＭ１０３は、ＣＰＵ１０１による制御の下に実行される各種処理の処理プログラムを格納する。ＲＡＭ１０４は、当該各種処理の実行時に使用される一次記憶装置である。ＨＤＤ１０５は、ＣＰＵ１０１による制御の下に処理された画像データや、外部から取り込んだ画像データなどを記憶する。
【００２９】
画像データ出力部４１は、プリンタやディスプレイ等の出力装置とその制御手段によって構成され、画像処理装置１００での処理によって追記ドキュメントから抽出され、途切れ部分や欠損部分が修復された途切れや欠損のない追記情報（追記抽出情報）を印刷（記録）紙に印刷出力したり、あるいは、表示画面上に表示出力したりする。
【００３０】
［実施例１］
図５は、本発明の実施例１に係る画像処理装置１００Ａの機能構成例を示すブロック図である。図５に示すように、本実施例１に係る画像処理装置１００Ａは、差分抽出部１１１、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成となっている。
【００３１】
（差分抽出部）
差分抽出部１１１は、特許請求の範囲の情報抽出手段に相当し、所定の画像から所定の情報を抽出する。例えば、原本ドキュメント画像データと、原本に含まれない追記情報を含む追記ドキュメント画像データとの差分をとることにより、原本に含まれない追記情報を抽出して追記抽出画像データとして出力する。ここで、差分抽出には、周知の技術、例えば特開２００４−２１３２３０号公報や、特開２００４−３４１９１４号公報等に記載の技術を用いることができる。その差分抽出技術とは、例えば、原本ドキュメント画像データのｘ，ｙ座標位置と、追記ドキュメント画像データのｘ，ｙ座標位置との差分の有無を検出し、差分が存在する場合にのみ追記情報として抽出するというものである。
【００３２】
この差分抽出処理例について図６を参照してより具体的に説明する。図６には、原本ドキュメント２５１と追記ドキュメント２５２とから差分を抽出する処理例を示している。追記ドキュメント２５２には、元々の原本ドキュメント２５１には含まれない追記情報２５３が含まれている。
【００３３】
差分抽出部１１１は、原本ドキュメント２５１と追記ドキュメント２５２とから両画像の差分をとることによって追記情報を抽出し、その追記抽出画像データ２５４として出力する。ただし、図６から明らかなように、差分抽出によって得られる追記抽出画像データ２５４に含まれる抽出情報は、原本データとの重なり部分（図に示す原本に元々記載のある文字「ますか」との重なり部分）が途切れた不完全な追記情報である。
【００３４】
（細線化部）
第１の細線化部１１２は、差分抽出部１１１から出力される追記抽出画像データに対して細線化処理を実行する。第２の細線化部１１３は、追記ドキュメント画像データに対して細線化処理を実行する。
【００３５】
ここに、第１，第２の細線化部１１２，１１３での細線化処理とは、処理対象の画像に含まれる線分を、太い線も細い線も一律に、線分の中心を表す線幅が例えば１画素（ドット）の線に変換する処理を言う。具体的には、細線化処理では、例えば、着目画素を左上から右下へ移動させながら、その周りの画素値パターンによって着目画素の画素値を変更する。
【００３６】
図７に、第１，第２の細線化部１１２，１１３が実行する細線化処理の具体例を示す。第１の細線化部１１２は、図７（ａ）に示すように、差分抽出部１１１での差分抽出によって抽出した追記情報のみからなる追記抽出画像データ２５４に対して細線化処理を施すことにより、第１の細線化画像である細線化追記抽出画像２５５を生成し、当該細線化追記抽出画像２５５を欠損線分特定部１１４に対して出力する。この細線化処理により、細線化追記抽出画像２５５は欠損部を含む線分画像となる。
【００３７】
一方、第２の細線化部１１３は、図７（ｂ）に示すように、原本情報および追記情報の双方を含む追記ドキュメント画像データ２５６に対して細線化処理を施すことにより、第２の細線化画像である細線化追記ドキュメント２５６を生成し、当該細線化追記ドキュメント２５６を欠損線分特定部１１４に対して出力する。
【００３８】
なお、追記抽出画像データの細線化処理の前処理として、当該追記抽出画像データに対して膨張処理を施して太線化を実行し、微小な欠損部分を消滅させた後、細線化処理を実行する構成を採るようにしても良い。ここに、膨張処理（太線化処理）とは、線分などの有効画像領域を上下左右にｎ画素膨らませる処理を言う。この膨張処理により、微小な欠損部分を消滅させることが可能となる。その後、細線化処理を実行することで、比較的大きな欠損部分のみが残った細線化データを生成することができる。
【００３９】
（欠損線分特定部）
欠損線分特定部１１４は、第２の細線化部１１３が出力する細線化追記ドキュメント２５６から、第１の細線化部１１２が出力する細線化追記抽出画像２５５の欠損部分に相当する線分を特定して欠損線分画像を生成する。図５に示すように、欠損線分特定部１１４は、ノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４によって構成されている。
【００４０】
ノード位置特定部１１４１は、細線化追記抽出画像２５５における端点および細線化追記ドキュメント２５６における交点、分岐点、端点をノードとし、当該ノードの位置（座標）を特定する。具体的には、着目画素を左上から右下へ移動させながら、その周りの画素値パターンによって交点、分岐点、端点を抽出してノードとし、当該ノードの座標位置を記憶する。
【００４１】
リンク長算出部１１４２は、ノード位置特定部１１４１が特定したノードの座標位置を基に、ノードとノードとの結ぶ細線（以下、「リンク」と記述する）の長さを算出する。具体的には、各ノードからＯＮ画素（白背景における黒画素／黒背景における白画素）を１ドット（画素）ずつたどって、次のノードに到達するまでのドット数（画素数）をリンク長として算出する。
【００４２】
リンク分類部１１４３は、リンク長算出部１１４２が算出したリンク長を基に、各リンクが概ね細線化追記抽出画像２５５と重なるかどうかを検出して、重なり無しリンク集合を抽出する。例えば、全リンクを一つずつ細線化追記抽出画像２５５と重なりが無いかチェックしてゆき、重なるドットが1つでもあるリンクは、それを重なり有りと判定する。
【００４３】
最短リンク集合探索部１１４４は、リンク分類部１１４３が分類した最短リンク集合、即ち重なり無しリンク集合から、細線化追記抽出画像２５５の２端点を最短長で結ぶリンクの集合を探索して欠損線分画像とする。具体的には、細線化追記抽出画像２５５の端点から生成されたノード一つ一つについて、重なり無しリンク集合に属するリンクをつないで他の細線化追記抽出画像の端点から生成されたノードに到達するかどうかを検出し、つながるものがあればそれを最短リンク集合とする。また、複数ある場合は、リンク長の総和が小さい方を最短リンク集合とする。
【００４４】
また、別の方法として、ダイクストラ法を使うこともできる。ダイクストラ法は、カーナビ等で現在地から目的地に至る最短距離経路を求める手法として多用されており、任意のノードを起点に他の全てのノードに到達する最短距離経路、即ち最短リンク集合を一意的に求めることができる。この特性を利用し、細線化追記抽出画像２５５の端点から生成されたノードが最短距離で到達できる他の追記画像細線の端点から生成されたノードおよびその経路を一意的に求めることができる。
【００４５】
（合成部）
合成部１１５は、欠損線分特定部１１４が特定した欠損線分画像と、第１の細線化部１１２が追記抽出画像データから生成した細線化追記抽出画像との合成処理を実行して、修復追記抽出画像データとして出力する。この合成処理では、欠損線分特定部１１４の最短リンク集合探索部１１４４が探索した最短リンク集合に相当する細線化追記抽出画像２５５上の画素をＯＮ画素（画像を表示する有効画素）にする画素値変更を行う。
【００４６】
合成部１１５の処理例について、図８を参照して説明する。図８に示す細線化追記抽出画像２５５は、第１の細線化部１１２が追記抽出画像データから生成した細線化追記抽出画像データに基づく画像である。また、図８に示す欠損線分特定部１１４の出力画像２７１は、欠損線分特定部１１４が細線化追記ドキュメント２５６から特定した、細線化追記抽出画像２５５の欠損部分に相当する欠損線分によって構成される画像である。本例の場合、出力画像２７１には、５つの欠損線分ａ，ｂ，ｃ，ｄ，ｅが含まれている。
【００４７】
合成部１１５は、これら図８に示す細線化追記抽出画像２５５と欠損線分特定部１１４の出力画像２７１とを合成する処理を行う。この合成処理の結果、図８に示す修復追記抽出画像データ２８１が生成される。
【００４８】
以上説明した実施例１に係る画像処理装置１００Ａの各構成要素、即ち差分抽出部１１１、第１，第２の細線化部１１２，１１３、欠損線分特定部１１４および合成部１１５、さらには欠損線分特定部１１４を構成するノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４については、パーソナルコンピュータ（ＰＣ）のように、所定プログラムを実行することによって情報記憶処理、画像処理、演算処理等の各機能を実行するコンピュータ機器を利用してソフトウェア構成によって実現することが考えられる。ただし、ソフトウェア構成による実現に限られるものではなく、ハードウェア構成、あるいはハードウェアとソフトウェアの複合構成によって実現することも可能である。
【００４９】
ソフトウェア構成によって実現する場合、差分抽出部１１１、第１，第２の細線化部１１２，１１３、欠損線分特定部１１４および合成部１１５、さらにはノード位置特定部１１４１、リンク長算出部１１４２、リンク分類部１１４３および最短リンク集合探索部１１４４としてコンピュータを機能させるプログラムが本発明による画像処理プログラムとなる。
【００５０】
また、以下に説明する画像処理シーケンスにおける各ステップの処理を実行するプログラムが、本発明による画像処理プログラムであるとも言える。そして、これらの画像処理プログラムについては、あらかじめコンピュータ内にインストールしておくことが考えられる。ただし、あらかじめインストールされているのではなく、コンピュータ読み取り可能な記憶媒体に格納されて提供されるものであっても良く、または有線若しくは無線による通信手段を介して配信されるものであっても良い。
【００５１】
（欠損部の修復処理）
次に、上記構成の実施例１に係る画像処理装置１００Ａにおいて、ＣＰＵ１０１（図４参照）による制御の下に実行する、追記抽出画像の欠損部分を修復する画像処理の処理シーケンスの手順の一例について、図９および図１０のフローチャートにしたがって説明する。
【００５２】
先ず、差分抽出（差分抽出部１１１での処理に相当）によって抽出した追記情報のみからなる追記抽出画像に対して細線化処理を行って細線化追記抽出画像とし（ステップＳ１１）、次いで原本情報および追記情報の双方を含む追記ドキュメントに対して細線化処理を行って細線化追記ドキュメントとする（ステップＳ１２）。これらの細線化処理は、図５の第１，第２の細線化部１１２，１１３の処理に相当する。
【００５３】
次に、図７（ａ）から明らかなように、欠損部を多数含む線分画像である細線化追記抽出画像のノード（端点）を抽出し、抽出したノードの各々に識別子であるノードＩＤを付与するとともに、各ノードの位置（座標）を取得する（ステップＳ１３）。この時点における細線化追記抽出画像のノード数（端点数）をＮｍとする。次いで、細線化追記ドキュメントのノード（端点・交点・分岐点）を抽出し、抽出したノードの各々にノードＩＤを付与するとともに、各ノードの位置（座標）を取得する（ステップＳ１４）。細線化追記ドキュメントの全ノード数をＮｎとする。
【００５４】
次に、ノードＩＤの番号ｉをｉ＝１に設定し（ステップＳ１５）、次いで、ノード（ＩＤ＝ｉ）の分岐数Ｎｂを取得する（ステップＳ１６）。例えば、図１１に示すように、ノード（ＩＤ＝ｉ）が端点（Ａ）の場合はＮｂ＝１、分岐点（Ｂ）の場合はＮｂ＝３、交点（Ｃ）の場合はＮｂ＝４となる。ステップＳ１３〜ステップＳ１６までの各処理は、図５のノード位置特定部１１４１の処理に相当する。
【００５５】
次に、分岐数Ｎｂの番号ｊをｊ＝１に設定し（ステップＳ１７）、次いで、他のノードに到達するまでの細線をたどって２つのノード間の距離をリンク長Ｌとする（ステップＳ１８）。具体的には、あるノードからＯＮ画素を１ドット（画素）ずつたどって、他のノードに到達するまでのドット数（画素数）をリンク長Ｌとする。このステップＳ１７の処理は、図５のリンク長特定部１１４２の処理に相当する。
【００５６】
次に、両端のノードＩＤとリンク長とをリンクリストに記録し（ステップＳ１９）、次いで、分岐数Ｎｂの番号ｊをインクリメント（ｊ＝ｊ＋１）し(ステップＳ２０)、次いで、ノードＩＤの番号ｉが分岐数Ｎｂ以下（ｉ≦Ｎｂ）であるか否かを判断し（ステップＳ２１）、ｉ≦Ｎｂであれば、ステップＳ１８に戻って、ステップＳ１８〜ステップＳ２０の各処理を、ステップＳ２１でｉ＞Ｎｂと判定するまで繰り返して実行する。
【００５７】
ｉ＞Ｎｂであれば、分岐数Ｎｂの番号ｊをインクリメント（ｊ＝１＋１）し（ステップＳ２２）、次いで、ノードＩＤの番号ｉが全ノード数Ｎｎ以下（ｉ≦Ｎｎ）であるか否かを判断し（ステップＳ２３）、ｉ≦Ｎｎであれば、ステップＳ１６に戻って、ステップＳ１６〜ステップＳ２２の各処理を、ステップＳ２３でｉ＞Ｎｎと判定するまで繰り返して実行する。
【００５８】
このステップＳ１６〜ステップＳ２３までの処理ループは、リンクリストを作成するための処理ループである。ここで、リンクリストを作成する処理について、理解を容易にするために、図１２に示す簡易な線分図形を例に挙げて具体的に説明する。
【００５９】
図１２に示す簡易な線分図形では、ノードが７個（Ｎｎ＝７）存在する。これら７個のノードに対して、図の左上から右下への走査順にノードＩＤを付与する（ＩＤ＝１〜ＩＤ＝７）。ここで、ＩＤ＝１，ＩＤ＝２，ＩＤ＝４，ＩＤ＝６，ＩＤ＝７の５個のノードは端点（Ｎｂ＝１）である。ＩＤ＝３のノードは交点（Ｎｂ＝４）である。ＩＤ＝５は分岐点（Ｎｂ＝３）である。
【００６０】
これら７個のノード（ＩＤ＝１〜７）において、ＩＤ＝１のノードから順番のリンク長Ｌを求める。ここで、２つのノードにおいて、リンク長を求めるために細線をたどる際の出発側のノードをノード１、到達側のノードをノード２とする。
【００６１】
先ず、ｉ＝１のときは、Ｎｂ＝１、出発側のノード１はＩＤ＝１のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝１のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ１とする。次に、ｉ＝２のときは、Ｎｂ＝１、出発側のノード１はＩＤ＝２のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝１のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ２とする。
【００６２】
次に、ｉ＝３のときは、Ｎｂ＝４、出発側のノード１はＩＤ＝３のノードであり、当該ノードが交点であることから、４個の分岐（ｊ＝１〜４）についてリンク長Ｌを求めることになる。先ず、ｊ＝１のとき、到達側のノード２はＩＤ＝１のノードであり、ＩＤ＝３のノードからＩＤ＝１のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ１とする。ｊ＝２のとき、到達側のノード２はＩＤ＝２のノードであり、ＩＤ＝３のノードからＩＤ＝２のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ２とする。ｊ＝３のとき、到達側のノード２はＩＤ＝５のノードであり、ＩＤ＝３のノードからＩＤ＝５のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ４とする。ｊ＝４のとき、到達側のノード２はＩＤ＝４のノードであり、ＩＤ＝３のノードからＩＤ＝４のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ３とする。
【００６３】
次に、ｉ＝４のときは、出発側のノード１はＩＤ＝４のノードで、当該ノードが端点であり（ｊ＝１）、到達側のノード２はＩＤ＝３のノードとなる。そして、ＩＤ＝４のノードからＩＤ＝３のノードまでの細線をたどって求めた両ノード間のリンク長ＬをＬ３とする。以降、同様にして、ｉ＝５，６，７について、出発側のノード１から到達側のノード２までの細線をたどってリンク長Ｌを求める。そして、このようにして求めたノード１，２のノードＩＤと両ノード１，２間のリンク長Ｌとからリンクリストが作成される。図１３に、上記具体例の場合に作成されるリンクリストの一例を示す。
【００６４】
ここで、図１３のリンクリストから明らかなように、上述したリンクリストの作成処理の場合には、同じ２つのノード間のリンク長が重複して求められることになる。例えば、ｉ＝３のときに、ｊ＝１で求めたＩＤ＝３のノードとＩＤ＝１のノードとの間のリンク長Ｌ１は、ｉ＝１，ｊ＝１で求めたＩＤ＝１のノードとＩＤ＝３のノードとの間のリンク長Ｌ１と同じであり、ｊ＝２で求めたＩＤ＝３のノードとＩＤ＝２のノードとの間のリンク長Ｌ２は、ｉ＝２，ｊ＝１で求めたＩＤ＝２のノードとＩＤ＝３のノードとの間のリンク長Ｌ２と同じである。また、ｉ＝４，ｊ＝１で求めたＩＤ＝４のノードとＩＤ＝３のノードとの間のリンク長Ｌ３は、ｉ＝３，ｊ＝４で求めたＩＤ＝３のノードとＩＤ＝４のノードとの間のリンク長Ｌ３と同じである。
【００６５】
このように、一度求めたノード間（リンク）のリンク長Ｌについては、同じノード間のリンク長が既に求められているか否かの判断ステップを追加して、同じノード間のリンク長について重複して求めないようにすることも可能である。このようにして、重複した処理を省略することにより、リンクリストを作成する処理の処理スピードを上げることができる。
【００６６】
追記抽出画像の欠損部分を修復する処理シーケンスに説明を戻す。以降では、図１０のフローチャートにしたがって説明する。
【００６７】
上述した処理ループによるリンクリストの作成が完了したら、当該リンクリストから重複するリンクを削除し、残った各リンクの画像とそれに相当する位置の細線化追記抽出画像とで論理積（ＡＮＤ）をとり、その論理積結果にＯＮ画素があれば、即ち細線化追記抽出画像と重なる画素（ドット）が1つでもあれば、重なり有りと判定してそのリンクをリンクリストから除外する（ステップＳ２４）。このステップＳ２４の処理は、図５のリンク分類部１１４３の処理に相当する。
【００６８】
ここで、上述したように、リンクリストの作成処理において、同じノード間のリンク長について重複して求めないようにする場合には、ステップＳ２４におけるリンクリストから重複するリンクを削除する処理は不要となる。これにより、リンクリストから重複するリンクを削除する処理を省く分だけステップＳ２４の処理を高速化できる。
【００６９】
次に、ノードＩＤの番号ｉをｉ＝１に設定し（ステップＳ２５）、次いで、ステップＳ２４で分類した最短リンク集合、即ち重なり無しリンク集合から、細線化追記抽出画像２５５の２端点を最短長で結ぶリンクの集合を探索する（ステップＳ２６）。具体的には、ノード（ＩＤ＝１）から他のノードに至る距離を近い順に求め、ノード（ＩＤ≦Ｎｍ）にぶつかったら、それに至るまでの最短リンク集合とする。このステップＳ２６の処理は、図５の最短リング集合探索部１１４４の処理に相当する。
【００７０】
次に、ステップＳ２６で探索した最短リンク集合に相当する細線化追記抽出画像上の画素をＯＮ画素（有効画素）に画素値変更を行うことで、細線化追記抽出画像と欠損線分画像とを合成する（ステップＳ２７）。次に、ノードＩＤの番号ｉをインクリメント（ｉ＝１＋１）し（ステップＳ２８）、次いで、ノードＩＤの番号ｉがステップＳ１３で取得したノード数（端点数）Ｎｍ以下（ｉ≦Ｎｍ）であるか否かを判断し（ステップＳ２９）、ｉ≦Ｎｍであれば、ステップＳ２６に戻って、ステップＳ２６〜ステップＳ２８の各処理を、ステップＳ２９でｉ＞Ｎｍと判定するまで繰り返して実行する。
【００７１】
このステップＳ２６〜ステップＳ２９までの処理ループは、細線化追記抽出画像（例えば、図７（ａ）の細線化追記抽出画像２５５）における途切れの端点間を結ぶ最短リンクの組み合わせ（最短リンク集合）を求めるための処理ループである。
【００７２】
上述したように、例えばドキュメントから追記画像（追記情報）を抽出する画像処理において、抽出対象の追記ドキュメント画像と原本ドキュメント画像との差分から抽出される追記情報に含まれる欠損部分を修復する際に、欠損部分に相当する細線（リンク）を細線化追記ドキュメント画像（細線画像）から特定し（見つけ出し）、その特定した細線で欠損部分を修復する手法を採ることにより、どの端点とどの端点とを接続すれば良いのかが明確になるために、特に複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００７３】
また、追記画像の欠損部分に相当する細線化追記ドキュメント画像が複雑に分岐していて、当該欠損部分に相当する細線がどれなのか判別が難しい場合でも、細線の最短リンク集合を探索することで、最も確からしい欠損細線を見つけることができる。
【００７４】
なお、ノード位置特定部１１４１の処理において、細線化追記抽出画像（第１の細線化画像）２５５の端点をノードとするとき、当該細線化追記抽出画像２５５の端点と細線化追記ドキュメント画像（第２の細線化画像）２５６とが重ならない場合に、細線化追記抽出画像２５５の端点に相当する追記ドキュメントの画像上の画素に近接する追記ドキュメント画像２５６上の画素をノードするようにしても良い。この手法を採ることにより、細線化追記抽出画像２５５の端点付近が追記ドキュメント画像２５６とぴったり重ならず、微妙にずれる場合があっても、欠損部分を正確に修復できる。
【００７５】
なお、本実施例１では、原本ドキュメント画像データと、原本に含まれない追記情報を含む追記ドキュメント画像データとを差分抽出部１１１に入力して、当該差分抽出部１１１での差分抽出によって追記情報を抽出する画像処理装置１００Ａに適用した場合を例に挙げて説明したが、本発明は追記情報を抽出する画像処理装置１００Ａへの適用に限られるものではない。以下に、他の適用例に係る別の実施例について説明する。
【００７６】
［実施例２］
図１４は、本発明の実施例２に係る画像処理装置１００Ｂの機能構成例を示すブロック図であり、図中、図５と同等部分には同一符号を付して示している。
【００７７】
実施例１に係る画像処理装置１００Ａは、追記ドキュメント画像データと原本ドキュメント画像データとを入力とし、追記ドキュメント画像データと原本ドキュメント画像データとの差分をとって追記情報を抽出する構成を採っているのに対して、本実施例２に係る画像処理装置１００Ｂは、追記ドキュメント画像データのみを入力とし、当該追記ドキュメント画像データから直接追記情報を抽出する構成を採っている。
【００７８】
この追記ドキュメント画像データからの追記情報の直接抽出は、次の原理によって可能である。すなわち、例えば、原本の記録情報（画像情報）が全て黒色で記録され、追記情報が全て赤色で記録されている追記ドキュメントがある場合は、当該追記ドキュメントから赤色で記録された追記情報のみを抽出する色識別処理によって、追記情報の抽出が可能となる。
【００７９】
本実施例２に係る画像処理装置１００Ｂは、図５の差分抽出部１１６の代わりに追記抽出部１１６を備えており、それ以外の構成は実施例１に係る画像処理装置１００Ａの構成と同じである。すなわち、画像処理装置１００Ｂは、追記抽出部１１６、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成を採り、原本ドキュメントに含まれる文字情報などの色と追記された情報の色とが異なる場合、例えば、原本がすべて黒色の文字や線分によって記録され、追記が赤色で行われている場合に適用可能である。
【００８０】
この画像処理装置１００Ｂにおいて、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５が持つ機能は、実施例１に係る画像処理装置１００Ａの場合と同じであり、その説明については重複するので省略する。追記抽出部１１６は、追記ドキュメント画像データから、所定の色（本例では、追記情報の色である赤）を持つ情報を追記情報として抽出する。なお、追記抽出部１１６が抽出する追記情報の色情報については、ユーザが指定入力するなどの方法が考えられる。
【００８１】
この追記抽出部１１６において抽出された追記情報は、実施例１に係る画像処理装置１００Ａの差分抽出部１１１が生成する追記情報と同様に、やはり、原本に含まれる情報との重なり部分で途切れが発生する場合がある。例えば、原本に含まれる黒の文字上に追記された赤色が正確に赤とは認識されず、黒と認識される場合があり、このような重なり部分を追記抽出部１１６が追記情報として認識しない場合があるからである。
【００８２】
このような途切れ部分（欠損部分）は、実施例１に係る画像処理装置１００Ａの場合と同様に、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５における処理によって修復され、最終的に正確な追記情報からなる修復追記抽出画像データが生成される。その結果、実施例１に係る画像処理装置１００Ａの場合と同様に、スキャン画像の劣化が激しい場合でも、また複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００８３】
［実施例３］
図１５は、本発明の実施例３に係る画像処理装置１００Ｃの機能構成例を示すブロック図であり、図中、図１４と同等部分には同一符号を付して示している。
【００８４】
本実施例３に係る画像処理装置１００Ｃは、図１４の追記抽出部１１６の代わりに罫線分離部１１７を備えており、それ以外の構成は実施例１に係る画像処理装置１００Ａの構成と同じである。すなわち、画像処理装置１００Ｃは、罫線分離部１１７、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５を有する構成を採り、原本ドキュメントが例えば表などの罫線情報によって構成され、その表に元々記載されている文字やユーザが後から追記した文字などを、罫線を含まない記載内容情報として抽出する場合に有効となる。
【００８５】
この画像処理装置１００Ｂにおいて、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５が持つ機能は、実施例１に係る画像処理装置１００Ａの場合と同じであり、その説明については重複するので省略する。罫線分離部１１７は、ドキュメント画像データから、罫線のみを削除することによって記載内容情報を抽出する。
【００８６】
この罫線分離部１１７において抽出された記載内容情報は、実施例１に係る画像処理装置１００Ａの差分抽出部１１１が生成する追記情報と同様に、やはり、表罫線との重なり部分で途切れが発生する場合がある。例えば、罫線上に重なって記録された記載内容情報は、罫線情報として削除され、抽出される記載内容情報に含まれなくなるからである。
【００８７】
このような途切れ部分（欠損部分）は、実施例１に係る画像処理装置１００Ａの場合と同様に、第１の細線化部１１２、第２の細線化部１１３、欠損線分特定部１１４および合成部１１５における処理によって修復され、最終的に正確な記載内容情報からなる修復記載内容抽出画像データが生成される。その結果、実施例１に係る画像処理装置１００Ａの場合と同様に、スキャン画像の劣化が激しい場合でも、また複雑な文字に発生した途切れ部分など、複雑に途切れた部分で端点が密集している場合でも、欠損部分を正確に修復できる。
【００８８】
なお、本発明は、上記実施例１〜３に係る画像処理装置１００Ａ〜１００Ｃへの適用に限られるものではなく、例えば、追記ドキュメント画像に含まれる線分の色や揺らぎなどの特徴から、印刷による情報と手書きによる情報とを判別し、手書きによる追記情報を抽出するなど、原本に含まれない追記情報を含む追記ドキュメント画像データから当該追記情報を抽出する画像処理を行う画像処理装置全般に適用可能である。
【図面の簡単な説明】
【００８９】
【図１】本発明が適用される画像情報処理システムの構成の概略を示すシステム構成図である。
【図２】原本ドキュメントと追記ドキュメントとの差分処理によって追記情報を取得する処理例についての説明図である。
【図３】追記情報を取得する他の処理例についての説明図である。
【図４】本発明による画像処理装置を含む画像情報処理システムのより具体的な構成例を示すブロック図である。
【図５】本発明の実施例１に係る画像処理装置の機能構成例を示すブロック図である。
【図６】原本ドキュメントと追記ドキュメントとから差分を抽出する処理例についての説明図である。
【図７】細線化処理の具体例についての説明図である。
【図８】合成処理の具体例についての説明図である。
【図９】追記抽出画像の欠損部分を修復する処理シーケンスの手順の一例を示すフローチャート（その１）である。
【図１０】追記抽出画像の欠損部分を修復する処理シーケンスの手順の一例を示すフローチャート（その２）である。
【図１１】ノード（ＩＤ＝ｉ）の分岐数Ｎｂについての説明図である。
【図１２】リンクリストを作成する処理についての簡易な線分図形を用いた説明図である。
【図１３】リンクリストの一例を示す図である。
【図１４】本発明の実施例２に係る画像処理装置の機能構成例を示すブロック図である。
【図１５】本発明の実施例３に係る画像処理装置の機能構成例を示すブロック図である。
【符号の説明】
【００９０】
１０…原本ドキュメント、２０…追記ドキュメント、３０…スキャナ、４１…画像データ入力部、４２…画像データ出力部、１００，１００Ａ，１００Ｂ，１００Ｃ…画像処理装置、１１１…差分抽出部、１１２…第１の細線化部、１１３…第２の細線化部、１１４…欠損線分特定部、１１５…合成部、１１６…追記抽出部、１１７…罫線分離部
【特許請求の範囲】
【請求項１】
所定の画像から所定の情報を抽出する情報抽出手段と、
前記情報抽出手段が抽出した情報に対して細線化処理を実行する第１の細線化手段と、
前記所定の画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項２】
原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する追記情報抽出手段と、
前記追記情報抽出手段が抽出した追記情報に対して細線化処理を実行する第１の細線化手段と、
前記追記ドキュメントの画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項３】
ドキュメントの画像から表罫線の情報を分離してドキュメントに記載されている記載内容情報を抽出する記載内容情報抽出手段と、
前記記載内容情報抽出手段が抽出した記載内容情報に対して細線化処理を実行する第１の細線化手段と、
前記ドキュメントの画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項４】
前記欠損線分特定手段は、
前記第１の細線化画像の端点と前記第２の細線化画像の交点、分岐点および端点とをノードとするとき、当該ノードの位置を特定するノード位置特定手段と、
ノードとノードとを結ぶリンクの長さを計算するリンク長算出手段と、
前記リンク長算出手段が算出した各リンクが前記第１の細線化画像と重なるか否かを判断して重ならないリンク集合を抽出するリンク分類手段と、
前記リンク分類手段が抽出したリンク集合から前記第１の細線化画像の２端点を最短長で結ぶ重なり無しの最短リンク集合を探索して前記欠損線分画像とする最短リンク集合探索手段とを有する
ことを特徴とする請求項１記載の画像処理装置。
【請求項５】
前記合成手段は、前記最短リンク集合探索手段が探索した最短リンク集合に相当する前記第１の細線化画像上の画素を有効画素にすることにより、前記欠損線分画像と前記第１の細線化画像とを合成する
ことを特徴とする請求項２記載の画像処理装置。
【請求項６】
前記ノード位置特定手段は、前記第１の細線化画像の端点をノードとするとき、当該第１の細線化画像の端点と前記第２の細線化画像とが重ならない場合に、前記第１の細線化画像の端点に相当する前記追記ドキュメントの画像上の画素に近接する前記第２の細線化画像上の画素をノードとする
ことを特徴とする請求項２記載の画像処理装置。
【請求項７】
原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する追記情報抽出ステップと、
前記追記情報抽出ステップで抽出した追記情報に対して細線化処理を実行する第１の細線化ステップと、
前記追記ドキュメントの画像に対して細線化処理を実行する第２の細線化ステップと、
前記第２の細線化ステップで細線化した第２の細線化画像から、前記第１の細線化ステップで細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定ステップと、
前記欠損線分特定ステップで生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成ステップと
の各処理をコンピュータに実行させることを特徴とする画像処理プログラム。
【請求項１】
所定の画像から所定の情報を抽出する情報抽出手段と、
前記情報抽出手段が抽出した情報に対して細線化処理を実行する第１の細線化手段と、
前記所定の画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項２】
原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する追記情報抽出手段と、
前記追記情報抽出手段が抽出した追記情報に対して細線化処理を実行する第１の細線化手段と、
前記追記ドキュメントの画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項３】
ドキュメントの画像から表罫線の情報を分離してドキュメントに記載されている記載内容情報を抽出する記載内容情報抽出手段と、
前記記載内容情報抽出手段が抽出した記載内容情報に対して細線化処理を実行する第１の細線化手段と、
前記ドキュメントの画像に対して細線化処理を実行する第２の細線化手段と、
前記第２の細線化手段が細線化した第２の細線化画像から、前記第１の細線化手段が細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定手段と、
前記欠損線分特定手段が生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成手段と
を備えることを特徴とする画像処理装置。
【請求項４】
前記欠損線分特定手段は、
前記第１の細線化画像の端点と前記第２の細線化画像の交点、分岐点および端点とをノードとするとき、当該ノードの位置を特定するノード位置特定手段と、
ノードとノードとを結ぶリンクの長さを計算するリンク長算出手段と、
前記リンク長算出手段が算出した各リンクが前記第１の細線化画像と重なるか否かを判断して重ならないリンク集合を抽出するリンク分類手段と、
前記リンク分類手段が抽出したリンク集合から前記第１の細線化画像の２端点を最短長で結ぶ重なり無しの最短リンク集合を探索して前記欠損線分画像とする最短リンク集合探索手段とを有する
ことを特徴とする請求項１記載の画像処理装置。
【請求項５】
前記合成手段は、前記最短リンク集合探索手段が探索した最短リンク集合に相当する前記第１の細線化画像上の画素を有効画素にすることにより、前記欠損線分画像と前記第１の細線化画像とを合成する
ことを特徴とする請求項２記載の画像処理装置。
【請求項６】
前記ノード位置特定手段は、前記第１の細線化画像の端点をノードとするとき、当該第１の細線化画像の端点と前記第２の細線化画像とが重ならない場合に、前記第１の細線化画像の端点に相当する前記追記ドキュメントの画像上の画素に近接する前記第２の細線化画像上の画素をノードとする
ことを特徴とする請求項２記載の画像処理装置。
【請求項７】
原本ドキュメントに対して追記処理のなされた追記ドキュメントの画像から追記情報を抽出する追記情報抽出ステップと、
前記追記情報抽出ステップで抽出した追記情報に対して細線化処理を実行する第１の細線化ステップと、
前記追記ドキュメントの画像に対して細線化処理を実行する第２の細線化ステップと、
前記第２の細線化ステップで細線化した第２の細線化画像から、前記第１の細線化ステップで細線化した第１の細線化画像の欠損部分に相当する線分を特定して欠損線分画像を生成する欠損線分特定ステップと、
前記欠損線分特定ステップで生成した欠損線分画像と前記第１の細線化画像とを合成して修復追記抽出画像を生成する合成ステップと
の各処理をコンピュータに実行させることを特徴とする画像処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００７−２３３８８９（Ｐ２００７−２３３８８９Ａ）
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願番号】特願２００６−５７１６０（Ｐ２００６−５７１６０）
【出願日】平成１８年３月３日（２００６．３．３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願日】平成１８年３月３日（２００６．３．３）
【出願人】（０００００５４９６）富士ゼロックス株式会社 (21,908)
【Ｆターム（参考）】
[ Back to top ]