Rosetta Code

Median filter: Difference between revisions

Page Discussion

Median filter (view source)

Revision as of 00:38, 29 July 2011

881 bytes added ,  12 years ago
→‎{{header|C}}: replaced with O(n) method.
(Go solution)
(→‎{{header|C}}: replaced with O(n) method.)
Line 78:
 
=={{header|C}}==
O(n) filter with histogram.
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <ctype.h>
#include <string.h>
 
typedef struct { unsigned char r, g, b; } rgb_t;
Interface:
typedef struct {
int w, h;
rgb_t **pix;
} image_t, *image;
 
typedef struct {
<lang c>image median_filter(image si, int r);</lang>
int r[256], g[256], b[256];
int n;
} color_histo_t;
 
int write_ppm(image im, char *fn)
Support defines and functions:
{
FILE *fp = fopen(fn, "w");
if (!fp) return 0;
fprintf(fp, "P6\n%d %d\n255\n", im->w, im->h);
fwrite(im->pix[0], 1, sizeof(rgb_t) * im->w * im->h, fp);
fclose(fp);
return 1;
}
 
image img_new(int w, int h)
<lang c>#include "imglib.h"
{
int i;
image im = malloc(sizeof(image_t) + h * sizeof(rgb_t*)
+ sizeof(rgb_t) * w * h);
im->w = w; im->h = h;
im->pix = (rgb_t**)(im + 1);
for (im->pix[0] = (rgb_t*)(im->pix + h), i = 1; i < h; i++)
im->pix[i] = im->pix[i - 1] + w;
return im;
}
 
int read_num(FILE *f)
#define XGET(X) (((X)<0)?0:(((X)>=m->width)?m->width-1:(X)))
{
#define YGET(Y) (((Y)<0)?0:(((Y)>=m->height)?m->height-1:(Y)))
int n;
while (!fscanf(f, "%d ", &n)) {
if ((n = fgetc(f)) == '#') {
while ((n = fgetc(f)) != '\n')
if (n == EOF) break;
if (n == '\n') continue;
} else return 0;
}
return n;
}
 
image read_ppm(char *fn)
struct _pm
{
FILE *fp = fopen(fn, "r");
pixel p;
int w, h, maxval;
luminance lum;
image im = 0;
};
if (!fp) return 0;
 
if (fgetc(fp) != 'P' || fgetc(fp) != '6' || !isspace(fgetc(fp)))
static int _cmp(const void *a, const void *b)
goto bail;
 
w = read_num(fp);
h = read_num(fp);
maxval = read_num(fp);
if (!w || !h || !maxval) goto bail;
 
im = img_new(w, h);
fread(im->pix[0], 1, sizeof(rgb_t) * w * h, fp);
bail:
if (fp) fclose(fp);
return im;
}
 
void del_pixels(image im, int row, int col, int size, color_histo_t *h)
{
int i;
struct _pm *ap, *bp;
rgb_t *pix;
ap = (struct _pm *)a;
 
bp = (struct _pm *)b;
if (col < if0 (|| ap->lumcol >= bpim->lum w) return 1;
for (i = row - size; i <= row + size && i < im->h; i++) {
if ( ap->lum < bp->lum ) return -1;
if (i < 0) continue;
return 0;
pix = im->pix[i] + col;
h->r[pix->r]--;
h->g[pix->g]--;
h->b[pix->b]--;
h->n--;
}
}
 
void add_pixels(image im, int row, int col, int size, color_histo_t *h)
{
int i;
rgb_t *pix;
 
if (col < 0 || col >= im->w) return;
for (i = row - size; i <= row + size && i < im->h; i++) {
if (i < 0) continue;
pix = im->pix[i] + col;
h->r[pix->r]++;
h->g[pix->g]++;
h->b[pix->b]++;
h->n++;
}
}
 
void init_histo(image im, int row, int size, color_histo_t*h)
static void _get_median(image m,
unsigned int x, unsigned int y,
int r, pixel *p)
{
int j;
struct _pm *l;
int i, j;
unsigned int a,k;
l = malloc((2*r+1)*(2*r+1)*sizeof(struct _pm));
if ( l != NULL )
{
a = 0;
for(i=-r; i <= r; i++)
{
for(j=-r; j <= r; j++)
{
for(k=0; k < 3; k++)
{
l[a].p[k] = GET_PIXEL(m,XGET(x+i),YGET(y+j))[k];
}
l[a].lum = (2126*l[a].p[0] + 7152*l[a].p[1] +
722*l[a].p[2]) / 10000;
a++;
}
}
qsort(l, (2*r+1)*(2*r+1), sizeof(struct _pm), _cmp);
for(k=0;k<3;k++)
{
(*p)[k] = l[r].p[k];
}
free(l);
}
}</lang>
 
memset(h, 0, sizeof(color_histo_t));
The median filter:
 
for (j = 0; j < size && j < im->w; j++)
add_pixels(im, row, j, size, h);
}
 
<langint c>image median_filtermedian(imageint si*x, int rn)
{
unsigned int x, yi;
for (n /= 2, i = 0; i < 256 && (n -= x[i]) > 0; i++);
image dst;
return i;
pixel op;
}
dst = alloc_img(si->width, si->height);
if ( dst != NULL )
{
for(x=0; x < si->width; x++)
{
for(y=0; y < si->height; y++)
{
_get_median(si, x, y, r, &op);
put_pixel_unsafe(dst, x, y, op[0], op[1], op[2]);
}
}
}
return dst;
}</lang>
 
void median_color(rgb_t *pix, color_histo_t *h)
Usage example:
{
pix->r = median(h->r, h->n);
pix->g = median(h->g, h->n);
pix->b = median(h->b, h->n);
}
 
image median_filter(image in, int size)
<lang c>#include <stdio.h>
{
#include "imglib.h"
int row, col;
image out = img_new(in->w, in->h);
color_histo_t *h = malloc(sizeof(color_histo_t));
 
for (row = 0; row < in->h; row ++) {
for (col = 0; col < in->w; col++) {
if (!col) init_histo(in, row, size, h);
else {
del_pixels(in, row, col - size, size, h);
add_pixels(in, row, col + size, size, h);
}
median_color(out->pix[row] + col, h);
}
}
 
return out;
}
 
int main(int c, char **v)
{
if (c <= 3) {
image input, ei;
printf("Usage: %s size ppm_in ppm_out\n", v[0]);
return 0;
input = get_ppm(stdin);
}
if ( input == NULL ) return 1;
int size = atoi(v[1]);
ei = median_filter(input, 2);
printf("filter size %d\n", size);
free_img(input);
if (size < 0) ifsize ( ei != NULL )1;
{
output_ppm(stdout, ei);
free_img(ei);
}
}</lang>
 
write_ppm(median_filter(read_ppm(v[2]), size), v[3]);
This reads from stdin and writes to stdout.
 
return 0;
The median filter, if implemented this way, can be very slow for big radius values or big images. [http://nomis80.org/ctmf.html This link] taken from Wikipedia shows an algorithm that is O(1)!
}</lang>
 
=={{header|D}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/92674"