UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE INGENIERÍA

Procesamiento Digital de Imágenes

Proyecto final “Detectores de esquinas”

Integrantes:Pacheco Estrada FernandoReynoso Martínez Alejandro

SEMESTRE 2013-2

INTRODUCCIÓN:

Podemos definir al borde de una imagen como puntos que tiene un alto valor del gradiente mientras que las esquinas con puntos prominentes contenidos en una imagen, caracterizados por presentar también un alto valor del gradiente pero a diferencia de los bordes, este alto valor del gradiente no solo se manifiesta en una dirección sino en diferente.

Las esquinas pueden ser utilizadas en una amplia gama de aplicaciones tales como el seguimiento de un objeto en secuencia de video, para ordenar las estructuras de objetos en visión estereoscópica, como puntos de referencia en la medición de características geométricas de objetos o bien en la calibración de cámaras para sistemas de visión. Algunas de las ventajas de las esquinas sobre otras características obtenidas de una imagen no son la robustez al cambio de perspectiva así como su confiablidad en su localización ante diferentes condiciones de luz.

Un algoritmo para la detección de las esquinas debe reunir algunos aspectos importantes tales como:

Detectar esquinas “importantes” de las “no importantes” Detectar las esquinas en presencia del ruido propio de la imagen Rápida ejecución para permitir su implementación en tiempo real

Como es de suponer, existen varios enfoques que son capaces de cumplir con estas características en donde la mayoría de ellos se basan en la medición del valor del gradiente en el punto que se considera como potencialmente esquina.

La mayoría de los algoritmos utilizados para la detección de esquinas utilizan el criterio de la primera o segunda derivada sobre la imagen en la dirección x o y como aproximación del valor del gradiente.

OBJETIVOS:

Comparar distintos algoritmos de detección de esquinas para determinar cuál de ellos es el mejor.

Desarrollo:

Algoritmo de Harris:

El cálculo se basa en la primera derivada parcial en un pixel I(x,y) en dirección horizontal y vertical.Para cada pixel de la imagen (x,y) son calculados tres diferentes cantidades que serán denominadas HE11(x,y), HE22(x,y) y HE12(x,y), donde:

HE11 ( x , y )=I x2 ( x , y )

HE22 ( x , y )=I x2 ( x , y )

HE12 ( x , y )=I x ( x , y ) · I y ( x , y )

Estos valores pueden ser interpretados como aproximaciones de los elementos de la matriz de estructuras denominada como HE tal que:

HE=[HE11 HE12HE21 HE22 ]Donde HE12 = HE21

Para encontrar las esquinas con este algoritmo es necesario suavizar los valores de cada uno de los elementos de la matriz de estructuras mediante su convolución por un filtro Gaussiano tal que:

E=[HE11∗H σ HE12∗H σ

HE21∗H σ HE22∗H σ]=[A CC B ]

El algoritmo de Harris utiliza una propiedad significativa, esta la implementa como medida de valor de la esquina la función es la siguiente:

V ( x , y )=det (E )−α (tr (E ) )2

Aplicado a nuestro caso la función sería la siguiente:

V ( x , y )=( A·B−C2 )−α ( A+B )2

Donde el parámetro α controla la sensibilidad del algoritmo.

Un punto de la imagen (x,y) es considerado como punto esquina potencial si la condición

V ( x , y )>t h

Se cumple. Donde th es el umbral y normalmente su valor típico se encuentra dentro del intervalo de 900 a 10000, dependiendo del contenido de la imagen. A partir de esta condición se tendrá una matriz binaria conteniendo unos donde la condición fue cumplida y ceros donde no lo fue.

Esquinas calculadas mediante el algoritmo de Harris:

Todos los siguientes algoritmos se basan en el cálculo de alguna operación desarrollada con la matriz Hessiana o el Hessiano.

La matriz Hessiana de una función f de n variables, es la matriz cuadrada de nxn, de las segundas derivadas parciales. Por lo que dada una función real f de 2 variables reales:

f=( x , y )

Si todas las segundas derivas parciales de f existen, se define la matriz Hessiana de f como

H f ( x , y )=[ ∂2 f (x , y)∂2 x2

∂2 f ( x , y )∂x ∂ y

∂2 f (x , y)∂x ∂ y

∂2 f ( x , y )∂2 y2

]Normalmente son definidas las componentes del Hessiano como:

I xx=∂2 f ( x , y )∂2 x2

I yy=∂2 f (x , y)∂2 y2

I xy=∂2 f (x , y )∂ x∂ y

Algoritmo de Beaudet:

