473,585 Members | 2,734 Online

# Row-wise vs. column-wise image processing

Hello all,

I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

The code itself is very simple. There are 2 loops to scan through rows
and colums (horizontal pass), or columns and rows (vertical pass)
depending on the pass. The processing part is simple and is contained
in a single line. 'pixel' is a pointer to the current pixel. The new
value of the current pixel is first updated, and the pointer is then
incremented to the next pixel, which is either in the next column or in
the next row depending on the pass. I should add that the image is
stored as a large 1-D vector, i.e. the values of each rows are
contiguous in memory. Here is a simplified version of the code:

############### #####
// HORIZONTAL
// loop for every row
....
// then for every column
for(col=firstCo l+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;
}

// VERTICAL
// loop for every column
....
// then for every row
for(row=firstRo w+1 ; row<=lastRow-1 ; ++row)
{
*pixel = (*pixel) * 2 / 3;
pixel+=imgWidth ;
}
############### ###

For this small amount of code, timings are as follow:
- horizontal = 0.035 sec.
- vertical =* *0.135 sec.

Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

My only guess relates to memory management issues. Since the image is
stored row-wise, the current and next values are physically next in
memory during the horizontal pass. On the other hand, for the vertical
pass, the next value is stored in the next row, and the distance
between them becomes 'image_width'. My guess is that the next pixel
value in such a case is not close enough to be stored in the processor
cache or register. The processor has to fetch it from memory, hence the
massive loss in speed. This is however just a guess.

I would really appreciate if anybody could enlighten me on this topic.

Enrique

Jan 25 '07 #1
10 5708
Enrique Cruiz wrote:
Hello all,

I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

The code itself is very simple. There are 2 loops to scan through rows
and colums (horizontal pass), or columns and rows (vertical pass)
depending on the pass. The processing part is simple and is contained
in a single line. 'pixel' is a pointer to the current pixel. The new
value of the current pixel is first updated, and the pointer is then
incremented to the next pixel, which is either in the next column or in
the next row depending on the pass. I should add that the image is
stored as a large 1-D vector, i.e. the values of each rows are
contiguous in memory. Here is a simplified version of the code:

############### #####
// HORIZONTAL
// loop for every row
...
// then for every column
for(col=firstCo l+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;
}

// VERTICAL
// loop for every column
...
// then for every row
for(row=firstRo w+1 ; row<=lastRow-1 ; ++row)
{
*pixel = (*pixel) * 2 / 3;
pixel+=imgWidth ;
}
############### ###

For this small amount of code, timings are as follow:
- horizontal = 0.035 sec.
- vertical = 0.135 sec.

Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

My only guess relates to memory management issues. Since the image is
stored row-wise, the current and next values are physically next in
memory during the horizontal pass. On the other hand, for the vertical
pass, the next value is stored in the next row, and the distance
between them becomes 'image_width'. My guess is that the next pixel
value in such a case is not close enough to be stored in the processor
cache or register. The processor has to fetch it from memory, hence the
massive loss in speed. This is however just a guess.

I would really appreciate if anybody could enlighten me on this topic.

Without a complete, minimal, compilable example, our guess is as good
as yours, which is probably a good guess. Use the time program to
observe time spent by your code and time spent in system code. That'll
give an indication if your guess is right.

In anycase, the C standard says nothing about efficiency of the code
generated. If the small delay is too much for your application, then
you'll have to profile your code to find out the area where it is
stalling and look at what to do about it.

Jan 25 '07 #2
On 25 Jan, 11:00, Enrique Cruiz <jni6l03mdo6n.. .@jetable.orgwr ote:
I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!
[Snip]

This is not really a question about the C language. A general forum
such as comp.programmin g may be more appropriate than a C language
forum.
My only guess relates to memory management issues.
<Off-topic>
You are almost certainly right, and there's probably not a lot you can
do to change it with this processing style.
In your horizontal pass you can process a cache's worth of data at a
time before pulling the next cachefull. In the worst case, your
vertical pass could have a cache miss for each pixel accessed.
</Off-topic>

Jan 25 '07 #3
Enrique Cruiz wrote:
Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.
I'm pretty sure it's because the processor for which you are compiling
has an INC-command which increments a given number quite fast. Your
"pixel++" is compiled into such an INC, whereas "pixel+=imgWidt h" can
only be translated into an ADD-command which takes much longer.

