Added reduce operation #4251

homm · Dec 5, 2019

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

ImagingReduce1x2, ImagingReduce1x3, ImagingReduce2x1, ImagingReduce3x1

homm · Dec 5, 2019

src/PIL/Image.py


        return self._new(self.im.resize(size, resample, box))

+    def reduce(self, factor, box=None):


The name of the operation and argument could be discussed.

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

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

thumbs up for the current naming!

v-atamanenko

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

Tests/test_image_reduce.py

v-atamanenko · Dec 27, 2019

src/PIL/Image.py


        return self._new(self.im.resize(size, resample, box))

+    def reduce(self, factor, box=None):


thumbs up for the current naming!

src/PIL/Image.py

homm added 20 commits November 24, 2019 17:39

dummy method

335f543

naive implementation

01094a9

good balance

ab25d9f

more special

e6c3055

final set of special cases

fba833e

ImagingReduceCorners

7e978ae

tests for supported modes

8b6ad4a

better branches

f72d5c0

complete tests for supported modes

a241f1e

L mode support

008c1c8

unsupported modes

1d1f3be

Special cases:

d970a39

ImagingReduce1x2, ImagingReduce1x3, ImagingReduce2x1, ImagingReduce3x1

F mode support

a576b14

I mode support

d92c58f

Add La mode packing and unpacking

cc30b1e

add box parameter

778b5f9

add box parameter to all optimized versions

b236251

args test

5838d77

Merge branch 'master' into reduce

5283141

not square test image

b655e81

homm commented Dec 5, 2019

View reviewed changes

homm added 2 commits December 5, 2019 22:13

turn on ImagingReduce5x5 special case

e54b9b3

unused import

5283538

homm force-pushed the reduce branch from f997bf5 to 5283538 Compare December 5, 2019 19:20

Merge branch 'master' into reduce

ea9c6e9

homm mentioned this pull request Dec 17, 2019

Reduce for resize #4273

Merged

3 tasks

homm added 2 commits December 20, 2019 20:22

Merge branch 'master' into reduce

d41f271

Merge branch 'master' into reduce

dda5558

v-atamanenko reviewed Dec 27, 2019

View reviewed changes

wording

fc02488

homm merged commit 5f69035 into python-pillow:master Dec 27, 2019

homm deleted the reduce branch December 27, 2019 12:12

radarhere changed the title ~~Reduce operation~~ Added reduce operation Dec 27, 2019

radarhere mentioned this pull request Mar 20, 2020

JPEG 2000 file cannot be Image.reduce() 'd #4343

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Added reduce operation #4251

Added reduce operation #4251

Uh oh!

homm commented Dec 5, 2019 •

edited

Loading

Uh oh!

homm Dec 5, 2019

Uh oh!

homm Dec 25, 2019

Uh oh!

hugovk Dec 27, 2019

Uh oh!

v-atamanenko Dec 27, 2019

Uh oh!

v-atamanenko left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

v-atamanenko Dec 27, 2019

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants


		return self._new(self.im.resize(size, resample, box))

		def reduce(self, factor, box=None):

Search code, repositories, users, issues, pull requests...

Uh oh!

Added reduce operation #4251

Added reduce operation #4251

Uh oh!

Conversation

homm commented Dec 5, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

What is it

Why is it

Why not use resize with BOX filter?

Why so much code?

Performance

Uh oh!

homm Dec 5, 2019

Choose a reason for hiding this comment

Uh oh!

homm Dec 25, 2019

Choose a reason for hiding this comment

Uh oh!

hugovk Dec 27, 2019

Choose a reason for hiding this comment

Uh oh!

v-atamanenko Dec 27, 2019

Choose a reason for hiding this comment

Uh oh!

v-atamanenko left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

v-atamanenko Dec 27, 2019

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

homm commented Dec 5, 2019 •

edited

Loading