6 ms·

Is doing lanczos really faster and/or better quality for scaling down than just doing a simple pixel mixing: http://entropymine.com/imageworsener/pixelmixing/

Is 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 ago
Probably 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 ago
  Despite 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 ago
    Okay, 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.
    - mark-r 9y ago
      I agree completely by the way.
  - smallnamespace 9y ago
    The 2D frequency response is poor because treating pixels as 'little squares' essentially substitutes Manhattan distance for Euclidean distance between pixel positions. You have reasonable behavior along the orthogonal dimensions, but you're introducing a sqrt(2) stretch factor along diagonals.
    - mark-r 9y ago
      I think you're missing my point. Although the "little squares" are used as a justification for the algorithm, the application of it is not dependent on that view. You're doing a convolution of points against a filter formula, just as you would with bicubic or Lanczos. The stretch factor along diagonals will be the same for any separable filter will it not?
      - jacobolus 9y ago
        Yes, any separable filter causes grid artifacts that can be partially ameliorated by using a radial filter. My own pipe-dream is that we would use a triangular grid (if you like, the Voronoi cells here are hexagonal pixels) for intermediate image representations. This is more spatially efficient and has nicer 2-dimensionnal frequency response than a square grid, and displays are so heterogeneous nowadays that we need to do some amount of resampling for output pretty much all the time anyway, and our GPUs are getting fast enough that resampling at high quality from a hexagon grid to a square grid for output should add only relatively cheap overhead.
- wtallis 9y ago
  That memo needs to die. There are better ways to make the few of its points that are still valid, without making assumptions and assertions that are frequently invalid with today's technology. Pixels are often not representative of little squares (rectangles). However, they are more likely to be representative of little rectangles now than they were in 1995, now that most photographs are captured on Bayer arrays of square sensors, most computer-generated images are rendered as an average of point samples weighted according to estimated coverage of a square pixel, and everything is displayed on LCD or OLED panels with square pixels comprised of rectangular subpixels. If you take a random JPEG or PNG off the Internet, interpreting the pixel data as point samples will usually be less accurate than interpreting them as integrated over a rectangle. Interpreting the data as integrated over a gaussian distribution is also less realistic than the rectangle interpretation. Doing image processing in a point sample or gaussian context is certainly useful, but it's definitely not more fundamentally right than the little square model. Historically, that context was at best a neutral choice that was equally unrealistic no matter what kind of hardware you were working with, but mathematically convenient. The paper's arguments about coordinate systems (whether the y-coordinate should grow toward the top of the screen or the bottom, and whether pixels should be centered on half-integer points) are also a waste of time for the modern reader.
  - jacobolus 9y ago
    The better alternatives are all like 50-page papers with worse titles and a lot of math. If you know a nice 5–10-page “modern” summary of how to treat filters for image resampling aimed at a non-specialist audience, please link away. I’ll agree that treating pixels as Gaussians is not especially great. In practice most images go through multiple layers of processing, physical sensor and display pixels come in all kinds of wacky shapes (and as you point out have channels offset by different amounts, etc.). It’s usually better to treat pixels as point samples for generic intermediate processing because you have no idea what kind of source an image comes from, and you have no idea what someone down the line is going to do with your image before sending a final signal to the display hardware. Creating synthetic images by integrating over little rectangles produces markedly inferior results to applying some real resampling filter to the samples, but gets done by computer games etc. because it’s computationally cheap, with the hope that there are enough pixels moving fast enough that someone won’t notice the artifacts.
- deleted 9y ago
  [deleted]
- a_e_k 9y ago
  I'd say usually better quality rather than definitely better quality. While the Lanczos filter is always superior to the box filter in theory, there are some case in practice where the box filter may be better. If you're downsampling a line-art image, for example, you may actually be better off with some variation of the box filter. The negative lobes on the Lanczos filter can induce objectionable ringing because line-art tends to be full of what are basically step functions. It's a similar issue as with strong mosquito artifacts on JPEG compressed line-art. A filter function that is everywhere non-negative, such as the box filter or a Gaussian can't suffer from this problem. Of the two, the box filter will give you sharper results but of course it doesn't antialias as well, either.
