user83807 user83807 - 3 years ago 46
C Question

Border image segmentation

I'm trying to create a code to find the border of an image inside the other, like the image below.

Image

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
------------------------------------------------
0: . . . . . . . . . . . . . . . .
1: . . . . . . . . . . . . . . . .
2: . . . . . . . . . . . . . . . .
3: . . . . x . . . . . . . . . . .
4: . . . x . x . . . . x . . . . .
5: . . x x . . . . . x x x . . . .
6: . . . x x x x x . x x x x . . .
7: . . . x x x x x . x x x x . . .
8: . . . . . x x x x x x x x . . .
9: . . . . . x x x x x x x x . . .
10: . . . . . x x x . x x x . . . .
11: . . . . x . x x x x x . . . . .
12: . . . x . . . . x x . . . . . .
13: . . . . . . . . . . . . . . . .
14: . . . . . . . . . . . . . . . .
15: . . . . . . . . . . . . . . . .


I have to mark every x that is border of this image.
I'm trying to do that based on the neighbors, but I don't know what kind of logic should I take.
Every help is welcome. Thank you.

Answer Source

First, you will need to write a function that processes the image. Presumably, the image is represented by a 2d character array, so the function will need to iterate over this array. A second function may be used to determine whether each 'x' of the image is on an edge or not. The results can be stored in an output array.

Now, to write the second function, which might be called is_edge(), you need to decide what it means for an 'x' to lie on the edge of the image. A first try might have a foreground pixel on the edge of the image if it is adjacent to a background pixel (an '.'). This sounds good, but the resulting image may be a bit "heavy":

Image edges (is_edge1):
    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
   -------------------------------------------------
 0: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 1: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 2: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 3: .  .  .  .  x  .  .  .  .  .  .  .  .  .  .  .  
 4: .  .  .  x  .  x  .  .  .  .  x  .  .  .  .  .  
 5: .  .  x  x  .  .  .  .  .  x  x  x  .  .  .  .  
 6: .  .  .  x  x  x  x  x  .  x  .  x  x  .  .  .  
 7: .  .  .  x  x  x  .  x  .  x  .  .  x  .  .  .  
 8: .  .  .  .  .  x  .  x  x  x  .  .  x  .  .  .  
 9: .  .  .  .  .  x  .  x  x  x  .  x  x  .  .  .  
10: .  .  .  .  .  x  x  x  .  x  x  x  .  .  .  .  
11: .  .  .  .  x  .  x  x  x  x  x  .  .  .  .  .  
12: .  .  .  x  .  .  .  .  x  x  .  .  .  .  .  .  
13: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
14: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
15: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  

Here there are some pixels, e.g., at [5][10], that might have been removed. If this seems not quite right, then you can rethink the is_edge() function. What if instead, a foreground pixel is on an edge if it is adjacent to a background pixel that is not at one of its corners? This should remove extra pixels of the type just seen:

Image edges (is_edge2):
    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
   -------------------------------------------------
 0: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 1: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 2: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 3: .  .  .  .  x  .  .  .  .  .  .  .  .  .  .  .  
 4: .  .  .  x  .  x  .  .  .  .  x  .  .  .  .  .  
 5: .  .  x  x  .  .  .  .  .  x  .  x  .  .  .  .  
 6: .  .  .  x  x  x  x  x  .  x  .  .  x  .  .  .  
 7: .  .  .  x  x  .  .  x  .  x  .  .  x  .  .  .  
 8: .  .  .  .  .  x  .  .  x  .  .  .  x  .  .  .  
 9: .  .  .  .  .  x  .  .  x  .  .  .  x  .  .  .  
10: .  .  .  .  .  x  .  x  .  x  .  x  .  .  .  .  
11: .  .  .  .  x  .  x  x  x  .  x  .  .  .  .  .  
12: .  .  .  x  .  .  .  .  x  x  .  .  .  .  .  .  
13: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
14: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
15: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  

This method seems better in some respects, but it also seems to remove too many interior pixels. Note that the pixel at [11][9] has now been removed; from the original image, it seems like this should not be removed. A modification would be to consider that a foreground pixel is on an edge if it is adjacent to a background pixel that is not at one of its corners, or if it is adjacent to two background pixels at opposite diagonal corners. This would preserve "bridge" pixels such as the one at [11][9]:

Image edges (is_edge3):
    0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 
   -------------------------------------------------
 0: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 1: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 2: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
 3: .  .  .  .  x  .  .  .  .  .  .  .  .  .  .  .  
 4: .  .  .  x  .  x  .  .  .  .  x  .  .  .  .  .  
 5: .  .  x  x  .  .  .  .  .  x  .  x  .  .  .  .  
 6: .  .  .  x  x  x  x  x  .  x  .  .  x  .  .  .  
 7: .  .  .  x  x  .  .  x  .  x  .  .  x  .  .  .  
 8: .  .  .  .  .  x  .  .  x  .  .  .  x  .  .  .  
 9: .  .  .  .  .  x  .  .  x  .  .  .  x  .  .  .  
10: .  .  .  .  .  x  .  x  .  x  .  x  .  .  .  .  
11: .  .  .  .  x  .  x  x  x  x  x  .  .  .  .  .  
12: .  .  .  x  .  .  .  .  x  x  .  .  .  .  .  .  
13: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
14: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  
15: .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  

This may be the best of the above alternatives. But consider this test case:

.  .  .  .  .
.  .  x  .  .
.  x  x  x  .
.  .  x  .  .
.  .  .  .  .

Of the three methods suggested above, only the second will remove the x from the center of the image. Perhaps one method works better in some cases, and another in other cases. Or perhaps a better method is needed.

