7

here で概説されているように、テクスチャ合成のアルゴリズムを実装しています。このために、差の二乗和を計算する必要があります。これは、templateと の異なる位置の間の誤差を推定する指標imageです。次のように、動作が遅い実装があります。 

total_weight = valid_mask.sum()  
for i in xrange(input_image.shape[0]):  
    for j in xrange(input_image.shape[1]):  
        sample = image[i:i + window, j:j + window]  
        dist = (template - sample) ** 2  
        ssd[i, j] = (dist * valid_mask).sum() / total_weight

ここでtotal_weightは、正規化のためだけです。一部のピクセルは強度が不明なためvalid_mask、マスキングに使用します。このネストされたループは 2 つのループの内側にあるため、4 つのネストされたループは明らかにパフォーマンス キラーです!

このネストされたループの代わりに、NumPy または Python で高速化する方法はありますか? ベクトル化は可能ですか? の (3, 3) を使用して の(3, 3)一部に取り組む必要があります。imagetemplate

その後、これを Cython に実装する予定なので、NumPy だけを使用してより速く動作させることができれば、より良い結果が得られます。

完全なコードはここにあります。62行目から67行目はここに引用されています。

ありがとう、
チンタク

4

4 に答える 4

10

これは基本的に Warren Weckesser の回答を改善したものです。元の配列の多次元ウィンドウ ビューを使用する方法は明らかですが、そのビューがコピーをトリガーしないようにする必要があります。を展開するsum((a-b)**2)と に変換sum(a**2) + sum(b**2) - 2*sum(a*b)でき、線形代数演算子で実行できるこの積和演算を乗算してから縮小することができ、パフォーマンスとメモリ使用量の両方が大幅に改善されます。

def sumsqdiff3(input_image, template):
    window_size = template.shape
    y = as_strided(input_image,
                    shape=(input_image.shape[0] - window_size[0] + 1,
                           input_image.shape[1] - window_size[1] + 1,) +
                          window_size,
                    strides=input_image.strides * 2)
    ssd = np.einsum('ijkl,kl->ij', y, template)
    ssd *= - 2
    ssd += np.einsum('ijkl, ijkl->ij', y, y)
    ssd += np.einsum('ij, ij', template, template)

    return ssd

In [288]: img = np.random.rand(500, 500)

In [289]: template = np.random.rand(3, 3)

In [290]: %timeit a = sumsqdiff2(img, template) # Warren's function
10 loops, best of 3: 59.4 ms per loop

In [291]: %timeit b = sumsqdiff3(img, template)
100 loops, best of 3: 18.2 ms per loop

In [292]: np.allclose(a, b)
Out[292]: True

valid_maskどのように使用するのか完全には理解できないため、意図的にパラメーターを省略しました。原則として、templateand/orの対応する値をゼロにするだけでinput_image、同じトリックを実行できます。

于 2013-07-26T16:01:55.073 に答える
6

as_stridednumpy のブロードキャスト機能と組み合わせることで、驚くべきことができます。関数の 2 つのバージョンを次に示します。

import numpy as np
from numpy.lib.stride_tricks import as_strided


def sumsqdiff(input_image, template, valid_mask=None):
    if valid_mask is None:
        valid_mask = np.ones_like(template)
    total_weight = valid_mask.sum()
    window_size = template.shape
    ssd = np.empty((input_image.shape[0] - window_size[0] + 1,
                    input_image.shape[1] - window_size[1] + 1))
    for i in xrange(ssd.shape[0]):  
        for j in xrange(ssd.shape[1]):  
            sample = input_image[i:i + window_size[0], j:j + window_size[1]]  
            dist = (template - sample) ** 2  
            ssd[i, j] = (dist * valid_mask).sum()
    return ssd


def sumsqdiff2(input_image, template, valid_mask=None):
    if valid_mask is None:
        valid_mask = np.ones_like(template)
    total_weight = valid_mask.sum()
    window_size = template.shape

    # Create a 4-D array y, such that y[i,j,:,:] is the 2-D window
    #     input_image[i:i+window_size[0], j:j+window_size[1]]
    y = as_strided(input_image,
                    shape=(input_image.shape[0] - window_size[0] + 1,
                           input_image.shape[1] - window_size[1] + 1,) +
                          window_size,
                    strides=input_image.strides * 2)

    # Compute the sum of squared differences using broadcasting.
    ssd = ((y - template) ** 2 * valid_mask).sum(axis=-1).sum(axis=-1)
    return ssd

