<div dir="ltr"><div><div><div><div><div><div><div><div><div>Hello all,<br><br></div>This mail is mostly for reference if somebody will have the same task as mine to solve.<br><br></div>Sparse image implementation from Dan works quite well, just small updates required - implement not to store, and remove pixel with m_FillBufferValue.<br>
</div><div><br></div>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.<br>
</div>Since in my case I need distance field values for object only, I just do not setup values out of object.<br></div></div></div><br>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.<br>
<br></div>All mentioned above allowed me to end up with usage of memory of order of object size.<br><br></div><div>But time compexity is still the order of number of all pixels of image - I have not reduced it.<br></div>
<div>
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 <a href="http://www.csd.uwo.ca/~olga/Courses/Fall2009/9840/Chosen/linearExactEucl.pdf">http://www.csd.uwo.ca/~olga/Courses/Fall2009/9840/Chosen/linearExactEucl.pdf</a> <br>
</div><div class="gmail_extra">If anybody know how algorithm of building Voronoi diagram could be modified in simple way, <span id="result_box" class="" lang="en"><span class="">I will be</span> <span class="">grateful for description.<br>
</span></span><br clear="all"><div>--<div>Best wishes,</div><div>Sergiy Tkachuk</div><br></div><br><div class="gmail_quote">On Thu, Mar 28, 2013 at 11:59 PM, Sergiy Tkachuk <span dir="ltr"><<a href="mailto:sergtk.job@gmail.com" target="_blank">sergtk.job@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Dan,<br><br>Thanks a lot for the link!<br>It looks like what I was looking for!<br>I tried code and just substituted itk::Image with itk::SparseImage and it works!<br>
<br>I read your article before at <a href="http://www.kitware.com/media/html/AlternativeMemoryModelsForITK.html" target="_blank">http://www.kitware.com/media/html/AlternativeMemoryModelsForITK.html</a> . <br>
After this I looked at <a href="http://www.itk.org/Doxygen/html/classitk_1_1SparseImage.html" target="_blank">http://www.itk.org/Doxygen/html/classitk_1_1SparseImage.html</a> and this completely measleaded me - implementation of SparseImage in ITK is do something different. But SparseImage at <a href="http://www.insight-journal.org/browse/publication/646" target="_blank">http://www.insight-journal.org/browse/publication/646</a> is ok!<br>
<br>Thanks,<br clear="all"><div>--<div>Best wishes,</div><div>Sergiy Tkachuk</div><div><br></div></div>
<br><br><div class="gmail_quote">On Fri, Mar 22, 2013 at 9:58 PM, Dan Mueller <span dir="ltr"><<a href="mailto:dan.muel@gmail.com" target="_blank">dan.muel@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div dir="ltr">Hi Sergiy,<div><br></div><div>You might also be interested in the following Insight Journal article:</div><div> <a href="http://www.insight-journal.org/browse/publication/646" target="_blank">http://www.insight-journal.org/browse/publication/646</a></div>
<div><br></div><div>It is quite old, so I doubt it will compile with the latest ITK without modifications...</div><div><br></div><div>HTH</div><div><br></div><div>Cheers, Dan</div></div>
<div class="gmail_extra"><br><br><div class="gmail_quote">On 22 March 2013 23:16, Sergiy Tkachuk <span dir="ltr"><<a href="mailto:sergtk.job@gmail.com" target="_blank">sergtk.job@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Hello all,<br><br>I want to build distance field for the object.<br>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.<br>Number of voxel in 3d grid is about 10^10 (more precisely: 2000x2000x2000)<br>
Number of voxel in object itself is about 10^6.<br><br>I tried to play with itk::SignedMaurerDistanceMapImageFilter creating image 5x5x5 in sandbox:<br><br><br> const unsigned int Dimension = 3;<br> typedef char InputPixelType;<br>
typedef float OutputPixelType;<br><br> typedef itk::Image<InputPixelType, Dimension> InputImageType;<br> typedef itk::Image<OutputPixelType, Dimension> OutputImageType;<br><br> InputImageType::Pointer image = InputImageType::New();<br>
<br> InputImageType::SizeType size;<br> size[0] = 5;<br> size[1] = 5;<br> size[2] = 5;<br><br> InputImageType::IndexType start;<br> start.Fill(0);<br><br> InputImageType::RegionType region;<br> region.SetIndex(start);<br>
region.SetSize(size);<br><br> image->SetRegions(region);<br> image->Allocate();<br><br> image->FillBuffer(0);<br><br> InputImageType::IndexType index;<br><br> // initialize <br> InputImageType::IndexType gapIndex;<br>
gapIndex[0] = gapIndex[1] = gapIndex[2] = 2;<br> for (index[0] = 0; index[0] < size[0]; ++index[0])<br> for (index[1] = 0; index[1] < size[1]; ++index[1])<br> for (index[2] = 0; index[2] < size[2]; ++index[2]) {<br>
if (index == gapIndex) continue;<br> image->SetPixel(index, 1);<br> }<br><br> // Define the distance map filter and apply it to the image<br> typedef itk::SignedMaurerDistanceMapImageFilter<InputImageType, OutputImageType> DistanceFilterType;<br>
DistanceFilterType::Pointer distanceFilter = DistanceFilterType::New();<br> distanceFilter->SetInput(image);<br> distanceFilter->SetBackgroundValue(0);<br> distanceFilter->SetSquaredDistance(false);<br>
distanceFilter->Update();<br> <br> // Output distance field values<br> for (int x = 1; x < size[0]-1; ++x)<br> {<br> for (int y = 1; y < size[1]-1; ++y)<br> {<br> for (int z = 1; z < size[2]-1; ++z)<br>
{<br> InputImageType::IndexType ind;<br> ind[0] = x;<br> ind[1] = y;<br> ind[2] = z;<br><br> float value = distanceFilter->GetOutput()->GetPixel(ind);<br>
std::cout << x << " " << y << " " << z << " -> " << value << std::endl;<br> }<br> }<br> }<br><br><br>The code works fine.<br>
But it requires memory for every voxel of grid, and this is not acceptable for 10^10 voxels.<br><br>Is it possible to use some kind of sparse structure to build distance field?<br><br>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.<br>
<br>If itk::SparseImage is not sutable in my case, is it possible to implement custom Image format for input to itk::SignedMaurerDistanceMapImageFilter?<br>If so, are the any useful guidelines to achieve this?<br>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.<br>
<br>Any ideas could be helpful for me!<br><br>Thanks in advance,<br>Sergiy<br><br>
<br>_____________________________________<br>
Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at<br>
<a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Kitware offers ITK Training Courses, for more information visit:<br>
<a href="http://www.kitware.com/products/protraining.php" target="_blank">http://www.kitware.com/products/protraining.php</a><br>
<br>
Please keep messages on-topic and check the ITK FAQ at:<br>
<a href="http://www.itk.org/Wiki/ITK_FAQ" target="_blank">http://www.itk.org/Wiki/ITK_FAQ</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://www.itk.org/mailman/listinfo/insight-users" target="_blank">http://www.itk.org/mailman/listinfo/insight-users</a><br>
<br></blockquote></div><br></div>
</blockquote></div><br>
</blockquote></div><br></div></div>