выровнять 2 матрицы для максимального перекрытия

Question

Итак, следующая проблема - собеседование.

Даны две N ² матрицы с записями 0 или 1. Как мы можем узнать число максимально возможных перекрытий 1?

Примечание: Вы можете перемещать матрицу только вверх, вниз, влево и вправо, поэтому вращение не допускается

В настоящее время я застрял на самом наивном методе O(N^4), который заключается в выравнивании верхнего левого угла одной матрицы с каждой возможной позицией другой матрицы и подсчете всех перекрывающихся единиц.

* * Пример тысячи двадцать-одина * +1022 *: * +1023 *

   [0 1 0]      [0 0 1]
A: [1 0 0]   B: [0 0 1]
   [1 0 0]      [0 0 0]

Тогда число максимально перекрывающихся 1-х равно 2 , что мы высветим (0,2) от B до (1,0) от A, тогда (0,2) и (1,0) равны 1, а (1,2) и (2,0) равны 1.

Можно ли оптимизировать от O (N ⁴ ) ?

Answer 1

Если арифметические вычисления с плавающей точкой возможны, эта проблема может быть решена с помощью 2D взаимной корреляции (с использованием быстрого преобразования Фурье) за O(n^2 logn) времени. Этот метод используется при поиске двумерных образов.

Не совсем очевидный совет: для реализации корреляции и получения правильных результатов необходимо сдвинуть значения, чтобы сделать "сигналы" биполярными (преобразовать нули в -1 или вычесть среднее значение матрицы из всех элементов матрицы)

Рассчитать матрицу корреляции, найти индекс (dx,dy) максимального значения - он должен соответствовать вектору выравнивания.