# Vectorizing a polar coordinate conversion loop in a fingerprint-matching process

I am working on a fingerprint matching technique and it takes a lot of computation time to obtain the result. I am trying to implement the matching process given in A Minutia Matching Algorithm in Fingerprint Verification. I would like to know if there is any method available to reduce the for loop for this code:

[Tdrow,Tdcol]=size(Td);
[Idrow,Idcol]=size(Id);
matchingscore=zeros(Tdrow,Idrow);
rv = bsxfun(@minus,Td(:,3),permute(Id(:,3),[2 1]));
%convert each minutiae point to polar coordinates with respect to the
%reference minutiae in each case
for i=1:Tdrow
for j=1:Idrow
Tdp=zeros(Tdrow,Tdcol);
Idp=zeros(Idrow,Idcol);
tref=Td(i,:);
iref=Id(j,:);
Tdp(:,1)=sqrt((Td(:,1)-tref(1)).^2 + (Td(:,2)-tref(2)).^2);
Tdp(:,2)=mod(atan2(tref(1)-Td(:,1),Td(:,2)-tref(2)) * 180/pi,360);
Tdp(:,3)=mod(Td(:,3)-tref(3),360);
Tdp(:,4)=Td(:,4);
Idp(:,1)=sqrt((Id(:,1)-iref(1)).^2 + (Id(:,2)-iref(2)).^2);
Idp(:,2)=mod((atan2(iref(1)-Id(:,1),Id(:,2)-iref(2)) * 180/pi) + rv(i,j),360);
Idp(:,3)=mod(Id(:,3)-iref(3),360);
Idp(:,4)=Id(:,4);
Tdp1 {i,j}= Tdp(:,:);
Idp1 {i,j}= Idp(:,:);
end
end


Here, the variable Td is the fingerprint template to be compared and Id is the input fingerprint template. Both Td and Id have four columns, i.e. 1st and 2nd column provide x and y coordinate respectively, 3rd column is the angle and 4th column is the type of minutiae. Tdp and Idp are calculated using the equation provided in the attachment provided in the link.

Can this code be vectorized? I understand that the indexes have hardly been used. But without changing the index i cannot continue to the further steps. It would be very helpful is anyone could provide me with any suggestions.

The data values are available on Google Drive. These has both the input data and output data.

• You would be more likely to get an answer if you provided some sample input, expected output, and an explanation, so that we don't need to reverse-engineer your code. Note that MathJax is available. Jun 13 '16 at 21:23
• @200_success I have attached the data values. Jun 13 '16 at 22:09
• I struggle a bit reading this code... Not because it is bad, but because T and I look so similar. Is it correct that it takes about 2-3 seconds, when it's not warmed up? Are you running this code many times in a row in a loop, or is it a one time thing? If it's a process you're doing manually, then your time is probably best spent working on some other part of your project. Relevant xkcd. Jun 21 '16 at 15:10
• @stewie. Thank you for taking a look at it. But yes it runs in a loop several times. But it turns out my input to this section was sometimes 1000x4 matrix. But it shouldn't have exceeded 80x4. This code works good now. Jul 7 '16 at 4:50
• (This is a year and a half after the fact, blame Jamal for editing old posts...) Don't do this Tdp1{i,j}= Tdp(:,:);. Do this instead Tdp1{i,j}= Tdp;. I don't know how clever the MATLAB interpreter is, but it's likely expensive redundancy. Jan 11 '18 at 22:14

You said your code works good, as the input isn't too big, so I won't go ahead an try to vectorize this. So, I've provided a general review of the code.

Overall your code looks nice. You should however attempt to have a bit more spaces

[Tdrow, Tdcol] = size(Td);  <-- This
[Tdrow,Tdcol]=size(Td);     <-- Not this


There are only a few things I would do differently in the code:

1. You can speed this up quite a bit even without vectorization: The size of the cells Tdp1 and Idp1 are known, so these cells can be pre-allocated in front of the loop:

[Tdp1{1:Tdrow, 1:Idrow}] = zeros(Tdrow, Tdcol);
[Idp1{1:Tdrow, 1:Idrow}] = zeros(Idrow, Idcol);


This way you avoid creating Tdrow*Idrow arrays inside the loop. That should save you some time.

2. Tdp(:,:) is the same as just Tdp, so you can do:

Tdp1{ii,jj} = Tdp;

3. Note, ii and jj are better than i and j as iterator names in Matlab.

4. You are converting angles from radians to degrees a few places atan2(x,y) * 180 / pi. Instead, use atan2d(x,y). It returns the value in degrees directly.

Without trying to understand your code too much, it's obvious that your double loop needs to be a single loop. This is the code inside the loop:

        tref=Td(i,:);
iref=Id(j,:);


Here you extract tref and iref, which depend in i and j, respectively. Then you compute:

        Tdp(:,1)=sqrt((Td(:,1)-tref(1)).^2 + (Td(:,2)-tref(2)).^2);
Tdp(:,2)=mod(atan2(tref(1)-Td(:,1),Td(:,2)-tref(2)) * 180/pi,360);
Tdp(:,3)=mod(Td(:,3)-tref(3),360);
Tdp(:,4)=Td(:,4);


This part does not depend on j or in iref. This should not be inside the loop over j. Next you compute:

        Idp(:,1)=sqrt((Id(:,1)-iref(1)).^2 + (Id(:,2)-iref(2)).^2);
Idp(:,2)=mod((atan2(iref(1)-Id(:,1),Id(:,2)-iref(2)) * 180/pi) + rv(i,j),360);
Idp(:,3)=mod(Id(:,3)-iref(3),360);
Idp(:,4)=Id(:,4);


This part does not dpeend on tref or i, nor on Tdp. This should not be inside the loop over i.

[Tdrow,Tdcol]=size(Td);
[Idrow,Idcol]=size(Id);
rv = bsxfun(@minus,Td(:,3),permute(Id(:,3),[2 1]));
for i=1:Tdrow
Tdp=zeros(Tdrow,Tdcol);
tref=Td(i,:);
Tdp(:,1)=sqrt((Td(:,1)-tref(1)).^2 + (Td(:,2)-tref(2)).^2);
Tdp(:,2)=mod(atan2(tref(1)-Td(:,1),Td(:,2)-tref(2)) * 180/pi,360);
Tdp(:,3)=mod(Td(:,3)-tref(3),360);
Tdp(:,4)=Td(:,4);
Tdp1{i,:}=Tdp;
end
for j=1:Idrow
Idp=zeros(Idrow,Idcol);
iref=Id(j,:);
Idp(:,1)=sqrt((Id(:,1)-iref(1)).^2 + (Id(:,2)-iref(2)).^2);
Idp(:,2)=mod((atan2(iref(1)-Id(:,1),Id(:,2)-iref(2)) * 180/pi) + rv(i,j),360);
Idp(:,3)=mod(Id(:,3)-iref(3),360);
Idp(:,4)=Id(:,4);
Idp1{:,j}=Idp;
end


And once you do that you notice the symmetry of the problem, you only need to write one of these loops, and re-use it by reversing the inputs.

Weird though, that you are never comparing Id to Td. What does this code do? And why do you need to populate Tdp1 and Idp1 with repeated arrays?

Are you sure this code is correct?

Using longer names would simplify things: Id becomes input, Td becomes template, etc. It would make it a lot easier to spot issues, since I and T look so much alike.