Optimization of C code: smoothing an image.

In summary, the compiler errors I'm getting are related to the function calls in smooth(). I need help figuring out how to fix them.
  • #1
Fronzbot
62
0

Homework Statement


I need to optimize this given code:
Code:
/* A struct used to compute averaged pixel value */
typedef struct {
    int red;
    int green;
    int blue;
    int num;
} pixel_sum;

/* Compute min and max of two integers, respectively */
static int min(int a, int b) { return (a < b ? a : b); }
static int max(int a, int b) { return (a > b ? a : b); }

/*
 * initialize_pixel_sum - Initializes all fields of sum to 0
 */
static void initialize_pixel_sum(pixel_sum *sum)
{
    sum->red = sum->green = sum->blue = 0;
    sum->num = 0;
    return;
}

/*
 * accumulate_sum - Accumulates field values of p in corresponding
 * fields of sum
 */
static void accumulate_sum(pixel_sum *sum, pixel p)
{
    sum->red += (int) p.red;
    sum->green += (int) p.green;
    sum->blue += (int) p.blue;
    sum->num++;
    return;
}

/*
 * assign_sum_to_pixel - Computes averaged pixel value in current_pixel
 */
static void assign_sum_to_pixel(pixel *current_pixel, pixel_sum sum)
{
    current_pixel->red = (unsigned short) (sum.red/sum.num);
    current_pixel->green = (unsigned short) (sum.green/sum.num);
    current_pixel->blue = (unsigned short) (sum.blue/sum.num);
    return;
}

/*
 * avg - Returns averaged pixel value at (i,j)
 */
static pixel avg(int dim, int i, int j, pixel *src)
{
    int ii, jj;
    pixel_sum sum;
    pixel current_pixel;

    initialize_pixel_sum(&sum);
    for(ii = max(i-1, 0); ii <= min(i+1, dim-1); ii++)
	for(jj = max(j-1, 0); jj <= min(j+1, dim-1); jj++)
	    accumulate_sum(&sum, src[RIDX(ii, jj, dim)]);

    assign_sum_to_pixel(&current_pixel, sum);
    return current_pixel;
}

/******************************************************
 * Your different versions of the smooth kernel go here
 ******************************************************/

/*
 * naive_smooth - The naive baseline version of smooth
 */
char naive_smooth_descr[] = "naive_smooth: Naive baseline implementation";
void naive_smooth(int dim, pixel *src, pixel *dst)
{
    int i, j;

    for (i = 0; i < dim; i++)
	for (j = 0; j < dim; j++)
	    dst[RIDX(i, j, dim)] = avg(dim, i, j, src);
}

Homework Equations


The Attempt at a Solution


I figured the best approach would be to eliminate the function calls, but I'm getting a bunch of compiler errors that I can't figure out how to fix. I will post my code and then the compiler messages. Basically (for now, at least) I'm just looking for help on how to fix the errors I'm getting. From there I can move forward and tweak until I get at least a 3.5x speed up (required for a 100 on this assignment).

Code:
424: void smooth(int dim, pixel *src, pixel *dst)
425: {
426:  int i, j;
427:  pixel *current_pixel;
428:  pixel_sum *sum;
429:  pixel_sum *sum_red;
430:  pixel_sum *sum_green;
431:  pixel_sum *sum_blue;
432:  pixel_sum *sum_num;
433:  pixel p;
434:  int red, green, blue, num;
435:  int ii, jj;
436:  int min_i, min_j, max_i, max_j;
437:  int a_min_i, a_max_i, b_min, b_max;
438:  int a_min_j, a_max_j;
439:
440:   
441:  for (i = 0; i < dim; i++){
442:    for (j = 0; j < dim; j++){
443:       sum = (int *)&sum;
444:       sum_red = 0;
445:       sum_green = 0;
446:       sum_blue = 0;
447:       sum_num = 0;
448:
449:       a_max_i = i-1;
450:       b_max = 0;
451:       a_min_i = i+1;
452:       b_min = dim-1;
453:       max_i = (a_max_i > b_max ? a_max_i : b_max);
454:       min_i = (a_min_i < b_min ? a_min_i : b_min);
455:
456:       a_max_j = j-1;
457:       a_min_j = j+1;
458:       max_j = (a_max_j > b_max ? a_max_j : b_max);
459:       min_i = (a_min_i < b_min ? a_min_j : b_min);
460:       for(ii = max_i; ii <= min_i; ii++){
461:          for(jj = max_j; jj <= min_j; jj++){
462:              p = src[RIDX(ii, jj, dim)];
463:              sum_red += (int) p.red;
464:              sum_green += (int) p.green;
465:              sum_blue += (int) p.blue;
466:              sum_num++;
467:     
468:          }
469:       }
470:       current_pixel = (int *)&current_pixel;
471:       current_pixel->red = (unsigned short) (sum.red/sum.num);
472:       current_pixel->green = (unsigned short) (sum.green/sum.num);
473:       current_pixel->blue = (unsigned short) (sum.blue/sum.num);
474:       dst[RIDX(i, j, dim)] = *current_pixel;
475:     } 
476:  }
477:}

