Detector de región afín de Harris

El algoritmo detector de esquinas de Harris se basa en un principio fundamental: en una esquina, la intensidad de la imagen cambia considerablemente en múltiples direcciones. Esto también puede formularse examinando los cambios de intensidad debidos a desplazamientos en una ventana local. Alrededor de un punto de esquina, la intensidad de la imagen cambia notablemente cuando la ventana se desplaza en una dirección arbitraria. Siguiendo esta intuición y mediante una ingeniosa descomposición, el detector de Harris utiliza la matriz de segundo momento como base para sus decisiones de esquina. (Véase detección de esquinas para una derivación más completa). La matriz${\displaystyle A}$También se la ha llamado matriz de autocorrelación y tiene valores estrechamente relacionados con las derivadas de la intensidad de la imagen .

${\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}}}$

dónde${\displaystyle I_{x}}$y${\displaystyle I_{y}}$son las derivadas respectivas (de la intensidad del píxel) en el${\displaystyle x}$y${\displaystyle y}$dirección en el punto (${\displaystyle p}$,${\displaystyle q}$);${\displaystyle p}$y${\displaystyle q}$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${\displaystyle I_{x}}$y${\displaystyle I_{y}}$, mientras que las entradas diagonales son los cuadrados de las derivadas respectivas . La función de ponderación${\displaystyle w(x,y)}$puede ser uniforme, pero más típicamente es una gaussiana circular isotrópica,

${\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 como un promedio en una región local, dando mayor peso a los valores cercanos al centro.

Resulta que esto${\displaystyle A}$La 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${\displaystyle \lambda _{1}}$y${\displaystyle \lambda _{2}}$sean los valores propios de${\displaystyle A}$, entonces 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${\displaystyle A}$Una matriz centrada en los puntos de esquina tendrá dos autovalores grandes y positivos. ^{[ 8 ]} En lugar de extraer estos autovalores utilizando métodos como la descomposición en valores singulares , se utiliza la medida de Harris basada en la traza y el determinante:

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

dónde${\displaystyle \alpha }$es una constante. Los puntos de esquina tienen valores propios grandes y positivos, y por lo tanto tendrían una medida de Harris grande. Así, los puntos de esquina se identifican como máximos locales de la medida de Harris que superan un umbral específico.

${\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{umbral}}\end{aligned}}}$

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

Una representación en el espacio de escala gaussiano de una imagen es el conjunto de imágenes que resultan de la convolución de un núcleo gaussiano de varios 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} )}$

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

${\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, pueden adaptarse a una representación en el espacio de escalas calculando esta medida utilizando un conjunto de escalas recursivamente donde${\displaystyle n}$la escala es${\displaystyle s_{n}=k^{n}s_{0}}$Consulte el espacio de escala para obtener una descripción más completa.

El detector Harris-Laplace combina el detector de esquinas Harris 2D tradicional con la idea de una representación de espacio de escala gaussiana para crear un detector invariante a la escala. Los puntos de esquina 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 a la escala y, por lo tanto, la matriz de segundo momento debe modificarse para reflejar una propiedad de invariancia a la escala. Denotemos,${\displaystyle M=\mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$como la matriz de segundo momento adaptada a la escala utilizada en el detector de Harris-Laplace.

${\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 ]}

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

Partiendo de 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 .

El algoritmo realiza búsquedas sobre 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${\displaystyle k=1.4}$. Para cada escala de integración,${\displaystyle \sigma _{I}}$De este conjunto, se elige la escala de diferenciación apropiada como un factor constante de la escala de integración:${\displaystyle \sigma _{D}=s\sigma _{I}}$. Mikolajczyk y Schmid (2004) utilizaron${\displaystyle s=0.7}$. ^{[ 11 ]} Utilizando estas escalas, los puntos de interés se detectan mediante una medida de Harris en el${\displaystyle \mu (\mathbf {x} ,\sigma _{\mathit {I}},\sigma _{\mathit {D}})}$matriz. La condición de esquina, al igual que la medida típica de Harris, se define como:

${\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 de Harris tradicional, los puntos de esquina son aquellos máximos locales (vecindario de 8 puntos) de la característica de esquina que están por encima de un umbral especificado.

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.${\displaystyle \mathbf {x} }$que fueron detectados inicialmente a gran escala${\displaystyle \sigma _{I}}$mediante el detector Harris multiescala (${\displaystyle k}$indica el${\displaystyle kth}$iteración):

• Elige la escala${\displaystyle \sigma _{I}^{(k+1)}}$que maximiza el Laplaciano de Gaussianos (LoG) sobre un rango predefinido de escalas vecinas. Las escalas vecinas se eligen típicamente de un rango que se encuentra dentro de un vecindario de dos escalas . Es decir, si los puntos originales se detectaron utilizando un factor de escala de${\displaystyle 1.4}$Entre escalas sucesivas, un vecindario de espacio de dos escalas es el rango${\displaystyle t\in [0.7,\dots ,1.4]}$Por lo tanto, las escalas gaussianas examinadas son:${\displaystyle \sigma _{I}^{(k+1)}=t\sigma _{I}^{k}}$La medida LoG se define como:

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

dónde${\displaystyle L_{xx}}$y${\displaystyle L_{yy}}$son las segundas derivadas en sus respectivas direcciones. ^{[ 12 ]} La${\displaystyle \sigma _{I}^{2}}$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 vecindario de dos espacios de escala se considera la escala característica ,${\displaystyle \sigma _{I}^{(k+1)}}$y se utiliza en iteraciones posteriores. Si no se encuentra ningún extremo o máximo del LoG, este punto se descarta para búsquedas futuras.

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

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

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

${\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})}$

