Алгоритмы поиска двумерных паттернов

Question

Мне нужно узнать об алгоритмах поиска 2D-паттернов.Советы и ссылки с благодарностью.

Более точно:

Приведена матрица M [m, n] со значениями в K
пример

000000000000
000001000000
010 1 00010010 = M, K = {0, 1}
010 1 00010001
101 11 1010111

и матрица L [i, j] со значениями в K + {X}, представляющих «форму»
пример, форму буквы «L»

1 X
1 X = L
11

Какие алгоритмы могут ответить на следующие вопросы:

1. Можно ли L найти в M?
2. Сколько раз L можно найти в M (дизъюнктивных L's, нет общих фигур (1 или 0))
3. Сколько раз L можно найти в M (может иметь общие части (1 или 0))
4. Сколько раз L и K (K определяется аналогично тому, как L, K! = L) можно найти в M (дизъюнкт) и т. Д.

Язык реализации должен быть JavaScript, но подойдет любой другой.

РЕДАКТИРОВАТЬ Также найдено этот PDF .

Answer 1

Взгляните на эту презентацию , она должна дать вам базовые знания.

Символ X можно трактовать как подстановочный знак, поэтому он всегда будет совпадать.

Не знаю, что именно вы подразумеваете под

Сколько раз L и K (K определяется как L) можно найти в M (непересекающихся) и т. Д.

K обозначает алфавит или форму (например, L)?

Задача определения максимального количества непересекающихся совпадений будет сложнее. Подход будет следующим:

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

РЕДАКТИРОВАТЬ: Если ваша форма L, совпадение может быть эффективно рассчитано. Создайте таблицы для столбцов и строк и для каждой ячейки проверьте, если есть совпадение вверх и вправо.