Here is the complete program that was used to generate the above outputs. The find_edges() function takes a function pointer as an argument, so that different is_edge() functions may be easily implemented, tried, and compared. I am sure that you can find ways to improve upon this code.

#include <stdio.h>

#define IMAGE_SZ  16

void show_image(char img[][IMAGE_SZ], size_t img_sz);
void find_edges(char in[][IMAGE_SZ],
                char out[][IMAGE_SZ],
                size_t img_sz,
                int (*is_edge)(size_t, size_t, char [][IMAGE_SZ], size_t));
int is_edge1(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz);
int is_edge2(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz);
int is_edge3(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz);

int main(void)
{
    char image_in[IMAGE_SZ][IMAGE_SZ] = { "................",
                                          "................",
                                          "................",
                                          "....x...........",
                                          "...x.x....x.....",
                                          "..xx.....xxx....",
                                          "...xxxxx.xxxx...",
                                          "...xxxxx.xxxx...",
                                          ".....xxxxxxxx...",
                                          ".....xxxxxxxx...",
                                          ".....xxx.xxx....",
                                          "....x.xxxxx.....",
                                          "...x....xx......",
                                          "................",
                                          "................",
                                          "................" };

    char edge_out[IMAGE_SZ][IMAGE_SZ];

    puts("Input image:");
    show_image(image_in, IMAGE_SZ);

    puts("Image edges (is_edge1):");
    find_edges(image_in, edge_out, IMAGE_SZ, is_edge1);
    show_image(edge_out, IMAGE_SZ);

    puts("Image edges (is_edge2):");
    find_edges(image_in, edge_out, IMAGE_SZ, is_edge2);
    show_image(edge_out, IMAGE_SZ);

    puts("Image edges (is_edge3):");
    find_edges(image_in, edge_out, IMAGE_SZ, is_edge3);
    show_image(edge_out, IMAGE_SZ);

    return 0;
}

void show_image(char img[][IMAGE_SZ], size_t img_sz)
{
    /* print top numbers */
    printf("%4c", ' ');
    for (size_t j = 0; j < img_sz; j++) {
        printf("%-3zu", j);
    }
    putchar('\n');

    /* print dashes */
    printf("%4c", '-');
    for (size_t j = 0; j < img_sz; j++) {
        printf("%3s", "---");
    }
    putchar('\n');

    /* print rows */
    for (size_t i = 0; i < img_sz; i++) {
        printf("%2zu: ", i);
        for (size_t j = 0; j < img_sz; j++) {
            printf("%-3c", img[i][j]);
        }
        putchar('\n');
    }
    putchar('\n');
}

void find_edges(char in[][IMAGE_SZ],
                char out[][IMAGE_SZ],
                size_t img_sz,
                int (*is_edge)(size_t, size_t, char [][IMAGE_SZ], size_t))
{
    for (size_t i = 0; i < img_sz; i++) {
        for (size_t j = 0; j < img_sz; j++) {
            out[i][j] = is_edge(i, j, in, img_sz) ? 'x' : '.';
            }
        }
}

/* A pixel is an edge if it is adjacent to a background pixel */
int is_edge1(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz)
{
    int edge_found = 0;
    if (in[y][x] == 'x') {
        size_t y_start = (y == 0 ? 0 : y-1);
        size_t y_stop = (y == (img_sz-1) ? img_sz-1: y+1);
        size_t x_start = (x == 0 ? 0 : x-1);
        size_t x_stop = (x == (img_sz-1) ? img_sz-1 : x+1);


        for (size_t i = y_start; i <= y_stop; i++) {
            for (size_t j = x_start; j <= x_stop; j++) {
                if (in[i][j] == '.') {
                    edge_found = 1;
                    break;
                }
            }
            if (edge_found) {
                break;
            }
        }
    }

    return edge_found;
}

/* a pixel is an edge if it is adjacent to a background pixel that is
 * not a corner pixel
 */
int is_edge2(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz)
{
    int edge_found = 0;
    if (in[y][x] == 'x') {
        size_t y_start = (y == 0 ? 0 : y-1);
        size_t y_stop = (y == (img_sz-1) ? img_sz-1: y+1);
        size_t x_start = (x == 0 ? 0 : x-1);
        size_t x_stop = (x == (img_sz-1) ? img_sz-1 : x+1);

        edge_found = (in[y_start][x] == '.' ||
                      in[y][x_start] == '.' ||
                      in[y][x_stop] == '.'  ||
                      in[y_stop][x] == '.');
    }

    return edge_found;
}

/* a pixel is an edge if it is adjacent to a background pixel that is
 * not a corner pixel or if it is adjacent to two opposite diagonal
 * corner pixels.
 */
int is_edge3(size_t y, size_t x, char in[][IMAGE_SZ], size_t img_sz)
{
    int edge_found = 0;
    if (in[y][x] == 'x') {
        size_t y_start = (y == 0 ? 0 : y-1);
        size_t y_stop = (y == (img_sz-1) ? img_sz-1: y+1);
        size_t x_start = (x == 0 ? 0 : x-1);
        size_t x_stop = (x == (img_sz-1) ? img_sz-1 : x+1);

        edge_found = (in[y_start][x] == '.' ||
                      in[y][x_start] == '.' ||
                      in[y][x_stop] == '.'  ||
                      in[y_stop][x] == '.');
        if (edge_found == 0) {
            edge_found = ((in[y_start][x_start] == '.' &&
                           in[y_stop][x_stop] == '.') ||
                          (in[y_start][x_stop] == '.' &&
                           in[y_stop][x_start] == '.'));
        }
    }

    return edge_found;
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download