How to speed up algorithm (Binarization, integral image)

Question

I wrote this procedure based on integral image algorithm described at this url

http://people.scs.carleton.ca/~roth/iit-publications-iti/docs/gerh-50002.pdf

Is there any way to do this code faster?

Pointers are much faster as dynamic arrays?

procedure TForm1.bBinarizationClick(Sender: TObject);
var
  iX1, iY1,
  iX2, iY2,
  ii, jj,
  s, s2,
  iSum, iCount,  index,
  iHeight, iWidth : Integer;
  iSize: Integer;

  row : ^TRGBTriple;
  black : TRGBTriple;
  aIntegralIm: array  of Integer;
  aGrays : array of Byte;

  startTime : Cardinal;

begin
  iWidth := bBitmap.Width;
  iHeight := bBitmap.Height;
  iSize := iWidth * iHeight;

  SetLength(aGrays, iSize);
  SetLength(aIntegralIm, iSize);

  black.rgbtRed  := (clBlack and $0000FF);
  black.rgbtGreen := (clBlack and $00FF00) shr 8;
  black.rgbtBlue := (clBlack and $FF0000) shr 16;

  bBitmap2.Canvas.Brush.Color := clWhite;
  bBitmap2.Canvas.FillRect(Rect(0, 0, bBitmap2.Width, bBitmap2.Height));

  s := Round(iWidth / TrackBar2.Position);
    s2 := Round(s / 2);

  startTime := GetTickCount();

  index := 0;

  for ii := 0 to iHeight - 1 do begin
     row := bBitmap.ScanLine[ii];
     for jj := 0 to iWidth - 1 do begin
       aGrays[index] := ((row.rgbtRed * 77 + row.rgbtGreen * 150 + row.rgbtBlue * 29) shr 8);
       inc(index);
       inc(row);
     end;
  end;


  for ii := 0 to iWidth - 1 do begin
     iSum := 0;
     for jj := 0 to iHeight - 1 do begin
       index := jj*iWidth+ii;
       iSum := iSum + aGrays[index];
       if ii = 0 then aIntegralIm[index] := iSum
       else aIntegralIm[index] := aIntegralIm[index - 1] + iSum;
     end;
  end;


  for jj := 0 to iHeight - 1 do begin
     row := bBitmap2.ScanLine[jj];
     for ii := 0 to iWidth - 1 do begin

       index := jj*iWidth+ii;

       iX1 := ii-s2;
       iX2 := ii+s2;
       iY1 := jj-s2;
       iY2 := jj+s2;

       if (iX1 < 0) then iX1 := 0;
         if (iX2 >= iWidth) then  iX2 := iWidth-1;
           if (iY1 < 0) then  iY1 := 0;
             if (iY2 >= iHeight) then  iY2 := iHeight-1;

       iCount := (iX2 - iX1) * (iY2 - iY1);

       iSum := aIntegralIm[iY2*iWidth+iX2]
              - aIntegralIm[iY1*iWidth+iX2]
              - aIntegralIm[iY2*iWidth+iX1]
              + aIntegralIm[iY1*iWidth+iX1];

       if (aGrays[index] * iCount) < (iSum * (100 - TrackBar1.Position) / 100) then  row^ :=  black;

       inc(row);

     end;
  end;

  ePath.Text :=  'Time: ' + inttostr(GetTickCount() - startTime) + ' ms';

  imgOryginal.Picture.Bitmap.Assign(bBitmap2);

end;

You will need to explain what this algorithm does in order for people to help you. — Daniel A. White, Feb 17 '10 at 12:39

score 2 · Answer 1 · answered Feb 17 '10 at 13:05

2

You can at least do a few simple things:

precalculate (100 - TrackBar1.Position) into a variable
Instead of division: / 100 use * 100 on the other side. You might not need any floating point values.
Use lookup tables for the following (care to explain the identation btw?):

Code:

if (iX1 < 0) then iX1 := 0;
if (iX2 >= iWidth) then  iX2 := iWidth-1;
if (iY1 < 0) then  iY1 := 0;
if (iY2 >= iHeight) then  iY2 := iHeight-1;

Try to keep the index and icremnet, decrement istead of multiplication: index := jj*iWidth+ii;

answered Feb 17 '10 at 13:05

Ritsaert Hornstra

5,013
1
33
51

thanks for reply its helped. but what do You think that i should used pointers rather than dynamic arrays, and do some pointers incrementation? – Kowalikus Feb 17 '10 at 13:31
Pointers are definitely faster so you can use those. If you disable range checking it already shaves off some CPU cycles to the index based access but it still will be slower. – Ritsaert Hornstra Feb 17 '10 at 13:39

score 2 · Answer 2 · edited May 23 '17 at 12:06

My guess is that the second loop is the slow bit.

The trick would be to avoid to recalculate everything in the second loop all the time

If S is constant (relative to the loop I mean, not absolute)

iy1,iy2 only change with the main(jj) loop and so do iy1*width (and iy2*width). Precalculate them, or optimize them away in the same way you do with row. (precalculate once per line, increment inbetween)
change the ii loop into three loops:
- the first bit where ix1=0
- the second where ix1=ii-s ix2=ii+s;
- the third where ix1=ii-s and ix2=iwidth-1

this removes a lot of checks out of the loops, to be done only once.

make a dedicated loop for the condition if (aGrays[index] * iCount) < (iSum * (100 - TrackBar1.Position) / 100) then row^ := black; so that it isn't evaluated for each pixel, since you can precalculate the area's where this happens ?
introduce pointers into the gray calculating loop so that you don't have to recalculate the index each pixel (but e.g. only for the row loop, incrementing a ptr per pixel)

If you are hardy, you can also precalculate the jump between lines. Keep in mind that abs(scanline[j]-scanline[i])-width is a metric for the number of alignment bytes per row.

Even more advanced is optimizing for cache effects on the level of your algorithm. See rotating bitmaps. In code to get an idea how this works. Some pointer tricks are demonstrated there too (but only for 8-bit elements)

score 1 · Answer 3 · answered Feb 18 '10 at 08:23

I would first use a profiler to find out the CPU usage repartition, to figure out the smallest part(s) of code that would benefit the most from optimisation. Then I would adapt the effort according to the results. If some code represents 90% of the CPU load and is executed zillions of times, even extreme measures (recoding a few sequences using inline assembly language) might make sense.

score 0 · Answer 4 · answered Feb 18 '10 at 10:16

Use the excellent and free SamplingProfiler to find out the bottleneck in your code. Then optimize and run the profiler again to find the next bottleneck. This approach is much better than guessing what's need to be optimized because even experts are often wrong about that.

How to speed up algorithm (Binarization, integral image)

4 Answers4