How to compute the distance of a set points

Question

I have a problem about computing the distance of points. Let see my definition. I have a finite set points:

S={a_i=(a_i1,a_i2) ∈ Ω, 1<=i<=k }

where Ω is image domain, i is index of pixel.

The distance function d is tuned by parameter sigma that allows adjustment according to the number of points to be fitted:

Let I:Ω->R given by

I= [200 219 226 228 228 240 243 245 245
    212 222 229 233 241 247 248 252 252
    220 226 234 239 247 250 250 255 253
    225 231 244 248 249 248 247 253 250
    233 238 251 252 254 249 242 242 235
    243 250 255 246 250 244 230 216 200
    252 255 250 231 225 211 187 166 153
    250 249 234 213 192 164 129 111 114
    236 226 195 168 138 119 93  84  91]

Now, I want to compute distance d with a given sigma=3, I want to compute the distance d that follows the above equation. Could you help me implement it by matlab code? Thank you in advance.

Answer 1

If I'm interpreting the equation right, you have k row/column coordinates. For each pair of row/column coordinates you have ai1,ai2, you wish to compute the term inside the brackets of the expression in your post. This results in k matrices, and you'll then have a matrix d such that it's the same size as your image and it computes the product of all of these matrices together.

However, for numerical stability, if you take the logarithmic sum, add up the terms, and then take the exponential of the result, you'll get the same thing and it's actually much quicker (tip of the hat goes to Nikos M. for the tip).

I'd like to note that x seems to be dealing with image coordinates and has nothing to do with the intensities of the image itself. This makes sense given from what I read from the paper. The paper seems to stress that this distance measure looks at spatial locality of pixel locations.

In terms of ease, the quickest way to get something running would be to have a for loop that accumulates all of the results together.

Something like this:

ai1 = [3, 5, 7]; %// Example row coordinates
ai2 = [6, 8, 9]; %// Example column coordinates

%// Image defined by you
I= [200 219 226 228 228 240 243 245 245
    212 222 229 233 241 247 248 252 252
    220 226 234 239 247 250 250 255 253
    225 231 244 248 249 248 247 253 250
    233 238 251 252 254 249 242 242 235
    243 250 255 246 250 244 230 216 200
    252 255 250 231 225 211 187 166 153
    250 249 234 213 192 164 129 111 114
    236 226 195 168 138 119 93  84  91];

sigma = 3; %// Defined by you

out = zeros(size(I)); %// Define output image

%// Define 2D grid of points
[x1,x2] = ndgrid(1:size(I,1), 1:size(I,2));

for idx = 1 : numel(ai1) %// Or numel(ai2) as it's the same size
    %// Compute internal function
    p = 1 - exp(-(x1 - ai1(idx)).^2 / (2*sigma^2)).*exp(-(x2 - ai2(idx)).^2 / (2*sigma^2));

    %// Accumulate
    out = out + log(p);
end

%// Take anti-log
out = exp(out);

---

Bear in mind that the above notation is with respect to 1-indexing as MATLAB starts indexing things at 1. Traditionally, image indexing starts at 0, so if you want to start at 0, simply offset ai1 and ai2 by 1, and also in the ndgrid call, subtract the values by 1.

So, modify here:

ai1 = [3, 5, 7] - 1; %// Example row coordinates
ai2 = [6, 8, 9] - 1; %// Example column coordinates

... and here:

%// Define 2D grid of points
[x1,x2] = ndgrid(1:size(I,1), 1:size(I,2));
x1 = x1 - 1; x2 = x2 - 1;

---

I'm assuming that the zero-indexing is what is desired. As such, with the above code, I get this as the output:

out =

  Columns 1 through 8

    1.6849    1.1763    0.7129    0.3843    0.2042    0.1387    0.1508    0.2215
    1.5092    0.9580    0.4959    0.2025    0.0633    0.0242    0.0372    0.0784
    1.4192    0.8515    0.4004    0.1353    0.0236         0    0.0089    0.0249
    1.4240    0.8534    0.4032    0.1427    0.0348    0.0084    0.0057    0.0056
    1.5171    0.9519    0.4857    0.2003    0.0682    0.0208    0.0047         0
    1.6802    1.1341    0.6418    0.3054    0.1241    0.0424    0.0110    0.0029
    1.8866    1.3832    0.8733    0.4735    0.2227    0.0903    0.0304    0.0073
    2.1040    1.6730    1.1773    0.7265    0.3965    0.1940    0.0855    0.0342
    2.3020    1.9666    1.5312    1.0730    0.6811    0.4020    0.2315    0.1446

  Column 9

    0.3566
    0.1563
    0.0594
    0.0180
    0.0056
    0.0036
         0
    0.0199
    0.1250

As you can see, the row and column coordinates of what we specified in ai1 and ai2 are zero in the distance matrix while the rest of the points reflect the rough distance from each of the anchor points. It honestly looks like a watered down version of the distance transform. The zero coefficients make perfect sense. Remember, we are taking the product of all of the k matrices together for the final output, and what's going to happen is that x1 and x2 will certainly have a ai1 / ai2 pair and so the subtraction in the exponent thus leads to a 1 output, and 1 - 1 = 0, and the product of anything (except infinity) with 0 is 0.... hence the reason why there's a 0 coefficient there!