Базовое распознавание образов в двоичном (пикселированном) изображении

Question

Вот обрезанный пример (около 11x9 пикселей) типа изображений (которые в конечном итоге фактически имеют размер 28x28, но хранятся в памяти, уплощенной как массив 784 -компонентов), я буду пытатьсяприменить алгоритм к:

По сути, я хочу иметь возможность распознавать, когда появляется эта форма (красные линии используются для выделенияразделение пикселей, в то время как окружающая черная рамка используется для лучшего контурирования изображения на белом фоне StackOverflow):

Ориентация этогоне имеет значения: он должен быть обнаружен в любом из его возможных представлений (повороты и симметрии) вдоль горизонтальной и вертикальной оси (поэтому, например, не следует рассматривать поворот на 45 ° или диагональную симметрию: учитывайте только 90Например, повороты °, 180 ° и 270 °).

На этом изображении, которое я впервые представил, есть два решения, хотя нужно найти только одно.(игнорируйте серый размытие, окружающее белую область):

Возьмите этот другой образец (который также демонстрирует, что белые цифры внутри изображений невсегда полностью окружен черными пикселями):

Функция должна возвращать True , поскольку фигура присутствует:

Теперь, очевидно, существует простое решение этого вопроса:

Используйте переменную, например pattern = [[1,0,0,0],[1,1,1,1]], создайте ее варианты, а затем сдвиньтевсе вариации на изображении, пока не будет найдено точное соответствие, в этот момент все это просто останавливается и возвращает True.

Однако в худшем случае это может занять до 8*(28-2)*(28-4)*(2*4)это примерно 40000 операций для одного изображения, что кажется немного излишним (если я правильно сделал свои быстрые вычисления).

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

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

В качестве примечания, хотя вроде как взломать, я предполагаю, что это видпроблемы, которые могут быть выгружены в GPU, но у меня нет большого опыта с этим. Хотя это будет не то, что я ищу в первую очередь , если вы дадите ответ, не стесняйтесь добавить примечание, касающееся графического процессора.

Answer 1

Операция, которую вы реализуете, является оператором в математической морфологии, который называется hit and miss .

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

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

---

В качестве примера того, какой вывод ожидать, я сгенерировал простое тестовое изображение (слева), применил оператор удара и пропуска с шаблоном, который совпадает ровно в одном месте изображения (в центре), и снова с шаблоном, который нигде не соответствует (справа):

Я сделал это в MATLAB, а не в Python, потому что он у меня открыт и его проще всего использовать.Это код:

se = [1,1,1,1      % Defines the template
      0,0,0,1];
img = [0,0,0,0,0,0 % Defines the test image
       0,1,1,1,1,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];
img = dip_image(img,'bin');

res1 = hitmiss(img,se);
res2 = hitmiss(img,rot90(se,2));

% Quick-and-dirty display
h = dipshow([img,res1,res2]);
diptruesize(h,'tight',3000)
hold on
plot([5.5,5.5],[-0.5,5.5],'r-')
plot([11.5,11.5],[-0.5,5.5],'r-')

Приведенный выше код использует оператор удара и пропуска, как я реализовал в DIPimage .Эта же реализация доступна в Python в PyDIP как HitAndMiss (пока нет бинарной версии PyDIP, вам нужно скомпилировать ее самостоятельно):

import PyDIP as dip
# ...
res = dip.HitAndMiss(img, se)

Answer 2

Если у вас слишком много операций, подумайте, как выполнить их меньше.

Для этой задачи я бы использовал интегралы изображений.

Если вы сворачиваете суммирующее ядро ​​по образу (это очень быстрая операция в области fft только с conv2, imfilter), вы знаете, что только в тех местах, где интеграл равен 5 (вваш случай) возможны места сопоставления с образцом.Проверка их (даже для ваших 4 вращений) должна быть очень быстрой в вычислительном отношении.В вашем примере изображения не может быть более 50 мест, которые соответствуют этому шаблону.

Мой питон не слишком беглый, но это является доказательством концепции вашего первого изображения в MATLAB, я уверен, что перевод этогоКод не должен быть проблемой.

% get the same image you have (imgur upscaled it and made it RGB)
I=rgb2gray(imread('https://i.stack.imgur.com/l3u4A.png'));
I=imresize(I,[9 11]);
I=double(I>50);

% Integral filter definition (with your desired size)
h=ones(3,4);

% horizontal and vertical filter (because your filter is  not square)
Ifiltv=imfilter(I,h);
Ifilth=imfilter(I,h');
% find the locations where integral is exactly the value you want
[xh,yh]=find(Ifilth==5);
[xv,yv]=find(Ifiltv==5);

% this is just plotting, for completeness
figure()
imshow(I,[]);
hold on
plot(yh,xh,'r.');
plot(yv,xv,'r.');

В результате проверяется 14 мест.Мой стандартный компьютер в среднем потребляет 230 нс для вычисления обоих интегралов изображения, которые я бы назвал fast .

Кроме того, вычисления на GPUне взломать: D.Это способ справиться с большой кучей проблем из-за огромной вычислительной мощности, которую они имеют.Например, свертки в графических процессорах невероятно быстрые.