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

Last change on this file since 2745 was 2745, checked in by Sam Hocevar, 12 years ago
  • median.c: fix the RGBA median filter.
File size: 4.4 KB
Line 
1/*
2 *  libpipi       Proper image processing implementation 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#include "common.h"
21
22#include <stdlib.h>
23#include <stdio.h>
24#include <string.h>
25#include <math.h>
26
27#include "pipi.h"
28#include "pipi_internals.h"
29
30pipi_image_t *pipi_median(pipi_image_t *src, int radius)
31{
32    return pipi_median_ext(src, radius, radius);
33}
34
35/* FIXME: this is in desperate want of optimisation. Here is what could
36 * be done to improve the performance:
37 *  - prefetch the neighbourhood; most neighbours are the same as the
38 *    previous pixels.
39 *  - use a better sort algorithm; bubble sort is ridiculous
40 *  - even better, use state-of-the art median selection, ie. O(3n), for
41 *    most common combinations (9, 25, 49, 81). */
42pipi_image_t *pipi_median_ext(pipi_image_t *src, int rx, int ry)
43{
44    pipi_image_t *dst;
45    pipi_pixels_t *srcp, *dstp;
46    float *srcdata, *dstdata;
47    double *list;
48    int x, y, w, h, i, j, k, size, gray;
49
50    w = src->w;
51    h = src->h;
52    size = (2 * rx + 1) * (2 * ry + 1);
53
54    gray = (src->last_modified == PIPI_PIXELS_Y_F);
55
56    srcp = gray ? pipi_getpixels(src, PIPI_PIXELS_Y_F)
57                : pipi_getpixels(src, PIPI_PIXELS_RGBA_F);
58    srcdata = (float *)srcp->pixels;
59
60    dst = pipi_new(w, h);
61    dstp = gray ? pipi_getpixels(dst, PIPI_PIXELS_Y_F)
62                : pipi_getpixels(dst, PIPI_PIXELS_RGBA_F);
63    dstdata = (float *)dstp->pixels;
64
65    list = malloc(size * (gray ? 1 : 4) * sizeof(double));
66
67    for(y = 0; y < h; y++)
68    {
69        for(x = 0; x < w; x++)
70        {
71            double tmp;
72            double *parser = list;
73
74            /* Make a list of neighbours */
75            for(j = -ry; j <= ry; j++)
76            {
77                int y2 = y + j;
78                if(y2 < 0) y2 = h - 1 - ((-y2 - 1) % h);
79                else if(y2 > 0) y2 = y2 % h;
80
81                for(i = -rx; i <= rx; i++)
82                {
83                    int x2 = x + i;
84                    if(x2 < 0) x2 = w - 1 - ((-x2 - 1) % w);
85                    else if(x2 > 0) x2 = x2 % w;
86
87                    if(gray)
88                    {
89                        *parser++ = srcdata[y2 * w + x2];
90                    }
91                    else
92                    {
93                        *parser++ = srcdata[4 * (y2 * w + x2)];
94                        *parser++ = srcdata[4 * (y2 * w + x2) + 1];
95                        *parser++ = srcdata[4 * (y2 * w + x2) + 2];
96                        *parser++ = srcdata[4 * (y2 * w + x2) + 3];
97                    }
98                }
99            }
100
101            /* Sort the list */
102            for(i = 0; i < size; i++)
103            {
104                for(j = 0; j < i; j++)
105                {
106                    if(gray)
107                    {
108                        if(list[i] < list[j])
109                        {
110                            tmp = list[i];
111                            list[i] = list[j];
112                            list[j] = tmp;
113                        }
114                    }
115                    else
116                    {
117                        for(k = 0; k < 4; k++)
118                        {
119                            if(list[4 * i + k] < list[4 * j + k])
120                            {
121                                tmp = list[4 * i + k];
122                                list[4 * i + k] = list[4 * j + k];
123                                list[4 * j + k] = tmp;
124                            }
125                        }
126                    }
127                }
128            }
129
130            /* Store the median value */
131            if(gray)
132            {
133                dstdata[y * w + x] = list[0 * size / 2];
134            }
135            else
136            {
137                dstdata[4 * (y * w + x)] = list[size / 2 * 4];
138                dstdata[4 * (y * w + x) + 1] = list[size / 2 * 4 + 1];
139                dstdata[4 * (y * w + x) + 2] = list[size / 2 * 4 + 2];
140                dstdata[4 * (y * w + x) + 3] = list[size / 2 * 4 + 3];
141            }
142        }
143    }
144
145    return dst;
146}
147
Note: See TracBrowser for help on using the repository browser.