Detector de región afín de Harris

En los campos de la visión artificial y el análisis de imágenes , el detector de regiones afines de Harris pertenece a la categoría de detección de características . La detección de características es un paso de preprocesamiento de varios algoritmos que se basan en la identificación de puntos característicos o puntos de interés para realizar correspondencias entre imágenes, reconocer texturas, categorizar objetos o construir panoramas.

Descripción general

El detector afín de Harris puede identificar regiones similares entre imágenes que están relacionadas a través de transformaciones afines y tienen diferentes iluminaciones. Estos detectores afines-invariantes deberían ser capaces de identificar regiones similares en imágenes tomadas desde diferentes puntos de vista que están relacionadas por una transformación geométrica simple: escala, rotación y cizallamiento. Estas regiones detectadas se han llamado tanto invariantes como covariantes . Por un lado, las regiones se detectan invariantes de la transformación de la imagen, pero las regiones cambian covariantemente con la transformación de la imagen. ^[1] No se detenga demasiado en estas dos convenciones de nomenclatura; lo importante es entender que el diseño de estos puntos de interés los hará compatibles en imágenes tomadas desde varios puntos de vista. Otros detectores que son afines-invariantes incluyen el detector de región afín de Hessian , las regiones extremales de máxima estabilidad , el detector de saliencia de Kadir-Brady , las regiones basadas en bordes (EBR) y las regiones basadas en extremos de intensidad (IBR).

Mikolajczyk y Schmid (2002) describieron por primera vez el detector afín de Harris tal como se utiliza hoy en día en An Affine Invariant Interest Point Detector. ^[2] Los trabajos anteriores en esta dirección incluyen el uso de la adaptación de forma afín por Lindeberg y Garding para calcular descriptores de imagen invariantes afines y de esta manera reducir la influencia de las deformaciones de la imagen en perspectiva, ^[3] el uso de puntos característicos adaptados afines para una amplia coincidencia de línea base por Baumberg ^[4] y el primer uso de puntos característicos invariantes de escala por Lindeberg; ^{[5] [6] [7]} para una descripción general de los antecedentes teóricos. El detector afín de Harris se basa en la combinación de puntos de esquina detectados a través de la detección de esquinas de Harris , el análisis de múltiples escalas a través del espacio de escala gaussiano y la normalización afín utilizando un algoritmo iterativo de adaptación de forma afín . El algoritmo recursivo e iterativo sigue un enfoque iterativo para detectar estas regiones:

1. Identificar los puntos iniciales de la región utilizando el detector Harris-Laplace invariante de escala .
2. Para cada punto inicial, normalice la región para que sea invariante afín utilizando la adaptación de forma afín .
3. Estimar iterativamente la región afín: selección de la escala de integración adecuada, escala de diferenciación y localización espacial de los puntos de interés.
4. Actualice la región afín utilizando estas escalas y localizaciones espaciales.
5. Repita el paso 3 si no se cumple el criterio de detención.

Descripción del algoritmo

Detector de Harris-Laplace (puntos de la región inicial)

El detector afín de Harris depende en gran medida tanto de la medida de Harris como de una representación del espacio de escala gaussiana . Por lo tanto, a continuación se presenta un breve análisis de ambos. Para obtener derivaciones más exhaustivas, consulte detección de esquinas y espacio de escala gaussiana o sus artículos asociados. ^{[6] [8]}

Medida de esquina de Harris

El algoritmo del detector de esquinas de Harris se basa en un principio central: en una esquina, la intensidad de la imagen cambiará en gran medida en múltiples direcciones. Esto se puede formular de manera alternativa examinando los cambios de intensidad debidos a los cambios en una ventana local. Alrededor de un punto de esquina, la intensidad de la imagen cambiará en gran medida cuando la ventana se desplace en una dirección arbitraria. Siguiendo esta intuición y mediante una descomposición inteligente, el detector de Harris utiliza la segunda matriz de momentos como base de sus decisiones de esquina. (Véase detección de esquinas para una derivación más completa). La matriz , también se ha denominado matriz de autocorrelación y tiene valores estrechamente relacionados con las derivadas de la intensidad de la imagen . ${\displaystyle A}$

${\displaystyle A(\mathbf {x} )=\sum _{p,q}w(p,q){\begin{bmatrix}I_{x}^{2}(p,q)&I_{x}I_{y}(p,q)\\I_{x}I_{y}(p,q)&I_{y}^{2}(p,q)\\\end{bmatrix}}}$

donde y son las derivadas respectivas (de la intensidad de los píxeles) en la dirección y en el punto ( , ); y son los parámetros de posición de la función de ponderación w. Las entradas fuera de la diagonal son el producto de y , mientras que las entradas diagonales son cuadrados de las derivadas respectivas . La función de ponderación puede ser uniforme, pero es más típicamente una función gaussiana circular isótropa. ${\displaystyle I_{x}}$ ${\displaystyle I_{y}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle I_{x}}$ ${\displaystyle I_{y}}$ ${\displaystyle w(x,y)}$

${\displaystyle w(x,y)=g(x,y,\sigma )={\frac {1}{2\pi \sigma ^{2}}}e^{\left(-{\frac {x^{2}+y^{2}}{2\sigma ^{2}}}\right)}}$

que actúa para promediar en una región local mientras pondera más fuertemente aquellos valores cerca del centro.

Resulta que esta matriz describe la forma de la medida de autocorrelación como resultado de cambios en la ubicación de la ventana. Por lo tanto, si dejamos que y sean los valores propios de , estos valores proporcionarán una descripción cuantitativa de cómo cambia la medida de autocorrelación en el espacio: sus curvaturas principales. Como señalan Harris y Stephens (1988), la matriz centrada en los puntos de esquina tendrá dos valores propios positivos y grandes. ^[8] En lugar de extraer estos valores propios utilizando métodos como la descomposición en valores singulares, se utiliza la medida de Harris basada en la traza y el determinante: ${\displaystyle A}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle \lambda _{2}}$ ${\displaystyle A}$ ${\displaystyle A}$

