[cairo] [PATCH] image: V5 Use convolution filters for sample reconstruction when downscaling
Bryce W. Harrington
b.harrington at samsung.com
Wed Jun 18 13:14:34 PDT 2014
On Fri, Jun 13, 2014 at 05:37:19PM -0700, Bill Spitzak wrote:
> (This version clips extreme up and down scale sizes to avoid errors and
> extreme slowness or memory usage. The BEST setting transitions smoothly from
> normal blurry result to square pixels as the scale gets larger than 2, this
> looks really nice.)
>
> (Is anybody looking at this? Anxious for any feedback.)
Hi Bill,
First up, let me just say a big thank you for working on this. We need
to get better downscaling support in cairo, and this moves us forward.
> This code contains an all-new filter generator to replace the one that is
> in pixman. Results in 222 pass/298 failed image tests, which is much better
> than the previous versions of this patch.
What is the delta in passes and failures compared with trunk?
(I know the current downscaling tests have truth images that will show
failures inappropriately, which iirc accounts for a hundred and some
false failures when just changing the downscaling algorithm.)
> Filter generator (which should probably be in pixman):
>
> - Single filter, no "reconstruction" and "sample" filter
> - Filters for derivative < 1 work
> - Fixed IMPULSE and BOX
> - Added TRIANGLE, CATMULL, NOTCH. Remove LANZCOS2.
> - Renamed CUBIC to MITCHELL
Thanks for including the commentary on each of them. I don't have
appropriate background to comment on the viability of all of these, but
expanding the options does seem like a good idea.
Regarding removal of lanzcos2, would it make sense to leave it in for
one release, but mark it deprecated?
I'm also curious about whether we should include this temporarily in
cairo, vs. focus on getting it into pixman. It might be handy to split
this patch up into a few pieces to facilitate this (and to make review a
bit easier). Like one patch that adds filters but does not impact
behavior, another which updates the filter quality mappings, another for
the xlib change, etc.
> Cairo's filter settings:
>
> - CAIRO_FILTER_GOOD: uses BOX filter for scales less than .75 in either
> direction. Uses PIXMAN_FILTER_GOOD (ie BILINEAR) otherwise.
>
> - CAIRO_FILTER_BEST: uses CATMULL filter always. Upscaling more than 2x will
> produce anti-aliased square pixels, similar to OS/X.
>
> - CAIRO_FILTER_GAUSSIAN: this obsolete value is used to test other filters.
> The program must declare and poke the filter into the static varialbe
> ikernel. This should be removed for production code.
>
> NYI: This version uses the fallback for xlib always. The xlib and xcb backends
> must be rewritten to use the fallback version if filtering is needed. Or the
> filtering code must be moved to XRender.
I may have missed the discussion on a previous patch, but could you
explain this in more detail?
Also, does this potentially affect any other backend behaviors?
Thanks,
Bryce
> ---
> src/cairo-image-source.c | 435 +++++++++++++++++++++++++++++++++++++++++++++-
> src/cairo-xlib-display.c | 2 +-
> 2 files changed, 432 insertions(+), 5 deletions(-)
>
> diff --git a/src/cairo-image-source.c b/src/cairo-image-source.c
> index c5bd228..aceb846 100644
> --- a/src/cairo-image-source.c
> +++ b/src/cairo-image-source.c
> @@ -526,6 +526,379 @@ _pixel_to_solid (cairo_image_surface_t *image, int x, int y)
> }
> }
>
> +/* ========================================================================== */
> +/* This portion should probably be in pixman */
> +
> +/* Produce contribution of a filter of size r for pixel centered on x.
> + For a typical low-pass function this evaluates the function at x/r.
> + If the frequency is higher than 1/2, such as when r is less than 1,
> + this may need to integrate several samples, see cubic for examples.
> +*/
> +typedef double (* kernel_func_t) (double x, double r);
> +
> +/* Return maximum number of pixels that will be non-zero. Except for
> + impluse this is the maximum of 2 and the width of the non-zero part
> + of the filter rounded up to the next integer.
> +*/
> +typedef int (* kernel_width_func_t) (double r);
> +
> +/* Index into filter table */
> +typedef enum
> +{
> + KERNEL_IMPULSE,
> + KERNEL_BILINEAR,
> + KERNEL_BOX,
> + KERNEL_TRIANGLE,
> + KERNEL_CATMULL,
> + KERNEL_MITCHELL,
> + KERNEL_LANCZOS3,
> + KERNEL_NOTCH
> +} kernel_t;
> +
> +/* Table of filters */
> +typedef struct
> +{
> + kernel_func_t func;
> + kernel_width_func_t width;
> + const char* name;
> +} filter_info_t;
> +
> +/* Helper functions */
> +static double _min(double a, double b) { return a < b ? a : b; }
> +static double _max(double a, double b) { return a > b ? a : b; }
> +
> +/* IMPULSE: Returns pixel nearest the center. This matches
> + CAIRO_FILTER_NEAREST. This is useful if you wish to combine nearest
> + filter in one direction with another filter in the other.
> +*/
> +
> +static double
> +impulse_kernel (double x, double r)
> +{
> + return x >= -0.5 && x < 0.5 ? 1.0 : 0.0;
> +}
> +
> +static int
> +impulse_width (double r)
> +{
> + return 1;
> +}
> +
> +/* BILINEAR: Weighted sum of the two pixels nearest the center, or a
> + triangle of width 2. This matches CAIRO_FILTER_BILINEAR. This is
> + useful if you wish to combine bilinear filter in one direction with
> + another filter in the other.
> +
> + At r == 1 this is equal to BOX and TRIANGLE, allowing filters to be
> + changed at this point.
> +*/
> +
> +static double
> +bilinear_kernel (double x, double r)
> +{
> + return _max(1.0 - fabs(x), 0.0);
> +}
> +
> +static int
> +bilinear_width (double r)
> +{
> + return 2;
> +}
> +
> +/* BOX: Intersection of a box of width r with square pixels. This is
> + the smallest possible filter such that the output image contains an
> + equal contribution from all the input pixels. Lots of software uses
> + this. The function is a trapazoid of width r+1, not a box.
> +
> + At r == 1 this is equal to BILINEAR and TRIANGLE, allowing filters to be
> + changed at this point.
> +*/
> +
> +static double
> +box_kernel (double x, double r)
> +{
> + return _max (0.0, _min (_min (r, 1.0),
> + _min ((r + 1) / 2 - x, (r + 1) / 2 + x)));
> +}
> +
> +static int
> +box_width (double r)
> +{
> + return r < 1.0 ? 2 : ceil(r + 1);
> +}
> +
> +/* TRIANGLE: Triangle of width 2r. Lots of software uses this as a
> + "better" filter, twice the size of a box but smaller than a cubic.
> +
> + At r == 1 this is equal to BILINEAR and BOX, allowing filters to be
> + changed at this point.
> +*/
> +
> +static double
> +triangle_kernel (double x, double r)
> +{
> + if (r < 1.0)
> + return box_kernel(x, r);
> + else
> + return _max (1.0 - fabs(x / r), 0.0);
> +}
> +
> +static int
> +triangle_width (double r)
> +{
> + return r < 1.0 ? 2 : ceil(2 * r);
> +}
> +
> +/* Cubic functions described in the Mitchell-Netravali paper.
> + http://mentallandscape.com/Papers_siggraph88.pdf. This describes
> + all possible cubic functions that can be used for sampling.
> +*/
> +
> +static double
> +general_cubic_i (double a, double B, double C)
> +{
> + double ax = fabs(a);
> +
> + if (ax < 1)
> + {
> + return (((12 - 9 * B - 6 * C) * ax +
> + (-18 + 12 * B + 6 * C)) * ax * ax
> + + (6 - 2 * B)) / 6;
> + }
> + else if (ax < 2)
> + {
> + return ((((-B - 6 * C) * ax +
> + (6 * B + 30 * C)) * ax +
> + (-12 * B - 48 * C)) * ax +
> + (8 * B + 24 * C)) / 6;
> + }
> + else
> + {
> + return 0.0;
> + }
> +}
> +
> +static double
> +general_cubic (double x, double r, double B, double C)
> +{
> + if (r < 1.0)
> + return
> + general_cubic(x * 2 - .5, r * 2, B, C) +
> + general_cubic(x * 2 + .5, r * 2, B, C);
> + else
> + return
> + general_cubic_i(x / r, B, C);
> +}
> +
> +static int
> +cubic_width (double r)
> +{
> + return _max(2.0, ceil (r * 4));
> +}
> +
> +/* CATMULL: Catmull-Rom interpolation. Often called "cubic interpolation",
> + "b-spline", or just "cubic" by other software. This filter has
> + negative values so it can produce ringing and output pixels outside
> + the range of input pixels. This is very close to lanczos2 so there
> + is no reason to supply that as well.
> +*/
> +
> +static double
> +catmull_kernel (double x, double r)
> +{
> + return general_cubic (x, r, 0.0, 0.5);
> +}
> +
> +/* MITCHELL: Cubic recommended by the Mitchell-Netravali paper.
> + This has negative values and because the values at +/-1 are not
> + zero it does not interpolate the pixels, meaning it will change
> + an image even if there is no translation.
> +
> + Note that Pixman calls this "CUBIC", which is misleading as almost
> + all other software uses the word "CUBIC" to mean an interpolating
> + function such as CATMULL.
> +*/
> +
> +static double
> +mitchell_kernel (double x, double r)
> +{
> + return general_cubic (x, r, 1/3.0, 1/3.0);
> +}
> +
> +/* NOTCH: Cubic recommended by the Mitchell-Netravali paper to
> + remove postaliasing artifacts. Note this does not remove aliasing
> + already present in the source image, though it may appear to due
> + to it's excessive blurriness. In any case this is more useful
> + than gaussian for image reconstruction.
> +*/
> +
> +static double
> +notch_kernel (double x, double r)
> +{
> + return general_cubic (x, r, 1.5, -0.25);
> +}
> +
> +/* LANCZOS3: lanczos windowed sinc function from -3 to +3. Very
> + popular with high-end software though I think any advantage over
> + cubics is hidden by quantization and programming mistakes. You
> + will see LANCZOS5 or even 7 sometimes.
> +*/
> +
> +static double
> +sinc (double x)
> +{
> + return x ? sin (M_PI * x) / (M_PI * x) : 1.0;
> +}
> +
> +static double
> +lanczos (double x, int n)
> +{
> + return fabs(x) < n ? sinc (x) * sinc (x * (1.0 / n)) : 0.0;
> +}
> +
> +static double
> +lanczos3_kernel (double x, double r)
> +{
> + if (r < 1.0)
> + return
> + lanczos3_kernel(x * 2 - .5, r * 2) +
> + lanczos3_kernel(x * 2 + .5, r * 2);
> + else
> + return lanczos (x / r, 3);
> +}
> +
> +static int
> +lanczos3_width (double r)
> +{
> + return _max(2.0, ceil (r * 6));
> +}
> +
> +static const filter_info_t filters[] =
> +{
> + { impulse_kernel, impulse_width, "IMPULSE" },
> + { bilinear_kernel, bilinear_width, "BILINEAR" },
> + { box_kernel, box_width, "BOX" },
> + { triangle_kernel, triangle_width, "TRIANGLE" },
> + { catmull_kernel, cubic_width, "CATMULL" },
> + { mitchell_kernel, cubic_width, "MITCHELL" },
> + { lanczos3_kernel, lanczos3_width, "LANCZOS3" },
> + { notch_kernel, cubic_width, "NOTCH" }
> +};
> +
> +/* Returns the number of samples in filter array, computes width & subsample.
> + * Clip is maximum number of samples per filter, if the filter is larger
> + * only the center is calculated, this will approach a box of clip size
> + * as r gets larger.
> + */
> +static int get_sizes(kernel_t filter, double r, int clip,
> + int* width, int* subsample)
> +{
> + int s, w;
> + w = filters[filter].width(r);
> + if (w > clip) w = clip;
> + s = 0;
> + if (w > 1) /* no subsamples needed for impulse filter */
> + while (r * (1 << s) <= 128.0) s++;
> + *width = w;
> + *subsample = s;
> + return (1 << s) * w;
> +}
> +
> +/* Fills in one dimension of the filter array */
> +static void get_filter(kernel_t filter, double r, int width, int subsample,
> + pixman_fixed_t* out)
> +{
> + int i;
> + pixman_fixed_t *p;
> + int n_phases;
> + double step;
> + kernel_func_t func;
> +
> + p = out;
> + n_phases = 1 << subsample;
> + step = 1.0 / n_phases;
> + func = filters[filter].func;
> +
> + /* special-case the impulse filter: */
> + if (width <= 1) {
> + for (i = 0; i < n_phases; ++i)
> + *p++ = pixman_fixed_1;
> + return;
> + }
> +
> + for (i = 0; i < n_phases; ++i) {
> + double frac = (i + .5) * step;
> + /* Center of left-most pixel: */
> + double x1 = ceil (frac - width / 2.0 - 0.5) - frac + 0.5;
> + pixman_fixed_t new_total;
> + double total;
> + int j;
> +
> + total = 0;
> + for (j = 0; j < width; ++j) {
> + double c = func(x1 + j, r);
> + total += c;
> + p[j] = (pixman_fixed_t)(c * 65536.0 + 0.5);
> + }
> +
> + /* Normalize */
> + total = 1 / total;
> + new_total = 0;
> + for (j = 0; j < width; ++j) {
> + pixman_fixed_t t = p[j] = p[j] * total + 0.5;
> + new_total += t;
> + }
> +
> + if (new_total != pixman_fixed_1)
> + p[width / 2] += (pixman_fixed_1 - new_total);
> + p += width;
> + }
> +}
> +
> +
> +/* Create the parameter list for a SEPARABLE_CONVOLUTION filter
> + * with the given kernels and scale parameters.
> + */
> +static pixman_fixed_t *
> +create_separable_convolution (int *n_values,
> + kernel_t xfilter,
> + double xr,
> + int xclip,
> + kernel_t yfilter,
> + double yr,
> + int yclip)
> +{
> + int xwidth, xsubsample, ywidth, ysubsample;
> + int size_x = get_sizes(xfilter, xr, xclip, &xwidth, &xsubsample);
> + int size_y = get_sizes(yfilter, yr, yclip, &ywidth, &ysubsample);
> + pixman_fixed_t *params;
> +
> + *n_values = 4 + size_x + size_y;
> + params = malloc (*n_values * sizeof (pixman_fixed_t));
> + if (!params) return 0;
> +
> + params[0] = pixman_int_to_fixed (xwidth);
> + params[1] = pixman_int_to_fixed (ywidth);
> + params[2] = pixman_int_to_fixed (xsubsample);
> + params[3] = pixman_int_to_fixed (ysubsample);
> +
> + get_filter(xfilter, xr, xwidth, xsubsample, params + 4);
> + get_filter(yfilter, yr, ywidth, ysubsample, params + 4 + size_x);
> +
> + return params;
> +}
> +
> +/* THIS IS FOR TESTING ONLY. Selects kernel used by "GAUSSIAN" */
> +int ikernel = KERNEL_NOTCH;
> +void inckernel(void)
> +{
> + ikernel++;
> + if (ikernel > KERNEL_NOTCH) ikernel = KERNEL_IMPULSE;
> + printf("kernel is %s\n", filters[ikernel].name);
> +}
> +
> +/* ========================================================================== */
> +
> static cairo_bool_t
> _pixman_image_set_properties (pixman_image_t *pixman_image,
> const cairo_pattern_t *pattern,
> @@ -555,16 +928,58 @@ _pixman_image_set_properties (pixman_image_t *pixman_image,
> else
> {
> pixman_filter_t pixman_filter;
> + kernel_t kernel;
> + double dx, dy;
> + int clip;
> +
> + /* Compute scale factors from the pattern matrix. These scale
> + * factors are from user to pattern space, and as such they
> + * are greater than 1.0 for downscaling and less than 1.0 for
> + * upscaling. The factors are the size of an axis-aligned
> + * rectangle with the same area as the parallelgram a 1x1
> + * square transforms to.
> + */
> + dx = hypot (pattern->matrix.xx, pattern->matrix.xy);
> + dy = hypot (pattern->matrix.yx, pattern->matrix.yy);
> +
> + /* Clip at maximum pixman_fixed number. Besides making it
> + * passable to pixman, this avoids errors from inf and nan.
> + */
> + if (! (dx < 0x7FFF)) dx = 0x7FFF;
> + if (! (dy < 0x7FFF)) dy = 0x7FFF;
>
> switch (pattern->filter) {
> case CAIRO_FILTER_FAST:
> pixman_filter = PIXMAN_FILTER_FAST;
> break;
> case CAIRO_FILTER_GOOD:
> + default:
> pixman_filter = PIXMAN_FILTER_GOOD;
> + if (dx > 1.35 || dy > 1.35) {
> + pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
> + kernel = KERNEL_BOX;
> + clip = 16; /* could be 256 if 2-pass filtering is done */
> + /* Match the bilinear filter for dimension scaling up: */
> + if (dx < 1.0) dx = 1.0;
> + if (dy < 1.0) dy = 1.0;
> + }
> break;
> case CAIRO_FILTER_BEST:
> pixman_filter = PIXMAN_FILTER_BEST;
> + pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
> + kernel = KERNEL_CATMULL; /* LANCZOS3 is better but not much */
> + clip = 16;
> + /* blur up to 2x scale, then blend to square pixels for larger: */
> + if (dx < 1.0) {
> + if (dx < 1.0/128) dx = 1.0/128;
> + else if (dx < 0.5) dx = 1.0 / (1.0 / dx - 1.0);
> + else dx = 1.0;
> + }
> + if (dy < 1.0) {
> + if (dy < 1.0/128) dy = 1.0/128;
> + else if (dy < 0.5) dy = 1.0 / (1.0 / dy - 1.0);
> + else dy = 1.0;
> + }
> break;
> case CAIRO_FILTER_NEAREST:
> pixman_filter = PIXMAN_FILTER_NEAREST;
> @@ -577,12 +992,24 @@ _pixman_image_set_properties (pixman_image_t *pixman_image,
> * whatsoever, so it was really a mistake to have it in the
> * API. We could fix this by officially deprecating it, or
> * else inventing semantics and providing an actual
> - * implementation for it. */
> - default:
> - pixman_filter = PIXMAN_FILTER_BEST;
> + * implementation for it. For now used as a test of
> + * all the kernels. */
> + pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
> + kernel = (kernel_t)ikernel;
> + clip = 64; /* !! */
> }
>
> - pixman_image_set_filter (pixman_image, pixman_filter, NULL, 0);
> + if (pixman_filter == PIXMAN_FILTER_SEPARABLE_CONVOLUTION) {
> + int n_params;
> + pixman_fixed_t *params;
> + params = create_separable_convolution
> + (&n_params, kernel, dx, clip, kernel, dy, clip);
> + pixman_image_set_filter (pixman_image, pixman_filter,
> + params, n_params);
> + free (params);
> + } else {
> + pixman_image_set_filter (pixman_image, pixman_filter, NULL, 0);
> + }
> }
>
> {
> diff --git a/src/cairo-xlib-display.c b/src/cairo-xlib-display.c
> index c7708c5..a073d08 100644
> --- a/src/cairo-xlib-display.c
> +++ b/src/cairo-xlib-display.c
> @@ -151,7 +151,7 @@ static const cairo_device_backend_t _cairo_xlib_device_backend = {
>
> static void _cairo_xlib_display_select_compositor (cairo_xlib_display_t *display)
> {
> -#if 1
> +#if 0
> if (display->render_major > 0 || display->render_minor >= 4)
> display->compositor = _cairo_xlib_traps_compositor_get ();
> else if (display->render_major > 0 || display->render_minor >= 0)
> --
> 1.7.9.5
>
> --
> cairo mailing list
> cairo at cairographics.org
> http://lists.cairographics.org/mailman/listinfo/cairo
More information about the cairo
mailing list