6
$\begingroup$

I wrote an algorithm to do bicubic interpolation of an image. I used the method desribed in the wikipedia page. On simple images, the result looks good, but on more complex ones, I got strange artifacts in non-smooth zones.

What could be a probable source of those artifacts, and what can I try to get rid of them ?

My code is on github, but I checked it several times, so I don't think the problem comes from it but rather from the simple implementation suggested in wikipedia

I'm using this particular equation (3rd-order Hermite polynomial interpolation) to do the interpolation (in one dimension):

$$x(n+t)=\frac{1}{2} \begin{bmatrix} 1 & t & t^2 & t^3 \\ \end{bmatrix} \begin{bmatrix} 0 & 2 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 2 & -5 & 4 & -1 \\ -1 & 3 & -3 & 1 \\ \end{bmatrix} \begin{bmatrix} x[n-1] \\ x[n] \\ x[n+1] \\ x[n+2] \\ \end{bmatrix}$$

where $x[n-1]$, ... $x[n+2]$, .. are the values of the surrounding pixels (in one dimension), and $t$ is the fractional coordinate (where $0 \le t < 1$) of the interpolated pixel between the adjacent pixels $x[n]$, $x[n+1]$. $n$ is an integer and $x(n)=x[n]$ for any integer $n$.

The expected output:

The expected output

My result, look closely at the bird head,a lot of white pixels have appeared.

My result

---EDIT--- To show that my code does produce coherent results, here is the example of my scaling up on simple image with 16 red pixels.

input 4*4 px

And here is the ouput of the library (which also use 3rd-order Hermite polynomial interpolation):

the outpout of the library 200x200

And here is my results:

the outpout of my code 200x200

In this case the difference are IMO totally acceptable, but it shows that my interpolation does something legit.

$\endgroup$
  • 3
    $\begingroup$ maybe it's just my unprofessional gaze, but i don't see much difference between the two images. where are the artifacts? in order to really test the interpolation, you need to expand or shrink the image by something like 1%, don't you? i don't see any difference in scale. since this particular Hermite cubic interpolation goes through the original values, then if you interpolate and resample at the same coordinates, you'll get the same thing back, no? $\endgroup$ – robert bristow-johnson Aug 4 '14 at 14:58
  • $\begingroup$ okay, i can sorta see that barely noticeable difference with the spots on the bird's head. what i don't get is why there is any interpolation happening at all, if you are not expanding or shrinking the image or translating the image by a distance that is a non-integer number of pixels. the interpolation $$x(t)=\frac{1}{2} \begin{bmatrix} 1 & t & t^2 & t^3 \\ \end{bmatrix} \begin{bmatrix} 0 & 2 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ 2 & -5 & 4 & -1 \\ -1 & 3 & -3 & 1 \\ \end{bmatrix} \begin{bmatrix} x[-1] \\ x[0] \\ x[1] \\ x[2] \\ \end{bmatrix}$$ shows that $x(0)=x[0]$ and $x(1)=x[1]$. $\endgroup$ – robert bristow-johnson Aug 5 '14 at 16:36
  • $\begingroup$ I'm sorry I haven't been clear. The images I posted are the result of a scaling operation on a bigger one. On the top I use a java library, on the bottom I use my implementation. I was expecting some differences due to rounding, but not that much. $\endgroup$ – gwenzek Aug 6 '14 at 12:00
  • $\begingroup$ so both images are the scaled-down result from a common source. and the scale-down ratio is identical for both. okay. personally, i would say that your cubic interpolation is doing pretty good, since only 4 neighboring points are used, two to the left and two to the right. perhaps the other algorithm, which you are using for the standard to compare to, is using many more than 4 adjacent points. maybe 8 or 12. personally, i am pretty impressed that a 3rd-order Hermite polynomial does so well for interpolation. not perfect, but pretty good. $\endgroup$ – robert bristow-johnson Aug 6 '14 at 13:26
  • $\begingroup$ The smoothing does not occur on downsampling as only few pixels from the original image are considered. The image should be either pre-smoothed (e.g. with Gaussian kernel) or a larger interpolation kernel need to be used. $\endgroup$ – Libor Aug 6 '14 at 20:19
3
$\begingroup$

What you're seeing is acutance, as described in the wikipedia article on bicubic interpolation.

However, for downsampling an image, cubic interpolation is perhaps not the ideal choice, but makes more sense for upsampling.

Note that if you're downsampling by more than a facor of 4, there will be many pixels in the original image that are simply never used in the downsampled version.

The easiest way to get around this is to downsample by iteratively taking the mean value of 4 neighbouring pixels, until you're within a factor of 2 of the desired image size. Then you can do the last part by cubic interpolation.

If you're want high quality resampling, try taking a look at the ImageMagik documentation for inspiration. In particular they recommend using windowed filters for downsampling, such as Lanczos or Sinc.

$\endgroup$
-1
$\begingroup$

I'm not sure what the problem is, but my first guess is that somehow the 16 pixels that the code is pulling from the image is getting interpreted in the wrong order.

In other words, perhaps the block of code currently

val b_1 = q(x1, x2, x3)(extracted(0), extracted(1), extracted(2), extracted(3))
val b0  = q(x1, x2, x3)(extracted(4), extracted(5), extracted(6), extracted(7))
val b1  = q(x1, x2, x3)(extracted(8), extracted(9), extracted(10), extracted(11))
val b2  = q(x1, x2, x3)(extracted(12), extracted(13), extracted(14), extracted(15))

needs to be something else, perhaps something like

val b_1 = q(x1, x2, x3)(extracted(0), extracted(4), extracted(8), extracted(12))
val b0  = q(x1, x2, x3)(extracted(1), extracted(5), extracted(9), extracted(13))
val b1  = q(x1, x2, x3)(extracted(2), extracted(6), extracted(10), extracted(14))
val b2  = q(x1, x2, x3)(extracted(3), extracted(7), extracted(11), extracted(15))

?

That sort of shuffling pixels around would give results similar to what you are seeing -- the output looks fine in "smooth" regions, but the results are more obviously wrong in non-smooth regions.

This "nonscaling" test (run the "interpolation" to generate an image of exactly the same size) is a great first test -- it should give pixel-for-pixel exactly the same output image as the input image. (Tests that expand or shrink the image, it's not as clear exactly what the output image ought to be).

I would also consider running a nonscaling test (or perhaps even a scaling test) on a very simple image, small enough that a human can single-step through every pixel in the image -- perhaps something like

0 0 0
0 5 6
0 8 9

Once you get this "nonscaling" test working, I agree with Robert that to really test the interpolation, you need to also run some tests that expand or shrink the image.

$\endgroup$
  • $\begingroup$ David, if you first expand the image by, say, 1%, that is scaling it by 1.01 , then reduce the image by a factor of 1/1.01 and then what you get out should be the same as the original image (assuming you got the edges right). at least, in audio, that's how i tested sample rate conversion algorithms. $\endgroup$ – robert bristow-johnson Aug 6 '14 at 1:40
  • $\begingroup$ Ok, thanks for the suggestion, I'll look into it. $\endgroup$ – gwenzek Aug 6 '14 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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