source: libpipi/trunk/pipi/filter/median.c @ 3563

Last change on this file since 3563 was 3563, checked in by sam, 5 years ago

Improve the median filter performance.

File size: 4.2 KB
Line 
1/*
2 *  libpipi       Pathetic image processing interface library
3 *  Copyright (c) 2004-2008 Sam Hocevar <sam@zoy.org>
4 *                All Rights Reserved
5 *
6 *  $Id$
7 *
8 *  This library is free software. It comes without any warranty, to
9 *  the extent permitted by applicable law. You can redistribute it
10 *  and/or modify it under the terms of the Do What The Fuck You Want
11 *  To Public License, Version 2, as published by Sam Hocevar. See
12 *  http://sam.zoy.org/wtfpl/COPYING for more details.
13 */
14
15/*
16 * median.c: median filter functions
17 */
18
19#include "config.h"
20
21#include <stdlib.h>
22#include <stdio.h>
23#include <string.h>
24#include <math.h>
25
26#include "pipi.h"
27#include "pipi_internals.h"
28
29static int cmpint(void const *i1, void const *i2)
30{
31    /* On Linux amd64, this is 20 to 30 % faster than using a real
32     * comparison (which wouldn't work on Windows since it expects both
33     * negative and positive values), a ternary operator, or floats instead
34     * of doubles. */
35    union { int32_t i; double d; } u;
36    u.d = *(double const *)i1 - *(double const *)i2;
37    return u.i;
38}
39
40pipi_image_t *pipi_median(pipi_image_t *src, int radius)
41{
42    return pipi_median_ext(src, radius, radius);
43}
44
45/* FIXME: this is in desperate want of optimisation. Here is what could
46 * be done to improve the performance:
47 *  - prefetch the neighbourhood; most neighbours are the same as the
48 *    previous pixels.
49 *  - use a better sort algorithm; bubble sort is ridiculous
50 *  - even better, use state-of-the art median selection, ie. O(3n), for
51 *    most common combinations (9, 25, 49, 81). */
52pipi_image_t *pipi_median_ext(pipi_image_t *src, int rx, int ry)
53{
54    pipi_image_t *dst;
55    pipi_pixels_t *srcp, *dstp;
56    float *srcdata, *dstdata;
57    double *list;
58    int x, y, w, h, i, j, size, gray;
59
60    w = src->w;
61    h = src->h;
62    size = (2 * rx + 1) * (2 * ry + 1);
63
64    gray = (src->last_modified == PIPI_PIXELS_Y_F32);
65
66    srcp = gray ? pipi_get_pixels(src, PIPI_PIXELS_Y_F32)
67                : pipi_get_pixels(src, PIPI_PIXELS_RGBA_F32);
68    srcdata = (float *)srcp->pixels;
69
70    dst = pipi_new(w, h);
71    dstp = gray ? pipi_get_pixels(dst, PIPI_PIXELS_Y_F32)
72                : pipi_get_pixels(dst, PIPI_PIXELS_RGBA_F32);
73    dstdata = (float *)dstp->pixels;
74
75    list = malloc(size * (gray ? 1 : 4) * sizeof(double));
76
77    for(y = 0; y < h; y++)
78    {
79        for(x = 0; x < w; x++)
80        {
81            double *parser = list;
82
83            /* Make a list of neighbours */
84            for(j = -ry; j <= ry; j++)
85            {
86                int y2 = y + j;
87                if(y2 < 0) y2 = h - 1 - ((-y2 - 1) % h);
88                else if(y2 > 0) y2 = y2 % h;
89
90                for(i = -rx; i <= rx; i++)
91                {
92                    int x2 = x + i;
93                    if(x2 < 0) x2 = w - 1 - ((-x2 - 1) % w);
94                    else if(x2 > 0) x2 = x2 % w;
95
96                    if(gray)
97                    {
98                        *parser++ = srcdata[y2 * w + x2];
99                    }
100                    else
101                    {
102                        parser[0] = srcdata[4 * (y2 * w + x2)];
103                        parser[size * 1] = srcdata[4 * (y2 * w + x2) + 1];
104                        parser[size * 2] = srcdata[4 * (y2 * w + x2) + 2];
105                        parser[size * 3] = srcdata[4 * (y2 * w + x2) + 3];
106                        parser++;
107                    }
108                }
109            }
110
111            /* Sort the list */
112            qsort(list, size, sizeof(double), cmpint);
113            if(!gray)
114            {
115                qsort(list + size, size, sizeof(double), cmpint);
116                qsort(list + 2 * size, size, sizeof(double), cmpint);
117                qsort(list + 3 * size, size, sizeof(double), cmpint);
118            }
119
120            /* Store the median value */
121            if(gray)
122            {
123                dstdata[y * w + x] = list[size / 2];
124            }
125            else
126            {
127                dstdata[4 * (y * w + x)] = list[size / 2];
128                dstdata[4 * (y * w + x) + 1] = list[size / 2 + size * 1];
129                dstdata[4 * (y * w + x) + 2] = list[size / 2 + size * 2];
130                dstdata[4 * (y * w + x) + 3] = list[size / 2 + size * 3];
131            }
132        }
133    }
134
135    return dst;
136}
137
Note: See TracBrowser for help on using the repository browser.