Calculate Euclidean distance between RGB vectors in a large matrix

Question

I have this RGB matrix of a set of different pixels. (N pixels => n rows, RGB => 3 columns). I have to calculate the minimum RGB distance between any two pixels from this matrix. I tried the loop approach, but because the set is too big (let's say N=24000), it looks like it will take forever for the program to finish. Is there another approach? I read about pdist, but the RGB Euclidean distance cannot be used with it.

k=1;
for i = 1:N
    for j = 1:N
        if (i~=j)
            dist_vect(k)=RGB_dist(U(i,1),U(j,1),U(i,2),U(j,2),U(i,3),U(j,3))
        k=k+1;
        end
    end
end

Euclidean distance between two pixels: So, pdist syntax would be like this: D=pdist2(U,U,@calc_distance());, where U is obtained like this:

rgbImage = imread('peppers.png');
rgb_columns = reshape(rgbImage, [], 3)    
[U, m, n] = unique(rgb_columns, 'rows','stable');

But if pdist2 does the loops itself, how should I enter the parameters for my function?

function[distance]=RGB_dist(R1, R2, G1, G2, B1, B2),

where R1,G1,B1,R2,G2,B2 are the components of each pixel.

I made a new function like this:

function[distance]=RGB_dist(x,y)

  distance=sqrt(sum(((x-y)*[3;4;2]).^2,2));

end

and I called it D=pdist(U,U,@RGB_dist); and I got 'Error using pdist (line 132) The 'DISTANCE' argument must be a string or a function.'

Testing RGB_dist new function alone, with these input set

x=[62,29,64;
    63,31,62;
    65,29,60;
    63,29,62;
    63,31,62;];


d=RGB_dist(x,x);
disp(d);

outputs only values of 0.

Answer 1

Contrary to what your post says, you can use the Euclidean distance as part of pdist. You have to specify it as a flag when you call pdist.

The loop you have described above can simply be computed by:

dist_vect = pdist(U, 'euclidean');

This should compute the L2 norm between each unique pair of rows. Seeing that your matrix has a RGB pixel per row, and each column represents a single channel, pdist should totally be fine for your application.

If you want to display this as a distance matrix, where row i and column j corresponds to the distance between a pixel in row i and row j of your matrix U, you can use squareform.

dist_matrix = squareform(dist_vect);

As an additional bonus, if you want to find which two pixels in your matrix share the smallest distance, you can simply do a find search on the lower triangular half of dist_matrix. The diagonals of dist_matrix are going to be all zero as any vector whose distance to itself should be 0. In addition, this matrix is symmetric and so the upper triangular half should be equal to the lower triangular half. Therefore, we can set the diagonal and the upper triangular half to Inf, then search for the minimum for those elements that are remaining. In other words:

indices_to_set = true(size(dist_matrix));
indices_to_set = triu(indices_to_set);
dist_matrix(indices_to_set) = Inf;
[v1,v2] = find(dist_matrix == min(dist_matrix(:)), 1);

v1 and v2 will thus contain the rows of U where those RGB pixels contained the smallest Euclidean distance. Note that we specify the second parameter as 1 as we want to find just one match, as what your post has stated as a requirement. If you wish to find all vectors who match the same distance, simply remove the second parameter 1.

---

Edit - June 25th, 2014

Seeing as how you want to weight each component of the Euclidean distance, you can define your own custom function to calculate distances between two RGB pixels. As such, instead of specifying euclidean, you can specify your own function which can calculate the distances between two vectors within your matrix by calling pdist like so:

pdist(x, @(XI,XJ) ...);

@(XI,XJ)... is an anonymous function that takes in a vector XI and a matrix XJ. For pdist you need to make sure that the custom distance function takes in XI as a 1 x N vector which is a single row of pixels. XJ is then a M x N matrix that contains multiple rows of pixels. As such, this function needs to return a M x 1 vector of distances. Therefore, we can achieve your weighted Euclidean distance as so:

weights = [3;4;2];
weuc = @(XI, XJ, W) sqrt(bsxfun(@minus, XI, XJ).^2 * W);
dist_matrix = pdist(double(U), @(XI, XJ) weuc(XI, XJ, weights));

bsxfun can handle that nicely as it will replicate XI for as many rows as we need to, and it should compute this single vector with every single element in XJ by subtracting. We thus square each of the differences, weight by weights, then take the square root and sum. Note that I didn't use sum(X,2), but I used vector algebra to compute the sum. If you recall, we are simply computing the dot product between the square distance of each component with a weight. In other words, x^{T}y where x is the square distance of each component and y are the weights for each component. You could do sum(X,2) if you like, but I find this to be more elegant and easy to read... plus it's less code!

Now that I know how you're obtaining U, the type is uint8 so you need to cast the image to double before we do anything. This should achieve your weighted Euclidean distance as we talked about.

As a check, let's put in your matrix in your example, then run it through pdist then squareform

x=[62,29,64;
63,31,62;
65,29,60;
63,29,62;
63,31,62];
weights = [3;4;2];
weuc = @(XI, XJ, W) sqrt(bsxfun(@minus,XI,XJ).^2 * W);
%// Make sure you CAST TO DOUBLE, as your image is uint8
%// We don't have to do it here as x is already a double, but 
%// I would like to remind you to do so!
dist_vector = pdist(double(x), @(XI, XJ) weuc(XI, XJ, weights));
dist_matrix = squareform(dist_vector)

dist_matrix =

     0    5.1962    7.6811    3.3166    5.1962
5.1962         0    6.0000    4.0000         0
7.6811    6.0000         0    4.4721    6.0000
3.3166    4.0000    4.4721         0    4.0000
5.1962         0    6.0000    4.0000         0

As you can see, the distance between pixels 1 and 2 is 5.1962. To check, sqrt(3*(63-62)^2 + 4*(31-29)^2 + 2*(64-62)^2) = sqrt(3 + 16 + 8) = sqrt(27) = 5.1962. You can do similar checks among elements within this matrix. We can tell that the distance between pixels 5 and 2 is 0 as you have made these rows of pixels the same. Also, the distance between each of themselves is also 0 (along the diagonal). Cool!