快速扩散强度算法

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算法(将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

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

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

看起来您已经手动实现了与此内核的卷积.

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

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