Page MenuHome

Dilate node speed improvement
Closed, ResolvedPublicPATCH

Description

This patch includes a better algorithm for Dilate/Erode node in Steps mode (so that it doesn't perform the steps anymore).
Resulting image is exactly the same, but computation time does not depend on the Steps count. It performs quicker even if steps = 1.

It works by dilating all rows first and then all resulting columns. Dilation in Steps mode creates squares, so this is OK.
The 1D algorithm divides the input into blocks of width = Steps and pre-calculates maxima from the beginning and to the end of each block. From these and the maximum of the whole block, maximum of any Steps-wide block can be calculated in constant time. The total running time is linear to pixel count.

Erosion works exactly the same way, except for that it calculates the minimum.

Event Timeline

The patch was created against r49166, v. 2.63.14 -- sorry, I forgot to mention that in the original description.

Jeroen, can you check on that when you have time? :)

other algorithm has been applied. If there is a real difference this patch needs to be updated

Jeroen Bakker (jbakker) changed the task status from Unknown Status to Resolved.Jan 25 2013, 11:00 AM

The algorithm applied is practically the same, just perhaps better readable.

What I measured, the difference in speed (this vs. #33972) is not much significant (so I don't even post the updated version of this).