La forma más rápida de encontrar una submatriz m x n en la matriz M X N

Estaba pensando en un método rápido para buscar una submatriz m en una matriz más grande. También necesito identificar coincidencias parciales.

Un par de enfoques que podría pensar son:

Optimice la fuerza bruta normal para procesar solo filas y columnas incrementales.Puede extenderse el algoritmo de Rabin-karp a 2-d pero no está seguro de cómo manejar las coincidencias parciales con él.

Creo que este es un problema bastante frecuente en el procesamiento de imágenes y apreciaría si alguien pudiera verter sus aportaciones o señalarme recursos / documentos sobre este tema.

EDITAR: Ejemplo más pequeño:

Matriz más grande:
1 2 3 4 5
4 5 6 7 8
9 7 6 5 2

Matriz más pequeña:
7 8
5 2

Resultado: (fila: 1 col: 3)

Un ejemplo de matriz más pequeña que califica como una coincidencia parcial en (1, 3):
7 9
5 2

Si más de la mitad de los píxeles coinciden, entonces se toma como coincidencia parcial.

Gracias.

Respuestas a la pregunta(4)

Su respuesta a la pregunta