CODEWITHSUNDEEP
arraysmatlabeuclidean-distance
mind_
mind_

Reputation: 134

Efficient way to compute multiple euclidean distances Matlab

I am training my own self organizing map to cluster colorvalues. Now I want to make some sort of a U-matrix to show euclidean distances between the nodes and their direct neighbors. My problem now is, that my algorithm is quite unefficient!! There is certainly a way to compute this more efficiently?

function displayUmatrix(dims,weights) %#dims is [30 30], size(weights) = [900 3], 
                                      %#consisting of values between 1 and 0

hold on; 
axis off;
A = zeros(dims(1), dims(2), 3);
B = reshape(weights',[dims(1) dims(2) size(weights,1)]);
if size(weights,1)==3
    for i=1:dims(1)
        for j=1:dims(2)
            if i~=1
                if j~=1
                    A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i-1,j-1,:)).^2;
                end
                A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i-1,j,:)).^2;
                if j~=dims(2)
                    A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i-1,j+1,:)).^2;
                end
            end
            if i~=dims(1)
                if j~=1
                    A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i+1,j-1,:)).^2;
                end
                A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i+1,j,:)).^2;
                if j~=dims(2)
                    A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i+1,j+1,:)).^2;
                end
            end 
            if j~=1
                A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i,j-1,:)).^2;
            end
            if j~=dims(2)
                A(i,j,:)=A(i,j,:)+(B(i,j,:)-B(i,j+1,:)).^2;
            end
            C(i,j)=sum(A(i,j,:));
        end
    end
    D = flipud(C);
    maximum = max(max(D));
    D = D./maximum;
    imagesc(D)
else
    error('display function does only work on 3D input');
end
hold off;
drawnow;

end

Thanks, Max

Upvotes: 1

Views: 1164

Answers (1)

Josef Borkovec
Josef Borkovec

Reputation: 1079

You can calculate the (squared) distance of each point to its neigbor to the right by: 

sum((B(:,1:end-1,:) - B(:,2:end,:)).^2, 3)

Similarly, you calculate the distance of each point to the point below, and on both diagonals. You don't have all those values for points on borders so you pad them with zeros. Then you add the distances and divide them by the number of neighbors a point has to get the average distance to all the neighbors.

Here is my code:

%calculate distances to neighbors
right = sum((B(:,1:end-1,:)- B(:,2:end,:)).^2, 3);
bottom = sum((B(1:end-1,:,:)- B(2:end,:,:)).^2, 3); zeros();
diag1 = sum((B(1:end-1,1:end-1,:)- B(2:end,2:end,:)).^2, 3);
diag2 = sum((B(2:end,2:end,:)- B(1:end-1,1:end-1,:)).^2, 3);

%pad them with zeros to the correct size
rightPadded = [right zeros(dim(1) , 1)];
leftPadded = [zeros(dim(1) , 1) right];

botomPadded = [bottom; zeros(1,dim(2))];
upPadded = [zeros(1,dim(2));bottom];

bottomRight = zeros(dim(1), dim(2));
bottomRight(1:end-1,1:end-1) = diag1;
upLeft = zeros(dim(1), dim(2));
upLeft(2:end,2:end) = diag1;

bottomLeft = zeros(dim(1), dim(2));
bottomLeft(1:end-1,2:end) = diag2;
upRight = zeros(dim(1), dim(2));
upRight(2:end,1:end-1) = diag2;

%add distances to all neighbors
sumDist = rightPadded + leftPadded + bottomRight + upLeft + bottomLeft + upRight;

%number of neighbors a point has
neighborNum = zeros(dim(1), dim(2)) + 8;
neighborNum([1 end],:) = 5;
neighborNum(:,[1 end]) = 5;
neighborNum([1 end],[1 end]) = 3;

%divide summed distance by number of neighbors
avgDist = sumDist./neighborNum;

It is all vectorized, so it should be faster than your version. If you want the exact U-matrix, you can interleave the average distances with the neighboring distances.

Upvotes: 2

Related Questions