Вопрос по numpy, python – Нахождение соответствующих подматриц внутри матрицы

8

У меня есть двумерный массив 100x200, представленный в виде пустого массива, состоящего из черных (0) и белых (255) ячеек. Это растровый файл. Затем у меня есть двумерные фигуры (их проще всего воспринимать как буквы), которые также являются двумерными черно-белыми ячейками.

Я знаю, что могу наивно проходить по матрице, но это будет "горячо". часть моего кода, так что скорость является проблемой. Есть ли быстрый способ сделать это в Numpy / Scipy?

Я кратко посмотрел на функцию корреляции Сципи. Меня не интересуют «нечеткие совпадения», только точные совпадения. Я также посмотрел на некоторые научные статьи, но они выше моей головы.

Ваш Ответ

2   ответа
8

Вот метод, который вы можете использовать или адаптировать, в зависимости от деталей ваших требований. Оно используетndimage.label and ndimage.find_objects:

  1. label the image using ndimage.label this finds all blobs in the array and labels them to integers.
  2. Get the slices of these blobs using ndimage.find_objects
  3. Then use set intersection to see if the found blobs correspond with your wanted blobs

Код для1. а также2.:

import scipy
from scipy import ndimage
import matplotlib.pyplot as plt

#flatten to ensure greyscale.
im = scipy.misc.imread('letters.png',flatten=1)
objects, number_of_objects = ndimage.label(im)
letters = ndimage.find_objects(objects)

#to save the images for illustrative purposes only:
plt.imsave('ob.png',objects)
for i,j in enumerate(letters):
    plt.imsave('ob'+str(i)+'.png',objects[j])

Пример ввода:

enter image description here

маркированы:

enter image description here

изолированные капли для проверки:

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

Удивительно! Это почти то, что я пытаюсь сделать. Мне нужно попробовать оба ответа и посмотреть, что работает лучше всего. Спасибо, что нашли время, чтобы опубликовать это! DaveO
9

Выcan используйте коррелят. Вам необходимо установить значения черного в -1, а значения белого в 1 (или наоборот), чтобы вы знали значение пика корреляции и чтобы оно встречалось только с правильной буквой.

Следующий код делает то, что я думаю, что вы хотите.

import numpy
from scipy import signal

# Set up the inputs
a = numpy.random.randn(100, 200)
a[a<0] = 0
a[a>0] = 255

b = numpy.random.randn(20, 20)
b[b<0] = 0
b[b>0] = 255

# put b somewhere in a
a[37:37+b.shape[0], 84:84+b.shape[1]] = b

# Now the actual solution...

# Set the black values to -1
a[a==0] = -1
b[b==0] = -1

# and the white values to 1
a[a==255] = 1
b[b==255] = 1

max_peak = numpy.prod(b.shape)

# c will contain max_peak where the overlap is perfect
c = signal.correlate(a, b, 'valid')

overlaps = numpy.where(c == max_peak)

print overlaps

Это выводы(array([37]), array([84])), местоположения смещений, установленных в коде.

Скорее всего, вы обнаружите, что если размер вашей буквы, умноженный на размер вашего большого массива, больше, чем примерно Nlog (N), где N - соответствующий размер большого массива, в котором вы ищете (для каждого измерения), то вы, вероятно, получите ускорить с помощью алгоритма на основе FFT, какscipy.signal.fftconvolve (учитывая, что вам нужно будет перевернуть каждую ось одного из наборов данных, если вы используете свертку, а не корреляцию -flipud а такжеfliplr). Единственной модификацией было бы назначение c:

c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid')

Сравниваем сроки по размерам выше:

In [5]: timeit c = signal.fftconvolve(a, numpy.fliplr(numpy.flipud(b)), 'valid')
100 loops, best of 3: 6.78 ms per loop

In [6]: timeit c = signal.correlate(a, b, 'valid')
10 loops, best of 3: 151 ms per loop
Вау, отличный ответ (время даже)! У меня есть несколько тестов для запуска. DaveO
Что-то только что произошло со мной, вы можете не заботиться о нем. области вашей подматрицы, установив значение в 0. Это означает, что эти значения не будут влиять на взаимную корреляцию.max_peak значение может быть найдено какmax_peak = b[b!=0].size (это будет работать независимо от того, есть ли у вас 0 значений).
Обратите внимание, чтоflipud(fliplr(x)) это матлабизм --- вы можете написатьx[::-1, ::-1] вместо.
Итак, я провел день, редактируя свой код, и он заработал! Допустим, было найдено 2 вхождения формы 2х3 в (массив ([0, 6]), массив ([1, 7])), что означает верхние левые углы [0, 1] и [6, 7]. То, что я хочу сделать, - это иметь возможность индексировать все 2x3 ячейки фигуры и присваивать им 0, чтобы на следующей фигуре, которую мы ищем, мы не проверим эту часть изображения (согласно вашему комментарию выше). Как я могу использовать возвращаемое значение correlate / fftconvolve для индексации 2d фигуры без использования циклов? Сортировка среза списка местоположений. DaveO
Это то, что вы хотите сделать? Установка в ноль эквивалентна установке не заботы, что означает, что она, скорее всего, будет забрана. Также трудно установить max_peak, если вы устанавливаете нули в основном поисковом массиве. Если ваш подчиненный массив не содержит другого вложенного массива, у вас не возникнет проблем, и тогда наилучшим способом будет тщательно установить порядок поиска и, возможно, загрязнить данные (переключив 1 на -1 или наоборот), чтобы разбить в поисках будущих фигур. Переключение одного значения в смещении должно быть достаточно для обеспечения этого.

Похожие вопросы