[Insight-users] Sparse image for building distance field
Sergiy Tkachuk
sergtk.job at gmail.com
Thu Apr 25 14:13:52 EDT 2013
Hello all,
This mail is mostly for reference if somebody will have the same task as
mine to solve.
Sparse image implementation from Dan works quite well, just small updates
required - implement not to store, and remove pixel with m_FillBufferValue.
But fixing only Sparse image does not resolve the issue with memory because
in general itk::SignedMaurerDistanceMapImageFilter fill whole image with
different values - output is not sparse any more.
Since in my case I need distance field values for object only, I just do
not setup values out of object.
SignedMaurerDistanceMapImageFilter also uses two filters to fill initial
zero value on border of the object: itk::BinaryThresholdImageFilter,
itk::BinaryContourImageFilter, which also fill all value of image for
calculation. But it is not difficult to avoid usage them - it is quite easy
to fill border with hand written code to eliminate using these filters.
All mentioned above allowed me to end up with usage of memory of order of
object size.
But time compexity is still the order of number of all pixels of image - I
have not reduced it.
It looks like it is good idea to investigate how Voronoi diagram is built
and modify it for sparse object, the paper is available at
http://www.csd.uwo.ca/~olga/Courses/Fall2009/9840/Chosen/linearExactEucl.pdf
If anybody know how algorithm of building Voronoi diagram could be modified
in simple way, I will be grateful for description.
--
Best wishes,
Sergiy Tkachuk
On Thu, Mar 28, 2013 at 11:59 PM, Sergiy Tkachuk <sergtk.job at gmail.com>wrote:
> Hi Dan,
>
> Thanks a lot for the link!
> It looks like what I was looking for!
> I tried code and just substituted itk::Image with itk::SparseImage and it
> works!
>
> I read your article before at
> http://www.kitware.com/media/html/AlternativeMemoryModelsForITK.html .
> After this I looked at
> http://www.itk.org/Doxygen/html/classitk_1_1SparseImage.html and this
> completely measleaded me - implementation of SparseImage in ITK is do
> something different. But SparseImage at
> http://www.insight-journal.org/browse/publication/646 is ok!
>
> Thanks,
> --
> Best wishes,
> Sergiy Tkachuk
>
>
>
> On Fri, Mar 22, 2013 at 9:58 PM, Dan Mueller <dan.muel at gmail.com> wrote:
>
>> Hi Sergiy,
>>
>> You might also be interested in the following Insight Journal article:
>> http://www.insight-journal.org/browse/publication/646
>>
>> It is quite old, so I doubt it will compile with the latest ITK without
>> modifications...
>>
>> HTH
>>
>> Cheers, Dan
>>
>>
>> On 22 March 2013 23:16, Sergiy Tkachuk <sergtk.job at gmail.com> wrote:
>>
>>> Hello all,
>>>
>>> I want to build distance field for the object.
>>> My object is very sparsed and I want to build distance field for it and
>>> not to allocate memory for every voxel in the grid.
>>> Number of voxel in 3d grid is about 10^10 (more precisely:
>>> 2000x2000x2000)
>>> Number of voxel in object itself is about 10^6.
>>>
>>> I tried to play with itk::SignedMaurerDistanceMapImageFilter creating
>>> image 5x5x5 in sandbox:
>>>
>>>
>>> const unsigned int Dimension = 3;
>>> typedef char InputPixelType;
>>> typedef float OutputPixelType;
>>>
>>> typedef itk::Image<InputPixelType, Dimension> InputImageType;
>>> typedef itk::Image<OutputPixelType, Dimension> OutputImageType;
>>>
>>> InputImageType::Pointer image = InputImageType::New();
>>>
>>> InputImageType::SizeType size;
>>> size[0] = 5;
>>> size[1] = 5;
>>> size[2] = 5;
>>>
>>> InputImageType::IndexType start;
>>> start.Fill(0);
>>>
>>> InputImageType::RegionType region;
>>> region.SetIndex(start);
>>> region.SetSize(size);
>>>
>>> image->SetRegions(region);
>>> image->Allocate();
>>>
>>> image->FillBuffer(0);
>>>
>>> InputImageType::IndexType index;
>>>
>>> // initialize
>>> InputImageType::IndexType gapIndex;
>>> gapIndex[0] = gapIndex[1] = gapIndex[2] = 2;
>>> for (index[0] = 0; index[0] < size[0]; ++index[0])
>>> for (index[1] = 0; index[1] < size[1]; ++index[1])
>>> for (index[2] = 0; index[2] < size[2]; ++index[2]) {
>>> if (index == gapIndex) continue;
>>> image->SetPixel(index, 1);
>>> }
>>>
>>> // Define the distance map filter and apply it to the image
>>> typedef itk::SignedMaurerDistanceMapImageFilter<InputImageType,
>>> OutputImageType> DistanceFilterType;
>>> DistanceFilterType::Pointer distanceFilter =
>>> DistanceFilterType::New();
>>> distanceFilter->SetInput(image);
>>> distanceFilter->SetBackgroundValue(0);
>>> distanceFilter->SetSquaredDistance(false);
>>> distanceFilter->Update();
>>>
>>> // Output distance field values
>>> for (int x = 1; x < size[0]-1; ++x)
>>> {
>>> for (int y = 1; y < size[1]-1; ++y)
>>> {
>>> for (int z = 1; z < size[2]-1; ++z)
>>> {
>>> InputImageType::IndexType ind;
>>> ind[0] = x;
>>> ind[1] = y;
>>> ind[2] = z;
>>>
>>> float value = distanceFilter->GetOutput()->GetPixel(ind);
>>> std::cout << x << " " << y << " " << z << " -> " <<
>>> value << std::endl;
>>> }
>>> }
>>> }
>>>
>>>
>>> The code works fine.
>>> But it requires memory for every voxel of grid, and this is not
>>> acceptable for 10^10 voxels.
>>>
>>> Is it possible to use some kind of sparse structure to build distance
>>> field?
>>>
>>> I read about itk::SparseImage, but it seems this structure is sparse
>>> concerning value only, but indices are allocated for the whole grid. Am I
>>> undestood correctly? If no, I will be glad if somebody point out where I am
>>> mistaken. Thanks.
>>>
>>> If itk::SparseImage is not sutable in my case, is it possible to
>>> implement custom Image format for input to
>>> itk::SignedMaurerDistanceMapImageFilter?
>>> If so, are the any useful guidelines to achieve this?
>>> For now it is not clear for me how to correctly derive my Image type
>>> from DataObject and handle regions - I don't need full power of ITK filter
>>> pipeline, just to call itk::SignedMaurerDistanceMapImageFilter - possibly
>>> this helps me to simplify custom image implementation.
>>>
>>> Any ideas could be helpful for me!
>>>
>>> Thanks in advance,
>>> Sergiy
>>>
>>>
>>> _____________________________________
>>> Powered by www.kitware.com
>>>
>>> Visit other Kitware open-source projects at
>>> http://www.kitware.com/opensource/opensource.html
>>>
>>> Kitware offers ITK Training Courses, for more information visit:
>>> http://www.kitware.com/products/protraining.php
>>>
>>> Please keep messages on-topic and check the ITK FAQ at:
>>> http://www.itk.org/Wiki/ITK_FAQ
>>>
>>> Follow this link to subscribe/unsubscribe:
>>> http://www.itk.org/mailman/listinfo/insight-users
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.itk.org/pipermail/insight-users/attachments/20130425/b2bc3b85/attachment.htm>
More information about the Insight-users
mailing list