Crop before resize in Fill

[charlie-collard]

83 Crop before resizing in the Fill function for the sake of efficiency.

This breaks one test, TestFill/Fill_4x4_2x8_Top_Nearest and I'm afraid I'm not sure why, I'm pretty sure the code is correct as all other tests pass, but maybe there's a strange edge case I'm not thinking of.

I've also added some benchmarks for the Fill function, on my machine I get speedups of around 8x:

Before

goos: windows
goarch: amd64
pkg: github.com/bspammer/imaging
BenchmarkFill/Vertical_NearestNeighbor_JPEG-8                500       3501987 ns/op     7393248 B/op         17 allocs/op
BenchmarkFill/Vertical_NearestNeighbor_PNG-8                 500       3370063 ns/op     7393200 B/op         17 allocs/op
BenchmarkFill/Vertical_Linear_JPEG-8                         100      10374025 ns/op     9178134 B/op         38 allocs/op
BenchmarkFill/Vertical_Linear_PNG-8                          100      10154148 ns/op     9178224 B/op         38 allocs/op
BenchmarkFill/Vertical_CatmullRom_JPEG-8                     100      13472248 ns/op     9260050 B/op         38 allocs/op
BenchmarkFill/Vertical_CatmullRom_PNG-8                      100      13222394 ns/op     9260042 B/op         38 allocs/op
BenchmarkFill/Vertical_Lanczos_JPEG-8                        100      17240083 ns/op     9341974 B/op         38 allocs/op
BenchmarkFill/Vertical_Lanczos_PNG-8                         100      17819746 ns/op     9341968 B/op         38 allocs/op
BenchmarkFill/Horizontal_NearestNeighbor_JPEG-8             1000       1852933 ns/op     4049702 B/op         17 allocs/op
BenchmarkFill/Horizontal_NearestNeighbor_PNG-8              1000       1690025 ns/op     4049702 B/op         17 allocs/op
BenchmarkFill/Horizontal_Linear_JPEG-8                       300       5520155 ns/op     4931467 B/op         38 allocs/op
BenchmarkFill/Horizontal_Linear_PNG-8                        300       5296951 ns/op     4931474 B/op         38 allocs/op
BenchmarkFill/Horizontal_CatmullRom_JPEG-8                   200       6946002 ns/op     4988816 B/op         38 allocs/op
BenchmarkFill/Horizontal_CatmullRom_PNG-8                    200       6746117 ns/op     4988812 B/op         38 allocs/op
BenchmarkFill/Horizontal_Lanczos_JPEG-8                      200       9024805 ns/op     5046154 B/op         38 allocs/op
BenchmarkFill/Horizontal_Lanczos_PNG-8                       200       8829919 ns/op     5046162 B/op         38 allocs/op
PASS
ok      github.com/bspammer/imaging 30.481s

After

goos: windows
goarch: amd64
pkg: github.com/bspammer/imaging
BenchmarkFill/Vertical_NearestNeighbor_JPEG-8               3000        404434 ns/op      479008 B/op         12 allocs/op
BenchmarkFill/Vertical_NearestNeighbor_PNG-8                3000        411429 ns/op      479006 B/op         12 allocs/op
BenchmarkFill/Vertical_Linear_JPEG-8                        2000        877495 ns/op      790118 B/op         38 allocs/op
BenchmarkFill/Vertical_Linear_PNG-8                         2000        878994 ns/op      790120 B/op         38 allocs/op
BenchmarkFill/Vertical_CatmullRom_JPEG-8                    2000       1154835 ns/op      826726 B/op         38 allocs/op
BenchmarkFill/Vertical_CatmullRom_PNG-8                     2000       1149338 ns/op      826732 B/op         38 allocs/op
BenchmarkFill/Vertical_Lanczos_JPEG-8                       1000       1681033 ns/op      862314 B/op         38 allocs/op
BenchmarkFill/Vertical_Lanczos_PNG-8                        1000       1723007 ns/op      862314 B/op         38 allocs/op
BenchmarkFill/Horizontal_NearestNeighbor_JPEG-8             5000        285236 ns/op      550748 B/op         12 allocs/op
BenchmarkFill/Horizontal_NearestNeighbor_PNG-8             10000        240661 ns/op      550747 B/op         12 allocs/op
BenchmarkFill/Horizontal_Linear_JPEG-8                      2000        969941 ns/op      963304 B/op         38 allocs/op
BenchmarkFill/Horizontal_Linear_PNG-8                       2000        925467 ns/op      963306 B/op         38 allocs/op
BenchmarkFill/Horizontal_CatmullRom_JPEG-8                  1000       1210303 ns/op      999915 B/op         38 allocs/op
BenchmarkFill/Horizontal_CatmullRom_PNG-8                   2000       1172325 ns/op      999916 B/op         38 allocs/op
BenchmarkFill/Horizontal_Lanczos_JPEG-8                     1000       1801962 ns/op     1035500 B/op         38 allocs/op
BenchmarkFill/Horizontal_Lanczos_PNG-8                      1000       1838941 ns/op     1035501 B/op         38 allocs/op
PASS
ok      github.com/bspammer/imaging 30.730s

