如何盡快將像素與其周圍環境進行比較？

我正在嘗試找到一種快速演算法，例如：

• 輸入：Image (width w x height h)，radius R

• 內容：對于每個像素 (x,y) 作為

  • [R, wR] 中的 x
  • y 在 [R, hR]

  在半徑R和中心 (x,y)的圓中找到最具代表性的顏色。（在影像中）

• 輸出：Image (w-2R x h-2R)根據結果??構建的影像

目前，我已經在 python 中實作了基本演算法，它具有復雜性O(n*R^2)（帶有n = w*h）。

我現在想知道是否O(n)可能存在復雜的演算法。對我來說這聽起來可能，但我無法建立一個。

所以：

• 你認為可能存在這樣的演算法嗎？
  • 如果是這樣，他將使用什么/他將如何作業？
  • 否則，為什么？
• 如何加快演算法的執行速度？（以演算法方式，即與并行化無關）

編輯：

• 我使用帶有二維陣列的影像表示。每個像素（即陣列的單元格）是一個整數元組：紅色、綠色、藍色，介于 0 和 255 之間。
• 在運行這個演算法之前，我對影像進行“調平”：減少影像中不同顏色的數量（通過一種顏色和接近度的聚類）
• 如果周圍的每個像素都不同，那么它應該保持相同的顏色（現在通過賦予原始像素顏色更重要的“權重”來實作）

注意：我不確定“將像素與其周圍的像素進行比較”是描述我想要做什么的最佳方式，因此如果您有改進標題的想法，請在評論中告訴我

uj5u.com熱心網友回復：

根據Cris Luengo 的評論，我通過以下方式改進了我的演算法：

• 將資料結構的內容從 int 元組替換為集群 ID
• 使用“移動內核”：從像素 (x,y) 到 (x 1, y)，僅更新有關離開和進入內核的單元格的內容
  • 隨著半徑的R增加，這種改進更加明顯

因此，輸入：image，radius

1. 用 id 替換顏色

   colors = {}
   id_counter = 0
   raw = np.zeros((image.width, image.height))
   data = image.load()
   for x in range(image.width):
       for y in range(image.height):
           color = data[x,y]
           id = colors.get(color, -1)
           if id == -1:
               id = id_counter
               id_counter  = 1
               colors[color] = id
           raw[x,y] = id
   

2. 構建kernel和delta kernel. Delta 核包含細胞離開和進入的相對位置，以及它們是離開還是進入

   kernel = []
   for dx in range(-radius, radius 1):
       for dy in range(-radius, radius 1):
           if dx*dx   dy*dy <= radius*radius:
               kernel.append((dx,dy))
   
   delta_kernel = []
   for dx in range(-radius, radius 1):
       mini = None
       for dy in range(-radius, radius 1):
           if dx*dx   dy*dy <= radius*radius:
               mini = dy - 1
               break
       delta_kernel.append((dx, mini, -1))
   
   for dx in range(-radius, radius 1):
       maxi = -9999
       for dy in range(-radius, radius 1):
           if dx*dx   dy*dy <= radius*radius:
               maxi = max(dy, maxi)
       delta_kernel .append((dx, maxi, 1))
   

   注意：這實際上合并在一個回圈中，但為了清楚起見，我將步驟分開

3. 實際演算法

   counter = {} # Map counting occurrences
   new_raw = np.zeros((raw.shape[0] - radius*2, raw.shape[1] - radius*2))
   
   direction =  1 # Y direction  /-1
   y = radius
   for x in range(radius, raw.shape[0]-radius):
       if x == radius: # First time: full kernel
           for (dx, dy) in kernel:
               key = raw[x dx, y dy]
               counter[key] = counter.get(key, 0)   1
       else: # move to the right (x  ): delta kernel horizontally
           for (dy, dx, sign) in delta_kernel:
               key = raw[x   dx, y   direction*dy]
               new_val = counter.get(key,0)   sign
               if new_val <= 0:
                   counter.pop(key) # Remove key to useless key values in the map
               else:
                   counter[key] = new_val
   
       for i in range(raw.shape[1]-2*radius):
           if i > 0:
               # y moves forward: delta radius (on y=0, x moved forward not y)
               for (dx, dy, sign) in delta_kernel:
                   key = raw[x   dx, y   direction*dy]
                   new_val = counter.get(key,0)   sign
                   if new_val <= 0:
                       counter.pop(key)
                   else:
                       counter[key] = new_val
   
           # Find most represented value
           winner_item = max(counter.items(), key=lambda i:i[1])
           if winner_item[1] == 1: # Every pixels are different: take the center one by default.
               winner_key = raw[x,y]
           else:
               winner_key = winner_item[0]
           new_raw[x-radius, y-radius] = winner_key
           y  = direction
       y -= direction # Prevent y to go out from range
   
       direction *= -1
   

4. 重建鏡像

   reversed_color_map = {}
   for key, value in colors.items():
       reversed_color_map[value] = key
   
   result = Image.new(mode=image.mode, size=(image.width-2*radius, image.height-2*radius))
   out_data = result.load()
   for x in range(raw.shape[0]):
       for y in range(raw.shape[1]):
           out_data[x,y] = reversed_color_map[raw[x,y]]
   

歡迎評論，評論，改進想法:)

標籤：Python 算法 图片 图像处理

上一篇：hudi clustering 資料聚集（一）

下一篇：通過多個元素進行二分搜索