それらを比較する ipython セッションを次に示します。

デモに使用するテンプレート:

In [72]: template
Out[72]: 
array([[-1,  1, -1],
       [ 1,  2,  1],
       [-1,  1, -1]])

結果を調べるための小さな入力:

In [73]: x
Out[73]: 
array([[  0.,   1.,   2.,   3.,   4.,   5.,   6.],
       [  7.,   8.,   9.,  10.,  11.,  12.,  13.],
       [ 14.,  15.,  16.,  17.,  18.,  19.,  20.],
       [ 21.,  22.,  23.,  24.,  25.,  26.,  27.],
       [ 28.,  29.,  30.,  31.,  32.,  33.,  34.]])

2 つの関数を に適用してx、同じ結果が得られることを確認します。

In [74]: sumsqdiff(x, template)
Out[74]: 
array([[  856.,  1005.,  1172.,  1357.,  1560.],
       [ 2277.,  2552.,  2845.,  3156.,  3485.],
       [ 4580.,  4981.,  5400.,  5837.,  6292.]])

In [75]: sumsqdiff2(x, template)
Out[75]: 
array([[  856.,  1005.,  1172.,  1357.,  1560.],
       [ 2277.,  2552.,  2845.,  3156.,  3485.],
       [ 4580.,  4981.,  5400.,  5837.,  6292.]])

次に、より大きな入力「画像」を作成します。

In [76]: z = np.random.randn(500, 500)

パフォーマンスを確認します。

In [77]: %timeit sumsqdiff(z, template)
1 loops, best of 3: 3.55 s per loop

In [78]: %timeit sumsqdiff2(z, template)
10 loops, best of 3: 33 ms per loop

汚すぎる格好はやめて。:)

2 つの欠点:

  • の計算によりsumsqdiff2、3x3 テンプレートの場合、 の 9 倍のサイズになる一時的な配列が生成されinput_imageます。(一般的にはtemplate.sizeの倍の大きさになりinput_imageます。)
  • これらの「ストライド トリック」は、コードを Cythonize する場合には役に立ちません。Cython に変換すると、numpy でベクトル化するときに削除したループを元に戻すことになることがよくあります。
于 2013-07-26T13:51:20.017 に答える
1

行ごとに計算を実行するようにアルゴリズムを再配置すると、どのように実行されるかを確認する価値があるかもしれません。メモリを連続して読み取ると、CPUキャッシュをより適切に使用できるという考えがあります。

擬似コード:

for template_row in template:
  for row in image:
    for col in image:
      # find distance template_row to sample_row
      # add sum to ssd[row - template_row, col]

実際のコード (ウォーレンの後):

def sumsqdiffr(input_image, template, valid_mask=None):
    if valid_mask is None:
        valid_mask = np.ones_like(template)
    total_weight = valid_mask.sum()
    window_size = template.shape
    ssd = np.zeros((input_image.shape[0] - window_size[0] + 1,
                    input_image.shape[1] - window_size[1] + 1))

    for tr in xrange(template.shape[0]):
        for i in xrange(tr, ssd.shape[0] + tr):
            for j in xrange(ssd.shape[1]):  
                sample = input_image[i, j:j + window_size[1]]  
                dist = (template[tr] - sample) ** 2  
                ssd[i - tr, j] += (dist * valid_mask[tr]).sum()
    return ssd

元の実装よりも2 倍以上遅くなります。

（誰かが私に全体的な考えが間違っていたのか、それとも何が原因なのかを教えてくれたら、喜んで理解してもらいたい）

于 2013-07-26T13:31:02.923 に答える
0

アルゴリズムの実装はうまくいったと思います。ベクトル化はオプションですが、Python 構文をマシン コードにコンパイルするNumba最適化コンパイラを使用することをお勧めします。Numba 効果はかなり印象的です。Numba vs. Cython: Take 2は、Numba の簡単な紹介とパフォーマンスの比較です。

于 2013-07-26T12:59:28.163 に答える