[disintegration]

Thank you! I will review the changes next weekend.

[disintegration]

This breaks one test, TestFill/Fill_4x4_2x8_Top_Nearest and I'm afraid I'm not sure why

It's because the new algorithm crops the source image to 1x4px first. So it takes a second pixel column and resizes it to 2x8px. The old algorithm provides a more accurate result for such a small image. Here's a visual representation using letters in place of pixels.

Source image      New result      Old result

ABCD              BB               BC         
EFGH              BB               BC         
IKLM              FF               FG         
NPQR              FF               FG         
                  KK               KL         
                  KK               KL         
                  PP               PQ         
                  PP               PQ         

[charlie-collard]

Ah I understand, it's because the new algorithm crops so that the pre-resize aspect ratio matches the post-resize aspect ratio. This means that it selects the 1x4 BFKP column because it matches the 0.25 aspect ratio of the destination image.

In order to get the more accurate result, I think we'd have to crop to subpixels before we did the resize. The 1x4 selection would be half column BFKP and half column CGLQ. Upscale these subpixels and, in theory, out pops the correct 2x8 image. In reality, I think we'd have to crop to include any pixel which is fractionally in the selection, resize to the desired height, then crop again to the desired width.

This is getting a bit convoluted for a fairly minor performance gain. Should I try to implement this? I'd be happy to give it a go, but if you think the final code would be too messy for the library then feel free to just close the pull request :)

[disintegration]

Sorry for the delayed response.

Here's another example where the old algorithm does better job. The 3x3 checkers image is scaled to 100x125px. Ideally the individual pixels should be transformed to squares.

func main() {
    src := &image.Gray{
        Rect:   image.Rect(0, 0, 3, 3),
        Stride: 3,
        Pix: []uint8{
            0, 255, 0,
            255, 0, 255,
            0, 255, 0,
        },
    }
    dst := imaging.Fill(src, 100, 125, imaging.TopLeft, imaging.NearestNeighbor)
    imaging.Save(dst, "dst.jpg")
}

Old result	New result

Ah I understand, it's because the new algorithm crops so that the pre-resize aspect ratio matches the post-resize aspect ratio. This means that it selects the 1x4 BFKP column because it matches the 0.25 aspect ratio of the destination image.

In order to get the more accurate result, I think we'd have to crop to subpixels before we did the resize. The 1x4 selection would be half column BFKP and half column CGLQ. Upscale these subpixels and, in theory, out pops the correct 2x8 image. In reality, I think we'd have to crop to include any pixel which is fractionally in the selection, resize to the desired height, then crop again to the desired width.

This is getting a bit convoluted for a fairly minor performance gain. Should I try to implement this? I'd be happy to give it a go, but if you think the final code would be too messy for the library then feel free to just close the pull request :)

I think this would work. On the other hand the additional cropping step is the downside of this approach.

After doing some tests, it looks like the new algorithm works fine most of the times. If the size of the original image is not too small, we have enough pixels in both directions to make the initial crop with the desired aspect ratio. We could fallback to the old algorithm for images smaller than, say, 100x100px.

if srcW >= 100 && srcH >= 100 {
    cropAndResize(...)
} else {
    resizeAndCrop(...)
}

[coveralls]

Coverage decreased (-1.2%) to 98.819% when pulling 4ae66ee5699ae44efd821054a55894e0d3bcc082 on bspammer:crop_before_resize into 9458da53d1e65e098d48467a4317c403327e4424 on disintegration:master.

[coveralls]

Coverage decreased (-0.1%) to 99.882% when pulling 26f80372420aa44d8e61c6d09df4ee7eeecf294b on bspammer:crop_before_resize into 9458da53d1e65e098d48467a4317c403327e4424 on disintegration:master.

[charlie-collard]

I've added the fallback, and updated the documentation. I did try the subpixel method but was still getting inconsistent results, so I think this is a good solution.

I'm guessing the two new functions need tests, it seems to me that the current tests for Fill could also be used for resizeAndCrop as it has identical functionality to the old Fill.

As for cropAndResize, I'm unsure. If it's meant to be used solely for large images then maybe a few golden examples will do?

[disintegration]

Sure, for resizeAndCrop we can use the existing test cases. As for cropAndResize, despite the fact that it's meant to be used with larger images, in tests we just want to ensure that the algorithm works as intended, so I think we still can use a few small-sized test cases. A golden test would be nice to have too.

[disintegration]

Thank you!