Code covered by the BSD License

# Fingerprint matching algorithm using shape context and orientation descriptors

### Joshua Abraham (view profile)

04 Nov 2010 (Updated )

Fingerprint matching code using a hybrid descriptor. EER < 1% (approx. 0.75%) on FVC2002 Db1_A.

hungarian.m
```function [C,T]=hungarian(A)
%HUNGARIAN Solve the Assignment problem using the Hungarian method.
%
%[C,T]=hungarian(A)
%A - a square cost matrix.
%C - the optimal assignment.
%T - the cost of the optimal assignment.

% Adapted from the FORTRAN IV code in Carpaneto and Toth, "Algorithm 548:
% Solution of the assignment problem [H]", ACM Transactions on
% Mathematical Software, 6(1):104-111, 1980.

% v1.0  96-06-14. Niclas Borlin, niclas@cs.umu.se.
%                 Department of Computing Science, Ume University,
%                 Sweden.
%                 All standard disclaimers apply.

% A substantial effort was put into this code. If you use it for a
% publication or otherwise, please include an acknowledgement or at least
% notify me by email. /Niclas

[m,n]=size(A);

if (m~=n)
error('HUNGARIAN: Cost matrix must be square!');
end

% Save original cost matrix.
orig=A;

% Reduce matrix.
A=hminired(A);

% Do an initial assignment.
[A,C,U]=hminiass(A);

% Repeat while we have unassigned rows.
while (U(n+1))
% Start with no path, no unchecked zeros, and no unexplored rows.
LR=zeros(1,n);
LC=zeros(1,n);
CH=zeros(1,n);
RH=[zeros(1,n) -1];

% No labelled columns.
SLC=[];

% Start path in first unassigned row.
r=U(n+1);
% Mark row with end-of-path label.
LR(r)=-1;
% Insert row first in labelled row set.
SLR=r;

% Repeat until we manage to find an assignable zero.
while (1)
% If there are free zeros in row r
if (A(r,n+1)~=0)
% ...get column of first free zero.
l=-A(r,n+1);

% If there are more free zeros in row r and row r in not
% yet marked as unexplored..
if (A(r,l)~=0 & RH(r)==0)
% Insert row r first in unexplored list.
RH(r)=RH(n+1);
RH(n+1)=r;

% Mark in which column the next unexplored zero in this row
% is.
CH(r)=-A(r,l);
end
else
% If all rows are explored..
if (RH(n+1)<=0)
% Reduce matrix.
[A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR);
end

% Re-start with first unexplored row.
r=RH(n+1);
% Get column of next free zero in row r.
l=CH(r);
% Advance "column of next free zero".
CH(r)=-A(r,l);
% If this zero is last in the list..
if (A(r,l)==0)
% ...remove row r from unexplored list.
RH(n+1)=RH(r);
RH(r)=0;
end
end

% While the column l is labelled, i.e. in path.
while (LC(l)~=0)
% If row r is explored..
if (RH(r)==0)
% If all rows are explored..
if (RH(n+1)<=0)
% Reduce cost matrix.
[A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR);
end

% Re-start with first unexplored row.
r=RH(n+1);
end

% Get column of next free zero in row r.
l=CH(r);

% Advance "column of next free zero".
CH(r)=-A(r,l);

% If this zero is last in list..
if(A(r,l)==0)
% ...remove row r from unexplored list.
RH(n+1)=RH(r);
RH(r)=0;
end
end

% If the column found is unassigned..
if (C(l)==0)
% Flip all zeros along the path in LR,LC.
[A,C,U]=hmflip(A,C,LC,LR,U,l,r);
% ...and exit to continue with next unassigned row.
break;
else
% ...else add zero to path.

% Label column l with row r.
LC(l)=r;

% Add l to the set of labelled columns.
SLC=[SLC l];

% Continue with the row assigned to column l.
r=C(l);

% Label row r with column l.
LR(r)=l;

% Add r to the set of labelled rows.
SLR=[SLR r];
end
end
end

% Calculate the total cost.
T=sum(orig(logical(sparse(C,1:size(orig,2),1))));

function A=hminired(A)
%HMINIRED Initial reduction of cost matrix for the Hungarian method.
%
%B=assredin(A)
%A - the unreduced cost matris.
%B - the reduced cost matrix with linked zeros in each row.

% v1.0  96-06-13. Niclas Borlin, niclas@cs.umu.se.

[m,n]=size(A);

% Subtract column-minimum values from each column.
colMin=min(A);
A=A-colMin(ones(n,1),:);

% Subtract row-minimum values from each row.
rowMin=min(A')';
A=A-rowMin(:,ones(1,n));

% Get positions of all zeros.
[i,j]=find(A==0);

% Extend A to give room for row zero list header column.
A(1,n+1)=0;
for k=1:n
% Get all column in this row.
cols=j(k==i)';
% Insert pointers in matrix.
A(k,[n+1 cols])=[-cols 0];
end

function [A,C,U]=hminiass(A)
%HMINIASS Initial assignment of the Hungarian method.
%
%[B,C,U]=hminiass(A)
%A - the reduced cost matrix.
%B - the reduced cost matrix, with assigned zeros removed from lists.
%C - a vector. C(J)=I means row I is assigned to column J,
%              i.e. there is an assigned zero in position I,J.
%U - a vector with a linked list of unassigned rows.

% v1.0  96-06-14. Niclas Borlin, niclas@cs.umu.se.

[n,np1]=size(A);

% Initalize return vectors.
C=zeros(1,n);
U=zeros(1,n+1);

% Initialize last/next zero "pointers".
LZ=zeros(1,n);
NZ=zeros(1,n);

for i=1:n
% Set j to first unassigned zero in row i.
lj=n+1;
j=-A(i,lj);

% Repeat until we have no more zeros (j==0) or we find a zero
% in an unassigned column (c(j)==0).

while (C(j)~=0)
% Advance lj and j in zero list.
lj=j;
j=-A(i,lj);

% Stop if we hit end of list.
if (j==0)
break;
end
end

if (j~=0)
% We found a zero in an unassigned column.

% Assign row i to column j.
C(j)=i;

% Remove A(i,j) from unassigned zero list.
A(i,lj)=A(i,j);

% Update next/last unassigned zero pointers.
NZ(i)=-A(i,j);
LZ(i)=lj;

% Indicate A(i,j) is an assigned zero.
A(i,j)=0;
else
% We found no zero in an unassigned column.

% Check all zeros in this row.

lj=n+1;
j=-A(i,lj);

% Check all zeros in this row for a suitable zero in another row.
while (j~=0)
% Check the in the row assigned to this column.
r=C(j);

% Pick up last/next pointers.
lm=LZ(r);
m=NZ(r);

% Check all unchecked zeros in free list of this row.
while (m~=0)
% Stop if we find an unassigned column.
if (C(m)==0)
break;
end

% Advance one step in list.
lm=m;
m=-A(r,lm);
end

if (m==0)
% We failed on row r. Continue with next zero on row i.
lj=j;
j=-A(i,lj);
else
% We found a zero in an unassigned column.

% Replace zero at (r,m) in unassigned list with zero at (r,j)
A(r,lm)=-j;
A(r,j)=A(r,m);

% Update last/next pointers in row r.
NZ(r)=-A(r,m);
LZ(r)=j;

% Mark A(r,m) as an assigned zero in the matrix . . .
A(r,m)=0;

% ...and in the assignment vector.
C(m)=r;

% Remove A(i,j) from unassigned list.
A(i,lj)=A(i,j);

% Update last/next pointers in row r.
NZ(i)=-A(i,j);
LZ(i)=lj;

% Mark A(r,m) as an assigned zero in the matrix . . .
A(i,j)=0;

% ...and in the assignment vector.
C(j)=i;

% Stop search.
break;
end
end
end
end

% Create vector with list of unassigned rows.

% Mark all rows have assignment.
r=zeros(1,n);
rows=C(C~=0);
r(rows)=rows;
empty=find(r==0);

% Create vector with linked list of unassigned rows.
U=zeros(1,n+1);
U([n+1 empty])=[empty 0];

function [A,C,U]=hmflip(A,C,LC,LR,U,l,r)
%HMFLIP Flip assignment state of all zeros along a path.
%
%[A,C,U]=hmflip(A,C,LC,LR,U,l,r)
%Input:
%A   - the cost matrix.
%C   - the assignment vector.
%LC  - the column label vector.
%LR  - the row label vector.
%U   - the
%r,l - position of last zero in path.
%Output:
%A   - updated cost matrix.
%C   - updated assignment vector.
%U   - updated unassigned row list vector.

% v1.0  96-06-14. Niclas Borlin, niclas@cs.umu.se.

n=size(A,1);

while (1)
% Move assignment in column l to row r.
C(l)=r;

% Find zero to be removed from zero list..

% Find zero before this.
m=find(A(r,:)==-l);

% Link past this zero.
A(r,m)=A(r,l);

A(r,l)=0;

% If this was the first zero of the path..
if (LR(r)<0)
...remove row from unassigned row list and return.
U(n+1)=U(r);
U(r)=0;
return;
else

% Move back in this row along the path and get column of next zero.
l=LR(r);

% Insert zero at (r,l) first in zero list.
A(r,l)=A(r,n+1);
A(r,n+1)=-l;

% Continue back along the column to get row of next zero in path.
r=LC(l);
end
end

function [A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR)
%HMREDUCE Reduce parts of cost matrix in the Hungerian method.
%
%[A,CH,RH]=hmreduce(A,CH,RH,LC,LR,SLC,SLR)
%Input:
%A   - Cost matrix.
%CH  - vector of column of 'next zeros' in each row.
%RH  - vector with list of unexplored rows.
%LC  - column labels.
%RC  - row labels.
%SLC - set of column labels.
%SLR - set of row labels.
%
%Output:
%A   - Reduced cost matrix.
%CH  - Updated vector of 'next zeros' in each row.
%RH  - Updated vector of unexplored rows.

% v1.0  96-06-14. Niclas Borlin, niclas@cs.umu.se.

n=size(A,1);

% Find which rows are covered, i.e. unlabelled.
coveredRows=LR==0;

% Find which columns are covered, i.e. labelled.
coveredCols=LC~=0;

r=find(~coveredRows);
c=find(~coveredCols);

% Get minimum of uncovered elements.
m=min(min(A(r,c)));

% Subtract minimum from all uncovered elements.
A(r,c)=A(r,c)-m;

% Check all uncovered columns..
for j=c
% ...and uncovered rows in path order..
for i=SLR
% If this is a (new) zero..
if (A(i,j)==0)
% If the row is not in unexplored list..
if (RH(i)==0)
% ...insert it first in unexplored list.
RH(i)=RH(n+1);
RH(n+1)=i;
% Mark this zero as "next free" in this row.
CH(i)=j;
end
% Find last unassigned zero on row I.
row=A(i,:);
colsInList=-row(row<0);
if (length(colsInList)==0)
% No zeros in the list.
l=n+1;
else
l=colsInList(row(colsInList)==0);
end
% Append this zero to end of list.
A(i,l)=-j;
end
end
end

% Add minimum to all doubly covered elements.
r=find(coveredRows);
c=find(coveredCols);

% Take care of the zeros we will remove.
[i,j]=find(A(r,c)<=0);

i=r(i);
j=c(j);

for k=1:length(i)
% Find zero before this in this row.
lj=find(A(i(k),:)==-j(k));
% Link past it.
A(i(k),lj)=A(i(k),j(k));
% Mark it as assigned.
A(i(k),j(k))=0;
end

A(r,c)=A(r,c)+m;
```

Contact us