COMPILER:
Code:
kernels.c: In function âsmoothâ:
kernels.c:443: warning: dereferencing type-punned pointer will break strict-aliasing rules
kernels.c:443: warning: assignment from incompatible pointer type
kernels.c:470: warning: dereferencing type-punned pointer will break strict-aliasing rules
kernels.c:470: warning: assignment from incompatible pointer type
kernels.c:471: error: request for member âredâ in something not a structure or union
kernels.c:471: error: request for member ânumâ in something not a structure or union
kernels.c:472: error: request for member âgreenâ in something not a structure or union
kernels.c:472: error: request for member ânumâ in something not a structure or union
kernels.c:473: error: request for member âblueâ in something not a structure or union
kernels.c:473: error: request for member ânumâ in something not a structure or union
kernels.c:434: warning: unused variable ânumâ
kernels.c:434: warning: unused variable âblueâ
kernels.c:434: warning: unused variable âgreenâ
kernels.c:434: warning: unused variable âredâ
make: *** [kernels.o] Error 1

Any help would be greatly appreciated!
 
Physics news on Phys.org
  • #2
The first two warnings refer to line 443
443: sum = (int *)&sum;

Why are you doing this? sum is a pointer to pixel_sum, so why are you casting it to int *?
 
  • #3
Mark44 said:
The first two warnings refer to line 443
443: sum = (int *)&sum;

Why are you doing this? sum is a pointer to pixel_sum, so why are you casting it to int *?

Honestly, that was just me trying to get rid of the error. My original code had
sum = &sum; There is no good reason I recast it, but I figured it was worth a shot :rolleyes:

Also, I talked to my professor briefly and he pointed out that there were a lot of areas where i was confusing structures and pointers. I'll tidy up the code a bit and come back with any problems I still have (hopefully none!)
 
  • #4
Here is one of those places:
471: current_pixel->red = (unsigned short) (sum.red/sum.num);

sum is a pointer to pixel_sum. You are using it as if it were a struct, not a pointer. The parenthesized expression on the right should be (sum->red/sum->num) or ((*sum).red/(*sum).num) . Most likely this expression came from the earlier code, where you had p.red/p.num, but in that code p was a struct.
 
  • #5
Cool, thanks Mark! I figured out why I was getting those errors and I now have fixed them. However, now when I run the code I get an error when dim=96. Obviously there is something wrong with my code so I'll start walking through it to make sure it's doing the same thing as naive_smooth. If anyone can give me any hints I would be grateful :smile:

Here's the new code:
Code:
void smooth(int dim, pixel *src, pixel *dst)
{
	int i, j;
  	pixel *current_pixel;
  	pixel current_pixel_val;
  	pixel_sum *sum;
  	pixel_sum sum_val;
  	pixel p;
  	int ii, jj;
  	int min_i, min_j, max_i, max_j;
  	int a_min_i, a_max_i, b_min, b_max;
  	int a_min_j, a_max_j;


  	for (i = 0; i < dim; i++){
  		for (j = 0; j < dim; j++){
  	    	sum = &sum_val;
  	    	sum->red = 0;
  	    	sum->green = 0;
  	    	sum->blue = 0;
  	    	sum->num = 0;

  	    	a_max_i = i-1;
  	    	b_max = 0;
  	    	a_min_i = i+1;
  	    	b_min = dim-1;
  	    	max_i = (a_max_i > b_max ? a_max_i : b_max);
  	    	min_i = (a_min_i < b_min ? a_min_i : b_min);

  	    	a_max_j = j-1;
  	    	a_min_j = j+1;
  	    	max_j = (a_max_j > b_max ? a_max_j : b_max);
  	    	min_j = (a_min_i < b_min ? a_min_j : b_min);
  	    	for(ii = max_i; ii <= min_i; ii++){
				for(jj = max_j; jj <= min_j; jj++){
					  p = src[RIDX(ii, jj, dim)];
					  sum->red += (int) p.red;
					  sum->green += (int) p.green;
					  sum->blue += (int) p.blue;
					  sum->num++;

				}
  	    	}
  	    	current_pixel = &current_pixel_val;
  	    	current_pixel->red = (unsigned short) (sum->red/sum->num);
  	    	current_pixel->green = (unsigned short) (sum->green/sum->num);
  	    	current_pixel->blue = (unsigned short) (sum->blue/sum->num);
  	    	dst[RIDX(i, j, dim)] = *current_pixel;
  	  	}
  	}
}
 
  • #7
