Geekly Articles each Day

非局所画像平滑化アルゴリズム

ノイズから画像を取り除くことは、コンピュータービジョンの基本的な操作の1つです。 スムージングアルゴリズムは、ほぼすべての場所で使用されます。これらは、写真を改善するための独立した手順と、たとえば画像内のオブジェクトを認識するためのより複雑な手順の最初の手順の両方になります。 したがって、膨大な数のスムージング方法があります。そのうちの1つについてお話したいと思います。これは、多数の同一のディテールを持つテクスチャおよび画像への良好な適用性において他とは異なります。

カットの下には多くの写真があり、より正確には交通量があります。

予備情報


タスクについて簡単に説明します。 理想的な世界では完璧な画像が得られると思われます 私は （行列またはベクトル N \回M 要素）、外部の世界に関する情報を完全に伝えます。 残念ながら、私たちはそのような美しい場所に住んでいないため、さまざまな理由で、画像で操作する必要があります I + n どこで n -行列またはノイズベクトル。 多くのノイズモデルがありますが、この記事では、 n -ホワイトガウスノイズ。 画像を復元しようとしている情報に基づいて I_d それは完璧な画像に近くなります 私は 。 残念なことに、これはほとんど常に不可能です。ノイズが多いと、データの一部が必然的に失われるためです。 さらに、問題のステートメント自体には、無限の数のソリューションが含まれます。

通常、 通常の平滑化フィルターは、隣接ピクセルに関する情報を使用して各ピクセルに新しい値を設定します。 たとえば、安価で怒っているガウスフィルターは、イメージマトリックスをガウスマトリックスで折りたたみます。 その結果、新しい画像では、各ピクセルは同じ数の元の画像とその近傍のピクセルの加重和になります。 わずかに異なるアプローチでは、中央値フィルターを使用します。つまり、各ピクセルを近くのすべてのピクセルの中央値に置き換えます。 これらの平滑化方法のアイデアの開発は、双方向フィルターです。 この手順では、選択したピクセルまでの距離とカラーのピクセルの近接度の両方に基づいて、加重和を取ります。

フィルターのアイデア


ただし、上記のフィルターはすべて、近くのピクセルに関する情報のみを使用します。 非局所平滑化フィルターの主な考え方は、処理されたピクセルに隣接するピクセルだけでなく、画像内のすべての情報を使用することです。 多くの場合、遠くのポイントの値は互いに完全に独立しているため、これはどのように機能しますか？

同じオブジェクトの異なるノイズレベルを持つ複数の画像がある場合、それらをノイズのない1つの画像に結合できることは明らかです。 これらの複数のオブジェクトが同じ画像の異なる場所に配置されている場合、この追加情報を使用できます（最初はこれらのオブジェクトを見つけます）。 また、これらのオブジェクトの外観が少し異なっていたり、部分的に重複していても、使用できる冗長データが残っています。 非局所平滑化フィルターはこの考え方を使用します。画像の類似した領域を検出し、それらの情報を相互平均に使用します。 もちろん、画像の部分が類似しているということは、それらが同じオブジェクトに属していることを意味するものではありませんが、原則として、近似は非常に良いことがわかります。 線画を見てください。 明らかに、ウィンドウ2と3はウィンドウ1に似ていますが、ウィンドウ4、5、6は似ていません。 ハンガリー議会の写真では、多数の同一の要素にも気付くことができます。

画像画像
画像

あるウィンドウのピクセルの近傍が別のウィンドウの対応するピクセルの近傍に類似している場合、これらのピクセルの値を相互平均に使用できると仮定します（図の青と緑のドット）。 しかし、これらの同様のウィンドウを見つける方法は？ 重みをそれらに合わせてどのように配置し、どのような力で互いに影響を与えますか？ イメージの断片の「類似性」の概念を形式化します。 まず、2つのピクセルを区別する関数が必要です。 ここではすべてが単純です。白黒画像の場合、通常はピクセル値の差の単純なモジュールが使用されます。 画像に関する追加情報がある場合、オプションが可能です。 たとえば、きれいな画像が完全に白い背景の完全に黒い色のオブジェクトで構成されていることがわかっている場合、ゼロの距離を色がそれほど変わらないピクセルにマッピングするメトリックを使用することをお勧めします。 カラー画像の場合、オプションも可能です。 RGB形式のユークリッドメトリックまたはHSV形式ではよりトリッキーなものを使用できます。 画像ウィンドウの「相違点」は、ピクセルの違いの合計です。

