快速扩散强度算法

Convo lution 是一种常见的图像处理技术(现在您有一个关键字要搜索!).

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

看起来您已经用这个内核手工实现了卷积。

为了加快速度:因为卷积是关联的,所以可以预先计算一个过滤器,而不是多次应用原始过滤器。例如,如果passes=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

如果你要反复这样做,可能值得学习 Fourier Transform 有一个定理说明

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

或者在应用逆傅立叶变换之后,

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

换句话说,复杂的卷积可以用简单的乘法来代替。

嗯,在你的 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;
};

如果迭代顺序对您的算法不重要,您可以反向迭代您的数组,即 known 更快:

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 非常好),以真正衡量性能并快速发现瓶颈。

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

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

编辑

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

一个非常强大的实现是 Hashlife . 基本上,它使用一个聪明的散列来跟踪哪些单元格实际需要更新,以及记忆(缓存模式)计算。你可以从它的策略中找到灵感。

由于上面的ephemient的响应,我能够得到修复该算法所需的信息。最后我得到了一个速度快50-55%的算法。还要感谢CMS对javascript性能的攻击(它们实际上有很大的区别)。

为了完整性,我将代码包括在内:

注意:代码是经过优化的,因此它不是neatest代码(展开后继续、数组的后向迭代等)许多本地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; 
    }

谢谢大家

圭多