Resizing algorithms — how to deal with edges?

[Mark S Abeln]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms, and is wondering how to deal with edges. Since the bicubic methods rely on a number of neighboring pixels, some method must be used to ‘fake’ the data along the edges.

Simply by looking at upsized Photoshop images, it appears that the pixels along the edges are duplicated, since an uprezed image appears to have a ‘border’ around it, with no diagonal detail. I tried the same thing with a generic cubic uprez in ImageMagick, and (while the output was considerably different) it still appeared to have a border artifact.

Is this considered acceptable to most developers, or are there better methods for faking the data? Other suggested methods include adding black pixels to the outside of the data, or duplicating some interior neighbor pixels to the outside.

Original, magnified 500%:



Photoshop bicubic from 100x100 to 172x172, magnified, with obvious border region:



My gut feeling is that duplicating the pixels to the outside is likely adequate, but perhaps some sort of extrapolation could be useful.

--

The Refracted Light

A website about the Art and Science of Photography

therefractedlight.blogspot.com

 

[hjulenissen]

You might pad using som sensible average ("128").

Or duplicate the edge values. Or mirror them spatially and/or level-wise (minimale n-th order derivate discontinuity). FFT based processing leads to som kind of wrap around. Mr Robidoux might have something to and.

In the end, this is more or less educated guesswork and expect worse results on bordvers or crop.

 

[ProfHankD]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms ... Original, magnified 500%:

Ok. Sampled back down to 100x100....

Photoshop bicubic from 100x100 to 172x172, magnified, with obvious border region:

What does that mean? 500x500 is not a multiple of 172x172, so how did you "magnify" it? Any way I can think of will introduce artifacts....

For what it's worth, here's what GIMP does for cubic 100x100->172x172:



Not seeing a problem here....

GIMP also has Sinc interpolation as an option, and it does even better.

In case you didn't know, full source code for GIMP is freely available, so you can see precisely how they handle edges.

 

[Mark S Abeln]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms ... Original, magnified 500%:

Ok. Sampled back down to 100x100....

OK here are the originals:





Hm these don’t look right, but whatever.

Photoshop bicubic from 100x100 to 172x172, magnified, with obvious border region:

What does that mean? 500x500 is not a multiple of 172x172, so how did you "magnify" it? Any way I can think of will introduce artifacts....

I used nearest neighbor, which retains the blockiness.

For what it's worth, here's what GIMP does for cubic 100x100->172x172:

You can still see a clear border strop around it. My correspondent thinks that this is a problem.

Not seeing a problem here....

GIMP also has Sinc interpolation as an option, and it does even better.

In case you didn't know, full source code for GIMP is freely available, so you can see precisely how they handle edges.

Maybe I’ll take a look. For whatever reason, they want to use bicubic for this use. I’m sure sync can have a similar problem.

--

The Refracted Light

A website about the Art and Science of Photography

therefractedlight.blogspot.com

 

[MirekE]

Is this considered acceptable to most developers, or are there better methods for faking the data?

If it is used in PS (industry standard) and IM (developed by people like Robidoux), then I suppose it is considered acceptable. It is probably not a big concern in photography, where one line of pixels is usually not a big deal. If it is a problem in your application, perhaps - depending on the criteria - you could enlarge more and crop the few lines of pixels that look repeated?

As far as methods for faking the data are concerned, look at address modes in OpenCL for some ideas how to handle that. I used CLK_ADDRESS_CLAMP_TO_EDGE in my attempt to implement fast and photography friendly resizing. The attached image is a corner (see top row and left column) of one of these attempts. This is downsizing, though and probably not interesting for you.







There is also somewhere on the Internet a "Separable filtering image rescaler by Rich Geldreich", that implements functions to handle the situation in several ways, similar to OpenCL, I think.

 

[ProfHankD]

For what it's worth, here's what GIMP does for cubic 100x100->172x172:

You can still see a clear border strop around it. My correspondent thinks that this is a problem.

No, that isn't a border strip... but I get your concern.

Fundamentally, the value of a pixel is really the value assumed to be at the center of that pixel. With no pixels past the edges, the central value usually is considered to apply from the outer edge of the pixel to its center, thus making edge pixels seem thicker. They really aren't.

If you don't like extending the pixel values to the edges, the fix is simple: treat the pixel values as valid only at pixel centers. In scaling a 100x100 to 200x200, you would expect each pixel to form a 2x2 pixel clump in the scaled result. However, the 100x100 image has pixel centers that are 99x99 pixel-scale-units apart. Thus, you'd treat the edge pixel values as defining the scaled edge values and would scale the inset-by-1/2-pixel 99x99 image to 200x200. Thus, a 2X integer scaling factor actually becomes slightly more than 2X. In fact, the original video wall library my group built in the mid 1990s did precisely this. The catch is that edge pixels are then effectively influencing only half the area of central pixels, and in the long run we found that more annoying than the usual edge treatment.

Incidentally, if you have raw files, the edge issue can go away -- JPEGs are usually inset from the raw data edges a bit to allow for easier interpolation (and make the dimensions a multiple of 8 for the 8x8 DCTs used in JPEGs). If you scale the raw and crop to the scaled JPEG dimensions, you've essentially got real pixel data past the edge, so there would be no edge effect.

 

[Sasha B]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms, and is wondering how to deal with edges. Since the bicubic methods rely on a number of neighboring pixels, some method must be used to ‘fake’ the data along the edges.

