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 | |
---|
29 | static 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 | |
---|
40 | pipi_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). */ |
---|
52 | pipi_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 | |
---|