# 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\left(x,y\right)=min\left(r1,r2\right)$

Where

$r1={\left(p1-pc\right)}^{2}+{\left(p1\text{'}-pc\right)}^{2}$

and

$r2={\left(p2-pc\right)}^{2}+{\left(p2\text{'}-pc\right)}^{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:

with

${B}_{1}=\left(p2-p1\right)\left(p1-pc\right)+\left(p2\text{'}-p1\text{'}\right)\left(p1\text{'}-pc\right)$
${B}_{2}=\left(p2-p1\text{'}\right)\left(p1\text{'}-pc\right)+\left(p2\text{'}-p1\right)\left(p1-pc\right)$
$B=min\left({B}_{1},{B}_{2}\right)$
$C=r1$
$A=r2-r1-2B$

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

$m\left(x,y\right)

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  ```

### 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\left(x,y\right)=min\left(r1,r2,r3,r4\right)$

with

$r1={\left(p1-pc\right)}^{2}+{\left(p1\text{'}-pc\right)}^{2}$
$r2={\left(p2-pc\right)}^{2}+{\left(p2\text{'}-pc\right)}^{2}$
$r3={\left(p3-pc\right)}^{2}+{\left(p3\text{'}-pc\right)}^{2}$
$r4={\left(p4-pc\right)}^{2}+{\left(p4\text{'}-pc\right)}^{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:

with

$B1=\left(p2-p1\right)\left(p1-pc\right)+\left(p2\text{'}-p1\text{'}\right)\left(p1\text{'}-pc\right)$
$B2=\left(p3-p2\right)\left(p2-pc\right)+\left(p3\text{'}-p2\text{'}\right)\left(p2\text{'}-pc\right)$
$B3=\left(p4-p3\right)\left(p4-pc\right)+\left(p4\text{'}-p3\text{'}\right)\left(p4\text{'}-pc\right)$
$B4=\left(p1\text{'}-p4\right)\left(p4-pc\right)+\left(p1-p4\text{'}\right)\left(p4\text{'}-pc\right)$
$A1=r2-r1-2B1$
$A2=r3-r2-2B1$
$A3=r4-r3-2B1$
$A4=r1-r4-2B1$

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

$m\left(x,y\right)

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  ```