結果の値をより馴染みのあるウェイト形式に変換するといいでしょう w \ [0、1] 。 前のステップで計算されたウィンドウの差をいくつかの減少する（または少なくとも増加しない）関数に転送し、すべての可能なウィンドウでこの関数の値の合計によって得られる結果を正規化します。 通常、そのような機能の役割は、歯を磨く前に誰もがよく知っています。 e ^ {-\ frac {x ^ 2} {h ^ 2} どこで x -距離、および h -スケールの広がりのパラメーター。 以上 h 、スムージングのウィンドウ間の差が小さい。 で h \右矢印\ infty 、すべてのウィンドウは、それらの違いに関係なく、各ピクセルに等しく寄与し、画像は次のように完全にグレーになります h \右矢印0 、それ自体に対応するウィンドウのみが重要な重みを持ち、スムージングは​​機能しません。

したがって、非ローカル平均化フィルターの単純な数学モデルは次のようになります。

I_d（j）= \ sum_ {j \ in I} w（i、j）I（j）

私は 結果の画像の5番目のピクセルは、重み付きで撮影された元の画像のすべてのピクセルの合計に等しい w 重量は

w（i、j）= \ frac {1} {Z（i）} e ^ {-\ frac {\ | I（N_i）-I（N_j）\ | ^ 2_2} {h ^ 2}}

正規化ディバイダー

Z（i）= \ sum_ {j \ in I} e ^ {-\ frac {\ | I（N_i）-I（N_j）\ | ^ 2_2} {h ^ 2}}

上記の代替指標：

\ rho（x、y、t）= \ begin {cases} 0、＆amp; \ text {if $ | x-y |＆lt; t $}。\\ | x-y | -t、＆amp; \テキスト{その他の場合}。 \ end {cases}

すべての場合 \ | I（N_i）-I（N_j）\ | 上記のウィンドウ間の要素ごとの違いを示します。

よく見ると、最終的な式はバイラテラルフィルターの式とほぼ同じです。ピクセル間の幾何学的な距離と色差ではなく、指数のみが画像のフラップ間の差であり、合計は画像のすべてのピクセルで実行されます。

効率に関する考慮事項と実装


明らかに、提案されたアルゴリズムの複雑さ O（n ^ 2（2r + 1）） どこで r 画像部分の類似性が計算されるウィンドウの半径です。 n -ピクセルの合計数。各ピクセルについて、サイズの近傍を比較するため 2r + 1 他のすべてのピクセルの近傍で。 アルゴリズムの素朴な実装は300x300の画像でも非常にゆっくりと動作するため、これはあまり良くありません。 通常、次の改善が提案されます。


このアルゴリズムを検討するときに生じる通常の質問は、なぜ領域の中心ピクセルの値のみを使用するのかということです。 一般的に言えば、二国間アンチエイリアシングのように、エリア全体の合計をメイン式に入れることを妨げるものはなく、これは複雑さにわずかに影響を及ぼしますが、修正されたアルゴリズムの結果はぼやけすぎます。 実際の画像では、同じオブジェクトであっても完全に同一であることはめったにないことを忘れないでください。アルゴリズムのこのような修正はそれらを平均化します。 隣接する画像要素からの情報を活用するために、通常の双方向のアンチエイリアスを事前に実行できます。 元のオブジェクトがまったく同じであることがわかっていた場合（テキストを平滑化した場合）には、そのような変更は有益です。

アルゴリズムの単純な実装（C + OpenCV 2.4.11）：

#include "targetver.h" #include <stdio.h> #include <math.h> #include <opencv2/opencv.hpp> #include "opencv2/imgproc/imgproc.hpp" #include "opencv2/imgproc/imgproc_c.h" #include "opencv2/highgui/highgui.hpp" #include "opencv2/core/core.hpp" #include "opencv2/features2d/features2d.hpp" #include "opencv2/calib3d/calib3d.hpp" #include "opencv2/nonfree/nonfree.hpp" #include "opencv2/contrib/contrib.hpp" #include <opencv2/legacy/legacy.hpp> #include <stdlib.h> #include <stdio.h> using namespace cv; /* Returns measure of diversity between two pixels. The more pixels are different the bigger output number. Usually it's a good idea to use Euclidean distance but there are variations. */ double distance_squared(unsigned char x, unsigned char y) { unsigned char zmax = max(x, y); unsigned char zmin = min(x, y); return (zmax - zmin)*(zmax - zmin); } /* Returns weight of interaction between regions: the more dissimilar are regions the less resulting influence. Usually decaying exponent is used here. If distance is Euclidean, being combined, they form a typical Gaussian function. */ double decay_function(double x, double dispersion) { return exp(-x/dispersion); } int conform_8bit(double x) { if (x < 0) return 0; else if (x > 255) return 255; else return static_cast<int>(x); } double distance_over_neighbourhood(unsigned char* data, int x00, int y00, int x01, int y01, int radius, int step) { double dispersion = 15000.0; //should be manually adjusted double accumulator = 0; for(int x = -radius; x < radius + 1; ++x) { for(int y = -radius; y < radius + 1; ++y) { accumulator += distance_squared(static_cast<unsigned char>(data[(y00 + y)*step + x00 + x]), static_cast<unsigned char>(data[(y01 + y)*step + x01 + x])); } } return decay_function(accumulator, dispersion); } int main(int argc, char* argv[]) { int similarity_window_radius = 3; //may vary; 2 is enough for text filtering char* imageName = "text_noised_30.png"; IplImage* image = 0; image = cvLoadImage(imageName, CV_LOAD_IMAGE_GRAYSCALE); if (image == NULL) { printf("Can not load image\n"); getchar(); exit(-1); } CvSize currentSize = cvGetSize(image); int width = currentSize.width; int height = currentSize.height; int step = image->widthStep; unsigned char *data = reinterpret_cast<unsigned char *>(image->imageData); vector<double> processed_data(width*height, 0); //External cycle for(int x = similarity_window_radius + 1; x < width - similarity_window_radius - 1; ++x) { printf("x: %d/%d\n", x, width - similarity_window_radius - 1); for(int y = similarity_window_radius + 1; y < height - similarity_window_radius - 1; ++y) { //Inner cycle: computing weight map vector<double> weight_map(width*height, 0); double* weight_data = &weight_map[0]; double norm = 0; for(int xx = similarity_window_radius + 1; xx < width - similarity_window_radius - 1; ++xx) for(int yy = similarity_window_radius + 1; yy < height - similarity_window_radius - 1; ++yy) { double weight = distance_over_neighbourhood(data, x, y, xx, yy, similarity_window_radius, step); norm += weight; weight_map[yy*step + xx] = weight; } //After all weights are known, one can compute new value in pixel for(int xx = similarity_window_radius + 1; xx < width - similarity_window_radius - 1; ++xx) for(int yy = similarity_window_radius + 1; yy < height - similarity_window_radius - 1; ++yy) processed_data[y*step + x] += data[yy*step + xx]*weight_map[yy*step + xx]/norm; } } //Transferring data from buffer to original image for(int x = similarity_window_radius + 1; x < width - similarity_window_radius - 1; ++x) for(int y = similarity_window_radius + 1; y < height - similarity_window_radius - 1; ++y) data[y*step + x] = conform_8bit(processed_data[y*step + x]); cvSaveImage("gray_denoised.png", image); cvReleaseImage(&image); return 0; }

例


いくつかの結果を見てみましょう：

画像画像

線のほぼ完璧な平滑化と明確なエッジに注意してください。 画像内の正方形領域が同じであるほど、アルゴリズムの動作は向上します。 ここでは、ラインに沿ったすべての正方形の領域がほぼ同じであるため、プログラムには各タイプの近隣の十分な例がありました。

もちろん、単純な正方形のウィンドウではエリアの「類似性」を検出できない場合には、すべてがそれほどバラ色ではありません。 例：

画像画像

背景と円の内側は滑らかになりましたが、アーチファクトは円に沿って残りました。 もちろん、アルゴリズムは円の右側が左側と同じであり、180度回転していることを理解できないため、これを平滑化の際に使用します。 このような明らかなミスは、回転したウィンドウを調べることで修正できますが、実行時間はウィンドウの回転数を考慮した回数だけ増加します。

アルゴリズムが直線だけでなく平滑化できることは間違いないので、平滑化パラメーターを選択することの重要性を同時に示す別の例を次に示します。

画像画像
画像画像

2番目の図では、前のケースとほぼ同じアーティファクトが表示されています。 ここでは、同様のウィンドウが不足しているわけではありませんが、パラメーターが小さすぎます h ：同様の領域でも、重量が増えすぎます。 対照的に、4番目の写真では、大きすぎるサイズが選択されました h 、およびすべてのエリアがほぼ同じ重量を受け取りました。 3番目は中間点を表します。

テキストの作業の別の例。 小さくて非常にノイズの多い画像でさえ、その後のマシンでの使用に十分に処理されます（もちろん、ヒストグラムをイコライズし、シャープにした後）：

画像
画像
画像

すでに最適化された非ローカルアンチエイリアシングアルゴリズムを適用できるサイトのいくつかの例：





順序：元の、うるさい、復元された。 似たような要素が多いエッシャーの図面がどれほどきれいに掃除されたかに注目してください。 黒い線のみがより透明になり、テクスチャが滑らかになりました。

特徴点記述子を使用した重みのカウント

残念ながら、アルゴリズムの計算の複雑さが高いため、その実用的な用途が制限されていますが、繰り返し要素を使用して画像を平滑化する問題については良い結果を示しています。 このアルゴリズムの主な問題は、重みを計算するという基本的な考え方にあります。 各ピクセルが他のすべてのピクセルを回る必要があります。 すべてのピクセルをダブル表示することは避けられない悪であると想定しても、ウィンドウ3の半径でさえ重みを計算する時間が49倍増加するため、その隣のピクセルを表示することは不要に思えます。 元のアイデアに戻りましょう。 互いに滑らかにするためにそれらを使用するために、画像内の同様の場所を見つけたいです。 ただし、画像内のすべての可能なウィンドウをピクセルごとに比較して、同様の場所を見つける必要はありません。 興味深い画像要素を特定して比較する良い方法はすでにあります！ もちろん、私はさまざまな機能記述子について話している。 通常、これはSIFTを意味しますが、この段階の目標は、まったく同じではなく、かなり類似した領域を多数見つけることであるため、精度が低いものを使用することをお勧めします。 記述子を使用する場合、重みを計算する手順は次のようになります。


このアプローチの利点：


短所：


おわりに

結論：


このため、画像内の類似オブジェクトに関する情報を使用して、きれいな画像に最も近似する平滑化アルゴリズムを検討しました。 このような「疑似認識」から、類似オブジェクトの選択後、実際のスムージングへの移行はそれほど遠くありません。 実際、画像復元の最新のアプローチでは、この目的のためにニューラルネットワークを使用しており、原則として、実際にはより良く、より速く動作します。 ただし、ニューラルネットワークにはより多くのプログラミングスキルと微調整が必​​要です。 このようなアルゴリズムでさえ、認識のシミュレーションのみで、同等の、場合によってはより良い結果が得られます。

ソース


Antoni Buades、Bartomeu Coll画像ノイズ除去のための非ローカルアルゴリズム
Yifei Lou、Paolo Favaro、Stefano Soatto、Andrea Bertozzi非局所類似画像フィルタリング

Source: https://habr.com/ru/post/J273159/

More articles:


All Articles