Velocity Reviews > Row-wise vs. column-wise image processing

# Row-wise vs. column-wise image processing

Enrique Cruiz
Guest
Posts: n/a

 01-25-2007
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=firstCol+1 ; col<=lastCol-1 ; ++col)
{
*pixel = (*pixel) * 2 / 3;
pixel++;
}

// VERTICAL
// loop for every column
....
// then for every row
for(row=firstRow+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+=imgWidth;"), 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

santosh
Guest
Posts: n/a

 01-25-2007
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=firstCol+1 ; col<=lastCol-1 ; ++col)
> {
> *pixel = (*pixel) * 2 / 3;
> pixel++;
> }
>
> // VERTICAL
> // loop for every column
> ...
> // then for every row
> for(row=firstRow+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+=imgWidth;"), 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.

mark_bluemel@pobox.com
Guest
Posts: n/a

 01-25-2007
On 25 Jan, 11:00, Enrique Cruiz <(E-Mail Removed)> 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?!

[Snip]

This is not really a question about the C language. A general forum
such as comp.programming 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>

Steffen Buehler
Guest
Posts: n/a

 01-25-2007
Enrique Cruiz wrote:

> Now if we simply remove in each case the line updating the pixel
> pointer (i.e. "pixel++;" and "pixel+=imgWidth;"), 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+=imgWidth" 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

santosh
Guest
Posts: n/a

 01-25-2007
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+=imgWidth;"), 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+=imgWidth" 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>

Enrique Cruiz
Guest
Posts: n/a

 01-25-2007
On 2007-01-25 11:55:10 +0000, "santosh" <(E-Mail Removed)> said:
>
> <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

Dik T. Winter
Guest
Posts: n/a

 01-25-2007
In article <(E-Mail Removed). com> http://www.velocityreviews.com/forums/(E-Mail Removed) writes:
> On 25 Jan, 11:00, Enrique Cruiz <(E-Mail Removed)> 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?!

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

CBFalconer
Guest
Posts: n/a

 01-25-2007
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=firstCol+1 ; col<=lastCol-1 ; ++col)
> {
> *pixel = (*pixel) * 2 / 3;
> pixel++;
> }
>
> // VERTICAL
> // loop for every column
> ...
> // then for every row
> for(row=firstRow+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+=imgWidth;"), 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

santosh
Guest
Posts: n/a

 01-25-2007
Enrique Cruiz wrote:
> On 2007-01-25 11:55:10 +0000, "santosh" <(E-Mail Removed)> said:
> >
> > <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.

William Hughes
Guest
Posts: n/a

 01-25-2007

On Jan 25, 6:00 am, Enrique Cruiz <(E-Mail Removed)> 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=firstCol+1 ; col<=lastCol-1 ; ++col)
> {
> *pixel = (*pixel) * 2 / 3;
> pixel++;
>
> }// VERTICAL
> // loop for every column
> ...
> // then for every row
> for(row=firstRow+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+=imgWidth;"), 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

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post mike VHDL 10 02-06-2009 11:58 PM =?ISO-8859-1?Q?Rapha=EBl_MARC?= Python 1 10-04-2005 10:58 AM Mike Henley Digital Photography 42 01-30-2005 08:26 AM Laszlo Zsolt Nagy Python 1 01-26-2005 09:55 PM Hubert Hung-Hsien Chang Python 2 09-17-2004 03:10 PM