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.