3
$\begingroup$

I have a grayscale image and want to "resize" it in terms of "pixel concentration".
That means I divide the source image x_old * y_old into x_new * y_new sections, and all (sub)pixel grayscale values in each section shall be accumulated to make the new grayscale value.

Writing two loops also considering the sub pixel parts in each section is easy, but doesn't seem very sophisticated.
Are there some smart and yet efficient algorithms doing the task?

$\endgroup$
  • 1
    $\begingroup$ Could you clarify what is meant by "subpixel" in a greyscale context? Is this just where a new section overlaps with a non-integer number of old pixels, and a proportional value is returned? $\endgroup$ – trichoplax Jul 2 '17 at 8:01
  • $\begingroup$ It seems worth checking whether you are only interested in this approach specifically, or whether you are just looking for the best approach to resizing. There are other approaches, and which is best will depend on the purpose of resizing and your priorities. $\endgroup$ – trichoplax Jul 2 '17 at 8:05
  • 2
    $\begingroup$ Your description sounds like box filtering which while easy is not very good in terms of quality $\endgroup$ – joojaa Jul 3 '17 at 8:16
  • $\begingroup$ @trichoplax: Your "subpixel" assumption is correct. *_new is not necessarily an integer quotient of *_old. And it's not just about resizing - I know there are better algorithms for that. Let's say that in my case each pixel value represents an amount of energy, and I want to know how much energy each pixel of a downsized image must emit when the sum of energy shall be constant. $\endgroup$ – mic Jul 3 '17 at 11:57
  • $\begingroup$ Unless you are only interested in this specific approach, it might help to edit the question to describe your underlying objectives, like the energy conservation you mentioned. $\endgroup$ – trichoplax Jul 3 '17 at 12:29
2
$\begingroup$

Long story short: downscale using a standard downscaling algorithm. Then multiply the value in each element by originalArea/scaledArea. This is what Rahul meant in the comments.

Why that works:
You can think of every output pixel as a (weighted or not) average of a neighbourhood of the source pixel. And as we know:

average = sum / count

Now, for the caveats.

Broadly, there are 3 types of downscaling algorithms:

  1. Ones that simply do resampling with some kernel
    1.1. Ones that lowpass first
    1.2. Ones that don't
  2. Pyramid downscaling
  3. Algorithms like the one in "Genuine Fractals" which are intended for detail-preserving upscaling, but could conceivably be abused for downscaling

Since "3." is not intended for downscaling, it's not useful for your case.

The problem with "1.2." is that, normally a small (e.g. 5x5) resampling kernel is used, which means that only a few of the source pixels are taken into account. In image resizing applications, this can manifest as aliasing. In your application, it can manifest as inaccuracy.

This problem with "1.2." can be fixed by using a big resampling kernel. I believe that's what the ImageMagick library used to do. E.g. taking a good-quality kernel like Lanczos and stretching it by x and y. Or you could go ahead and use a big box kernel like you describe in the question. Which one is appropriate depends on your exact application, but if you're dead set on using a box kernel, use that. The algorithm you described in the question would work fine, and I believe that on a CPU there is no better one (except splitting this one into threads), for the reason that any algorithm would need at least N (number of pixels) operations to take into account all the pixels, and your algorithm does a tiny amount of work for each of these N pixels.

But on the GPU there is a better algorithm that takes full advantage of the GPU's strong parallelism. It's called "parallel reduction", you can find info on it based on that. Since it's widely documented, I'll just sketch the algorithm:

Iteratively downscale the image by a factor of 2 by x and y until you get to your desired size.

"1.1." would probably also suit your needs, but I won't comment on it for now, as it's not much better than the other options.

$\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.