Motion - Labeling Speed Patch

Labeling Speed Improvement Patch


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


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 smile

-- 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
Topic revision: r7 - 30 Jan 2005, KennethLavrsen
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Please do not email Kenneth for support questions (read why). Use the Support Requests page or join the Mailing List.
This website only use harmless session cookies. See Cookie Policy for details. By using this website you accept the use of these cookies.