Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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++;
         }
     }
}
share|improve this question
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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Many thanks for your reply . –  user2350469 May 27 '13 at 17:38

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

share|improve this answer
    
Thank you very much for your answer . –  user2350469 May 27 '13 at 17:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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