algorithm - カーネルを近似する可変半径ガウスぼかし

Question

可変半径 (標準偏差) のガウスぼかしを書いています。つまり、画像の各ピクセルは異なるカーネルを使用して畳み込まれています。ガウスぼかしを計算するための標準的な手法はここでは機能しません: FFT、軸分離、繰り返されるボックスぼかし - それらはすべて、カーネルが画像全体で同じであると仮定しています。

今、私は次のスキームを使用してそれを近似しようとしています:

ガウス カーネル K(x,y) を、次のように、軸に沿った四角形 R _kの集合 Nと係数 α _kによって定義される区分定数関数 f(x,y) で近似します。

    f(x,y) = ∑<sub>k=1 ^N α _k ·χ _{R k} (x,y)

g(x,y) を画像とすると、

    ∬<sub>ℝ<sup>2 K(x,y)·g(x,y) dxdy ≈ ∬<sub>ℝ<sup>2 f(x,y)·g(x,y) dxdy = ∑< sub>k=1 ^N α _k ·∬<sub>R _k g(x,y) dxdy

RHS の積分は四角形の単純な積分であるため、画像全体の部分和を事前に計算することで一定時間で計算できます。

結果のアルゴリズムは O(W·H·N) で実行されます。ここで、W と H は画像の次元であり、N は (AFAIK) 近似の誤差に反比例します。

残りの部分は、適切な近似関数 f(x,y) を見つけることです。長方形の数 N (誤差を最小化) または誤差 (長方形の数を最小化) が与えられたときに、ガウス分布の最適な近似を見つける方法は?

Answer 1

長方形の位置とサイズが分かれば、係数を計算するのはかなり簡単なはずなので、本当の問題は長方形をどこに置くかです。

ガウスを近似しているので、中心がガウスの中心と一致する長方形に注意を制限することは少なくとも合理的であるように思われるため、実際には1次元の問題のみがあります-入れ子になった長方形のセットのサイズを計算しますアスペクト比が 1 以外の場合は、正方形であるか、ガウスに似ていると思います。

これは動的計画法で解決できます。外側から真ん中に向かって作業するとします。ステージ N で、最大 1,2,..k 個の異なる長方形の外側ピクセルの 1,2...N リングと、最も内側の長方形のサイズから生じる最良の近似誤差を与える nxk テーブルを作成しました。その最高のエラーに責任があります。ステージ N+1 を計算するには、これまでの最も内側の長方形になるすべての可能なサイズを検討し、ピクセルの x リングを外側の領域に寄与させます。新しいリング内のピクセルと外側の四角形に残されていないその外側のリングに最適な四角形のアルファを計算します。すでに計算された表の値を使用すると、それらの領域をカバーするために最大 k 個の外側の長方形を残すときに得られる可能性のある最良のエラーがわかります。そのため、現在の N+1 リングのピクセルから寄与する最良の合計エラーを計算できます。これにより、N+1 外側ピクセルのテーブル エントリを埋めることができます。エリアの中央まで進んだら、エリア全体の最適解を導き出すことができます。