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

Last change on this file since 2902 was 2902, checked in by Sam Hocevar, 12 years ago

Support C99 types on Win32 through the same hacks as in libcaca.

File size: 3.9 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    return *(double const *)i1 < *(double const *)i2;
32}
33
34pipi_image_t *pipi_median(pipi_image_t *src, int radius)
35{
36    return pipi_median_ext(src, radius, radius);
37}
38
39/* FIXME: this is in desperate want of optimisation. Here is what could
40 * be done to improve the performance:
41 *  - prefetch the neighbourhood; most neighbours are the same as the
42 *    previous pixels.
43 *  - use a better sort algorithm; bubble sort is ridiculous
44 *  - even better, use state-of-the art median selection, ie. O(3n), for
45 *    most common combinations (9, 25, 49, 81). */
46pipi_image_t *pipi_median_ext(pipi_image_t *src, int rx, int ry)
47{
48    pipi_image_t *dst;
49    pipi_pixels_t *srcp, *dstp;
50    float *srcdata, *dstdata;
51    double *list;
52    int x, y, w, h, i, j, size, gray;
53
54    w = src->w;
55    h = src->h;
56    size = (2 * rx + 1) * (2 * ry + 1);
57
58    gray = (src->last_modified == PIPI_PIXELS_Y_F);
59
60    srcp = gray ? pipi_getpixels(src, PIPI_PIXELS_Y_F)
61                : pipi_getpixels(src, PIPI_PIXELS_RGBA_F);
62    srcdata = (float *)srcp->pixels;
63
64    dst = pipi_new(w, h);
65    dstp = gray ? pipi_getpixels(dst, PIPI_PIXELS_Y_F)
66                : pipi_getpixels(dst, PIPI_PIXELS_RGBA_F);
67    dstdata = (float *)dstp->pixels;
68
69    list = malloc(size * (gray ? 1 : 4) * sizeof(double));
70
71    for(y = 0; y < h; y++)
72    {
73        for(x = 0; x < w; x++)
74        {
75            double *parser = list;
76
77            /* Make a list of neighbours */
78            for(j = -ry; j <= ry; j++)
79            {
80                int y2 = y + j;
81                if(y2 < 0) y2 = h - 1 - ((-y2 - 1) % h);
82                else if(y2 > 0) y2 = y2 % h;
83
84                for(i = -rx; i <= rx; i++)
85                {
86                    int x2 = x + i;
87                    if(x2 < 0) x2 = w - 1 - ((-x2 - 1) % w);
88                    else if(x2 > 0) x2 = x2 % w;
89
90                    if(gray)
91                    {
92                        *parser++ = srcdata[y2 * w + x2];
93                    }
94                    else
95                    {
96                        parser[0] = srcdata[4 * (y2 * w + x2)];
97                        parser[size * 1] = srcdata[4 * (y2 * w + x2) + 1];
98                        parser[size * 2] = srcdata[4 * (y2 * w + x2) + 2];
99                        parser[size * 3] = srcdata[4 * (y2 * w + x2) + 3];
100                        parser++;
101                    }
102                }
103            }
104
105            /* Sort the list */
106            qsort(list, size, sizeof(double), cmpint);
107            if(!gray)
108            {
109                qsort(list + size, size, sizeof(double), cmpint);
110                qsort(list + 2 * size, size, sizeof(double), cmpint);
111                qsort(list + 3 * size, size, sizeof(double), cmpint);
112            }
113
114            /* Store the median value */
115            if(gray)
116            {
117                dstdata[y * w + x] = list[size / 2];
118            }
119            else
120            {
121                dstdata[4 * (y * w + x)] = list[size / 2];
122                dstdata[4 * (y * w + x) + 1] = list[size / 2 + size * 1];
123                dstdata[4 * (y * w + x) + 2] = list[size / 2 + size * 2];
124                dstdata[4 * (y * w + x) + 3] = list[size / 2 + size * 3];
125            }
126        }
127    }
128
129    return dst;
130}
131
Note: See TracBrowser for help on using the repository browser.