mark-r 9y ago
Nice writeup. I think it spells out the difference pretty well - less aliasing and artifacts for Lanczos. But you gotta admit it's fast. For large shrink factors you'd be just as well off averaging whole pixels, even if the rectangles being averaged aren't all the same size.
est 9y ago
can we add this to Pillow?
dahart 9y ago
Yes, lanczos really is better quality, but it seems like the pixel mixing article admits and explains that openly. You don't always need better quality, sometimes a box filter is fine, but for some applications it can be super important to use a high quality filter. Faster depends on implementation details, but from the looks of it, to implement pixel mixing, you either have to generate your convolution kernel dynamically, or chop some source pixels into potentially 4 separate pieces? I would guess that it's easier to optimize a static kernel than to make a dynamic kernel faster than a static one. But I'm not entirely sure how fast pixel mixing could be made. > It can be confused with a box filter or with linear interpolation, but it is not the same as either of them... [pixel mixing] Treats pixels as if they were little squares, which gets on some experts’ nerves. This is a funny way of putting it. Pixel mixing is definitely using a box filter, just slightly differently than what people normally call box filter resizing. The author even says that later: "Another way to think of pixel mixing is as the integral of a nearest-neighbor function." Pixel mixing as described here is clipping the source image under the box filter rather than using a static kernel. The reason that a box filter isn't ideal is well understood. It's because the filter itself has high frequencies in it. This is the reason that the quality of pixel mixing resizes is low. One of the benefits of a box filter is that applied multiple times, it becomes a better filter, and approximates a Gaussian after several times. I'm not sure but I would bet that clipping to the exact filter boundary actually prevents you from being able to do that with pixel mixing.
- mark-r 9y ago
  Generating the factors dynamically isn't that hard. I implemented this algorithm back in the late 80's, and it had acceptable performance on a 25 MHz processor. Not only that but it had to do some distortion correction at the same time, so it was applying a different resize factor to every single line of the image. All with integer math.
  - dahart 9y ago
    Oh absolutely, I believe it, and I looked at @pedrocr's code. Very simple. But, a static box filter is even simpler. Did you call it pixel mixing in the 80s? I've been doing image resizing for decades and never heard the term before tonight. I have implemented a couple of very similar algorithms to pixel mixing for CG films, once in a shader and once for antialiasing in a particle renderer.
homm 9y ago
Well, 3680x2456 / 0.06 seconds ≈ 150 Mp/s or 75 Mp/s/per core. Pillow-SIMD's current implementation runs on ≈ 700 Mp/s/pre core for bicubic (which is closer to this implementation). Obviously, your implementation could be further optimized, but quality drawbacks will remain the same.
- pedrocr 9y ago
  I've since made a small change that doubled performance and I'm operating on >5x more data per pixel (32x4 vs 8x3). So a 10x factor makes this already faster without any explicit SIMD yet. Proper benchmarking on the same machine would need to be done obviously. On the quality drawbacks I'd have to do some more checking. This algorithm is closest to what the image would be if you had a camera with that native sensor size. The standard filtering approach may very well have plenty of cases where it produces better output but it can also cause issues so I wonder if this isn't a conservative solution.
CyberDildonics 9y ago
Filters are not there for speed, they are there for quality. If you image is not a square power of two, pixel mixing will have artifacts.
- pedrocr 9y ago
  >If you image is not a square power of two, pixel mixing will have artifacts. I've implemented it generally by weighing the pixels by the actual area overlapping so border pixels get weights <1.0 for non power of two reductions. Haven't seen any artifacts from it.
  - CyberDildonics 9y ago
    That can be generalized to a filter kernel.

jacobolus 9y ago

Probably 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 ago
Despite 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 ago
  Okay, 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.
  - mark-r 9y ago
    I agree completely by the way.
- smallnamespace 9y ago
  The 2D frequency response is poor because treating pixels as 'little squares' essentially substitutes Manhattan distance for Euclidean distance between pixel positions. You have reasonable behavior along the orthogonal dimensions, but you're introducing a sqrt(2) stretch factor along diagonals.
  - mark-r 9y ago
    I think you're missing my point. Although the "little squares" are used as a justification for the algorithm, the application of it is not dependent on that view. You're doing a convolution of points against a filter formula, just as you would with bicubic or Lanczos. The stretch factor along diagonals will be the same for any separable filter will it not?
    - jacobolus 9y ago
      Yes, any separable filter causes grid artifacts that can be partially ameliorated by using a radial filter. My own pipe-dream is that we would use a triangular grid (if you like, the Voronoi cells here are hexagonal pixels) for intermediate image representations. This is more spatially efficient and has nicer 2-dimensionnal frequency response than a square grid, and displays are so heterogeneous nowadays that we need to do some amount of resampling for output pretty much all the time anyway, and our GPUs are getting fast enough that resampling at high quality from a hexagon grid to a square grid for output should add only relatively cheap overhead.
wtallis 9y ago
That memo needs to die. There are better ways to make the few of its points that are still valid, without making assumptions and assertions that are frequently invalid with today's technology. Pixels are often not representative of little squares (rectangles). However, they are more likely to be representative of little rectangles now than they were in 1995, now that most photographs are captured on Bayer arrays of square sensors, most computer-generated images are rendered as an average of point samples weighted according to estimated coverage of a square pixel, and everything is displayed on LCD or OLED panels with square pixels comprised of rectangular subpixels. If you take a random JPEG or PNG off the Internet, interpreting the pixel data as point samples will usually be less accurate than interpreting them as integrated over a rectangle. Interpreting the data as integrated over a gaussian distribution is also less realistic than the rectangle interpretation. Doing image processing in a point sample or gaussian context is certainly useful, but it's definitely not more fundamentally right than the little square model. Historically, that context was at best a neutral choice that was equally unrealistic no matter what kind of hardware you were working with, but mathematically convenient. The paper's arguments about coordinate systems (whether the y-coordinate should grow toward the top of the screen or the bottom, and whether pixels should be centered on half-integer points) are also a waste of time for the modern reader.
- jacobolus 9y ago
  The better alternatives are all like 50-page papers with worse titles and a lot of math. If you know a nice 5–10-page “modern” summary of how to treat filters for image resampling aimed at a non-specialist audience, please link away. I’ll agree that treating pixels as Gaussians is not especially great. In practice most images go through multiple layers of processing, physical sensor and display pixels come in all kinds of wacky shapes (and as you point out have channels offset by different amounts, etc.). It’s usually better to treat pixels as point samples for generic intermediate processing because you have no idea what kind of source an image comes from, and you have no idea what someone down the line is going to do with your image before sending a final signal to the display hardware. Creating synthetic images by integrating over little rectangles produces markedly inferior results to applying some real resampling filter to the samples, but gets done by computer games etc. because it’s computationally cheap, with the hope that there are enough pixels moving fast enough that someone won’t notice the artifacts.
