Самый быстрый способ найти подматрицу 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

Если более половины пикселей совпадают, то это принимается как частичное совпадение.

Благодарю.

 gaussblurinc10 мая 2012 г., 10:22
добавить условие для ваших подматриц? пожалуйста
 amit10 мая 2012 г., 10:04
Каким ограничениям должна подчиняться меньшая матрица? Если ничего не существует - просто возьмите первую подматрицу m x n, ...
 knowledgeSeeker10 мая 2012 г., 12:01
добавил условие для подматриц.
 knowledgeSeeker10 мая 2012 г., 12:37
Я добавил несколько примеров. Вопрос должен быть довольно ясным.
 harold10 мая 2012 г., 12:03
Это не ограничение. Тогда возьмите верхний левый квадрат.

Ответы на вопрос(4)

если вы хотите предварительно обработать матрицу и если у вас много запросов на одну и ту же матрицу.

Посмотрите на статьи по алгебраическим базам данных исследовательской группой по мультимедийным базам данных (проф. Клаузен, Боннский университет). Посмотрите на этот документ, например:http: //www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pd

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

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

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

Редактироват:

Эта идея также работает с частичными совпадениями, если вы правильно их определили.

 Michael Foukarakis01 июн. 2016 г., 18:25
К сожалению, ссылка сейчас не работает. Есть ли шанс обновить его или включить его название для дальнейшего использования?

алгоритмы сопоставления с образцом 2d". Вы получите много результатов. Я просто свяжу первый хит в Google,бумаг который представляет алгоритм для вашей проблемы.

Вы также можете посмотреть цитаты в конце статьи, чтобы получить представление о других существующих алгоритмах.

Аннотация:

Представлен алгоритм поиска двумерного шаблона m x m в двумерном тексте n x n. Он выполняет в среднем меньше сравнений, чем размер текста: n ^ 2 / m, используя m ^ 2 дополнительного пространства. По сути, он использует сопоставление нескольких строк только для n / m строк текста. Это работает не более 2n ^ 2 времени и близко к оптимальному n ^ 2 времени для многих паттернов. Он постоянно распространяется на алфавитно-независимый алгоритм с похожим наихудшим случаем. Экспериментальные результаты включены для практической версии.

что вы не можете просто догадаться, где находится подматрица с некоторым подходом, но вы можете оптимизировать свой поиск.

Например, для матрицы A MxN и подматрицы B mxn вы можете сделать так:

SearchSubMatrix (Matrix A, Matrix B)

answer = (-1, -1)

Loop1:
for i = 0 ... (M-m-1)
|
|   for j = 0 ... (N-n-1)
|   | 
|   |   bool found = true
|   |
|   |   if A[i][j] = B[0][0] then
|   |   |
|   |   |   Loop2:
|   |   |   for r = 0 ... (m-1)
|   |   |   |   for s = 0 ... (n-1)
|   |   |   |   |   if B[r][s] != A[r+i][s+j] then
|   |   |   |   |   |   found = false
|   |   |   |   |   |   break Loop2
|   |
|   |   if found then
|   |   |   answer = (i, j)
|   |   |   break Loop1
|
return answer

Делая это, вы уменьшите ваш поиск по причине размера подматрицы.

Matrix         Submatrix         Worst Case:
1 2 3 4           2 4            [1][2][3] 4
4 3 2 1           3 2            [4][3][2] 1
1 3 2 4                          [1][3]{2  4}
4 1 3 2                           4  1 {3  2}

                                 (M-m+1)(N-n+1) = (4-2+1)(4-2+1) = 9

Хотя этоO(M*N), это никогда не будет выглядетьM*N раз, если ваша подматрица не имеет только 1 измерение.

если вам когда-нибудь нужно будет сопоставить одну маленькую матрицу с одной большой матрицей. Но если вам нужно сделать много маленьких матриц для больших матриц, то предварительно обработайте большую матрицу.

Простой пример, точное совпадение, множество матриц 3х3 против одной гигантской матрицы.

Создайте новую «матрицу соответствия», такого же размера, как и «большая матрица». Для каждого местоположения в большой матрице вычислите хэш 3x3 для каждого x, y - x + 3, y + 3 в большой матрице. Теперь вы просто сканируете матрицу совпадений на предмет совпадения хэшей.

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

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

Решение 3x3 будет работать для любой тестовой матрицы 3x3 или более. Вам не нужно иметь идеальный метод хеширования - вам просто нужно что-то, что отклонит большинство неудачных совпадений, а затем выполнит полное совпадение для потенциальных совпадений в хеш-таблице.

Ваш ответ на вопрос