Thread: Median of a 2d matrix

Hey,

I m doing a image processing project. I need to find the median in a 2d matrix.

What is the another way, instead of saving elements in 1d array, sort and then find median.

What is the another way, instead of saving elements in 1d array, sort and then find median.

Why not just sort the 2d array, then find the median?


Jim

I think complexity can be reduced in that way..

The only optimisation Wikipedia mentions is the use of a selection sort, but only until the median value is found.

Since this is for an image processing project,
Are you referring to a median filter?

Median filter - Wikipedia, the free encyclopedia

-

Yes, I am referring median filter

hey I am getting below error in my code.I am really fail to overcome this.
median22: malloc.c:2451: sYSMALLOc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 * (sizeof(size_t))) - 1)) & ~((2 * (sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long)old_end & pagemask) == 0)' failed.
Aborted (core dumped)


My code is:

#include <stdio.h>
#include <stdlib.h>
#define SIZE 50

typedef struct PGM
{
char name[100];
int width;
int height;
int max_value;
int **matrix;
} PGM;

int ** create_matrix(int height, int width)
{

int **matrix = malloc(height*sizeof(int*)) ;

if (matrix)
{
int i;
for (i = 0; i < height; i++)
{
matrix[i] =malloc(width * sizeof (int)) ;
}
}
return matrix;
}


//void display(PGM *p) {
// printf("displaying p matrix");
// printf("name %s\n", p->name);
// printf("height %d width %d max_value %d\n", p->height, p->width, p->max_value);
// int i,j;
// for (i = 0; i < p->height; i++) {
// for (j = 0; j < p->width; j++) {
// printf("%2d ", p->matrix[i][j]);
// }
// printf("\n");
// }
// }


void skip_comments(FILE* fp, char* line, int size)
{
do{
fgets(line, size, fp);
if (line[0] != '#')
{
return ;
}
} while(line!= NULL);
}

PGM* f2p(char *file_name) {

FILE * fp;
char c;
char name[100];
char line[SIZE];
int height, width, max_value;

fp = fopen(file_name, "r");

if (fp == NULL)
return NULL;

PGM *p = malloc(sizeof(PGM));


skip_comments(fp, line, SIZE);
sscanf(line, "%s", p->name);

skip_comments(fp, line, SIZE);
sscanf(line, "%d %d", &width, &height);

skip_comments(fp, line, SIZE);
sscanf(line, "%d", &max_value);

int **matrix = malloc(height*sizeof(int*)) ;
if (matrix){
int i,j;
for (i = 0; i < height; i++) {

matrix[i] = malloc(width * sizeof (int)) ;
for (j = 0; j < width; j++) {

c = fscanf(fp, "%d", &matrix[i][j]);
}
}

p->matrix = matrix;
p->height = height;
p->width = width;
p->max_value = max_value;
return p;
}

fclose(fp);
return NULL;
}

void p2f(PGM* p, char *file_name) {
FILE* fp = fopen(file_name, "w");
fprintf(fp, "%s\n", p->name);
fprintf(fp, "%d %d\n%d\n", p->width, p->height, p->max_value);
int i,j;
for (i = 0; i < p->height; i++)
{
for (j = 0; j < p->width; j++)
{
fprintf(fp, "%d ", p->matrix[i][j]);
}
fprintf(fp,"\n");
}
fclose(fp);
}

int sort(int *a,int filt)
{
int i,j,t;
for (i = 1 ; i <= filt; i++)
{
for (j = 1 ; j <= filt ; j++)
{
if (a[j] <= a[j+1])
{
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
else continue ;
}
}
return a[(filt+1)/2];
}


void apply_median_filter(int** source, int** dest, int height, int width,int k,int filt) {
int i,j,m,l,median;
for (i = k; i < height; i++){
for (j = k; j < width ; j++){
int c=0;
int *temp=(int*)malloc(filt*filt*sizeof(int));
for(m=0;m<filt;m++){

for(l=0;l<filt;l++)
temp[c++]=source[i-k+m][j-k+l];
}

median=sort(temp,filt*filt);
dest[i-k][j-k]=median;
}
}

}



void apply_padding(PGM* p,int n)
{
int k;
k=n/2;
int new_height = p->height + k;
int new_width = p->width + k;


int **matrix = create_matrix(new_height, new_width);


if (matrix){
int i,j;


for (i = 0; i < new_height; i++){
for (j = 0; j < new_width; j++){

if((i<k) || (j<k) || i>(p->height) || j>(p->width))

matrix[i][j] = 0;
}
}


for (i = k; i < new_height-k; i++){
for (j = k; j < new_width-k; j++) {
matrix[i][j] = p->matrix[i-k][j-k];
}
}

apply_median_filter(matrix, p->matrix, p->height, p->width,k,n);


}
}
int main()
{
char file_name[50];
int n;
printf("Enter the file name you want to open\n");
scanf("%s",file_name);
PGM *p = f2p(file_name);

printf("Enter any odd number for the mask-size which you want to apply\n");
scanf("%d",&n);

apply_padding(p,n);
//display(p);

char file_name1[] = "output.pgm";
p2f(p, file_name1);
}

Argh! My eyes are bleeding!

Please post your code in [code][/code] tags and make sure it is properly formatted and indented. Use the "preview post" button (you may need to use the advanced editor UI) to ensure your post looks nice before you submit it.