Labeling Speed Improvement Patch

Introduction

This patch improves the speed of the alg_labeling function substantially. It also fixed a bug in said function.

Description of Patch

The patch does the following:

• Fixes a bug that made iflood get called too many times.
• Uses memset (fast) instead of a loop (slow) to zero-initialize labels.
• Rearranges the two main loops to allow pixelpos to be incremented (fast) instead of calculated (slow).

Benchmarks

This is an excerpt from the flat execution profile, without the patch:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 29.87     41.11    41.11      334   123.09   133.54  alg_labeling
...
  2.54    131.94     3.49   686242     0.01     0.01  iflood 

First in the list, i.e. most expensive, is alg_labeling. Note that iflood has been called 686242 times! That's around 2000 times per call to alg_labeling.

This is an excerpt from the profile with the patch:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
...
 10.48     57.52     8.37      243    34.45    38.60  alg_labeling
...
  1.26     78.47     1.01     2648     0.38     0.38  iflood 

Now, alg_labeling is no longer first in the list. The performance gain is around 70%! Note also that iflood has been called a lot less.

Installation of Patch

The usual procedure:

1. cd motion-3.1.18
2. zcat ../motion-3.1.18_snap7-labeling.patch.gz | patch -p1

Discussion and Comments

---

Added to my sources and being testes

Great job

-- KennethLavrsen - 29 Nov 2004

---

Shame on me:-( How could I swap X and Y without ever noticing... Thank you, Per.

-- JoergWeber - 29 Nov 2004

---

Joerg, you shouldn't feel that way! The optimizations weren't obvious, and I was kind of surprised that the performance gain turned out to be that big.

-- PerJonsson - 30 Nov 2004

---