Contexto de forma

El contexto de forma es un descriptor de características utilizado en el reconocimiento de objetos . Serge Belongie y Jitendra Malik propusieron el término en su artículo "Matching with Shape Contexts" 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 con todos los demás puntos. El conjunto de todos estos vectores es una rica descripción de la forma localizada en ese punto, pero es demasiado detallada. La idea clave es que la distribución entre posiciones relativas es un descriptor robusto, compacto y altamente discriminativo. Entonces, para el punto p _i , el histograma aproximado 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 logarítmico-polar. El hecho de que el contexto de forma sea un descriptor rico y discriminativo se puede ver en la siguiente figura, 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 borde 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 puede verse, 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ística sea útil, debe tener ciertas invariancias. En particular, debe ser invariante ante la traslación, el escalado, las pequeñas perturbaciones y, según la aplicación, la rotación. La invariancia traslacional es algo natural para dar forma al contexto. 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 formas son robustos a las deformaciones, el ruido y los valores atípicos ^[4] utilizando 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 ángulos en cada punto con respecto a la dirección de la tangente en ese punto (ya que los puntos se eligen en aristas). Esto da como resultado un descriptor completamente invariante rotacional. Pero, por supuesto, esto no siempre es deseado, ya que algunas características locales pierden su poder discriminativo 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".

Usar en combinación de formas

Un sistema completo que utiliza contextos de formas para hacer coincidir 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 encuentran 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. Relaciona cada punto de la forma conocida con un punto de una forma desconocida. Para minimizar el costo de hacer coincidir, primero elija una transformación (por ejemplo , afín , placa delgada , etc.) que deforme los bordes de la forma conocida a la desconocida (esencialmente alineando las dos formas). Luego seleccione el punto de la forma desconocida que más se corresponda con cada punto deformado de la forma conocida.
4. Calcule la "distancia de forma" entre cada par de puntos en las dos formas. Utilice una suma ponderada de la distancia del contexto de la forma, la distancia de apariencia de la imagen y la energía de flexión (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 la distancia de su 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 es esencialmente capturada por un subconjunto finito de puntos en los contornos internos o externos del objeto. Estos se pueden obtener simplemente usando el detector de bordes Canny y seleccionando un conjunto aleatorio de puntos de los bordes. Tenga en cuenta que estos puntos no tienen por qué corresponderse y, en general, no corresponden a puntos clave como 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 la forma

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

Paso 3: Calcular la matriz de costos

Considere dos puntos p y q que tienen histogramas 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 el estadístico de prueba χ 2 como el "coste 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 esto varían de 0 a 1. ^[1] Además del costo del contexto de la forma, se puede agregar un costo adicional basado en la apariencia. Por ejemplo, podría ser una medida de disimilitud de ángulo tangente (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 un círculo unitario entre los vectores unitarios con ángulos y . Sus valores también varían de 0 a 1. Ahora 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 en la primera forma y un punto q _j en la segunda forma, calcule el costo como se describe y llámelo C _{i , j} . Esta es la matriz de costos.

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

Resultados del emparejamiento

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

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

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

Paso 5: Modelar 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 placa delgada (TPS) es el modelo más utilizado para transformaciones cuando se trabaja con contextos de formas. 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 uno de los ƒ _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 del núcleo está definida por . Los detalles exactos de cómo resolver los parámetros se pueden encontrar en otros lugares ^{[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 permitimos denotar los valores de la función objetivo en las ubicaciones correspondientes (tenga en cuenta que para , sería la coordenada x del punto correspondiente y para él 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 llama parámetro de regularización. Esta ƒ que minimiza H [ ƒ ] se puede encontrar de una manera bastante sencilla. ^[9] Si se utilizan coordenadas normalizadas para , entonces 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 repetimos los pasos para encontrar correspondencias y estimar transformaciones (es decir, repetimos los pasos 2 a 5 con la forma recién transformada) podemos superar este problema. Normalmente, bastan tres iteraciones 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 de contexto de forma : esta 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 los de 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 el costo de apariencia como la suma de las diferencias de brillo al cuadrado en 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 grises ( 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 del 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 usar un clasificador de vecino más cercano (k-NN) con la distancia definida como la distancia de la forma calculada aquí. Los resultados de aplicar esto a diferentes situaciones se dan 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 similitudes de siluetas

Los autores experimentaron con la base de datos de siluetas de formas MPEG-7, realizando el experimento central CE-Shape-1 parte B, que mide el rendimiento de la recuperación basada en similitudes. ^[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 consulta y contando el número de imágenes correctas entre las 40 coincidencias principales. Para este experimento, los autores aumentaron la cantidad de puntos muestreados de cada forma. Además, dado que las formas en la base de datos a veces se rotaban o invertían, los autores definieron la distancia entre una forma de referencia y una forma de consulta como la distancia mínima entre la forma de consulta y la referencia sin cambios, la invertida verticalmente o la referencia horizontalmente. volteado. ^{[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 en contextos de formas involucró 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 varias vistas igualmente espaciadas para cada objeto y las vistas restantes se utilizaron 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 la forma y la agrupación de k-medoides que mejoró su rendimiento. ^[4]

Recuperación de marcas

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

enlaces externos

• Emparejar con contextos de formas
• Base de datos MNIST de dígitos escritos a mano
• 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 formas". Taller IEEE sobre acceso basado en contenido de bibliotecas de imágenes y videos (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 formas" (PDF) . Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 24 (4): 509–521. doi : 10.1109/34.993558. S2CID  129468.
3. S. Belongie; J. Malik y J. Puzicha (julio de 2001). "Formas coincidentes" (PDF) . Octava Conferencia Internacional IEEE sobre Visión por Computadora (julio de 2001) .
4. S. Belongie; J. Malik y J. Puzicha (2000). "Contexto de forma: un nuevo descriptor para la coincidencia de formas y el reconocimiento de objetos" (PDF) . NIPS 2000 .
5. H. Chui y A. Rangarajan (junio de 2000). "Un nuevo algoritmo para la coincidencia 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 corto para problemas de asignación lineal densos y dispersos". Informática . 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 y Aplicaciones Computacionales (CTAC '95) . doi :10.1142/9789814530651.
8. J. Duchon (1977). "Splines que minimizan las seminormas invariantes de rotación en espacios de Sobolev". Teoría Constructiva de Funciones de Varias Variables . Apuntes de conferencias de 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. Matemática Industrial y Aplicada. ISBN 9780898712445.
10. Kowsari, Kamran; Heidarysafa, Mojtaba; Marrón, Donald E.; Meimandi, Kiana Jafari; Barnes, Laura E. (3 de mayo de 2018). "RMDL: aprendizaje profundo multimodelo aleatorio para clasificación". Actas de la Segunda Conferencia Internacional sobre Sistemas de Información y Minería de Datos . págs. 19-28. arXiv : 1805.01890 . Código Bib : 2018arXiv180501890K. doi :10.1145/3206098.3206111. ISBN 9781450363549. S2CID  19208611.
11. S. Jeannin y M. Bober (marzo de 1999). "Descripción de experimentos principales para movimiento/forma MPEG-7. Informe técnico ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Seúl". {{cite journal}}: Citar diario requiere |journal=( ayuda )