12 ms·
Pillow-SIMD – Fast, production-ready image resize for x86
- gfody 9y ago> I wasn’t building it for fun: I work for Uploadcare and resizing images has always been a practical issue with on-the-fly image processing. you ever consider pushing the work entirely to the client with a resize implemented in javascript? that would cut down on bandwidth as well.
- nneonneo 9y agoHe's scaling images down, not up. Think taking an uploaded smartphone picture (multiple megapixels) and scaling it down to thumbnail-sized images for various screens.
- gfody 9y agoic - I thought it was just the usual image-downsample-and-upload thing you see everywhere. even so, if the service is hosting your images in multiple resolutions you could do it all client side at upload time. they'd be trading bandwidth for cpu time.
- striking 9y agoBandwidth is more valuable than CPU time when communicating across the wider internet.
- igordebatur 9y agoUploadcare supports shrinking images before uploading, https://uploadcare.com/documentation/widget/#image-shrink https://uploadcare.com/documentation/widget/#image-shrink (I'm one of co-founders)
- homm 9y agoIt's exactly what my previous article "Image resize in browsers is broken" is about ) https://blog.uploadcare.com/image-resize-in-browsers-is-broken-e38eed08df01 https://blog.uploadcare.com/image-resize-in-browsers-is-brok... It originally was written two years ago, so some things have changed. But in general, it is still correct: for most browsers, you need to combine several ugly technics to get suitable results. Though, the quality will have nothing common with quality when you have direct access to hardware.
- vortico 9y agoLooks fantastic! Are there other bottlenecks, such as JPEG encoding and decoding that can be ported to SIMD code in Pillow?
- lcnmrn 9y agoNo, that’s handled by libjpeg which can be replaced by libjpeg-turbo but nothing else at the moment.
- ttoinou 9y agoHave you tried to use a fast blur (like StackBlur for example : http://www.quasimondo.com/BoxBlurForCanvas/FastBlur2Demo.html http://www.quasimondo.com/BoxBlurForCanvas/FastBlur2Demo.htm... , the radius should be computed according to the ratio between original size and target size) as a first step before taking the classic nearest neighbor ? And also try to make an algorithm that resize to multiple resolution at the same time could improve speed I take an image of 2560x1600 pixels in size and resize it to the following resolutions: 320x200, 2048x1280, and 5478x3424 So you are also upscaling ?
- vadiml 9y agoGreat work and great article. One question though: Did you consider to replace convolution based filters by FFT based ones ?
- stagger87 9y agoFor small filter sizes, convolution is going to be faster than an FFT approach. Plus, correct me if I'm wrong, but you need to perform a convolution for every output pixel where the filter kernel is different for each convolution (Sampling the lanczos filter at different points depending on the resample ratio), which would really slow down an FFT approach.
- pishpash 9y agoBeyond the mismatched signal size, the FFT approach creates circular convolutions, which is not what you want in images. You'd need windowing or a larger effective signal size, and pay the cost of conversions back and forth.
- deleted 9y ago[deleted]
- homm 9y agoNo. As I can see, no one uses FFT for image scaling. I guess because of it much slower.
- cyphar 9y agoIt's a bit of a misnomer to talk about a distinction between convolution and FFT. By the convolution theorem, the two are mathematically equivalent. In addition, on paper, FFT-based convolution scales much better than traditional convolution because it reduces the complexity from O(n^2) to O(n log n). I haven't done the benchmarks for a fully optimised implementation, but comparing naive implementations you can easily tell that FFT-based is much faster (even with all of the tricks that MATLAB does to optimise sparse matrix operations).
- vadiml 9y agoGreat work and great article. One question though: Did you consider to replace convolution based filters by FFT based ones ?
- Asooka 9y agoLet me insert my personal pet-peeve: have you thought of making it colour-space-aware? Most (all?) images you'll encounter are stored in sRGB colourspace, which isn't linear, so you can't do the convolution by just multiplying and adding (the result will be slightly off). The easiest way would be to convert it to 16-bit-per-channel linear colour space using a lookup table, do the convolution in linear 16-bit space, then convert back to 8-bit sRGB.
- pishpash 9y agoFor that matter, the conversion should be to CIELAB, which is perceptually uniform.
- pornel 9y agoNo, it shouldn't be done in perceptually uniform color space. LAB, like sRGB, is non-linear. Resampling simulates physical properties of the light, not subjective perception of the eye.
- jacobolus 9y agoResampling in CIELAB space tends to work better than resampling in gamma-adjusted R′G′B′ space, because at least you never end up averaging two pixels and getting a lightness which is outside the range of input lightnesses, which is what causes the worst artifacts in R′G′B′. A linear space will give a better result, but CIELAB results are usually acceptable.
- lcrs 9y agoPerceptual uniformity is in some ways opposite to the linearization suggested above - the L* component of CIELAB is much more like the gamma-encoded values of sRGB than a linear light measure. It seems tough to come up with hard and fast rules for whether to mimic the linear physical processes, or work in a perceptual space more like the human visual system. I'd love to hear about more rigorous work in this area - most things I read have boiled down to "this way works better on these images". It's interesting for example that using Sinc-type filters to resize truly linear data, like that from HDR cameras, usually gives rise to horrible dark haloing artifacts around small specular highlights, despite that being the most "physically correct" way to do it. Doing the same operation in a more perceptual space immediately sorts out the problem.
- MuffinFlavored 9y ago> With optimizations, Uploadcare now needs six times fewer servers to handle its load than before. This is devil's advocate, but did you guys have concrete need for this optimization? You now need six times fewer servers, but was that a crippling problem, or is it a cool statistic for the future when you get more users?
- igordebatur 9y agoNow we're a little happier every time AWS send their bills
- girvo 9y agoOne can make an argument that the CO2 and energy cost for wasted server usage is a decent reason for it! 6x fewer is not a small amount, that's a great result.
- dmitrymukhin 9y agoI thought this was in article already :)
- FridgeSeal 9y agoDoes it need to be a crippling problem before you do anything about it? Even discounting that, the fact that their server bill will now be 6x smaller is justification enough? Even if the cost savings aren't quite that much (suppose they work out to be 50% of previous costs), if I was running a business I would totally be implementing optimisations that allowed me to halve my running costs...
- mark-r 9y agoI'm really happy to see this. The one time I tried looking at the PIL sources for resizing, I was appalled at what I saw. Simply seeing that you're expanding the filter size as the input to output ratio shrinks is a huge deal. When I wrote my own resizing code, I found it helpful to debug using a nearest-neighbor kernel: 1 from -0.5 to 0.5 and 0 everywhere else. It shook out some off-by-one errors.
- cvwright 9y ago> No tricks like decoding a smaller image from a JPEG Given that most cameras are producing JPEG now, I'm curious why you don't make use of the compressed / frequency-domain representation. To a novice in this area (read: me), It seems like a quick shortcut to an 8x or 4x or 2x downsample. Or is the required iDCT operation just that much more expensive than the convolution approach?
- jacobolus 9y agoThat’s a shortcut if you only ever have to downsample by powers of two and you don’t mind worse image quality, since your down-sampled picture won’t use any data from across block boundaries.
- mark-r 9y agoYou can use it in a multi-step process. Use JPEG blocks to get slightly above the target size, then Lanczos to finish it off.
- jpap 9y agoThey would likely get another big speedup by doing this. iDCT gets faster as you perform a "DCT downscaling" operation because you require fewer add/mul [1]. You could probably go for another speedup, independently of DCT downscaling, by operating in YCbCr before a colorspace conversion to RGB. For example, for 4:2:0 encoded content (a majority of JPEG photographs), you end up processing 50% less pixels in the chroma planes. When you combine both techniques, you can have your cake and eat it too: for example, to downsample 4:2:0 content by 50% you can do a DCT downscale on only the Y plane, keeping the CbCr planes as they are before colorspace conversion to RGB. No lanczos required! If you need a downsample other than {1/n; n = 2,4,8}, you can round up to the nearest integer n then perform a lanczos to the final resolution: the resampling filter will be operating on a lot less data. On quality I once saw a comparison roughly equating DCT downscaling to bilinear (if I can find the reference I'll update this comment). With the example above, it really depends on how you compare: if you compare to a 4:2:0 image decoded to RGB where the chroma is first pixel-doubled or bicubic-upsampled before conversion to RGB then downsampled, it might be that the above lanczos-free technique will look just as good because it didn't modify the chroma at all. Ultimately it's best to try-and-compare. Lastly you could leverage both SIMD and multicore by processing each of the Y, Cb, and/or Cr planes in parallel. [1] http://jpegclub.org/djpeg/ http://jpegclub.org/djpeg/
- pedrocr 9y agoIs doing lanczos really faster and/or better quality for scaling down than just doing a simple pixel mixing: http://entropymine.com/imageworsener/pixelmixing/ http://entropymine.com/imageworsener/pixelmixing/ I implemented this for my image pipeline: https://github.com/pedrocr/rawloader/blob/230432a403a9febb5e5c004780211f7e765130b9/src/imageops/demosaic.rs#L155-L190 https://github.com/pedrocr/rawloader/blob/230432a403a9febb5e... Makes for simple enough code and even before any serious effort at optimization or SIMD it can convert a 3680x2456x4 image in 32bit float (source article is 3x8bit) to 320x200x4 also in 32bit float in about 60ms (across 4 threads in 2 cores on a i5-6200U).
- jacobolus 9y agoProbably not faster. Definitely better quality. As Alvy Ray Smith said, a pixel is not a little square, http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf http://alvyray.com/Memos/CG/Microsoft/6_pixel.pdf Edit: If you want to do even better than the tensor product Lanczos filtering, you can do a filter based on Euclidean distance. Make sure that you work in linear (non-gamma-adjusted) color space. A couple more resources to read: http://www.imagemagick.org/Usage/filter/#cylindrical http://www.imagemagick.org/Usage/filter/#cylindrical http://www.imagemagick.org/Usage/filter/nicolas/ http://www.imagemagick.org/Usage/filter/nicolas/ Edit 2: really weird that this is getting downvoted. There’s not really anything to dispute here. It is straight-forward to show that the Lanczos method has objectively better output. Moreover, Alvy Ray Smith’s paper is a classic which anyone interested in image processing should read.
- mark-r 9y agoDespite what the writeup says, you don't need to view pixels as little squares to make sense of this algorithm. It's a filter just like any other. You can evaluate its quality by examining its frequency response.
- jacobolus 9y agoOkay, sure. Go ahead and make a white paper about your analysis of the frequency response of this method for some particular scale of resizing (it ends up somewhere between a box filter and a bilinear filter), and you’ll see that it ends up doing a significantly worse job than the Lanczos filter. You’ll get less detail resolved and more aliasing artifacts.
- nostrademons 9y agoCurious how this would compare vs. running it on the GPU? This is literally what GPUs are made for, and they often have levels of parallelism 500+ times greater than SIMD.
- dimatura 9y agoI tried to do this once with Theano, and found that the latency of the roundtrip to GPU and back made it not worthwhile for a single image. Maybe a batch of images at once would make it worthwhile. And this isn't what theano is intended for, admittedly - custom CUDA might do a better job.
- fulafel 9y agoI got curious about the numbers so I did a napkin calculation: In a 2012 vintage Nvidia article[1] they get 5-6 GB/s in both directions (array size 4MB) which would be around 1500 Mpix/s with 8bit RGBA pixels. 15 Mpix image: Transfers both ways would take 20 ms, and given GPU kernel going at ~5x the CPU speed (CPU 30, GPU 150 Mpix/s), you would spend 100 ms doing the computation. So 120 ms on GPU vs 500 ms on the CPU. [1] https://devblogs.nvidia.com/parallelforall/how-optimize-data-transfers-cuda-cc/ https://devblogs.nvidia.com/parallelforall/how-optimize-data... edit: so I have no idea about the real GPU spedup, but this shows that the transfers shouldn't hurt too much unless the speedup vs CPU is very small.
- nostrademons 9y agoInteresting, thanks. So it seems like it'd still be a pretty heavy win for the GPU. Also, a common use-case on the web today is to have one input image and then a large number of output images (usually smaller) for different screen resolutions & thumbnails. Seems like you could save a lot of time by uploading the input image once and then running a bunch of resize convolutions for different output sizes while it's still in the GPU memory, then download the output files as a batch.
- stephencanon 9y agoFWIW the Accelerate framework[1] gives roughly comparable performance[2] for Lanczos resizing. Apple platforms only, but all Apple platforms, not limited to x86. [1] vImageScale_ARGB8888( ). [2] I don't have identical hardware available to time on, and it's doing an alpha channel as well, so this is slightly hand-wavy.
- arcticbull 9y agoAccelerate is a really amazing and highly underrated framework. Sure the function names are, uh, sub optimal (I'm looking at you, vDSP). That said, having a framework guaranteed across all devices to implement algorithms and primitives in the fastest way for each new device as they come out is amazingly valuable. I've built production systems over the last few years with it that really wouldnt have been possible without it.
- izacus 9y agoWhat kind of (server-side) production system can afford to only run on Apple consumer hardware? Or was it a mobile app?
- nuschk 9y agoIMGIX (a image scaling service) used to use Mac Pros [1]. Dunno if they still do though. [1] http://photos.imgix.com/racking-mac-pros http://photos.imgix.com/racking-mac-pros
- stephencanon 9y agoJust to provide a little context for the vDSP function names, vecLib predates OS X--it was part of OS 9--and the vDSP interfaces descend from the SAL library at Mercury; like LAPACK and BLAS, they needed to be short for Fortran 77 compatibility.
- legulere 9y agoCan the speed increased even further using GPGPU?
- deleted 9y ago[deleted]
- techdragon 9y agoAny reason this had to be a fork? I would much rather this feature be in Pillow so ALL of the python ecosystem could get 6 times faster image resizing.
- girvo 9y agoHe addressed that in the article: Pillow is cross-platform and cross-architecture, so these sorts of specific optimisations (x86-64 only, with some pretty specific instruction requirements) meant that the author felt it wouldn't be a good fit in the original library
- Veratyr 9y agoLooks really nice! I'd love to see vips in the benchmark comparison, perhaps a Halide-based resizer too as those are the fastest I've found so far. Perhaps GraphicsMagick too, as I believe it's meant to be faster than ImageMagick in many cases.
- dahart 9y agoGraphicsMagick (GM) is definitely loads faster than ImageMagick (IM) for some resize operations, but I doubt it's in the same league as Pillow-SIMD, just guessing though. I've had to do some large image (gigapixel) resizing, and IM keeps the entire image in memory, which causes it to hit swap. GM streams the image resize instead, so it doesn't have to swap, and it can finish in a few minutes instead of many hours.
- FrozenVoid 9y agoObligatory: http://johncostella.webs.com/magic/ http://johncostella.webs.com/magic/
- dahart 9y agoI'd be very interested in an optional Pillow-SIMD downsampling resize that produces 16 bit output internally and then uses a dither to convert from 16 bit to 8 bit. Photoshop does this by default and it produces superior downsampling. Without keeping the color resolution higher, you can end up with visible color banding in resized 8 bit images that wasn't visible in the source image. I am curious if the reason that Pillow-SIMD is more than 4x faster than IPP is due to features IPP supports - like higher internal resolution - that Pillow-SIMD doesn't? The reported speeds here are amazing, and I'm definitely going to check this project out and probably use it, but I'd love a little clarity on what the tradeoffs are against IPP or others. I assume there are some.
- jacobolus 9y agoI suspect on a GPU it will be better to use 32-bit floating point internally. But yeah, dithering the output when converting back to integers would be great. In Photoshop I always convert to 16-bit linear color before doing any kind of compositing or resampling.
- homm 9y agoEach resampling algorithm will internally produce some high-precision result before cutting it to 8 bits. For Pillow-SIMD it is 32-bit integers. Currently, I haven't considered dithering, but it is a very interesting idea. Do you have any links for further reading about downsampling banding and dithering? About IPP's features: the comparison is pretty fair: the same input, the same algorithm and filters, pretty much the same output. If IPP uses more resources internally with the same output, so, maybe it shouldn't. Shame on me, I still haven't added the link to IPP's test file I used. Here is it: https://gist.github.com/homm/9b35398e7e105a3c886ab1d60bf598dd https://gist.github.com/homm/9b35398e7e105a3c886ab1d60bf598d... It is modified ipp_resize_mt program from IPP's examples. If you have installed IPP, you'll easily find and build it.
- dahart 9y ago> Do you have any links for further reading about downsampling banding and dithering? Sadly, no, I wish I did. I just made some expensive mistakes printing giclee images from downsampled digital files, and whipped up my own dither for converting 16bit to 8bit. It wasn't until it bit me that I noticed Photoshop does it better than most apps because dithering is on by default. That's when I went looking and found an option for it in Photoshop's settings. The main banding problem when downsampling is with slow changing gradients. Sky and interior walls, for example. I bump into it a lot with digital art too, since the source images don't have any noise. But even when there's noise in the source image, downsampling 2x or more with a good filter can eliminate the noise and cause gradients to stabilize and show their edges in 8bit color. In my experience, the problem is more common with print than on-screen resized images, but it's still pretty easy to spot on a screen, especially in the darks, and especially when jpeg compressing the results. Implementation wise, the 16-to-8 bit dither is nowhere near as sensitive as the dithers we normally see converting 8bits to black & white or when posterizing. Almost anything you come up with will do. You don't need any fancy error diffusion or anything like that. Here's what I do: imagine the filtered 16 bit result as an 8.8 fixed point number in the [0-256) range, so the least significant bits are in the [0-1) range. I add a random number between -0.5 and +0.5 before rounding to the nearest integer. Viola, drop the low 8bits and the result is a dithered 8 bit value. What I just described will be way slow in your world if you call a random number function every pixel, so don't do that. :P For Pillow-SIMD you'd want a random number lookup table or something slightly smarter than a random() function. And I dither on the color channels separately, but there might be some way to make it blaze by dithering the brightness and rounding all three channels up or down at the same time. I've just never tried to optimize it the way you're doing, but if you find a way and release anything that dithers, I would LOVE to hear about it.
- gioele 9y agoUnrelated: since when has this picture of Bologna become a new lenna.jpg? I think I have already seen it in a couple of recent posts about image compression. (Fits perfectly the definition of Baader-Meinhof phenomenon [1].) [1] https://en.wikipedia.org/wiki/List_of_cognitive_biases#Frequency_illusion https://en.wikipedia.org/wiki/List_of_cognitive_biases#Frequ...
- josteink 9y ago> Unrelated: since when has this picture of Bologna become a new lenna.jpg? Lenna does IMO not contain enough sharp edges and contrasts to highlight the differences between the different resize techniques. With Bologna, you can clearly see the problems with a nearest-neighbour approach. I'm not sure that would have been equally visible with lenna.
- homm 9y agoThis picture from great site with collections of high-resolution photos under free license https://unsplash.com/photos/vXpcpTl2Tt4 https://unsplash.com/photos/vXpcpTl2Tt4 Bu the way, thank you fo pointing out that this is Bologna! I'm going to Italy at the end of the month, can visit it :-)
- deleted 9y ago[deleted]
- McKayDavis 9y agoEven in 1996 there was discussion [1] about the controversy around lenna.jpg and its decline due to its origins and possible copyright issues. [1] http://www.cs.cmu.edu/~chuck/lennapg/editor.html http://www.cs.cmu.edu/~chuck/lennapg/editor.html
- ashishuthama 9y agoAnother data point: MATLAB, glnxa64 AVX2, 12 core >> maxNumCompThreads(1); >> im = randi(255, [2560, 1600, 3],'uint8'); >> timeit(@()imresize(im,[320,200],'bilinear','Antialiasing',false)) ans = 0.0083 >> timeit(@()imresize(im,[320,200],'bilinear')) ans = 0.0301 >> maxNumCompThreads(6); >> timeit(@()imresize(im,[320,200],'bilinear','Antialiasing',false)) ans = 0.0062 >> timeit(@()imresize(im,[320,200],'bilinear')) ans = 0.0113 Oh, missed that lanczos2 part: >> maxNumCompThreads(1); >> timeit(@()imresize(im,[320,200],'lanczos2','Antialiasing',false)) ans = 0.0146 >> maxNumCompThreads(6); >> timeit(@()imresize(im,[320,200],'lanczos2','Antialiasing',false)) ans = 0.0049 Since MATLAB tries to do most of the computation in double precision, its harder to extract much from SIMD.