Image Manipulation – How to Index a Pixel in an Image

image manipulation

I had a look at the code for the implementation of this paper Graph-Based segmentation by Pedro F. Felzenszwalb

But I didn't understand how in the below code that y * width + x is used to build a graph from an image.

// build graph
edge *edges = new edge[width*height*4];
int num = 0;
for (y = 0; y < height; y++) {
    for ( x = 0; x < width; x++) {
        if (x < width-1) {
             edges[num].a = y * width + x;
             edges[num].b = y * width + (x+1);
             edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y);
             num++;
         }

         if (y < height-1) {
            edges[num].a = y * width + x;
            edges[num].b = (y+1) * width + x;
            edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x, y+1);
            num++;
         }

         if ((x < width-1) && (y < height-1)) {
            edges[num].a = y * width + x;
            edges[num].b = (y+1) * width + (x+1);
            edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y+1);
            num++;
         }

         if ((x < width-1) && (y > 0)) {
            edges[num].a = y * width + x;
            edges[num].b = (y-1) * width + (x+1);
            edges[num].w = diff(smooth_r, smooth_g, smooth_b, x, y, x+1, y-1);
            num++;
         }
     }
}

Best Answer

A 2D matrix can be stored in a 1D vector as a sequence of consecutive fixed-width rows, and the formula for accessing position (x, y) is y*width + x.

Here's a visual example. Suppose you have a 3x3 matrix filled with 0 and a $ at position (1, 2) (that's column first, row second, using 0-based indices). You can store it as a 1D vector as follows:

[0 0 0 0 0 0 0 $ 0]

And here it is visually re-arranged to make sense as a 3x3 matrix:

          y
 [0 0 0   0
  0 0 0   1
  0 $ 0]  2

x 0 1 2

Because it is a 1D vector (see first figure), we need a single index to get at that $ value. But because we think of it as a 2D matrix, all we have is the (1, 2) location. We need a formula to convert it to a single index.

That formula is the y*width + x, like you saw. It roughly means "y is how many full rows I have to skip, before moving to the correct column using x". Note the formula as written works because we are using 0-based indices, otherwise it requires minor modification.

So in this example, y = 2, x = 1 and width = 3:

2 * 3 + 1 = 7

And index 7 of our original vector [0 0 0 0 0 0 0 $ 0] has the value $ that we wanted. (Again, note 7 is a zero-based index).

Related Topic