Блог

Главная - Вопросы по программированию - Как как можно быстрее сравнить пиксель с его окружением?

Как как можно быстрее сравнить пиксель с его окружением?

#python #algorithm #image #image-processing

Вопрос:

Я пытаюсь найти быстрый алгоритм, такой как :

  • входные данные: Image (width w x height h) , radius R
  • содержание: для каждого пикселя (x,y) как
    • x в [R, w-R]
    • y в [R, h-R]

    найдите наиболее представленный цвет в круге радиуса R и центра (x,y). (На изображении)

  • вывод: Image (w-2R x h-2R) изображение, построенное на основе результатов

На данный момент я реализовал базовый алгоритм этого в python, который имеет сложность O(n*R^2) (с n = w*h ).

Теперь мне интересно O(n) , может ли существовать алгоритм сложности. Мне это кажется возможным, но я не могу его построить.

Так:

  • Как вы думаете, может ли существовать такой алгоритм ?
    • Если да, то что бы он использовал / как бы он работал ?
    • Иначе, зачем ?
  • Как я могу ускорить выполнение своего алгоритма ? (алгоритмическим способом, т. Е. независимо от распараллеливания)

Правки:

  • Я использую представление изображения с массивом 2 измерений. Каждый пиксель (т. е. ячейка массива) представляет собой кортеж int: красный, Зеленый, Синий, от 0 до 255.
  • Перед запуском этого алгоритма я «выравниваю» изображение: уменьшаю количество различных цветов, присутствующих на изображении (путем своего рода кластеризации по цвету и близости).
  • Если каждый пиксель отличается от окружающего, то он должен оставаться того же цвета (на данный момент реализован путем придания «веса» более важному цвету исходного пикселя).

Примечание: Я не уверен, что «сравнение пикселя с его окружением» — лучший способ описать то, что я хочу сделать, поэтому, если у вас есть идеи по улучшению заголовка, дайте мне знать в комментариях

Комментарии:

1. не уверен, но вам n уже нужно, потому что вам определенно нужно просмотреть все изображение, но вам также нужно проверить, находится ли конкретный пиксель в радиусе, что требует двух проверок, поэтому я не могу точно представить алгоритм, который был бы O(n)

2. Я могу представить себе способ, которым каждый пиксель, когда его посещают, как бы «распространяет» свою информацию, чтобы следующим пикселям не нужно было на самом деле проверять ее значение (немного похоже на проблему с рюкзаком). Но мне не удается выстроить в своей голове что-то, что может сработать.

3. Как именно вы представляете изображение? Вы рассматривали возможность поиска инструментов для работы с изображениями для такого рода задач?

4. Ничего не вылетело у меня из головы, извини. Для круговых фильтров вы обычно раскладываете их на строки. Для фильтра среднего значения, когда вы перемещаете круг на один пиксель, у вас есть один пиксель, выходящий из каждой строки, и один входящий пиксель. Таким образом, вы обновляете среднее значение по окружности, вычитая значения, выходящие слева, и добавляя значения, входящие справа. (1/2)

5. Медианный фильтр можно оптимизировать, поместив все значения под ядром в гистограмму; при перемещении ядра вы обновляете гистограмму так же, как и среднее значение, удаляя и добавляя значения в гистограмму. Вероятно, вы могли бы сделать что-то подобное в своем случае. Я бы посоветовал вам применить фильтр к изображению, где каждый пиксель является идентификатором кластера, а не цветом, связанным с этим кластером. Это сделает все остальное намного проще. (2/2)

Ответ №1:

Основываясь на комментариях Криса Луэнго, я улучшил свой алгоритм,:

  • Замена содержимого структуры данных из кортежей int на идентификаторы кластеров
  • Использование «движущегося ядра»: от пикселя (x,y) до (x 1, y), только обновление содержимого ячеек, выходящих и входящих в ядро
    • Это улучшение становится более заметным по мере увеличения радиуса R

Итак, ввод: image , radius

  1. Замените цвета идентификаторами 
     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 . Дельта-ядро содержит относительные положения ячеек, выходящих и входящих, и если они выходят или входят 
     kernel = [] for dx in range(-radius, radius 1):  for dy in range(-radius, radius 1):  if dx*dx   dy*dy lt;= 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 lt;= 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 lt;= 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 lt;= 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 gt; 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 lt;= 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]]

Комментарии, замечания, идеи по улучшению приветствуются 🙂

Метки: