3
$\begingroup$

I'm trying to implement image downscaling using a triangle filter (it's narrow therefore fast, and goes hand in hand with linear interpolation when upscaling), and the triangle function used for filtering has a span proportional to the downscaling ratio.

artifacts

Alas when the ratio is non-integer, grid artifacts appear (as shown above) on the downscaled image. The following plot shows what happens with the way triangles for each pixel of the input image overlap and add up in those cases:

plot

I don't know what I should do to fix/work around this, but I'm sure this problem must have been encountered by others before (Google was no help).

$\endgroup$
  • 2
    $\begingroup$ Nice demonstration. You're correct: when the resampling ratio isn't an integer, then each pixel in the output image experiences a differing amount of weighting from the corresponding input pixels (shown by the nonuniformity in your animation. You need to calculate and adjust for this gain on a per-pixel when doing your resampling. You know how to calculate it already. $\endgroup$ – Jason R Nov 20 '15 at 18:10
  • $\begingroup$ Very nice animation! $\endgroup$ – Peter K. Nov 20 '15 at 19:32
  • $\begingroup$ Thanks @JasonR, I went with a somewhat equivalent solution that changes the kernel instead of normalising the output. See dsp.stackexchange.com/a/27319/18381 $\endgroup$ – Michel Rouzic Nov 26 '15 at 13:06
1
$\begingroup$

I went with Jason R's idea of adjusting the linear filtering, except I didn't like the idea of doing a division on every output pixel, using more than just a simple kernel or how normalising that way would ruin the smooth borders. So instead I modified the kernel itself, which it turns out is done by flattening the peak of the triangle.

image

It seems like a pretty good solution, and you can see how the sum of the triangles progresses into something resembling a Gaussian function.

Here's how it's done, first of all there's a 'knee' joining the flat top with the rest of the triangle. It ping-pongs on the horizontal axis between 0 and 0.5 like so. Note: $n$ is the scale multiplier for the width of the kernel and the size of the downscaling, it's always 1 or lower, it's the reciprocal of the number displayed at the top of the animation. The smaller $n$, the smaller the output image, the wider the kernel over the original image.

$knee = 0.5 - |(n^{-1} \mod 1) - 0.5|$

Next we need to calculate the height of the top of the flattened triangle, which is done like this:

$m = \lfloor n^{-1} + 0.5\rfloor$

$top = \frac{1 - knee \cdot n}{2m - nm^2}$

And finally we turn it into an affine function which we can use directly when calculating weights:

$c_1 = \frac{-top}{n^{-1}-knee}$

$c_0 = \frac{-c_1}{n}$

The above is calculated only once and $knee$, $top$, $c_1$ and $c_0$ are stored and used when computing weights like this:

$$f(x) = \begin{cases} \hfill top \hfill & \text{ if $|x| \leq knee$ } \\ \hfill c_1 x + c_0 \hfill & \text{ if $knee < |x| \leq n^{-1}$ } \\ \hfill 0 \hfill & \text{ otherwise } \\ \end{cases}$$

$\endgroup$

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.