l'image de fond

fr       en

Interest Points Detection

Trajkovic corner detection algorithm

4 neighbour Method

This corner detection use a circle to find the intensity of variations between pixels. Let's take the below circle:

Thanks to this circle, we perform the next computation:

d ( x , y ) = min ( r 1 , r 2 )

Where

r 1 = ( p 1 - p c ) 2 + ( p 1 ' - p c ) 2

and

r 2 = ( p 2 - p c ) 2 + ( p 2 ' - p c ) 2

The coordinates x and y correspond to the center of the circle pc. This computation allows to determine the potential corner of the image. Pixels having a value enough important are considered as potential corners. For each potential corners, we performe the calculation of the minimal variation among all directions thanks to the next algorithm:

m ( x , y ) = { C - B 2 A  if  B < 0  and  ( A + B ) > 0 d ( x , y )  otherwise  }

with

B 1 = ( p 2 - p 1 ) ( p 1 - p c ) + ( p 2 ' - p 1 ' ) ( p 1 ' - p c )
B 2 = ( p 2 - p 1 ' ) ( p 1 ' - p c ) + ( p 2 ' - p 1 ) ( p 1 - p c )
B = min ( B 1 , B 2 )
C = r 1
A = r 2 - r 1 - 2 B

Then, we remove all values of m matrice which are below a threshold T

m ( x , y ) < T = 0

Then, a local maxima detection is applyed.

4 neighbour Program

clear all;
close all;
[filename, pathname] = uigetfile({'*.jpg;*.tif;*.png;*.gif;*.bmp','All Image Files';...
          '*.*','All Files' },'mytitle',...
          'C:\Work\myfile.jpg')
img = imread(filename);
img=mean(img,3);
[ligneorigine colonneorigine]=size(img);
 
taille=1;
%effet de bord
img = wextend(2,'zpd',img,1);
[ligne colonne]=size(img);
d=zeros(ligne,colonne);
 
for i = taille+1 : ligne-(taille+1)
    for j = taille+1 : colonne -(taille+1)
        d(i,j)=min( (img(i,j-1)-img(i,j))^2+(img(i,j+1)-img(i,j))^2 ,...
                    (img(i-1,j)-img(i,j))^2+(img(i+1,j)-img(i,j))^2 );
    end
    i
end

threshold = 50;
d(d<=threshold)=0;
d(d>threshold)=1;
m=zeros(ligne,colonne);

%threshold = 35000;
for i = taille+1 : ligne-(taille+1)
    for j = taille+1 : colonne -(taille+1)
        if d(i,j)~=0
            c=min( (img(i,j-1)-img(i,j))^2+(img(i,j+1)-img(i,j))^2 ,...
                    (img(i-1,j)-img(i,j))^2+(img(i+1,j)-img(i,j))^2 );
            B1= (img(i-1,j)-img(i,j-1))*(img(i,j-1)-img(i,j))+(img(i+1,j)-img(i,j+1))*(img(i,j+1)-img(i,j));
            B2= (img(i-1,j)-img(i,j+1))*(img(i,j+1)-img(i,j))+(img(i+1,j)-img(i,j-1))*(img(i,j-1)-img(i,j));
            RA=(img(i,j-1)-img(i,j))^2+(img(i,j+1)-img(i,j))^2;
            RB=(img(i-1,j)-img(i,j))^2+(img(i+1,j)-img(i,j))^2;
            C= RA;
            B=min(B1,B2);
            A= RB-RA-2*B;
            if B<0 && (A+B)>0
                m(i,j)=C-(B^2/A);
            else
                m(i,j)=c;
            end
        else
            m(i,j)=0;
        end
    end
    i
end

m = m(taille:end-taille-1,taille:end-taille-1);
threshold = 1000;
m(m<=threshold)=0;
 
[imax,vmax]= maxlocaux(m,10);
figure(  'name','détection de coin Trajkovic 4 voisins',...
            'NumberTitle','off',...
            'MenuBar','none',...
            'color',[0.3137 0.3137 0.5098]);
imshow(uint8(img))
hold on
nb=200;
if length(imax)>nb
    nbcorner = nb;
else
    nbcorner=length(imax);
end
for i = 1 :  nbcorner %length(imax)
    plot([vmax(i,2)-2 vmax(i,2)-2 vmax(i,2)+2 vmax(i,2)+2 vmax(i,2)-2],...
        [vmax(i,1)-2 vmax(i,1)+2 vmax(i,1)+2 vmax(i,1)-2 vmax(i,1)-2] ,'r','LineWidth',1)
end


 

4 neighbour Example



8 neighbour Method

An improuvement of the first version can be to take 8 neighbour rather than 4. This improuvement of number of variation onto the circle allows to erase some errors due to the noise. Let's take the next circle:

Then, Equations become:

d ( x , y ) = min ( r 1 , r 2 , r 3 , r 4 )

with

r 1 = ( p 1 - p c ) 2 + ( p 1 ' - p c ) 2
r 2 = ( p 2 - p c ) 2 + ( p 2 ' - p c ) 2
r 3 = ( p 3 - p c ) 2 + ( p 3 ' - p c ) 2
r 4 = ( p 4 - p c ) 2 + ( p 4 ' - p c ) 2

Thanks to this computation, we determine the potantial corners of the image. For each potential corners, we compute the minimal variation for all directions thanks to the next algorithm:

m ( x , y ) = { d ( x , y )  if  B i ≥ 0  or  A i + B i ≤ 0  for  ∀ i = 1,2 ,3,4 min( r i - B i 2 A i )  if  B i < 0  and  A i + B i > 0  for  ∀ i = 1,2 ,3,4 }

with

B 1 = ( p 2 - p 1 ) ( p 1 - p c ) + ( p 2 ' - p 1 ' ) ( p 1 ' - p c )
B 2 = ( p 3 - p 2 ) ( p 2 - p c ) + ( p 3 ' - p 2 ' ) ( p 2 ' - p c )
B 3 = ( p 4 - p 3 ) ( p 4 - p c ) + ( p 4 ' - p 3 ' ) ( p 4 ' - p c )
B 4 = ( p 1 ' - p 4 ) ( p 4 - p c ) + ( p 1 - p 4 ' ) ( p 4 ' - p c )
A 1 = r 2 - r 1 - 2 B 1
A 2 = r 3 - r 2 - 2 B 1
A 3 = r 4 - r 3 - 2 B 1
A 4 = r 1 - r 4 - 2 B 1

Then, we remove all values of m matrice which are below a threshold T

m ( x , y ) < T = 0

and a local maxima detection is applyed

8 neighbour Program

clear all;
close all;
[filename, pathname] = uigetfile({'*.jpg;*.tif;*.png;*.gif;*.bmp','All Image Files';...
          '*.*','All Files' },'mytitle',...
          'C:\Work\myfile.jpg')
img = imread(filename);
img=mean(img,3);
[ligneorigine colonneorigine]=size(img);
 
taille=2;
%effet de bord
img = wextend(2,'zpd',img,1);

[ligne colonne]=size(img);
d=zeros(ligne,colonne);
 
for i = taille+1 : ligne-(taille+1)
    for j = taille+1 : colonne -(taille+1)
            A=img(i-1,j);
            Ap=img(i+1,j);
            B=img(i,j-1);
            Bp=img(i,j+1);
            C=img(i,j);
            D=img(i-1,j-1);
            Dp=img(i+1,j+1);
            E=img(i-1,j+1);
            Ep=img(i+1,j-1);
           
            RA=(A-C)^2+(Ap-C)^2;
            RB=(B-C)^2+(Bp-C)^2;
            RD=(D-C)^2+(Dp-C)^2;
            RE=(E-C)^2+(Ep-C)^2;
           
        d(i,j)=min([RA,RB,RD,RE]);
    end
    i
end



threshold = 50;
d(d<=threshold)=0;

m=zeros(ligne,colonne);

for i = taille+1 : ligne-(taille+1)
    for j = taille+1 : colonne -(taille+1)
        if d(i,j)~=0
            A=img(i-1,j);
            Ap=img(i+1,j);
            B=img(i,j-1);
            Bp=img(i,j+1);
            C=img(i,j);
            D=img(i-1,j-1);
            Dp=img(i+1,j+1);
            E=img(i-1,j+1);
            Ep=img(i+1,j-1);
           
            B1= (B-A)*(A-C)+(Bp-Ap)*(Ap-C);
            B2= (D-B)*(B-C)+(Dp-Bp)*(Bp-C);
            B3= (E-D)*(E-C)+(Ep-Dp)*(Ep-C);
            B4= (Ap-E)*(E-C)+(A-Ep)*(Ep-C);
           
           
            RA=(A-C)^2+(Ap-C)^2;
            RB=(B-C)^2+(Bp-C)^2;
            RD=(D-C)^2+(Dp-C)^2;
            RE=(E-C)^2+(Ep-C)^2;
           
            A1=RB-RA-2*B1;
            A2=RD-RB-2*B2;
            A3=RE-RD-2*B3;
            A4=RA-RE-2*B4;
           

            if max([B1,B2,B3,B4])<0 && min([(A1+B1),(A2+B2),(A3+B3),(A4+B4)])>0
                D1=RA - (B1^2/A1);
                D2=RB - (B2^2/A2);
                D3=RD - (B3^2/A3);
                D4=RE - (B4^2/A4);
                m(i,j)=min([D1,D2,D3,D4]);
            else
                m(i,j)=min([RA,RB,RD,RE]);
            end
        else
            m(i,j)=0;
        end
    end
    i
end
 
m = m(taille:end-taille-1,taille:end-taille-1);
[ligne colonne]=size(img);
 
radius=10;
[imax,vmax]= maxlocaux(m,radius);
figure(  'name','détection de coin Trajkovic 4 voisins',...
            'NumberTitle','off',...
            'color',[0.3137 0.3137 0.5098]);
imshow(uint8(img))
hold on
nb=200;
if length(imax)>nb
    nbcorner = nb;
else
    nbcorner=length(imax);
end
for i = 1 :  nbcorner %length(imax)
    plot([vmax(i,2)-2 vmax(i,2)-2 vmax(i,2)+2 vmax(i,2)+2 vmax(i,2)-2],...
        [vmax(i,1)-2 vmax(i,1)+2 vmax(i,1)+2 vmax(i,1)-2 vmax(i,1)-2] ,'r','LineWidth',1)
end
 

8 neighbour example



Copyright © 2010-2014, all rights reserved, contact: operationpixel@free.fr