${\displaystyle R=\det(A)-\alpha \operatorname {trace} ^{2}(A)=\lambda _{1}\lambda _{2}-\alpha (\lambda _{1}+\lambda _{2})^{2}}$

donde es una constante. Los puntos de esquina tienen valores propios positivos y grandes y, por lo tanto, tendrían una medida de Harris grande. Por lo tanto, los puntos de esquina se identifican como máximos locales de la medida de Harris que están por encima de un umbral especificado. ${\displaystyle \alpha }$

${\displaystyle {\begin{aligned}\{x_{c}\}={\big \{}x_{c}\mid R(x_{c})>R(x_{i}),\forall x_{i}\in W(x_{c}){\big \}},\\R(x_{c})>t_{\text{threshold}}\end{aligned}}}$

donde son el conjunto de todos los puntos de esquina, es la medida de Harris calculada en , es un conjunto de 8 vecinos centrado en y es un umbral especificado. ${\displaystyle \{x_{c}\}}$ ${\displaystyle R(x)}$ ${\displaystyle x}$ ${\displaystyle W(x_{c})}$ ${\displaystyle x_{c}}$ ${\displaystyle t_{\text{threshold}}}$

Barrio de 8 puntos

Espacio de escala gaussiano

Una representación espacial a escala gaussiana de una imagen es el conjunto de imágenes que resultan de la convolución de un núcleo gaussiano de distintos tamaños con la imagen original. En general, la representación se puede formular como:

${\displaystyle L(\mathbf {x} ,s)=G(s)\otimes I(\mathbf {x} )}$

donde es un núcleo gaussiano circular isótropo como se definió anteriormente. La convolución con un núcleo gaussiano suaviza la imagen utilizando una ventana del tamaño del núcleo. Una escala mayor, , corresponde a una imagen resultante más suave. Mikolajczyk y Schmid (2001) señalan que las derivadas y otras mediciones deben normalizarse en todas las escalas. ^[9] Una derivada de orden , , debe normalizarse mediante un factor de la siguiente manera: ${\displaystyle G(s)}$ ${\displaystyle s}$ ${\displaystyle m}$ ${\displaystyle D_{i_{1},...i_{m}}}$ ${\displaystyle s^{m}}$

${\displaystyle D_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)=s^{m}L_{i_{1},\dots ,i_{m}}(\mathbf {x} ,s)}$

Estas derivadas, o cualquier medida arbitraria, se pueden adaptar a una representación del espacio de escala calculando esta medida utilizando un conjunto de escalas de forma recursiva, donde la escala th es . Consulte el espacio de escala para obtener una descripción más completa. ${\displaystyle n}$ ${\displaystyle s_{n}=k^{n}s_{0}}$

Combinación del detector de Harris en el espacio de escala gaussiano

El detector Harris-Laplace combina el detector de esquinas Harris 2D tradicional con la idea de una representación espacial de escala gaussiana para crear un detector invariante en la escala. Los puntos de esquina de Harris son buenos puntos de partida porque se ha demostrado que tienen una buena invariancia rotacional y de iluminación, además de identificar los puntos interesantes de la imagen. ^[10] Sin embargo, los puntos no son invariantes en la escala y, por lo tanto, la matriz de segundo momento debe modificarse para reflejar una propiedad invariante en la escala. Denotemos, como la matriz de segundo momento adaptada a la escala utilizada en el detector Harris-Laplace. ${\displaystyle M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$

${\displaystyle M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})=\sigma _{D}^{2}g(\sigma _{I})\otimes {\begin{bmatrix}L_{x}^{2}(\mathbf {x} ,\sigma _{D})&L_{x}L_{y}(\mathbf {x} ,\sigma _{D})\\L_{x}L_{y}(\mathbf {x} ,\sigma _{D})&L_{y}^{2}(\mathbf {x} ,\sigma _{D})\end{bmatrix}}}$^[11]

donde es el núcleo gaussiano de escala y . De manera similar al espacio de escala gaussiana, es la imagen suavizada gaussiana. El operador denota convolución. y son las derivadas en su dirección respectiva aplicadas a la imagen suavizada y calculadas utilizando un núcleo gaussiano con escala . En términos de nuestro marco de trabajo de espacio de escala gaussiano, el parámetro determina la escala actual en la que se detectan los puntos de esquina de Harris. ${\displaystyle g(\sigma _{I})}$ ${\displaystyle \sigma _{I}}$ ${\displaystyle \mathbf {x} =(x,y)}$ ${\displaystyle L(\mathbf {x} )}$ ${\displaystyle \mathbf {\otimes } }$ ${\displaystyle L_{x}(\mathbf {x} ,\sigma _{D})}$ ${\displaystyle L_{y}(\mathbf {x} ,\sigma _{D})}$ ${\displaystyle \sigma _{D}}$ ${\displaystyle \sigma _{I}}$

Basándose en esta matriz de segundo momento adaptada a la escala, el detector de Harris-Laplace es un proceso doble: aplicar el detector de esquinas de Harris en múltiples escalas y elegir automáticamente la escala característica .

Puntos de esquina de Harris de múltiples escalas

El algoritmo realiza la búsqueda en un número fijo de escalas predefinidas. Este conjunto de escalas se define como:

${\displaystyle {\sigma _{1}\dots \sigma _{n}}={k^{1}\sigma _{0}\dots k^{n}\sigma _{0}}}$

Mikolajczyk y Schmid (2004) utilizan . Para cada escala de integración, , elegida de este conjunto, se elige la escala de diferenciación adecuada para que sea un factor constante de la escala de integración: . Mikolajczyk y Schmid (2004) utilizaron . ^[11] Utilizando estas escalas, los puntos de interés se detectan utilizando una medida de Harris en la matriz. La arista, al igual que la medida de Harris típica, se define como: ${\displaystyle k=1.4}$ ${\displaystyle \sigma _{I}}$ ${\displaystyle \sigma _{D}=s\sigma _{I}}$ ${\displaystyle s=0.7}$ ${\displaystyle \mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$

${\displaystyle {\mathit {cornerness}}=\det(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}}))}$

