[Insight-users] Order of complexity

[Luis Ibanez]

Hi Jayant,

The order of complexity for the GeodesicActiveContour
level set should be evaluated over the entire ser of
operations it performs. Here is a tentative estimation
that will help you to get started:


N  = number of Pixels in the input image

D  = image dimension (eg. 2D, 3D).

NI = Number of iterations

---

Preparation:

1) Time to compute Speed image =  O(N)

2) Time to compute Advection image =
    Compute a gradient magnitude followed
    by a gradient = 2 * O(N^D) * D

3) Time to compute the rescale intensity
    filter = O(N)

4) Time to compute the zero
     crossing = O(N) * D


Iterative execution (to be multiplied by
the number of iterations NI that you run
the filter)

1) Time to iterate over all the pixels
    performing a curvature computation = D * O(N)

2) Time to update the pixel value in the level
    set = O(N)

3) Time to promote layers of the narrow band
    in or out = D * O(N)




The actual computation of the iterative
part of the filter are performed by the parent
class, the SparseFieldLevelSetImageFilter.


Note that the level set filters do not actually
execute over all the pixels in the image but
only those in the NarrowBand. Therefore N is
actually to be taken as the number of pixels
in the Narrow band. This number depend on the
width you select for the band, and on the
complexity of the contour of the object you
are segmenting.




Regards,


    Luis



----------------------
Jayant Chauhan wrote:

> Hey Fellas,
> I would be grateful if someone could tell me about the order of 
> complexity and maybe its computation aswell for the Geodesic Active 
> Region level Set segmentation method (ie, the updation and the updater 
> scheme) and also for the Watershed method or maybe give me a pointer or 
> something (not much is given about in Sethians book ).
>  
> with regards
> Jayant
>