0
$\begingroup$

I need to resize an image using bilinear interpolation and create an image pyramid. I will detect corners at the different levels of the pyramid and scale the pixel co-ordinates so that they are relative to the dimensions of the largest image.

If a corner of an object is detected as a corner/keypoint/feature in all the levels, after scaling the corresponding pixel coordinates from the different levels so that they fall on the largest image, ideally I would like them to have the same value. Thus when resizing the images, I am trying to be as accurate as possible.

Let's assume I am resizing an image L_n_minus_1 to create a smaller image L_n.

My scale factor is ratio ( with ratio > 1).

I can resize using the pseudocode below (which is what I generally find when I search online for resizing algorithms.)

I cannot use any library.

int offset = 0;
for (int i = 0; i < height_of_L_n; i++){
    for (int j = 0; j < width_of_L_n; j++){
        //********* This part will differ in the later version I provided below **********
        //
        int xSrcInt = (int)(ratio * j);
        float xDiff = ratio * j - xSrcInt;

        int ySrcInt = (int)(ratio * i);
        float yDiff = ratio * i - ySrcInt;

        //********** The above code will differ in the later version I provided below **********

        index = (ySrcInt * width_of_L_n_minus_1 + xSrcInt);

        //Get the 4 pixel values to interpolate
        a = L_n_minus_1[index];
        b = L_n_minus_1[index + 1];
        c = L_n_minus_1[index + width_of_L_n_minus_1];
        d = L_n_minus_1[index + width_of_L_n_minus_1 + 1];

        //Calculate the coefficients for interpolation
        float c0 = (1 - x_diff)*(1 - y_diff);
        float c1 = (x_diff)*(1 - y_diff);
        float c2 = (y_diff)*(1 - x_diff);
        float c3 = (x_diff*y_diff);

        //half is added for rounding the pixel intensity.
        int intensity = (a*c0) + (b*c1) + (c*c2) + (d*c3) + 0.5;

        if (intensity > 255)
            intensity = 255;

        L_n[offset++] = intensity;
    }
}

Or I could use this modified piece of code below :

int offset = 0;
for (int i = 0; i < height_of_L_n; i++){
    for (int j = 0; j < width_of_L_n; j++){

        //********* Here the code differs from the first piece of code **********
        // Assume pixel centers start from (0.5,0.5). The top left pixel has co-ordinate (0.5,0.5)
        // 0.5 is added to go to the co-ordinates where top left pixel has co-ordinate (0.5,0.5) 
        // 0.5 is subtracted to go to the generally used co-ordinates where top left pixel has co-ordinate (0,0)
        // or in other words map the new co-ordinates to array indices

        int xSrcInt = int((ratio * (j + 0.5)) - 0.5);
        float xDiff = (ratio * (j + 0.5)) - 0.5 - xSrcInt;

        int ySrcInt = int((ratio * (i + 0.5)) - 0.5);
        float yDiff = (ratio * (i + 0.5)) - 0.5 - ySrcInt;

        //********** Difference with previous code ends here ************

        index = (ySrcInt * width_of_L_n_minus_1 + xSrcInt);

        //Get the 4 pixel values to interpolate
        a = L_n_minus_1[index];
        b = L_n_minus_1[index + 1];
        c = L_n_minus_1[index + width_of_L_n_minus_1];
        d = L_n_minus_1[index + width_of_L_n_minus_1 + 1];

        //Calculate the coefficients for interpolation
        float c0 = (1 - x_diff)*(1 - y_diff);
        float c1 = (x_diff)*(1 - y_diff);
        float c2 = (y_diff)*(1 - x_diff);
        float c3 = (x_diff*y_diff);

        //half is added for rounding the pixel intensity.
        int intensity = (a*c0) + (b*c1) + (c*c2) + (d*c3) + 0.5;

        if (intensity > 255)
            intensity = 255;

        L_n[offset++] = intensity;
    }
}

The second piece of code was developed assuming pixel centers having co-ordinates like (0.5, 0.5) as they have in textures. This way the top left pixel will have co-ordinate (0.5, 0.5).

