Added reduce operation

[homm]

What is it

A new operation that reduces an image size in N×M integer times. Each pixel gets an average value of N×M pixels of the source image. With N == M and N == {2, 4, 8} this operation perfectly match JPEG DCT Scaling. When the image width is divisible by N and image height is divisible by M, this operation is perfectly match .resize((im.width / N, im.height / M), Image.BOX).

Why is it

This will be used in the next Pull request in .resize() operation (through new argument) and in .thumbnail() by default. In a nutshell, it allows speed up resizing in times in some cases.

Why not use resize with BOX filter?

Two reasons:

• BOX filter is just a filter for general resizing convolution algorithm. While it's most fast of other filters, it still has many unnecessary actions, such as coefficient computation and multiplications. Direct reduce implementation is much simpler and faster.
• There is no way to get right geometry in one operation when the width is not divisible by N or image height is not divisible by M. This increases the error in the next steps.

Why so much code?

The good news is you don't have to review it all. There are:

• Special fast implementations ImagingReduce1x2, ImagingReduce1x3, ImagingReduce2x1, ImagingReduce3x1, ImagingReduce2x2, ImagingReduce3x3, ImagingReduce4x4 and ImagingReduce5x5 for predefined scales.
• Special fast implementations ImagingReduce1xN and ImagingReduceNx1 for xscale == 1 and yscale == 1.
• Most common implementation ImagingReduceNxN for any other scales.
• Common implementation ImagingReduceCorners for the last row and last column if any, which is shared across all scales.
• Only one common implementation for INT32 and FLOAT32 data types: ImagingReduceNxN_32bpc and ImagingReduceCorners_32bpc respectively.

All of them are:

• Mostly copypaste of ImagingReduceNxN and ImagingReduce2x2 with very little changes in logic (more/less columns/rows).
• Careful tested using comparations with reference image crafted from BOX filter (see TestImageReduce.compare_reduce_with_reference) and error threshold only 1 tier per channel.
• Not contain any memory allocations, error handling, other complex logic.

So basically, all you need is to carefully check the tests.

Performance

bench_reduce.py

from functools import partial
from timeit import repeat
from PIL import Image


def run_tests(name, stmt):
    print()
    print(name)
    print("=" * len(name))
    print('   ', "".join(f"{x:>6}"for x in range(1, 16)))

    for yscale in range(1, 16):
        print(f"{yscale:>3}:", end='')
        for xscale in range(1, 16):
            to_run = partial(stmt, xscale, yscale)
            runs = sorted(repeat(to_run, number=1, repeat=7))
            median_ms = sum(runs[2:-2]) / (len(runs) - 4) * 1000
            print(f" {f'{median_ms:5.1f}':>5}", end='')
        print()


im = Image.open('../imgs/space.jpeg')
im.load()
print('Size: {}x{}'.format(*im.size))


def reduce(xscale, yscale):
    return im.reduce((xscale, yscale))

