1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Optimization of C code: smoothing an image.

  1. May 10, 2010 #1
    1. The problem statement, all variables and given/known data
    I need to optimize this given code:
    Code (Text):
    /* 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);
    }

    2. Relevant equations



    3. 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 (Text):
    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 (Text):
    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!
     
  2. jcsd
  3. May 10, 2010 #2

    Mark44

    Staff: Mentor

    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 *?
     
  4. May 10, 2010 #3
    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!)
     
  5. May 10, 2010 #4

    Mark44

    Staff: Mentor

    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.
     
  6. May 10, 2010 #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 (Text):

    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. May 10, 2010 #6

    Mark44

    Staff: Mentor

    What's the error?
     
  8. May 10, 2010 #7
    Code (Text):

    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".
     
  9. May 10, 2010 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    That error is reporting on the last row. You have an edge effect error.
     
  10. May 10, 2010 #9
    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?
     
  11. May 10, 2010 #10

    Mark44

    Staff: Mentor

    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 (Text):
    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.
     
  12. May 10, 2010 #11

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    This looks might problematic:
    Code (Text):
                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?
     
  13. May 10, 2010 #12
    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?
     
  14. May 10, 2010 #13

    Mark44

    Staff: Mentor

    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.
     
  15. May 10, 2010 #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 (Text):

    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?
     
  16. May 10, 2010 #15

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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>
     
  17. May 10, 2010 #16

    Mark44

    Staff: Mentor

    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.
     
  18. May 10, 2010 #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.
     
  19. May 10, 2010 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    You certainly can take advantage of the items I talked about before my rant in your code.
     
  20. May 10, 2010 #19

    Mark44

    Staff: Mentor

    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.
     
  21. May 12, 2010 #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 (Text):
    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 (Text):

    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
     
  22. May 12, 2010 #21

    Mark44

    Staff: Mentor

    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[][])
     
  23. May 12, 2010 #22
    When I do that I still get
    Code (Text):
    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 (Text):

    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: May 12, 2010
  24. May 13, 2010 #23

    Mark44

    Staff: Mentor

    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.
     
  25. May 13, 2010 #24

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Here is a typical implementation:
    Code (Text):
    #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.
     
  26. May 13, 2010 #25


    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?

    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!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook