c++ - inverse matrix in c

La forma más rápida de encontrar la submatriz amxn en la matriz de MXN

Question

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:

1. Optimice la fuerza bruta normal para procesar solo filas y columnas incrementales.
2. 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.

Answer 1

Creo que no puedes adivinar dónde está la submatriz con algún enfoque, sino que puedes optimizar tu búsqueda.

Por ejemplo, dada una matriz A MxN y una submatriz B mxn, puede hacer lo siguiente:

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

Al hacer esto, reducirá su búsqueda en la razón del tamaño de la submatriz.

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

Aunque esto es O(M*N) , nunca se verá M*N veces, a menos que su submatriz tenga solo 1 dimensión.

Answer 2

Hay algoritmos muy rápidos para esto si está dispuesto a preprocesar la matriz y si tiene muchas consultas para la misma matriz.

Eche un vistazo a los documentos sobre bases de datos algebraicos del grupo de investigación sobre bases de datos multimedia (Prof. Clausen, Universidad de Bonn). Eche un vistazo a este documento, por ejemplo: http://www-mmdb.iai.uni-bonn.de/download/publications/sigir-03.pdf

La idea básica es generalizar la lista invertida, de modo que utilicen cualquier tipo de transformación algebraica, en lugar de solo desplazamientos en una dirección como ocurre con las listas invertidas ordinarias.

Esto significa que este enfoque funciona siempre que las modificaciones que necesite hacer a los datos de entrada se puedan modelar algebraicamente. Esto específicamente que se pueden recuperar las consultas que se traducen en cualquier número de dimensiones, rotado, volteado, etc.

El documento muestra principalmente esto para datos musicales, ya que este es su principal interés de investigación, pero es posible que pueda encontrar otros, que muestren cómo adaptar esto a los datos de imagen también (o puede intentar adaptarlo usted mismo, si lo desea). entender el principio es bastante simple).

Editar :

Esta idea también funciona con coincidencias parciales, si las define correctamente.

Answer 3

No hay manera de hacer esto rápido si solo necesita hacer coincidir una matriz pequeña con una matriz grande. Pero si necesita hacer muchas matrices pequeñas contra matrices grandes, preprocesar la matriz grande.

Un ejemplo simple, coincidencia exacta, muchas matrices 3x3 contra una matriz gigante.

Cree una nueva "matriz de coincidencia", del mismo tamaño que "matriz grande". Para cada ubicación en matriz grande, calcule un hash 3x3 para cada x, y a x + 3, y + 3 en matriz grande. Ahora simplemente escanea la matriz de coincidencias para los hashes coincidentes.

Puede lograr coincidencias parciales con funciones hash especializadas que le dan el mismo hash a las cosas que tienen las mismas propiedades parciales parciales. Difícil.

Si desea acelerar más y tener memoria para ello, cree una tabla hash para la matriz de coincidencia y busque los hashes en la tabla hash.

La solución 3x3 funcionará para cualquier matriz de prueba 3x3 o mayor. No es necesario que tenga un método hash perfecto; solo necesita algo que rechace la mayoría de las coincidencias incorrectas y luego realice una coincidencia completa para las posibles coincidencias en la tabla hash.

Answer 4

Recomiendo hacer una búsqueda en internet sobre "algoritmos de coincidencia de patrones 2d". Obtendrá un montón de resultados. Solo enlazaré el primer hit en Google, un artículo que presenta un algoritmo para su problema.

También puede echar un vistazo a las citas al final del documento para tener una idea de otros algoritmos existentes.

El abstracto:

Se presenta un algoritmo para buscar un patrón mxm bidimensional en un texto nxn bidimensional. Realiza en promedio menos comparaciones que el tamaño del texto: n ^ 2 / m usando m ^ 2 espacio extra. Básicamente, utiliza la coincidencia de varias cadenas en solo n / m filas del texto. Se ejecuta a lo sumo en el tiempo 2n ^ 2 y está cerca del tiempo n ^ 2 óptimo para muchos patrones. Se extiende constantemente a un algoritmo independiente del alfabeto con un peor caso similar. Se incluyen resultados experimentales para una versión práctica.