Code:
ERROR: Dimension=96, 282 errors
E.g., 
You have dst[95][93].{red,green,blue} = {28763,43398,44112}
It should be dst[95][93].{red,green,blue} = {23151,37441,41242}
Benchmark "smooth() function" failed correctness check for dimension 96.

We're using a makefile that runs through the code. As far as I know, that error isn't very helpful beyond saying "your pixels are wrong".
 
  • #8
That error is reporting on the last row. You have an edge effect error.
 
  • #9
D H said:
That error is reporting on the last row. You have an edge effect error.

I'm not entirely sure what an edge effect error is, but if I were to wager a guess I'd say it has to do with the pixels on the edges of the picture getting skewed because it's trying to smooth them in with pixels that don't exist (outside the picture)? What steps could I take to fix that? Possibly create another loop for rows 0 and dim-1 and columns 0 and dim-1? Or is that unnecessary?
 
  • #10
I don't think the problem is with dim = 96 so much, but rather that you are getting the wrong totals for the number red, green, and blue pixels.

It could be because your 3rd and 4th nested loops are running too many times.
Code:
for(ii = max_i; ii <= min_i; ii++){
   for(jj = max_j; jj <= min_j; jj++){
The usual practice for C and C++ for loops is to write the terminating condition with <, rather than <=.

For example, this loop runs 10 times:
for (i = 0; i < 10; i++)
{
...
}
This loop runs 11 times:
for (i = 0; i <= 10; i++)
{
...
}
I might be wrong, though.
 
  • #11
This looks might problematic:
Code:
  	    	max_j = (a_max_j > b_max ? a_max_j : b_max);
  	    	min_j = (a_min_i < b_min ? a_min_j : b_min);

Too late now, but what is wrong with inline?
 
  • #12
D H said:
This looks might problematic:
Code:
  	    	max_j = (a_max_j > b_max ? a_max_j : b_max);
  	    	min_j = (a_min_i < b_min ? a_min_j : b_min);

Too late now, but what is wrong with inline?

Wow, can't believe I missed that! Thanks, it runs now!
Only an average speed up of 1.2x though and I need 3.5x. Now what's this inline thing? I've never used it and certainly do not recall learning it in class. Does it align values in the cache or something?
 
  • #13
inline causes the compiler to put the code for a function inline in the object code, rather than emitting the instructions that call the function and return from it. Making a function inline can save some time if a function is called a great many times. It's essentially what you did by hand, putting all your code into the smooth function.
 
  • #14
Ok, gotcha, thanks!

I stumbled across this code which runs 4.3x faster (though I don't want to use it because 1) that's cheating and 2) I've put in so much work already that I don't want it all to be for nothing):
Code:
static inline void add_pixel_2(pixel_sum *sum, pixel *a, pixel *b) {
    sum->red = a->red + b->red;
    sum->green = a->green + b->green;
    sum->blue = a->blue + b->blue;
}

static inline void add_pixel_3(pixel_sum *sum, pixel *a, pixel *b, pixel *c) {
    sum->red = a->red + b->red + c->red;
    sum->green = a->green + b->green + c->green;
    sum->blue = a->blue + b->blue + c->blue;
}

static inline void do_row_sum(pixel_sum *sums, int dim, pixel *row) {
    int i;
    add_pixel_2(sums++, row, row+1);
    row++;
    for (i=1; i<dim-1; i++) {
        add_pixel_3(sums++, row-1, row, row+1);
        row++;
    }
    add_pixel_2(sums, row-1, row);
}

static inline void avg_pixel_sums_2(pixel *dst, pixel_sum *a, pixel_sum *b, int num) {
    dst->red = (a->red + b->red)/num;
    dst->green = (a->green + b->green)/num;
    dst->blue = (a->blue + b->blue)/num;
}

static inline void avg_pixel_sums_3(pixel *dst, pixel_sum *a, pixel_sum *b, pixel_sum *c, int num) {
    dst->red = (a->red + b->red + c->red)/num;
    dst->green = (a->green + b->green + c->green)/num;
    dst->blue = (a->blue + b->blue + c->blue)/num;
}

void smooth(int dim, pixel *src, pixel *dst) {
    pixel_sum *row_sums = malloc(3*dim*sizeof(pixel_sum));
    pixel_sum *r0 = row_sums;
    pixel_sum *r1 = r0+dim;
    pixel_sum *r2;
    int i, j;

    do_row_sum(r0, dim, src);
    do_row_sum(r1, dim, src+dim);
    // calculate row 0
    avg_pixel_sums_2(dst++, r0++, r1++, 4);
    for (i=1; i<dim-1; i++)
        avg_pixel_sums_2(dst++, r0++, r1++, 6);
    avg_pixel_sums_2(dst++, r0, r1, 4);

    // calculate all the middle rows
    for (i=1; i<dim-1; i++) {
        r0 = row_sums+((i-1)%3)*dim;
        r1 = row_sums+(i%3)*dim;
        r2 = row_sums+((i+1)%3)*dim;
        do_row_sum(r2, dim, src+(i+1)*dim);
        avg_pixel_sums_3(dst++, r0++, r1++, r2++, 6);
        for (j=1; j<dim-1; j++)
            avg_pixel_sums_3(dst++, r0++, r1++, r2++, 9);
        avg_pixel_sums_3(dst++, r0, r1, r2, 6);
    }

    // calculate the last row
    r0 = row_sums+((i-1)%3)*dim;
    r1 = row_sums+(i%3)*dim;
    avg_pixel_sums_2(dst++, r0++, r1++, 4);
    for (i=1; i<dim-1; i++)
        avg_pixel_sums_2(dst++, r0++, r1++, 6);
    	avg_pixel_sums_2(dst, r0, r1, 4);
}

Now what I'm having trouble with is understand where the significant speed-up occurs. I THINK it's because there are separate loops for when the rows are on top and bottom because there are less pixels to average but I could be wrong. Also, what use is malloc here? I mean, I think it's freeing memory but if I were to not include that wouldn't it not matter too much?
 
  • #15
That code performs well because
  • It uses (borderline abuses) pointer arithmetic.
  • It uses inlined functions.
  • It has reorganized the operations.
  • It treats the special things that must be done on the edges separately.
<rant>

I can't resist asking: What kind of silly class is this? This is not a jibe at you, Fronzbot. It's a jibe at your professor and at your school. At this stage of your education you should be learning the basics. How computers work, how to program, data structures, algorithms. By your own admittance, you are having problems understanding structures and pointers. This is what your school should be teaching you, not how to optimize some previously written chunk of code.

Optimization is one of the last concerns (or it should be; 50 years of programming nightmares tells us this). Getting the right data structures and right algorithms will go a long, long ways toward making for a more efficient program; efficiency ofttimes is a freebie. There are many software quality metrics. Running fast is one metric, but it is often the least important metric. More important: Is your code understandable, not overly complex, maintainable, and verifiable? Performance can go against all of these other metrics. Most programs have very small bottlenecks where performance is key. A lot of times, 1% of the code (in terms of lines) is responsible for 90% of the CPU usage.

If this optimization class has any merits the teaching should be optimal. To identify those few places where optimization is important you should have been taught how to identify those bottlenecks. To improve the performance in those hot spots you should have been taught little things like inlining and use of pointer arithmetic and big things like knowing when to rewrite the whole mess from scratch. To keep the code maintainable they should have taught you about all those other software quality metrics.

</rant>
 
  • #16
You haven't told us the purpose of your code, but from your later remarks, perhaps the averaging that occurs takes place by computing the average values for a pixel from its 8 neighbors (for an interior pixel). If that's the case, pixels along the top or bottom rows, or along the vertical edges don't have as many neighbors, so the algorithm needs to take those facts into account. A pixel in the top row, for example, has left and right neighbors, and three neighbors in the next row. And similar for the bottom row. Otherwise, it's not clear to me what your code is supposed to do.

malloc allocates memory; it doesn't free it.
 
  • #17
It might be worth mentioning, I'm an Electrical Engineering major and this is an Electrical Engineering class. This class is a basic class to understand the point where software meets hardware (but we focus more on the software side. Computer Architecture focuses on hardware). That may explain my severe ineptitude when it comes to software :p

As for the class- for the most part, I think it's stupid. I understand I definitely need to know at least SOME software, but some of these labs I have are equivalent to labs for CompSci majors. The work in class, like understanding caches and memory, are pretty useful all things considered.

Also, thanks for the explanation- I figured there was something with the edges involved. I think I'm getting this, but I'll come back if I have any more hiccups!

EDIT- sorry, Mark, you're right! I forgot to say what it does- it takes an image with dim equal to multiples of 32 (32, 64, 96, etc) and smooths it which involves averaging the pixels around one pixel and moving to the next and doing the same.
 
  • #18
You certainly can take advantage of the items I talked about before my rant in your code.
 
  • #19
Fronzbot said:
As for the class- for the most part, I think it's stupid. I understand I definitely need to know at least SOME software, but some of these labs I have are equivalent to labs for CompSci majors. The work in class, like understanding caches and memory, are pretty useful all things considered.
The line between hardware and software is pretty blurred, so it would be to your advantage to keep an open mind. As a case in point, think about graphics processors. One of the reasons that computers are able to display a large number of frames per second of high resolution graphics is that many operations that used to be done in software (vertex shading, texture mapping and shading, etc.) are now done in hardware, and hence can be done much faster. It's entirely possible that you as a hardware engineer might be called on to implement in silicon the code that another engineer implemented in software, and due to memory or speed constraints, might be called on to optimize that software code.
 
  • #20
So I started from scratch and rethought the whole process and thought I had something that would work well but I'm confused on a few things.

1) I'm getting weird compiler errors that I can't seem to fix
2) It still runs, but the speed up is only 1.2 and it should be much higher (I think).
3) Would it run faster if I used pointers rather than arrays? If so, how would I tell a pointer to, say, src[0] to increment the right element rather than the left?