Al igual que el detector Harris tradicional, los puntos de esquina son aquellos máximos locales (vecindario de 8 puntos) de la esquina que están por encima de un umbral especificado.

Identificación de escala característica

Un algoritmo iterativo basado en Lindeberg (1998) localiza espacialmente los puntos de esquina y selecciona la escala característica . ^[6] La búsqueda iterativa tiene tres pasos clave, que se llevan a cabo para cada punto que se detectó inicialmente a escala por el detector Harris multiescala ( indica la iteración): ${\displaystyle \mathbf {x} }$ ${\displaystyle \sigma _{I}}$ ${\displaystyle k}$ ${\displaystyle kth}$

• Seleccione la escala que maximice el laplaciano de gaussianos (LoG) en un rango predefinido de escalas vecinas. ${\displaystyle \sigma _{I}^{(k+1)}}$ Las escalas vecinas se eligen típicamente de un rango que se encuentra dentro de un entorno de dos escalas espaciales . Es decir, si los puntos originales se detectaron utilizando un factor de escala de entre escalas sucesivas, un entorno de dos escalas espaciales es el rango . Por lo tanto, las escalas gaussianas examinadas son: . La medición LoG se define como: ${\displaystyle 1.4}$ ${\displaystyle t\in [0.7,\dots ,1.4]}$ ${\displaystyle \sigma _{I}^{(k+1)}=t\sigma _{I}^{k}}$

${\displaystyle |\operatorname {LoG} (\mathbf {x} ,\sigma _{I})|=\sigma _{I}^{2}\left|L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I})\right|}$

donde y son las derivadas segundas en sus respectivas direcciones. ^[12] El factor (como se discutió anteriormente en el espacio de escala gaussiano) se utiliza para normalizar el LoG en todas las escalas y hacer que estas medidas sean comparables, haciendo así que un máximo sea relevante. Mikolajczyk y Schmid (2001) demuestran que la medida LoG alcanza el mayor porcentaje de puntos de esquina detectados correctamente en comparación con otras medidas de selección de escala. ^[9] La escala que maximiza esta medida LoG en el entorno de dos espacios de escala se considera la escala característica , y se utiliza en iteraciones posteriores. Si no se encuentran extremos o máximos del LoG, este punto se descarta de futuras búsquedas. ${\displaystyle L_{xx}}$ ${\displaystyle L_{yy}}$ ${\displaystyle \sigma _{I}^{2}}$ ${\displaystyle \sigma _{I}^{(k+1)}}$

• Utilizando la escala característica, los puntos se localizan espacialmente. Es decir, el punto se elige de manera que maximice la medida de esquina de Harris ( esquina definida anteriormente) dentro de un entorno local de 8x8. ${\displaystyle \mathbf {x} ^{(k+1)}}$
• Criterio de parada : y . ${\displaystyle \sigma _{I}^{(k+1)}==\sigma _{I}^{(k)}}$ ${\displaystyle \mathbf {x} ^{(k+1)}==\mathbf {x} ^{(k)}}$

Si no se cumple el criterio de detención, el algoritmo repite el proceso desde el paso 1 utilizando los nuevos puntos y la nueva escala. Cuando se cumple el criterio de detención, los puntos encontrados representan aquellos que maximizan el LoG en todas las escalas (selección de escala) y maximizan la medida de la esquina de Harris en un vecindario local (selección espacial). ${\displaystyle k+1}$

Puntos afines invariantes

Teoría matemática

Los puntos detectados por Harris-Laplace son invariantes en cuanto a la escala y funcionan bien para regiones isotrópicas que se observan desde el mismo ángulo de visión. Para que sean invariantes ante transformaciones afines arbitrarias (y puntos de vista), se debe revisar el marco matemático. La matriz del segundo momento se define de manera más general para regiones anisotrópicas: ${\displaystyle \mathbf {\mu } }$

${\displaystyle \mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})=\det(\Sigma _{D})g(\Sigma _{I})*(\nabla L(\mathbf {x} ,\Sigma _{D})\nabla L(\mathbf {x} ,\Sigma _{D})^{T})}$

donde y son matrices de covarianza que definen las escalas del kernel gaussiano de diferenciación e integración. Aunque esto puede parecer significativamente diferente de la matriz de segundo momento en el detector de Harris-Laplace; de ​​hecho, es idéntica. La matriz anterior era la versión isotrópica 2D en la que las matrices de covarianza y eran matrices de identidad 2x2 multiplicadas por factores y , respectivamente. En la nueva formulación, uno puede pensar en los kernels gaussianos como distribuciones gaussianas multivariadas en oposición a un kernel gaussiano uniforme. Un kernel gaussiano uniforme puede considerarse como una región circular isótropa. De manera similar, un kernel gaussiano más general define un elipsoide. De hecho, los vectores propios y los valores propios de la matriz de covarianza definen la rotación y el tamaño del elipsoide. Por lo tanto, podemos ver fácilmente que esta representación nos permite definir completamente una región afín elíptica arbitraria sobre la que queremos integrar o diferenciar. ${\displaystyle \Sigma _{I}}$ ${\displaystyle \Sigma _{D}}$ ${\displaystyle \mu }$ ${\displaystyle \Sigma _{I}}$ ${\displaystyle \Sigma _{D}}$ ${\displaystyle \sigma _{I}}$ ${\displaystyle \sigma _{D}}$

El objetivo del detector invariante afín es identificar regiones en imágenes que están relacionadas a través de transformaciones afines. Por lo tanto, consideramos un punto y el punto transformado , donde A es una transformación afín. En el caso de las imágenes, tanto y viven en el espacio. Las matrices de segundo momento están relacionadas de la siguiente manera: ^[3] ${\displaystyle \mathbf {x} _{L}}$ ${\displaystyle \mathbf {x} _{R}=A\mathbf {x} _{L}}$ ${\displaystyle \mathbf {x} _{R}}$ ${\displaystyle \mathbf {x} _{L}}$ ${\displaystyle R^{2}}$