Let us assume a 2 by 2 pixel Destination Image is being resized from a 4 by 4 Source Image.

In the first piece of code, it is assumed that the first pixel has co-ordinates (0,0), thus for example my ratio is 2. Then

xSrcInt = (int)(0*2); // 0
ySrcInt = (int)(0*2); // 0

xDiff = (0*2) - 0; // 0
yDiff = (0*2) - 0; // 0

Thus effectively I will just be copying the first pixel value from the source, as c0 will be 1 and c1,c2 and c3 will be 0.

But in the second piece of code I will get

xSrcInt = (int)((0.5*2) - 0.5); // 0;
ySrcInt = (int)((0.5*2) - 0.5); // 0;

xDiff = ((0.5*2) - 0.5) - 0; // 0.5;
yDiff = ((0.5*2) - 0.5) - 0; // 0.5;

In this case c0,c1,c2 and c3 will all be equal to 0.25. Thus I will be using the 4 pixels at the top left.

There is any bug in my second piece of code. As far as visual results go they are working perfectly.

But yes I do seem to notice better alignment of keypoints with the second piece of code. But may be that's because I am judging with prejudice.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If you've described the outcome correctly, the I believe the second approach is sounder.

The first approach will cause aliasing artifacts, because it is just copying one of the four pixels into Ln from Ln_minus_1.

The second approach will effectively low pass filter Ln by averaging the four pixels from Ln_minus_1 into the one pixel of Ln.

I've made an attempt to simulate this in the graph below. The images are:

  • Top Left: The original Ln_minus_1
  • Top Right: Ln taking one lot of pixels, using the first code.
  • Bottom Left:Ln taking another lot of pixels, using the first code.
  • Bottom Right: Ln using the second code.

Note that I've added reference pixels in the diagonally opposite corners so that you can see the effect of the averaging.

enter image description here

R Code Below

#30443

N <- 10

Ln_minus_1 <- rep(1,N*N)
dim(Ln_minus_1) <- c(N,N)

for (j in seq(1,N))
{
  for (k in seq(1,N))
  {
    Ln_minus_1[j,k] = (j + k) %% 2 
  }
}

Ln <- rep(1,N*N/4)
dim(Ln) <- c(N/2,N/2)

Ln2 <- rep(1,N*N/4)
dim(Ln2) <- c(N/2,N/2)

Ln3 <- rep(1,N*N/4)
dim(Ln3) <- c(N/2,N/2)

for (j in seq(1,N/2))
{
  for (k in seq(1,N/2))
  {
    Ln[j,k] = Ln_minus_1[2*j,2*k]
    Ln2[j,k] = Ln_minus_1[2*j-1,2*k]
    Ln3[j,k] = (Ln_minus_1[2*j,2*k] + Ln_minus_1[2*j-1,2*k-1] + Ln_minus_1[2*j,2*k-1] +Ln_minus_1[2*j-1,2*k] )/4
  }
}

par(mfrow=c(2,2), pty='s')
image(Ln_minus_1)
title('Ln_minus_1')

Ln[1,1] <- 0
Ln[N/2,N/2] <- 1
image(Ln) 
title('Ln no averaging v 1')

Ln2[1,1] <- 0
Ln2[N/2,N/2] <- 1
image(Ln2)
title('Ln no averaging v 2')

Ln3[1,1] <- 0
Ln3[N/2,N/2] <- 1
image(Ln3)
title('Ln with averaging')
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks a lot Peter for your great answer. Yes it works poorly when scale factors are like 2, 3, etc, which should imply bad accuracy but what is hard to notice is the difference when scale factor is something like 1.7, images produced by the two codes look the same. What I need to assure is that keypoints corresponding to the same corner detected in different levels (different resized images) map to the same point when they are all superimposed on the largest image after scaling. It is very hard to quantify but the second approach seems to be slightly better. Thanks again. $\endgroup$
    – PineTree
    May 3, 2016 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.