(57)【特許請求の範囲】
【請求項１】
二値のビットマップ画像であるオリジナル画像およびターゲット画像の間における改変を検知するために、情報処理装置内に実装される方法であって、
（ａ）それぞれが一つの文字に関する一つ以上の連結したピクセル群を囲む複数の境界ボックスを、前記オリジナル画像および前記ターゲット画像の中に定義するステップと、
（ｂ）前記オリジナル画像および前記ターゲット画像のそれぞれにおいて実質的に同じ位置にある複数の対となる前記境界ボックスのペアを、前記オリジナル画像および前記ターゲット画像の中に特定するステップと、
（ｃ）対となる前記境界ボックスのペアそれぞれについて、
（ｃ１）（１）前記境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数、および、（２）前記文字のペア間のハウスドルフ距離、を含む複数の形状特徴を算出し、
（ｃ２）（１）前記文字のペアのオイラー数が等しいかどうか、および、（２）前記文字のペア間のハウスドルフ距離が所定の第一閾値よりも小さいかどうか、を評価することにより前記境界ボックスのペアにより囲まれる前記文字のペアが、同一の文字か異なる文字かを判定するステップと、
を有する文書改変検知方法。
【請求項２】
前記ステップ（ｃ２）は、
（１）前記文字のペアのオイラー数が等しく、かつ、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さい場合には、前記文字のペアが同一の文字と判定するステップと、
上記以外の場合には、前記文字のペアが異なる文字と判定するステップと、
を有する請求項１に記載の文書改変検知方法。
【請求項３】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２である請求項１または請求項２に記載の文書改変検知方法。
【請求項４】
前記ステップ（ｃ１）において算出される複数の形状特徴は、（３）前記境界ボックスのペアそれぞれのアスペクト比、および、（４）前記境界ボックスの文字に属するピクセル数を前記境界ボックス全体のピクセル数で割って得られる、前記境界ボックスのペアそれぞれのピクセル密度をさらに含み、
前記ステップ（ｃ２）は、（３）前記境界ボックスのペアのアスペクト比の差分が所定の第二閾値よりも小さいかどうか、および、（４）前記境界ボックスのペアのピクセル密度の差分が所定の第三閾値よりも小さいかどうか、をさらに評価することにより実行される請求項１〜３のいずれかに記載の文書改変検知方法。
【請求項５】
前記ステップ（ｃ２）は、
（１）前記文字のペアのオイラー数が等しく、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さく、（３）前記境界ボックスのペアのアスペクト比の差分が前記所定の第二閾値よりも小さく、かつ、（４）前記境界ボックスのペアのピクセル密度の差分が前記所定の第三閾値よりも小さい場合には、前記文字のペアが同一の文字だと判定するステップと、
上記以外の場合には、前記文字のペアが異なる文字だと判定するステップと、
を有する請求項４に記載の文書改変検知方法。
【請求項６】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２であり、前記所定の第二閾値は０．１であり、前記所定の第三閾値は０．２である請求項４または請求項５に記載の文書改変検知方法。
【請求項７】
前記文字のペアのそれぞれに一つずつとして、二つのスケルトンが取得され、前記二つのスケルトンの間のハウスドルフ距離が算出されることにより、前記文字のペア間のハウスドルフ距離が算出される請求項１〜６のいずれかに記載の文書改変検知方法。
【請求項８】
前記境界ボックスは長方形である請求項１〜７のいずれかに記載の文書改変検知方法。
【請求項９】
前記ステップ（ｃ２）での判定に基づき、改変検知結果表示を生成するステップをさらに有する請求項１〜８のいずれかに記載の文書改変検知方法。
【請求項１０】
前記ステップ（ａ）の後に、ステップ（ｄ）として、前記オリジナル画像および前記ターゲット画像の一方には存在する境界ボックスであって、もう一方には対となるものが存在しない境界ボックスを特定するステップをさらに有する請求項１〜９のいずれかに記載の文書改変検知方法。
【請求項１１】
前記ステップ（ｃ２）での判定に基づく改変検知結果と、前記ステップ（ｄ）で特定された境界ボックスとを表示する図を生成するステップをさらに有する請求項１０に記載の文書改変検知方法。
【請求項１２】
情報処理装置に二値のビットマップ画像であるオリジナル画像とターゲット画像との間における改変を検知する処理を実行させるために、前記情報処理装置を制御するためのコンピュータプログラムであって、
（ａ）それぞれが一つの文字に関する一つ以上の連結したピクセル群を囲む複数の境界ボックスを、前記オリジナル画像および前記ターゲット画像の中に定義するステップと、
（ｂ）前記オリジナル画像および前記ターゲット画像のそれぞれにおいて実質的に同じ位置にある複数の対となる前記境界ボックスのペアを、前記オリジナル画像および前記ターゲット画像の中に特定するステップと、
（ｃ）対となる前記境界ボックスのペアそれぞれについて、
（ｃ１）（１）前記境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数、および、（２）前記文字のペア間のハウスドルフ距離、を含む複数の形状特徴を算出し、
（ｃ２）（１）前記文字のペアのオイラー数が等しいかどうか、および、（２）前記文字のペア間のハウスドルフ距離が所定の第一閾値よりも小さいかどうか、を評価することにより前記境界ボックスのペアにより囲まれる前記文字のペアが、同一の文字か異なる文字かを判定するステップと、
をコンピュータに実行させるコンピュータプログラム。
【請求項１３】
前記ステップ（ｃ２）は、（１）前記文字のペアのオイラー数が等しく、かつ、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さい場合には、前記文字のペアが同一の文字と判定するステップと、
上記以外の場合には、前記文字のペアが異なる文字と判定するステップと、
を有する請求項１２に記載のコンピュータプログラム。
【請求項１４】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２である請求項１２または請求項１３に記載のコンピュータプログラム。
【請求項１５】
前記ステップ（ｃ１）において算出される複数の形状特徴は、（３）前記境界ボックスのペアそれぞれのアスペクト比、および、（４）前記境界ボックスの文字に属するピクセル数を前記境界ボックス全体のピクセル数で割って得られる前記境界ボックスのペアそれぞれのピクセル密度をさらに含み、
前記ステップ（ｃ２）は、（３）前記境界ボックスのペアのアスペクト比の差分が所定の第二閾値よりも小さいかどうか、および、（４）前記境界ボックスのペアのピクセル密度の差分が所定の第三閾値よりも小さいかどうか、をさらに評価することにより実行される請求項１２〜１４のいずれかに記載のコンピュータプログラム。
【請求項１６】
前記ステップ（ｃ２）は、（１）前記文字のペアのオイラー数が等しく、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さく、（３）前記境界ボックスのペアのアスペクト比の差分が前記所定の第二閾値よりも小さく、かつ、（４）前記境界ボックスのペアのピクセル密度の差分が前記所定の第三閾値よりも小さい場合には、前記文字のペアが同一の文字だと判定するステップと、
そうでない場合には、前記文字のペアが異なる文字だと判定するステップと、
を有する請求項１５に記載のコンピュータプログラム。
【請求項１７】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２であり、前記所定の第二閾値は０．１であり、前記所定の第三閾値は０．２である請求項１５または請求項１６に記載のコンピュータプログラム。
【請求項１８】
前記文字のペアのそれぞれに一つずつとして、二つのスケルトンが取得され、前記二つのスケルトンの間のハウスドルフ距離が計算されることにより、前記文字のペア間のハウスドルフ距離が算出される請求項１２〜１７のいずれかに記載のコンピュータプログラム。
【請求項１９】
前記境界ボックスは長方形である請求項１２〜１８のいずれかに記載のコンピュータプログラム。
【請求項２０】
前記ステップ（ｃ２）での判定に基づき、改変検知結果表示を生成するステップをさらに有する請求項１２〜１９のいずれかに記載のコンピュータプログラム。
【請求項２１】
前記ステップ（ａ）の後に、ステップ（ｄ）として、前記オリジナル画像および前記ターゲット画像の一方には存在する境界ボックスであって、もう一方には対となるものが存在しない境界ボックスを特定するステップをさらに有する請求項１２〜２０のいずれかに記載のコンピュータプログラム。
【請求項２２】
前記ステップ（ｃ２）での判定に基づく改変検知結果と、前記ステップ（ｄ）で特定された境界ボックスとを表示する図を生成するステップをさらに有する請求項２１に記載のコンピュータプログラム。
【請求項２３】
各境界ボックスに囲まれた一つ以上の連結されたピクセル群である文字であって、二値のビットマップ画像であるオリジナル画像およびターゲット画像のそれぞれの中にある二つの文字を比較するために、情報処理装置において実行される方法であって、
（１）前記境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数、および、（２）前記文字のペア間のハウスドルフ距離、を含む複数の形状特徴を算出する算出ステップと、
（１）前記文字のペアのオイラー数が等しいかどうか、および、（２）前記文字のペア間のハウスドルフ距離が所定の第一閾値よりも小さいかどうか、を評価することにより前記境界ボックスのペアにより囲まれる前記文字のペアが同一の文字か異なる文字かを判定する判定ステップと、
を有する文字比較方法。
【請求項２４】
前記判定ステップは、
（１）前記文字のペアのオイラー数が等しく、かつ、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さい場合には、前記文字のペアが同一の文字と判定するステップと、
上記以外の場合には、前記文字のペアが異なる文字と判定するステップと、
を有する請求項２３に記載の文字比較方法。
【請求項２５】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２である請求項２３または請求項２４に記載の文字比較方法。
【請求項２６】
前記算出ステップにおいて算出される複数の形状特徴は、（３）前記境界ボックスのペアそれぞれのアスペクト比、および、（４）前記境界ボックスの文字に属するピクセル数を前記境界ボックス全体のピクセル数で割って得られる前記境界ボックスのペアそれぞれのピクセル密度をさらに含み、
前記判定ステップは、（３）前記境界ボックスのペアのアスペクト比の差分が所定の第二閾値よりも小さいかどうか、および、（４）前記境界ボックスのペアのピクセル密度の差分が所定の第三閾値よりも小さいかどうかをさらに評価することにより実行される請求項２３〜２５のいずれかに記載の文字比較方法。
【請求項２７】
前記判定ステップは、
（１）前記文字のペアのオイラー数が等しく、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さく、（３）前記境界ボックスのペアのアスペクト比の差分が前記所定の第二閾値よりも小さく、かつ、（４）前記境界ボックスのペアのピクセル密度の差分が前記所定の第三閾値よりも小さい場合には、その文字のペアが同一の文字だと判定するステップと、
そうでない場合には、その文字のペアが異なる文字だと判定するステップと、
を有する請求項２６に記載の文字比較方法。
【請求項２８】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２であり、前記所定の第二閾値は０．１であり、前記所定の第三閾値は０．２である請求項２６または請求項２７に記載の文字比較方法。
【請求項２９】
前記文字のペアのそれぞれに一つずつとして、二つのスケルトンが取得され、前記二つのスケルトンの間のハウスドルフ距離が算出されることにより前記文字のペア間のハウスドルフ距離が算出される請求項２３〜２８のいずれかに記載の文字比較方法。
【請求項３０】
前記境界ボックスは長方形である請求項２３〜２９のいずれかに記載の文字比較方法。
【請求項３１】
各境界ボックスに囲まれた一つ以上の連結されたピクセル群である文字であって、二値のビットマップ画像であるオリジナル画像とターゲット画像それぞれの中にある二つの文字を比較する処理を情報処理装置に実行させるために、前記情報処理装置を制御するためのコンピュータプログラムであって、
（１）前記境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数、および、（２）前記文字のペア間のハウスドルフ距離、を含む複数の形状特徴を算出する算出ステップと、
（１）前記文字のペアのオイラー数が等しいかどうか、および、（２）前記文字のペア間のハウスドルフ距離が所定の第一閾値よりも小さいかどうか、を評価することにより前記境界ボックスのペアにより囲まれる前記文字のペアが同一の文字か異なる文字かを判定する判定ステップと、
をコンピュータに実行させるコンピュータプログラム。
【請求項３２】
前記判定ステップは、（１）前記文字のペアのオイラー数が等しく、かつ、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さい場合には、その文字のペアが同一の文字と判定するステップと、
上記以外の場合には、その文字のペアが異なる文字と判定するステップと、
を有する請求項３１に記載のコンピュータプログラム。
【請求項３３】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２である請求項３１または請求項３２に記載のコンピュータプログラム。
【請求項３４】
前記算出ステップにおいて算出される複数の形状特徴は、（３）前記境界ボックスのペアそれぞれのアスペクト比、および、（４）前記境界ボックスの文字に属するピクセル数を前記境界ボックス全体のピクセル数で割って得られる前記境界ボックスのペアそれぞれのピクセル密度をさらに含み、
前記判定ステップは、（３）前記境界ボックスのペアのアスペクト比の差分が所定の第二閾値よりも小さいかどうか、および、（４）前記境界ボックスのペアのピクセル密度の差分が所定の第三閾値よりも小さいかどうか、をさらに評価することにより実行される請求項３１〜３３のいずれかに記載のコンピュータプログラム。
【請求項３５】
前記判定ステップは、（１）前記文字のペアのオイラー数が等しく、（２）前記文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さく、（３）前記境界ボックスのペアのアスペクト比の差分が前記所定の第二閾値よりも小さく、かつ、（４）前記境界ボックスのペアのピクセル密度の差分が前記所定の第三閾値よりも小さい場合には、その文字のペアが同一の文字だと判定するステップと、
上記以外の場合には、その文字のペアが異なる文字だと判定するステップと、
を有する請求項３４に記載のコンピュータプログラム。
【請求項３６】
文字の大きさによって正規化された距離として定義された前記所定の第一閾値は０．２であり、前記所定の第二閾値は０．１であり、前記所定の第三閾値は０．２である請求項３４または請求項３５に記載のコンピュータプログラム。
【請求項３７】
前記文字のペアのそれぞれに一つずつとして、二つのスケルトンが取得され、前記二つのスケルトンの間のハウスドルフ距離が算出されることにより前記文字のペアのハウスドルフ距離が算出される請求項３１〜３６のいずれかに記載のコンピュータプログラム。
【請求項３８】
前記境界ボックスは長方形である請求項３１〜３７のいずれかに記載のコンピュータプログラム。
【請求項３９】
請求項１２〜２２および請求項３１〜３８のいずれかに記載のコンピュータプログラムが保存されたコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ターゲットとする文書におけるオリジナルの文書に関する改変を検知する方法に関し、特に改変を検知するために文字の形状特徴を用いる改変検知方法に関する。
【背景技術】
【０００２】
閉ループプロセスとは、オリジナルのデジタル文書（文字、図形、画像等を含む）を印刷し、印刷された文書のハードコピーを配布および複製等の方法で利用し、また文書のハードコピーをスキャンして再びデジタル形式に戻すことを指す。スキャンされたデジタル文書の認証とは、スキャンされた文書がオリジナルのデジタル文書の真正な複製であるかどうか、すなわちその文書がハードコピーの状態で改変されたかどうかを判定することを指す。様々な種類の文書認証および文書改変検知方法が提唱されている。多くの文書認証方法の目的は、追加や削除といった改変の内容を検知することである。文書認証方法の一種類においては、オリジナルのデジタル文書とスキャンされた文書の画像比較を行う。これは、ピクセルベースの改変検知方法と呼ばれることがある。他の種類の文書認証方法においては、文書の内容を表すデータまたは文書の内容に関連するデータがバーコードとして符号化され、後で行う文書認証を補助するために、そのバーコードが文書そのものの上に印刷される。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
従来のピクセルベースの改変検知方法において、対象となるスキャンされた画像に改変点があるかどうかを判定するために、オリジナルのデジタル画像とスキャンされた画像についてピクセル毎の比較を行う。プリンターとスキャナーの両方の解像度が高ければ、スキャンされた画像の解像度も高くなる。従来の改変検知方法における画像全体について網羅的に画像比較を行う処理は、非常に計算量が多い。
【０００４】
さらに、ピクセル毎の比較は、誤った改変検知を行うことがある。例えば、オリジナル画像とターゲット画像の同じ位置にある二つの文字が、たとえ二つの文字が同一（すなわち文字が改変されていない）の場合でも、ターゲット画像とオリジナル画像においてピクセルレベルでの相違点は存在しうる。ターゲット文書を生成する印刷およびスキャンの過程によって生じる、このようなピクセルレベルの違いが、誤った改変検知につながる可能性がある。
【課題を解決するための手段】
【０００５】
本発明は、オリジナルのデジタル文書の画像とスキャンされた文書の画像との画像比較を行うことにより、文書の認証方法の改良を目指したものである。
【０００６】
本発明の目的は、誤った改変検知を抑止する画像比較に基づく改変検知方法を提供することである。
【０００７】
本発明の追加の特徴および利点は以下の説明に記載され、ある程度は説明から明らかであり、または本発明の実施により知ることができる。本発明の目的および他の利点は、それについて記載された明細書、特許請求の範囲および添付の図面において特に指摘された構造によって実現および達成される。
【０００８】
本書において具現化され、広範に記載された目的及び他の目的を達成するために、本発明は二値のビットマップ画像であるオリジナル画像およびターゲット画像の間における改変を検知するために、情報処理装置内に実装される方法であって、（ａ）それぞれが一文字に関する一つ以上の連結したピクセル群を有する複数の境界ボックスを、オリジナル画像およびターゲット画像の中に定義するステップと、（ｂ）オリジナル画像およびターゲット画像それぞれにおいて実質的に同じ位置にある複数の対となる境界ボックスのペアを、オリジナル画像およびターゲット画像の中に特定するステップと、（ｃ）それぞれの対となる境界ボックスのペアについて、（ｃ１）（１）境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数と、（２）境界ボックスのペアそれぞれのアスペクト比と、（３）境界ボックスの文字に属するピクセル数を境界ボックス全体のピクセル数で割って得られる境界ボックスのペアそれぞれのピクセル密度と、（４）文字のペア間のハウスドルフ距離とを含む複数の形状特徴を算出し、（ｃ２）（１）文字のペアのオイラー数が等しいかどうか、（２）境界ボックスのペアのアスペクト比の差分が所定の第一閾値よりも小さいかどうか、（３）境界ボックスのペアのピクセル密度の差分が所定の第二閾値よりも小さいかどうか、（４）文字のペア間のハウスドルフ距離が所定の第三閾値よりも小さいかどうか、を評価することにより境界ボックスのペアにより囲まれる文字が、同一の文字か異なる文字かを判定するステップと、を含む文書改変検知方法を提供する。
【０００９】
一つの例において、ステップ（ｃ２）は、（１）文字のペアのオイラー数が等しく、（２）文字のペア間のハウスドルフ距離が前記所定の第一閾値よりも小さく、（３）境界ボックスのペアのアスペクト比の差分が前記所定の第二閾値よりも小さく、かつ、（４）境界ボックスのペアのピクセル密度の差分が前記所定の第三閾値よりも小さい場合には、その文字のペアが同一の文字だと判定するステップと、そうでない場合には、その文字のペアが異なる文字だと判定するステップとを含む。
【００１０】
その他の態様において、本発明は、各境界ボックスに囲まれた一つ以上の連結されたピクセル群である文字であって二値のビットマップ画像であるオリジナル画像およびターゲット画像のそれぞれの中にある二つの文字を比較するために、情報処理装置において実行される方法であって、（ａ）（１）境界ボックスのペアにより囲まれる文字のペアそれぞれに関するオイラー数と、（２）境界ボックスのペアそれぞれのアスペクト比と、（３）境界ボックスの文字に属するピクセル数を境界ボックス全体のピクセル数で割って得られる境界ボックスのペアそれぞれのピクセル密度と、（４）文字のペア間のハウスドルフ距離とを含む複数の形状特徴を算出するステップと、（ｂ）（１）文字のペアのオイラー数が等しいかどうか、（２）境界ボックスのペアのアスペクト比の差分が所定の第二閾値よりも小さいかどうか、（３）境界ボックスのペアのピクセル密度の差分が所定の第三閾値よりも小さいかどうか、（４）文字のペア間のハウスドルフ距離が所定の第一閾値よりも小さいかどうかを評価することにより境界ボックスのペアにより囲まれる文字が、同一の文字か異なる文字かを判定するステップと、を含む文字比較方法を提供する。
【００１１】
その他の態様において、本発明は、情報処理装置を制御するために組み込まれたコンピュータプログラムと、情報処理装置が上記の方法を実行するように設定されたコンピュータプログラムとをその中に含むコンピュータで使用可能な非一時的記憶媒体（例えばメモリまたは記憶装置）を有するコンピュータプログラムおよびコンピュータプログラム製品を提供する。
【００１２】
前述の概要及び以下の詳述は、いずれも典型例及び説明を示すものであり、特許請求の範囲に記載された発明の仔細な説明を提供することを目的としている。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に係る改変検知方法のフローチャートを示す図である。
【図２】図１のプロセスにおける形状特徴比較のステップを仔細に示すフローチャートである。
【図３ａ】それぞれが一つの文字を囲む二つの境界ボックスを示す図である。
【図３ｂ】図３ａに示す二つの文字から生成される二つのスケルトンを示す図である。
【発明を実施するための形態】
【００１４】
本発明の実施形態に係る文書改変検知方法は、文字の形状特徴の比較を用いて、オリジナルのデジタル文書画像とスキャンされたデジタル文書画像（ターゲット画像）の比較を行う。ターゲット画像とオリジナル画像にある二つの文字は、実際に文字を認識することなく様々な文字の形状特徴を分析することにより、同じ文字または異なる文字と判定される。言い換えれば、文字認識（すなわちある文字を特定の言語における特定の文字と認識すること）は必要ではない。
【００１５】
図１および図２を参照して、改変検知方法をより詳細に説明する。図１は本発明の実施形態に係る改変検知方法のフローチャートである。図２は図１におけるステップＳ１５を更に詳細を示すものである。
【００１６】
第一に、未加工オリジナル画像および未加工ターゲット画像を取得する（ステップ１１）。両方の画像はビットマップ画像とする。一般に、未加工ターゲット画像は、元々オリジナルのデジタル文書から印刷された文書のハードコピーをスキャンすることにより取得する。例えば、オリジナルのデジタル文書は、コンピュータの文書加工アプリケーションにより生成した文書、ハードコピーをスキャンすることにより得られる画像、カメラで撮影した写真等である。オリジナルのデジタル文書が印刷された後、そのハードコピーは、未加工ターゲット画像を生成するためにスキャンし直されるまでの間に、回覧や複写等が行われる。ある実施形態における認証または改変検知プロセスの目的は、最初に印刷された時からスキャンし直されるまでの間、ハードコピー文書が改変されたかどうかを検知することである。
【００１７】
ステップＳ１１で取得する未加工オリジナル画像は、オリジナルのデジタル文書から生成した画像でもよいし、オリジナルのデジタル文書そのものでもよい。例えば、オリジナルのデジタル文書が文書加工アプリケーションにより生成された文書である場合、未加工オリジナル画像は、オリジナルのデジタル文書を表示する画像を生成するコンピュータプログラムを使用して取得してもよい。また、未加工オリジナル画像は、オリジナルのデジタル文書を印刷後すぐに改変することなくスキャンして取得してもよい。また、未加工オリジナル画像は、オリジナルとみなされるハードコピー文書をスキャンして取得してもよい。未加工オリジナル画像を得るための他の方法も使用してもよい。未加工オリジナル画像はオリジナル文書を改変していない画像を表す。
【００１８】
未加工オリジナル画像およびターゲット画像が例えばマイクロソフト社のワード形式やＰＤＦ形式等のようなアプリケーション特有の形式を持つ場合、それらは以降のプロセスのためにビットマップ画像に変換される。加えて、未加工オリジナル画像およびターゲット画像のビットマップ画像は、好ましくは解像度が同一となるように調整されている。
【００１９】
改変検知の典型的なシナリオにおいて、未加工ターゲット画像はオリジナル文書のコピーであり、従って通常、未加工ターゲット画像は一般的にオリジナル文書に類似した外観を持ち、もし改変されていたとしても限定的な改変だと想定されていることに留意されたい。
【００２０】
未加工オリジナル画像および未加工ターゲット画像は事前処理される（ステップＳ１２）。事前処理は、すでに二値画像である場合を除き、グレースケールまたはカラーの画像を閾値により二値画像に変換する処理を含む。事前処理はまた、傾き補正、サイズ補正、位置補正のような一つ以上の歪み補正工程も含む。傾き補正は、一般に印刷工程やスキャン工程において生じる回転誤差の修正を指す。ハフ変換およびフーリエ‐メリン変換等の多くの傾き補正方法が知られている。傾き補正を行うために、未加工ターゲット画像のみを使用する方法もあれば、未加工ターゲット画像と未加工オリジナル画像の両方を使用する方法もある。本ステップにおいて、いかなる好適な傾き補正方法を使用してもよい。同様に、多くのサイズ補正方法が知られている。未加工ターゲット画像のサイズ補正を行うためには、一般に未加工オリジナル画像と未加工ターゲット画像を比較する必要がある。二つの画像の実効的なコンテンツの面積を比較するサイズ補正方法もある。本ステップにおいて、いかなる好適なサイズ補正方法を使用してもよい。未加工ターゲット画像のサイズ補正は、例えば印刷された解像度とは異なる解像度でハードコピー文書がスキャンされる場合のように、未加工オリジナル画像と未加工ターゲット画像が異なる解像度を持つようなケースにおいて、特に必要となる。サイズ補正された未加工ターゲット画像は、少なくとも対象となる画像領域においては、未加工オリジナル画像と同じ解像度と同じピクセル数を持つ。未加工ターゲット画像を移動させる位置補正は、未加工ターゲット画像を未加工オリジナル画像に正確に揃えるように行われる。位置補正は、一般に二つの画像を比較することにより行われる。テンプレートマッチング等、多くの画像位置補正方法が知られている。本ステップにおいて、いかなる好適な画像位置補正方法を使用してもよい。未加工オリジナル画像については、印刷およびスキャンの工程を経ない場合、歪み補正工程を省略してもよい。
【００２１】
加工されたオリジナル画像およびターゲット画像は、改変を検知するために比較される。これを行うために、オリジナル画像およびターゲット画像のそれぞれの文字について境界ボックスを生成する（ステップＳ１３）。各境界ボックスは、通常一つの文字について一つ以上の連結したピクセル群を囲う。境界ボックスは長方形であることが望ましい。文字の境界ボックスを生成するステップはＯＣＲ（光学文字認識）技術において一般に使用されており、ステップＳ１３においては、いかなる好適な境界ボックス生成方法を使用してもよい。
【００２２】
オリジナル画像およびターゲット画像の境界ボックスは対応するペアを形成する。対となる境界ボックスのペアは、各画像上において実質的に同じ位置にある、オリジナル画像の境界ボックスと、ターゲット画像の境界ボックスとから構成される。ここで、実質的に同じ位置とは、二つの境界ボックスにおける位置の違いが水平および垂直方向において所定の閾値より小さいことを意味する。閾値はインチ単位またはピクセル単位（この場合、値は画像の解像度に依存する）で計測してもよい。閾値は様々な要素に依存してもよい。さらに、動的な閾値を使用してもよい。例えば、閾値は水平および垂直それぞれの閾値について、文章の該当する行における文字の平均的な幅および高さの半分としてもよい。閾値を該当する行における隣接した境界ボックスの平均距離とする例もある。一方の画像中にある境界ボックスが、他方の画像中に対となる境界ボックスを持たない場合、例えば文字の削除または追加といった改変が検知される（ステップＳ１４）。
【００２３】
図３ａは、それぞれ文字「ｙ」を含む境界ボックスの典型的なペアを示す
そして、オリジナル画像およびターゲット画像中の対となる境界ボックスのペアは、文字のペアが同一の文字かどうかを判定するために、境界ボックスの文字における形状特徴を比較する処理が施される（ステップＳ１５）。図２を参照して、ステップＳ１５をより詳細に説明する。
【００２４】
図２の工程は、ここでは図２の改変検知工程全体の中の一つのステップとして記載されているが、図２に示すアルゴリズムは、他の実用的なアプリケーションにおいてもより一般的に適用可能であり、二つの文字が同一の文字かどうかを判断するための比較に使用できる点に留意されたい。
【００２５】
図２に示すように、対となる境界ボックスの各ペアについて、以下の形状特徴がそれぞれの境界ボックスについて算出される。
【００２６】
文字のオイラー数（ステップＳ２１）。オイラー数（対数）は画像のトポロジーを測る尺度である。これは、Ｅ＝Ｃ−Ｈという数式により定義され、ここで、Ｅはオイラー数、Ｃは画像中の接続された画像構成要素の数、Ｈは穴の数である。英文字およびアラビア数字のオイラー数は、一般に１、０または−１である。本ステップにおいて、文字のオイラー数を算出するためのいかなる好適なアルゴリズムも使用可能である。
【００２７】
境界ボックスのアスペクト比（ステップＳ２２）。長方形の境界ボックスについて、アスペクト比は幅と高さの比として定義してもよい。境界ボックスが平行四辺形などの他の形状である場合、他の尺度を使用してもよい。
【００２８】
境界ボックスのピクセル密度（ステップＳ２３）。これは文字に属するピクセル数（前景ピクセルと呼ばれることがある）を、バウンディングボ境界ボックスの全ピクセル数、例えば境界ボックスが長方形であればその高さ掛ける幅（ピクセル単位）、で割ったものと定義される。
【００２９】
加えて、二つの文字間のハウスドルフ距離が算出される（ステップＳ２４）。本ステップは、まずは二つの文字それぞれのスケルトンを取得することにより実現される。文字のスケルトンは、文字の中線または中心線である。図３ｂは、図３ａに示す二つの文字から取得した二つのスケルトンを示す。スケルトンは形態的細線化アルゴリズムを使用して取得してもよい。ここで、二つ文字に関する二つのスケルトン間のハウスドルフ距離が算出される。数学的には、ハウスドルフ距離は一方の集合から他方の集合における最も近い点までの距離の最大値である。より正式には、集合Ａから集合Ｂまでのハウスドルフ距離は以下に定義される最大値関数である。
【００３０】
【数１】
0005616308.tif 000002
【００３１】
【数２】
0005616308.tif 000003
【００３２】
【数３】
0005616308.tif 000004
【００３３】
ここで、ａおよびｂはそれぞれ集合Ａおよび集合Ｂ上の点であり、またｄ（ａ、ｂ）はこれらの点間の任意の距離であり、例えばｄ（ａ、ｂ）はａとｂのユークリッド距離としてもよい。ハウスドルフ距離はコンピュータビジョン、コンピュータグラフィックスおよび他の分野で広く使用される。二つのスケルトン間のハウスドルフ距離を算出するためのいかなる好適なアルゴリズムを使用してもよい。
【００３４】
そして、二つの文字が同一かどうかを判断する決定が行われる。好ましい実施形態において、二つの文字が下記の四つの条件を満たした場合、二つの文字は同一だと判定される。
【００３５】
二つの文字のオイラー数が同一である（ステップＳ２５）。
【００３６】
二つのアスペクト比の差分値が所定の第一閾値より小さい（ステップＳ２６）。
【００３７】
二つのピクセル密度の差分値が所定の第二閾値より小さい（ステップ２７）。
【００３８】
二つの文字間のハウスドルフ距離が所定の第三閾値より小さい（ステップ２８）。
【００３９】
これらの条件において使用される閾値は、事前の統計的分析を行うことにより予め設定可能である。好適な実施形態において、上記の条件（ステップＳ２６、Ｓ２７、Ｓ２８）における三つの所定の閾値は、それぞれ約０．１、０．２、５．５（解像度６００ｄｐｉの画像について、ピクセルを単位として計測）である。しかし、いかなる他の好適な値を使用してもよい。特に、ハウスドルフ距離の閾値は画像の解像度に依存する。他の実施形態においては、ハウスドルフ距離の閾値は文字の大きさ（文字の幅、文字の高さ、またはその二つの組み合わせ）により正規化された距離である。好適な実施形態において、正規化された閾値は０．２である。
【００４０】
上記四つの条件がすべて満たされた場合（ステップＳ２５からＳ２８までの全てにおいて「Ｙ」となった場合）、二つの文字は同一と判定される（ステップＳ２９）。いずれかの条件が満たされない場合（ステップＳ２５からＳ２８までのいずれかにおいて「Ｎ」となった場合）、二つの文字は異なると判断される（ステップＳ３０）。上記の工程（ステップＳ２１からＳ３０まで）は、オリジナル画像およびターゲット画像にある全ての対となる境界ボックスのペアについて、繰り返し実行される。
【００４１】
図２は四つの算出ステップ（Ｓ２１からＳ２４まで）および四つの判定ステップ（Ｓ２５からＳ２８まで）を記載しているが、ステップの順番は図２に記載したものから変更可能な点である点に留意されたい。例えば、各判定ステップは対応する算出ステップの後にすぐ実施可能であり、判定ステップの一つにおいて判定条件を満たさない場合、二つの文字は異なると判定され（ステップＳ３０）、残りの算出および判定ステップは（もしあれば）スキップされる。
【００４２】
さらに、図２の実施形態において、二つの文字が同一とみなされるためには四つの条件全てを満たす必要があるが、条件を緩和することも可能である。例えば、ある実施形態において、四つの条件（ステップＳ２５からＳ２８までに示す）のうち少なくとも三つを満たせば、二つの文字は同一と判定される。他の実施形態において、ハウスドルフ距離の条件（ステップＳ２８）を満たし、かつ、他の三つの条件（ステップＳ２５からＳ２７まで）のうち少なくとも二つを満たせば、二つの文字は同一と判定される。この点において、四つの条件のそれぞれは、多くの実際の環境においては、これらの条件が単独で使用された場合、対となる二つの文字が同一かどうかを判定するには不十分だと言える。実際の経験から、発明者はオイラー数条件およびハウスドルフ距離条件の組み合わせが誤判定の割合を減少させることを発見した。ハウスドルフ距離条件の判定精度は、オイラー数条件の判定精度と組み合わせることにより補完することが可能だと言われている。その理由は、ハウスドルフ距離条件は、どのように対応する文字のスケルトンを抽出するかというアルゴリズムに大きく依存しており、比較される画像の質が低い場合には、精度が相対的に低くなるためである。しかし、他の組み合わせを使用してもよい。
【００４３】
全ての対となる境界ボックスのペアが処理された後（図２の「リターン」）、ステップＳ１４において検知された全ての改変およびステップＳ１５（すなわち図２）において検知された全ての改変は、改変検知結果表示（便宜上、ここでは改変マップという）を生成するために統合され、改変マップはユーザにディスプレイ表示、印刷、保管等される（図１のステップＳ１６）。
【００４４】
改変マップはオリジナル画像およびターゲット画像における改変点（差異点）を表示できるものであれば、いかなる好適な形式とすることも可能である。例えば、改変マップは、二つの画像の間でどのピクセルが異なるかを示す二値の差異マップとしてもよい。そのようなマップにおいて、改変されていない領域は空白であり、改変された領域はマップ上に表れる。他の例として、改変マップは、画像中の改変（追加、削除、変更等）された部分を示すマーカーまたはハイライト（四角、円、線、矢印、色等）を用いた、オリジナル画像またはターゲット画像のマークアップ版としてもよい。追加または削除された文字は、その文字を表示または非表示とするマーカーによって表現してもよい。異なる種類の改変（追加、削除、変更等）を表現するために、改変マップにおいて異なる色を使用してもよい。他の例において、改変マップは、いかなる文字も含まず、改変された場所を示すマーカーだけを含むことも可能である。
【００４５】
図２に示す形状特徴の比較工程はいかなる言語におけるいかなる文字の比較にも使用することが可能である。先述したように、この比較のために、ＯＣＲ処理のように実際に文字を認識する必要はない。
【００４６】
上記の改変検知方法は、メモリーに格納されたソフトウェアまたはファームウェアに実装され、例えばコンピュータや情報処理部を有するプリンターまたはスキャナーなどの好適な情報処理装置により実行してもよい。この点において、図１のフローチャートを実現するために作成されるコンピュータが実行可能なソフトウェアは、好適な情報処理装置の中央処理装置（ＣＰＵ）またはマイクロ処理装置（ＭＰＵ）からアクセスされるコンピュータメモリに格納してもよい。印刷およびスキャンのステップは、プリンターおよびスキャナー、もしくは印刷部分とスキャン部分を一つの装置の中に併せ持つオールインワン装置により実行してもよい。これらの装置および器具の構造はよく知られており、ここでは詳述しない。
【００４７】
上記の方法、特に図２のアルゴリズムは、文書改善検知の文脈において記載されているが、このアルゴリズムは二つの文字が同一の文字かどうかを判定するための比較方法として一般的に使用してもよい。
【００４８】
本発明の思想または範囲から逸脱することなく、本発明に係る改変検知方法の様々な修正および変更が可能であることは、当業者にとって明らかである。このように、本発明は、添付された特許請求の範囲およびそれらの同等物に記載の範囲で行われる修正や変更も含む。
【図１】
0005616308.tif 000005
【図２】
0005616308.tif 000006
【図３ａ】
0005616308.tif 000007
【図３ｂ】
0005616308.tif 000008