通過形狀改進二維數組最大過濾器的性能

Question

讓說我有一個二維數組

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），然後用最大數字替換形狀中心。這個喜歡在圖像形態膨脹和腐蝕

這是我在斯威夫特實現：

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（在雙不在詮釋樣品輸入）和菱形爲41x41。與python（1秒）相比，性能超慢（10秒）。這裏我使用python result = maximum_filter(img, footprint=shape)的代碼。我看不到maximum_filter的源代碼，所以我自己實現它。我得到了同樣的結果，但表現比他們的慢得多。

Answer 1

您不能期望從使用您想到的第一個算法的框架中獲得與專用函數相同的性能。該Python函數背後的代碼可能使用先進的內存管理技術和不同的邏輯進行了優化。

正如樣的區別，這可能意味着的一個例子，下面是執行比你有一個41x41十字形狀要快20倍4096×4096的圖像上相同功能的天真的算法：

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個技術中沒有看到的任何技術。