Поиск пустых областей на изображении

Question

Этот вопрос в некоторой степени не зависит от языка, но мой инструмент выбора - просто массив.

То, что я делаю, берет разницу двух изображений через PIL:

img = ImageChops.difference(img1, img2)

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

Например, рассмотрим следующее, где o - ненулевой пиксель:

______________________
|o            ooo    |
|      oooo   ooo    |
|      o             |
|      o  o          |
|                    |
|     oo       o     |
|    o  o     ooo    |
|     oo     ooooo   |
|             ooo    |
|              o     |
|____________________|

Я бы хотел получить кортежи 4x4, содержащие ограничивающие рамки для каждой ненулевой области. Для крайнего случая

oooo
o
o  o

структура, меня не очень беспокоит то, как это обрабатывается - либо получение обоих разделов по отдельности, либо вместе, потому что границы формы перевернутой буквы L будут полностью перекрывать границы одного пикселя.

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

Моя версия psuedocode-ish выглядит примерно так:

for line in image:
   started = False
   for pixel in line:
      if pixel and not started:
         started = True
         save start coords
      elif started and not pixel:
         started = False
         save end coords (x - 1 of course)

Это должно дать мне список координат, но тогда я должен определить, являются ли регионы смежными. Я мог бы сделать это с помощью поиска типа графа? (Мы сделали много DFS и BFS в алгоритмах в прошлом семестре) Конечно, я думаю, что я мог бы сделать это вместо / в сочетании с моими предыдущими циклами?

Я не буду делать это на «больших» изображениях - они взяты с веб-камеры, и лучшее, что у меня есть, - 640x480. В лучшем случае я бы использовал 720p или 1080p, но это достаточно далеко в будущем, и это не будет проблемой.

Итак, мой вопрос (-ы): я направляюсь по правильному пути или я далеко? И что более важно, есть ли какие-то встроенные функции, которые мешают мне заново изобретать колесо? И, наконец, есть ли хорошие ресурсы, на которые я должен обратить внимание (учебные пособия, статьи и т. Д.), Которые помогут мне в этом?

Спасибо!

Answer 1

Я полагаю, модуль scipy ndimage имеет все, что вам нужно ...

Вот краткий пример

import numpy as np
import scipy as sp
import scipy.ndimage.morphology

# The array you gave above
data = np.array( 
        [
           [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
           [0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0], 
           [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
        ])


# Fill holes to make sure we get nice clusters
filled = sp.ndimage.morphology.binary_fill_holes(data)

# Now seperate each group of contigous ones into a distinct value
# This will be an array of values from 1 - num_objects, with zeros
# outside of any contigous object
objects, num_objects = sp.ndimage.label(filled)

# Now return a list of slices around each object
#  (This is effectively the tuple that you wanted)
object_slices =  sp.ndimage.find_objects(objects)

# Just to illustrate using the object_slices
for obj_slice in object_slices:
    print data[obj_slice]

Это выводит:

[[1]]
[[1 1 1]
 [1 1 1]]
[[1 1 1 1]
 [1 0 0 0]
 [1 0 0 1]]
[[1]]
[[0 1 1 0]
 [1 0 0 1]
 [0 1 1 0]]
[[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]]

Обратите внимание, что "object_slices" - это, в основном, то, что вы изначально запрашивали, если вам нужны фактические признаки.

Редактировать: просто хотел бы отметить, что, несмотря на то, что он правильно обрабатывает крайний случай

[[1 1 1 1]
 [1 0 0 0]
 [1 0 0 1]]

на самом деле это не так (таким образом, одинокий [[1]]).Это можно увидеть, если распечатать массив «objects» и взглянуть на объекты 3 и 4.

[[1 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0]
 [0 0 0 0 0 0 3 3 3 3 0 0 0 2 2 2 0 0 0 0]
 [0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 3 0 0 4 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
 [0 0 0 0 0 5 5 0 0 0 0 0 0 0 6 0 0 0 0 0]
 [0 0 0 0 5 5 5 5 0 0 0 0 0 6 6 6 0 0 0 0]
 [0 0 0 0 0 5 5 0 0 0 0 0 6 6 6 6 6 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0]]

Надеюсь, это поможет!

[ 1 ]

Answer 2

Пакет кластеризации (, т. Е. Этот ) должен быть в состоянии выполнять большую часть работы (найти подключенные пиксели). Найти ограничивающий прямоугольник для кластера тривиально.

Answer 3

Вы можете найти подключенные компоненты на изображении, а затем определить ограничивающие рамки этих компонентов.