0

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++;
         }
     }
}
3
  • 1
    what is your question? what specifically you don't understand? – gnat May 25 '13 at 11:55
  • @gnat the number y * width + x – user2350469 May 25 '13 at 12:02
  • The number y*width+x is the number of the case in the grid – user2350469 May 25 '13 at 13:38
3

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).

0
1

When you read an image file, it's a linear series of pixels. Let's take an example. Say you have a 32x32 image. This results in a series of 1024 points. In order to get the linear index of the pixel at y=4 and x=16, you'll use the formula y * witdth + x, which in this case is 4 * 32 + 16 = 144

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.