deleted 9y ago
[deleted]
a_e_k 9y ago
I'd say usually better quality rather than definitely better quality. While the Lanczos filter is always superior to the box filter in theory, there are some case in practice where the box filter may be better. If you're downsampling a line-art image, for example, you may actually be better off with some variation of the box filter. The negative lobes on the Lanczos filter can induce objectionable ringing because line-art tends to be full of what are basically step functions. It's a similar issue as with strong mosquito artifacts on JPEG compressed line-art. A filter function that is everywhere non-negative, such as the box filter or a Gaussian can't suffer from this problem. Of the two, the box filter will give you sharper results but of course it doesn't antialias as well, either.

mark-r 9y ago

Nice writeup. I think it spells out the difference pretty well - less aliasing and artifacts for Lanczos. But you gotta admit it's fast. For large shrink factors you'd be just as well off averaging whole pixels, even if the rectangles being averaged aren't all the same size.

est 9y ago

can we add this to Pillow?

dahart 9y ago

Yes, lanczos really is better quality, but it seems like the pixel mixing article admits and explains that openly. You don't always need better quality, sometimes a box filter is fine, but for some applications it can be super important to use a high quality filter. Faster depends on implementation details, but from the looks of it, to implement pixel mixing, you either have to generate your convolution kernel dynamically, or chop some source pixels into potentially 4 separate pieces? I would guess that it's easier to optimize a static kernel than to make a dynamic kernel faster than a static one. But I'm not entirely sure how fast pixel mixing could be made. > It can be confused with a box filter or with linear interpolation, but it is not the same as either of them... [pixel mixing] Treats pixels as if they were little squares, which gets on some experts’ nerves. This is a funny way of putting it. Pixel mixing is definitely using a box filter, just slightly differently than what people normally call box filter resizing. The author even says that later: "Another way to think of pixel mixing is as the integral of a nearest-neighbor function." Pixel mixing as described here is clipping the source image under the box filter rather than using a static kernel. The reason that a box filter isn't ideal is well understood. It's because the filter itself has high frequencies in it. This is the reason that the quality of pixel mixing resizes is low. One of the benefits of a box filter is that applied multiple times, it becomes a better filter, and approximates a Gaussian after several times. I'm not sure but I would bet that clipping to the exact filter boundary actually prevents you from being able to do that with pixel mixing.

mark-r 9y ago
Generating the factors dynamically isn't that hard. I implemented this algorithm back in the late 80's, and it had acceptable performance on a 25 MHz processor. Not only that but it had to do some distortion correction at the same time, so it was applying a different resize factor to every single line of the image. All with integer math.
- dahart 9y ago
  Oh absolutely, I believe it, and I looked at @pedrocr's code. Very simple. But, a static box filter is even simpler. Did you call it pixel mixing in the 80s? I've been doing image resizing for decades and never heard the term before tonight. I have implemented a couple of very similar algorithms to pixel mixing for CG films, once in a shader and once for antialiasing in a particle renderer.

homm 9y ago

Well, 3680x2456 / 0.06 seconds ≈ 150 Mp/s or 75 Mp/s/per core. Pillow-SIMD's current implementation runs on ≈ 700 Mp/s/pre core for bicubic (which is closer to this implementation). Obviously, your implementation could be further optimized, but quality drawbacks will remain the same.

pedrocr 9y ago
I've since made a small change that doubled performance and I'm operating on >5x more data per pixel (32x4 vs 8x3). So a 10x factor makes this already faster without any explicit SIMD yet. Proper benchmarking on the same machine would need to be done obviously. On the quality drawbacks I'd have to do some more checking. This algorithm is closest to what the image would be if you had a camera with that native sensor size. The standard filtering approach may very well have plenty of cases where it produces better output but it can also cause issues so I wonder if this isn't a conservative solution.

CyberDildonics 9y ago

Filters are not there for speed, they are there for quality. If you image is not a square power of two, pixel mixing will have artifacts.

pedrocr 9y ago
>If you image is not a square power of two, pixel mixing will have artifacts. I've implemented it generally by weighing the pixels by the actual area overlapping so border pixels get weights <1.0 for non power of two reductions. Haven't seen any artifacts from it.
- CyberDildonics 9y ago
  That can be generalized to a filter kernel.