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

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))

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