0

假设我有一个二维数组

let img = [[0, 1, 2, 1, 3, 0],
           [1, 1, 1, 1, 1, 1],
           [1, 2, 1, 0, 1, 1],
           [1, 1, 1, 1, 1, 1],
           [0, 1, 4, 1, 5, 0],
           ]

let shape = [[0,1,0],
             [1,1,1],
             [0,1,0]]

let diamon_shape = [[0, 0, 1, 0, 0],
                    [0, 1, 1, 1, 0],
                    [1, 1, 1, 1, 1],
                    [0, 1, 1, 1, 0],
                    [0, 0, 1, 0, 0]]

我将形状（菱形）的中心放在每一列上，然后将每一行放在形状内的最大数量（= 1）上，然后用最大数量替换形状中心。这喜欢图像形态中的膨胀和腐蚀

这是我在 Swift 中的实现：

class func maximum_filter(image:[[Int]], shape:[[Int]]) -> [[Int]]{
        let wShape = shape[0].count
        let hShape = shape.count
        let wImage = image[0].count
        let hImage = image.count
        var final = Array(repeating: Array(repeating: 0.0, count: image[0].count), count: image.count)
        for i in 0..<hImage {
            for ii in 0..<wImage {
                var startOfWZ = 0
                var startOfHZ = 0
                var wStart = ii - wShape/2
                if wStart < 0 {
                    wStart = 0
                    startOfWZ = 1
                }
                var wEnd = ii + wShape/2
                if wEnd >= wImage {
                    wEnd = wImage - 1
                }
                var hStart = i - hShape/2
                if hStart < 0 {
                    hStart = 0
                    startOfHZ = 1
                }
                var hEnd = i + hShape/2
                if hEnd >= hImage {
                    hEnd = hImage - 1
                }

                var hz = startOfHZ
                var maxNumber = 0.0
                for x in hStart...hEnd {
                    var wz = startOfWZ
                    for xx in wStart...wEnd {
                        if shape[hz][wz] == 1 {
                            let currentNumber = image[x][xx]
                            if currentNumber > maxNumber {
                                maxNumber = currentNumber
                            }
                        }
                        wz += 1
                    }
                    hz += 1
                }
                final[i][ii] = maxNumber
            }
        }

        return final
    }

前 2 个循环我迭代矩阵的每个元素以将形状的中心放置到上面。然后在接下来的 2 个循环中，我得到图像映射的所有元素以及形状元素（=1），然后比较它们以获得最大数量。没什么复杂的。结果是：

1 2 2 3 3 3
1 2 2 1 3 1 
2 2 2 1 1 1 
1 2 4 1 5 1
1 4 4 5 5 5

但是当我尝试使用真实图像 4096x4096（样本中的 Double 中的输入不在 Int 中）并且菱形为 41x41 时。与python（1秒）相比，性能超慢（10秒）。这是我在 python 中使用的代码result = maximum_filter(img, footprint=shape)。后面的源码看不到maximum_filter，所以自己实现。我得到了相同的结果，但性能比他们的慢得多。

4

1 回答 1

0

您不能期望使用您想到的第一个算法从框架中获得与专门功能相同的性能。Python 函数背后的代码可能使用高级内存管理技术和不同的逻辑进行了优化。

就像这可能意味着的那种差异的一个例子一样，这里有一个简单的算法，用于相同的函数，它在 4096 x 4096 的图像和 41x41 十字准线形状上的执行速度比你的快 20 倍：

func naiveFilter(image:[[Int]],  shape:[[Int]]) -> [[Int]]
{

   let imageRows      = image.count
   let imageCols      = image.first!.count
   let shapeRows      = shape.count
   let shapeCols      = shape.first!.count
   let shapeCenterRow = shapeRows / 2  
   let shapeCenterCol = shapeCols / 2 

   let outerRowIndex  = imageRows - shapeRows + shapeCenterRow
   let outerColIndex  = imageCols - shapeCols + shapeCenterCol

   let shapeOffsets  = shape.enumerated().flatMap{ row,rowFlags in rowFlags.enumerated().filter{$1 == 1}
                                                                           .map{(row - shapeCenterRow, $0.0 - shapeCenterCol) } }

   var maxValues  = image 

   var imageRow   = 0
   var imageCol   = 0
   var imageValue = 0
   var maxValue   = 0

   for row in (0..<imageRows)
   {
        let innerRow = row >= shapeCenterRow && row < outerRowIndex

        for col in (0..<imageCols)
        {
           maxValue = 0

           if innerRow && col >= shapeCenterCol && col < outerColIndex           
           {
              for (rowOffset,colOffset) in shapeOffsets
              {
                 imageValue = image[row+rowOffset][col+colOffset]
                 if imageValue > maxValue { maxValue = imageValue }
              }
           }
           else
           {
              for (rowOffset,colOffset) in shapeOffsets
              {
                 imageRow = row + rowOffset
                 imageCol = col + colOffset

                 guard imageRow < imageRows else { break }

                 if imageRow >= 0
                 && imageCol >= 0
                 && imageCol < imageCols
                 {
                    imageValue = image[row+rowOffset][col+colOffset]
                    if imageValue > maxValue { maxValue = imageValue }
                 } 
              }
           }
           if maxValue > 0 { maxValues[row][col] = maxValue }
       }
   }

   return maxValues  
}

我什至没有进入平面内存模型、范围检查和保留循环优化、寄存器移位、汇编代码或任何你没有看到的代码中可能使用的 100 种技术。

于 2017-05-10T18:11:25.350 回答