Any suggestions at what I should look at?

New code:
Code:
486: void smooth(int dim, struct pixel src[dim][dim], struct pixel dst[dim][dim])
{
    int i, j;
    //top left
    dst[0][0].red = (src[0][0].red + src[1][0].red + src[0][1].red + src[1][1].red)/4;
    dst[0][0].green = (src[0][0].green + src[1][0].green + src[0][1].green + src[1][1].green)/4;
    dst[0][0].blue = (src[0][0].blue + src[1][0].blue + src[0][1].blue + src[1][1].blue )/4;

    //top right
    dst[0][dim-1].red = (src[0][dim-1].red + src[1][dim-1].red + src[0][dim-2].red + src[1][dim-2].red)/4;
    dst[0][dim-1].green = (src[0][dim-1].green + src[1][dim-1].green + src[0][dim-2].green + src[1][dim-2].green)/4;
    dst[0][dim-1].blue = (src[0][dim-1].blue + src[1][dim-1].blue + src[0][dim-2].blue + src[1][dim-2].blue )/4;

    //bottom left
    dst[dim-1][0].red = (src[dim-1][0].red + src[dim-1][1].red + src[dim-2][0].red + src[dim-2][1].red)/4;
    dst[dim-1][0].green = (src[dim-1][0].green + src[dim-1][1].green + src[dim-2][0].green + src[dim-2][1].green)/4;
    dst[dim-1][0].blue = (src[dim-1][0].blue + src[dim-1][1].blue + src[dim-2][0].blue + src[dim-2][1].blue )/4;

    //bottom right
    dst[dim-1][dim-1].red = (src[dim-1][dim-1].red + src[dim-1][dim-2].red + src[dim-2][dim-1].red + src[dim-2][dim-2].red)/4;
    dst[dim-1][dim-1].green = (src[dim-1][dim-1].green + src[dim-1][dim-2].green + src[dim-2][dim-1].green + src[dim-2][dim-2].green)/4;
    dst[dim-1][dim-1].blue = (src[dim-1][dim-1].blue + src[dim-1][dim-2].blue + src[dim-2][dim-1].blue + src[dim-2][dim-2].blue )/4;

    //top edge
    for(i = 1; i < dim-1; i++){
        dst[0][i].red = (src[0][i].red + src[0][i-1].red + src[0][i+1].red + src[1][i].red + src[1][i-1].red + src[1][i+1].red)/6;
        dst[0][i].green = (src[0][i].green + src[0][i-1].green + src[0][i+1].green + src[1][i].green + src[1][i-1].green + src[1][i+1].green)/6;
        dst[0][i].blue = (src[0][i].blue + src[0][i-1].blue + src[0][i+1].blue + src[1][i].blue + src[1][i-1].blue + src[1][i+1].blue)/6;
    }

    //bottom edge
    for(i = 1; i < dim-1; i++){
        dst[dim-1][i].red = (src[dim-1][i].red + src[dim-1][i-1].red + src[dim-1][i+1].red + src[dim-2][i].red + src[dim-2][i-1].red + src[dim-2][i+1].red)/6;
        dst[dim-1][i].green = (src[dim-1][i].green + src[dim-1][i-1].green + src[dim-1][i+1].green + src[dim-2][i].green + src[dim-2][i-1].green + src[dim-2][i+1].green)/6;
        dst[dim-1][i].blue = (src[dim-1][i].blue + src[dim-1][i-1].blue + src[dim-1][i+1].blue + src[dim-2][i].blue + src[dim-2][i-1].blue + src[dim-2][i+1].blue)/6;
    }

    //left column
    for(i = 1; i < dim-1; i++){
        dst[i][0].red = (src[i][0].red + src[i-1][0].red + src[i+1][0].red + src[i][1].red + src[i-1][1].red + src[i+1][1].red)/6;
        dst[i][0].green = (src[i][0].green + src[i-1][0].green + src[i+1][0].green + src[i][1].green + src[i-1][1].green + src[i+1][1].green)/6;
        dst[i][0].blue = (src[i][0].blue + src[i-1][0].blue + src[i+1][0].blue + src[i][1].blue + src[i-1][1].blue + src[i+1][1].blue)/6;
    }

    //right column
    for(i = 1; i < dim-1; i++){
        dst[i][dim-1].red = (src[i][dim-1].red + src[i-1][dim-1].red + src[i+1][dim-1].red + src[i][dim-2].red + src[i-1][dim-2].red + src[i+1][dim-2].red)/6;
        dst[i][dim-1].green = (src[i][dim-1].green + src[i-1][dim-1].green + src[i+1][dim-1].green + src[i][dim-2].green + src[i-1][dim-2].green + src[i+1][dim-2].green)/6;
        dst[i][dim-1].blue = (src[i][dim-1].blue + src[i-1][dim-1].blue + src[i+1][dim-1].blue + src[i][dim-2].blue + src[i-1][dim-2].blue + src[i+1][dim-2].blue)/6;
    }

    //middle of picture
    for(i = 2; i < dim-2; i++){
        for(j = 2; j < dim-2; j+=2){
            dst[i][j].red = (src[i][j].red + src[i][j+1].red + src[i][j-1].red + src[i-1][j].red + src[i-1][j-1].red + src[i-1][j+1].red + src[i+1][j].red + src[i+1][j-1].red + src[i+1][j+1].red)/9;
            dst[i][j].green = (src[i][j].green + src[i][j+1].green + src[i][j-1].green + src[i-1][j].green + src[i-1][j-1].green + src[i-1][j+1].green + src[i+1][j].green + src[i+1][j-1].green + src[i+1][j+1].green)/9;
            dst[i][j].blue = (src[i][j].blue + src[i][j+1].blue + src[i][j-1].blue + src[i-1][j].blue + src[i-1][j-1].blue + src[i-1][j+1].blue + src[i+1][j].blue + src[i+1][j-1].blue + src[i+1][j+1].blue)/9;

            dst[i][j+1].red = (src[i][j+1].red + src[i][j+2].red + src[i][j].red + src[i-1][j+1].red + src[i-1][j].red + src[i-1][j+2].red + src[i+1][j+1].red + src[i+1][j].red + src[i+1][j+2].red)/9;
            dst[i][j+1].green = (src[i][j+1].green + src[i][j+2].green + src[i][j].green + src[i-1][j+1].green + src[i-1][j].green + src[i-1][j+2].green + src[i+1][j+1].green + src[i+1][j].green + src[i+1][j+2].green)/9;
            dst[i][j+1].blue = (src[i][j+1].blue + src[i][j+2].blue + src[i][j].blue + src[i-1][j+1].blue + src[i-1][j].blue + src[i-1][j+2].blue + src[i+1][j+1].blue + src[i+1][j].blue + src[i+1][j+2].blue)/9;



        }
    }
}