El detector de Beaudet es un operador isotrópico basado en el cálculo del determinante del Hessiano:

det (H f ( x , y ) )=I xx I yy−I xy2

De tal forma que bajo este operador serán consideradas como esquinas aquellos puntos de B(x,y) que sobrepasen o sean iguales a un determinado umbral prefijado.

Algoritmo de Kitchen & Rosenfeld.

Ellos propusieron un detector de esquinas en el cambio de la dirección del gradiente a lo largo de un borde multiplicado por la dirección del gradiente local en el pixel en cuestión, propusieron calcular la siguiente matriz.

KR ( x , y )=(I¿¿xx I y2+ I yy I x

2−I xy I y❑)/ (I¿¿ x2+ I y

2)¿¿

En este enfoque se considera a las esquinas como aquellos valores que sobrepasen un valor prefijado considerado como umbral.

Algoritmo de Wang & Brady

Para la detección de esquinas considera una imagen como una superficie, de tal forma que el algoritmo busca lugares en imagen donde la dirección de un borde cambia abruptamente, como es el caso de las esquinas. Para ello se mide el coeficiente C(x,y) que se establece para cada pixel definido como:

C ( x , y )=∇2 I ( x , y )+C|∇ I ( x , y )|

De esta manera se define el operador

∇ I ( x , y )=[ 0 −0.5 0−0.5 0 0.50 0.5 0 ]

Y:

∇2 I ( x , y )=[0 1 01 −4 10 1 0]

Código:

Algoritmo de Harris%Limpiamosclear();clc();ruido = 'speckle';%Leeemos imagen y convertimos a escala de grisesIma=imread('tren.jpg');Ir = rgb2gray(Ima);%Ir = imnoise(Ir, ruido, 0.2);%Guardamos dimensiones de la imagen en una matriz[m n]=size(Ir);

%Declaramos matrices donde pondremos resultados y las llenamos con cerosV1=zeros(size(Ir));S=zeros(size(Ir)); %Filtro de 3x3 normalizadoh=ones(3,3)/9; %Convertimos imagen a doubleId=double(Ir); %Aplicamos filtro lineal a la imagenIf=imfilter(Id,h); %Filtro Sobel para X e YHx=[-0.5 0 0.5];Hy=[-0.5; 0; 0.5]; %Aplicamos el filtro Sobel a la imagen anterior ya filtradaIx=imfilter(If,Hx);Iy=imfilter(If,Hy); %Obtenemos los valores X e Y de la imagen filtrada y los guardamos en HE11=Ix.*Ix;HE22=Iy.*Iy;HE12=Ix.*Iy; %Filtro Gaussiano normalizadoHg=[0 1 2 1 0; 1 3 5 3 1; 2 5 9 5 2; 1 3 5 3 1; 0 1 2 1 0];Hg=Hg*(1/57); %Aplicamos el filtro Gaussiano a los componentes de la imagen filtrada%anteriormenteA=imfilter(HE11,Hg);B=imfilter(HE22,Hg);C=imfilter(HE12,Hg); %Variable para sensibilidad de detección de esquinas%alfa=-0.0001;alfa=0.04; %Obtenemos el valor de la esquinaRp=A+B;Rp1=Rp.*Rp; %Ecuación de Harris para detectar las esquinasQ=((A.*B)-(C.*C))-(alfa*Rp1); %Guardamos aquellos valores mayores a 1000 de la ec. anteriorV1=Q>1000; %Cantidad de valores de vecindad que va a tomar en cuenta el pixel en%cuestiónpixel=10; %Leemos imagen (filas y columnas)for r=1:m for c=1:n if(V1(r,c)) fprintf('calculando\n');

%Pixeles que se encuentren en los 4 márgenes de la imagen %Izquierdo, Dereho, Superior e Inferior I1=[r-pixel 1]; I2=[r+pixel m]; I3=[c-pixel 1]; I4=[c+pixel n]; %Guardamos valores Máximos y minimos de los pixeles calculados %anteriormente datxi=max(I1); datxs=min(I2); datyi=max(I3); datys=min(I4); %Calculamos y guardamos el valor máximo de la vecindad de los %pixeles calculados Bloc=Q(datxi:1:datxs,datyi:1:datys); MaxB=max(max(Bloc)); %Si Encontramos el valor máximo, ponemos valor de 1 en la matriz S if(Q(r,c)==MaxB) S(r,c)=1; end end endend %Mostramos imagenimshow(Ir); %Mostramos resultados, marcando las esquinas con un '+'hold onfor r=1:m for c=1:n if(S(r,c)) plot(c,r,'+'); end endend

