基本的な複雑さの質問 - コンボリューション

Question

私はいくつかの基本的な画像フィルタリングアルゴリズムの複雑さを評価しようとしています。あなたはこの理論を検証することができれば、私は思っていた。

逆のようなピクセルフィルタによる基本画素について演算の数は、（ピクセル）入力のサイズとともに直線的に成長し、

画像の辺のS =長う してみましょうM =＃ピクセルの入力

逆順序O（M）またはO（S ^ 2）である。

一方、畳み込みフィルタは、各フィルタのための次の画素値を確立する畳み込みに近傍のサイズを決定するパラメータRを有している。

う畳み込みフィルタのR =半径

コンボリューションが注文Oである（M *（（R + R * 2）^ 2）= O（M *（4R ^ 2）= O（MR ^ 2）

または私はNピクセルにおける畳み込みフィルタ（エリア）のサイズ=せなければならない

O（M *（N））= O（MN）

最終的畳み込みフィルタは、ピクセルの数及び近傍の画素の数の積に直線的に依存している。

あなたは、これはそれを文書化された用紙へのリンクを持っている場合は、

をいただければ幸いです。

敬具、

ギャビン

Answer 1

O（MN）が、私は関係なく、Nが正方形であることの、画像内の各画素に対して畳み込み近隣Nの画素値の調整があることを理解右場合と思われます。依存性は、ソース画像内の画素ごとに調整する画素であるため、Nは最適三角形であってもよい...しかし、近傍の画素を提供するが、画像内の画素毎に調整され、次いでO（MN）は、より理にかなっています。

興味深いことに、非正規周辺に一部の画素は他のものより近傍マスクによって調整することができるが、O（MN）が静止します。

近傍画素Pに中心であり、次いでこれが立っていない地域（各ピクセルが一度変換されることを意味する）にした次のPに移動した場合。