Contexto de forma

El contexto de forma es un descriptor de características que se utiliza en el reconocimiento de objetos . Serge Belongie y Jitendra Malik propusieron el término en su artículo "Matching with Shape Contexts" (Coincidencia con contextos de forma) en 2000. ^[1]

Teoría

El contexto de forma pretende ser una forma de describir formas que permita medir la similitud de formas y recuperar correspondencias de puntos. ^[1] La idea básica es elegir n puntos en los contornos de una forma. Para cada punto p _i en la forma, considere los n  − 1 vectores obtenidos al conectar p _i a todos los demás puntos. El conjunto de todos estos vectores es una descripción rica de la forma localizada en ese punto, pero es demasiado detallada. La idea clave es que la distribución sobre posiciones relativas es un descriptor robusto, compacto y altamente discriminativo. Entonces, para el punto p _i , el histograma grueso de las coordenadas relativas de los n  − 1 puntos restantes,

${\displaystyle h_{i}(k)=\#\{q\neq p_{i}:(q-p_{i})\in {\mbox{bin}}(k)\}}$

se define como el contexto de forma de . Normalmente, se considera que los contenedores son uniformes en el espacio log-polar. El hecho de que el contexto de forma sea un descriptor rico y discriminante se puede ver en la figura siguiente, en la que se muestran los contextos de forma de dos versiones diferentes de la letra "A". ${\displaystyle p_{i}}$

(a) y (b) son los puntos de los bordes muestreados de las dos formas. (c) es el diagrama de los contenedores log-polares utilizados para calcular el contexto de forma. (d) es el contexto de forma para el punto marcado con un círculo en (a), (e) es el del punto marcado como un diamante en (b) y (f) es el del triángulo. Como se puede ver, dado que (d) y (e) son los contextos de forma para dos puntos estrechamente relacionados, son bastante similares, mientras que el contexto de forma en (f) es muy diferente.

Para que un descriptor de características sea útil, debe tener ciertas invariancias. En particular, debe ser invariante a la traslación, el escalamiento, las pequeñas perturbaciones y, según la aplicación, la rotación. La invariancia traslacional surge naturalmente en el contexto de forma. La invariancia de escala se obtiene normalizando todas las distancias radiales por la distancia media entre todos los pares de puntos en la forma ^{[2] [3]} aunque también se puede utilizar la distancia mediana. ^{[1] [4]} Se ha demostrado empíricamente que los contextos de forma son robustos a las deformaciones, el ruido y los valores atípicos ^[4] mediante experimentos de coincidencia de conjuntos de puntos sintéticos. ^[5] ${\displaystyle \alpha }$

Se puede proporcionar una invariancia rotacional completa en contextos de forma. Una forma es medir los ángulos en cada punto en relación con la dirección de la tangente en ese punto (ya que los puntos se eligen en los bordes). Esto da como resultado un descriptor completamente invariante en cuanto a la rotación. Pero, por supuesto, esto no siempre es lo deseado, ya que algunas características locales pierden su poder discriminatorio si no se miden en relación con el mismo marco. De hecho, muchas aplicaciones prohíben la invariancia rotacional, por ejemplo, distinguir un "6" de un "9".

Uso en combinación de formas

Un sistema completo que utiliza contextos de formas para la coincidencia de formas consta de los siguientes pasos (que se tratarán con más detalle en la sección Detalles de implementación):

1. Seleccione aleatoriamente un conjunto de puntos que se encuentren en los bordes de una forma conocida y otro conjunto de puntos en una forma desconocida.
2. Calcule el contexto de forma de cada punto encontrado en el paso 1.
3. Haga coincidir cada punto de la forma conocida con un punto de una forma desconocida. Para minimizar el costo de la coincidencia, primero elija una transformación (por ejemplo, afín , spline de placa delgada , etc.) que deforme los bordes de la forma conocida con los desconocidos (básicamente, alineando las dos formas). Luego, seleccione el punto de la forma desconocida que corresponda más estrechamente a cada punto deformado de la forma conocida.
4. Calcula la "distancia de forma" entre cada par de puntos de las dos formas. Utiliza una suma ponderada de la distancia del contexto de la forma, la distancia de apariencia de la imagen y la energía de curvatura (una medida de cuánta transformación se requiere para alinear las dos formas).
5. Para identificar la forma desconocida, utilice un clasificador de vecino más cercano para comparar su distancia de forma con las distancias de forma de objetos conocidos.

Detalles de implementación

Paso 1: Encontrar una lista de puntos en los bordes de la forma

El enfoque supone que la forma de un objeto se captura esencialmente mediante un subconjunto finito de los puntos en los contornos internos o externos del objeto. Estos se pueden obtener simplemente utilizando el detector de bordes Canny y eligiendo un conjunto aleatorio de puntos de los bordes. Tenga en cuenta que estos puntos no necesitan corresponder, y en general no corresponden, a puntos clave como los máximos de curvatura o puntos de inflexión . Es preferible tomar muestras de la forma con un espaciado aproximadamente uniforme, aunque no es crítico. ^[2]

Paso 2: Calcular el contexto de forma

Este paso se describe en detalle en la sección Teoría.

Paso 3: Cálculo de la matriz de costos

Consideremos dos puntos p y q que tienen histogramas de K -bin normalizados (es decir, contextos de forma) g ( k ) y h ( k ). Como los contextos de forma son distribuciones representadas como histogramas, es natural utilizar la estadística de prueba χ 2 como el "costo del contexto de forma" de hacer coincidir los dos puntos:

${\displaystyle C_{S}={\frac {1}{2}}\sum _{k=1}^{K}{\frac {[g(k)-h(k)]^{2}}{g(k)+h(k)}}}$

Los valores de este rango van de 0 a 1. ^[1] Además del costo del contexto de forma, se puede agregar un costo adicional basado en la apariencia. Por ejemplo, podría ser una medida de disimilitud de ángulos tangentes (particularmente útil en el reconocimiento de dígitos):

${\displaystyle C_{A}={\frac {1}{2}}{\begin{Vmatrix}{\dbinom {\cos(\theta _{1})}{\sin(\theta _{1})}}-{\dbinom {\cos(\theta _{2})}{\sin(\theta _{2})}}\end{Vmatrix}}}$

Esta es la mitad de la longitud de la cuerda en el círculo unitario entre los vectores unitarios con ángulos y . Sus valores también varían de 0 a 1. Ahora bien, el costo total de hacer coincidir los dos puntos podría ser una suma ponderada de los dos costos: ${\displaystyle \theta _{1}}$ ${\displaystyle \theta _{2}}$

${\displaystyle C=(1-\beta )C_{S}+\beta C_{A}\!\,}$

Ahora, para cada punto p _i de la primera figura y un punto q _j de la segunda figura, calcula el costo como se describe y llámalo C _{i , j} . Esta es la matriz de costos.

Paso 4: Encontrar la combinación que minimice el costo total

Resultados de la comparación

Ahora, una correspondencia uno a uno que hace coincidir cada punto p _i en la forma 1 y q _j en la forma 2 que minimiza el costo total de correspondencia, ${\displaystyle \pi (i)}$

${\displaystyle H(\pi )=\sum _{i}C\left(p_{i},q_{\pi (i)}\right)}$

es necesario. Esto se puede hacer a tiempo utilizando el método húngaro , aunque hay algoritmos más eficientes. ^[6] Para tener un manejo robusto de los valores atípicos, se pueden agregar nodos "ficticios" que tengan un costo de coincidencia constante pero razonablemente grande a la matriz de costos. Esto haría que el algoritmo de coincidencia coincida con los valores atípicos con un "ficticio" si no hay una coincidencia real. ${\displaystyle O(N^{3})}$

Paso 5: Modelado de la transformación

Dado el conjunto de correspondencias entre un conjunto finito de puntos de las dos formas, se puede estimar una transformación para mapear cualquier punto de una forma a la otra. Hay varias opciones para esta transformación, que se describen a continuación. ${\displaystyle T:\mathbb {R} ^{2}\to \mathbb {R} ^{2}}$

Afín

El modelo afín es una opción estándar: . La solución de mínimos cuadrados para la matriz y el vector de desplazamiento traslacional o se obtiene mediante: ${\displaystyle T(p)=Ap+o\!}$ ${\displaystyle A}$

${\displaystyle o={\frac {1}{n}}\sum _{i=1}^{n}\left(p_{i}-q_{\pi (i)}\right),A=(Q^{+}P)^{t}}$

Donde con una expresión similar para . es la pseudoinversa de . ${\displaystyle P={\begin{pmatrix}1&p_{11}&p_{12}\\\vdots &\vdots &\vdots \\1&p_{n1}&p_{n2}\end{pmatrix}}}$ ${\displaystyle Q\!}$ ${\displaystyle Q^{+}\!}$ ${\displaystyle Q\!}$

Estría de placa delgada

El modelo de spline de placa delgada (TPS) es el modelo más utilizado para las transformaciones cuando se trabaja con contextos de forma. Una transformación 2D se puede separar en dos funciones TPS para modelar una transformación de coordenadas:

${\displaystyle T(x,y)=\left(f_{x}(x,y),f_{y}(x,y)\right)}$

donde cada una de las ƒ _x y ƒ _y tienen la forma:

${\displaystyle f(x,y)=a_{1}+a_{x}x+a_{y}y+\sum _{i=1}^{n}\omega _{i}U\left({\begin{Vmatrix}(x_{i},y_{i})-(x,y)\end{Vmatrix}}\right),}$

y la función kernel está definida por . Los detalles exactos de cómo resolver los parámetros se pueden encontrar en otra parte ^{[7] [8]} pero esencialmente implica resolver un sistema lineal de ecuaciones . La energía de flexión (una medida de cuánta transformación se necesita para alinear los puntos) también se obtendrá fácilmente. ${\displaystyle U(r)\!}$ ${\displaystyle U(r)=r^{2}\log r^{2}\!}$

TPS regularizado

La formulación TPS anterior tiene un requisito de coincidencia exacta para los pares de puntos en las dos formas. Para datos ruidosos, es mejor relajar este requisito exacto. Si dejamos que denotemos los valores de la función objetivo en las ubicaciones correspondientes (nótese que para , sería la coordenada x del punto correspondiente a y para sería la coordenada y, ), relajar el requisito equivale a minimizar ${\displaystyle v_{i}}$ ${\displaystyle p_{i}=(x_{i},y_{i})}$ ${\displaystyle f_{x}}$ ${\displaystyle v_{i}}$ ${\displaystyle x'}$ ${\displaystyle p_{i}}$ ${\displaystyle f_{y}}$ ${\displaystyle y'}$

${\displaystyle H[f]=\sum _{i=1}^{n}(v_{i}-f(x_{i},y_{i}))^{2}+\lambda I_{f}}$

donde es la energía de flexión y se denomina parámetro de regularización. Este ƒ que minimiza H [ ƒ ] se puede encontrar de una manera bastante sencilla. ^[9] Si se utilizan coordenadas normalizadas para , se mantiene la invariancia de escala. Sin embargo, si se utilizan las coordenadas originales no normalizadas, entonces es necesario normalizar el parámetro de regularización. ${\displaystyle I_{f}\!}$ ${\displaystyle \lambda \!}$ ${\displaystyle (x_{i},y_{i}){\mbox{ and }}(x'_{i},y'_{i})}$

Tenga en cuenta que en muchos casos, independientemente de la transformación utilizada, la estimación inicial de las correspondencias contiene algunos errores que podrían reducir la calidad de la transformación. Si iteramos los pasos de búsqueda de correspondencias y estimación de transformaciones (es decir, repitiendo los pasos 2 a 5 con la forma recién transformada), podemos superar este problema. Por lo general, tres iteraciones son todo lo que se necesita para obtener resultados razonables.

Paso 6: Calcular la distancia de la forma

Ahora, una distancia de forma entre dos formas y . Esta distancia será una suma ponderada de tres términos potenciales: ${\displaystyle P\!}$ ${\displaystyle Q\!}$

Distancia del contexto de forma : es la suma simétrica de los costos de coincidencia del contexto de forma sobre los mejores puntos de coincidencia:

${\displaystyle D_{sc}(P,Q)={\frac {1}{n}}\sum _{p\in P}\arg {\underset {q\in Q}{\min }}C(p,T(q))+{\frac {1}{m}}\sum _{q\in Q}\arg {\underset {p\in P}{\min }}C(p,T(q))}$

donde T (·) es la transformada TPS estimada que asigna los puntos en Q a aquellos en P.

Costo de apariencia : después de establecer correspondencias de imágenes y deformar adecuadamente una imagen para que coincida con la otra, se puede definir un costo de apariencia como la suma de las diferencias de brillo al cuadrado en las ventanas gaussianas alrededor de los puntos de imagen correspondientes:

${\displaystyle D_{ac}(P,Q)={\frac {1}{n}}\sum _{i=1}^{n}\sum _{\Delta \in Z^{2}}G(\Delta )\left[I_{P}(p_{i}+\Delta )-I_{Q}(T(q_{\pi (i)})+\Delta )\right]^{2}}$

donde y son las imágenes en nivel de gris ( es la imagen después de la deformación) y es una función de ventana gaussiana. ${\displaystyle I_{P}\!}$ ${\displaystyle I_{Q}\!}$ ${\displaystyle I_{Q}\!}$ ${\displaystyle G\!}$

Costo de transformación : el costo final mide cuánta transformación es necesaria para alinear las dos imágenes. En el caso de TPS, se le asigna la energía de flexión. ${\displaystyle D_{be}(P,Q)\!\,}$

Ahora que tenemos una forma de calcular la distancia entre dos formas, podemos utilizar un clasificador de vecino más próximo (k-NN) con la distancia definida como la distancia entre formas calculada aquí. Los resultados de aplicar esto a diferentes situaciones se muestran en la siguiente sección.

Resultados

Reconocimiento de dígitos

Los autores Serge Belongie y Jitendra Malik probaron su enfoque en la base de datos MNIST . Actualmente, se han probado más de 50 algoritmos en la base de datos. La base de datos tiene un conjunto de entrenamiento de 60.000 ejemplos y un conjunto de prueba de 10.000 ejemplos. La tasa de error para este enfoque fue del 0,63 % utilizando 20.000 ejemplos de entrenamiento y 3-NN. En el momento de la publicación, esta tasa de error era la más baja. Actualmente, la tasa de error más baja es del 0,18 %. ^[10]

Recuperación basada en similitud de siluetas

Los autores experimentaron con la base de datos de siluetas de formas MPEG-7, realizando el experimento básico CE-Shape-1 parte B, que mide el rendimiento de la recuperación basada en similitud. ^[11] La base de datos tiene 70 categorías de formas y 20 imágenes por categoría de forma. El rendimiento de un esquema de recuperación se prueba utilizando cada imagen como una consulta y contando el número de imágenes correctas en las 40 coincidencias principales. Para este experimento, los autores aumentaron el número de puntos muestreados de cada forma. Además, dado que las formas en la base de datos a veces se rotaban o volteaban, los autores definieron la distancia entre una forma de referencia y la forma de consulta como la distancia de forma mínima entre la forma de consulta y la referencia sin cambios, la volteada verticalmente o la referencia volteada horizontalmente. ^{[1] [2] [3] [4]} Con estos cambios, obtuvieron una tasa de recuperación del 76,45%, que en 2002 fue la mejor.

Reconocimiento de objetos 3D

El siguiente experimento realizado sobre contextos de forma involucró los 20 objetos domésticos comunes en la Biblioteca de imágenes de objetos de Columbia (COIL-20). Cada objeto tiene 72 vistas en la base de datos. En el experimento, el método se entrenó en una cantidad de vistas espaciadas de manera uniforme para cada objeto y las vistas restantes se usaron para realizar pruebas. Se utilizó un clasificador 1-NN. Los autores también desarrollaron un algoritmo de edición basado en la similitud del contexto de forma y la agrupación en grupos de k-medoides que mejoró su rendimiento. ^[4]

Recuperación de marca registrada

Se utilizaron contextos de forma para recuperar las marcas comerciales más similares a una marca registrada consultada en una base de datos (útil para detectar infracciones de marca registrada). El algoritmo no pasó por alto ninguna marca comercial visualmente similar (verificado manualmente por los autores). ^[2]

Enlaces externos

• Correspondencia con contextos de formas
• Base de datos de dígitos escritos a mano del MNIST
• Biblioteca de imágenes de objetos de Columbia (COIL-20)
• Base de datos Caltech101

Referencias

1. S. Belongie y J. Malik (2000). "Coincidencia con contextos de forma". Taller IEEE sobre acceso basado en contenido a bibliotecas de imágenes y vídeos (CBAIVL-2000) . doi :10.1109/IVL.2000.853834.
2. S. Belongie; J. Malik y J. Puzicha (abril de 2002). "Coincidencia de formas y reconocimiento de objetos mediante contextos de forma" (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 24 (4): 509–521. doi :10.1109/34.993558. S2CID  129468.
3. S. Belongie; J. Malik y J. Puzicha (julio de 2001). "Matching Shapes" (PDF) . Octava Conferencia Internacional IEEE sobre Visión por Computador (julio de 2001) .
4. S. Belongie; J. Malik y J. Puzicha (2000). "Contexto de forma: un nuevo descriptor para la correspondencia de formas y el reconocimiento de objetos" (PDF) . NIPS 2000 .
5. H. Chui y A. Rangarajan (junio de 2000). "Un nuevo algoritmo para la correspondencia de puntos no rígidos". CVPR . Vol. 2. págs. 44–51. doi :10.1109/CVPR.2000.854733.
6. R. Jonker y A. Volgenant (1987). "Un algoritmo de ruta de aumento más corta para problemas de asignación lineal densos y dispersos". Computing . 38 (4): 325–340. doi :10.1007/BF02278710. S2CID  7806079.
7. MJD Powell (1995). "Un método de spline de placa delgada para mapear curvas en curvas en dos dimensiones". Técnicas computacionales y aplicaciones (CTAC '95) . doi :10.1142/9789814530651.
8. J. Duchon (1977). "Splines que minimizan seminormas invariantes a la rotación en espacios de Sobolev". Teoría constructiva de funciones de varias variables . Apuntes de clase en matemáticas. Vol. 571. págs. 85-100. doi :10.1007/BFb0086566. ISBN. 978-3-540-08069-5.
9. G. Wahba (1990). Modelos spline para datos observacionales . Soc. Industrial and Applied Math. ISBN 9780898712445.
10. Kowsari, Kamran; Heidarysafa, Mojtaba; Brown, Donald E.; Meimandi, Kiana Jafari; Barnes, Laura E. (3 de mayo de 2018). "RMDL: aprendizaje profundo multimodelo aleatorio para clasificación". Actas de la 2.ª Conferencia internacional sobre sistemas de información y minería de datos . págs. 19–28. arXiv : 1805.01890 . Código Bibliográfico :2018arXiv180501890K. doi :10.1145/3206098.3206111. ISBN . 9781450363549.S2CID19208611  .​
11. S. Jeannin y M. Bober (marzo de 1999). "Descripción de los experimentos básicos para el movimiento y la forma de MPEG-7. Informe técnico ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Seúl". {{cite journal}}: Requiere citar revista |journal=( ayuda )