madrid2i

Resumen

Method to calculate optimal correspondence between geometric patterns, comprising: - establish a binary constraint between two geometric entities belonging to the same geometric pattern, defining a metric between two geometric entities of the same pattern; - coding a graph of association g with vertices the cartesian product of the vertices of the model graphs (l 1 , l 2 ... ) and observation (o 1 , o 2 ... ) in an adjacency matrix a; being the matrix a a binary matrix where the value 1 of the element a ij of the matrix a represents that there is an edge between the nodes (x i , x j ) of the graph, and in which the coding of said matrix a is done by integer variables of size w size , where w size , the number of bits that has a cpu record in charge of performing the calculation; - apply a modified mcp algorithm that uses bit parallelism for the computation. (Machine-translation by Google Translate, not legally binding)

Reivindicaciones

1. 1. Método para calcular la correspondenciaóptima entre patrones geométricos, siendo dichos patronesgeométricos un modelo o referencia y una observación o muestra, caracterizado porque comprende: 2. - establecer una restricción binaria entre dosentidades geométricas pertenecientes al mismo patrón geométrico, yasean entidades geométricas del modelo (Li1, Li2, ...) o dela observación (Oj1, Oj2, ...) , mediante la definición deal menos una métrica m entre dos entidades geométricas del mismopatrón, m: ExE 3. \rightarrow 4. - codificar un grafo de asociación G que tienecomo vértices el producto cartesiano de los vértices de los grafosmodelo (L1, L2, ...) y observación (O1, O2, ...) en una matriz de adyacencias A; dicho grafo de asociación G seconstruye determinando las aristas entre nodos, correspondiendocada arista del grafo con la existencia de la compatibilidadbinaria entre las entidades que componen los nodos conectados ysiendo la matriz A una matriz binaria donde el valor 1 del elementoAij de la matriz A representa que existe una aristaentre los nodos (xi, xj) del grafo, siendodicho valor 0 en caso de que no exista arista y en el que lacodificación de dicha matriz A se hace mediante variables enterasde tamaño Wsize, siendo Wsize el número de bits que tieneel registro de la CPU encargada de realizar el cálculo de lacorrespondencia óptima entre patrones geométricos; 5. - aplicar un algoritmo MCP (Problema del MáximoClique) modificado que emplea el paralelismo de bits para elcómputo de las operaciones fundamentales de la búsqueda de formaeficiente. 6. 2. Método para calcular la correspondenciaóptima entre patrones geométricos según la reivindicación 1, caracterizado por el uso de paralelismo de bits que seaplica en las siguientes operaciones del algoritmo MCP: 7. - el cómputo del nuevo subgrafo a examinar apartir de la expansión de uno de los vértices del grafo actual; 8. - el cómputo de un umbral superioru (U) del tamaño del máximo clique para cadasubgrafo. 9. 3. Método para calcular la correspondenciaóptima entre patrones geométricos según la reivindicación 2, caracterizado porque en la operación del algoritmo MCPrelativa al cómputo del nuevo subgrafo a examinar a partir de laexpansión de uno de los vértices vk del grafo actual, dichonuevo subgrafo a examinar tras la expansión del vértice vkpuede computarse en el espacio de vectores de bits como: 10. 4. Método para calcular la correspondenciaóptima entre patrones geométricos según la reivindicación 2, caracterizado porque en la operación del algoritmo MCPrelativa al cómputo de un umbral superior u (U) deltamaño del máximo clique para cada subgrafo se emplea un algoritmode coloreado en el cual se efectúan dos operaciones medianteoperaciones de enmascaramiento de bits: 11. - sea Ak la fila k-ésima de lamatriz A y sea Q = (VQ, EQ) unsubgrafo cualquiera inducido de G a colorear, se calcula laexpresión Q ∩ N 12. \overline{G} 13. - sean BBU y BBCk losvectores de bits que codifican el conjuntó de vértices de U yCk respectivamente, U - Ck se calcula de lasiguiente forma:

Índice de la ficha

En detalle

Resumen

Reivindicaciones

Etiquetas