${\displaystyle {\begin{aligned}\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})&{}=A^{T}\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})A\\M_{L}&{}=\mu (\mathbf {x} _{L},\Sigma _{I,L},\Sigma _{D,L})\\M_{R}&{}=\mu (\mathbf {x} _{R},\Sigma _{I,R},\Sigma _{D,R})\\M_{L}&{}=A^{T}M_{R}A\\\Sigma _{I,R}&{}=A\Sigma _{I,L}A^{T}{\text{ and }}\Sigma _{D,R}=A\Sigma _{D,L}A^{T}\end{aligned}}}$

donde y son las matrices de covarianza para el marco de referencia. Si continuamos con esta formulación y hacemos cumplir que ${\displaystyle \Sigma _{I,b}}$ ${\displaystyle \Sigma _{D,b}}$ ${\displaystyle b}$

${\displaystyle {\begin{aligned}\Sigma _{I,L}=\sigma _{I}M_{L}^{-1}\\\Sigma _{D,L}=\sigma _{D}M_{L}^{-1}\end{aligned}}}$

donde y son factores escalares, se puede demostrar que las matrices de covarianza para el punto relacionado están relacionadas de manera similar: ${\displaystyle \sigma _{I}}$ ${\displaystyle \sigma _{D}}$

${\displaystyle {\begin{aligned}\Sigma _{I,R}=\sigma _{I}M_{R}^{-1}\\\Sigma _{D,R}=\sigma _{D}M_{R}^{-1}\end{aligned}}}$

Al exigir que las matrices de covarianza satisfagan estas condiciones, surgen varias propiedades interesantes. Una de estas propiedades es que la raíz cuadrada de la matriz de segundo momento transformará la región anisotrópica original en regiones isotrópicas que están relacionadas simplemente a través de una matriz de rotación pura . Estas nuevas regiones isotrópicas pueden considerarse como un marco de referencia normalizado. Las siguientes ecuaciones formulan la relación entre los puntos normalizados y : ${\displaystyle M^{\tfrac {1}{2}}}$ ${\displaystyle R}$ ${\displaystyle x_{R}^{'}}$ ${\displaystyle x_{L}^{'}}$

${\displaystyle {\begin{aligned}A=M_{R}^{-{\tfrac {1}{2}}}RM_{L}^{\tfrac {1}{2}}\\x_{R}^{'}=M_{R}^{\tfrac {1}{2}}x_{R}\\x_{L}^{'}=M_{L}^{\tfrac {1}{2}}x_{L}\\x_{L}^{'}=Rx_{R}^{'}\\\end{aligned}}}$

La matriz de rotación se puede recuperar utilizando métodos de gradiente como los del descriptor SIFT . Como se explicó con el detector de Harris, los valores propios y los vectores propios de la matriz de segundo momento caracterizan la curvatura y la forma de las intensidades de los píxeles. Es decir, el vector propio asociado con el valor propio más grande indica la dirección del mayor cambio y el vector propio asociado con el valor propio más pequeño define la dirección del menor cambio. En el caso 2D, los vectores propios y los valores propios definen una elipse. Para una región isotrópica, la región debe tener forma circular y no elíptica. Este es el caso cuando los valores propios tienen la misma magnitud. Por lo tanto, una medida de la isotropía alrededor de una región local se define de la siguiente manera: ${\displaystyle M=\mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})}$

${\displaystyle {\mathcal {Q}}={\frac {\lambda _{\min }(M)}{\lambda _{\max }(M)}}}$

donde denotan valores propios. Esta medida tiene un rango de . Un valor de corresponde a una isotropía perfecta. ${\displaystyle \lambda }$ ${\displaystyle [0\dots 1]}$ ${\displaystyle 1}$

Algoritmo iterativo

Utilizando este marco matemático, el algoritmo del detector afín de Harris descubre iterativamente la matriz de segundo momento que transforma la región anisotrópica en una región normalizada en la que la medida isotrópica es suficientemente cercana a uno. El algoritmo utiliza esta matriz de adaptación de forma , , para transformar la imagen en un marco de referencia normalizado. En este espacio normalizado, los parámetros de los puntos de interés (ubicación espacial, escala de integración y escala de diferenciación) se refinan utilizando métodos similares al detector de Harris-Laplace. La matriz de segundo momento se calcula en este marco de referencia normalizado y debe tener una medida isotrópica cercana a uno en la iteración final. En cada iteración, cada región de interés se define por varios parámetros que el algoritmo debe descubrir: la matriz, la posición , la escala de integración y la escala de diferenciación . Debido a que el detector calcula la matriz de segundo momento en el dominio transformado, es conveniente denotar esta posición transformada como donde . ${\displaystyle U}$ ${\displaystyle k}$ ${\displaystyle U^{(k)}}$ ${\displaystyle \mathbf {x} ^{(k)}}$ ${\displaystyle \sigma _{I}^{(k)}}$ ${\displaystyle \sigma _{D}^{(k)}}$ ${\displaystyle \mathbf {x} _{w}^{(k)}}$ ${\displaystyle U^{(k)}\mathbf {x} _{w}^{(k)}=\mathbf {x^{(k)}} }$

1. El detector inicializa el espacio de búsqueda con puntos detectados por el detector Harris-Laplace.

   ${\displaystyle U^{(0)}={\mathit {identity}}}$y , , y son los del detector Harris-Laplace. ${\displaystyle \mathbf {x} ^{(0)}}$ ${\displaystyle \sigma _{D}^{(0)}}$ ${\displaystyle \sigma _{I}^{(0)}}$

