javascript - 高速拡散強度アルゴリズム

Question

最初にタイトルについてお詫び申し上げます。それが私が達成しようとしていることを説明しているかどうかはわかりませんが、それは私が持っている最高のものです。

基本的に、2D 空間での強度を表す配列があります。次に、この強度を特定の一連の反復で近隣に分散させたいと考えています。つまり、次の配列があるとします。

intensity = [ 0, 0, 0, 0, 0, 
              0, 0, 0, 0, 0, 
              0, 0, 0, 0, 0, 
              0, 0, 100, 0, 0, 
              0, 0, 0, 0, 0, 
              0, 0, 0, 0, 0,
              0, 0, 0, 0, 0 ]

次に、distributeIntensity アルゴリズムを 1 回実行します (強度の 50% を近隣に分配します)。次に、次のようになります。

            [ 0,  0,   0,  0, 0, 
              0,  0,   0,  0, 0, 
              0, 50,  50, 50, 0, 
              0, 50, 100, 50, 0, 
              0, 50,  50, 50, 0, 
              0,  0,   0,  0, 0,
              0,  0,   0,  0, 0 ]

元の配列を 2 回パスすると、結果の配列は次のようになります。

          [ 0,   0,   0,   0, 0, 
           25,  50,  75,  50, 25, 
           50, 150, 200, 150, 50, 
          75, 200, 300, 200, 75, 
           50, 150, 200, 150, 50, 
           25,  50,  75,  50, 25,
            0,   0,   0,   0, 0 ]

私の現在のコードは次のとおりです。

this.distributeIntensities = function(passes, shareRatio) {     
    for (var i = 0; i < passes; i++) { this.distributeIntensity(shareRatio); }
}

this.distributeIntensity = function(shareRatio) {       
    var tmp = hm.intensity.slice(0); // copy array
    for (var i = 0; i < tmp.length; i++) {          
        if (hm.intensity[i] <= 0) { continue; }
        var current = hm.intensity[i];
        var shareAmount = current * shareRatio;                     
        this.shareIntensityWithNeighbours(tmp, shareAmount, i);                                                             
    }       
    hm.intensity = tmp;
}

this.shareIntensityWithNeighbours = function(arr, heat, i) {                    
    // This should be var x = Math.floor(...) however 
    // this is slower and without gives satisfactory results
    var x = i % hm.columnCount; 
    var y = i / hm.columnCount; 

    if (x > 0) {
        if (y > 0) arr[i - hm.columnCount - 1] += heat;
        arr[i - 1] += heat;
        if (y < (hm.rowCount - 1)) arr[i + hm.columnCount - 1] += heat;
    }               

    if (y > 0) arr[i - hm.columnCount] += heat;     
    if (y < (hm.rowCount - 1)) arr[i + hm.columnCount] += heat;

    if (x < (hm.columnCount - 1)) {
        if (y > 0) arr[i - hm.columnCount + 1] += heat;
        arr[i + 1] += heat;
        if (y < (hm.rowCount - 1)) arr[i + hm.columnCount + 1] += heat;
    }               
}

現在、これは機能しますが、非常に遅いです (私は巨大な配列と 8 つのパスで作業しています)。これを行うためのより速く/より良い/よりクリーンな方法があることは知っていますが、それは私の能力を超えているので、誰かが私を正しい方向に向けることができることを期待してそこに置きました(注: 私は流暢な数学を話せません。実際には私はかなり数学的に文盲です）。

前もって感謝します

グイド

Answer 1

コンボリューションは一般的な画像操作テクニックです（これで検索するキーワードができました！）。

[[ 0.5, 0.5, 0.5 ],
 [ 0.5, 1.0, 0.5 ],
 [ 0.5, 0.5, 0.5 ]]

このカーネルを使用して手動で畳み込みを実装したようです。

処理を高速化するには：畳み込みは結合法則であるため、元のフィルターを複数回適用する代わりに、単一のフィルターを事前に計算できます。たとえば、passs=2の場合。

once = [[ 0.5, 0.5, 0.5 ], [ 0.5, 1.0, 0.5 ], [ 0.5, 0.5, 0.5 ]]
twice = once ⊗ once =
    [[ 0.25, 0.50, 0.75, 0.50, 0.25 ],
     [ 0.50, 1.50, 2.00, 1.50, 0.50 ],
     [ 0.75, 2.00, 3.00, 2.00, 0.75 ], 
     [ 0.50, 1.50, 2.00, 1.50, 0.50 ], 
     [ 0.25, 0.50, 0.75, 0.50, 0.25 ]]

distribute(hm) = hm ⊗ once ⊗ once
               = hm ⊗ twice

これを繰り返し行う場合は、フーリエ変換を学ぶ価値があるかもしれません。それを述べる定理があります

FT(X ⊗ Y) = FT(X) ⋅ FT(Y)

または逆フーリエ変換を適用した後、

X ⊗ Y = IFT(FT(X) ⋅ FT(Y))

言い換えれば、複雑な畳み込みは単純な乗算に置き換えることができます。

Answer 2

さて、関数のforループで、distributeIntensityいくつかの小さな変更を加えることができると思います:

• 配列を格納しlengthます。
• ifステートメントを回避するには、ステートメントを反転しcontinueます。

this.distributeIntensity = function(shareRatio) {       
    var tmp = hm.intensity.slice(0); // copy array
    for (var i = 0, n = tmp.length; i < n; i++) {                      
        if (hm.intensity[i] > 0) {
          var current = hm.intensity[i];
          var shareAmount = current * shareRatio;
          this.shareIntensityWithNeighbours(tmp, shareAmount, i);
        }
    }
    hm.intensity = tmp;
};

アルゴリズムにとって反復順序が重要でない場合は、より高速であることが知られている配列を逆反復することができます。

this.distributeIntensity = function(shareRatio) {       
    var tmp = hm.intensity.slice(0); // copy array
    var i = tmp.length;
    while (i--) {
        if (hm.intensity[i] > 0) {
          var current = hm.intensity[i];
          var shareAmount = current * shareRatio;
          this.shareIntensityWithNeighbours(tmp, shareAmount, i);
        }
    }
    hm.intensity = tmp;
};

shareIntensityWithNeighboursまた、関数をループ内に統合することを検討することもできます。関数呼び出しは多少高価になる可能性があります。

ただし、パフォーマンスを実際に測定してボトルネックをすばやく見つけるために、プロファイラー ( Firebugに組み込まれているものは非常に優れています) を使用することを強くお勧めします。

Answer 3

注意すべき点の1つは、比較的まばらなケース（強度が0より大きいエントリが1つしかない最初のセットアップなど）では、いくつかのエントリだけを気にする必要があるということです。

必要に応じて、実際に更新する必要のあるエントリを追跡し、余分な計算を無視することができる場合があります。

編集

私はそのようなアプローチの例を掘り下げに行きました。コンウェイのライフゲーム/セルオートマトンのシミュレーションでは、最適化において同様の問題が発生します。各段階で、各セルの状態は周囲のセルに基づいて計算する必要があります。

非常に強力な実装は、Hashlifeの実装です。基本的に、巧妙なハッシュを使用して、実際に更新する必要のあるセルを追跡し、計算をメモ化（キャッシュパターン）します。あなたはその戦略にインスピレーションを見つけるかもしれません。

Answer 4

上記の ephemient の回答のおかげで、このアルゴリズムを修正するために必要な情報を得ることができました。最終的に、50 ～ 55% 高速なアルゴリズムになりました。また、javascript パフォーマンス ハックを提供してくれた CMS にも感謝します (実際には大きな違いがあります)。

完全を期すために、コードを含めます。

注: コードは最適化されているため、適切なコードではありません (アンラップされた継続、配列の逆方向の反復など) 多数のローカル var キャッシュなどがあります。

    this.distributeHeatMapIntensities = function(passes, shareRatio) {              
        var tmp = hm.intensity.slice(0);

        var distances = {};
        for (var i = -passes; i <= passes; i++) { distances[i] = Math.abs(i); }
        var shares = [];
        for (var i = 0; i <= passes; i++) { shares.push(i === 0 ? 0 : Math.pow(shareRatio, i)); }
        var len = tmp.length - 1;

        for(var i = len; i >= 0; i--) {     
            var intens = hm.intensity[i];
            if (intens > 0) {                       
                var x = Math.floor(i % hm.columnCount);
                var y = Math.floor(i / hm.columnCount);                     

                for (var tx = -passes; tx <= passes; tx++) { 
                    var nx = x + tx;
                    if (nx >= 0 && nx < hm.columnCount) {               
                        var dx = distances[tx];
                        for (var ty = -passes; ty <= passes; ty++) { 
                            var ny = y + ty;
                            if (ny >= 0 && ny < hm.rowCount) {                      
                                var dy = distances[ty];
                                var distance = dx >= dy ? dx : dy;
                                var share = shares[distance] * intens;
                                var i2 = (ny * hm.columnCount) + nx;
                                tmp[i2] += share;
                            }
                        }
                    }
                }
            }
        }   
        hm.intensity = tmp; 
    }

皆さんありがとう

グイド