This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project gfxprim.git. The branch, master has been updated discards 9b8d0d259aedd7b0ce02b082a328f434a7107e5f (commit) via 7609f2afad8b10921084c8d2fe14283873e75ff2 (commit) This update added new revisions after undoing existing revisions. That is to say, the old revision is not a strict subset of the new revision. This situation occurs when you --force push a change and generate a repository containing something like this: * -- * -- B -- O -- O -- O (9b8d0d259aedd7b0ce02b082a328f434a7107e5f) N -- N -- N (7609f2afad8b10921084c8d2fe14283873e75ff2) When this happens we assume that you've already had alert emails for all of the O revisions, and so we here report only the revisions in the N branch from the common base, B. Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- http://repo.or.cz/w/gfxprim.git/commit/7609f2afad8b10921084c8d2fe14283873e75... commit 7609f2afad8b10921084c8d2fe14283873e75ff2 Author: Cyril Hrubis <metan@ucw.cz> Date: Sat Jul 21 18:26:07 2012 +0200 filters: Add initial median filter implementation. diff --git a/include/filters/GP_Filters.h b/include/filters/GP_Filters.h index 1bcc6f8..a6a6f92 100644 --- a/include/filters/GP_Filters.h +++ b/include/filters/GP_Filters.h @@ -65,4 +65,7 @@ /* Laplace based filters */ #include "filters/GP_Laplace.h" +/* Median filter */ +#include "filters/GP_Median.h" + #endif /* GP_FILTERS_H */ diff --git a/include/filters/GP_Median.h b/include/filters/GP_Median.h new file mode 100644 index 0000000..891ae70 --- /dev/null +++ b/include/filters/GP_Median.h @@ -0,0 +1,70 @@ +/***************************************************************************** + * This file is part of gfxprim library. * + * * + * Gfxprim is free software; you can redistribute it and/or * + * modify it under the terms of the GNU Lesser General Public * + * License as published by the Free Software Foundation; either * + * version 2.1 of the License, or (at your option) any later version. * + * * + * Gfxprim is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with gfxprim; if not, write to the Free Software * + * Foundation, Inc., 51 Franklin Street, Fifth Floor, * + * Boston, MA 02110-1301 USA * + * * + * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz> * + * * + *****************************************************************************/ + + /* + + Constant time Median Filter (the computational complexity is independend of + radius). + + The xmed and ymed are radius values for x and y. The algorithm uses xmed + respectively ymed pixel neighbours from each side so the result is median + of rectangle of 2 * xmed + 1 x 2 * ymed + 1 pixels. + + */ + +#ifndef GP_FILTERS_MEDIAN_H +#define GP_FILTERS_MEDIAN_H + +#include "GP_Filter.h" + +int GP_FilterMedianEx(const GP_Context *src, + GP_Coord x_src, GP_Coord y_src, + GP_Size w_src, GP_Size h_src, + GP_Context *dst, + GP_Coord x_dst, GP_Coord y_dst, + int xmed, int ymed, + GP_ProgressCallback *callback); + +GP_Context *GP_FilterMedianExAlloc(const GP_Context *src, + GP_Coord x_src, GP_Coord y_src, + GP_Size w_src, GP_Size h_src, + int xmed, int ymed, + GP_ProgressCallback *callback); + +static inline int GP_FilterMedian(const GP_Context *src, + GP_Context *dst, + int xmed, int ymed, + GP_ProgressCallback *callback) +{ + return GP_FilterMedianEx(src, 0, 0, src->w, src->h, + dst, 0, 0, xmed, ymed, callback); +} + +static inline GP_Context *GP_FilterMedianAlloc(const GP_Context *src, + int xmed, int ymed, + GP_ProgressCallback *callback) +{ + return GP_FilterMedianExAlloc(src, 0, 0, src->w, src->h, + xmed, ymed, callback); +} + +#endif /* GP_FILTERS_MEDIAN_H */ diff --git a/libs/filters/GP_Median.c b/libs/filters/GP_Median.c new file mode 100644 index 0000000..9e60d60 --- /dev/null +++ b/libs/filters/GP_Median.c @@ -0,0 +1,228 @@ +/***************************************************************************** + * This file is part of gfxprim library. * + * * + * Gfxprim is free software; you can redistribute it and/or * + * modify it under the terms of the GNU Lesser General Public * + * License as published by the Free Software Foundation; either * + * version 2.1 of the License, or (at your option) any later version. * + * * + * Gfxprim is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with gfxprim; if not, write to the Free Software * + * Foundation, Inc., 51 Franklin Street, Fifth Floor, * + * Boston, MA 02110-1301 USA * + * * + * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz> * + * * + *****************************************************************************/ + +#include "core/GP_Context.h" +#include "core/GP_GetPutPixel.h" +#include "core/GP_TempAlloc.h" +#include "core/GP_Clamp.h" + +#include "core/GP_Debug.h" + +#include "GP_Median.h" + +#include <string.h> + +#define HIST_INIT(w) + unsigned int R[w][256]; + unsigned int G[w][256]; + unsigned int B[w][256]; + memset(R, 0, sizeof(R)); + memset(G, 0, sizeof(G)); + memset(B, 0, sizeof(B)); + +static inline void hist_inc(unsigned int h[][256], unsigned int x, unsigned int val) +{ + h[x][val]++; +} + +static inline void hist_dec(unsigned int h[][256], unsigned int x, unsigned int val) +{ + h[x][val]--; +} + +static inline void hist_sub(unsigned int *a, unsigned int *b) +{ + int j; + + for (j = 0; j < 256; j++) + a[j] -= b[j]; +} + +static inline void hist_add(unsigned int *a, unsigned int *b) +{ + int j; + + for (j = 0; j < 256; j++) + a[j] += b[j]; +} + +#define HIST_INC hist_inc +#define HIST_DEC hist_dec + +static inline unsigned int hist_median(unsigned int *hist, unsigned int len, + unsigned int trigger) +{ + unsigned int i; + unsigned int acc = 0; + + for (i = 0; i < len; i++) { + acc += hist[i]; + if (acc >= trigger) + return i; + } + + GP_BUG("Trigger not reached"); + return 0; +} + +static int GP_FilterMedian_Raw(const GP_Context *src, + GP_Coord x_src, GP_Coord y_src, + GP_Size w_src, GP_Size h_src, + GP_Context *dst, + GP_Coord x_dst, GP_Coord y_dst, + int xmed, int ymed, + GP_ProgressCallback *callback) +{ + int i, x, y; + + GP_DEBUG(1, "Median filter size %ux%u xmed=%u ymed=%u", + w_src, h_src, 2 * xmed + 1, 2 * ymed + 1); + + /* Create and initalize arrays for row of histograms */ + /* The buffer is w + 2*xmed + 1 size because we read the last value but we don't use it */ + HIST_INIT(w_src + 2 * xmed + 1); + + /* Prefill row of histograms */ + for (x = 0; x < (int)w_src + 2*xmed; x++) { + int xi = GP_CLAMP(x_src + x - xmed, 0, (int)src->w - 1); + + for (y = -ymed; y <= ymed; y++) { + int yi = GP_CLAMP(y_src + y, 0, (int)src->h - 1); + + GP_Pixel pix = GP_GetPixel_Raw_24BPP(src, xi, yi); + + HIST_INC(R, x, GP_Pixel_GET_R_RGB888(pix)); + HIST_INC(G, x, GP_Pixel_GET_G_RGB888(pix)); + HIST_INC(B, x, GP_Pixel_GET_B_RGB888(pix)); + } + } + + /* Apply the median filter */ + for (y = 0; y < (int)h_src; y++) { + unsigned int XR[256], XG[256], XB[256]; + + memset(XR, 0, sizeof(XR)); + memset(XG, 0, sizeof(XG)); + memset(XB, 0, sizeof(XB)); + + /* Compute first histogram */ + for (i = 0; i <= 2*xmed; i++) { + hist_add(XR, R[i]); + hist_add(XG, G[i]); + hist_add(XB, B[i]); + } + + /* Generate row */ + for (x = 0; x < (int)w_src; x++) { + int r = hist_median(XR, 256, (xmed + ymed + 1)); + int g = hist_median(XG, 256, (xmed + ymed + 1)); + int b = hist_median(XB, 256, (xmed + ymed + 1)); + + GP_PutPixel_Raw_24BPP(dst, x_dst + x, y_dst + y, + GP_Pixel_CREATE_RGB888(r, g, b)); + + /* Recompute histograms */ + hist_sub(XR, R[x]); + hist_sub(XG, G[x]); + hist_sub(XB, B[x]); + + hist_add(XR, R[x + 2 * xmed + 1]); + hist_add(XG, G[x + 2 * xmed + 1]); + hist_add(XB, B[x + 2 * xmed + 1]); + } + + /* Recompute histograms, remove y - ymed pixel add y + ymed + 1 */ + for (x = 0; x < (int)w_src + 2*xmed; x++) { + int xi = GP_CLAMP(x_src + x - xmed, 0, (int)src->w - 1); + int yi = GP_CLAMP(y_src + y - ymed, 0, (int)src->h - 1); + + GP_Pixel pix = GP_GetPixel_Raw_24BPP(src, xi, yi); + + HIST_DEC(R, x, GP_Pixel_GET_R_RGB888(pix)); + HIST_DEC(G, x, GP_Pixel_GET_G_RGB888(pix)); + HIST_DEC(B, x, GP_Pixel_GET_B_RGB888(pix)); + + yi = GP_MIN(y_src + y + ymed + 1, (int)src->h - 1); + + pix = GP_GetPixel_Raw_24BPP(src, xi, yi); + + HIST_INC(R, x, GP_Pixel_GET_R_RGB888(pix)); + HIST_INC(G, x, GP_Pixel_GET_G_RGB888(pix)); + HIST_INC(B, x, GP_Pixel_GET_B_RGB888(pix)); + } + + if (GP_ProgressCallbackReport(callback, y, h_src, w_src)) { + // GP_TempAllocFree(temp); + return 1; + } + } + + GP_ProgressCallbackDone(callback); + + return 0; +} + +int GP_FilterMedianEx(const GP_Context *src, + GP_Coord x_src, GP_Coord y_src, + GP_Size w_src, GP_Size h_src, + GP_Context *dst, + GP_Coord x_dst, GP_Coord y_dst, + int xmed, int ymed, + GP_ProgressCallback *callback) +{ + GP_CHECK(src->pixel_type == dst->pixel_type); + + /* Check that destination is large enough */ + GP_CHECK(x_dst + (GP_Coord)w_src <= (GP_Coord)dst->w); + GP_CHECK(y_dst + (GP_Coord)h_src <= (GP_Coord)dst->h); + + GP_CHECK(xmed >= 0 && ymed >= 0); + + return GP_FilterMedian_Raw(src, x_src, y_src, w_src, h_src, + dst, x_dst, y_dst, xmed, ymed, callback); +} + +GP_Context *GP_FilterMedianExAlloc(const GP_Context *src, + GP_Coord x_src, GP_Coord y_src, + GP_Size w_src, GP_Size h_src, + int xmed, int ymed, + GP_ProgressCallback *callback) +{ + int ret; + + GP_CHECK(xmed >= 0 && ymed >= 0); + + GP_Context *dst = GP_ContextAlloc(w_src, h_src, src->pixel_type); + + if (dst == NULL) + return NULL; + + ret = GP_FilterMedian_Raw(src, x_src, y_src, w_src, h_src, + dst, 0, 0, xmed, ymed, callback); + + if (ret) { + GP_ContextFree(dst); + return NULL; + } + + return dst; +} ----------------------------------------------------------------------- Summary of changes: libs/filters/GP_Median.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) repo.or.cz automatic notification. Contact project admin jiri.bluebear.dluhos@gmail.com if you want to unsubscribe, or site admin admin@repo.or.cz if you receive no reply. -- gfxprim.git ("A simple 2D graphics library with emphasis on correctness and well-defined operation.")