dónde${\displaystyle \Sigma _{I}}$y${\displaystyle \Sigma _{D}}$son matrices de covarianza que definen las escalas del núcleo gaussiano de diferenciación e integración. Aunque esto pueda parecer significativamente diferente de la matriz de segundo momento en el detector de Harris-Laplace, de hecho, es idéntica. La anterior${\displaystyle \mu }$La matriz era la versión isotrópica 2D en la que las matrices de covarianza${\displaystyle \Sigma _{I}}$y${\displaystyle \Sigma _{D}}$eran matrices identidad de 2x2 multiplicadas por factores${\displaystyle \sigma _{I}}$y${\displaystyle \sigma _{D}}$respectivamente. En la nueva formulación, se puede pensar en los núcleos gaussianos como distribuciones gaussianas multivariadas en contraposición a un núcleo gaussiano uniforme. Un núcleo gaussiano uniforme puede considerarse como una región circular isotrópica. De manera similar, un núcleo gaussiano más general define un elipsoide. De hecho, los autovectores y autovalores 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 cual queremos integrar o diferenciar.

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

${\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}}}$

dónde${\displaystyle \Sigma _{I,b}}$y${\displaystyle \Sigma _{D,b}}$son las matrices de covarianza para la${\displaystyle b}$marco de referencia. Si continuamos con esta formulación y reforzamos que

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

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

${\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 del segundo momento,${\displaystyle M^{\tfrac {1}{2}}}$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.${\displaystyle R}$Estas nuevas regiones isotrópicas pueden considerarse como un marco de referencia normalizado. Las siguientes ecuaciones formulan la relación entre los puntos normalizados.${\displaystyle x_{R}^{'}}$y${\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 discutió con el detector de Harris, los valores propios y los vectores propios de la matriz de segundo momento,${\displaystyle M=\mu (\mathbf {x} ,\Sigma _{I},\Sigma _{D})}$caracterizan la curvatura y la forma de las intensidades de los píxeles. Es decir, el vector propio asociado al mayor valor propio indica la dirección del mayor cambio y el vector propio asociado al menor valor propio define la dirección del menor cambio. En el caso bidimensional, 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. Esto ocurre 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 {\mathcal {Q}}={\frac {\lambda _{\min }(M)}{\lambda _{\max }(M)}}}$

dónde${\displaystyle \lambda }$denota valores propios. Esta medida tiene el rango${\displaystyle [0\dots 1]}$. Un valor de${\displaystyle 1}$corresponde a una isotropía perfecta.

Utilizando este marco matemático, el algoritmo 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 está suficientemente cerca de uno. El algoritmo utiliza esta matriz de adaptación de forma ,${\displaystyle U}$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 debería tener una medida isotrópica cercana a uno en la iteración final. En cada${\displaystyle k}$En la iteración , cada región de interés se define mediante varios parámetros que el algoritmo debe descubrir:${\displaystyle U^{(k)}}$matriz, posición${\displaystyle \mathbf {x} ^{(k)}}$escala de integración${\displaystyle \sigma _{I}^{(k)}}$y escala de diferenciación${\displaystyle \sigma _{D}^{(k)}}$. Debido a que el detector calcula la matriz de segundo momento en el dominio transformado, es conveniente denotar esta posición transformada como${\displaystyle \mathbf {x} _{w}^{(k)}}$dónde${\displaystyle U^{(k)}\mathbf {x} _{w}^{(k)}=\mathbf {x^{(k)}} }$.