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