Eu estava pensando em um método rápido para procurar uma submatriz m em um mtrix maior M. Eu também preciso identificar correspondências parciais.

Algumas abordagens que consegui pensar são:

Otimize a força bruta normal para processar apenas linhas e colunas incrementais.Pode ser estender o algoritmo de Rabin-karp para 2-d, mas não tenho certeza de como lidar com correspondências parciais com ele.

Acredito que isso seja um problema frequentemente encontrado no processamento de imagens e apreciaria se alguém pudesse fornecer seus dados ou me indicar recursos / artigos sobre esse assunto.

EDITAR: Exemplo menor:

Matriz maior:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2

Matriz Menor:
7 8
5 2

Resultado: (linha: 1 col: 3)

Um exemplo de matriz Menor que se qualifica como uma correspondência parcial em (1, 3):
7 9
5 2

Se mais da metade dos pixels corresponder, será considerado como correspondência parcial.

Obrigado.