Самый быстрый способ найти подматрицу m x n в матрице M X N
Я думал о быстром способе поиска подматрицы m в большей mtrix M. Мне также нужно определить частичные совпадения.
Вот несколько подходов, о которых я мог подумать:
Optimize the normal bruteforce to process only incremental rows and columns. May be extend Rabin-karp algorithm to 2-d but not sure how to handle partial matches with it.Я считаю, что это довольно часто встречающаяся проблема при обработке изображений, и был бы признателен, если бы кто-то мог высказать свое мнение или указать мне ресурсы / статьи на эту тему.
EDIT: Smaller example:
Большая матрица:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2
Меньшая матрица:
7 8
5 2
Результат: (строка: 1 столбец: 3)
Пример меньшей матрицы, которая квалифицируется как частичное совпадение в (1, 3):
7 9
5 2
Если более половины пикселей совпадают, то это принимается как частичное совпадение.
Благодарю.