Как найти определенную «фигуру» в двумерном массиве?

Question

[orellero]

Привет!
Есть двумерный массив типа такого:

var matrix = new Array(
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
);

Требуется искать определенные "фигуры" внутри массива, например найти

[0, 0],
[0, 0]

или

[0],
[0],
[0, 0, 0]

Подскажите, возможно есть какие либо готовые алгоритмы для такого поиска?

Comments

[orellero]

Всем спасибо за ответы!

Средний размер поля 50x50, может доходить до 200x200
Средний размер элемента 5 клеток, максимально 9
Ищутся именно нули.
Разных фигур около 20.

[Mrrl]

Какие габариты у искомых фигур? Они вписываются в квадрат 3*3?

[orellero]

Mrrl: нет, не вписываются, но максимальная сторона 6 клеток

Answer 1

[Андрей]

Слишком мало входных данных:
- каков средний/максимальный размер поля;
- каков средний/максимальный размер искомого элемента;
- что является инвариантным между событиями поиска: поле, искомый элемент или ни то и ни другое.

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

Comments

[Андрей]

P.S. Искомый элемент всегда заполнен только "нулями" ?

Answer 2

[Mrrl]

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

Answer 3

[Армянское Радио]

Каскады Хаара к вашим услугам.

Comments

[Игорь Ермолаев]

Достаточно спорный совет. Для каждой фигуры потребуется длительный процесс обучения HAAR- каскадов. Я думаю, что в простейшем случае достаточно простого попиксельного сравнения. Или какой-нибудь корреляционный метод, если вдруг возможны небольшие отличия.

[orellero]

Я не планирую сравнивать изображения. Нужно что-то простое и быстрое. Искать буду именно в массиве нулей и единичек. Разных фигур не очень много ~20

[Eddy_Em]

В данном случае самым простым решением будет инвертировать, свернуть и искать значения 4 для первого и 5 для второго случая.

Answer 4

[SeptiM]

Я бы искал эти паттерны как подстроки. Строим доп. массив по тому, где встречаются два и три нуля в строке, два и три нуля в столбце. Потом ищем где они образуют фигуры. Можно в лоб написать, можно КМП использовать.

Answer 5

[dtestyk]

hit or miss transform
image processing/feature extraction/template matching
feature_detection

есть нечто похожее для библиотеки aforge c#, может почерпнете какие-нибудь идеи там

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

решения в лоб:
-ходим фигурой(и, возможно, маской) по массиву:
4 цикла: 2 по координатам и 2 по фигуре
-ходим базовой точкой и массивом относительных смещений и значений:
3 цикла: 2 по координатам и 1 по точкам