[cairo] [PATCH] image: V4 Use convolution filters for sample reconstruction when downscaling
spitzak at gmail.com
spitzak at gmail.com
Thu Jun 12 12:27:43 PDT 2014
From: Bill Spitzak <spitzak at gmail.com>
(This version includes some slight optimization to the filter generator and
clean up of the comments and commit message. I think it is done now, awaiting
any comments!)
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.
This filter generator:
- Removes unnecessary pair of sample/reconstruction filters, only a single
filter is used for each direction
- Can produce filters for derivatives < 1, these will produce anti-aliased
squares for the pixels when you zoom in, similar to OS/X. To get standard
"blurry" results set the size to max(1,derivative).
- Fixed impulse to sample exactly one pixel
- Added BILINEAR that matches the normal bilinear filter and samples 2 pixels.
- Fixed BOX to be the correct trapazoid
- Added TRIANGLE filter (sometimes called tent)
- Added CATMULL (-Rom) filter, replacing LANZCOS2
- Renamed CUBIC to MITCHELL to avoid confusion as the majority of software
uses "cubic" to mean CATMULL or another interpolating filter.
Cairo filter settings changed like this:
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, thus up-scaling produces
anti-aliased squares like OS/X. The improvement with LANZCOS3 is inperceptable
in 8-bit images so I did not use this.
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.
This patch is hardly complete but I need some other assistance to get it
done. I suspect the filter generator should be moved into pixman, perhaps
replacing the existing one. The xlib and xcb backends must use the fallback
if any of these filters are needed, this patch just makes xlib use the
fallback always. Or xrender must be improved to use this filtering.
---
src/cairo-image-source.c | 391 +++++++++++++++++++++++++++++++++++++++++++++-
src/cairo-xlib-display.c | 2 +-
2 files changed, 388 insertions(+), 5 deletions(-)
diff --git a/src/cairo-image-source.c b/src/cairo-image-source.c
index c5bd228..e01846e 100644
--- a/src/cairo-image-source.c
+++ b/src/cairo-image-source.c
@@ -526,6 +526,355 @@ _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_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);
+}
+
+/* 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" }
+};
+
+/* Returns the number of samples in filter array, computes width+subsample */
+static int get_sizes(kernel_t filter, double r, int* width, int* subsample)
+{
+ int s;
+ *width = filters[filter].width(r);
+ s = 0;
+ if (*width > 1) /* no subsamples needed for impulse filter */
+ while (r * (1 << s) <= 128.0 && s < 10) s++;
+ *subsample = s;
+ return (1 << s) * *width;
+}
+
+/* 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,
+ kernel_t yfilter,
+ double yr)
+{
+ int xwidth, xsubsample, ywidth, ysubsample;
+ int size_x = get_sizes(xfilter, xr, &xwidth, &xsubsample);
+ int size_y = get_sizes(yfilter, yr, &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_CATMULL;
+void inckernel(void)
+{
+ ikernel++;
+ if (ikernel > KERNEL_LANCZOS3) 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 +904,39 @@ _pixman_image_set_properties (pixman_image_t *pixman_image,
else
{
pixman_filter_t pixman_filter;
+ kernel_t kernel;
+ double scale_x, scale_y;
+
+ /* 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 transform
+ * of a 1x2 square.
+ */
+ scale_x = hypot (pattern->matrix.xx, pattern->matrix.xy);
+ scale_y = hypot (pattern->matrix.yx, pattern->matrix.yy);
switch (pattern->filter) {
case CAIRO_FILTER_FAST:
pixman_filter = PIXMAN_FILTER_FAST;
break;
case CAIRO_FILTER_GOOD:
+ default:
pixman_filter = PIXMAN_FILTER_GOOD;
+ if (scale_x > 1.35 || scale_y > 1.35) {
+ pixman_filter = PIXMAN_FILTER_SEPARABLE_CONVOLUTION;
+ kernel = KERNEL_BOX;
+ if (scale_x < 1.0) scale_x = 1.0;
+ if (scale_y < 1.0) scale_y = 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 */
+ if (pattern->extend == CAIRO_EXTEND_NONE)
+ kernel = KERNEL_TRIANGLE; /* avoid ringing at edge */
break;
case CAIRO_FILTER_NEAREST:
pixman_filter = PIXMAN_FILTER_NEAREST;
@@ -577,12 +949,23 @@ _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;
}
- 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, scale_x, kernel, scale_y);
+ 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
More information about the cairo
mailing list