Bucubic spine interpolation is "the method" used to fill data gaps. Depending on specific spline you get different interpolation. Are you looking for implementation details?

 

[olliess]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms, and is wondering how to deal with edges. Since the bicubic methods rely on a number of neighboring pixels, some method must be used to ‘fake’ the data along the edges.

Bucubic spine interpolation is "the method" used to fill data gaps. Depending on specific spline you get different interpolation. Are you looking for implementation details?

No, he's asking about how to deal with the edges, where you can't do "interpolation" (only "extrapolation").

 

[Its RKM]

A correspondent asked me to look into the implementation of bicubic image resampling algorithms, and is wondering how to deal with edges. Since the bicubic methods rely on a number of neighboring pixels, some method must be used to ‘fake’ the data along the edges.

Simply by looking at upsized Photoshop images, it appears that the pixels along the edges are duplicated, since an uprezed image appears to have a ‘border’ around it, with no diagonal detail. I tried the same thing with a generic cubic uprez in ImageMagick, and (while the output was considerably different) it still appeared to have a border artifact.

Is this considered acceptable to most developers, or are there better methods for faking the data? Other suggested methods include adding black pixels to the outside of the data, or duplicating some interior neighbor pixels to the outside.

If the border issue is problem for your client, and there always will be some artefact along the border because of the fake data, why not simply resample from a slightly lower resolution in the first place. (or to a higher resolution followed by cropping the centre out)

In your example, for instance, you want to go from 100x100 to 172x172 pixels, but the bicubic algorithm results in a single pixel duplicated border. If you resampled the central 98x98 up to 172x172 then you wouldn't need to "fake" the edge pixels, you could use real data from the original 100x100.

Scaling will, of course, be slightly off but that is less objectionable than duplicated pixels.

 

[Nicolas Robidoux]

The simplest "abyss policy" is duplicating the border values (this is sometimes called "clamp" or "nearest neighbour"). Its visual impact on the texture of the image can be minimized by a slight inward crop. One of the most common image alignment conventions for image resizing does this automatically. However, most software packages use, across the board, the convention that generally gives more desirable results when downsampling, in part because downsampling is the most commonly performed operation. This is the case of ImageMagick, VIPS/NIP2, the "work in progress" 16-bit/float GIMP (based on GEGL). This convention, however, makes the abyss "creep in" when enlarging.
More details (the references are recent and related to me but this "image alignment convention issue" has been discussed for decades):
http://libvips.blogspot.dk/2011/12/task-of-day-resize-image-with-align.html
Section 4.2 of Adam Turcotte's masters thesis http://web.cs.laurentian.ca/nrobidoux/misc/AdamTurcotteMastersThesis.pdf
One can devise more sophisticated abyss policies but when dealing with megapixels computational expediency favours simplicity given that it only affects a thin border.
(Apologies for the rather terse answers: urgent work to be done.)

 

[Nicolas Robidoux]

I just realized that what I wrote is quite opaque: What is commonly done (and some of you know this already I'm sure) is to extend the image by duplicating the border pixels, and then using the slightly enlarged image to feed values to, say, the bicubic filter. (An abyss policy is a specification of the method used to extend the image so that the resampling filter "has values to put in every slot"; this is performed before feeding values to the filter.)
I also incorrectly described ImageMagick's abyss policy. In many cases, what is used is a "transparent black" abyss. Because the filter is normalized by the sum of its coefficients, one can fix things so that the abyss values are "ignored" by suitably taking transparency into account in the weighted sums that define the interpolated values. See the ImageMagick source code (start with resize.c) for details.

 

[Nicolas Robidoux]

Now you may ask: If one convention is better when upsampling (enlarging), and another is better when downsampling (reducing), why don't software packages use one for enlarging and one for reducing?
Answer (part 1): If you do, reducing then re-enlarging, or vice versa, will produce misaligned results. This is annoying and confuses users, and gets in the way of painless usability.
Answer (part 2): Many packages resample in other ways than plain resizing. When warping, the convention that's used would vary with the location and the direction in which the boundary is approached...
Answer (part 3): Programming expediency.
In other words, fixing this minor problem without breaking something is a PITA.

 

[Nicolas Robidoux]

One last note: There are two different issues:
1) What abyss policy (or policies) should you choose?
2) Which image geometry convention (or, alternately, crop near the boundary) minimizes the negative impact of the abyss policy when enlarging while being inobstrusive? (Abyss policy choice also impacts results when reducing but differences are less obvious because individual pixel values have smaller weights when downsampling so that the choice of abyss policy is somewhat irrelevant, esp. when using the most common image geometry convention, which makes the center of the corner pixels of the reduced image creep inward relative to their position in the full size one.)
I mostly discussed 2).

 

[Nicolas Robidoux]

One last comment: My contributions to ImageMagick are minor. Much greater contributions were made by Cristy, Anthony Thyssen, and Glenn Randers-Pehrson. Anthony Thyssen, in particular, is responsible for the high quality of the image resampling code.
I highly recommend Anthony's approach to abyss policy issues, especially as he implemented them for separable filters (see resize.c). For code that only resizes, I'd switch image alignment convention when enlarging (from the one that's used across the board in ImageMagick). But his approach to "what to do with a filter that wants values from outside known territory" is sane, simple, and gives better results than "clamp".

 

[Mark S Abeln]

Thank you for your advice!