I don't think you can do much C-specific here. Maybe, if imgWidth is a
power of two, there is a chance of using some strange &s and |s, but I
wonder...

Regards
Steffen
Jan 25 '07 #4
Steffen Buehler wrote:
Enrique Cruiz wrote:
Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

I'm pretty sure it's because the processor for which you are compiling
has an INC-command which increments a given number quite fast. Your
"pixel++" is compiled into such an INC, whereas "pixel+=imgWidt h" can
only be translated into an ADD-command which takes much longer.
<snip>

<OT>
With regard to modern x86s, as far as I can tell, the ADD instruction
is faster than the INC instruction. The OP didn't specify the size of
the image being processed, and the cache sizes of the CPU, so one can't
tell if the slowdown is due to cache misses.
</OT>

Jan 25 '07 #5
On 2007-01-25 11:55:10 +0000, "santosh" <sa*********@gm ail.comsaid:
>
<OT>
With regard to modern x86s, as far as I can tell, the ADD instruction
is faster than the INC instruction. The OP didn't specify the size of
the image being processed, and the cache sizes of the CPU, so one can't
tell if the slowdown is due to cache misses.
</OT>
10 MB pixels image, 3650x2730

I have no idea how to find out about the sizes of the CPU cache?!

Enrique
Jan 25 '07 #6
In article <11************ *********@a75g2 000cwd.googlegr oups.comma**********@po box.com writes:
On 25 Jan, 11:00, Enrique Cruiz <jni6l03mdo6n.. .@jetable.orgwr ote:
I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!
....
You are almost certainly right, and there's probably not a lot you can
do to change it with this processing style.
In your horizontal pass you can process a cache's worth of data at a
time before pulling the next cachefull. In the worst case, your
vertical pass could have a cache miss for each pixel accessed.
Indeed. Cache misses can give a huge loss of cycles.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Jan 25 '07 #7
Enrique Cruiz wrote:
On 2007-01-25 11:55:10 +0000, "santosh" <sa*********@gm ail.comsaid:

<OT>
With regard to modern x86s, as far as I can tell, the ADD instruction
is faster than the INC instruction. The OP didn't specify the size of
the image being processed, and the cache sizes of the CPU, so one can't
tell if the slowdown is due to cache misses.
</OT>

10 MB pixels image, 3650x2730

I have no idea how to find out about the sizes of the CPU cache?!
Under Linux 'dmesg | grep cpu' should do the trick. Under Windows
msinfo.exe should show the sizes.

Anyway, a 10 Mb file will definitely cause hundreds of cache misses,
when you read non-sequentially. I don't there's anything much you can
do about it. Generally the delay is acceptable.

Jan 25 '07 #8
Enrique Cruiz wrote:
>
I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

The code itself is very simple. There are 2 loops to scan through rows
and colums (horizontal pass), or columns and rows (vertical pass)
depending on the pass. The processing part is simple and is contained
in a single line. 'pixel' is a pointer to the current pixel. The new
value of the current pixel is first updated, and the pointer is then
incremented to the next pixel, which is either in the next column or in
the next row depending on the pass. I should add that the image is
stored as a large 1-D vector, i.e. the values of each rows are
contiguous in memory. Here is a simplified version of the code:

############### #####
// HORIZONTAL
// loop for every row
...
// then for every column
for(col=firstCo l+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;
}

// VERTICAL
// loop for every column
...
// then for every row
for(row=firstRo w+1 ; row<=lastRow-1 ; ++row)
{
*pixel = (*pixel) * 2 / 3;
pixel+=imgWidth ;
}
############### ###

For this small amount of code, timings are as follow:
- horizontal = 0.035 sec.
- vertical = 0.135 sec.

Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

My only guess relates to memory management issues. Since the image is
stored row-wise, the current and next values are physically next in
memory during the horizontal pass. On the other hand, for the vertical
pass, the next value is stored in the next row, and the distance
between them becomes 'image_width'. My guess is that the next pixel
value in such a case is not close enough to be stored in the processor
cache or register. The processor has to fetch it from memory, hence the
massive loss in speed. This is however just a guess.
Your guess is almost certainly correct. But, for the code you
show, there is no reason to even have the second scan. The
operation could simply be *pixel *= 4.0 / 9;

Assuming the operations are really more complex, and depend on
adjacent pixels, you could maintain cache coherency by keeping
things local. No need for the two sweeps.

