# Help me understand how to index a pixel in an image

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++;
}
}
}
``````
• 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

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

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`