Skip to content

Added reduce operation#4251

Merged
homm merged 26 commits intopython-pillow:masterfrom
uploadcare:reduce
Dec 27, 2019
Merged

Added reduce operation#4251
homm merged 26 commits intopython-pillow:masterfrom
uploadcare:reduce

Conversation

@homm
Copy link
Copy Markdown
Member

@homm homm commented Dec 5, 2019 •
edited
Loading

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
homm commented Dec 5, 2019
View reviewed changes
Comment thread src/PIL/Image.py

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

def reduce(self, factor, box=None):
Copy link
Copy Markdown
Member Author

@homm homm Dec 5, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The name of the operation and argument could be discussed.

Copy link
Copy Markdown
Member Author

@homm homm Dec 25, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown
Member

@hugovk hugovk Dec 27, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Copy Markdown

@v-atamanenko v-atamanenko Dec 27, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

thumbs up for the current naming!

@homm homm mentioned this pull request Dec 17, 2019
Merged
3 tasks
v-atamanenko
v-atamanenko reviewed Dec 27, 2019
View reviewed changes
Copy link
Copy Markdown

@v-atamanenko v-atamanenko left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Comment thread Tests/test_image_reduce.py Outdated
Comment thread Tests/test_image_reduce.py Outdated
Comment thread Tests/test_image_reduce.py Outdated
Comment thread Tests/test_image_reduce.py Outdated
Comment thread src/PIL/Image.py

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

def reduce(self, factor, box=None):
Copy link
Copy Markdown

@v-atamanenko v-atamanenko Dec 27, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

thumbs up for the current naming!

Comment thread src/PIL/Image.py Outdated
Comment thread src/PIL/Image.py Outdated
Comment thread src/PIL/Image.py Outdated
Comment thread src/PIL/Image.py Outdated
@homm homm merged commit 5f69035 into python-pillow:master Dec 27, 2019
@homm homm deleted the reduce branch December 27, 2019 12:12
@radarhere radarhere changed the title Reduce operation Added reduce operation Dec 27, 2019
@radarhere radarhere mentioned this pull request Mar 20, 2020
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@hugovk hugovk hugovk left review comments

+1 more reviewer

@v-atamanenko v-atamanenko v-atamanenko left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@homm @hugovk @v-atamanenko