Compilation message:
Code:
gcc -Wall -O2   -c -o kernels.o kernels.c
kernels.c:486: error: array type has incomplete element type
kernels.c:486: error: array type has incomplete element type
kernels.c:486: warning: âstruct pixelâ declared inside parameter list
kernels.c:486: warning: its scope is only this definition or declaration, which is probably not what you want
 
  • #21
Lets' take care of the errors/warnings first. I believe the problem is coming because of struct appearing in the function header on line 486. If so, leave off the "struct" in this header, and while you're at it, leave off the dim inside the brackets for the array. The compiler is most likely ignoring the dim value inside the brackets, but doesn't like "struct pixel" in the 2nd and 3rd parameters.

I seem to remember that this is/was a difference between C and C++.
486: void smooth(int dim, pixel src[][], pixel dst[][])
 
  • #22
Mark44 said:
Lets' take care of the errors/warnings first. I believe the problem is coming because of struct appearing in the function header on line 486. If so, leave off the "struct" in this header, and while you're at it, leave off the dim inside the brackets for the array. The compiler is most likely ignoring the dim value inside the brackets, but doesn't like "struct pixel" in the 2nd and 3rd parameters.

I seem to remember that this is/was a difference between C and C++.
486: void smooth(int dim, pixel src[][], pixel dst[][])

