javascript - 快速扩散强度算法

Question

首先为标题道歉，我不知道它是否描述了我想要实现的目标，但它是我所拥有的最好的。

基本上我有一个数组来描述二维空间的强度。然后我想在给定的一组迭代中将此强度分配给邻居，即假设我有以下数组：

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算法进行一次传递（将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 ]]

看起来您已经手动实现了使用此内核的卷积。

为了加快速度：因为卷积是关联的，您可以预先计算单个过滤器，而不是多次应用原始过滤器。例如，如果通过 = 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在循环中集成函数，函数调用可能有点昂贵。

但是，我强烈建议您使用 Profiler（ Firebug的内置功能非常好），以真正衡量性能并快速找到瓶颈。

Answer 3

需要注意的一点是，在相对稀疏的情况下（例如第一个设置，其中只有一个强度 > 0 的条目），您只需要关注一些条目。

根据您的需要，可以跟踪实际需要更新的条目，并忽略额外的计算。

编辑

我去挖掘了这种方法的一个例子。Conway 的生命游戏/元胞自动机的模拟在优化方面存在类似的困难。在每个阶段，必须根据周围的细胞计算每个细胞的状态。

一个非常强大的实现是Hashlife。基本上，它使用巧妙的散列来跟踪哪些单元格实际需要更新，并记忆（缓存模式）计算。你可能会从它的策略中找到灵感。

Answer 4

感谢上面 ehemient 的回复，我能够获得修复此算法所需的信息。我最终得到了一个快 50-55% 的算法。还要感谢 CMS 的 javascript 性能黑客（它们实际上有很大的不同）。

为了完整起见，我包含以下代码：

注意：代码已经过优化，因此它不是最简洁的代码（展开的继续、数组的反向迭代等）大量的本地 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; 
    }

谢谢大家

圭多