/* init pixel pointer */
for (row = firstRow + 1; row < lastRow; ++row) {
/* adjust pixel pointer, maybe pixel += 2 */
for (col = firstCol + 1; col < lastCol; ++col, ++pixel) {
}
}

--
<http://www.cs.auckland .ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
Jan 25 '07 #9

On Jan 25, 6:00 am, Enrique Cruiz <jni6l03mdo6n.. .@jetable.orgwr ote:
Hello all,

I am currently implementing a fairly simple algorithm. It scans a
grayscale image, and computes a pixel's new value as a function of its
original value. Two passes are made, first horizontally and second
vertically. The problem I have is that the vertical pass is 3 to 4
times slower than the horizontal, although the code is _exactly_ the
same in both cases?!

The code itself is very simple. There are 2 loops to scan through rows
and colums (horizontal pass), or columns and rows (vertical pass)
depending on the pass. The processing part is simple and is contained
in a single line. 'pixel' is a pointer to the current pixel. The new
value of the current pixel is first updated, and the pointer is then
incremented to the next pixel, which is either in the next column or in
the next row depending on the pass. I should add that the image is
stored as a large 1-D vector, i.e. the values of each rows are
contiguous in memory. Here is a simplified version of the code:

############### #####
// HORIZONTAL
// loop for every row
...
// then for every column
for(col=firstCo l+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;

}// VERTICAL
// loop for every column
...
// then for every row
for(row=firstRo w+1 ; row<=lastRow-1 ; ++row)
{
*pixel = (*pixel) * 2 / 3;
pixel+=imgWidth ;}############# #####

For this small amount of code, timings are as follow:
- horizontal = 0.035 sec.
- vertical = 0.135 sec.

Now if we simply remove in each case the line updating the pixel
pointer (i.e. "pixel++;" and "pixel+=imgWidt h;"), the timings then
becomes equal at 0.081. This simple instruction is responsible for the
massive loss of time. And I have no idea why.

My only guess relates to memory management issues. Since the image is
stored row-wise, the current and next values are physically next in
memory during the horizontal pass. On the other hand, for the vertical
pass, the next value is stored in the next row, and the distance
between them becomes 'image_width'. My guess is that the next pixel
value in such a case is not close enough to be stored in the processor
cache or register. The processor has to fetch it from memory, hence the
massive loss in speed. This is however just a guess.

I would really appreciate if anybody could enlighten me on this topic.

This is quite standard, and your guess is quite correct. The problem
is
that when you process by rows the elements are close together
and when you process by columns the elements are far apart.
This has little to do with C (if you use Fortran you will probably
find that processng by columns is faster than processing by rows).

You have several options

Live with things as they are (a drop in speed of three times
is not that severe. Suppose your matrix
was so large that a column operation caused a disc read
for every element. Can you say "several orders of magnitude")

Change to an algorithm that can be done with
only row processing (not always possible).

Do the row processing, transpose the matrix,
do the column processing, transpose the matrix
again. The two transposes may take less time
than the processing time difference.

Store the image in "tiles", so that close
by pixels in any direction are usually close
in memory. This is the most general solution
and also the hardest. Note that the
overhead of the tiling sheme will probably
make row processing slower. Hopefully, you
will more that make up for this in column processing.

Process in a different order. Process a few rows
and then do the needed column processing. Process
a pixel at a time, doing the needed row and column operations.
The change in memory access pattern may help.

-William Hughes

Jan 25 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 2 2262 by: lawrence | last post by: I had some code that worked fine for several weeks, and then yesterday it stopped working. I'm not sure what I did. Nor can I make out why it isn't working. I'm running a query that should return 3 items from the database. I then get a count of the return, which correctly tells me that I've got 3 items. I then go into a for loop which I expect... 23 2211 by: Eva | last post by: Hi i am trying to insert a new row into one of my datatabels that i have in my dataset when a button is clicked. here is my code Dim ClientInsRow As DataRow = dtClient.NewRo ClientInsRow("Surname") = txtSurname.Tex ClientInsRow("Forename") = txtForename.Tex ClientInsRow("OrgName") = txtOrganisation.Tex ClientInsRow("Address") =... 10 22194 by: AdamG | last post by: I am trying hard for days now to add and delete rows to a table. I could really use some help... Each row contains two buttons (images) - 'add row' and 'delete row'. When the user clicks add row within a specific cell/row, the index of that row should be passed to a function that creates a new row using that index (the new row should be... 7 16146 by: Micha? | last post by: Hello this is my problem: