画像領域補間
画像内の画素値を計算するための画像処理方法が開示される。該方法は、計算すべき対象画素の各々に対して、該対象画素の周囲の局所的な画像パターンを表すテンプレートパターンを規定することを含む。テンプレートパターンは、各対象画素が、テンプレートパターンの少なくとも２つに存在するように規定される。各テンプレートパターンに関して、画像の全体を含むか又はテンプレートパターンよりも大きい画像の領域を含む、探索エリアが規定される。各テンプレートパターン内の画素の値を、複数の候補パターンの各々の該画素の該値と比較し、各候補パターンは、そのテンプレートパターンのための探索エリアからの領域を含む。各対象画素に関して、該画素のテンプレートパターンとの最良一致を表す候補パターンを選択する。次に、選択された候補パターンから対象画素のそれぞれの画素値を求める。さらに、この方法で、対象画素の値を、対象画素を含む他の各テンプレートパターンから求める。その後、結果の値が、選択された各候補パターンから求められた画素値を結合することによって、各対象画素に対して生成される。有利には、選択されるパターンは、対応する対象画素の近くには限定されない。したがって、対象画素は、単なる対象画素の局所的な画像データではなく、対象画素の周囲の局所パターンに対する最良一致を与える画像データから計算される。応用は、スキャン画像における画素補間並びに汎用画像／ビデオの処理、復元及び編集を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本出願は、２００９年４月１５日付の欧州特許出願第０９１５７９４１．７号明細書に基づき優先権を主張する。欧州特許出願第０９１５７９４１．７号明細書は、本明細書中にその全体が記載されたものとして援用される、
【０００２】
［発明の分野］
本発明は、欠陥又はアーチファクトを有する画像データを処理して、補正された画像データを生成するための画像処理に関する。
【０００３】
本発明は、限定するものではないが、印刷されたテキストのページ、グラフィクス、画像等の文書をスキャンするスキャナから得られた画像データの処理に特に有用である。スキャナは、デジタルコピー機やファクシミリ装置等の一部を構成することもできるし、又はパーソナルコンピュータ等に接続されるフラットベッドスキャナやハンドヘルドスキャナ等のスタンドアロンシステムを構成することもできる。したがって、画像処理は、スキャナそのものの内部で行うこともでき、スキャナを含む装置内で行うこともでき、スキャンされた画像データをスキャナから受信する装置内で行うこともできる。
【背景技術】
【０００４】
多くの従来の文書スキャナ、特にフラットベッドスキャナは、密着イメージセンサー（ＣＩＳ）を使用して、スキャン画像データを生成する。
【０００５】
ＣＩＳは、スキャン中の文書を照明する光源（通常はＬＥＤで構成される）と、文書から反射された光を検出するセンサーと、反射光をセンサー上に集光するレンズ系とを備える。ＣＩＳ撮像系は通常、図１に概略的に示すセンサチップ（１）、（２）、…、（Ｎ）のラインセンサからなる。
【０００６】
そのような画像センサチップのリニア配列の１つの問題は、スキャンされた文書中の欠落画素である。画像センサチップの不正確な配置のため、このような画素は、画像センサチップ間において取り込むことができない。この問題を図２に示す。図２は、２つの隣接する画像センサチップＫ及びＫ＋１の間のギャップを示し、垂直走査方向の場合、このギャップは、スキャンされた文書において欠落した画素列となる。
【０００７】
欠落画素の問題に対して考え得る解決策は、３つのカテゴリに分類することができる。
１．センサチップの新たなレイアウトの設計。センサチップ間のギャップを除去するために、センサチップを図３に示すような「千鳥行(staggered row)」に配置することができる。この場合、欠落画素の問題は存在しないが、別の問題が生じる。すなわち、センサチップ間での画像のつなぎ合わせである。また、この解決策は、既存のＣＩＳ製品の完全な再設計と、異なるモデルの市場への導入を必要とする。
２．センサチップの高精度な配置。この解決策では、センサチップ間のギャップを、隣接するセンサチップのＲＧＢセンサー間の距離を最小化することにより除去する（図２）。しかしながら、これは、高価な機器と製造技術の変更を必要とする高コストの解決策である。
３．画像の近傍から必要な欠落画素値を取得する画像処理方法による画素補間。これは、画像処理ハードウェアを更新することによって実装でき、よって、再設計も製造技術の変更も必要とすることなく既存のＣＩＳ製品を更新できるため、比較的低コストな手法である。
【０００８】
標準的な画像補間方法の主な問題は、テクスチャーのあるエリアの画素値については、局所的な画素近傍が必要な情報を含まないので正確に再構成できないという点である。図４は、この問題の一例を示すものであり、スキャン画像の一列が欠落した断片を左側に示し、線形補間の結果を右側に示す。結果の画像における補間誤差は、ユーザーにとてもはっきりと見える。
【発明の概要】
【０００９】
本発明によれば、画像を定義する画像データを処理して、該画像内の複数の画素について画素値を計算する方法であって、
値を計算すべき各画素に関して、画素のテンプレートパターンを複数規定することであって、各テンプレートパターンが前記画像の異なる領域を含み、値を計算すべき前記画素を含むようにする、テンプレートパターンを規定することと、
各テンプレートパターンに関して、
−前記画像の全体を含むか、又は前記テンプレートパターンよりも大きい該画像の領域を含む、探索エリアを規定すること、
−前記テンプレートパターン内の前記画素の前記値を複数の候補パターンの各々の該画素の該値と比較することであって、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの異なる領域を含み、該テンプレートパターンと前記候補パターンとの間の類似度を表す各候補パターンについて類似度測度を導出するようにする、比較すること、
−前記複数の候補パターンから、前記テンプレートパターンとの最高の類似度を表す前記類似度測度を有する候補パターンを選択すること、及び
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めることと、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成することであって、各値が異なる候補パターンから導出されるようにする、生成することと、
値を計算すべき各画素に関して、該画素に対する前記導出された画素値を結合することと、を含む、方法が提供される。
【００１０】
本発明はまた、画像を定義する画像データを処理して、該画像内の複数の画素について画素値を計算するように動作可能な画像処理装置であって、
前記画像内の、値を計算すべき各画素に関して、画素のテンプレートパターンを複数規定するように動作可能なテンプレートパターン選択器であって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、各テンプレートパターンが値を計算すべき前記画素を含むようにする、テンプレートパターン選択器と、
各テンプレートパターンに関して、前記画像の全体を含むか又は前記テンプレートパターンよりも大きい該画像の領域を含む、探索エリアを規定するように動作可能な探索エリア選択器と、
各テンプレートパターンに関して処理を行うように動作可能なパターンマッチャであって、
前記パターンマッチャは、前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々の該画素の該値と比較し、
各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含み、
前記パターンマッチャは、前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択するように動作可能であり、
前記パターンマッチャは、前記テンプレートパターン内の値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めるように動作可能であり、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成し、各値が異なる候補パターンから導出される、
パターンマッチャと、
値を計算すべき各画素に関して、該画素値に対する前記導出された画素値を結合するように動作可能な画素コンバイナと、を備える、画像処理装置を提供する。
【００１１】
本発明はさらに、プログラマブル処理装置を、上述のような方法を行うように動作可能となるようにプログラムするためのコンピュータプログラム命令を担持するコンピュータプログラム製品（コンピュータ可読記憶媒体やコンピュータ可読信号等）を提供する。
【００１２】
次に、本発明の実施形態を単なる例示として、添付図面を参照して説明する。
【図面の簡単な説明】
【００１３】
【図１】従来のＣＩＳにおける画像センサチップレイアウトを概略的に示す図である。
【図２】従来のセンサチップの欠落画素の問題を示す図である。
【図３】欠落画素の問題に対処するためのＣＩＳセンサチップの代替的なレイアウトを示す図である。
【図４】テクスチャーのあるエリアにおける欠落画素の線形補間に関する問題を示す図である。
【図５】本発明の実施形態において使用される最良一致パターン技法を示す図である。
【図６】本発明の実施形態における最良一致パターンからの画素の平均化による画素補間を示す図である。
【図７】一実施形態によって図４の画像に対して行われる処理の結果を示す図である。
【図８】一実施形態によってテキストを含む画像に対して行われる処理の結果を示す図である。
【図９】本発明の第１の実施形態の構成要素を概略的に示す図である。
【図１０】第１の実施形態によって行われる処理動作のフローチャートである。
【図１１】一実施形態における、補間すべき画素、テンプレートパターン及び補間すべき画素を中心とする探索エリアのレイアウト例を示す図である。
【図１２】最良一致パターンからの画素を累積するために第１の実施形態において行われる処理を示す図である。
【図１３】「ライン入力−ライン出力」の実装を使用する一実施形態の場合の、入力画像ラインと出力画像ラインとの間の遅延を示す図である。
【図１４】一実施形態における提案された方法の反復的実装のフローチャートである。
【図１５】一実施形態における反復０の結果と反復１の結果との間で決定を行うための処理のフローチャートである。
【図１６】任意形状の領域に対処するために変更形態において使用される最良一致パターン技法を示す図である。
【図１７】任意形状の領域に対処するための変更形態における最良一致パターンからの画素の平均化による画素補間を示す図である。
【発明を実施するための形態】
【００１４】
本発明の実施形態を説明する前に、理解を助けるために、実施形態の基礎となる動作の理論、及び結果の例を説明する。
【００１５】
各実施形態は、類似するパターンからの画素の非局所的平均に基づく画素補間方法を使用する。より詳細には、図５に示すように、補間の必要な各画素に関して、その周囲の小さな２Ｄパターン（テンプレートパターン）を、ある（好ましくは大きな）探索エリアにおける他の全てのそのような２Ｄパターンと照合する。
【００１６】
図５を参照すると、画素（ａ）、（ｂ）及び（ｃ）は、補間が必要な画像列からの３つの画素である。補間される領域の各画素（黒丸）の周囲の矩形は、探索エリアからの他の全てのパターンと照合されるパターンを示す。矩形（Ａ）、（Ｂ）及び（Ｃ）は、画素（ａ）、（ｂ）及び（ｃ）の最良一致パターンの場所を示す。
【００１７】
図６に示すように、最良一致パターンからの各画素は内部バッファに累積され、累積された画素を加重平均することによって出力画素が得られる。
【００１８】
図６を参照すると、各最良一致パターン（Ａ）、（Ｂ）及び（Ｃ）は、それぞれ画素ｂ（黒丸）の独自のバージョン（候補）を含む。各候補を（ｂＡ）、（ｂＢ）及び（ｂＣ）で示す。結果の値は、次式に従って全ての候補画素を平均化することによって得られる。
【００１９】
【数１】
【００２０】
式中、ｂは補間された画素値であり、ｂＡはパターンＡからの候補画素の値であり、ｂＢはパターンＢからの候補画素の値であり、ｂＣはパターンＣからの候補画素の値であり、ｗＡ，ｗＢ，ｗＣは重み値である。
【００２１】
パターンマッチングは、多くの異なる方法で実装することができるが、一実施形態では、積分距離技法（integral distance technique）を用いて非常に効率的に実装される。
【００２２】
提案する方法は、大きな探索エリアを用いることによって局所的補間方法の欠点を克服する。未知の画素値は、局所近傍から合成するのではなく、多くの類似パターンから直接取得する。この手法は、図７に示すように、テクスチャーのあるエリアにおける画像を正確に再構成する。図７は、提案する方法を図４からの画像に適用した一例を示す。さらに、この手法は、例えば図８に示すような、テキスト等の規則的な構造を壊さない。図８において、上の画像は人工的にノイズの線を埋め込んだテキストのスキャン画像を含み、下の画像は、提案する方法によるノイズの線の補間を示す。
【００２３】
［第１の実施形態］
最初に、本発明の最も単純な実施形態を説明する。例示を簡単にするために、画像中の１画素幅の列を１列補間するための処理を説明する。しかしながら、画素列（複数可）は任意の幅とすることができることが理解されるであろう。さらに、補間される領域は、単なる画素の縦の列よりも複雑である可能性がある。例えば、領域は、可変の幅及び曲線的な形状を有してもよい。下記の実施形態の説明は、これらの代替形態の全てに対しても有効であり、複雑な領域への適用に関するさらなる詳細は、本明細書において後述する。
【００２４】
図９は、第１の実施形態の構成要素のブロック図を示し、図１０は、第１の実施形態によって行われる処理動作のフローチャートを示す。
【００２５】
図９を参照すると、スキャナの処理要素２が示されている。本実施形態において、処理要素２はプログラマブルであり、従来と同様に、１つ又は複数のプロセッサ、メモリ、グラフィックカード等を、表示装置４、１つ又は複数のユーザー入力装置６（キーボード等）と共に備える。
【００２６】
処理要素２は、入力されるプログラミング命令に従って動作するようにプログラムされる。プログラミング命令は、例えば、データ記憶媒体１２（光学ＣＤ ＲＯＭ、半導体ＲＯＭ、磁気記録媒体等）に記憶されたデータとして、及び／又は、処理装置２に入力される信号１４（例えば電気信号又は光信号）として入力される。信号１４は、例えば、遠隔データベースから、通信ネットワーク（インターネット等、図示せず）を介した伝送により、又は、大気中の伝送により入力される。
【００２７】
処理要素２は、プログラミング命令によりプログラムされたときに処理動作を行う多数の機能ユニットとして構成されたものと考えることができる。そのような機能ユニット及びそれらの相互接続の例を図９に示す。
【００２８】
図９に示す機能ユニットを参照すると、中央コントローラー２０は、ユーザー入力装置（複数可）からの入力を処理すると共に、他の機能ユニットに対して制御及び処理を行うように動作可能である。ワーキングメモリ３０は、中央コントローラー２０及び他の機能ユニットによって使用されるように設けられる。
【００２９】
入力データインターフェース４０は、処理装置２内の入力データの記憶を制御するように動作可能である。本実施形態において、入力データは、スキャナの検出器（図示せず）によって記録された画像データを含む。
【００３０】
入力データストア５０が、画像入力データを記憶するために設けられる。
【００３１】
初期充填値計算機（initial fill calculator）６０は、スキャナの検出器間のギャップ（複数可）により欠落している画素の初期値を計算するように動作可能である。
【００３２】
テンプレートパターン選択器７０は、補間値を計算すべき各画素の周囲のテンプレートパターンを選択するように動作可能である。
【００３３】
探索エリア選択器８０は、補間値を計算すべき画素の周囲の探索エリアを選択し、それによって、テンプレートパターン内のパターンに一致するパターンの探索を行うエリアを規定するように動作可能である。
【００３４】
最良一致パターン選択器９０は、パターンテンプレート内のパターンを探索エリアのさまざまな領域のパターンと照合するパターンマッチングを行うように動作可能であり、さらに、それらのパターンから最良一致パターンを選択する処理を行うように動作可能である。
【００３５】
画素累積器１００及び重み累積器１１０は、それぞれのメモリバッファを含む。画素累積器１００は、最良一致パターン選択器９０によって特定された画素値を累積するように構成されている。重み累積器１１０は、最良一致パターン選択器９０によって特定された画素の重み値を累積するように構成されている。
【００３６】
平均画素値計算機１２０は、画素累積器１００及び重み累積器１１０に累積された値を処理して、現在処理中の画素に対する補間された画素値を計算するように動作可能である。
【００３７】
中央コントローラー２０の制御下のディスプレイコントローラー１３０は、表示装置４を制御して、画像データストア５０に記憶された入力画像データを、平均画素計算機１２０によって計算された補間画素値と共に表示し、それによって、補正された画像データを表示するように動作可能である。
【００３８】
出力データインターフェース１５０は、処理要素２からのデータの出力を制御するように動作可能である。本実施形態において、出力データは、補正された画像データを含む。すなわち、スキャナの検出器から受信され画像データストア５０に記憶された画像データと、スキャナの検出器におけるギャップに起因するギャップを埋めるために計算された補間された画素値とを含む。出力データインターフェース１５０は、データを、例えばコンピュータ可読記憶媒体１５２（光学ＣＤ ＲＯＭ、半導体ＲＯＭ、磁気記録媒体等）上のデータとして、及び／又は、信号１５４（例えば、通信ネットワーク（インターネット等）を介して伝送される、または大気中を伝送される、電気信号又は光信号）として、出力するように動作可能である。出力データの記録は、出力信号１５４を直接的又は間接的に記録することによって行うことができる。
【００３９】
次に図１０のブロック１０を参照すると、初期充填値計算機６０は、未知の画素値を初期化する。すなわち、初期充填値計算機６０は、画像内においてスキャナの検出器におけるギャップに対応する各画素（よって、検出器によって記録された値を持たないもの）の初期値を与える。本実施形態において、各初期値は、任意の従来技術の画素補間方法によって計算される。例えば、式（２）によって与えられるように、左側ｎ個の画素及び右側ｎ個の画素の一次結合を用いることができる。式中、ｋｉは線形補間の係数であり、Ｃはカラーチャンネルのうちの１つ（Ｒ、Ｇ又はＢ）である。
【００４０】
【数２】
【００４１】
最も単純なケースでは、２つの近傍画素の平均が計算される（ｋ１＝１及びｋｉ＝０，ｉ＞１）。
【００４２】
ブロック２０において、中央コントローラー２０は、処理すべき次の画素（ｘ０，ｙ）を選択し、テンプレート選択器７０は、該画素に対するテンプレートパターンＮを選択し、探索エリア選択器８０は、該画素に対する探索エリアＳを選択する。本実施形態において、テンプレートパターンＮ及び探索エリアＳは共に、画素（ｘ０，ｙ）を中心とする。選択の一例を図１１に示す。補間領域は、探索エリアを２つの部分（例えば、補間すべき画素の縦の線がある場合、左側部分及び右側部分）に分割する。アルゴリズムは、補間領域の画素を中心にしたパターンを考慮しない。任意選択で、（図１１に示すような）パラメータｄが、探索エリアの左側部分と右側部分との間の最小距離を決定してもよい。このパラメータは、最良一致パターンが補間領域の近くで選択され得ないことを保証する（補間領域の近くでは、未知の画素値のためにパターン間の距離の信頼性が比較的低い）。
【００４３】
ブロック３０において、最良一致パターン選択器９０は、パターンマッチング及び最良一致パターンの選択を行う。この処理は、多数の異なる方法で行うことができる。例えば、本実施形態において、テンプレートＮ（ｘ０，ｙ）と、探索エリアからの他の任意のパターンＮ（ｘ０＋ｓｘ，ｙ＋ｓｙ）との間の距離は、重み付けされた色差分絶対値和（sum of absolute colour differences）（ＳＡＣＤ）として計算される。
【００４４】
【数３】
【００４５】
式（３）において、パラメータｗＲ，ｗＧ，ｗＢは、各カラーチャンネルの重みを決定する。最も単純な実装では、全ての重みを１に設定してもよい。また、他の任意の標準的な距離測度又は類似度測度（差の二乗和又は相関）をパターンマッチングにおいて用いてもよい。なお、本実施形態において、距離は、式（３）によって、ブロック１０における線形補間によって置き換えられた未知の画素を含む、テンプレートの全ての画素を用いて計算される。
【００４６】
最良一致パターンの位置Ｎ＊（ｘ０，ｙ）＝Ｎ（ｘ０＋ｓｘ＊，ｙ＋ｓｙ＊）は、距離測度の最小値によって決まる。
【００４７】
【数４】
【００４８】
ブロック４０はさらに、ブロック３０で見つけた最良一致パターンを処理する。この処理の詳細を図１２に示す。テンプレートパターンＮの中央にある未定義の画素は、パターンＮ＊における明確に定義された画素に対応する。これは、探索が、（図１１に示すパラメータｄによって規制されるとおり）補間領域の近くでは行われないことによる。したがって、Ｎ＊からの画素は、未知の画素の考え得る候補である。（図５に示すような）テンプレートパターンの重なりにより、未知の画素のそれぞれは、（図６に示すような）数個の最良一致パターンからの、対応する候補を有する。本実施形態において、候補はブロック５０において、平均画素値計算機１２０によって平均化されて、未知の画素の推定値が得られる。
【００４９】
画素平均を効率的に行うために、アルゴリズムの開始前に、２つのメモリバッファ（画素累積器Ｐ １００及び重み累積器Ｗ １１０）が割り当てられ、０で初期化される。これらの累積器１００、１１０は、補間領域と同一のトポロジーを有する。例えば、領域が１つの画像の列である場合、これらの累積器は１次元アレイである。領域がいくつかの列からなる場合、これらの累積器は２次元アレイである。領域が任意の形状を有する場合、これらの累積器は、領域の形状によってマスキングされた２次元アレイとして実装することができる。
【００５０】
画素累積プロセスを図１２に示す。テンプレートパターンＮが座標（ｘｉ，ｙｉ）（ｉ＝１，…，ｍ）を有するｍ個の未知画素を含む場合、最良一致パターンＮ＊において、該画素の座標は（ｘｉ＋ｓｘ＊，ｙｉ＋ｓｙ＊）となる。なお、現画素（ｘ０，ｙ）はこれらのｍ個の画素の中に含まれる。累積器１００、１１０は、次のように更新される。
【００５１】
【数５】
【００５２】
これらの式中、Ｃは原画像のカラーチャンネルのうちの１つ（Ｒ、Ｇ又はＢ）を示す。定数ａ及びｂは、画像に対する累積器アレイの起点を決める。補間領域がｘ０における画素列全体である最も単純な場合、ａ＝ｘ０かつｂ＝０である。
【００５３】
式（５．１）及び（５．２）における重み関数ｗは任意の形態を有することができ、例えば、定数とすることができる。しかし直感的に、最良一致パターンＮ＊（ｘ０，ｙ）が、他の最良一致パターン、例えばＮ＊（ｘ０，ｙ±１）よりも画素（ｘ０，ｙ）の補間に寄与するはずであることは明白である。したがって、本実施形態において、ｗは現画素（ｘ０，ｙ）を中心として対称であり、パターンの両端において減少する。例えば、重み関数は、図１２の右側のグラフに示し、式（６）によって与えられるように、線形減少することができる。
【００５４】
【数６】
【００５５】
最後に、ブロック５０において、平均画素値計算機１２０は、画素累積器の値を重み累積器の値で除算し、それにより加重平均を計算することによって、補間の結果を生成する。
【００５６】
【数７】
【００５７】
その後、アルゴリズムは次の画素（ｘ０，ｙ＋１）に進み、ブロック２０から開始して、補間が必要な全ての画素を処理するまで行われる。
【００５８】
［変更形態及び変形形態］
上述の実施形態に対して、例えば以下のように、多くの変更及び変形を加えることができる。
【００５９】
［「画像ライン入力−画像ライン出力」の実装］
上記の実施形態における処理アルゴリズムは、パターンマッチングプロセスがパターンの中心を探索エリアの各画素に配置するので、１つの画素を補間するために、該画素を中心とする（２（Ｎｘ＋Ｓｘ）＋１）×（２（Ｎｙ＋Ｓｙ）＋１）のサイズの画像領域を必要とする。２（Ｎｙ＋Ｓｙ）＋１本の画像ラインのみをメモリバッファに保持することによって、効率的なメモリ消費を達成することができる。まず、最初の２（Ｎｙ＋Ｓｙ）＋１本の画像ラインをバッファに入れる。該バッファからの情報は、バッファの中心線に対応する番号Ｎｙ＋Ｓｙ＋１の画像ラインを処理するには十分である。次に、全てのバッファラインをシフトして、１行目のラインを廃棄し、２行目のラインが１行目になり、以下同様となる。バッファの最後のラインに新たな画像ラインが入れられ、中心バッファラインに対応する次の出力画像ラインを生成することを可能にする。したがって、この実装は、図１３に示すように、入力画像ラインと出力画像ラインとの間にＮｙ＋Ｓｙ＋１に等しい遅延を有する。
【００６０】
積分距離を用いた高速パターンマッチング
関数ｆを距離の式（３）における内部和（inner sum）とする。
【００６１】
【数８】
【００６２】
式中、
【００６３】
【数９】
【００６４】
（８）における補間画素位置ｘ０は定数である。２つの他のパラメータｓｘ及びｓｙが固定されている場合、関数ｆはｉのみに依存し、式（８）は、
【００６５】
【数１０】
【００６６】
となる。
【００６７】
次に、積分距離関数（ＩＳＡＣＤ）が導入された場合、
【００６８】
【数１１】
【００６９】
距離の計算は、ＩＳＡＣＤの２つの値しか必要とせず、遥かに単純になる。
【００７０】
【数１２】
【００７１】
式（１０）〜（１２）において仮定しているように、探索パラメータを定数にする方法を示すために、表１において、第１の実施形態の単純なパターンマッチングの実装を、Ｃ／Ｃ＋＋のような疑似コードを用いる本変更形態の高速パターンマッチングの実装と比較する。コンパクトなコードのために、パターンマッチングの最初の部分のみ、すなわち、最小距離（４．１）の探索が実装される。もう一方の部分である、最良一致パターンの位置（４．２）の選択は、ＭｉｎＤｉｓｔａｎｃｅの値を得た直後に追加することができる。
【００７２】
【表１】
【００７３】
低速アルゴリズムと高速アルゴリズムとの間の主な違いは、高速アルゴリズムがパターン距離の計算の中間結果を盛んに再利用することである。これは、各ループの異なる順序によって実装される。すなわち、低速アルゴリズムでは、探索ループ（ｓｘ，ｓｙ）が画素位置ループ（ｙ）内にあり、高速アルゴリズムでは、画素位置ループ（ｙ）が探索ループ（ｓｘ，ｓｙ）内にある。結果として、ＳＡＣＤ値は、低速アルゴリズムでは２Ｄループによっても計算されるが、高速アルゴリズムでは直接は計算されず、したがって、計算時間が節約される。高速実装の副作用は、内部結果を記憶するためにより多くのメモリ（画像の高さのサイズのバッファＩＳＡＣＤ［］及びＭｉｎＤｉｓｔａｎｃｅ［］）を必要とすることである。
【００７４】
［反復的アルゴリズム］
第１の実施形態の別の変形は、パターンマッチングプロセスの反復的な適用であり、補間の新たな結果を次の反復において未知の画素の初期近似値として用いる。この場合、最初の線形補間（図１０のブロック１０）は、反復０として考えることができる。反復的アルゴリズムのブロック図を図１４に示す。
【００７５】
多くの場合において、入力画像は、単純な構造（例えば、均一なエリア）を有し、そのような画素の良好な補間結果を線形方法（１）によって得ることができる。この場合、さらなる変形では、最良一致パターンへの距離が閾値を上回る場合に、パターンマッチングの結果を廃棄し、初期線形補間の結果を受け入れる。アルゴリズムのこの変更例を図１５に示す。他の反復間で同様の受け入れ条件を実装することは単純である。
【００７６】
［任意形状の領域］
上述の第１の実施形態は、単一の画素列の補間を目的としていた。複数の列［ｘ１，ｘ２］（ｘ２−ｘ１＋１に等しい幅を有する領域）への拡張は、ｘ０∈［ｘ１，ｘ２］の範囲からの全ての画素位置を反復することによって、上記の説明から得ることができる。
【００７７】
任意形状の領域の場合にも、本方法を適用することができるが、補間領域の曲線的な境界及び変動する幅のために調整が必要である。図１６及び図１７は、本方法の主要な思想が変わらないことを示す。必要な主な変更は次の通りである。
・画素累積器及び重み累積器の形状を補間領域の形状に類似させるべきである。
・テンプレートパターンの適応的なサイズ。テンプレート内に存在する値を計算すべき画素（補間画素）が多すぎる場合、信頼できる画素数を増やすために、テンプレートのサイズを増大させるべきである。
・上述した高速実装の変更形態において、積分距離ｆは１次元関数でなくなる。その代わりに、２次元関数となり、積分画像に関する周知の技法を用いて実装することができる。
【００７８】
図１６を参照すると、補間領域の５つの画素の最良一致パターンが黒丸により示されている。各画素の周囲の矩形（細線の矩形）は、探索エリアからの他の全てのパターンに照合されるパターンを示す。太線の矩形は、各最良一致パターンの位置を示す。最良一致パターンにおいて、中心画素（黒丸）は、テンプレートパターンの中心に対応する。他の画素（白丸）は、補間領域の他の画素のバージョン（候補）である。ここでもまた、複数の候補を平均化して、補間の結果を得ることができる（図１７を参照）。
【００７９】
図１７を参照すると、曲線的な領域からの画素の補間が示されている。補間される画素（黒丸）は、各最良一致パターンからの、対応する画素を平均化することによって得られる。最良一致パターンのそれぞれ（矩形により示す）は、補間される画素の独自のバージョン（候補）を含む。結果の値は、全ての候補画素を平均化することによって得られる。
【００８０】
［画素の結合方法］
上述の第１の実施形態では、候補画素を結合して、加重平均により結果の値を与える。ここで、重みは幾何関数である。しかし、結果の値を与えるための他の任意の結合方法、例えば、
・単純平均
・トリム平均(Trimmed averaging)
・距離値に基づく重みを用いた加重平均
・全ての候補画素の中央値（又は他の任意の統計値）
を用いることができる。
【００８１】
［代替的な応用］
上述の第１の実施形態並びにその変更形態及び変形形態において、画像領域の補間処理は、スキャナから得られた画像データに対して行われる。しかしながら、同一の処理を、汎用の画像／ビデオ処理、復元及び編集に、特に細長い領域の除去が必要である場合、例えば、
・古い写真／フィルムからの掻き傷の除去
・映画のポストプロダクション中のワイヤ除去
・ビデオフレームの奇数／偶数の画素行を補間することによるビデオのインタレース除去
に用いることができる。
【００８２】
［他の変更形態及び変形形態］
多くの他の変更形態及び変形形態が可能である。
【００８３】
例えば、第１の実施形態において、処理要素２はスキャナの一部を構成する。しかしながら、その代わりに、処理要素２は、スキャナとは別の処理装置（スキャナからスキャン画像データを受信するパーソナルコンピュータ等）の一部とすることができる。
【００８４】
上述の第１の実施形態並びにその変更形態及び変形形態では、ＲＧＢ配色が使用される。しかしながら、ＣＭＹＫ等の他の配色をその代わりに用いることもできる。
【００８５】
上述の第１の実施形態並びに変更形態及び変形形態において、各テンプレートパターン及び各探索エリアは、対応する補間すべき画素を中心とする。しかし、これは必ずしもそうである必要はなく、各テンプレートパターン及び／又は各探索エリアを、補間すべき画素がその中心とならないようにずらすこともできる（ただし、補間すべき画素は中心に近いことが好ましい）。
【００８６】
上述の第１の実施形態並びに変更形態及び変形形態において、各探索エリアは、画像の領域を含む。しかしながら、各探索エリアは、画像全体を含むこともできる。
【００８７】
上述の第１の実施形態並びに変更形態及び変形形態において、処理は、プログラマブル処理装置によって行われ、コンピュータプログラム命令によって定義される処理ルーチンを用いて行われる。しかしながら、処理の一部又は全部は、その代わりに、ハードウェアを用いて行うこともできる。
【技術分野】
【０００１】
［関連出願の相互参照］
本出願は、２００９年４月１５日付の欧州特許出願第０９１５７９４１．７号明細書に基づき優先権を主張する。欧州特許出願第０９１５７９４１．７号明細書は、本明細書中にその全体が記載されたものとして援用される、
【０００２】
［発明の分野］
本発明は、欠陥又はアーチファクトを有する画像データを処理して、補正された画像データを生成するための画像処理に関する。
【０００３】
本発明は、限定するものではないが、印刷されたテキストのページ、グラフィクス、画像等の文書をスキャンするスキャナから得られた画像データの処理に特に有用である。スキャナは、デジタルコピー機やファクシミリ装置等の一部を構成することもできるし、又はパーソナルコンピュータ等に接続されるフラットベッドスキャナやハンドヘルドスキャナ等のスタンドアロンシステムを構成することもできる。したがって、画像処理は、スキャナそのものの内部で行うこともでき、スキャナを含む装置内で行うこともでき、スキャンされた画像データをスキャナから受信する装置内で行うこともできる。
【背景技術】
【０００４】
多くの従来の文書スキャナ、特にフラットベッドスキャナは、密着イメージセンサー（ＣＩＳ）を使用して、スキャン画像データを生成する。
【０００５】
ＣＩＳは、スキャン中の文書を照明する光源（通常はＬＥＤで構成される）と、文書から反射された光を検出するセンサーと、反射光をセンサー上に集光するレンズ系とを備える。ＣＩＳ撮像系は通常、図１に概略的に示すセンサチップ（１）、（２）、…、（Ｎ）のラインセンサからなる。
【０００６】
そのような画像センサチップのリニア配列の１つの問題は、スキャンされた文書中の欠落画素である。画像センサチップの不正確な配置のため、このような画素は、画像センサチップ間において取り込むことができない。この問題を図２に示す。図２は、２つの隣接する画像センサチップＫ及びＫ＋１の間のギャップを示し、垂直走査方向の場合、このギャップは、スキャンされた文書において欠落した画素列となる。
【０００７】
欠落画素の問題に対して考え得る解決策は、３つのカテゴリに分類することができる。
１．センサチップの新たなレイアウトの設計。センサチップ間のギャップを除去するために、センサチップを図３に示すような「千鳥行(staggered row)」に配置することができる。この場合、欠落画素の問題は存在しないが、別の問題が生じる。すなわち、センサチップ間での画像のつなぎ合わせである。また、この解決策は、既存のＣＩＳ製品の完全な再設計と、異なるモデルの市場への導入を必要とする。
２．センサチップの高精度な配置。この解決策では、センサチップ間のギャップを、隣接するセンサチップのＲＧＢセンサー間の距離を最小化することにより除去する（図２）。しかしながら、これは、高価な機器と製造技術の変更を必要とする高コストの解決策である。
３．画像の近傍から必要な欠落画素値を取得する画像処理方法による画素補間。これは、画像処理ハードウェアを更新することによって実装でき、よって、再設計も製造技術の変更も必要とすることなく既存のＣＩＳ製品を更新できるため、比較的低コストな手法である。
【０００８】
標準的な画像補間方法の主な問題は、テクスチャーのあるエリアの画素値については、局所的な画素近傍が必要な情報を含まないので正確に再構成できないという点である。図４は、この問題の一例を示すものであり、スキャン画像の一列が欠落した断片を左側に示し、線形補間の結果を右側に示す。結果の画像における補間誤差は、ユーザーにとてもはっきりと見える。
【発明の概要】
【０００９】
本発明によれば、画像を定義する画像データを処理して、該画像内の複数の画素について画素値を計算する方法であって、
値を計算すべき各画素に関して、画素のテンプレートパターンを複数規定することであって、各テンプレートパターンが前記画像の異なる領域を含み、値を計算すべき前記画素を含むようにする、テンプレートパターンを規定することと、
各テンプレートパターンに関して、
−前記画像の全体を含むか、又は前記テンプレートパターンよりも大きい該画像の領域を含む、探索エリアを規定すること、
−前記テンプレートパターン内の前記画素の前記値を複数の候補パターンの各々の該画素の該値と比較することであって、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの異なる領域を含み、該テンプレートパターンと前記候補パターンとの間の類似度を表す各候補パターンについて類似度測度を導出するようにする、比較すること、
−前記複数の候補パターンから、前記テンプレートパターンとの最高の類似度を表す前記類似度測度を有する候補パターンを選択すること、及び
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めることと、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成することであって、各値が異なる候補パターンから導出されるようにする、生成することと、
値を計算すべき各画素に関して、該画素に対する前記導出された画素値を結合することと、を含む、方法が提供される。
【００１０】
本発明はまた、画像を定義する画像データを処理して、該画像内の複数の画素について画素値を計算するように動作可能な画像処理装置であって、
前記画像内の、値を計算すべき各画素に関して、画素のテンプレートパターンを複数規定するように動作可能なテンプレートパターン選択器であって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、各テンプレートパターンが値を計算すべき前記画素を含むようにする、テンプレートパターン選択器と、
各テンプレートパターンに関して、前記画像の全体を含むか又は前記テンプレートパターンよりも大きい該画像の領域を含む、探索エリアを規定するように動作可能な探索エリア選択器と、
各テンプレートパターンに関して処理を行うように動作可能なパターンマッチャであって、
前記パターンマッチャは、前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々の該画素の該値と比較し、
各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含み、
前記パターンマッチャは、前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択するように動作可能であり、
前記パターンマッチャは、前記テンプレートパターン内の値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めるように動作可能であり、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成し、各値が異なる候補パターンから導出される、
パターンマッチャと、
値を計算すべき各画素に関して、該画素値に対する前記導出された画素値を結合するように動作可能な画素コンバイナと、を備える、画像処理装置を提供する。
【００１１】
本発明はさらに、プログラマブル処理装置を、上述のような方法を行うように動作可能となるようにプログラムするためのコンピュータプログラム命令を担持するコンピュータプログラム製品（コンピュータ可読記憶媒体やコンピュータ可読信号等）を提供する。
【００１２】
次に、本発明の実施形態を単なる例示として、添付図面を参照して説明する。
【図面の簡単な説明】
【００１３】
【図１】従来のＣＩＳにおける画像センサチップレイアウトを概略的に示す図である。
【図２】従来のセンサチップの欠落画素の問題を示す図である。
【図３】欠落画素の問題に対処するためのＣＩＳセンサチップの代替的なレイアウトを示す図である。
【図４】テクスチャーのあるエリアにおける欠落画素の線形補間に関する問題を示す図である。
【図５】本発明の実施形態において使用される最良一致パターン技法を示す図である。
【図６】本発明の実施形態における最良一致パターンからの画素の平均化による画素補間を示す図である。
【図７】一実施形態によって図４の画像に対して行われる処理の結果を示す図である。
【図８】一実施形態によってテキストを含む画像に対して行われる処理の結果を示す図である。
【図９】本発明の第１の実施形態の構成要素を概略的に示す図である。
【図１０】第１の実施形態によって行われる処理動作のフローチャートである。
【図１１】一実施形態における、補間すべき画素、テンプレートパターン及び補間すべき画素を中心とする探索エリアのレイアウト例を示す図である。
【図１２】最良一致パターンからの画素を累積するために第１の実施形態において行われる処理を示す図である。
【図１３】「ライン入力−ライン出力」の実装を使用する一実施形態の場合の、入力画像ラインと出力画像ラインとの間の遅延を示す図である。
【図１４】一実施形態における提案された方法の反復的実装のフローチャートである。
【図１５】一実施形態における反復０の結果と反復１の結果との間で決定を行うための処理のフローチャートである。
【図１６】任意形状の領域に対処するために変更形態において使用される最良一致パターン技法を示す図である。
【図１７】任意形状の領域に対処するための変更形態における最良一致パターンからの画素の平均化による画素補間を示す図である。
【発明を実施するための形態】
【００１４】
本発明の実施形態を説明する前に、理解を助けるために、実施形態の基礎となる動作の理論、及び結果の例を説明する。
【００１５】
各実施形態は、類似するパターンからの画素の非局所的平均に基づく画素補間方法を使用する。より詳細には、図５に示すように、補間の必要な各画素に関して、その周囲の小さな２Ｄパターン（テンプレートパターン）を、ある（好ましくは大きな）探索エリアにおける他の全てのそのような２Ｄパターンと照合する。
【００１６】
図５を参照すると、画素（ａ）、（ｂ）及び（ｃ）は、補間が必要な画像列からの３つの画素である。補間される領域の各画素（黒丸）の周囲の矩形は、探索エリアからの他の全てのパターンと照合されるパターンを示す。矩形（Ａ）、（Ｂ）及び（Ｃ）は、画素（ａ）、（ｂ）及び（ｃ）の最良一致パターンの場所を示す。
【００１７】
図６に示すように、最良一致パターンからの各画素は内部バッファに累積され、累積された画素を加重平均することによって出力画素が得られる。
【００１８】
図６を参照すると、各最良一致パターン（Ａ）、（Ｂ）及び（Ｃ）は、それぞれ画素ｂ（黒丸）の独自のバージョン（候補）を含む。各候補を（ｂＡ）、（ｂＢ）及び（ｂＣ）で示す。結果の値は、次式に従って全ての候補画素を平均化することによって得られる。
【００１９】
【数１】
【００２０】
式中、ｂは補間された画素値であり、ｂＡはパターンＡからの候補画素の値であり、ｂＢはパターンＢからの候補画素の値であり、ｂＣはパターンＣからの候補画素の値であり、ｗＡ，ｗＢ，ｗＣは重み値である。
【００２１】
パターンマッチングは、多くの異なる方法で実装することができるが、一実施形態では、積分距離技法（integral distance technique）を用いて非常に効率的に実装される。
【００２２】
提案する方法は、大きな探索エリアを用いることによって局所的補間方法の欠点を克服する。未知の画素値は、局所近傍から合成するのではなく、多くの類似パターンから直接取得する。この手法は、図７に示すように、テクスチャーのあるエリアにおける画像を正確に再構成する。図７は、提案する方法を図４からの画像に適用した一例を示す。さらに、この手法は、例えば図８に示すような、テキスト等の規則的な構造を壊さない。図８において、上の画像は人工的にノイズの線を埋め込んだテキストのスキャン画像を含み、下の画像は、提案する方法によるノイズの線の補間を示す。
【００２３】
［第１の実施形態］
最初に、本発明の最も単純な実施形態を説明する。例示を簡単にするために、画像中の１画素幅の列を１列補間するための処理を説明する。しかしながら、画素列（複数可）は任意の幅とすることができることが理解されるであろう。さらに、補間される領域は、単なる画素の縦の列よりも複雑である可能性がある。例えば、領域は、可変の幅及び曲線的な形状を有してもよい。下記の実施形態の説明は、これらの代替形態の全てに対しても有効であり、複雑な領域への適用に関するさらなる詳細は、本明細書において後述する。
【００２４】
図９は、第１の実施形態の構成要素のブロック図を示し、図１０は、第１の実施形態によって行われる処理動作のフローチャートを示す。
【００２５】
図９を参照すると、スキャナの処理要素２が示されている。本実施形態において、処理要素２はプログラマブルであり、従来と同様に、１つ又は複数のプロセッサ、メモリ、グラフィックカード等を、表示装置４、１つ又は複数のユーザー入力装置６（キーボード等）と共に備える。
【００２６】
処理要素２は、入力されるプログラミング命令に従って動作するようにプログラムされる。プログラミング命令は、例えば、データ記憶媒体１２（光学ＣＤ ＲＯＭ、半導体ＲＯＭ、磁気記録媒体等）に記憶されたデータとして、及び／又は、処理装置２に入力される信号１４（例えば電気信号又は光信号）として入力される。信号１４は、例えば、遠隔データベースから、通信ネットワーク（インターネット等、図示せず）を介した伝送により、又は、大気中の伝送により入力される。
【００２７】
処理要素２は、プログラミング命令によりプログラムされたときに処理動作を行う多数の機能ユニットとして構成されたものと考えることができる。そのような機能ユニット及びそれらの相互接続の例を図９に示す。
【００２８】
図９に示す機能ユニットを参照すると、中央コントローラー２０は、ユーザー入力装置（複数可）からの入力を処理すると共に、他の機能ユニットに対して制御及び処理を行うように動作可能である。ワーキングメモリ３０は、中央コントローラー２０及び他の機能ユニットによって使用されるように設けられる。
【００２９】
入力データインターフェース４０は、処理装置２内の入力データの記憶を制御するように動作可能である。本実施形態において、入力データは、スキャナの検出器（図示せず）によって記録された画像データを含む。
【００３０】
入力データストア５０が、画像入力データを記憶するために設けられる。
【００３１】
初期充填値計算機（initial fill calculator）６０は、スキャナの検出器間のギャップ（複数可）により欠落している画素の初期値を計算するように動作可能である。
【００３２】
テンプレートパターン選択器７０は、補間値を計算すべき各画素の周囲のテンプレートパターンを選択するように動作可能である。
【００３３】
探索エリア選択器８０は、補間値を計算すべき画素の周囲の探索エリアを選択し、それによって、テンプレートパターン内のパターンに一致するパターンの探索を行うエリアを規定するように動作可能である。
【００３４】
最良一致パターン選択器９０は、パターンテンプレート内のパターンを探索エリアのさまざまな領域のパターンと照合するパターンマッチングを行うように動作可能であり、さらに、それらのパターンから最良一致パターンを選択する処理を行うように動作可能である。
【００３５】
画素累積器１００及び重み累積器１１０は、それぞれのメモリバッファを含む。画素累積器１００は、最良一致パターン選択器９０によって特定された画素値を累積するように構成されている。重み累積器１１０は、最良一致パターン選択器９０によって特定された画素の重み値を累積するように構成されている。
【００３６】
平均画素値計算機１２０は、画素累積器１００及び重み累積器１１０に累積された値を処理して、現在処理中の画素に対する補間された画素値を計算するように動作可能である。
【００３７】
中央コントローラー２０の制御下のディスプレイコントローラー１３０は、表示装置４を制御して、画像データストア５０に記憶された入力画像データを、平均画素計算機１２０によって計算された補間画素値と共に表示し、それによって、補正された画像データを表示するように動作可能である。
【００３８】
出力データインターフェース１５０は、処理要素２からのデータの出力を制御するように動作可能である。本実施形態において、出力データは、補正された画像データを含む。すなわち、スキャナの検出器から受信され画像データストア５０に記憶された画像データと、スキャナの検出器におけるギャップに起因するギャップを埋めるために計算された補間された画素値とを含む。出力データインターフェース１５０は、データを、例えばコンピュータ可読記憶媒体１５２（光学ＣＤ ＲＯＭ、半導体ＲＯＭ、磁気記録媒体等）上のデータとして、及び／又は、信号１５４（例えば、通信ネットワーク（インターネット等）を介して伝送される、または大気中を伝送される、電気信号又は光信号）として、出力するように動作可能である。出力データの記録は、出力信号１５４を直接的又は間接的に記録することによって行うことができる。
【００３９】
次に図１０のブロック１０を参照すると、初期充填値計算機６０は、未知の画素値を初期化する。すなわち、初期充填値計算機６０は、画像内においてスキャナの検出器におけるギャップに対応する各画素（よって、検出器によって記録された値を持たないもの）の初期値を与える。本実施形態において、各初期値は、任意の従来技術の画素補間方法によって計算される。例えば、式（２）によって与えられるように、左側ｎ個の画素及び右側ｎ個の画素の一次結合を用いることができる。式中、ｋｉは線形補間の係数であり、Ｃはカラーチャンネルのうちの１つ（Ｒ、Ｇ又はＢ）である。
【００４０】
【数２】
【００４１】
最も単純なケースでは、２つの近傍画素の平均が計算される（ｋ１＝１及びｋｉ＝０，ｉ＞１）。
【００４２】
ブロック２０において、中央コントローラー２０は、処理すべき次の画素（ｘ０，ｙ）を選択し、テンプレート選択器７０は、該画素に対するテンプレートパターンＮを選択し、探索エリア選択器８０は、該画素に対する探索エリアＳを選択する。本実施形態において、テンプレートパターンＮ及び探索エリアＳは共に、画素（ｘ０，ｙ）を中心とする。選択の一例を図１１に示す。補間領域は、探索エリアを２つの部分（例えば、補間すべき画素の縦の線がある場合、左側部分及び右側部分）に分割する。アルゴリズムは、補間領域の画素を中心にしたパターンを考慮しない。任意選択で、（図１１に示すような）パラメータｄが、探索エリアの左側部分と右側部分との間の最小距離を決定してもよい。このパラメータは、最良一致パターンが補間領域の近くで選択され得ないことを保証する（補間領域の近くでは、未知の画素値のためにパターン間の距離の信頼性が比較的低い）。
【００４３】
ブロック３０において、最良一致パターン選択器９０は、パターンマッチング及び最良一致パターンの選択を行う。この処理は、多数の異なる方法で行うことができる。例えば、本実施形態において、テンプレートＮ（ｘ０，ｙ）と、探索エリアからの他の任意のパターンＮ（ｘ０＋ｓｘ，ｙ＋ｓｙ）との間の距離は、重み付けされた色差分絶対値和（sum of absolute colour differences）（ＳＡＣＤ）として計算される。
【００４４】
【数３】
【００４５】
式（３）において、パラメータｗＲ，ｗＧ，ｗＢは、各カラーチャンネルの重みを決定する。最も単純な実装では、全ての重みを１に設定してもよい。また、他の任意の標準的な距離測度又は類似度測度（差の二乗和又は相関）をパターンマッチングにおいて用いてもよい。なお、本実施形態において、距離は、式（３）によって、ブロック１０における線形補間によって置き換えられた未知の画素を含む、テンプレートの全ての画素を用いて計算される。
【００４６】
最良一致パターンの位置Ｎ＊（ｘ０，ｙ）＝Ｎ（ｘ０＋ｓｘ＊，ｙ＋ｓｙ＊）は、距離測度の最小値によって決まる。
【００４７】
【数４】
【００４８】
ブロック４０はさらに、ブロック３０で見つけた最良一致パターンを処理する。この処理の詳細を図１２に示す。テンプレートパターンＮの中央にある未定義の画素は、パターンＮ＊における明確に定義された画素に対応する。これは、探索が、（図１１に示すパラメータｄによって規制されるとおり）補間領域の近くでは行われないことによる。したがって、Ｎ＊からの画素は、未知の画素の考え得る候補である。（図５に示すような）テンプレートパターンの重なりにより、未知の画素のそれぞれは、（図６に示すような）数個の最良一致パターンからの、対応する候補を有する。本実施形態において、候補はブロック５０において、平均画素値計算機１２０によって平均化されて、未知の画素の推定値が得られる。
【００４９】
画素平均を効率的に行うために、アルゴリズムの開始前に、２つのメモリバッファ（画素累積器Ｐ １００及び重み累積器Ｗ １１０）が割り当てられ、０で初期化される。これらの累積器１００、１１０は、補間領域と同一のトポロジーを有する。例えば、領域が１つの画像の列である場合、これらの累積器は１次元アレイである。領域がいくつかの列からなる場合、これらの累積器は２次元アレイである。領域が任意の形状を有する場合、これらの累積器は、領域の形状によってマスキングされた２次元アレイとして実装することができる。
【００５０】
画素累積プロセスを図１２に示す。テンプレートパターンＮが座標（ｘｉ，ｙｉ）（ｉ＝１，…，ｍ）を有するｍ個の未知画素を含む場合、最良一致パターンＮ＊において、該画素の座標は（ｘｉ＋ｓｘ＊，ｙｉ＋ｓｙ＊）となる。なお、現画素（ｘ０，ｙ）はこれらのｍ個の画素の中に含まれる。累積器１００、１１０は、次のように更新される。
【００５１】
【数５】
【００５２】
これらの式中、Ｃは原画像のカラーチャンネルのうちの１つ（Ｒ、Ｇ又はＢ）を示す。定数ａ及びｂは、画像に対する累積器アレイの起点を決める。補間領域がｘ０における画素列全体である最も単純な場合、ａ＝ｘ０かつｂ＝０である。
【００５３】
式（５．１）及び（５．２）における重み関数ｗは任意の形態を有することができ、例えば、定数とすることができる。しかし直感的に、最良一致パターンＮ＊（ｘ０，ｙ）が、他の最良一致パターン、例えばＮ＊（ｘ０，ｙ±１）よりも画素（ｘ０，ｙ）の補間に寄与するはずであることは明白である。したがって、本実施形態において、ｗは現画素（ｘ０，ｙ）を中心として対称であり、パターンの両端において減少する。例えば、重み関数は、図１２の右側のグラフに示し、式（６）によって与えられるように、線形減少することができる。
【００５４】
【数６】
【００５５】
最後に、ブロック５０において、平均画素値計算機１２０は、画素累積器の値を重み累積器の値で除算し、それにより加重平均を計算することによって、補間の結果を生成する。
【００５６】
【数７】
【００５７】
その後、アルゴリズムは次の画素（ｘ０，ｙ＋１）に進み、ブロック２０から開始して、補間が必要な全ての画素を処理するまで行われる。
【００５８】
［変更形態及び変形形態］
上述の実施形態に対して、例えば以下のように、多くの変更及び変形を加えることができる。
【００５９】
［「画像ライン入力−画像ライン出力」の実装］
上記の実施形態における処理アルゴリズムは、パターンマッチングプロセスがパターンの中心を探索エリアの各画素に配置するので、１つの画素を補間するために、該画素を中心とする（２（Ｎｘ＋Ｓｘ）＋１）×（２（Ｎｙ＋Ｓｙ）＋１）のサイズの画像領域を必要とする。２（Ｎｙ＋Ｓｙ）＋１本の画像ラインのみをメモリバッファに保持することによって、効率的なメモリ消費を達成することができる。まず、最初の２（Ｎｙ＋Ｓｙ）＋１本の画像ラインをバッファに入れる。該バッファからの情報は、バッファの中心線に対応する番号Ｎｙ＋Ｓｙ＋１の画像ラインを処理するには十分である。次に、全てのバッファラインをシフトして、１行目のラインを廃棄し、２行目のラインが１行目になり、以下同様となる。バッファの最後のラインに新たな画像ラインが入れられ、中心バッファラインに対応する次の出力画像ラインを生成することを可能にする。したがって、この実装は、図１３に示すように、入力画像ラインと出力画像ラインとの間にＮｙ＋Ｓｙ＋１に等しい遅延を有する。
【００６０】
積分距離を用いた高速パターンマッチング
関数ｆを距離の式（３）における内部和（inner sum）とする。
【００６１】
【数８】
【００６２】
式中、
【００６３】
【数９】
【００６４】
（８）における補間画素位置ｘ０は定数である。２つの他のパラメータｓｘ及びｓｙが固定されている場合、関数ｆはｉのみに依存し、式（８）は、
【００６５】
【数１０】
【００６６】
となる。
【００６７】
次に、積分距離関数（ＩＳＡＣＤ）が導入された場合、
【００６８】
【数１１】
【００６９】
距離の計算は、ＩＳＡＣＤの２つの値しか必要とせず、遥かに単純になる。
【００７０】
【数１２】
【００７１】
式（１０）〜（１２）において仮定しているように、探索パラメータを定数にする方法を示すために、表１において、第１の実施形態の単純なパターンマッチングの実装を、Ｃ／Ｃ＋＋のような疑似コードを用いる本変更形態の高速パターンマッチングの実装と比較する。コンパクトなコードのために、パターンマッチングの最初の部分のみ、すなわち、最小距離（４．１）の探索が実装される。もう一方の部分である、最良一致パターンの位置（４．２）の選択は、ＭｉｎＤｉｓｔａｎｃｅの値を得た直後に追加することができる。
【００７２】
【表１】
【００７３】
低速アルゴリズムと高速アルゴリズムとの間の主な違いは、高速アルゴリズムがパターン距離の計算の中間結果を盛んに再利用することである。これは、各ループの異なる順序によって実装される。すなわち、低速アルゴリズムでは、探索ループ（ｓｘ，ｓｙ）が画素位置ループ（ｙ）内にあり、高速アルゴリズムでは、画素位置ループ（ｙ）が探索ループ（ｓｘ，ｓｙ）内にある。結果として、ＳＡＣＤ値は、低速アルゴリズムでは２Ｄループによっても計算されるが、高速アルゴリズムでは直接は計算されず、したがって、計算時間が節約される。高速実装の副作用は、内部結果を記憶するためにより多くのメモリ（画像の高さのサイズのバッファＩＳＡＣＤ［］及びＭｉｎＤｉｓｔａｎｃｅ［］）を必要とすることである。
【００７４】
［反復的アルゴリズム］
第１の実施形態の別の変形は、パターンマッチングプロセスの反復的な適用であり、補間の新たな結果を次の反復において未知の画素の初期近似値として用いる。この場合、最初の線形補間（図１０のブロック１０）は、反復０として考えることができる。反復的アルゴリズムのブロック図を図１４に示す。
【００７５】
多くの場合において、入力画像は、単純な構造（例えば、均一なエリア）を有し、そのような画素の良好な補間結果を線形方法（１）によって得ることができる。この場合、さらなる変形では、最良一致パターンへの距離が閾値を上回る場合に、パターンマッチングの結果を廃棄し、初期線形補間の結果を受け入れる。アルゴリズムのこの変更例を図１５に示す。他の反復間で同様の受け入れ条件を実装することは単純である。
【００７６】
［任意形状の領域］
上述の第１の実施形態は、単一の画素列の補間を目的としていた。複数の列［ｘ１，ｘ２］（ｘ２−ｘ１＋１に等しい幅を有する領域）への拡張は、ｘ０∈［ｘ１，ｘ２］の範囲からの全ての画素位置を反復することによって、上記の説明から得ることができる。
【００７７】
任意形状の領域の場合にも、本方法を適用することができるが、補間領域の曲線的な境界及び変動する幅のために調整が必要である。図１６及び図１７は、本方法の主要な思想が変わらないことを示す。必要な主な変更は次の通りである。
・画素累積器及び重み累積器の形状を補間領域の形状に類似させるべきである。
・テンプレートパターンの適応的なサイズ。テンプレート内に存在する値を計算すべき画素（補間画素）が多すぎる場合、信頼できる画素数を増やすために、テンプレートのサイズを増大させるべきである。
・上述した高速実装の変更形態において、積分距離ｆは１次元関数でなくなる。その代わりに、２次元関数となり、積分画像に関する周知の技法を用いて実装することができる。
【００７８】
図１６を参照すると、補間領域の５つの画素の最良一致パターンが黒丸により示されている。各画素の周囲の矩形（細線の矩形）は、探索エリアからの他の全てのパターンに照合されるパターンを示す。太線の矩形は、各最良一致パターンの位置を示す。最良一致パターンにおいて、中心画素（黒丸）は、テンプレートパターンの中心に対応する。他の画素（白丸）は、補間領域の他の画素のバージョン（候補）である。ここでもまた、複数の候補を平均化して、補間の結果を得ることができる（図１７を参照）。
【００７９】
図１７を参照すると、曲線的な領域からの画素の補間が示されている。補間される画素（黒丸）は、各最良一致パターンからの、対応する画素を平均化することによって得られる。最良一致パターンのそれぞれ（矩形により示す）は、補間される画素の独自のバージョン（候補）を含む。結果の値は、全ての候補画素を平均化することによって得られる。
【００８０】
［画素の結合方法］
上述の第１の実施形態では、候補画素を結合して、加重平均により結果の値を与える。ここで、重みは幾何関数である。しかし、結果の値を与えるための他の任意の結合方法、例えば、
・単純平均
・トリム平均(Trimmed averaging)
・距離値に基づく重みを用いた加重平均
・全ての候補画素の中央値（又は他の任意の統計値）
を用いることができる。
【００８１】
［代替的な応用］
上述の第１の実施形態並びにその変更形態及び変形形態において、画像領域の補間処理は、スキャナから得られた画像データに対して行われる。しかしながら、同一の処理を、汎用の画像／ビデオ処理、復元及び編集に、特に細長い領域の除去が必要である場合、例えば、
・古い写真／フィルムからの掻き傷の除去
・映画のポストプロダクション中のワイヤ除去
・ビデオフレームの奇数／偶数の画素行を補間することによるビデオのインタレース除去
に用いることができる。
【００８２】
［他の変更形態及び変形形態］
多くの他の変更形態及び変形形態が可能である。
【００８３】
例えば、第１の実施形態において、処理要素２はスキャナの一部を構成する。しかしながら、その代わりに、処理要素２は、スキャナとは別の処理装置（スキャナからスキャン画像データを受信するパーソナルコンピュータ等）の一部とすることができる。
【００８４】
上述の第１の実施形態並びにその変更形態及び変形形態では、ＲＧＢ配色が使用される。しかしながら、ＣＭＹＫ等の他の配色をその代わりに用いることもできる。
【００８５】
上述の第１の実施形態並びに変更形態及び変形形態において、各テンプレートパターン及び各探索エリアは、対応する補間すべき画素を中心とする。しかし、これは必ずしもそうである必要はなく、各テンプレートパターン及び／又は各探索エリアを、補間すべき画素がその中心とならないようにずらすこともできる（ただし、補間すべき画素は中心に近いことが好ましい）。
【００８６】
上述の第１の実施形態並びに変更形態及び変形形態において、各探索エリアは、画像の領域を含む。しかしながら、各探索エリアは、画像全体を含むこともできる。
【００８７】
上述の第１の実施形態並びに変更形態及び変形形態において、処理は、プログラマブル処理装置によって行われ、コンピュータプログラム命令によって定義される処理ルーチンを用いて行われる。しかしながら、処理の一部又は全部は、その代わりに、ハードウェアを用いて行うこともできる。
【特許請求の範囲】
【請求項１】
画像を定義する画像データを処理して、前記画像内の複数の画素について画素値を計算する方法であって、
画素のテンプレートパターンを複数規定することであって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、値を計算すべき画素のそれぞれは、前記テンプレートパターンのうち少なくとも２つに存在する、テンプレートパターンを規定することと、
各テンプレートパターンに関して、
−前記画像の全体を含むか、又は前記テンプレートパターンよりも大きい前記画像の領域を含む、探索エリアを規定すること、
−前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々における前記画素の前記値と比較することであって、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含む、値を比較すること、
−前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択すること、及び
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めること
と、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成することであって、各値はそれぞれ異なる候補パターンから導出される、値を生成することと、
値を計算すべき各画素に関して、前記画素に対する前記導出された画素値を結合することであって、結果の値を生成する、画素値を結合することと、
を含む、方法。
【請求項２】
各テンプレートパターンの前記探索エリアは、前記画像内の、値を計算すべき前記画素を除外するように規定される、請求項１に記載の方法。
【請求項３】
前記テンプレートパターン内の前記画素の前記値を前記候補パターンの前記画素の前記値と比較することの前に、値を計算すべき各画素の初期値を計算することをさらに含み、
画素の各初期値は、近傍の画素の前記値に依存して計算される、請求項１又は２に記載の方法。
【請求項４】
前記導出された画素値を結合する前記プロセスであって、画素の結果の値を生成する、前記画素値を結合するプロセスは、前記導出された画素値の加重平均を計算することを含み、
前記加重平均は、
前記導出された画素値の重み付きバージョンを第１のメモリバッファに累積することと、
前記導出された画素値を重み付けするために用いる重み値を第２のメモリバッファに累積することと、
前記第１のメモリバッファからの前記累積された値を、前記第２のメモリバッファからの前記累積された値で除算することと、
によって計算される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
各テンプレートパターンは、前記テンプレートパターンに含まれる、値を計算すべき画素の数に依存するサイズで規定され、
それによって、値を計算すべき前記画素の数が増加するにつれて、前記テンプレートパターンの前記サイズが増加する、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
各テンプレートパターン及び各探索エリアは、値を計算すべき前記複数の画素のそれぞれに対して規定され、
各テンプレートパターン及び各探索エリアは、値を計算すべき前記対応する画素を中心とする、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
画像を定義する画像データを処理して、前記画像内の複数の画素について画素値を計算するように動作可能な画像処理装置であって、
画素のテンプレートパターンを複数規定するように動作可能なテンプレートパターン選択器（７０）であって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、値を計算すべき画素のそれぞれは、前記テンプレートパターンのうち少なくとも２つに存在する、テンプレートパターン選択器と、
各テンプレートパターンに関して、前記画像の全体を含むか又は前記テンプレートパターンよりも大きい前記画像の領域を含む、探索エリアを規定するように動作可能な探索エリア選択器（８０）と、
各テンプレートパターンに関して処理を行うように動作可能な最良一致パターン選択器（９０）であって、前記最良一致パターン選択器（９０）は、
−前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々の前記画素の前記値と比較し、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含み、
−前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択し、
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求め、
それによって、前記画像内の値を計算すべき各画素に関して複数の値を生成し、各値はそれぞれ異なる候補パターンから導出されるようにする、
最良一致パターン選択器（９０）と、
値を計算すべき各画素に関して、前記導出された画素値を結合するように動作可能な画素値計算機（１００、１１０、１２０）であって、それによって結果の値を生成する、画素値計算機と、を備える、画像処理装置。
【請求項８】
前記探索エリア選択器（８０）は、各テンプレートパターンに対して、前記画像内の値を計算すべき前記画素を除外するように前記探索エリアを規定するよう構成される、請求項７に記載の装置。
【請求項９】
初期充填値計算器（６０）をさらに備え、
前記初期充填値計算器（６０）は、前記最良一致パターン選択器（９０）が前記テンプレートパターン内の前記画素の前記値を前記候補パターンの前記画素の前記値と比較する前に、値を計算すべき各画素の初期値を前記初期充填値計算器（６０）が計算するように動作可能であり、
前記初期充填値計算機（６０）は、画素の各初期値を近傍の画素の前記値に依存して計算するように構成される、請求項７又は８に記載の装置。
【請求項１０】
前記画素値計算機（１２０）は、前記導出された画素値の加重平均を計算する処理を行うことによって、前記導出された画素値を結合して、画素の結果の値を生成するように構成され、
加重平均を計算する前記処理は、
前記導出された画素値の重み付きバージョンを第１のメモリバッファ（１００）に累積することと、
前記導出された画素値を重み付けするために用いる重み値を第２のメモリバッファ（１１０）に累積することと、
前記第１のメモリバッファ（１００）からの前記累積された値を、前記第２のメモリバッファ（１１０）からの前記累積された値で除算することと、
を含む、請求項７〜９のいずれか一項に記載の装置。
【請求項１１】
前記テンプレートパターン選択器（７０）は、各テンプレートパターンを、前記テンプレートパターンに含まれる、値を計算すべき画素の数に依存するサイズで規定するように構成され、
それによって、値を計算すべき前記画素の数が増加するにつれて、前記テンプレートパターンの前記サイズが増加する、請求項７〜１０のいずれか一項に記載の装置。
【請求項１２】
前記テンプレートパターン選択器（７０）及び前記探索エリア選択器（８０）は、各テンプレートパターン及び各探索エリアを、値を計算すべき前記複数の画素のそれぞれに対して規定するように構成され、
各テンプレートパターン及び各探索エリアは、値を計算すべき前記対応する画素を中心とする、請求項７〜１１のいずれか一項に記載の装置。
【請求項１３】
プログラマブル処理装置を、請求項１〜６のうちの少なくとも１つに記載の方法を行うように動作可能となるようプログラムするためのコンピュータプログラム命令を含む、コンピュータプログラム製品。
【請求項１】
画像を定義する画像データを処理して、前記画像内の複数の画素について画素値を計算する方法であって、
画素のテンプレートパターンを複数規定することであって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、値を計算すべき画素のそれぞれは、前記テンプレートパターンのうち少なくとも２つに存在する、テンプレートパターンを規定することと、
各テンプレートパターンに関して、
−前記画像の全体を含むか、又は前記テンプレートパターンよりも大きい前記画像の領域を含む、探索エリアを規定すること、
−前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々における前記画素の前記値と比較することであって、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含む、値を比較すること、
−前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択すること、及び
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求めること
と、
それによって、前記画像内の値を計算すべき各画素に関して、複数の値を生成することであって、各値はそれぞれ異なる候補パターンから導出される、値を生成することと、
値を計算すべき各画素に関して、前記画素に対する前記導出された画素値を結合することであって、結果の値を生成する、画素値を結合することと、
を含む、方法。
【請求項２】
各テンプレートパターンの前記探索エリアは、前記画像内の、値を計算すべき前記画素を除外するように規定される、請求項１に記載の方法。
【請求項３】
前記テンプレートパターン内の前記画素の前記値を前記候補パターンの前記画素の前記値と比較することの前に、値を計算すべき各画素の初期値を計算することをさらに含み、
画素の各初期値は、近傍の画素の前記値に依存して計算される、請求項１又は２に記載の方法。
【請求項４】
前記導出された画素値を結合する前記プロセスであって、画素の結果の値を生成する、前記画素値を結合するプロセスは、前記導出された画素値の加重平均を計算することを含み、
前記加重平均は、
前記導出された画素値の重み付きバージョンを第１のメモリバッファに累積することと、
前記導出された画素値を重み付けするために用いる重み値を第２のメモリバッファに累積することと、
前記第１のメモリバッファからの前記累積された値を、前記第２のメモリバッファからの前記累積された値で除算することと、
によって計算される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
各テンプレートパターンは、前記テンプレートパターンに含まれる、値を計算すべき画素の数に依存するサイズで規定され、
それによって、値を計算すべき前記画素の数が増加するにつれて、前記テンプレートパターンの前記サイズが増加する、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
各テンプレートパターン及び各探索エリアは、値を計算すべき前記複数の画素のそれぞれに対して規定され、
各テンプレートパターン及び各探索エリアは、値を計算すべき前記対応する画素を中心とする、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
画像を定義する画像データを処理して、前記画像内の複数の画素について画素値を計算するように動作可能な画像処理装置であって、
画素のテンプレートパターンを複数規定するように動作可能なテンプレートパターン選択器（７０）であって、前記テンプレートパターンは互いに重なり、各テンプレートパターンが前記画像の領域を含み、値を計算すべき画素のそれぞれは、前記テンプレートパターンのうち少なくとも２つに存在する、テンプレートパターン選択器と、
各テンプレートパターンに関して、前記画像の全体を含むか又は前記テンプレートパターンよりも大きい前記画像の領域を含む、探索エリアを規定するように動作可能な探索エリア選択器（８０）と、
各テンプレートパターンに関して処理を行うように動作可能な最良一致パターン選択器（９０）であって、前記最良一致パターン選択器（９０）は、
−前記テンプレートパターン内の前記画素の前記値を、複数の候補パターンの各々の前記画素の前記値と比較し、各候補パターンは、前記テンプレートパターンに対する前記探索エリアからの領域を含み、
−前記複数の候補パターンから、前記テンプレートパターンとの最良一致を表す候補パターンを選択し、
−前記テンプレートパターン内の、値を計算すべき各画素に関して、前記選択された候補パターンからそれぞれの画素値を求め、
それによって、前記画像内の値を計算すべき各画素に関して複数の値を生成し、各値はそれぞれ異なる候補パターンから導出されるようにする、
最良一致パターン選択器（９０）と、
値を計算すべき各画素に関して、前記導出された画素値を結合するように動作可能な画素値計算機（１００、１１０、１２０）であって、それによって結果の値を生成する、画素値計算機と、を備える、画像処理装置。
【請求項８】
前記探索エリア選択器（８０）は、各テンプレートパターンに対して、前記画像内の値を計算すべき前記画素を除外するように前記探索エリアを規定するよう構成される、請求項７に記載の装置。
【請求項９】
初期充填値計算器（６０）をさらに備え、
前記初期充填値計算器（６０）は、前記最良一致パターン選択器（９０）が前記テンプレートパターン内の前記画素の前記値を前記候補パターンの前記画素の前記値と比較する前に、値を計算すべき各画素の初期値を前記初期充填値計算器（６０）が計算するように動作可能であり、
前記初期充填値計算機（６０）は、画素の各初期値を近傍の画素の前記値に依存して計算するように構成される、請求項７又は８に記載の装置。
【請求項１０】
前記画素値計算機（１２０）は、前記導出された画素値の加重平均を計算する処理を行うことによって、前記導出された画素値を結合して、画素の結果の値を生成するように構成され、
加重平均を計算する前記処理は、
前記導出された画素値の重み付きバージョンを第１のメモリバッファ（１００）に累積することと、
前記導出された画素値を重み付けするために用いる重み値を第２のメモリバッファ（１１０）に累積することと、
前記第１のメモリバッファ（１００）からの前記累積された値を、前記第２のメモリバッファ（１１０）からの前記累積された値で除算することと、
を含む、請求項７〜９のいずれか一項に記載の装置。
【請求項１１】
前記テンプレートパターン選択器（７０）は、各テンプレートパターンを、前記テンプレートパターンに含まれる、値を計算すべき画素の数に依存するサイズで規定するように構成され、
それによって、値を計算すべき前記画素の数が増加するにつれて、前記テンプレートパターンの前記サイズが増加する、請求項７〜１０のいずれか一項に記載の装置。
【請求項１２】
前記テンプレートパターン選択器（７０）及び前記探索エリア選択器（８０）は、各テンプレートパターン及び各探索エリアを、値を計算すべき前記複数の画素のそれぞれに対して規定するように構成され、
各テンプレートパターン及び各探索エリアは、値を計算すべき前記対応する画素を中心とする、請求項７〜１１のいずれか一項に記載の装置。
【請求項１３】
プログラマブル処理装置を、請求項１〜６のうちの少なくとも１つに記載の方法を行うように動作可能となるようプログラムするためのコンピュータプログラム命令を含む、コンピュータプログラム製品。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公表番号】特表２０１２−５２４３１０（Ｐ２０１２−５２４３１０Ａ）
【公表日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願番号】特願２０１２−５０５１２９（Ｐ２０１２−５０５１２９）
【出願日】平成２２年４月９日（２０１０．４．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５４７０３
【国際公開番号】ＷＯ２０１０／１１８９８９
【国際公開日】平成２２年１０月２１日（２０１０．１０．２１）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
【公表日】平成２４年１０月１１日（２０１２．１０．１１）
【国際特許分類】
【出願日】平成２２年４月９日（２０１０．４．９）
【国際出願番号】ＰＣＴ／ＥＰ２０１０／０５４７０３
【国際公開番号】ＷＯ２０１０／１１８９８９
【国際公開日】平成２２年１０月２１日（２０１０．１０．２１）
【出願人】（５０１２５３３１６）ミツビシ・エレクトリック・アールアンドディー・センター・ヨーロッパ・ビーヴィ (77)
【氏名又は名称原語表記】ＭＩＴＳＵＢＩＳＨＩ ＥＬＥＣＴＲＩＣ Ｒ＆Ｄ ＣＥＮＴＲＥ ＥＵＲＯＰＥ Ｂ．Ｖ．
【住所又は居所原語表記】２０ Ｆｒｅｄｅｒｉｃｋ Ｓａｎｇｅｒ Ｒｏａｄ， Ｔｈｅ Ｓｕｒｒｅｙ Ｒｅｓｅａｒｃｈ Ｐａｒｋ， Ｇｕｉｌｄｆｏｒｄ， Ｓｕｒｒｅｙ ＧＵ２ ５ＹＤ， Ｇｒｅａｔ Ｂｒｉｔａｉｎ
【Ｆターム（参考）】
[ Back to top ]