Algoritmo de Beaudetclear();clc();Iorig=imread('tren.jpg');Im=double(rgb2gray(Iorig));h=ones(3)/9;Im=imfilter(Im,h);sx=[-1,0,1;-2,0,2; -1,0,1];sy=[-1,-2,-1; 0,0,0; 1,2,1];Ix=imfilter(Im,sx);Iy=imfilter(Im,sy);Ixx=imfilter(Ix,sx);Iyy=imfilter(Iy,sy);Ixy=imfilter(Ix,sy);B=(1+Ix.*Ix+Iy.*Iy).^2;A=Ixx.*Iyy-(Ixy).^2;B=(A./B);B=(1000/max(max(B)))*B;V1=(B)>100;

pixel=10;[n,m]=size(V1);res=zeros(n,m);for r=1:n for c=1:m if(V1(r,c)) I1=[r-pixel,1]; I1=max(I1); I2=[r+pixel,n]; I2=min(I2); I3=[c-pixel,1]; I3=max(I3); I4=[c+pixel,m]; I4=min(I4); tmp=B(I1:I2,I3:I4); maxim=max(max(tmp)); if(maxim==B(r,c)) res(r,c)=1; end end endendimshow(uint8(Im));hold on[re,co]=find(res');plot(re,co,'+');

Algoritmo de Kitchen&Rosenfield

clear();clc();Iorig=imread('objetos3.jpg');Im=rgb2gray(Iorig);h=ones(3)/9;Im=imfilter(Im,h);sx=[-1,0,1;-2,0,2; -1,0,1];sy=[-1,-2,-1; 0,0,0; 1,2,1];Ix=imfilter(Im,sx);Iy=imfilter(Im,sy);Ixx=imfilter(Ix,sx);Iyy=imfilter(Iy,sy);Ixy=imfilter(Ix,sy);A=(Ixx.*(Iy.^2))+(Iyy.*(Ix.^2))-(2*Ixy.*Iy);B=(Ix.^2)+(Iy.^2);V=(A./B);V=( 1000/max(max(V)))*V;V1=(V)>100;pixel=10;[n,m]=size(V1;)res=zeros(n,m);for r=1:n for c=1:m if(V1(r,c)) I1=[r-pixel,1]; I1=max(I1); I2=[r+pixel,n]; I2=min(I2); I3=[c-pixel,1]; I3=max(I3); I4=[c+pixel,m];

I4=max(I4); tmp=V(I1:I2,I3:I4); maxim=max(max(tmp)); if(maxim==V(r,c)) res(r,c)=1; end end endendimshow(uint8(Im));hold on[re, co]=find(res');plot(re,co,'+');

Algoritmo de Wang&Bradey

clear();clc();Iorig=imread('objetos3.bmp');Im=rgb2gray(Iorig);h=ones(3)/9;Im=imfilter(Im,h);d1=[0,-0.5,0;-0.5,0,0.5;0,0.5,0];d2=[0,1,0;1,-4,1;0,1,0];I1=imfilter(Im,d1);I2=imfilter(Im,d2);c=1;V=(I2-c*abs(I1));V=(1000/max(max(V)))*V;V1=(V)>100;pixel=10;[n,m]=size(V1);res=zeros(n,m);for r=1:n for c=1:m if(V1(r,c)) I1=[r-pixel,1]; I1=max(I1); I2=[r+pixel,n]; I2=min(I2); I3=[c-pixel,1]; I3=max(I3); I4=[c+pixel,m]; I4=max(I4); tmp=V(I1:I2,I3:I4); maxim=max(max(tmp)); if(maxim==V(r,c)) res(r,c)=1; end end endendimshow(uint8(Iorig));hold on[re, co]=find(res');plot(re,co,'+');

CONCLUSIONES:

En el desarrollo de esta práctica pudimos comparar varios de los algoritmos más importantes para la detección de esquinas, algunos desde los más básicos hasta los más precisos como lo es el algoritmo de Harris, ya que al hacer la comparación de todos estos nos dimos cuenta que seleccionaba las esquinas fundamentales, mientras que los demás detectan esquinas y también algunos bordes, ya que para el ojo humano es muy fácil detectar esquinas, sin embargo para la computadora es muy complicado y se tiene que hacer uso de estos algoritmos matemáticos.

Bibliografía:

- Procesamiento digital de imágenes con Matlab y SIMULINK, alfaomega, Erick Cuevas, Daniel Zaldivar, Marco Pérez Cisneros, 2010.