(57)【特許請求の範囲】
【請求項１】
オリジナルデジタル画像中の異常の有無および位置を決定する方法であって、
画素の値がオリジナル画像上の対応する位置でのグラディエントの大きさの判断指標となっているグラディエント画像を形成するグラディエント画像形成工程と、
前記グラディエント画像の画素の値を、その近傍の複数の画素値を組み合わせて得た値で置き換えることによって、前記グラディエント画像からボケ・グラディエント画像を形成するボケ・グラディエント画像形成工程と、
前記グラディエント画像と前記ボケ・グラディエント画像とを用いて、前記オリジナル画像の異常を決定する工程を備えた異常決定工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項２】
請求項１に記載の方法であって、
前記異常決定工程がさらに、
前記グラディエント画像と前記ボケ・グラディエント画像とを用いて、前記オリジナル画像における各異常候補が重複することなく登録された異常候補リストを作成する異常候補リスト作成工程と、
前記異常候補リストを間引く間引き工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項３】
請求項１に記載の方法であって、
前記オリジナル画像について検出される前記異常として、ダスト像が含まれることを特徴とするデジタル画像の異常検出方法。
【請求項４】
請求項２に記載の方法であって、
前記オリジナル画像について検出される前記異常として、キズ像が含まれることを特徴とするデジタル画像の異常検出方法。
【請求項５】
請求項２に記載の方法であって、
前記グラディエント画像として単チャネル多値画像を生成することを特徴とするデジタル画像の異常検出方法。
【請求項６】
請求項２に記載の方法であって、
前記ボケ・グラディエント画像として多値画像を生成することを特徴とするデジタル画像の異常検出方法。
【請求項７】
請求項２に記載の方法であって、
前記ボケ・グラディエント画像形成工程は、
前記ボケ・グラディエント画像のそれぞれの画素につき、当該画素の近傍にある各近傍画素のグラディエント値を前記グラディエント画像から求め、前記各画素のグラディエント値の加重和を用いて、前記ボケ・グラディエント画像の画素値を算出する平均化工程、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項８】
請求項７に記載の方法であって、
前記平均化工程においては、前記加重和は、前記各近傍画素の平均値の指標として、前記各近傍画素の最大値と最小値と間の中間値をとるように決定されることを特徴とするデジタル画像の異常検出方法。
【請求項９】
請求項２に記載の方法であって、
前記間引き工程が、
前記異常候補リストから間引くべき要素を所定のテストを用いて検出する工程、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１０】
請求項２に記載の方法であって、
各画像は画素グリッド上で定義されており、
前記グラディエント画像の画素グリッドと、前記ボケ・グラディエント画像の画素グリッドとは、前記オリジナル画像の画素グリッドに対して、それらの画像のある画素の中心位置が前記オリジナル画像の４つの画素の角境界に形成された頂点に対応していることを特徴とするデジタル画像の異常検出方法。
【請求項１１】
請求項２に記載の方法であって、
前記オリジナル画像は複数のカラーチャネルを有し；
前記グラディエント画像を形成する工程は、
前記オリジナル画像の各カラーチャネルを、カーネルでたたみ込み処理する工程と、
得られたたたみ込み画像を一つの単チャネル多値画像に合成して合成画像を得る合成工程と、
を備え、
チャネルの値が局所的に最も急激に変化するオリジナル画像領域の中心画素が前記合成画像の極値によって指示されるように、前記カーネルの構造と前記合成工程の合成態様とが決定されることを特徴とするデジタル画像の異常検出方法。
【請求項１２】
請求項１１に記載の方法において、
前記合成工程においては、
(a)  前記たたみ込みにおいては偶数行列のカーネルが用いられることによって、各たたみ込み画像の画素グリッドすなわち頂点グリッドにおいて各画素の中心が前記オリジナル画像の４つの画素の交点の頂点に揃っており、
(b)  前記オリジナル画像の各カラーチャネルが、行数および列数が偶数であるような偶数行列の正方カーネルとなっているｘカーネルを用いてたたみ込みされてｘ−たたみ込み値が得られ、かつ前記ｘ−たたみ込み値の極値が、たたみ込み対象となる画像の値がｘ方向に急激に変化している場所を示すように前記ｘカーネルの値が設定され、
(c)  前記オリジナル画像の各カラーチャネルが、前記ｘカーネルで使われたのと同じ偶数ｎの行数および列数を持つ正方カーネルのｙカーネルを用いてたたみ込みされてｙ−たたみ込み値が得られ、かつ前記ｙ−たたみ込みの極値が、たたみ込み対象となる画像の値がｙ方向に急激に変化している場所を示すように前記ｙカーネルの値が設定され、
(d)  前記頂点グリッド上の各カラーチャネルの各画素ごとに、前記ｘ−たたみ込み値の二乗と前記ｙ−たたみ込み値の二乗との和の平方根をとって、前記頂点グリッド上の各カラーチャネルの各画素ごとに固有のグラディエント指標が作成され、
(e)  前記頂点グリッドの各画素ごとに、前記頂点グリッドの各チャネルにおける対応画素の前記グラディエント指標の最大値を、当該画素のグラディエント指標とすることを特徴とするデジタル画像の異常検出方法。
【請求項１３】
請求項２に記載の方法であって、
前記グラディエント画像は第１補助多値画像として形成されるものであり、
前記ボケ・グラディエント画像形成工程は、
前記グラディエント画像の各画素の値をその近傍にある画素のグラディエント値の加重和で置き換えて前記ボケ・グラディエント画像を第２補助多値画像として形成する第２補助多値画像形成工程、
を備え、
前記第２補助多値画像形成工程が、
前記グラディエント画像を、前記グラディエント画像そのものを生成するために使われたカーネルよりも実質的に大きい平均カーネルでたたみ込む工程、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１４】
請求項２に記載の方法であって、
前記異常候補リスト作成工程が、
(a)  前記グラディエント画像および前記ボケ・グラディエント画像から、それらの画像と同じ画素グリッド上に、単チャネルの補助２値画像を生成する工程と、
(b)  前記補助２値画像から、前記異常候補リストを生成する工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１５】
請求項１４に記載の方法であって、
前記補助２値画像を生成する工程が、
(a)  前記グラディエント画像と前記ボケ・グラディエント画像から、それら画像と同じ画素グリッド上に、単チャネルの補助３値画像を生成する工程と、
(b)  前記補助３値画像を前記補助２値画像に変換する工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１６】
請求項１５に記載の方法であって、
前記補助３値画像を形成する工程が、
前記グラディエント画像の画素値（第１値）と前記ボケ・グラディエント画像の対応する画素値（第２値）とを比較し、前記第１値と前記第２値との大小関係に応じて、前記補助３値画像の対応する画素に所定の３つの画素インデクス値のいずれかを割り当てる画素インデクス値割当て工程、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１７】
請求項１６に記載の方法であって、
前記３つの画素インデクス値が第１、第２および第３の画素インデクス値からなっており、
前記画素インデクス値割当て工程が、
(a)  前記ボケ・グラディエント画像の一連の値に対して定義され、かつ前記ボケ・グラディエント画像のどの値ｖに対してもｈ1（ｖ）＞ｈ2（ｖ）となる二つの非減少関数 ｈ1 および ｈ2 を定義する工程と、
(b)  前記非減少関数ｈ1およびｈ2を使用して、前記ボケ・グラディエント画像のそれぞれの値ａを、
第１の閾値 ｈ1 （ａ）、および
第２の閾値 ｈ2 （ａ）
に変換する工程と、
前記グラディエント画像の画素ごとの値をｇとして、
(c)   ｇ ＜ ｈ2（ａ）  のとき、
当該画素に前記第１の画素インデクス値を与える工程と、
(d)   ｈ2（ａ） ≦ ｇ ＜ ｈ1（ａ） のとき、
当該画素に前記第２の画素インデクス値を与える工程と、
(e)   ｈ1（ａ） ≦ ｇ のとき、
当該画素に前記第３の画素インデクス値を与える工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項１８】
請求項１５に記載の方法において、
前記補助２値画像を生成する工程が、
(a)  前記第２または第３の画素インデクス値を持つ画素が連続した領域を含み、かつ、前記第３の画素インデクス値を持つ画素を少なくとも１つ含む３値画像部分において、前記第２の画素インデクス値を持つ画素を全て前記第３の画素インデクス値に置き換える工程と、
(b)  次に、画像全体において、前記第２の画素インデクス値を持つ画素を全て前記第１の画素インデクス値に置き換える工程と、
(c)  その後、画像全体において、前記第３の画素インデクス値を持つ画素を全て前記第２の画素インデクス値に置き換える工程と、
を備え、
前記補助２値画像が、前記第１と第２の画素インデクス値によって表現された２値画像によって得られることを特徴とするデジタル画像の異常検出方法。
【請求項１９】
請求項１４に記載の方法であって、
前記異常候補リスト作成工程が、
(a)  前記補助２値画像から、相互に空間的包含関係にある領域を含めてダスト／キズ候補領域をリストアップした第１異常候補リストを作成する工程と、
(b)  前記第１異常候補リストにおける前記ダスト／キズ候補領域のうち相互に空間的包含関係にあるものを除去することによって、前記第１異常候補リストを第２異常候補リストに再編成する工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項２０】
請求項１９に記載の方法において、
前記第１異常候補リストを形成する工程が、
前記補助２値画像の閉じた輪郭線すべてのリストを作成する工程、
を備え、
前記閉じた輪郭線のそれぞれは、前記オリジナル画像において輪郭線で囲まれた画素群を一義的に特定していることを特徴とするデジタル画像の異常検出方法。
【請求項２１】
請求項１９に記載の方法において、
前記第１異常候補リストを前記第２異常候補リストに再編成する工程が、
(a)  互いに包含関係にある輪郭線同士は同一のセットに含ませるようにしつつ、前記第１異常候補リストを複数のセットへと分割する工程と、
(b)  前記複数のセットのうち単集合でないセットについて、輪郭線同士の包含関係を系列表現することによって、各輪郭線がノードとして定義されたツリーを作成する工程と、
(c)  前記ツリーを順次に検査し、下記の第１規則または第２の規則によって前記ツリーの各ノードを保持または除外するノード検査処理工程と、
を備え、
ここにおいて、前記第１および第２規則は、
(c-１)  第１規則：前記ツリーに１つのノードだけを残す規則、
(c-２)  第２規則：相互に包含関係にない複数のノードを前記ツリーに残す規則、
であることを特徴とするデジタル画像の異常検出方法。
【請求項２２】
請求項２１に記載の方法において、
前記ツリーにおける従属ノードを「子ノード」と呼び、従属先ノードを「親ノード」と呼んだとき、
前記ノード検査処理工程が、
(a)  所定の付与基準によって各輪郭線に付与された異常性指標の値が閾値以下のノードについては、そのノードを前記第２異常候補リストから除外する工程と、
(b)  前記異常性指標の値が前記閾値以上のノードについては、そのノードを前記第２異常候補リストに残し、その輪郭線を親ノードとする子ノードの輪郭線をすべて前記第２異常候補リストから除外する工程と、
(c)  子ノードの輪郭線を持たないノードを前記第２異常候補リストに残す工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項２３】
請求項２に記載の方法であって、
前記異常候補には、ダストとキズとの候補としてダスト／キズ候補領域が含まれており、
前記間引き工程が、
(a)  各ダスト／キズ候補領域およびその周囲領域に、形状指標、サイズ指標、可視性指標およびカラー指標のうちの２以上の指標の値を与える工程と、
(b)  前記２以上の指標の値に基づいて、前記異常候補リストから前記ダスト／キズ候補領域を選択的に間引く工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項２４】
請求項２に記載の方法において、
前記異常候補には、ダストとキズとの候補としてダスト／キズ候補領域が含まれており、
前記間引き工程が、
(a)  各ダスト／キズ候補領域の画素を、当該ダスト／キズ候補領域の周囲領域の画素値に応じた値に置換する試行修復工程と、
(b)  各ダスト／キズ候補領域およびその周囲領域に、形状指標、サイズ指標、可視性指標およびカラー指標のうちの２以上の指標の値を与える工程と、
(c)  前記２以上の指標の値に基づいて、前記異常候補リストから前記ダスト／キズ候補領域を選択的に間引く工程と、
(d)  前記異常候補リストから選択的に間引かれたダスト／キズ候補領域については、前記試行修復工程でいったん置換された画素値を前記オリジナル画像の画素値に戻す工程と、
を備えることを特徴とするデジタル画像の異常検出方法。
【請求項２５】
デジタルのオリジナル画像の欠陥に相当する異常部分を検出するシステムであって、
(a)  前記オリジナル画像の各部のグラディエントを表現したグラディエント画像を生成するグラディエント画像生成手段と、
(b)  前記グラディエント画像の各画素値の大きさに応じて、前記グラディエント画像の各画素を、
1) 比較的大きなグラディエントを有する異常画素と、
2) 中間的なグラディエントを有する疑似異常画素と、
3) 比較的小さなグラディエントを有する正常画素と、
に分類した第１中間画像を得る第１中間画像生成手段と、
(c)  分類された各画素の空間的な相互分布関係に応じて前記第１中間画像中の疑似異常画素の分類を画素ごとに変更することによって、各画素が正常画素と異常画素との２種に区別された第２中間画像を生成する第２中間画像生成手段と、
(d)  前記２中間画像において異常画素の連鎖からなる輪郭線を特定する輪郭線特定手段と、
を備え、
前記第１中間画像生成手段が、
(b-1)  前記グラディエント画像のそれぞれの画素値を複数の閾値と比較して前記分類を行う比較手段、
を備え、
前記複数の閾値は、前記グラディエント画像の各部を平均化したボケ・グラディエント画像の画素値に応じて定められ、
前記輪郭線の情報に基づいて前記オリジナル画像の異常部分を特定することを特徴とするデジタル画像の異常検出システム。
【請求項２６】
請求項２５に記載のシステムであって、
前記複数の閾値は、前記ボケ・グラディエント画像の画素値に対して、単調変化区間と飽和区間とを有する特性線に従って定められることを特徴とするデジタル画像の異常検出システム。
【請求項２７】
請求項２５または請求項２６に記載のシステムであって、
(e)  前記輪郭線のそれぞれについて、検出すべき異常部分の特性をあらかじめ規定した所定のテストを行い、それによって前記輪郭線から選別を行う輪郭線選別手段、
をさらに備えることを特徴とするデジタル画像の異常検出システム。
【請求項２８】
コンピュータのメモリにインストールされ、当該コンピュータのＣＰＵによって実行されることによって、当該コンピュータを請求項１ないし請求項２４のいずれかに記載の方法を実行する装置として機能させるためのプログラムを記憶してあることを特徴とする、コンピュータ読取り可能な記憶媒体。
【請求項２９】
コンピュータのメモリにインストールされ、当該コンピュータのＣＰＵによって実行されることによって、当該コンピュータを請求項２５ないし請求項２７のいずれかに記載のシステムとして機能させるためのプログラムを記憶してあることを特徴とする、コンピュータ読取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、主としてコンピュータ画像処理技術に関するものであり、特に、オリジナルハードコピー画像上に存在するダストやキズに起因する異常部分を、デジタル画像で正確かつ迅速に認識する技術に関する。
【０００２】
【従来の技術】
画像処理における周知の問題点として、ハードコピーのポジ画像またはネガ陰画像上にダストの粒子が堆積したり、カメラやスキャナでその画像の二次コピーをとる前にハードコピーにキズがついたりするという問題がある。そして、写真ポジ／ネガ画像をコンピュータ処理に適したデジタル画像に変換するには、その画像を二次コピーするため、通常のデジタル画像はキズついていたりダストで汚れていたりすることになる。このようなダストやキズを以下では「画像の異常」ないしは「画像の欠陥」と総称することにする。
【０００３】
ダストによる汚れの問題は、早期検出技術（デジタル化する前での画像欠陥の検出技術）または、後期検出技術（デジタル化した後の画像欠陥の検出技術）によって、ある程度解決することができる。
【０００４】
例えばGuter et al.による米国特許第４,１８９,２３５号 ”Test Device for Dynamically Measuring the Degree of Dirt Accumulation on Bank-Notes”で教示されているように、早期検出技術では走査前にオリジナルハードコピー画像上のダストを検出しており、機械的手段によって走査前に画像をクリーンにすることができる。
【０００５】
これに対して後期検出技術は、オリジナル画像上でデジタル画像化されたダストを検出して、コンピュータシステムのユーザがダストを取り除く画像修正を行うというものである。一般に、早期検出技術を実行するには、標準的なデジタル画像処理装置の一部ではない特別なハードウエアが必要となる。それに対し後期検出技術は、通常のデジタル画像処理ハードウエアのみで行うことができる。後期検出技術では画像処理装置のメインコンピュータを使ってデジタル画像中のダストを認識するため、オペレータによる手動操作あるいは増設したコンピュータソフトウエアのどちらかによって画像からダストを取り除くことが可能となる。後述するように、本願発明は後期検出技術に分類される。
【０００６】
一方、Gray et al.による米国特許第５,４３６,９７９号 ”Process for Detecting and Mapping Dirt on the Surface of a Photographic Element”では、早期検出技術と後期検出技術とを合成した技術が教示されている。従来の画像処理ハードウエア及びソフトウエアを使って画像をスキャンしてデジタル画像のダスト画像を検出する、という点ではこの特許は後期検出技術と類似している。しかし、この先行技術の発明では空白画像（フィルムの空白部分）を走査して、ダストが空白画像上で見つかった場合にその後の空白以外の画像上でのダストレベルを最小にするよう、画像スキャナのオペレータがスキャナのクリーニングプロセスを調整できるようにしている。
【０００７】
この技術で走査する「空白」画像は画像としての構造を全く持たないわけではなく、たとえば未露光のフィルムであってもそのフィルム自身の粒状性を含んでいるように、微視的には画像としての構造を持っている。
【０００８】
従って、粒子の粗い走査背景をバックにしてダストの走査画像を認識する問題は、現像済フィルムを走査してダストの走査画像を認識する問題と共通する部分がある。
【０００９】
この米国特許では、(a)デジタル画像をぼかしてボケ画像とし、(b)そのボケ画像とオリジナル画像との差分画像を生成する工程を説明している。この差分画像の中でボケ画像と大きく異なる部分はすべて異常とみなされる。このように検出された異常は、さらなるテストを経て“みなし”ダスト候補となる。
【００１０】
先の米国特許第５,４３６,９７９号に記載されているように、デジタル画像中のダストを探す工程は、画像の異常を探す工程といえる。同じことがキズを探す工程にもいえる。従って、画像中のダスト／キズ検出技術の研究者は、画像の異常を検出する別の技術、例えば特に腫瘍の画像を検出するための医学画像ソフトウエアなどを参考にすることができる。後者の技術は例えば、Doi et al. による米国特許第４,９０７,１５６号 ”Method and System for Enhancement and Detection of Abnormal Anatomic Regions in a Digital Image”で教示されている。
【００１１】
”Abnormal anatomic region”に関する米国特許第４,９０７,１５６号は、オリジナル画像（あるいは単純にそこから派生してできた画像）とぼかしたオリジナル画像との違いから異常候補を検出する、という点で”Detecting and Mapping Dust”に関する米国特許第５,４３６,９７９号に類似している。差分画像の中で極値をとる画素は、オリジナル画像でそれに対応する画素の近傍画素とはかなり異なる値を持つ画素を表しているので、異常候補となる。”Anatomic regions”特許に特有の技術では、腫瘍などの異常な特徴が強調されるＳＮＲ最大化画像（ＳＮＲ＝Ｓ／Ｎ比）と、ボケ画像またはＳＮＲ最小化画像が生成される。そして、ＳＮＲ最大化画像とＳＮＲ最小化画像との差異を示す差分画像が生成される。
【００１２】
差分画像の中で極値をとる画素あるいは画素群は、腫瘍の“みなし”画像候補となる。そして、円環性（circularity）テスト、サイズテスト、及び成長テストを使った続く画像処理を行うことによって、すでに検出された腫瘍候補をさらに特徴づけている。
【００１３】
【発明が解決しようとする課題】
上述のような、画素値を局部近傍の平均画素値と比較する差分技術は、空などの一様なあるいはスムーズに変化する背景をバックにした場合の異常（ダスト、キズ、腫瘍など）を検出するのには役立つが、陽の当たった木の葉や小石だらけのビーチなど多様に変化したり雑然とした背景をバックにした場合の異常検出にはあまり役立たない。
【００１４】
後者の場合、上記差分技術では、疑似陽性、つまり、間違って異常とみなされる画素群を多数作ってしまう。これは、雑然とした画像部分の画素の多くが近傍の平均値とは大きく異なる値を持つという特徴から起こる。通常の差分技術では、この特徴はまさに“異常”の特徴となるので、雑然とした画像領域では極端に多くの疑似陽性ができることになる。
【００１５】
結果的に、そのような技術を用いる場合には、画面からの手動操作あるいは別のコンピュータ処理によって大幅な後処理を行い、疑似陽性画素または画素群をダスト／キズ候補から除外しなければならないという問題がある。
【００１６】
【発明の目的】
この発明は従来技術における上記の問題の克服を意図しており、比較的変化が多い背景をバックにした場合に画像の異常部分の検出を効率よく行うことを目的としている。
【００１７】
【発明の概要】
後に詳述する実施形態での例を引用しつつこの発明を概要を説明すると以下のようになる。ただし、ここでの説明は例示的なものを多分に含んでおり、それらの例示による説明は、この発明の範囲を規定するものではない。
【００１８】
この発明は、例えば写真など、画像上のダストやキズなどの異常を検出するシステムを提供し、先行技術で取り組まれてきた問題を克服している。
【００１９】
例えば、この発明では、誤検出が結果的に減少する。疑似異常の数すなわち疑似陽性数を減らすこの発明の手法の元となる主要概念は、雑然とした画像領域（小石だらけのビーチなど）では一様なまたはスムースに変化する領域（空など）よりもずっと強力な指標を用いて、ダスト／キズ候補として画素をタグ付けするというものである。
【００２０】
この発明では、近傍画素の平均値と大きく異なる値を持つ画素領域ではなく、むしろ近傍画素のグラディエント（微分値ないしは差分値）の平均値と大きく異なるグラディエント値を持つ画素領域をダストやキズ粒子の第１候補として選ぶことによって、最初にパスする疑似陽性の数を減らしている。
【００２１】
画素のグラディエント値は、その画素のすぐ近傍で画像がどのくらい急激に変化しているかを見極める指標となる。この発明では最初にパスするダスト／キズ候補は近傍画素の平均グラディエント値と大きく異なるグラディエント値を持つ画素群なので、画素をダスト／キズ候補としてタグ付けするために必要なグラディエント値は、平滑な画像部分よりも雑然と急激に変化する画像部分での方が高くなる。
【００２２】
総体的に、この発明のダスト／キズ検出手法は以下のように構成されている：
a) 最初にパスする疑似陽性の数を減らす；
b) ロバストで且つバランスがとれている（すなわち、検出される疑似陽性は多すぎも少なすぎもしない）；
c) 処理速度が速い。
【００２３】
これらは相互に関係している。つまり、(a)のように疑似陽性数を減らすと疑似陽性をより分けるのに必要な後処理量が減り、したがって(c)にあるようにシステムが速くなる。
【００２４】
この発明はさらに、（ダスト画素やキズ領域を無効にしたときにできるような）画像中の空隙を埋める発明と組み合わせて実施することにより、デジタル画像のダストやキズを検出し除去する好ましい全体システムを構成することができる。
【００２５】
ここでの穴埋め発明とは、１９９９年５月２９日に出願され、本願と同じ譲受人に譲渡されたMinnerによる米国特許出願第０９／０８７,２８４号”Image Enhancing Brush using Minimum Curvature Solution”のことである。
【００２６】
この発明は、パーソナルコンピュータやデスクトップ型コンピュータのプログラム内で実行される方法を含む。コンピュータユーザはデジタル画像がコンピュータの記憶装置の１つに格納されるようにする。一般にデジタル画像は何百万もの画素からなり、それらの画素は多くの場合に長方形の格子状に配列している。各画素は一つまたはそれ以上のチャネルに分割され、カラーチャネルでの光の強度を符号化している。単チャネル画像は白黒である。一般的な３チャネル画像では、各チャネルが赤（Ｒ）、青（Ｂ）、緑（Ｇ）の光の強度をそれぞれ符号化している。また、典型的な画像では、各画素の各チャネルごとに一定の可能輝度レベル範囲が決まっている。２つしか可能輝度レベルを持たない画像は２値画像である。典型的な多値画像は各チャネルそれぞれ、２５６（またはそれ以上）の輝度レベルないしは階調を持っている。
【００２７】
この発明の好ましい態様では、オリジナル画像に加えて二つの画像を用いることによって、最初にパスするダスト／キズ領域を正確に認識している。
【００２８】
第１の補足画像、つまりグラディエント画像は、オリジナル画像のチャネル（一つまたはそれ以上の）の平均的なグラディエントの大きさの指標となる。この第１補足画像に用いられているグラディエント指標は、オリジナル画像の一つあるいはそれ以上のチャネルを、一つあるいはそれ以上の（通常、２行２列の）カーネルとたたみ込み（convolve）することによって得られる。その目的は、オリジナル画像のうち４つの画素の頂点あるいは交点を中心とする極めて小さなオリジナル画像領域のばらつき度の指標を得ることである。
【００２９】
偶数行列のカーネルを選ぶことによって、これらグラディエント指標のグリッドがオリジナル画像のグリッドの半分だけオフセットされる。つまり、グラディエント画像の各画素の中心が、オリジナル画像の４つの画素の頂点に集中する。従って、グラディエント画像のグリッドとこの画像から派生する画像のグリッドとが、オリジナル画像のグリッドの頂点（画素の中心とは異なる）に定義され、それによって（オリジナル画像に対して）頂点中心のグリッドとなる。オリジナル画像は多くのチャネルを持っているが、グラディエント画像は単チャネル画像である。各画素における最終グラディエント指標は、それぞれのチャネルの同じ位置にある画素のグラディエント指標を組み合わせる処理（平均化または最大値をとる処理など）によって得られる。
【００３０】
第２補足画像、つまりボケ・グラディエント画像は、グラディエント画像の各画素の値をその近傍画素の平均値で置き換えることによって得られる。一般に、この置き換えグラディエント画像をより大きな奇数行列の平均カーネルでたたみ込むことによって行われる。ここで使われるカーネルは、例えば、４１行４１列である。画像端付近の画素の平均値はカーネルの大きさを小さくして実際に画像内にある画素のみをサンプリングするようにすることで得られる。
【００３１】
グラディエント画像とボケ・グラディエント画像は、デジタル画像中のデジタル化されたダスト粒子やキズなどの異常を認識する基礎となる。この認識工程では、ダスト粒子やキズの走査画像は一般に以下の２つの性質を持っているという実験上証明された結果を利用している。
【００３２】
そのような典型的異常の第１の性質は、近傍画素のグラディエント平均値よりずっと大きいグラディエント値を持つ画素を少なくとも一つ（多くの場合は複数）有しているという点である。そのような一まとまりの画素を「卵」との類似によってダスト粒子の「卵黄」と呼ぶ。
【００３３】
第２の性質は、ダスト粒子の「卵黄」から外側にはみ出した画素であって、かつ「卵黄」の画素が局所平均値を越える分よりは少ないものの、ある一定範囲分だけは局所グラディエント平均値を越えるグラディエント値を持った画素も、すべてダスト粒子の一部である、という点である。そのような一まとまりの画素を、再び卵との類似によって、異常の「卵白」と呼ぶ。
【００３４】
この発明の好ましい実施形態では、グラディエント画像の頂点中心画素をスキャンして、
・第１の閾値だけ局所平均値を越えるグラディエント値を持つ画素と、
・それより小さい第２の閾値だけ局所平均値を越えるグラディエント値を持つ画素と、
を探しだす。
【００３５】
そして、それらの画素にはそれぞれ、「２」と「１」が割り当てられる。頂点グリッドのその他の画素は全て「０」とされる。
【００３６】
グラディエント画像とボケ・グラディエント画像に基づいて頂点中心３値画像を形成した後、その画像をスキャンして、「２」の値の画素を少なくとも数個含む、正の値を持つ画素の小塊（一連のセット）を探し出す。つまり、「卵黄」を含む小塊を探し出すのである。「卵白」を含む小塊は全て異常候補と認識され、それらの構成画素は、新たな頂点中心ダスト／キズ候補２値画像で「１」に設定される。そして、「卵黄」を含んでいない小塊は全て無視され、それらの構成画素は新しい２値画像では「０」に設定される。これらの画素インデクス値「０」、「１」、「２」は例示的な値であり、一般には第１から第３の画素インデックス値として定義することができる。
【００３７】
以上がこの発明によるファースト・パス手法である。この手法の目的は、先の先行技術ほどではないが、わずかに疑似陽性よりにある粒子やキズ候補のリストを作成することにある。つまり、ファースト・パス・リストでは、いくつかの実際には存在するダスト粒子が誤って外され（疑似陰性もいくらか含む）、おそらくある程度の数の疑似陽性（疑似陰性よりは多い）が含まれている。このようなリストは、いくつかの疑似陽性を間引くことによって、ダスト粒子やキズの最終リストとなる。
【００３８】
最終的な間引き処理には、疑似陽性をリストから除去するために、可視性（visibility）テスト、カラーテスト、形状テスト、サイズテストなどのうちの少なくとも１つ（好ましくはこれらのうちの複数、さらに好ましくはこれらのすべて）を含む一連の検出的手法が用いられる。
【００３９】
以上の概略では、最初にパスするダスト粒子やキズの認識は、画像値と近隣画像平均値との比較ではなく、求めたグラディエント値と近傍の平均グラディエント値との比較を基礎として行われる、というこの発明の実施形態において最も重要な点を強調した。先にも述べたように、この発明のこの態様によって、疑似陽性の数を先行技術の手法に比べて大幅に削減することができる。
【００４０】
この発明の第２の重要な態様は、頂点中心グリッド上のグラディエント画像とボケ・グラディエント画像（従ってその後のファースト・パス２値ダストマップも）の位置をオリジナル画像の画素からＸ及びＹ方向に半画素分ずらすという点である。オリジナル画像の各画素または一連の画素は、頂点中心グリッドの画素からなる閉じた曲線で囲むことができる。例えば、後述する図２では、オリジナルグリッドの一つの画素１００が頂点中心グリッドの４つの画素１０１、１０２、１０３、１０４で囲まれている。
【００４１】
結果的にこの発明では、前述のファーストパスの最後に生成された頂点中心２値ダスト／キズマップ（リスト）を分析する際、頂点中心画像の正の値からなる閉じた輪郭線を元にしてオリジナル画像のダストやキズの認識を行うことができる。正の値からなる開いた輪郭線は、オリジナル画像のダスト認識をなんら損なうことなく、２値画像から切り捨てることができる。
【００４２】
例えば、図３に仮想の頂点中心ダスト／キズ２値画像が示されている。この画像には、一つの開いた輪郭線２００、一つの閉じた輪郭線２１０、そして閉じた部分２３０と尾部２４０を含む一つの複合輪郭線２２０が含まれている。図４は開いた輪郭線２００と複合輪郭線２２０の尾部２４０が削除された後の、図３と同じ仮想頂点中心ダスト／キズ２値画像を示す。図４で残ったのは、二つの閉じた輪郭線２１０と２３０である。
【００４３】
この発明の実施形態では、オリジナル画像のダストの認識は全て、補助頂点中心２値画像の閉じた輪郭線に基づいて行われる。
【００４４】
この発明のこの態様により、グラディエント画像とその派生画像（２値画像など）が頂点中心画像でない場合と比べて、オリジナル画像のダストとキズの認識がより高速に且つ計算上より簡単に行うことが可能となる。
【００４５】
【発明を構成する手段】
上記の原理に対応した構成として、この発明の請求項１〜請求項２４の方法は、オリジナルデジタル画像中の異常の有無および位置を決定する方法であって、画素の値がオリジナル画像上の対応する位置でのグラディエントの大きさの判断指標となっているグラディエント画像を形成するグラディエント画像形成工程と、前記グラディエント画像を用いて、前記オリジナル画像の異常を決定する異常決定工程とを備える方法と、その好ましい態様を提供する。
【００４６】
また、請求項２５〜請求項２７の発明は、デジタルのオリジナル画像の欠陥に相当する異常部分を検出するシステムであって、(a)前記オリジナル画像の各部のグラディエントを表現したグラディエント画像を生成するグラディエント画像生成手段と、(b)前記グラディエント画像の各画素値の大きさに応じて、前記グラディエント画像の各画素を、
1) 比較的大きなグラディエントを有する異常画素と、
2) 中間的なグラディエントを有する疑似異常画素と、
3) 比較的小さなグラディエントを有する正常画素と、
に分類した第１中間画像を得る第１中間画像生成手段と、(c)分類された各画素の空間的な相互分布関係に応じて前記第１中間画像中の疑似異常画素の分類を画素ごとに変更することによって、各画素が正常画素と異常画素との２種に区別された第２中間画像を生成する第２中間画像生成手段と、(d)前記２中間画像において異常画素の連鎖からなる輪郭線を特定する輪郭線特定手段とを備え、前記輪郭線の情報に基づいて前記オリジナル画像の異常部分を特定することを特徴とするシステムと、その好ましい態様を提供する。
【００４７】
またこの発明では、コンピュータを用いてこれらの方法ないしはシステムを実現するためのプログラムを記憶した記憶媒体も提供する。
【００４８】
【発明の実施の形態】
【システム構成】
図１は、デジタル画像のダストおよびキズを検出しタグ付けする画像処理システムの実施形態を示す。画像処理システム７０は、マイクロプロセッサ７２およびメモリ７４を含むコンピュータシステム７１を備える。マイクロプロセッサ７２は画像処理を行い、メモリ７４は画像処理用のコンピュータコードを保存する。コンピュータシステム７１は、たとえばＰＣ、マッキントッシュ、ラップトップ、メインフレームなど、どのようなタイプのコンピュータでもよい。画像システム７０はまた画像を直接走査するスキャナ８０も備えている。コンピュータシステム７１は、オリジナル画像や処理後の画像（キズなどの修復後の画像）を表示するグラフィカル・ユーザ・インターフェイスとしてのモニタ（ディスプレイ）７６に接続されている。コンピュータシステム７１はまた、内蔵または外付の記憶装置ドライブやマウス、キーボード（図示せず）などさまざまなインターフェイス装置にも接続されている。カラーまたはモノクロのプリンター７８によって、ユーザはどのような画像でも印刷することができる。またケーブル８２を付加することによって、オリジナル画像や修復画像をEメールやインターネット、または直接アクセスなどで別のコンピュータデバイスに伝送することができる。
【００４９】
また、後述するプロセスを実行するためのソフトウエアプログラムは、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭなどの記憶媒体８５に記憶させておくことができる。このプログラムは、コンピュータシステム７１によって読取られてその中にインストールされると、コンピュータシステム７１内のオペレーティングシステム（ＯＳ）と協働することによって後記の画像処理プロセスを実行することができる。
【００５０】
画像は、たとえば写真や印刷紙、本のページなどのハードコピーを平面走査型のスキャナ（たとえば図１のスキャナ８０）によってスキャニングすることで得られる。走査画像はバス７５を介して直接コンピュータシステム７１に送られ、そこでこの発明に基づいて処理される。この発明では、取得画像をコンピュータシステム７１へ送る方法を直接接続のみには限定していない。取得した画像をコンピュータシステム７１に送る際には、周知のどのような技術を用いてもよい。例えば、従来から既知のように、取得画像をメモリディスクに保存してメモリドライブで入力してもよいし、別のコンピュータシステムで印刷してその印刷画像をスキャナ８０で走査してもいいし、また画像伝達はインターネットを通してケーブル８２で行うこともできるし、衛星送信機や地上アンテナを使って行っても良い。
【００５１】
【処理対象画像例】
図５は、例として、平面走査型スキャナを使ってオリジナルの写真画像から取得したデジタル化ダストの写真画像の一部を模式的に示す。図５の左側にはコテージの二階部分が、また右側には木々が、そして中央と上部には空の一部が示されている。目に見えるダスト粒子はほぼ一様な画像のほんの一部分、つまり空の部分だけだが、全体の画像は非常にほこりっぽい（図示の都合上、細かなダストやキズは図５中には現れていない）。物体３００と３０１は大きなダスト粒子である。物体３０２は家の屋根につけられたアンテナである。物体３０３は家につながっている一対の電線である。
【００５２】
図６は、家と空と木の共通部分の領域を中心に図５を引き伸ばしたものである。この図では、ダスト粒子３００、３０１、アンテナ３０２、配線３０３の個々の画素を見ることができる。
【００５３】
このシステムの目的は、アンテナ３０２や配線３０３のように見た目にはダストやキズに似ているが実際には画像の特徴であるという部分をそのままにしつつ、ダスト粒子３００、３０１のような異常ないしは欠陥を（最終的には除去する目的で）図５および図６で示されたような画像の中から検出してタグ付けすることである。
【００５４】
【処理の概要】
図７は、本実施形態によって、図５や図６で示されるような取得画像のダストやキズを検出しタグ付けする工程を示すフローチャートである。コンピュータシステム７１では、ダストやキズを含む初期ステップ４００のオリジナル画像を図７に示される一連の工程によって処理する（詳細は後述する）。そして、ダスト粒子やキズ部分でない原画像の各画素が「０」に設定され、ダスト粒子やキズ部分の画素が「１」に設定された２値画像が、ステップ４５５で生成される。このタグ付けされたダスト２値画像はステップ４６０で、自動的にまたはユーザの介入によってダストやキズを消去するための別のソフトウエアに渡される。
【００５５】
【グラディエント画像の生成】
図７のステップ４１０では、図８に示される方法を使って、オリジナル画像４００から第１補助・多値・単チャネル・頂点中心画像が形成される。一般に、オリジナル画像は一つまたはそれ以上のカラーチャネルを有し、典型的な多チャネル画像は３つ以上のカラーチャネルを有している。多用されているのが、各要素ごとに赤（Ｒ）、緑（Ｇ）、青（Ｂ）の３つのチャネルを持っている画像である。図８は、このような３チャネル構成の例を示している。画像の各チャネルは二つのカーネル（ｘカーネルｋx、およびｙカーネルｋy）でたたみ込み（convolve）され、グラディエント画像（エッジ強調画像）ｇx、ｇyが生成される。
【００５６】
ここで、ｘカーネルｋxおよびｙカーネルｋyは、以下の式１のように定義される。
【００５７】
【数１】
0003877916.tif 000002
【００５８】
このうち、ｙカーネルｋyはｘカーネルｋxの転置行列ｋx(T)に相当する。ここにおいて、記号(T)は行列の転置を表現している。
【００５９】
これらのｘカーネルｋxおよびｙカーネルｋyは、２行２列の空間微分フィルタである。これらのカーネルｋx，ｋyのそれぞれとオリジナル画像とのたたみ込みを求めることは、オリジナル画像の画素値についてＸ方向およびＹ方向の微分画像（差分画像）ないしはエッジ（輪郭）強調画像を求めることに相当する。
【００６０】
これらのカーネルのパラメータαは正の数である。必須ではないが、最終グラディエント画像ｇは、オリジナル画像の個々のカラーチャネルと同じ範囲（同じ最大値および最小値；ないしはダイナミックレンジ）を持つように行列要素の値αを選ぶことが好ましい。αの好ましい値は１／sqrt（８）である。ただし、記号 sqrt（…）は、「…」部分の平方根をとる演算を表している。
【００６１】
各カラーチャネル面は別々にたたみ込み処理される。二つのカーネルの行数と列数はともに偶数（２）であるため、図２の点１０１、１０２、１０３、１０４のようにオリジナル画像の４つの画素の境界頂点を中心としたたたみ込み値が生成されることになる。つまり、たたみ込み画像のすべては、画素を中心とするオリジナル画像に対して、画素の境界頂点を中心とする画像となっている。図８のステップ５１０では、ｘカーネルｋxが各カラーチャネル面でオリジナル画像の画素値Ｍとたたみ込み処理され、もとの各面から新しい面上の画像ｇxが形成される。ステップ５２０では、ｙカーネルｋyが各カラーチャネル面でオリジナル画像の画素値Ｍとたたみ込み処理され、もとの各面から新しい面上の画像ｇyが形成される。
【００６２】
ただし、図８において×印を丸で囲んだ記号はたたみ込み演算を示しており、記号Ｍはオリジナル画像の画素の値を示している。
【００６３】
より具体的には、オリジナル画像の任意の２×２の画素クラスタのそれぞれの画素値をそれぞれ,
Ｍij、Ｍi(j+1)、Ｍ(i+1)j、Ｍ(i+1)(j+1)
とし、２×２カーネルの各成分をそれぞれ、
ｋ11、ｋ12、ｋ21、ｋ22
としたとき、このカーネルと画素クラスタとのたたみ込みは、下記の式２：
【００６４】
【数２】
0003877916.tif 000003
【００６５】
で定義される。
次のステップ５３０では各チャネルごとに、画像ｇxと画像ｇyが、下記の式：
【００６６】
【数３】
0003877916.tif 000004
【００６７】
と組み合わされ、Ｒ、Ｇ、Ｂのそれぞれのカラー成分ごとの画像ｇs（ｓ＝ｒ，ｇ，ｂ）として、３つで一組のエッジ強調画像カラーチャネルｇr，ｇg，ｇbが生成される。画像ｇsは、ｘ方向およびｙ方向のグラディエント値の２乗和の平方根であるから、グラディエント画像ベクトル（画素値の勾配方向に向き、かつ画素値変化率に比例した大きさを持つベクトル）の絶対値に相当する。
【００６８】
最後に、ステップ５４０では、各画素ごとに同じ画素の３つのチャネルの最大値ｇが、下記の式４：
【００６９】
【数４】
0003877916.tif 000005
【００７０】
のように求められ、ステップ５３０で生成された３チャネル画像ｇr，ｇg，ｇbが単チャネル画像ｇに縮約される。
【００７１】
既述したように、ステップ４１０の目的は、オリジナル画像の３つのチャネルから単チャネル・グラディエント画像ｇを生成することである。上述の方法では、各チャネルごとにグラディエント値ｇr，ｇg，ｇbを算出し、最後にそれぞれの最大値（ｇr，ｇg，ｇb）によって画像ｇを定義することによって、３つの別個のグラディエントチャネルを結合して一つのグラディエント画像ｇとしている。
【００７２】
上記のカーネルは微分カーネルであるから、チャネルの値が急激に変化するオリジナル画像領域の中心画素においてその値が大きくなる。そして、各チャネルについてのグラディエント画像の画素値の最大値をとるという合成手法を用いて最終的なグラディエント画像が得られるため、その最終的なグラディエント画像においても、チャネルの値が局所的に最も急激に変化するオリジナル画像領域の中心画素（に対応する位置）において、グラディエント画像の値が極値をとる。
【００７３】
この方法の変形例でも同じ結果が得られる。ある変形例では、三つの値（ｇr，ｇg，ｇb）で定義される平均関数から画像ｇが得られる。また別の変形例では、オリジナル多チャネル画像がまず単チャネルの白黒画像に変換され、その白黒画像からｘ−たたみ込み画像ｇxおよびｙ−たたみ込み画像ｇyが算出される。
【００７４】
【ボケ・グラディエント画像の生成】
図７のフローチャートの次のステップ４１５では、単チャネル・多値・頂点中心ボケ・グラディエント画像ｂｇがグラディエント画像ｇから生成される。ボケ・グラディエント画像ｂｇは、グラディエント画像ｇを正方形の（square）平均カーネルでたたみ込に処理することによって得られる。この平均カーネルには、ステップ４１０のグラディエント画像の生成に使用したカーネル（たとえば２行２列カーネル）よりもずっと大きいものや、奇数の行および列を持つ行列を持つものが選ばれる。こうすることによって、ボケ・グラディエント画像ｂｇをグラディエント画像と同じグリッド上に生成することができる。後者のカーネルの例として、４１行４１列のものが使われる。具体的には、この平均化処理は、下記の式５にしたがって行うことができる。
【００７５】
【数５】
0003877916.tif 000006
【００７６】
ただし、
Ｍ、Ｎは、矩形カーネルの行および列方向のサイズ（画素数）；
Σは、算出しようとするＭ行Ｎ列のボケ・グラディエント画像の画素の近傍（周囲）の矩形の画素マトリクスに含まれる各画素番号（ｉ,ｊ）についての和；である。
【００７７】
ボケ・グラディエント画像ｂｇもまた、オリジナル画像の４つの画素の境界頂点を中心とする画像となっている。
【００７８】
より一般的には、グラディエント画像ｇの各画素の値を、その近傍の複数の画素値の組合せで置き換えることによって、ボケ・グラディエント画像を形成することができる。
【００７９】
上記のようなの平均カーネルは、ボケ・グラディエント画像ｇのそれぞれの画素につき、当該画素の近傍にある各画素のグラディエント値をグラディエント画像ｇから求め、それら各画素のグラディエント値の加重和を用いて、ボケ・グラディエント画像の画素値を算出する手段のひとつの態様として機能する。
【００８０】
上記の平均カーネルは、近傍画素のそれぞれに等じウエイト値を与えた加重和を求めるものであるが、近傍画素の位置によってウエイト値を異なるものとすることもできる。後者の場合には近傍画素の加重平均によってボケ・グラディエント画像が得られる。また、単純平均および加重平均のいずれにおいても、加重和の値は、各近傍画素のうちの最大値と最小値と間の中間値をとる。
【００８１】
ボケ・グラディエント画像を生成する工程では、たたみ込み処理される画素が画像の端部に近すぎてカーネルが画像境界からあふれてしまってたたみ込み値が簡単に定義できない場合であっても、たたみ込みの結果が確実に定義されるような手段を講じている。この実施形態では、画像端付近の画素の平均カーネルを、画像外の画素を抽出しないように調整している。別の変形例では、たたみ込み処理する前の画像をｘ、ｙ両方向に外側に拡大し、そうしてできた境界をオリジナル画像の近傍画素の平均値で埋めることによって、同じ結果を得ている。画像外のサンプリングを避けるためにカーネルや画像を調整するという問題は、グラディエント画像ｇ自身の場合には起こらない。この実施形態のグラディエント画像ｇの生成用カーネルは２行２列の大きさであり、さらにグラディエント画像ｇはオリジナル画像グリッドの内部頂点でのみ定義されるので、グラディエントがどこに定義されたとしても、その生成カーネルは境界線内にあり、またその逆も同じである。
【００８２】
【異常／疑似異常／正常の分類】
図７のフローチャートの次のステップ４２０では、単チャネル・頂点中心・３値画像ｔが、グラディエント画像ｇとボケ・グラディエント画像ｂｇから生成される。この３値画像ｔは、
(1)  ダストやキズなどの異常と判断できる画素と、
(2)  ダストやキズなどの異常の可能性があるが、それだけでは異常と判断できない疑似異常状態にある画素と、
(3)  異常状態や疑似異常状態にはない正常の画素と、
を識別し、それらにラベル（画素インデクスないしはタグ）を付与するプロセスである。
【００８３】
具体的には、グラディエント画像ｇの各画素を、
1) 比較的大きなグラディエントを有する異常画素と、
2) 中間的なグラディエントを有する疑似異常画素と、
3) 比較的小さなグラディエントを有する正常画素と、
に分類する。
【００８４】
このプロセスでは、図９に示すように、大きい閾値関数ｈ1と小さい閾値関数ｈ2とを利用する。
【００８５】
図９には、ボケ・グラディエント画素値aの二つの非減少関数ｈ1とｈ2とが示されている。具体的な関数形も図９中に示されている。これらの関数形は、
(1) 二つの関数がともに非減少関数であり、かつ
(2) 前者の関数の値ｈ1(a)がどの場所においても後者の関数の値ｈ2(a)よりも大きな値を持つ、
ために求められる一般的条件の一例である。
【００８６】
頂点中心３値画像は、グラディエント画像からのグラディエント値ｇと、このグラディエント値ｇと同じグリッド位置におけるボケ・グラディエント値ａから算出される二つの関数ｈ1(ａ)，ｈ2(ａ)とを比較することによって構成される。この方式では、３値マップでの値ｔは以下の式６のようになる。
【００８７】
【数６】
0003877916.tif 000007
【００８８】
換言すれば、３値マップの値ｔは、グラディエント値ｇがボケ・グラディエント画像の対応する値ａに対して小さい場合は最小（ｔ＝０）とされ、グラディエント値ｇがボケ・グラディエント値ａよりもいくぶん大きい場合は中間（ｔ＝１）とされ、グラディエント値ｇがボケ・グラディエント値ａよりも大きい場合は最大（ｔ＝２)とされる。
【００８９】
図９からわかるように、関数ｈ1、ｈ2の双方は、ボケ・グラディエント画素値ａの低レベル領域に規定された比例区間（一般には単調増加区間ないしは単調変化区間）と、中〜高レベル領域での飽和区間（一定区間）とを有している。これは次のような事情に対応している。
【００９０】
すなわち、ボケ・グラディエント画素値ａが比較的小さい領域（すなわち画像の背景が平坦な領域）では、背景平均レベルとの間にエッジ強度（濃度の変化率）に差がある部分はダストやキズである可能性が高いため、それらを異常画素として積極的に検出できるように、上側閾値ｈ1をボケ・グラディエント画素値ａに比例して小さめにとる。
【００９１】
これに対して、ボケ・グラディエント画素値ａが大きい領域（すなわち画像のエッジ強度が平均として高い領域）では、グラディエント画素値ｇが比較的大きくても、それが被写体の一部分の像である可能性も高いため、それらは疑似異常画素として判断を保留することができるように、上側閾値ｈ1を大きめに固定的に設定し、かつ、下側閾値ｈ2を上側閾値ｈ1から比較的離したレベルに固定的に設定する。
【００９２】
以上までの工程で得られる画像が第１中間画像である。
【００９３】
なお、疑似異常画素に分類された画素は、下記の工程において別の基準によって異常画素／正常画素のいずれかに再分類される。
【００９４】
【疑似異常の異常／正常への変換】
図７のフローチャートの次のステップ４２５では、３値画像ｔから単チャネル／頂点中心／２値画像ｂが形成される。
【００９５】
この工程は図１０，図１１，図１２に示されている。
【００９６】
図１０は３値画像を示す。「０」の値を持つ画素を空白、「１」の値を持つ画素を軽いハッチング、「２」の値を持つ画素を網目のハッチングで示す。図１０では３つの「小塊」ないしは画素クラスター、つまり連続するゼロ以外の値を持つ画素の領域が示されている。小塊６００は「２」の値を持つ画素と、「１」の値を持つ画素との両方を含んでいる。小塊６１０は「２」の値を持つ画素のみを含んでいる。小塊６２０は「１」の値を持つ画素のみを含んでいる。
【００９７】
２値マップ生成工程の目的は、「２」の値を持つ画素を少なくとも１つ含む小塊（６００と６１０）のみを保持し、「１」の値を持つ画素のみを含む小塊を切り捨てることにある。この処理の基本原理は、極値画素（「２」の値を持つ画素）を少なくとも一つ含む異常領域（例えば、図１０の小塊６００,６１０）はダストあるいはキズである可能性が高く、そのような極値画素を持たない異常領域（例えば、図１０の小塊６２０）はダスト粒子やキズでない可能性が高い、という経験的結果から来ている。
【００９８】
前工程において、画像の各画素は異常・疑似異常・正常の３種類に分類されたが、次にこのうちの疑似異常画素を、周囲の画素値との関係（空間的な相対分布関係）に基づいて異常画素または正常画素に変換する。これによって得られる画像が第２中間画像である。
【００９９】
具体的なアルゴリズムは以下の通りである。
【０１００】
コンピュータによるデジタル画像処理の分野において、画素領域を埋める手法は周知である。この埋めこみアルゴリズムの詳細については、James D. Foley et al. の”Computer Graphic Principles and Practice, Addison-Wesley Publishing Company, Second Edition in C. １９９５, pp.９７９-９８６”または Andrew Glasner, editor,”Graphic Gens, Academic Press, Inc., １９９０, pp.２７５-２８４”に開示されている。埋めこみアルゴリズムの目的は、すべての候補画素を検出し、その値を目標値にリセットすることであるといえる。ここで候補画素とは、
Ｘ属性  ＝  画素値「１」または「２」を持つという属性；
Ｙ属性  ＝  画素値「２」を持つという属性；
と定義したとき、それ自身はＸ属性を持つとともに、Ｙ属性を持つ他の画素と間接的につながっているすべての画素を指す。「間接的につながる」とは、任意の画素からＹ属性を持つ画素との間にＸ属性を持つ画素のみを通る経路が存在する、という意味である。
【０１０１】
図１１は、図１０の小塊のうちで「２」の値を持つ画素を少なくとも一つ含む小塊が全て「２」の値を持つ画素で埋められた後の状態を示す。
【０１０２】
図１１のケースでの埋めこみ処理の結果、すべての小塊が一様に同一の値（すなわち「２」か「１」）で埋められ、「１」と「２」両方の画素を持つ小塊はなくなっている。
【０１０３】
図１１から図１２の次のステップは２部構成になっている。まず、「１」の値を持つ画素がすべて「０」に設定される。これによって、小塊６２０は消去される。次に、「２」の値を持つ画素がすべて「１」に設定される。これによってできる２値画像（図１２）では、小塊の中の画素はすべて「１」の値をとり、小塊外の画素は全て「０」の値をとる。
【０１０４】
これらをまとめると、正常画素／疑似異常画素／異常画素を区別するための第１ないし第３の画素インデクス値として「０」、「１」、「２」を割り当てたとき、下記のルールによって変換を行っていることになる。
【０１０５】
(a)  まず、第２の画素インデクス値（１）または第３の画素インデクス値（２）を持つ画素が連続した領域を含み、かつ、第３の画素インデクス値（２）を持つ画素を少なくとも１つ含む３値画像部分において、第２の画素インデクス値（１）を持つ画素を全て前記第３の画素インデクス値（２）に置き換える。
【０１０６】
(b)  次に、画像全体において、第２の画素インデクス値（１）を持つ画素を全て第１の画素インデクス値（０）に置き換える。
【０１０７】
(c)  そして、画像全体において、第３の画素インデクス値（２）を持つ画素を全て前記第２の画素インデクス値（１）に置き換える。
【０１０８】
これによって、第１の画素インデクス値（０）と第２の画素インデクス値（１）の２値のいずれかによって各画素が表現された２値画像が得られる。
【０１０９】
【異常画素の小塊の輪郭線の抽出】
図７のフローチャートの次のステップ４３０では、図１２の２値画像から一連の閉じた輪郭線が抽出される。この輪郭線抽出工程は図１３〜図１７、図２、図３で示されている。
【０１１０】
図１３は、図１０〜図１２で示されたのと同じ小塊６００を示している。図１３で小塊６００は拡大され、その２９個の構成画素にはそれぞれ番号がつけられている。
【０１１１】
小塊６００は２値画像ｂの構成要素なので、２値画像と同じ頂点中心グリッドに関係づけられている。この頂点中心グリッドはオリジナル画像グリッドの４つの画素の交点を中心としている。
【０１１２】
小塊６００およびその２値グリッドと、オリジナル画像およびその画素グリッドとの関係を図１４に示す。図１４では、小塊６００の２９個の画素がオリジナルグリッドの頂点を中心としていることがはっきりと示されている。図１４は、ｂ１〜ｂ１５の番号のついたオリジナル画像の１５個の画素を示している。各画素は、小塊６００の４つの頂点中心画素によって完全に囲まれている。
【０１１３】
オリジナル画像の１５個の画素ｂ１〜ｂ１５はまた、小塊６００の輪郭線、つまり小塊６００の端にある一連の画素にも囲まれている。デジタル画像処理分野において、小塊６００のような形の輪郭線を抽出することは周知である。そのような技術は例えば、William K. Prattの”Digital Image Processing, John Wiley&Sons, １９７８,p.５４３”で述べられている。図１５および図１６は小塊６００の輪郭線を示す。図１５では輪郭線の画素が正方形で示され、図１６ではグリッドの画素が×印で示されている。図１４と図１６を比べると明らかなように、図１４で小塊６００の４つの画素によってそれぞれ囲まれたのと同じオリジナル画像グリッドの同じ画素ｂ1〜ｂ15が、小塊６００の輪郭線によって完全に囲まれている。図１４と図１６との比較からさらに、輪郭線から突き出ている輪郭線の異常値点、a1、a2、a24、a29は、オリジナル画像のうち囲まれている点（画素）を認識する場合に何も貢献していないことも明らかである。これらの異常値点は、輪郭線に囲まれた一連の組（ｂ1〜ｂ15）やオリジナル画像の画素に何ら影響を与えず、除去することができる。
【０１１４】
図１６に示されているような第１の輪郭線、ないしは図３に示されているような第１の輪郭線の組を形成した後、図３の輪郭線２００のような開いた輪郭線すべてと、図３の輪郭線２２０の突出部２４０のような閉じた輪郭線のすべての突出とを除去する。その結果、図４および図１７に示すようになる。
【０１１５】
【輪郭線のリスト登録】
それぞれがオリジナル画像の一連の囲まれた画素をはっきりと示すような、上述の閉じた輪郭線はその後すべて、図７のステップ４３５に示すように、第１異常候補リストに登録される。
【０１１６】
それぞれがダスト粒子やキズの候補となる第１異常候補リストのひとつひとつの異常は、必ずしも重複することなく完全に登録されるように保証されているわけではい。つまり、オリジナル画像の各異常画素が第１異常候補リストの一つの輪郭線で囲まれているとは限らない。
【０１１７】
ここでの問題は、輪郭線は図１８に示すようにお互いに囲まれている可能性がある、という点である。図１８では、第１異常候補リストの４つの輪郭線７００、７１０、７２０、７３０が示されている。輪郭線は、×印で示される頂点中心グリッドの各点を結んでいる。オリジナル画像の画素は正方形で示されている。オリジナル画像の画素７４０は２つ以上の輪郭によって囲まれる画素の一例である。この画素は輪郭線７２０、７１０、７００で囲まれている。
【０１１８】
図７で示されるこの実施形態の次のステップ４４０では、オリジナル画像の各画素が最高１つの輪郭線で囲まれるように、十分な要素を第１異常候補リストから間引いている。このステップはまず第１異常候補リストを一連の包含関係輪郭線（enclosure-related coutours）に区分けすることから始まる。
【０１１９】
一方が他方を囲んでいる場合、それら２つの輪郭線は「直接包含関係状態」（directly enclosure-related）にある。
【０１２０】
第１の輪郭線から複数の第三の輪郭線を介して第２の輪郭線まで「直接包含関係性」（direct enclosure relationship）が存在する場合、それら２つの輪郭線は「間接包含関係状態」（indirect enclosure relationship）にある。
【０１２１】
各ペアが間接包含関係態にある一連の輪郭線を包含関係型セット（enclosure-related set）という。第１異常候補リストが包含関係型セットに区分けされた場合、そのようなセットの多くは単集合になる。つまり、第１異常候補リストのほとんどの輪郭線は別の輪郭線を囲んでもいなければ囲まれてもおらず、単集合の包含関係型セットとなる。しかし、図１８に示される４要素セットのように、単集合でない包含関係輪郭線セットもいくつか存在する。
【０１２２】
この実施形態では、そのような多要素一組の包含関係輪郭線はそれぞれ、１つの輪郭線または他の輪郭線を囲まない複数の輪郭線だけ残るように十分な数の輪郭線を除去することによって間引いている。この除去工程については後述するが、その準備段階は、セットの各輪郭線に異常得点（anomaly score）をつけることによって行われる。この異常得点は、図７のステップ４５０の最終検出的間引き処理に関して後で述べられるのと同じ一連の検出テスト（形状テスト、サイズテスト、可視性テストを含むことが好ましいが、必ずしもそれだけには限られていない）のうち１または複数を組み合わせたものに基づいている。輪郭線がダスト粒子やキズである可能性が高いほど、異常得点は高くなる。
【０１２３】
このようにして得られる第１異常候補リストは、補助２値画像の閉じた輪郭線すべてのリストとなっており、閉じた輪郭線のそれぞれは、オリジナル画像において輪郭線で囲まれた画素群を一義的に特定している。そして、それぞれの輪作線（リストの各要素）に異常得点が与えられている。
【０１２４】
【輪郭線リスト中の要素の間引きによる整理】
包含関係型セットの輪郭は、その後、図１９に示されるようにノードの従属関係の系列をツリー表現してグループ分けされる。図１９の矢印は包含関係を示し、丸印で囲まれたひとつひとつがノードである。
【０１２５】
包含関係によって相互に関係付けられているノード（輪郭線）のセットはひとつに限らず、複数存在している場合も多い。図１９において参照番号が付されていないノードのセットは、輪郭線７００から始まるセットとは別のセットである。
【０１２６】
このようなツリーにおいて各輪郭線はノードとして表現され、輪郭線相互の幾何学的包含関係がノード間の親子関係で示される。親子関係ないしは従属関係において、従属ノードを「子ノード」と呼び、従属先ノードを「親ノード」と呼ぶ。この系列図（ツリー）のそれぞれはルートノード（たとえばノード７００）から始まる深さを指標とする方式で縦断的に評価される。そして、各輪郭線の異常得点が閾値と比較される。
【０１２７】
異常得点が閾値より低い場合、その輪郭線は異常候補リストから除外される。異常得点が閾値を越える場合、その輪郭線は異常候補リストに保持され、その子輪郭線（その輪郭線で囲まれているすべての輪郭線）は全てリストから除外される。たとえば、図１９のルートノード７００の異常得点が閾値に及ばないとすると、輪郭線７００は異常候補リストから除外される。次に、輪郭線７１０の異常得点が閾値を越えたとする。そうすると、輪郭線７１０は異常候補リストに残され、その子輪郭線７２０、７３０はリストから除外される。
【０１２８】
縦断的評価中に子輪郭を持たない輪郭線に出くわした場合、その輪郭線は異常候補リストに保持される。たとえば、図１９で、輪郭線７００が閾値テストに落ちた場合、縦断的評価処理は輪郭線７１０に移る。そして輪郭線７１０が閾値テストに落ちた場合、縦断的評価処理は輪郭線７２０に移る。輪郭線７２０は子輪郭線を持っていないので、異常候補リストに保持される。つぎに縦断的評価処理は輪郭線７３０に移り、子輪郭線を持たないこの輪郭線も異常候補リストに保持される。
【０１２９】
上述の間引き工程が第１異常候補リストのすべての包含関係輪郭線セットに対して行われた場合、十分な数の輪郭線がリストから除外され、互いに包含関係を持つ輪郭線は残らない。これによって得られた輪郭線リストが、図７のステップ４４５で示される第２異常候補リストである。現時点でのオリジナル画像の各領域はすべて、第２異常候補リストのうちの最大一つの輪郭線で囲まれていることになる。
【０１３０】
すなわち、第１異常候補リストは、相互に空間的包含関係にある領域を含めてダスト／キズ候補領域をリストアップしたものであり、その第１異常候補リストにおけるダスト／キズ候補領域のうち相互に空間的包含関係にあるものを除去することによって、第１異常候補リストを第２異常候補リストに再編成するわけである。
【０１３１】
ここにおいては、唯一のノード（輪郭線）を残すか、あるいは相互に空間的包含関係にない複数のノード（輪郭線）を残すような再編成がなされている。
【０１３２】
上記の処理規則をまとめると、以下のようになる。
【０１３３】
(a)  所定の付与基準によって各輪郭線に付与された異常性指標（異常得点）の値が所定の閾値以下のノードについては、そのノードを第２異常候補リストから除外する。
【０１３４】
(b)  異常性指標の値が閾値以上のノードについては、そのノードを第２異常候補リストに残し、その輪郭線を親ノードとする子ノードの輪郭線をすべて第２異常候補リストから除外する。
【０１３５】
(c)  子ノードの輪郭線を持たないノードを第２異常候補リストに残す。
【０１３６】
【諸テストによるダスト／キズの抽出】
ダスト／キズ検出およびタグ付け工程の最後のステップ４５０では、一連の検出テストを第２異常候補リストにあてはめて、おそらくダストやキズではなく、真のデジタル画像の状況を示していると思われる輪郭線をリストから除外する。上記一連のテストは、以下で説明されるような一連の可視性テスト、形状テスト、サイズテスト、カラーテストを含むが、これに限定されるものではない。各テストでは得点がつけられ、高い点はダストやキズ、低い点は真の画像の状況を示す。いくつかのテストを以下に説明する。
【０１３７】
【１．可視性テスト】
上述したように、この発明は基本的にオリジナル画像のグラディエントに基づいている。ここで、高いグラディエント値をもつ可能性のあるオリジナル画像のさまざまな特徴を考えてみよう。オリジナル画像のうち、画素値が急速に変化するような領域はどれも高いグラディエント値を持つ。図２０に示すように、そのような領域は図２０(a)のような開いた「崖（cliffs）」と図２０(ｂ)のような閉じた「島（islands）」との両方を含んでいる。そのように基本的に異なる二種類の状況が、第２異常候補リスト４４５の同一の輪郭で囲まれる可能性がある。例えば、図２０(a)は、オリジナル画像の砂丘状の状況８１０を示している。状況８１０の右側では徐々に階調値が上昇しているが、左側は険しい崖になっている。この崖によって画像領域は高いグラディエント値を持つことになる。この高グラディエント画像部分は輪郭線８００で囲まれている。一方、図２０(ｂ)では、全く同じ輪郭線８００は、オリジナル画像において周囲とは異なる画素値を持つ完全な島領域８２０を囲んでいる。
【０１３８】
図２０(a)の輪郭線８００で囲まれる崖のような開いた状況は、画像のダストやキズの特徴ではない。それに対して、図２０(b)の輪郭線８００で囲まれる島７２０のような閉じた特徴はダストやキズの特徴である。
【０１３９】
この発明は、図２０(a)で示されたような崖状態を第２異常候補リストから間引く方法を含んでいる。この方法を図２１に示す。
【０１４０】
図２１(a)および図２１(b)は、横座標軸ｘに画像中の位置を、Ｌ縦座標軸にそれらの位置に沿った画素の輝度（濃度）を示している（輝度であるか濃度であるかは画像がネガであるかポジであるかなどの事情によって定まる）。図２１(ａ)からわかるように、崖領域８００の状況においては、異常部分内の平均輝度ＭＡ１が、異常部分の近傍にある外部画素の平均輝度ＭＮ１と非常に類似している。それに対して、図２１(b)によると、島構造の状況では、異常部分内の平均輝度ＭＡ２は異常部分の近傍の平均輝度ＭＮ２とはかなり異なる。
【０１４１】
崖領域とその周囲間とでは平均輝度差が小さく、島領域とその周囲間とでは平均輝度差が大きい、というこのような相異は、以下の意味では目に見える違いとなる。図２１(ａ)および図２１(b)に示される二つの異常部分を、その画素値を周囲の平均画素値から計算された新しい画素値で置換することによって修復したとする。この場合、当初平均値ＭＡ１を持つ図２１(ａ)の崖領域７００の画素は、そのオリジナル画像の値とほとんど変らない平均値ＭＮ１を持つ新しい値に置き換えられる。したがって、修復は視覚的にはあまり目立たない。それに対し、当初平均画素値ＭＡ２を持つ図２１(b)の島領域７００が、周囲から算出された平均値ＭＮ２を持つ新しい画素値で置き換えられて修復された場合、その修復は視覚的にかなり目立つものとなる。
【０１４２】
従って、オリジナル画像の特徴が崖状かそうでないかは、領域の修復が視覚的にどれほど目立つかどうかで判断できる。視覚的に目立つような修復は、その候補領域がダスト粒子やキズである可能性が高く、崖状でないということを意味する。ほとんど目立たない修正はその逆を意味する。
【０１４３】
したがって、着目領域内の平均輝度（濃度）とその周囲の近傍領域の平均輝度（濃度）との差を表現した可視性指標は、その特徴がどれくらいダスト状またはキズ状であるかを計る指標となる。この実施形態では、異常リストの各輪郭ごとに、得点としてそのような可視性指標を生成して各異常候補に付与している。
【０１４４】
【２．サイズテスト】
小さな候補領域は大きな領域よりもダスト粒子やキズである可能性が高い。この実施形態では、各候補領域のサイズ（画素数）を算出し、そのサイズから、サイズの逆数のように、領域のサイズが小さくなるとともに増加する指標を作成している。そのような指標はダストを示す指標となり、これも得点として異常リストの各輪郭に与えられる。
【０１４５】
【３．形状テスト】
ダスト粒子やキズは両方とも、その厚さが薄い傾向にある。画素領域の厚みの定義づけは、領域の画素の埋めこみ度（embeddedness）を指標として行うことができる。ある画素の埋めこみ度を（画素を四角と考えて）画素間の境界線の数と定義する。ここで画素境界線とは画素の中心から領域外のある画素の中心へ移動する場合に横断しなければならない線のことである。したがって、例えば、領域の端部にある画素は埋めこみ度「１」、境界内のさらに奥にある画素を埋めこみ度「２」とする。したがって、着目領域の厚みは、領域の一番奥まった位置にある画素の埋めこみ度と定義することができる。厚み値が大きいということは、その領域がダストでもキズでもないということを表している。逆に言えば、厚みの逆数（つまり領域の薄さ）がダストの指標となり、これも得点として異常リストの各輪郭に与えられる。
【０１４６】
【４．カラーテスト】
デジタル画像処理の分野において、色を表す三要素（赤、緑、青）を新しい三要素（色相、彩度、輝度）に変換することは周知である。この新しい三要素の構成要素はそれぞれ、色の色相を０〜３６０度の間の角度で、色の彩度を「０」と「１」の間の数で、色の輝度を「０」と「１」の間の数で表す。そのような指標の詳細については、たとえばJames D. Foley et al.の”Computer Graphics Principles and Practice, Addison-Wesley Publishing Company, Second Edition in C, １９９５, Ch.１３, pp. ５６３-６０４”に開示されている。既述したように、ダストらしいものを検出する指標のひとつは、周囲画素の平均輝度に対する候補画素群の平均輝度が大きいとダストである可能性が高いことに基づいている。ダストらしいものを検出する指標の他のものは、画素群の平均色相／彩度指標および周囲画素の平均色相／彩度指標が大きいとダストではない可能性が高いことに基づいている。
【０１４７】
そのような指標は、候補領域の平均ペア（色相、彩度）と周囲領域の平均ペア（色相、彩度）間のユークリッド距離から構成できる。また、彩度を無視して色相の角度差のみから構成された別の指標は、候補領域の平均色相角と周囲領域の平均色相角との差である。
【０１４８】
たとえば、着目している領域におけるオリジナル画像の平均色ベクトルをＣ0し、その周囲領域における平均色ベクトルをＣ1としたとき、それらの色相の角度差は、以下の式７で表現することができる。
【０１４９】
【数７】
0003877916.tif 000008
【０１５０】
ただし、記号 Abs(…) は、ベクトルの絶対値を示す記号であり、「Ｃ0・Ｃ1」はベクトルＣ0とＣ1との内積である。
【０１５１】
これらの距離や差は、その逆数をとって近接性指標(proximity measure)に変換される。ここで明確になったことは、異常候補と周囲との色相や彩度の違いが大きいほど、その候補はダストやキズというよりはむしろ画像の本物の物体（たとえば花など）である可能性が高い、ということである。したがって、色相や彩度の近接性指標がダスト指標となり、これも得点として異常リストの各輪郭に与えられる。
【０１５２】
【最終異常リストの生成と異常領域修復】
一連の検出指標を計算した結果は表形式で表現されるが、この表の行には第２異常候補リスト４４５の輪郭線の認識番号が、列にはそれら粒子がどれほどダスト状かキズ状かを表すそれぞれの検出指標（可視性、サイズ、形状、カラー指標を含むがそれのみに限定されない）の値が示される。そして、これらに基づく異常決定規則を公式化する。この規則によって、いくつか（好ましくは２以上）のテストにおいてスコアの低い（すなわち所定の閾値以下のスコアを持つ）ダスト／キズ候補領域が、異常リストから除外される領域とみなされる。この決定規則がリストの各輪郭ごとの一連の検出指標にあてはめられ、指標についての条件を満たさない輪郭線がリストから除外（間引き）される。
【０１５３】
この輪郭線選別プロセスないしは検出／間引きプロセスの結果、第２異常候補リスト４４５の要素の部分集合を含む新しいリストができる。このリストが図７の最終異常リスト４４５である。最終異常リスト４４５の各要素は、頂点中心グリッドの閉じた輪郭線である。このため、図１７に示すように、各輪郭線はそれぞれオリジナル画像のどの画素を囲むかを一意に決定する。従って、ステップ４４５の最終異常リストによって、ステップ４４５でオリジナル画像の画素グリッド上の最終２値画像が決定されることになる。この２値画像では、ダストやキズ領域内のすべてのオリジナル画像画素は「１」の値を持ち、それ以外の画素はすべて「０」の値を持っている。
【０１５４】
オリジナル画素のそれぞれは画面上での２次元的位置がそれぞれ定義されており、それから導出されたグラディエント画像その他の各画像の画素もまたその座標値が付随している。したがって、最終異常リストに登録されている輪郭線もそれ自身の位置情報を有しており、それによって囲まれる領域の各画素の座標値も特定することができる。このため、最終異常リストを参照することによって、ダストやキズなどの異常部分の有無と、（異常部分がある場合には）その位置とを特定することができる。
【０１５５】
本発明を実現する、ダストやキズを検出しタグ付けするためのコンピュータソフトウエアを実際に応用することによって実行される次のステップでは、オリジナル画像からダストやキズのサブ画像を除去する。この異常を除去するステップは図７のステップ４６０に相当し、さまざまな度合いのユーザ介入によって行うことができる。最も非自動的な例としては、異常候補リストの一連の異常がコンピュータスクリーン上に強調表示され、どの異常を除去するかをコンピュータユーザが選ぶことができる。最も自動的な例としては、最終異常リストのすべての異常を、１９９８年５月２９日に米国特許庁に出願され、本願と同じ出願人に譲渡されたMinnerによる米国特許出願第０９／０８７,２８４号“Image Enhancing Brush using Minimum Curvature Solution”の発明手法を用いて除去することができる。上記発明では、最終異常リストの全ての異常がまず、オリジナル画像で空隙に変換される。つまり、すべての画素が「０」にセットされる。そして空隙がそれらを取り囲む領域の画素値を元に埋められる。
【０１５６】
【変形例】
この発明の変形例として、先に引用された異常除去技術を検出／間引きステップ４５０の手段として用いることができる。この変形例では、図７のステップ４５０〜４６０を図２２のステップ４６５〜４８０に置き換える。
【０１５７】
上述の検出／間引き工程（図７のステップ４５０）では、異常候補の平均輝度を周囲画素の平均輝度と比べる可視性テストを行っていた。また、異常候補の平均色相／彩度と周囲画素の平均色相／彩度とを比べるカラーテストも行っていた。
【０１５８】
このようにある領域とその近傍領域とを比較する手法の一つとして、まずその領域の試行的修復を行って、それからその領域の修復前後の画素の平均特徴（輝度、色相、彩度など）を比べるというのがある。この修復アルゴリズムは、周囲の画素領域の画素値を使用して修復された異常候補領域の画素は、周囲の領域そのものの画素に類似している、というものである。したがって、修復前後の領域の画素を比べるということは、異常候補領域の画素とその周囲の領域の画素とを比べるということとほぼ同じである。
【０１５９】
この変形例では、異常の除去を実行するステップ（図２２のステップ４６５）を、第２異常候補リストの生成直後に行う。ステップ４６５では、すべての異常が、図７の実施形態の最終ステップ４６０と同じ手法を用いて除去される。しかし、異常除去ステップ４６５は、最終ステップではなく試行ステップである。特に、推定された異常候補が実際の異常でないとわかった場合に第２異常候補リスト４４５の削除された異常をどれでも元に戻せるように、オリジナル画像は修復された異常画像と共にコンピュータメモリに保存されている。
【０１６０】
図２２のステップ４７０においては、試行的に異常部分を修復したものを対象として、検出／間引き処理を行う。特に、異常得点を生成する工程では、修復前と修復後の異常画素を比較することによって得られる統計を利用している。
【０１６１】
図２２のステップ４７５では、検出／間引き工程の結果として、図７のステップ４５５のような、最終異常リストが得られる。
【０１６２】
この図２２の変形例は、図７の実施形態よりも計算処理上かなり有利である。すなわち、すべての異常候補の試行的修復を完了したものが、ステップ４６５の結果としてコンピュータビットマップに保存されており、オリジナル画像もまた保存されている。したがって、オリジナル画像からすべての異常を除去するという図２２のステップ４８０の工程は、単に第２異常候補リスト４４５について、
(a)  異常が最終異常リストからはねられている場合には、試行的修復を行った画像部分にオリジナル画像の該当部分のビットマップ画像を与えて復元し、
(b)  異常が最終異常リストに保持されている場合には、試行的修復を行った画像部分には何も行わない（したがって、修復されたままの状態となる）、
という処理に相当している。そして、このようにして修正された試行画像が最終修復画像となる。
【０１６３】
このように、最終画像に必要な画像は全てオリジナル画像かあるいはステップ４６５で生成された試行画像に存在するために、図２２の最終ステップ４８０は、修正画像を明確化する工程といえる。
【０１６４】
すなわち、この変形例においては、ダストとキズとの候補としてダスト／キズ候補領域が含まれた異常候補について、各ダスト／キズ候補領域の画素を、当該ダスト／キズ候補領域の周囲領域の画素値に応じた値に置換する。
【０１６５】
そして、各ダスト／キズ候補領域およびその周囲領域に、形状指標、サイズ指標、可視性指標およびカラー指標のうちの２以上の指標の値を与える。
【０１６６】
そして、各ダスト／キズ候補領域およびその周囲領域におけるそのような２以上の指標の差を所定の閾値と比較し、閾値以下の指標差を持つダスト／キズ候補領域（つまり修復前後のこれらの指標の差が小さいダスト／キズ候補領域）については、異常候補リストから選択的に間引かれる。
【０１６７】
そして、異常候補リストから選択的に間引かれたダスト／キズ候補領域については、上記の試行修復工程でいったん置換された画素値をオリジナル画像の画素値に戻すのである。
【０１６８】
結果として、この発明は、デジタル画像のダストやキズ部分を認識しタグ付けするという問題に対して効果かつ効率的な解決法を提供している。以上がこの発明の実施形態に関する記述の全てだが、これ以外にもさまざまな代替案や、変形例、また同等な方法を用いることが可能である。
【０１６９】
たとえば、実施形態に含まれる多くの処理ステップはそれぞれ、異常候補やその他の要素に順次に適用されている。すなわち、処理ステップをＡ，Ｂ，Ｃとしたとき、異常候補やその他の要素１、２、…ｎにこれらの処理ステップＡ，Ｂ，Ｃが順次適用されており、ｎ＝２の場合には、動作順序は、Ａ１、Ａ２、Ｂ１、Ｂ２、Ｃ１、Ｃ２となる。ただし、Ａ１はステップＡを要素１に適用することを表しており、他も同様である。このような場合の多くは、それぞれの処理を各要素に順次適用することもできる。例えば上の例で言えば、処理順序はＡ１、Ｂ１、Ｃ１、Ａ２、Ｂ２、Ｃ２とすることもできる。
【０１７０】
より具体的な例として、図２２の場合、まずステップ４６５でｎ個の異常すべてに対して異常除去実行工程（Ａ）が行われ、つぎにｎ個の異常すべてに対して検出／間引き工程（Ｂ）を行うことができる。そのかわりに、異常１に対して工程（Ａ），（Ｂ）を行い、その次に異常２に対して工程（Ａ），（Ｂ）を行う、というやり方でもよい。
【０１７１】
ダスト／キズ除去に関する発明は通常、ユーザ操作によって行われる、より大規模なコンピュータアプリケーションの一部である。画像汚染がダストやキズが原因で生じる可能性があるという印象をユーザが持っている場合もある。この場合、ユーザは、ダストである可能性を示す一方の極値からキズである可能性を示す他方の極値へスケールを絶えず動かしながら調節する。ここで中間の値はダストとキズ両方の可能性があることを示す。そして、このような指針に基づいて、異常候補のダストらしさの特性またはキズらしさの特性の指標に、大きなまたは小さなウエイトを与えるように、図７の検出／間引き処理４５０のために得られた検出指標の重み付けが行われる。
【０１７２】
これまでに説明されたものに加えて、ダストらしさの指標またはキズらしさの指標の他ものを、ダストやキズの検出のために使うこともできる。たとえば、図７のステップ４１０のオリジナル・グラディエント画像の構造は、画像の各チャネルごとに別個のｘグラディエント指標ｇxおよびｙグラディエント指標ｇyの構造を含んでいた。これら別個のｘグラディエント及びｙグラディエントは、各チャネルごとに g ＝ sqrt（ｇx2＋ｇy2）の式によって一つに合成され、その後、構成要素ｇxとｇyは切り捨てられていた。ここでｘグラディエントおよびｙグラディエント構成要素を保持し、頂点中心・２チャネル２値グラディエントマップ（ｇx、ｇyが二つのチャネルとなる）を生成することは、後の検出／間引き工程で役立つ。後者のマップは各画素ごとのベクトルグラディエント（ｇx，ｇy）を示している。後者のペアはその後、別の形式の可視性検出テストを発展させるのに利用できるかもしれない。このテストの目的は、図２０および図２１で示したように、輪郭線で囲まれたオリジナル画像の特徴が崖状か島状かを判断することである。その領域のグラディエントベクトル（ｇx，ｇy）に関する知識はそのような判断を行う際の助けとなる。
【０１７３】
上記の実施形態ではＢＧＲの３原色カラーチャネルを持つオリジナル画像を処理したが、ＹＭＣＫの４色カラーチャネルを持つオリジナル画像についての処理などにも適用できる。モノクロ画像への適用も可能である。
【０１７４】
以上、この発明の実施形態について説明したが、これはこの発明の範囲を限定するものではなく、特許請求の範囲に規定する範囲内においてさまざまな代案、変更などが可能である。
【０１７５】
【発明の効果】
以上説明したように、請求項１ないし請求項２７の発明ではグラディエント画像の状況に応じて異常検出を行っており、比較的変化が多い背景をバックにした場合に画像欠陥の検出を効率よく行うことができる。
【０１７６】
請求項１の発明では、グラディエント画像のほかにボケ・グラディエント画像をも作成し、それらを用いてオリジナル画像の異常を検出する。したがって、背景部分の平均的レベルを考慮しつつ画像欠陥を特定できる。
【０１７７】
請求項２の発明では、グラディエント画像とボケ・グラディエント画像とを利用して検出した異常候補をすべて画像欠陥とするのではなく、それらから間引きを行うことによって真の画像欠陥に対応した異常のみを残すことができる。
【０１７８】
請求項１１の発明では、カラー画像についての異常検出を、単一チャネルの画像の異常検出で実行可能となり、処理がさらに効率化する。
【０１７９】
請求項１８の発明では、異常、疑似異常、正常を区別する３種類の画素インデクス値のいずれかがそれぞれ与えられた各画素の相対的分布関係から画素インデクス値の再構成を行うため、疑似異常を異常または正常の画素として扱うことが可能になり、異常検出の正確性が向上する。
【０１８０】
請求項２１の発明では、異常候補の輪郭線を、それらの空間的関係からツリー構造に整理し、互いに包含関係にある輪郭線についてはひとつのみを残すようにしているため、実質的に同じ異常領域が複数の輪郭線によって重複して表現されてしまうことがない。
【０１８１】
請求項２３の発明では、異常候補について複数のテストを行って真の異常部分を特定するため、擬似的な異常部分が排除される。
【０１８２】
請求項２５〜請求項２７のシステムでは、グラディエント画像の画素値に応じて異常画素、疑似異常画素、正常画素に分類し、これらの画素の空間的な相互分布関係に基づいて疑似異常画素を異常画素と正常画素とに再構成するために、正常と異常との境界にある画素を正常とするか異常とするかを系統的に決定できる。
【０１８３】
請求項２８および請求項２９の記憶媒体を利用することによって、上記の利点を有する方法ないしはシステムを、コンピュータを用いて実現可能である。
【図面の簡単な説明】
【図１】  デジタル画像のダストおよびキズを検出しタグ付けする画像処理システムの実施形態を示す図である。
【図２】  オリジナル画素グリッドと頂点中心画素グリッドの相対位置を示す図である。
【図３】  頂点中心グリッド上の開いた輪郭線、閉じた輪郭線、複合輪郭線を示す図である。
【図４】  簡略化後の図３の輪郭線を示す図である。
【図５】  デジタル化されたダストの一部を示す図である。
【図６】  図５の拡大図であり、個々の画素を示す図である。
【図７】  実施形態の動作を示すフローチャートである。
【図８】  オリジナル画像からのグラディエント画像生成を示す図である。
【図９】  ボケ・グラディエント画像値からの上側閾値および下側閾値算出を示す図である。
【図１０】  頂点中心３値画像からの頂点中心２値画像生成を示す図である。
【図１１】  頂点中心３値画像からの頂点中心２値画像生成を示す図である。
【図１２】  頂点中心３値画像からの頂点中心２値画像生成を示す図である。
【図１３】  輪郭線抽出工程を示す図である。
【図１４】  輪郭線抽出工程を示す図である。
【図１５】  輪郭線抽出工程を示す図である。
【図１６】  輪郭線抽出工程を示す図である。
【図１７】  輪郭線抽出工程を示す図である。
【図１８】  包含関係による輪郭線クラスを示す図である。
【図１９】  それ以上包含関係が存在しなくなるまで包含クラスからセットを取り除くのに用いられる包含ツリー系列図である。
【図２０】  同じ輪郭線を持つオリジナル画素領域における二つの異なる特徴を示す図である。
【図２１】  間引き工程で用いられる画素領域の性質を示す図である。
【図２２】  変形例の最後の５処理を示す図である。
【符号の説明】
１００  オリジナル画像の画素
１０１〜１０４  頂点グリッド上の画素
２００〜２４０，８００〜８２０  輪郭線
３００，３０１  ダスト
Ｍ  オリジナル画像
ｋx  ｘ−カーネル
ｋy  ｙ−カーネル
ｇx  ｘ方向のグラディエント画像
ｇy  ｙ方向のグラディエント画像
ｇs  グラディエント画像ベクトルの絶対値
ｇr，ｇg，ｇb  エッジ強調画像のカラーチャネル
ｇ  （ｇr，ｇg，ｇb）の最大値
【図１】
0003877916.tif 000009
【図２】
0003877916.tif 000010
【図３】
0003877916.tif 000011
【図４】
0003877916.tif 000012
【図５】
0003877916.tif 000013
【図６】
0003877916.tif 000014
【図７】
0003877916.tif 000015
【図８】
0003877916.tif 000016
【図９】
0003877916.tif 000017
【図１０】
0003877916.tif 000018
【図１１】
0003877916.tif 000019
【図１２】
0003877916.tif 000020
【図１３】
0003877916.tif 000021
【図１４】
0003877916.tif 000022
【図１５】
0003877916.tif 000023
【図１６】
0003877916.tif 000024
【図１７】
0003877916.tif 000025
【図１８】
0003877916.tif 000026
【図１９】
0003877916.tif 000027
【図２０】
0003877916.tif 000028
【図２１】
0003877916.tif 000029
【図２２】
0003877916.tif 000030