2. Aplique la matriz de adaptación de forma de la iteración anterior para generar el marco de referencia normalizado. Para la primera iteración, aplique . ${\displaystyle U^{(k-1)}}$ ${\displaystyle U^{(k-1)}\mathbf {x} _{w}^{(k-1)}=\mathbf {x} ^{(k-1)}}$ ${\displaystyle U^{(0)}}$
3. Seleccione la escala de integración , , utilizando un método similar al detector de Harris-Laplace. La escala se elige como la escala que maximiza el Laplaciano de Gauss (LoG). El espacio de búsqueda de las escalas son aquellas dentro de dos espacios de escala de la escala de iteraciones anteriores. ${\displaystyle \sigma _{I}^{(k)}}$

   ${\displaystyle \sigma _{I}^{(k)}={\underset {\sigma _{I}=t\sigma _{I}^{(k-1)} \atop t\in [0.7,\dots ,1.4]}{\operatorname {argmax} }}\,\sigma _{I}^{2}\det(L_{xx}(\mathbf {x} ,\sigma _{I})+L_{yy}(\mathbf {x} ,\sigma _{I}))}$

   Es importante tener en cuenta que la escala de integración en el espacio difiere significativamente de la del espacio no normalizado. Por lo tanto, es necesario buscar la escala de integración en lugar de utilizar la escala en el espacio no normalizado. ${\displaystyle U-normalized}$
4. Seleccione la escala de diferenciación , . Para reducir el espacio de búsqueda y los grados de libertad, se toma la escala de diferenciación como relacionada con la escala de integración a través de un factor constante: . Por razones obvias, el factor constante es menor que uno. Mikolajczyk y Schmid (2001) señalan que un factor demasiado pequeño hará que el suavizado (integración) sea demasiado significativo en comparación con la diferenciación y un factor demasiado grande no permitirá que la integración promedie la matriz de covarianza. ^[9] Es común elegir . De este conjunto, la escala elegida maximizará la medida isotrópica . ${\displaystyle \sigma _{D}^{(k)}}$ ${\displaystyle \sigma _{D}^{k}=s\sigma _{I}^{k}}$ ${\displaystyle s\in [0.5,0.75]}$ ${\displaystyle {\mathcal {Q}}={\frac {\lambda _{min}(\mu )}{\lambda _{max}(\mu )}}}$

   ${\displaystyle \sigma _{D}^{(k)}={\underset {\sigma _{D}=s\sigma _{I}^{(k)},\;s\in [0.5,\dots ,0.75]}{\operatorname {argmax} }}\,{\frac {\lambda _{\min }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}{\lambda _{\max }(\mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D}))}}}$

   donde es la matriz de segundo momento evaluada en el marco de referencia normalizado. Este proceso de maximización hace que los valores propios converjan al mismo valor. ${\displaystyle \mu (\mathbf {x} _{w}^{(k)},\sigma _{I}^{k},\sigma _{D})}$
5. Localización espacial: seleccione el punto que maximice la medida de la esquina de Harris ( ) dentro de un vecindario de 8 puntos alrededor del punto anterior. ${\displaystyle \mathbf {x} _{w}^{(k)}}$ ${\displaystyle {\mathit {cornerness}}}$ ${\displaystyle \mathbf {x} _{w}^{(k-1)}}$

   ${\displaystyle \mathbf {x} _{w}^{(k)}={\underset {\mathbf {x} _{w}\in W(\mathbf {x} _{w}^{(k-1)})}{\operatorname {argmax} }}\,\det(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))-\alpha \operatorname {trace} ^{2}(\mu (\mathbf {x} _{w},\sigma _{I}^{k},\sigma _{D}^{(k)}))}$

   donde es la matriz de segundo momento definida anteriormente. La ventana es el conjunto de 8 vecinos más cercanos del punto de la iteración anterior en el marco de referencia normalizado. Debido a que nuestra localización espacial se realizó en el marco de referencia normalizado, el punto recién elegido debe transformarse nuevamente al marco de referencia original. Esto se logra transformando un vector de desplazamiento y agregándolo al punto anterior: ${\displaystyle \mu }$ ${\displaystyle W(\mathbf {x} _{w}^{(k-1)})}$ ${\displaystyle U}$

   ${\displaystyle \mathbf {x} ^{(k)}=\mathbf {x} ^{(k-1)}+U^{(k-1)}\cdot (\mathbf {x} _{w}^{(k)}-\mathbf {x} _{w}^{(k-1)})}$

6. Como se mencionó anteriormente, la raíz cuadrada de la matriz de segundo momento define la matriz de transformación que genera el marco de referencia normalizado. Por lo tanto, debemos guardar esta matriz: . La matriz de transformación se actualiza: . Para garantizar que la imagen se muestrea correctamente y que estamos expandiendo la imagen en la dirección del menor cambio (valor propio más pequeño), fijamos el valor propio máximo: . Al utilizar este método de actualización, se puede ver fácilmente que la matriz final toma la siguiente forma: ${\displaystyle \mu _{i}^{(k)}=\mu ^{-{\tfrac {1}{2}}}(\mathbf {x} _{w}^{(k)},\sigma _{I}^{(k)},\sigma _{D}^{(k)})}$ ${\displaystyle U}$ ${\displaystyle U^{(k)}=\mu _{i}^{(k)}\cdot U^{(k-1)}}$ ${\displaystyle \lambda _{max}(U^{(k)})=1}$ ${\displaystyle U}$

   ${\displaystyle U=\prod _{k}\mu _{i}^{(k)}\cdot U^{(0)}=\prod _{k}(\mu ^{-{\tfrac {1}{2}}})^{(k)}\cdot U^{(0)}}$

7. Si no se cumple el criterio de detención , continúe con la siguiente iteración en el paso 2. Debido a que el algoritmo resuelve iterativamente la matriz que transforma una región anisotrópica en una región isotrópica, tiene sentido detenerse cuando la medida isotrópica, , está suficientemente cerca de su valor máximo 1. Suficientemente cerca implica la siguiente condición de detención : ${\displaystyle U-normalization}$ ${\displaystyle {\mathcal {Q}}={\frac {\lambda _{\min }(\mu )}{\lambda _{\max }(\mu )}}}$

   ${\displaystyle 1-{\frac {\lambda _{\min }(\mu _{i}^{(k)})}{\lambda _{\max }(\mu _{i}^{(k)})}}<\varepsilon _{C}}$

   Mikolajczyk y Schmid (2004) tuvieron mucho éxito con . ${\displaystyle \epsilon _{C}=0.05}$

