[Insight-users] diameter of segmented object

[Benjamin King]

Hi James,

thanks a lot for your suggestion. It's very convenient that I can use the 
itk::ImageMomentsCalculator to do this.
Meanwhile I found some literature on this and also some code that quickly 
computes an approximization of a bounding sphere of a point set, so in case 
you're interested:

Fast and Robust Smallest Enclosing Balls (1999) Bernd Gärtner
(http://citeseer . nj . nec . com/106727 . html)

Smallest Enclosing Ellipses Fast and Exact (1997) Bernd Gärtner, Sven 
Schönherr
(http://citeseer . nj . nec . com/59939 . html)

Smallest enclosing disks (balls and ellipsoids) (1991) Emo Welzl
(http://citeseer . nj . nec . com/correct/235065)

And in Graphic Gems:
Ritter, Jack, An Efficient Bounding Sphere, p. 301-303, code: p. 723-725, 
BoundSphere.c
(http://www1 . acm . org/pubs/tog/GraphicsGems/gems . html)


cheers,
  Benjamin

On Tue, 18 Nov 2003 09:00:01 -0500, Miller, James V (Research) 
<millerjv at crd . ge . com> wrote:

> There may be some tricks in the Machine Vision literature for this. But I
> would probably just brute force it by computing the eigenvalues and
> eigenvectors of the scatter matrix of the indices in your binary object.
>
> Let I be an index that is set "on". We'll assume I is a column vector.
>
> Let M be the sample mean of the indices set "on"
>
> M = Sum_i I_i / N
>
> Let C be the covariance matrix of the indices set "on"
>
> C = Sum_i (I_i - M)*(I_i - M)' / (N-1)
> 2
> (C and M can be computed in one pass using something like C = (S - 
> M*M'/N) /
> N-1 where S = Sum_i I_i * I_i)
>
> Compute the eigenvalue and eigenvectors of C.
>
> The eigenvector associated with the largest eigenvalue is the direction 
> of
> the data that has the maximum "spread".  You now project your data onto 
> this
> "axis" and keep track of the min and max point once projected on this 
> axis.
> The difference between the min and max point will be the diameter.
>
> I think an eigenvector problem is order d^2 (where d is the dimension of 
> the
> problem, i.e 2d image, 3d image, etc.). So the overall time for this 
> approach is something like 2N + d^2.  Assuming N >> d, this will be
> a time savings.
>
>
>
> -----Original Message-----
> From: Benjamin King [mailto:king . benjamin at mh-hannover . de]
> Sent: Tuesday, November 18, 2003 7:18 AM
> To: ITK
> Subject: [Insight-users] diameter of segmented object
>
>
> Hi all,
>
> I want to compute the diameter of a segmented voxel object. As a first 
> approach, I took the binarized image and subtracted an eroded version to 
> get the boundary points. Then I compute the distance of each pair of 
> voxels and take the maximum.
> I need I much faster way (i.e. not O(N^2)) to do this.
>
> Any suggestion is much appreciated,
> Benjamin
>



-- 
Benjamin King
Institut für Medizinische Informatik
Medizinische Hochschule Hannover
Tel.: +49  511  532-2663