def box_resize(xscale, yscale):
    size = (im.width // xscale, im.height // yscale)
    return im.resize(size, Image.BOX, (0, 0, size[0] * xscale, size[1] * yscale))

run_tests("Reduce", reduce)
run_tests("BOX resize", box_resize)

Reduce in x•y times, time in ms.

$ python ./test_reduce.py 
Size: 4928x3280

Reduce
======
         1     2     3     4     5     6     7     8     9    10    11    12    13    14    15
  1:  26.8  16.6  15.9  22.7  20.2  18.5  16.8  16.0  15.3  14.6  13.6  13.7  13.0  12.6  12.7
  2:  15.3  12.8  23.0  19.5  17.3  15.8  14.8  14.4  13.8  13.1  12.6  12.5  11.9  11.5  11.5
  3:  13.8  24.2  11.6  17.0  16.7  15.4  14.3  14.3  13.0  12.5  11.9  11.9  11.4  11.1  11.1
  4:  20.2  20.8  16.9   9.4  14.2  12.8  11.9  11.3  11.0  10.8  10.4  10.4  12.1  11.9   9.8
  5:  19.8  19.4  17.0  15.2   9.2  12.8  11.9  11.5  11.1  10.9  10.5  10.4  10.1   9.9  10.1
  6:  20.0  18.0  15.2  13.8  12.8  11.5  10.8  10.4  10.1  10.0   9.7   9.7   9.4   9.2  10.4
  7:  17.0  18.0  15.2  13.8  12.7  11.8  11.1  11.0  10.5  10.3   9.9  10.0   9.6   9.5   9.7
  8:  16.4  16.7  14.1  13.0  12.1  10.9  10.6  10.0  10.1  11.5   9.6   9.4   9.2   8.9   9.1
  9:  16.0  16.7  14.5  12.9  12.1  11.3  10.8  10.2  10.0   9.9   9.5   9.8   9.4   9.4   9.4
 10:  15.3  15.8  13.2  12.4  11.7  10.9  10.2   9.7   9.5   9.6   9.2   9.5   9.2   9.0   9.0
 11:  14.8  15.6  13.2  12.5  11.7  11.0  10.5  10.0   9.9   9.9   9.5   9.7   9.2   9.2   9.2
 12:  14.5  15.1  12.9  12.2  11.4  10.7  10.2   9.6   9.6   9.6   9.2   9.3   9.0   8.9   9.0
 13:  14.3  14.8  12.8  12.2  11.6  10.8  10.4  10.0   9.9  11.0   9.4   9.6   9.3   9.1   9.1
 14:  13.9  14.5  12.5  12.1  11.3  11.0  10.0   9.9   9.6  10.7   9.2   9.3   9.9   8.8   9.0
 15:  14.1  15.2  12.5  12.1  11.5  10.6  10.3  10.0   9.9  12.1   9.3   9.5   9.2   9.0   9.2

BOX resize
==========
         1     2     3     4     5     6     7     8     9    10    11    12    13    14    15
  1:  26.5  39.6  32.1  29.1  27.2  25.3  24.0  23.5  22.9  22.8  22.9  22.5  22.7  22.1  21.4
  2:  39.5  75.6  45.2  39.2  35.2  32.0  29.9  28.3  30.3  27.1  27.0  26.2  29.8  28.8  25.3
  3:  31.8  69.9  42.6  37.6  33.9  31.0  29.0  27.8  26.9  26.4  26.2  25.5  25.5  24.9  24.0
  4:  27.5  66.7  41.3  36.3  33.1  30.4  28.9  27.5  26.4  25.9  25.8  25.2  25.5  24.4  23.7
  5:  25.9  65.4  40.7  35.9  32.8  30.2  28.5  27.2  26.5  25.8  25.9  25.3  25.3  24.6  23.6
  6:  25.1  64.2  40.1  35.6  32.9  29.9  28.3  27.0  26.0  25.8  25.7  24.9  24.9  24.2  23.4
  7:  25.8  69.4  45.2  35.4  32.5  29.7  28.1  27.6  26.8  26.5  26.3  25.6  25.7  25.1  24.2
  8:  23.0  63.3  39.9  35.5  32.8  30.0  33.5  27.2  26.5  26.3  26.3  25.6  25.6  24.9  24.2
  9:  22.4  63.1  39.7  35.6  32.8  30.1  28.6  27.2  30.9  26.4  26.3  25.5  25.6  24.9  24.1
 10:  22.1  63.2  39.5  35.5  32.9  30.3  28.5  27.0  26.5  26.4  26.6  25.5  25.7  25.2  24.2
 11:  22.0  62.8  42.4  35.4  32.8  30.1  28.5  27.0  26.4  26.2  26.5  25.5  25.5  25.2  24.1
 12:  21.5  62.4  45.5  35.3  32.8  30.0  28.5  26.9  26.3  26.1  26.5  25.5  25.5  25.1  24.0
 13:  21.3  62.1  39.9  35.2  32.5  29.9  28.4  26.9  26.3  26.7  31.2  25.7  25.8  25.4  24.2
 14:  21.6  62.6  39.5  35.5  32.8  30.0  28.5  27.1  26.5  26.4  26.7  25.6  25.6  25.3  28.2
 15:  21.5  62.4  39.5  35.8  32.6  30.0  28.4  27.1  26.3  26.3  27.8  25.5  25.5  25.2  24.1

[homm]

The name of the operation and argument could be discussed.

[homm]

@python-pillow/pillow-team any objections to naming?

[hugovk]

Well, I can't think of a better name :)

[v-atamanenko]

thumbs up for the current naming!

[v-atamanenko]

I suggested some small corrections. On the whole, everything is well written :)

[v-atamanenko]

thumbs up for the current naming!