(57)【要約】【課題】どのような色でどのような書き込みが行われても、その書き込みを精度よく抽出できる手法を提供する【解決手段】文書画像に書き込みが付加されてなる画像から書き込みを抽出する方法であって、書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する工程と、元画像と書込み画像とを比較して両画像の位置合わせを行う工程と、位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から類似した局所領域を求めることにより対の各局所領域を決定する工程と、対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する工程とをコンピュータが処理することを特徴とする書込み抽出方法。【選択図】図１
2008219800.tif 000002
【特許請求の範囲】
【請求項１】
文書画像に書き込みが付加されてなる画像から書き込みを抽出する方法であって、
書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する工程と、
元画像と書込み画像とを比較して両画像の位置合わせを行う工程と、
位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から類似した局所領域を求めることにより対の各局所領域を決定する工程と、
対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する工程と
をコンピュータが処理することを特徴とする書込み抽出方法。
【請求項２】
前記局所領域は、１またはそれ以上の画素を単位とする領域である請求項１記載の書き込み抽出方法。
【請求項３】
局所領域を書き込みとして抽出する工程は、対にされた局所領域の色成分の差分が所定の閾値よりも大きい場合、その対のうち書込み画像の局所領域を出力する工程である請求項１記載の書込み抽出方法。
【請求項４】
画像の位置合わせを行う工程は、元画像と書込み画像をそれぞれ色クラスタリングし、色クラスタリングされた各画像について元画像と書込み画像との対応をとる処理を含む請求項１記載の書込み抽出方法。
【請求項５】
画像の位置合わせを行う工程は、元画像と書込み画像から特徴点をそれぞれ抽出し、抽出された各特徴点について元画像と書込み画像との対応をとる処理を含む請求項１記載の書込み抽出方法。
【請求項６】
局所領域を書き込みとして抽出する工程の後に、抽出された書込みを整形して出力する整形工程をさらにコンピュータに処理させ、
前記整形工程は、書込みとして抽出された局所領域を透過部とし、前記透過部の領域をさらに所定量だけ拡張してなるマスクパターンを得る工程と、
得られたマスクパターンを元画像に重ね合わせ、拡張された透過部に重なる部分の元画像を出力する工程とを含んでなる請求項１記載の書込み抽出方法。
【請求項７】
マスクパターンを得る工程は、抽出された書込みの各局所領域を２値化する工程と、
２値化された各局所領域に対して連結処理を行う工程とを含む請求項６記載の書込み抽出方法。
【請求項８】
マスクパターンを得る工程は、連結処理により生成される書込みの領域のうち所定の面積よりも小さい領域を除去する工程をさらに含む請求項７記載の書込み抽出方法。
【請求項９】
文書画像に書き込みが付加されてなる書込み画像から書き込みを抽出する装置であって、
書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する画像取得部と、
元画像と書込み画像とを比較して両画像の位置合わせを行う位置合わせ部と、
位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から局所領域の色成分が最も近い局所領域を求めることにより対の各局所領域を決定する対局所領域決定部と、
対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する書込み抽出部とを備える書込み抽出装置。
【請求項１０】
文書画像に書き込みが付加されてなる書込み画像から書き込みを抽出する処理を実行させるためのプログラムであって、
書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する画像取得部と、
元画像と書込み画像とを比較して両画像の位置合わせを行う位置合わせ部と、
位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から局所領域の色成分が最も近い局所領域を求めることにより対の各局所領域を決定する対局所領域決定部と、
対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する書込み抽出部としての機能をコンピュータに実行させることを特徴とする書込み抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、文書に書き込みが付加されたものから書き込みを抽出する書込み抽出方法、書込み抽出装置および書込み抽出プログラムに関する。
【背景技術】
【０００２】
紙などの印刷媒体上に記された文書（紙文書）は高い可読性および可搬性を持つため、多くの情報が紙文書を介して提供されている。また、紙文書に対して注目した部分に印をつけたり、メモを書き込むなどの書き込み行為は一般的である。従って、紙文書における書き込みには利用者の興味や知識などの情報が豊富に蓄積されているといえ、書き込みを抽出・解析することで貴重な情報を得ることができると考えられる。具体的には、a)ユーザによる書き込みの閲覧、b) 書き込みの大まかな位置の同定、に用いることが考えられる。
【０００３】
前述の用途を考えると、必ずしも書き込みの領域を正確にトレースする必要はなく、人間にとって読みやすいことが重要である。正確な抽出を行おうとすると，しばしば，書き込みの抽出が不十分（分断して抽出されるなど）となり、ユーザによる可読性が低下する。分断などは、位置の同定にも悪影響を及ぼす。逆に、書き込み以外を抽出しても可読性には影響がない。
【０００４】
これまでに、紙文書から書き込みを抽出する様々な手法（例えば、非特許文献１，２，３および４）が提案されている。これらの手法は、機械による認識を念頭に置いたものであり、高い精度で書き込みを抽出するために、書き込みの色や種類に制限を課している。しかし、実環境で行われる書き込みには制限は存在しないため、どのような色でどのような書き込みが行われても、その抽出が可能な手法が必要である。
より詳細に説明すると、前述の従来手法は、以下の2つのタイプに分類される。
第１のタイプは書き込みの抽出ではなく、書き込みを用いた自動校正などの抽出された書き込みの利用に重点を置いたもの（非特許文献１，２）である。これらの手法では、抽出結果が機械で利用されるため、高精度な抽出が求められる。その実現のため、これらの手法では書き込みに制限を設けている。具体的には、書き込みに用いることのできるペンの色があらかじめ定められており、スキャンされた画像の画素の色によって書き込みであるか否かを判断する。そのため、これらの手法では書き込みの色に制限がある。
第２のタイプは、画像における連結成分を手書き文字と印刷された文字に分類するもの（非特許文献３，４）である。これらの手法では、書き込みのなされた文書の画像のみから書き込み抽出が可能であるという長所がある一方、抽出できる書き込みは文字に限られており、手書きの線や図形などを抽出することはできない。実際の書き込みでは下線や矢印などの図形は頻繁に用いられるため、そのような書き込みを抽出できる手法が必要である。
【０００５】
なお、この発明に関連する手法として、発明者らは、特徴点の局所的配置に基づく文書画像検索法を提案している（例えば、特許文献１、非特許文献５参照）。以下の説明では、この提案手法を単に文書画像検索法という。本願発明と前記文書画像検索法との関連については、後に説明する。
【特許文献１】国際公開第２００６／０９２９５７号パンフレット
【非特許文献１】D. Mori and H. Bunke, "Automatic Interpretation and Execution of Manual Corrections on Text Documents", in Handbook of Character Recognition and Document Image Analysis, ed. H. Bunke and P. S. P. Wang, pp.679-702, World Scientific, Singapore (1997).
【非特許文献２】J. Stevens, A. Gee, and C. Dance, "Automatic Processing of Document Annotations", In Proc. 1998 British Machine Vision Conf., Vol. 2, pp.438-448 (1998).
【非特許文献３】J. K. Guo and M. Y. Ma, "Separating Handwritten Material from Machine Printed Text using Hidden Markov Models", In Proc. 6th International Conf. on Document Analysis and Recognition, pp.436-443 (2001).
【非特許文献４】Y. Zheng, H. Li, and D. Doermann, "The Segmentation and Identification of Handwriting in Noisy Document Images", In Lecture Notes in Computer Science (5th International Workshop DAS2002), vol.2423, pp.95-105 (2002).
【非特許文献５】中居、黄瀬、岩村：「デジタルカメラを用いた高速文書画像検索におけるアフィン不変量及び相似不変量の利用」、信学技報、PRMU2005-188 (2006)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
この発明は、カラーの紙文書に任意の色で書き込みを行った場合でも、あるいは、文字以外に線や図形などを書き込んだ場合であっても、その書き込みを精度よく抽出できる手法を提供するものである。より詳細には、この発明は、書き込み対象の紙文書の画像（元画像）が利用可能であることを前提とし、書き込みの含まれる文書画像（書き込み画像）と元の文書画像との差分を求めることで書き込みを抽出するものである。
本発明では、前述の分断が起きるなど、書き込みの抽出が不十分にならないように、書き込みの領域を余計目に抽出する。これによって、書き込み以外の部分が、書き込みに混ざって抽出されることもあり得るが、ユーザによる閲覧や位置の同定にはそれほど悪影響を及ぼさない。
【課題を解決するための手段】
【０００７】
この発明は、文書画像に書き込みが付加されてなる画像から書き込みを抽出する方法であって、書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する工程と、元画像と書込み画像とを比較して両画像の位置合わせを行う工程と、位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から類似した局所領域を求めることにより対の各局所領域を決定する工程と、対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する工程と
をコンピュータが処理することを特徴とする書込み抽出方法を提供する。
【０００８】
また、異なる観点から、この発明は、文書画像に書き込みが付加されてなる書込み画像から書き込みを抽出する装置であって、書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する画像取得部と、元画像と書込み画像とを比較して両画像の位置合わせを行う位置合わせ部と、位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から局所領域の色成分が最も近い局所領域を求めることにより対の各局所領域を決定する対局所領域決定部と、対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する書込み抽出部とを備える書込み抽出装置を提供する。
【０００９】
さらに、異なる観点から、この発明は、文書画像に書き込みが付加されてなる書込み画像から書き込みを抽出する処理を実行させるためのプログラムであって、書き込みが付加される前の元画像と書き込みが付加された後の書込み画像とを色成分で表される局所領域の集合としてそれぞれ取得する画像取得部と、元画像と書込み画像とを比較して両画像の位置合わせを行う位置合わせ部と、位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から局所領域の色成分が最も近い局所領域を求めることにより対の各局所領域を決定する対局所領域決定部と、対にされた局所領域の色成分の差分に基づいて、書込み画像に含まれ、かつ、元画像に含まれない局所領域を書き込みとして抽出する書込み抽出部としての機能をコンピュータに実行させることを特徴とする書込み抽出プログラムを提供する。
【発明の効果】
【００１０】
この発明の書込み抽出方法は、位置合わせがなされた両画像の一方の画像の各局所領域について、それに対応する位置もしくはそれから所定範囲内の位置にある他方の画像の局所領域を対の候補とし、対の候補の中から局所領域の色成分が最も近い局所領域を求めることにより対の各局所領域を決定するので、両画像の対応する位置にある局所領域を対にする場合に比べ、より正確に書き込みを抽出することができる。換言すれば、元画像と書込み画像との位置合わせを局所領域単位で厳密に行わなくても、正確に対応局所領域を決定することができる。局所領域単位の厳密な位置合わせが不要になるので、位置合わせに時間を費やすことなく精度のよい抽出結果を得ることができる。
また、従来手法のような制約がないので、カラーの紙文書に任意の色で書き込みを行った場合でも、あるいは、文字以外に線や図形などを書き込んだ場合であっても、その書き込みを精度よく抽出することができる。
【００１１】
ここで、文書画像とは、文字および／または画像からなる情報が画像として表されたものをいう。さらに、前記画像が電子データ化された画像データも文書画像に含む。
【００１２】
書き込みとは、文書画像に対して付加された可視的な情報をいう。書き込みは、文字、線図などから構成される画像である。多くの場合、書き込みは手書きで付加されるが、それに限定されるものではなく、印刷やスタンプなど他の手法で付加されたものであってもよい。
【００１３】
また、位置合わせとは、書込み画像中の書き込む前から存在した部分と元画像とを重ね合わせるため、一方の画像に施すべき幾何的変換のパラメータを決定し、決定されたパラメータに基づく幾何変換を対象画像に適用する処理をいう。幾何変換は、変換の自由度に応じて射影変換、アフィン変換、相似変換などがある。以下の実施形態では、前記３種類の幾何変換のうち最も自由度の低い相似変換を前提とした位置合わせについて説明している。しかし、この発明の本質は、必ずしもこれに限定されない。
この発明の好ましい態様として、前記局所領域は、１またはそれ以上の画素を単位とする領域であってもよい。ここで、画像の読み取りは、画素単位で行われる。前記局所領域は、各画素に対応するものであってもよいし、所定の配置関係にある複数画素を単位としてもよい。
また、好ましくは、画像の読み取りは、レッド（Ｒ）、グリーン（Ｇ）、ブルー（Ｂ）の各色成分に分解して行われるのが一般的であるので、それらの色成分で表現される画素、即ちＲＧＢ色空間で表現される画素に対して各工程の処理を行うことができる。しかし、この発明は、必ずしもそれに限定されるものではなく、ＲＧＢ色空間以外の色空間で表現される画素に対して適用することができる。他の色空間としては、ＹＭＣ色空間やＬａｂ色空間などが知られており、演算により異なる色空間に変換が可能である。
【００１４】
また、好ましくは、局所領域を書き込みとして抽出する工程は、対にされた局所領域の色成分の差分が所定の閾値よりも大きい場合、その対のうち書込み画像の局所領域を出力する工程であってもよい。このようにすれば、書き込みとして抽出される画像の濃度は、元画像の局所領域の属性を示す値に影響されないので、抽出された書き込みを認識しやすい。
ここで、局所領域の属性を示す値とは、例えば、局所領域が１画素である場合はその画素値（画素の色成分の値）が属性を示す値に相当する。局所領域が複数画素からなる場合は、例えば、それらの各画素値を平均した値が属性を示す値に相当する。あるいは、各画素値に所定の重み付けをして平均してもよいし、その他の手順で算出されてもよい。
【００１５】
好ましくは、画像の位置合わせを行う工程は、元画像と書込み画像をそれぞれ色クラスタリングし、色クラスタリングされた各画像について元画像と書込み画像との対応をとる処理を含んでいてもよい。このようにすれば、色クラスタリングされた各画像について元画像と書込み画像との対応をとるので、カラーの元画像にカラーで書き込みを行った場合でも、精度よく書き込みを抽出することができる。
【００１６】
また、好ましくは、画像の位置合わせを行う工程は、元画像と書込み画像から特徴点をそれぞれ抽出し、抽出された各特徴点について元画像と書込み画像との対応をとる処理を含んでいてもよい。このようにすれば、元画像と書込み画像から抽出された特徴点を用いて位置合わせを行うので、特徴点を用いないで全局所領域を考慮して位置合わせを行う場合に比べて位置合わせに要する処理時間を圧倒的に短縮することができる。即ち、課題を解決するための手段を実現するためには、書き込み画像と元画像を高速かつ正確に位置合わせする必要がある。この問題について、前述した文書画像検索法を用いることができる。前記文書画像検索法と本願発明とは、その解決しようとする課題が異なるものである。しかし、前記文書画像検索法によれば、検索の過程で検索質問の文書画像と検索された文書画像の間で、部分ごとの対応関係を得ることができる。例えば、前記特許文献１の図３０あるいは図４４に検索処理のアルゴリズムが示されているが、このアルゴリズムを本願発明に流用すれば、高速に、および／または、精度よく画像の位置合わせを実現することができる。
【００１７】
また、好ましくは、局所領域を書き込みとして抽出する工程の後に、抽出された書込みを整形して出力する整形工程をさらにコンピュータに処理させ、前記整形工程は、書込みとして抽出された局所領域を透過部とし、前記透過部の領域をさらに所定量だけ拡張してなるマスクパターンを得る工程と、得られたマスクパターンを元画像に重ね合わせ、拡張された透過部に重なる部分の元画像を出力する工程とを含んでなるようにしてもよい。このようにすれば、整形工程がない場合よりも抽出された書き込みの局所領域をより多く抽出できるので、書き込みをより認識し易くできる。色成分の差分を判定する際の閾値の大きさによって、書き込みとして抽出された画像の線部が途切れたり細ったりすることがあるが、このようにすれば線部の途切れや細りを抑制して書き込みの認識を容易にすることができる。
【００１８】
さらに、好ましくは、マスクパターンを得る工程は、抽出された書込みの各局所領域を２値化する工程と、２値化された各局所領域に対して連結処理を行う工程とを含んでいてもよい。このようにすれば、書き込み中の線部の途切れを修復することができる。
【００１９】
さらにまた、好ましくは、マスクパターンを得る工程は、連結処理により生成される書込みの領域のうち所定の面積よりも小さい領域を除去する工程をさらに含んでいてもよい。このようにすれば、抽出された書き込みからドット状のノイズを除去することができるので、この処理を行わない場合に比べて書き込みをより認識し易くできる。
前述の好ましい態様は、組み合わせることができる。
【００２０】
なお、以下の実施形態においては、抽出結果の解析を目視によって行うものと想定しており、書き込みの厳密な抽出よりも良好な視認性を優先させる手法を記載している。ただし、本願発明の本質は、この手法に限定されるものではない。実験の結果、文字を多く含む文書画像については良好な結果が得られることが示された。
【００２１】
この発明の書き込みの抽出法は、元画像が取得可能であるという前提の下で、元画像と書込み画像の位置合わせを行い、差分を取ることで書き込みの抽出を行うものである。この発明の特徴は、大局的なずれのみならず、局所的なずれにも強い柔軟な差分処理である。
さらに、前述の位置合わせは、対応点探索によって幾何変換パラメータを求め、前記文書画像検索法を応用した高速な位置合わせを行うことが非常に好ましい。
【発明を実施するための最良の形態】
【００２２】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
１．処理の流れ
図１は、この発明の書き込み抽出方法の処理の流れを示す説明図である。処理は大きく位置合わせ処理１１と差分取得処理１３とに分かれる。
【００２３】
位置合わせ処理１１では、書き込み画像を元画像に合わせて相似変換し、ずれや回転、スケールの違いを補正する。位置合わせの処理はさらに４つの小さな処理に分けられる。
差分取得処理１３では補正された書き込み画像と元画像を比較し、差分を取ることで書き込み画像に含まれて元画像に含まれない局所領域を書き込みとして出力する。なお、以下の説明では、局所領域が１画素である場合を代表例として説明する。差分取得の処理は６つの小さな処理に分けられる。
【００２４】
２．位置合わせ
2.1. 特徴点抽出
位置合わせにおける第１の処理は、特徴点抽出である。ここでは書き込み画像および元画像から、変形やノイズに対してロバストな（強い）点を特徴点として抽出する。この実施形態では、画像をRGB色空間で色クラスタリングして得られた色ごとの連結成分の重心を特徴点とする。これは、文字などの単色領域の位置を特徴点として用いることを意図したものである。文字は特徴的な配置をもち、また背景とのコントラストが大きいため安定した抽出が可能である。
具体的な処理を以下に述べる。まず、処理の軽減のために画像を縮小する。縮小倍率は、書き込み画像と元画像の両方に対して同じ値Lを用いる。そして、ノイズの影響を減らすためにモルフォロジ演算によって画像をスムージングする。具体的には、3×3の矩形要素によるエロージョン（erosion、即ち浸食）演算をｌ（エル）回繰り返す。次に、画像をX倍に縮小した後、k-means法で画像を画素の色でk個の色クラスタにクラスタリングする。ここで、色クラスタの数kはあらかじめ定められた値である。また、クラスタリングの繰り返し処理は、処理回数がi回を超えたとき、または重心の移動距離がpを下回ったときに打ち切られる。
【００２５】
次に、図２に示すように、色クラスタリングの結果に基づいて対象画像15をk=5枚の色クラスタの画像17a,17b,17c,17dに分解する。このようにして得られた各色クラスタの画像から連結成分を抽出し、その面積を調べて面積がE以上のもの及び面積がe以下のものを除去する。これは、ノイズなどによる微小な領域や、背景などの大きい領域は安定でないと考えられるためである。このようにして残った連結成分の重心を色クラスタごとの特徴点とする。
【００２６】
なお、k-means法は、最終のクラスタ数（グループの数）kと各クラスタの評価基準が与えられたときに、与えられたデータを最適なクラスタに分類する公知の手法である（例えば、高木幹雄・下田陽久監修、画像解析ハンドブック、第１版、東京大学出版会、２００４年９月１０日、p.1576-1579参照）。
【００２７】
2.2. 対応点探索
第２の処理は、対応点検索である。ここでは、書き込み画像の特徴点と元画像の特徴点を、前記文書画像検索法を応用して対応付ける。
【００２８】
この段階では、書き込み画像と元画像のそれぞれがk個の色クラスタごとの特徴点をもつ。色クラスタによってはノイズの特徴点が多く含まれている場合があるため、全クラスタの特徴点をまとめてから対応付けるのではなく、色クラスタごとに対応付ける方が正しい対応点を得やすい。そのため、特徴点同士の対応付けに先立って、書き込み画像の色クラスタと元画像の色クラスタの1対1の対応付けを行う。この実施形態では、色クラスタのRGB色空間での重心の距離の最も小さいものから対応付ける。具体的には以下の処理のようになる。まず、書き込み画像の色クラスタと元画像の色クラスタのすべての組み合わせについて距離を求める。次に、最も距離の小さい組を対応付ける。そして、距離の小さい組を順に対応付けていく。ただし、既に組のいずれかの色クラスタが対応付けられていた場合は対応付けを行わない。この処理をすべての書き込み画像の色クラスタと元画像の色クラスタの対応が1対1で決定するまで繰り返し行う。
【００２９】
次に、対応付けられた色クラスタの組ごとに特徴点の対応付けを行う。これは、前記文書画像検索法のように、元画像の特徴点をデータベースに登録し、書き込み画像の各特徴点に対して対応するものを検索するという処理を対応付けられた色クラスタの各組に対して行うことで実現される。ただし、登録される画像が1つだけである点が前記文書画像検索法の場合と異なっている。なお、対応点探索で用いられるパラメータは、特徴量計算を行う近傍点の範囲n、特徴量計算に用いる点の数m、特徴量の離散化レベル数dである。
上記の処理により、特徴点の対応関係は、色クラスタの組ごとに得られる。画像全体の対応関係は、すべての色クラスタの対応関係を集めることによって得られる。図３に特徴点同士の対応関係を示す。
【００３０】
2.3. 相似変換パラメータの取得
第３の処理は、相似変換パラメータの取得である。ここでは、特徴点の対応関係に基づいて相似変換パラメータを取得する。相似変換パラメータは、拡大縮小、回転、ｘおよびｙ軸方向の並進の各要素からなる4次元のベクトルである。相似変換パラメータは、2組の対応点から計算される。しかし、この実施の形態における対応点には、誤ったものが含まれている場合があるため、誤った対応点を除いて変換パラメータを計算する必要がある。そこで、RANSACを用いて変換パラメータの推定を行う。RANSACは、複数の画像間の特徴点の対応を定めるのに多用される公知の手法である（例えば、M.A.Fischler and R.C.Bolles, "Random Sample Consensus: A Paradigm for Model Fitting with Application to Image Analysis and Automated Cartography", Comm. ACM, Vol.6, No.24, pp.381-395 (1981)を参照）。
【００３１】
変換パラメータの推定アルゴリズムを図４に示す。まず、対応関係の集合からランダムに2つの対応関係を選ぶ（図４の２行目）。そして、2つの対応関係から相似変換パラメータを求める（３行目）。次に、得られた相似変換パラメータの評価を行う。これは、相似変換パラメータを支持する対応関係の数をスコアとすることで行われる（４行目）。具体的には、対応関係の書き込み画像側の点をパラメータによって変換し、得られた点の座標と対応関係の元画像側の点の座標との距離を求めて、閾値ｔ以下であれば対応関係がパラメータを支持するとみなす。このような処理をT回繰り返し（１〜６行目のforループ）、最大のスコアが閾値以上であれば（７行目）最大のスコアを得たパラメータを推定結果とする（８行目）。そうでなければ推定失敗とする（１０行目）。
【００３２】
2.4. 相似変換処理
第４の処理は、相似変換処理である。ここまでの処理で得られた相似変換パラメータを用いて、書き込み画像に相似変換を適用し、元画像への位置合わせを行う。これにより、元画像と同じ大きさの補正された書き込み画像が得られる。
【００３３】
３．差分取得
3.1. 前処理
前述のように、差分取得処理１３は、６つの小さな処理に分けられる。第１の処理は、前処理である。ここでは以降の処理を適切に行うため、補正された書き込み画像と元画像に対して画像処理を施す。
まず、処理の軽減のため書き込み画像および元画像をそれぞれZ倍、z倍に縮小する。
次に、書き込み画像にカーネルの大きさがg×gのガウシアンフィルタを適用し、プリンタで印刷する際に生じるドットパターンの除去を行う。これは、電子文書では中間色となっている部分が印刷の際に原色を用いたドットパターンになるため、そのまま差分をとるとノイズが生じるためである。
【００３４】
元画像に対しても処理を行う。ここで、元画像として2つのパターンを考える。1つは、電子文書から直接得た画像であり、もう1つは、電子文書をプリンタで印刷し、それをスキャナで取り込んで得た画像である。前者の場合は、erosion演算をR回繰り返して画像を太らせる。これは、印刷の際ににじみの生じる書き込み画像との差分を適切に得るためである。後者の場合は、書き込み画像と同様にG×Gのガウシアンフィルタを適用し、ドットパターンの除去を行う。
【００３５】
3.2. 差分・閾値処理
第２の処理は、差分・閾値処理である。ここでは補正された書き込み画像と元画像を画素ごとに比較し、差分および閾値処理を行う。ただし、スキャナによる画像取り込みの際の歪みや特徴点の誤差などによって、書き込み画像と元画像に微小なずれがあり得る。このため、ずれを考慮しつつ差分を取る必要がある。
【００３６】
この実施形態では、以下のようにして差分および閾値処理を行う。まず、書き込み画像の各画素と元画像の対応する画素を比較する。書き込み画像の画素と比較する元画像の画素は、同一の座標のものではない。この実施形態では、図５に示すように、同一の座標を中心としたN×Nの正方形の領域内にある元画像の画素が対応画素の候補になる。前記領域内の画素のうち、比較対象の書込み画像の画素に画素値の最も近いものを対応画素とする。このように、所定範囲内の画素から画素値の最も近いものを探すことで、書き込み画像と元画像に微小なずれがあっても対応する画素を精度よく見つけることができる。こうして得られた書き込み画像と元画像の画素値の差分を求める。
【００３７】
ここで、画素値の差分をそのまま出力すると、その後の２値化処理で色付きの背景になされた書き込みが消えてしまう場合がある。例えば、濃い色の背景に書き込みを行った場合、差分の値は小さくなるため、２値化の閾値によっては失われることがある。また、小さい差分でも書き込みとして抽出するように２値化の閾値を設定すると、今度は汚れや変色がノイズとなって現れる。このような問題を避けるため、この実施形態においては画素値の差分と定められた閾値とを比較する。閾値を超えた場合は、画素値の差ではなく書き込み画像の画素値をそのまま出力する。これにより、濃い色の書き込みのみを得ることができる。
【００３８】
3.3. ２値化処理
第３の処理は、２値化処理である。ここでは、図６で示されるように、差分・閾値処理で得られた書き込み（差分画像）をあらかじめ定められた閾値で２値化する。なお２値化の閾値は、スキャナで得た画像に対してｕ、電子文書から直接得た画像に対してｘを用いる。一般に、ｕはｘより小さい。その理由は次の通りである。書き込み画像はスキャナで取り込むため、元画像をスキャナで取り込んだ場合は、両者は同様の画像変換を経ていることから、書き込み以外の領域ではほとんど差分がなくなる。一方、元画像を電子文書から変換して得た場合には、色合いなどが異なるために書き込み以外の領域でも差分が生じる。このような抽出対象でない差分を取り除くためには、２値化処理においてより大きな閾値が必要になる。
【００３９】
3.4. 書き込み連結処理
第４の処理は、書き込み連結処理である。ここまでの処理では、書き込みの抽出のために書き込み画像と元画像の差分を求め、２値化を行った。これまでの処理の問題点は、ノイズの影響で書き込みが部分的に失われていることである。そこで、モルフォロジ演算の１つであるクロージング（closing）を用いた画像処理によって連結成分をまとめることで書き込みの復元を行う。
【００４０】
図７にclosingによる書き込みの連結処理を示す。closingとは、まずディレーション（dilation、即ち拡張）によって連結成分を拡張し、次にerosionによって連結成分を縮小するものである。ここで、それぞれの処理で拡張・縮小されるピクセル数は同じであるため、ごま塩ノイズ（ドット状ノイズ）のように孤立した連結成分の面積は変化しない。一方、図７に示されるような分断された連結成分では、dilationで連結成分が結合するため、erosionで縮小した後もまとめられた状態を維持する。これによって分断された書き込みを連結させることができる。なお、closing処理において用いる繰り返し数をhとする。
【００４１】
以上の処理で書き込みに対応して得られる領域（透過領域）は、本来の書き込みよりも大きめのものになる。これは、この後のAND処理においてマスクとして用いるためである。AND処理において書き込みの欠損を防ぐためには、マスクの透過領域は書き込みよりも大きい必要がある。
【００４２】
3.5. ノイズ除去
第５の処理は、ノイズ除去処理である。ここでは、差分・２値化処理で生じた細かいノイズを除去する。具体的には、図８に示されるように、まず、各連結成分の面積を調べる。そして、予め定められた閾値M以上の面積の連結成分のみを書き出す。これにより、ノイズが除去される。なお、差分・閾値処理および２値化処理の段階で書き込み領域が細かく分断されていても、続く書き込み連結処理で閾値Ｍ以上の面積に結合された領域は、このノイズ除去処理で誤って除去されることはない。
【００４３】
3.6. AND処理
最後の第６の処理は、AND処理である。ここまでの処理で得られた画像にdilation演算を繰り返し数Dで適用し、マスクを作成する。マスクと書き込み画像とのANDを画素ごとにとることで書き込みを抽出する。処理を図９に示す。このように、マスクの透過領域が大きめに取られているため、書き込みだけでなく背景も抽出される。しかし、目視によって解析する際は、書き込みと背景は容易に判別できるためあまり問題とはならない。
【００４４】
4. 実験例
以下に、本願発明の手法についての実験例とその結果を説明する。この実験例では、カラーPDFファイルから得た画像を元画像とし、PDFファイルを印刷したものに書き込みを行い、スキャナで取得した画像を書き込み画像とした。
実験は2通りの元画像を用いて行った。一方はPDFファイルをラスタ形式に変換した画像（元画像Ａ）であり、もう一方はPDFファイルを一旦印刷し、書き込み画像の取得に用いたものと同じスキャナで取り込んで画像化したもの（元画像Ｂ）である。前者は印刷やスキャニングの際の色の変化や歪みを受けないため、書き込み画像との対応点探索処理や差分処理が比較的困難となる。後者は元画像と書き込み画像の両方に同様の変化が生じるため、これらの処理は比較的容易である。なお、元画像の数はそれぞれ109枚である。
【００４５】
書き込み画像は、印刷された文書に対して黒・赤・青のボールペンで文字や図形などを数箇所に書き込み、スキャナを用いて600dpiで取り込んで作成した。1つの元画像に対して3通りの書き込み画像を用意したため、書き込み画像の数は327枚である。2種類の元画像および書き込み画像の例を図１０に示す。図１０（ａ）が元画像Ａ、図１０（ｂ）が元画像Ｂ、図１０（ｃ）が書き込み画像である。
【００４６】
実験に用いた計算機はAMD Opteron 2.8GHzのCPUを搭載し、16GBのメモリを持つものである。また、実験でのパラメータを表１に示す。ここで、表１中の各アルファベットは、前述した実施形態の記載に対応している。例えば、Ｌは、特徴点抽出における画像の縮小倍率である。また、ｌ（エル）は特徴点抽出におけるerosion演算の繰り返し回数である。
【００４７】
4-1.  PDFからの画像を用いた場合
【表１】
2008219800.tif 000003
【００４８】
まず、元画像としてPDFファイルからの画像を用いた場合について述べる。この実験でのパラメータを表1に示す。元画像には109個のPDFファイルを600dpiで画像に変換したものを用いた。1つの元画像に対して3通りの書き込み画像を用意したため、書き込み画像の数は327枚である。書き込み抽出画像を目視で評価した結果を表２に示す。
【００４９】
【表２】
2008219800.tif 000004
【００５０】
ここで、成功、かすれ・ノイズあり、失敗は、抽出された書込みが以下の状態であることを表す。
1) 成功：書き込みが十分抽出され、ノイズがほとんどないもの（図１１参照）
2) かすれ・ノイズあり：書き込みが部分的にかすれたり、目立つノイズがあったりするもの（図１２参照）
3) 失敗：書き込みがほぼ完全に失われていたり、紙面の大半をノイズが占めていたりするもの（図１３参照）
表２には、文字などの単色領域を多く含む画像と、単色領域の少ない画像とで分けて示してある。これは、単色の連結成分の重心を特徴点とする実施態様での入力画像の性質の影響を明らかにするためである。なお、単色領域か多いかどうかの判定は目視によって行った。
【００５１】
なお、図１１（ａ）は、「成功」に分類された書き込み画像、図１１（ｂ）は、図１１（ａ）の画像から抽出された書き込みを示す。図１２（ａ）は、「かすれ・ノイズあり」に分類された書込み画像、図１２（ｂ）は、図１２（ａ）から抽出された書き込みを示す。また、図１３（ａ）は、「失敗」に分類された書込み画像、図１３（ｂ）は、図１３（ａ）から抽出された書き込みを示す。
【００５２】
以下では実験結果の考察を行う。PDFからの画像を直接画像に変換した場合はスキャンした画像を用いた場合よりも成功率が低くなっていることが分かる。これは、元画像が印刷とスキャニングを経ておらず、元画像と書き込み画像の色合いが異なり、このため、対応点探索に失敗することが原因と考えられる。元画像と書き込み画像の色合いが異なると、特徴点抽出処理での色クラスタリングの結果が異なるものになり、このために、対応する特徴点が得られないことがある。また、対応点探索処理で色クラスタ同士の対応付けに失敗することもある。これが、PDFからの画像を元画像とした場合に失敗の割合が多い原因であると考えられる。
【００５３】
この問題については、印刷およびスキャニングにおける画像劣化のモデルを作成することで対処できると考えられる。元画像がPDFから得たものであった場合、元画像に書き込み画像と同様の劣化を再現する処理を加えることができれば、色合いの相違を低減し、対応点探索における失敗を低減できると考えられる。
【００５４】
また、表2から、単色領域の多く含まれる画像の方が高い精度が得られたことが分かる。これは、単色領域の少ない画像はこの実施形態の手法に適さないためである。この実施形態では、色クラスタリングした結果の連結成分の重心を特徴点としている。これは、図１１のような、文字などの単一色の図形が多く含まれる画像に適したものである。しかし、図１３のように、文字があまり含まれず、グラデーションのある図形や写真が大部分を占める画像では、特徴点を安定に抽出することができない。つまり、元画像と書き込み画像で異なる特徴点が抽出される。そのため、対応点探索を正しく行うことができず、以降の処理に失敗する。このことから、特徴点が安定して得られる文字中心のモノクロ文書を対象とすればより高い精度が期待できると考えられる。
【００５５】
なお、処理時間については、A4サイズの文書を600dpiの解像度で取得した場合、1枚あたり平均で20秒程度、A3の文書ならば40秒程度という結果を得た。処理時間の多くは特徴点抽出や差分処理などの画像処理に費やされており、解像度を落とすなどの単純な高速化処理で処理時間の短縮が可能であると考えられる。
4-2.  スキャンした画像を用いた場合
【００５６】
次に、元画像としてスキャンした画像を用いた場合について述べる。この実験では、元画像は書き込み画像と同じスキャナおよび同じ設定で書き込みのない文書を取得したものである。
この発明の手法を適用する上での問題点を明確にするため、図14(a)に示されるようなポスターやWebページなどの図形や写真を多く含むカラー文書と、図14(b)に示されるような文字が紙面の大部分を占めるモノクロ文書を用いてそれぞれ実験を行った。
4.2.1. カラー文書を用いた実験
【００５７】
この実験では、PDFからの画像を用いた場合の実験と同様に、109枚の元画像および327枚の書き込み画像を用いた。特徴点抽出の際の連結成分の最大面積Eを∞（無限大）とした以外は表1と同じパラメータを用いた。Eを極めて大きい値としたのは、大きい連結成分からも特徴点を抽出するためである。
この実験では、最終的な書き込みの抽出結果だけでなく、位置合わせ処理が終わった時点の補正された書き込み画像についても評価を行った。これは、位置合わせ処理と差分処理の、それぞれの性能を明確にするためである。位置合わせ処理の結果の判定は、目視によって行った。
【００５８】
【表３】
2008219800.tif 000005
【００５９】
【表４】
2008219800.tif 000006
位置合わせの結果を表3に、抽出結果を表4に示す。
【００６０】
以下では実験結果を考察する。まず、表3に示す位置合わせの結果について考察する。全体では、91%が位置合わせに成功した。特に、単色領域の多いものでは99%が成功した。図１５は、単色領域が多い場合の対応点の例を示す説明図である。前述したように、単色領域が多いと、安定した特徴点を多く抽出することができ、多くの正しい対応点を得ることができる。一方、図１６は、単色領域が少ない場合の対応点の例を示す説明図である。単色領域が少ないと、正しい対応点があまり得られなくなる。単色領域が多いものでも2つの画像で失敗した。これらは、同一画像内で全く同じテキストが複数の場所に存在するなど、同じ特徴点の配置が複数あるものである。図１７は、同じ特徴点の配置を複数の場所にもつ例を示す説明図である。このような場合、誤った対応が生じるため位置合わせに失敗する。全体としては、ポスターなどのカラー文書でも91%で位置合わせに成功したことから、この実施形態の手法がロバストであることが示された。
【００６１】
次に、表4に示す書き込み抽出の結果について考察する。全体では76%、単色領域の多いものに限ると88%が書き込み抽出に成功した。また、単に閲覧するだけといった用途では、多少のかすれやノイズがあってもあまり問題はない。このような場合では、成功率は全体で91%、単色領域の多いものでは98%であるといえる。失敗に分類されたもののほとんどは、位置合わせの時点で失敗したものである。位置合わせが成功したにも関わらず、失敗あるいはノイズ・かすれありに分類されたものは、色付きの背景に書き込まれたために差分処理において書き込みが消失したものと、位置合わせに微小な誤差があったために差分処理後にノイズが生じたものである。
【００６２】
4.2.2. モノクロ文書を用いた実験
カラー文書を用いた実験では、文字などの単色領域の少ない画像や、色付きの背景に書き込みのなされた画像において書き込み抽出が困難であることが示された。本実験では、多数の文字を含み、白地に書き込みのなされるモノクロ文書に対してこの実施形態の手法を適用し、この発明の手法に適した対象での性能を調べた。
実験には英語論文のPDFファイルから作成した34枚の元画像と、それらに黒・赤・青のボールペンで書き込みを行った34枚の書き込み画像を用いた。色クラスタリングの際のクラスタ数はk=2とし、それ以外の条件は前記項目4.2.1の場合と同じものとした。
【００６３】
【表５】
2008219800.tif 000007
【００６４】
【表６】
2008219800.tif 000008
【００６５】
位置合わせおよび書き込み抽出の結果を、それぞれ表5と表6に示す。表5に示されるように、モノクロ文書の場合ではすべての画像で位置合わせに成功した。これは、多数の文字が含まれるため、多くの安定な特徴点を得ることが可能であり、それによって多くの正しい対応点から適切な変換パラメータを推定できるためである。表6に示されるように、2枚の文書において抽出された書き込みにかすれが生じていた。これらは、赤色のボールペンによる書き込みが薄くなっていたため、差分処理で部分的に消失したものである。ただし、94%のもので書き込み抽出に成功しており、失敗したものは存在しなかった。以上のことから、この発明の手法は文字中心のモノクロ文書に対しては極めて有効であることが示された。
【００６６】
なお、特徴点抽出処理を改良して文字をあまり含まない対象についても安定な特徴点を得られるように改善する手法として、Harrisオペレータ（例えば、C.Harris and M.Stephens, "A Combined Corner and Edge Detector", Proc. 4th Alvey Vision Conf., pp.147-151 (1988)を参照）などのコンピュータビジョンでの研究成果を導入することが有効であると考えられる。また、画像処理の改良によって、さらなる高速化も可能であると考える。
【００６７】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【産業上の利用可能性】
【００６８】
本発明によると、書き込みは、文書内での位置、大きさ、形状の情報とともに抽出される。元となる電子文書が利用可能であるとき、文書内での位置、大きさ、形状などの情報を用いると、書き込みの周囲にどのような図形、単語、文字が存在しているのかがわかる。この情報を利用することによって、書き込みの索引付けが可能となる。具体的には、書き込みの周囲に存在する単語をキーワードとして書き込みに付与する。一旦、キーワードが
付与されると、書き込みのキーワード検索が可能となるほか、(1)書き込みをした人が、その文書のどの部分に興味を持っていたのかという情報を抽出できる (ユーザ・プロファイルの作成）、(2)その文書のどの部分が重要であるのかをランク付けできる（例えば、多くのユーザが下線や囲みを施した箇所は重要）、などの情報処理が可能となる。
【図面の簡単な説明】
【００６９】
【図１】この発明の書込み抽出方法の処理の流れを示す説明図である。
【図２】対象画像と、それを色クラスタリングして得られる画像の一例を示す説明図である。
【図３】元画像と書込み画像との対応付けが、色クラスタの特徴点単位でなされた例を示す説明図である。
【図４】特徴点の対応関係に基づいて相似変換パラメータを推定するアルゴリズムの一例を示す説明図である。
【図５】元画像と書込み画像との対応画素の差分を求める処理の手順を示す説明図である。
【図６】差分・閾値処理によって抽出された書き込みを２値化処理する様子を示す説明図である。
【図７】closingによる書き込みの連結処理の手順を示す説明図である。
【図８】ノイズ除去処理の手順を示す説明図である。
【図９】AND処理の手順を示す説明図である。
【図１０】実験に用いた２種類の元画像と書込み画像の一例を示す説明図である。
【図１１】実験例で、「成功」に分類された書込み画像と書き込みの抽出結果を示す説明図である。
【図１２】実験例で、「かすれ・ノイズあり」に分類された書込み画像と書き込みの抽出結果を示す説明図である。
【図１３】実験例で、「失敗」に分類された書込み画像と書き込みの抽出結果を示す説明図である。
【図１４】実験に用いた図１０と異なる元画像の例を示す説明図である。
【図１５】単色領域が多い場合の対応点の例を示す説明図である。
【図１６】単色領域が少ない場合の対応点の例を示す説明図である。
【図１７】同じ特徴点の配置を複数の場所にもつ例を示す説明図である。
【符号の説明】
【００７０】
１１    位置合わせ処理
１３    差分取得処理
１５    対象画像
１７ａ、１７ｂ、１７ｃ、１７ｄ、１７ｅ  色クラスタの画像
【図１】
2008219800.tif 000009
【図２】
2008219800.tif 000010
【図３】
2008219800.tif 000011
【図４】
2008219800.tif 000012
【図５】
2008219800.tif 000013
【図６】
2008219800.tif 000014
【図７】
2008219800.tif 000015
【図８】
2008219800.tif 000016
【図９】
2008219800.tif 000017
【図１０】
2008219800.tif 000018
【図１１】
2008219800.tif 000019
【図１２】
2008219800.tif 000020
【図１３】
2008219800.tif 000021
【図１４】
2008219800.tif 000022
【図１５】
2008219800.tif 000023
【図１６】
2008219800.tif 000024
【図１７】
2008219800.tif 000025