Cálculo e implementación

La complejidad computacional del detector afín de Harris se divide en dos partes: detección de puntos iniciales y normalización de la región afín. El algoritmo de detección de puntos iniciales, Harris-Laplace, tiene una complejidad donde es el número de píxeles en la imagen. El algoritmo de normalización de la región afín detecta automáticamente la escala y estima la matriz de adaptación de forma , . Este proceso tiene una complejidad , donde es el número de puntos iniciales, es el tamaño del espacio de búsqueda para la selección automática de la escala y es el número de iteraciones necesarias para calcular la matriz. ^[11] ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle n}$ ${\displaystyle U}$ ${\displaystyle {\mathcal {O}}((m+k)p)}$ ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle U}$

Existen algunos métodos para reducir la complejidad del algoritmo a expensas de la precisión. Un método consiste en eliminar la búsqueda en el paso de escala de diferenciación. En lugar de elegir un factor de un conjunto de factores, el algoritmo acelerado elige que la escala sea constante a lo largo de las iteraciones y los puntos: . Aunque esta reducción en el espacio de búsqueda puede disminuir la complejidad, este cambio puede afectar gravemente la convergencia de la matriz. ${\displaystyle s}$ ${\displaystyle \sigma _{D}=s\sigma _{I},\;s=constant}$ ${\displaystyle U}$

Análisis

Convergencia

Se puede imaginar que este algoritmo podría identificar puntos de interés duplicados en múltiples escalas. Debido a que el algoritmo afín de Harris analiza cada punto inicial dado por el detector de Harris-Laplace de forma independiente, no hay discriminación entre puntos idénticos. En la práctica, se ha demostrado que estos puntos finalmente convergerán todos al mismo punto de interés. Después de terminar de identificar todos los puntos de interés, el algoritmo tiene en cuenta los duplicados comparando las coordenadas espaciales ( ), la escala de integración , la medida isotrópica y la asimetría. ^[11] Si estos parámetros de puntos de interés son similares dentro de un umbral especificado, entonces se etiquetan como duplicados. El algoritmo descarta todos estos puntos duplicados excepto el punto de interés que está más cerca del promedio de los duplicados. Por lo general, el 30% de los puntos afines de Harris son distintos y lo suficientemente diferentes como para no descartarse. ^[11] ${\displaystyle \mathbf {x} }$ ${\displaystyle \sigma _{I}}$ ${\displaystyle {\tfrac {\lambda _{\min }(U)}{\lambda _{\max }(U)}}}$

Mikolajczyk y Schmid (2004) demostraron que a menudo los puntos iniciales (40%) no convergen. El algoritmo detecta esta divergencia deteniendo el algoritmo iterativo si la inversa de la medida isotrópica es mayor que un umbral especificado: . Mikolajczyk y Schmid (2004) utilizan . De los que sí convergieron, el número típico de iteraciones requeridas fue 10. ^[2] ${\displaystyle {\tfrac {\lambda _{\max }(U)}{\lambda _{\min }(U)}}>t_{\text{diverge}}}$ ${\displaystyle t_{diverge}=6}$

Medida cuantitativa

El análisis cuantitativo de los detectores de regiones afines tiene en cuenta tanto la precisión de las ubicaciones de los puntos como la superposición de regiones en dos imágenes. Mioklajcyzk y Schmid (2004) amplían la medida de repetibilidad de Schmid et al. (1998) como la relación entre las correspondencias de puntos y los puntos mínimos detectados de las dos imágenes. ^{[11] [13]}

${\displaystyle R_{\text{score}}={\frac {C(A,B)}{\min(n_{A},n_{B})}}}$