When I do that I still get
Code:
error: array type has incomplete element type
I tried putting dim in the array while leaving off the 'struct' part and still get the error.

EDIT- I got an email from my prof saying I can't change the structure of smooth so the variables have to be as follows:
Code:
void smooth(int dim, pixel *src, pixel *dst)

So how can I create a pointer that points to either the first or second element in an array so I can increment it accordingly or can I not do that? I'd like to adhere to the code I have but I have a feeling that it might not be possible with pointers...
 
Last edited:
  • #23
So I gather that the RIDX macro works on a one-dimension array of pixel struct and is able to figure out the the position in the array of the pixel at a certain row and column in an image. I'm guessing that RIDX stands for row index.

The declarations pixel * src and pixel *dst mean that you can access what src and dst point to using array notation (src or dst for example) or with pointer notation (*(src + i) or *(dst + i)).

The latter forms use pointer arithmetic, which is different from ordinary arithmetic in that the result is scaled by the type of object pointed to. For example, in pointer addition, an expression that on the surface might look like 1000 + 1 might turn out to be 1001 (what you'd expect) or 1002 or 1004 or 1008 or even some other value. For different types of pointers, you get different results.

In the case of your pixel struct, which I assume is the same as what you earlier called pixel_sum, let's say that each struct instance takes up 16 bytes in memory. If you have an array of such structs in memory, and srce is declared as a pointer to pixel (i.e., pixel * src;) and initialized to point to the location in memory of the first element of the array, then you can access the array this way -- src[0] -- or this way -- *(src + 0). Note that you don't need the 0 in the second form. I put it there only to point out a similarity with the array form

If you want to access the second pixel struct in the array - this is your question -- you can do it this way -- src[1] -- or this way -- *(src + 1). Similarly, src or *(src + i) gives you access to the pixel struct at index i.

Here's where the business of pointer arithmetic comes in. Let's assume that the pixel array starts at location 1000 in memory. Assuming that each of these structs takes up 16 bytes, the next pixel struct would be at location 1016 in memory. In this case the expression src + 1 would evaluate to memory address 1000 + 16. What looks like 1 being added turns out to be 16 added.

The code that the compiler generates takes the scaling into effect so you don't have to. The actual arithmetic to calculate the address is 1000 + 1*sizeof(pixel). That's what I was talking about when I said that pointer arithmetic is "scaled by the type of object pointed to."

So src + 1 evaluates to the address of the 2nd pixel struct in memory, and *(src + 1) gives you access to that memory by dereferencing the pointer.

Hope that's clear.
 
  • #24
Mark44 said:
So I gather that the RIDX macro works on a one-dimension array of pixel struct and is able to figure out the the position in the array of the pixel at a certain row and column in an image. I'm guessing that RIDX stands for row index.
Here is a typical implementation:
Code:
#define RIDX(i,j,N) ((i)*(N)+(j))

Note well: Each use involves a multiplication. Do something smarter (i.e., pointer arithmetic) and the multiplications can go away.
 
  • #25
Mark44 said:
So I gather that the RIDX macro works on a one-dimension array of pixel struct and is able to figure out the the position in the array of the pixel at a certain row and column in an image. I'm guessing that RIDX stands for row index.

The declarations pixel * src and pixel *dst mean that you can access what src and dst point to using array notation (src or dst for example) or with pointer notation (*(src + i) or *(dst + i)).

The latter forms use pointer arithmetic, which is different from ordinary arithmetic in that the result is scaled by the type of object pointed to. For example, in pointer addition, an expression that on the surface might look like 1000 + 1 might turn out to be 1001 (what you'd expect) or 1002 or 1004 or 1008 or even some other value. For different types of pointers, you get different results.

In the case of your pixel struct, which I assume is the same as what you earlier called pixel_sum, let's say that each struct instance takes up 16 bytes in memory. If you have an array of such structs in memory, and srce is declared as a pointer to pixel (i.e., pixel * src;) and initialized to point to the location in memory of the first element of the array, then you can access the array this way -- src[0] -- or this way -- *(src + 0). Note that you don't need the 0 in the second form. I put it there only to point out a similarity with the array form

If you want to access the second pixel struct in the array - this is your question -- you can do it this way -- src[1] -- or this way -- *(src + 1). Similarly, src or *(src + i) gives you access to the pixel struct at index i.

Here's where the business of pointer arithmetic comes in. Let's assume that the pixel array starts at location 1000 in memory. Assuming that each of these structs takes up 16 bytes, the next pixel struct would be at location 1016 in memory. In this case the expression src + 1 would evaluate to memory address 1000 + 16. What looks like 1 being added turns out to be 16 added.

The code that the compiler generates takes the scaling into effect so you don't have to. The actual arithmetic to calculate the address is 1000 + 1*sizeof(pixel). That's what I was talking about when I said that pointer arithmetic is "scaled by the type of object pointed to."

So src + 1 evaluates to the address of the 2nd pixel struct in memory, and *(src + 1) gives you access to that memory by dereferencing the pointer.

Hope that's clear.


Thank you mark, that is very clear! Now if I wanted to define a pointer to, say, the first column of src (assuming the first dimension is a row and the second is a column) would I say something like pixel *pointer = src[][0];? Or would I even have to do that? Could I just use src[][0]? Or, better example, src[3][0] to do something to the 4th row and 1st column?

D H said:
Here is a typical implementation:
Code:
#define RIDX(i,j,N) ((i)*(N)+(j))

Note well: Each use involves a multiplication. Do something smarter (i.e., pointer arithmetic) and the multiplications can go away.
Whoa, where did you get that definition of RIDX? I'll have to sneak around the other files because knowing that is very, very useful! Thanks!
 
  • #26
Fronzbot said:
Whoa, where did you get that definition of RIDX? I'll have to sneak around the other files because knowing that is very, very useful! Thanks!
Three reasons. First off, it is clear from the required calling sequence void smooth(int dim, pixel *src, pixel *dst) that the images are stored as one dimensional arrays rather than 2D arrays. Secondly, I have done some image processing in the past; I know that is typically how image arrays are stored.

Thirdly, I searched the 'net for your assignment. This apparently is a fairly common one. Many schools not only use exactly the same assignment, they also use exactly the same machinery to automatically score student submissions. I wouldn't be surprised if the definition of that macro is right there on your homework handout sheet. It is on the handout sheet for many of the schools that use this pair of assignments (rotating and smoothing).I strongly suggested on your previous assignment that you look into that macro. While you can't modify the definition of that macro (and you don't want to modify it, anyhow), there is nothing saying you have to use it, is there?To achieve the kinds of performance boosts you are required to achieve you will need to do lots of different things. Some key things you need to do:
  • Avoid function calls, particular inside nested loops. Function calls are very expensive. One way to do that is to inline your functions, either manually or via the magic word inline.
  • Keep memory access compact, particularly inside nested loops. You need to make very efficient use of the cache. With today's high speed CPUs, every operation that requires a true memory fetch/write, as opposed to a fetch from/write to cache, costs dearly. Accomplishing this might (will!) require you to rearrange the computations, sometimes drastically.
  • Avoid multiplication, once again particularly so inside nested loops.
  • Learn about pointer arithmetic. You probably are not going to get a good score if you use the RIDX macro.
  • Get rid of redundant calculations.
 
Last edited:

1. How does smoothing an image improve its quality?

Smoothing an image helps to reduce noise and make it appear more visually appealing. It can also help to make edges and details appear more defined and clear.

2. What factors should be considered when optimizing C code for image smoothing?

Some important factors to consider when optimizing C code for image smoothing include the algorithm used for smoothing, the data structures used to store the image, and the efficiency of the code implementation.

3. What techniques can be used to optimize C code for image smoothing?

Some common techniques for optimizing C code for image smoothing include loop unrolling, vectorization, and parallelization. These techniques can help to improve the speed and efficiency of the code.

4. How can I measure the performance of my optimized C code for image smoothing?

There are various tools and techniques that can be used to measure the performance of optimized C code for image smoothing, such as benchmarking, profiling, and using performance analysis tools.

5. Are there any potential drawbacks to optimizing C code for image smoothing?

While optimizing C code for image smoothing can greatly improve its performance, it can also be a time-consuming and complex process. Additionally, some optimization techniques may lead to loss of accuracy in the image smoothing process.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
10
Views
11K
Back
Top