donde son el número de puntos correspondientes en las imágenes y . y son el número de puntos detectados en las imágenes respectivas. Debido a que cada imagen representa el espacio 3D, podría darse el caso de que una imagen contenga objetos que no están en la segunda imagen y, por lo tanto, cuyos puntos de interés no tienen posibilidad de corresponder. Para que la medida de repetibilidad sea válida, se eliminan estos puntos y solo se deben considerar los puntos que se encuentran en ambas imágenes; y solo se cuentan aquellos puntos tales que . Para un par de dos imágenes relacionadas a través de una matriz de homografía , se dice que dos puntos, y corresponden si: ${\displaystyle C(A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n_{B}}$ ${\displaystyle n_{A}}$ ${\displaystyle n_{A}}$ ${\displaystyle n_{B}}$ ${\displaystyle x_{A}=H\cdot x_{B}}$ ${\displaystyle H}$ ${\displaystyle \mathbf {x_{a}} }$ ${\displaystyle \mathbf {x_{b}} }$

Región de superposición de dos regiones elípticas.

1. El error en la ubicación del píxel es inferior a 1,5 píxeles: ${\displaystyle \|\mathbf {x_{a}} -H\cdot \mathbf {x_{b}} \|<1.5}$
2. El error de superposición de los dos puntos afines ( ) debe ser menor que un umbral especificado (normalmente el 40%). ^[1] Para las regiones afines, este error de superposición es el siguiente: ${\displaystyle \epsilon _{S}}$

   ${\displaystyle \epsilon _{S}=1-{\frac {\mu _{a}\cap (H^{T}\mu _{b}H)}{\mu _{a}\cup (H^{T}\mu _{b}H)}}}$

   donde y son las regiones elípticas recuperadas cuyos puntos satisfacen: . Básicamente, esta medida toma una proporción de áreas: el área de superposición (intersección) y el área total (unión). La superposición perfecta tendría una proporción de uno y tendría un . Diferentes escalas afectan la región de superposición y, por lo tanto, deben tenerse en cuenta al normalizar el área de cada región de interés. Las regiones con un error de superposición de hasta el 50% son detectores viables para ser emparejados con un buen descriptor. ^[1] ${\displaystyle \mu _{a}}$ ${\displaystyle \mu _{b}}$ ${\displaystyle \mu ^{T}\mathbf {x} \mu =1}$ ${\displaystyle \epsilon _{S}=0}$

   Una segunda medida, una puntuación de coincidencia , evalúa de manera más práctica la capacidad del detector para identificar puntos coincidentes entre imágenes. Mikolajczyk y Schmid (2005) utilizan un descriptor SIFT para identificar puntos coincidentes. Además de ser los puntos más cercanos en el espacio SIFT, dos puntos coincidentes también deben tener un error de superposición suficientemente pequeño (como se define en la medida de repetibilidad). La puntuación de coincidencia es la relación entre el número de puntos coincidentes y el mínimo del total de puntos detectados en cada imagen:

   ${\displaystyle M_{score}={\frac {M(A,B)}{\min(n_{A},n_{B})}}}$, ^[1]

   donde son el número de puntos coincidentes y y son el número de regiones detectadas en las respectivas imágenes. ${\displaystyle M(A,B)}$ ${\displaystyle n_{B}}$ ${\displaystyle n_{A}}$

Robustez a las transformaciones afines y de otro tipo

Mikolajczyk et al. (2005) han realizado un análisis exhaustivo de varios detectores de regiones afines de última generación: Harris afín, Hessian afín , MSER , ^[14] IBR y EBR ^[15] y detectores salientes ^{[16] . [1]} Mikolajczyk et al. analizaron tanto imágenes estructuradas como imágenes texturizadas en su evaluación. Los binarios de Linux de los detectores y sus imágenes de prueba están disponibles de forma gratuita en su página web. A continuación se incluye un breve resumen de los resultados de Mikolajczyk et al. (2005); consulte A comparison of affine region detectors para un análisis más cuantitativo.

• Cambio del ángulo del punto de vista: el detector afín de Harris tiene una robustez razonable (promedio) a este tipo de cambios. El detector mantiene un puntaje de repetibilidad de más del 50 % hasta un ángulo del punto de vista de más de 40 grados. El detector tiende a detectar una gran cantidad de regiones repetibles y coincidentes incluso con un gran cambio del punto de vista.
• Cambio de escala: el detector afín de Harris se mantiene muy constante ante cambios de escala. Aunque el número de puntos disminuye considerablemente ante grandes cambios de escala (por encima de 2,8), la repetibilidad (50-60 %) y los puntajes de coincidencia (25-30 %) se mantienen muy constantes, especialmente con imágenes texturizadas. Esto es coherente con el alto rendimiento del algoritmo iterativo de selección de escala automática.
• Imágenes borrosas: el detector afín de Harris se mantiene muy estable en condiciones de imágenes borrosas. Debido a que el detector no depende de la segmentación de imágenes ni de los límites de las regiones, la repetibilidad y los índices de coincidencia se mantienen constantes.
• Artefactos JPEG: El detector afín de Harris se degrada de manera similar a otros detectores afines: los puntajes de repetibilidad y coincidencia caen significativamente por encima del 80 % de compresión.
• Cambios de iluminación: el detector afín de Harris, al igual que otros detectores afines, es muy resistente a los cambios de iluminación: la repetibilidad y los puntajes de coincidencia permanecen constantes cuando la luz disminuye. Esto es de esperarse porque los detectores dependen en gran medida de intensidades relativas (derivadas) y no de intensidades absolutas.

Tendencias generales

• Los puntos de la región afín de Harris tienden a ser pequeños y numerosos. Tanto el detector afín de Harris como el afín de Hess identifican de manera consistente el doble de puntos repetibles que otros detectores afines: aproximadamente 1000 regiones para una imagen de 800x640. ^[1] Las regiones pequeñas tienen menos probabilidades de quedar ocluidas, pero tienen una menor probabilidad de superponerse con regiones vecinas.
• El detector afín de Harris responde bien a escenas con textura en las que hay muchas partes que parecen esquinas. Sin embargo, para algunas escenas estructuradas, como edificios, el detector afín de Harris funciona muy bien. Esto es complementario a MSER que tiende a funcionar mejor con escenas bien estructuradas (segmentables).
• En general, el detector afín de Harris funciona muy bien, pero todavía está por detrás del MSER y del afín de Hess en todos los casos, excepto en imágenes borrosas.
• Los detectores afines a Harris y afines a Hess son menos precisos que otros: su puntuación de repetibilidad aumenta a medida que aumenta el umbral de superposición.
• Las regiones invariantes afines detectadas pueden diferir en su rotación e iluminación. Cualquier descriptor que utilice estas regiones debe tener en cuenta la invariancia al utilizarlas para realizar comparaciones o para otros fines.

Aplicaciones

• Recuperación de imágenes basada en contenido ^{[17] [18]}
• Reconocimiento basado en modelos
• Recuperación de objetos en vídeo ^[19]
• Minería visual de datos: identificación de objetos, personajes y escenas importantes en vídeos ^[20]
• Reconocimiento y categorización de objetos ^[21]
• Análisis de imágenes obtenidas por teledetección: detección de objetos a partir de imágenes obtenidas por teledetección ^[22]

Paquetes de software

• Características covariantes afines: K. Mikolajczyk mantiene una página web que contiene binarios de Linux del detector afín de Harris además de otros detectores y descriptores. También está disponible el código Matlab que se puede utilizar para ilustrar y calcular la repetibilidad de varios detectores. También hay código e imágenes disponibles para duplicar los resultados encontrados en el artículo de Mikolajczyk et al. (2005).
• lip-vireo – código binario para Linux, Windows y SunOS del grupo de investigación VIREO. Ver más en la página de inicio Archivado el 11 de mayo de 2017 en Wayback Machine

Enlaces externos

• [1] – Diapositivas de presentación de Mikolajczyk et al. en su artículo de 2005.
• [2] – Laboratorio de visión artificial de Cordelia Schmid
• [3] – Código, imágenes de prueba, bibliografía de características covariantes afines mantenidas por Krystian Mikolajczyk y el Grupo de Geometría Visual del grupo de Robótica de la Universidad de Oxford.
• [4] – Bibliografía de detectores de características (y manchas) mantenida por el Instituto de Robótica y Sistemas Inteligentes de la USC
• [5] – Implementación digital del Laplaciano de Gauss

Véase también

• Afín a Hesse
• MSER
• Detector de saliencia Kadir-Brady
• Espacio de escala
• Isotropía
• Detección de esquinas
• Detección de puntos de interés
• Adaptación de forma afín
• Derivado de imagen
• Visión por computadora
• ASIFT -> Affine-Sift (un algoritmo de comparación de imágenes totalmente invariante y afín)

Referencias

1. K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Matas, F. Schaffalitzky, T. Kadir y L. Van Gool, una comparación de detectores de regiones afines. En IJCV 65(1/2):43-72, 2005
2. "Mikolajcyk, K. y Schmid, C. 2002. Un detector de puntos de interés invariante afín. En Actas de la 8.ª Conferencia Internacional sobre Visión por Computador, Vancouver, Canadá" (PDF) . Archivado desde el original (PDF) el 23 de julio de 2004. Consultado el 11 de diciembre de 2007 .
3. T. Lindeberg y J. Garding (1997). "Suavizado adaptado a la forma en la estimación de claves de profundidad 3-{D} a partir de distorsiones afines de la estructura 2-{D} local". Image and Vision Computing 15: págs. 415–434.
4. A. Baumberg (2000). "Reliable feature matching across broad separate views" (Coincidencia de características confiable en vistas muy separadas). Actas de la Conferencia IEEE sobre Visión artificial y reconocimiento de patrones: páginas I:1774–1781.
5. Lindeberg, Tony, Teoría del espacio de escala en la visión por computadora, Kluwer Academic Publishers, 1994, ISBN 0-7923-9418-6 
6. T. Lindeberg (1998). "Detección de características con selección automática de escala". Revista Internacional de Visión por Computador 30 (2): págs. 77–116.
7. Lindeberg, T. (2008). "Espacio de escala". En Wah, Benjamin (ed.). Enciclopedia de Ciencias Informáticas e Ingeniería. Vol. IV. John Wiley and Sons. págs. 2495–2504. doi :10.1002/9780470050118.ecse609. ISBN 978-0470050118.
8. C. Harris y M. Stephens (1988). "Un detector combinado de esquinas y bordes". Actas de la 4.ª Conferencia de Alvey Vision: páginas 147-151. Archivado el 16 de septiembre de 2007 en Wayback Machine.
9. K. Mikolajczyk y C. Schmid. Indexación basada en puntos de interés invariantes en la escala. En Actas de la 8.ª Conferencia Internacional sobre Visión por Computador, Vancouver, Canadá, páginas 525-531, 2001.
10. Schmid, C., Mohr, R. y Bauckhage, C. 2000. Evaluación de detectores de puntos de interés. Revista internacional de visión artificial, 37(2):151–172.
11. Mikolajczyk, K. y Schmid, C. 2004. Detectores de puntos de interés invariantes afines y de escala. Revista internacional sobre visión artificial 60(1):63-86.
12. "Filtros espaciales: Laplaciano/Laplaciano de Gauss". Archivado desde el original el 20 de noviembre de 2007. Consultado el 11 de diciembre de 2007 .
13. C. Schmid, R. Mohr y C. Bauckhage. Comparación y evaluación de puntos de interés. En International Conference on Computer Vision , págs. 230-135, 1998.
14. J. Matas, O. Chum, M. Urban y T. Pajdla, Estéreo de línea de base amplia y robusta a partir de regiones extremas de máxima estabilidad. En BMVC p. 384-393, 2002.
15. T. Tuytelaars y L. Van Gool, Coincidencia de puntos de vista muy separados en función de regiones invariantes afines. En IJCV 59(1):61-85, 2004.
16. T. Kadir, A. Zisserman y M. Brady, Un detector de regiones salientes invariante afín. En ECCV p. 404-416, 2004.
17. http://staff.science.uva.nl/~gevers/pub/overview.pdf ^{[ URL básica PDF ]}
18. R. Datta, J. Li y JZ Wang, “Recuperación de imágenes basada en contenido: enfoques y tendencias de la nueva era”, en Proc. Int. Workshop on Multimedia Information Retrieval, págs. 253-262, 2005. IEEE Transactions on Multimedia, vol. 7, núm. 1, págs. 127-142, 2005. Archivado el 28 de septiembre de 2007 en Wayback Machine.
19. J. Sivic y A. Zisserman. Vídeo google: un enfoque de recuperación de texto para la comparación de objetos en vídeos. En Actas de la Conferencia Internacional sobre Visión por Computador, Niza, Francia, 2003.
20. J. Sivic y A. Zisserman. Minería de datos de video utilizando configuraciones de regiones invariantes del punto de vista. En Actas de la Conferencia IEEE sobre Visión artificial y reconocimiento de patrones, Washington DC, EE. UU., págs. 488–495, 2004. ^{[ enlace muerto permanente ‍ ]}
21. G. Dorko y C. Schmid. Selección de vecindarios invariantes de escala para el reconocimiento de clases de objetos. En Actas de la Conferencia Internacional sobre Visión Artificial, Niza, Francia, págs. 634–640, 2003.
22. Beril Sirmacek y Cem Unsalan (enero de 2011). "Un marco probabilístico para detectar edificios en imágenes aéreas y satelitales" (PDF) . IEEE Transactions on Geoscience and Remote Sensing . 49 (1): 211–221. Bibcode :2011ITGRS..49..211S. doi :10.1109/TGRS.2010.2053713. S2CID  10637950.