[Insight-users] BinaryThinningImageFilter and BinaryPruningImageFiler

Uitert, Robert Van (NIH/CC/DRD) uitertr at cc.nih.gov
Tue Nov 30 15:39:32 EST 2004


Hi,

We had problems getting the BinaryThinningImageFilter and
BinaryPruningImageFilter to work properly.  The BinaryThinningImageFilter
was outputting one of the edges of the binary region rather than a skeleton
and the BinaryPruningImageFilter was not pruning the image at all.  Below
we've included a diff between the cvs version and our working versions of
the .txx files of these filters.  We would be glad to commit these back into
the itk repository.

Also on
http://www.itk.org/Doxygen/html/classitk_1_1BinaryThinningImageFilter.html
the documentation states that :
"This filter computes one pixel wide edges of the input image.
 The input is assumed to be a binary image. The filter will produce a
skeleton of the object"
those two lines contradict each other. The first should be:
"This filter computes one pixel wide skeleton of the input image."

For the itkBinaryPruningImageFilter, we decided to stop the pruning before
all desired iterations are completed, iff in the previous iteration there
were only 2 voxels eliminated. This is logical, as in this case the skeleton
has already been reduced to a single line.


Robert Van Uitert and Ingmar Bitter
Diagnostic Radiology Department
Clinical Center
National Institutes of Health



Index: itkBinaryThinningImageFilter.txx
===================================================================
RCS file:
/cvsroot/Insight/Insight/Code/Algorithms/itkBinaryThinningImageFilter.txx,v
retrieving revision 1.2
diff -r1.2 itkBinaryThinningImageFilter.txx
115a116
>   std::vector< std::vector<int> > structureElements(8);
117,124c118,216
<   typename NeighborhoodIteratorType::OffsetType offset1 = {{-1,-1}};
<   typename NeighborhoodIteratorType::OffsetType offset2 = {{-1,0}};
<   typename NeighborhoodIteratorType::OffsetType offset3 = {{-1,1 }};
<   typename NeighborhoodIteratorType::OffsetType offset4 = {{0,1}};
<   typename NeighborhoodIteratorType::OffsetType offset5 = {{1,1}};
<   typename NeighborhoodIteratorType::OffsetType offset6 = {{1,0}};
<   typename NeighborhoodIteratorType::OffsetType offset7 = {{1,-1}};
<   typename NeighborhoodIteratorType::OffsetType offset8 = {{0,-1}};
---
>   std::vector<typename NeighborhoodIteratorType::OffsetType> offset(8);
>   typename NeighborhoodIteratorType::OffsetType offset0 = {{-1,-1}};
>   offset[0] = offset0;
>   typename NeighborhoodIteratorType::OffsetType offset1 = {{-1,0}};
>   offset[1] = offset1;
>   typename NeighborhoodIteratorType::OffsetType offset2 = {{-1,1}};
>   offset[2] = offset2;
>   typename NeighborhoodIteratorType::OffsetType offset3 = {{0,1}};
>   offset[3] = offset3;
>   typename NeighborhoodIteratorType::OffsetType offset4 = {{1,1}};
>   offset[4] = offset4;
>   typename NeighborhoodIteratorType::OffsetType offset5 = {{1,0}};
>   offset[5] = offset5;
>   typename NeighborhoodIteratorType::OffsetType offset6 = {{1,-1}};
>   offset[6] = offset6;
>   typename NeighborhoodIteratorType::OffsetType offset7 = {{0,-1}};
>   offset[7] = offset7;
> 
>   // 3 4 5
>   // 2   6
>   // 1 8 7
> 
>   structureElements[0].push_back(1);
>   structureElements[0].push_back(2);
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(2);
>   structureElements[0].push_back(1);
>   structureElements[0].push_back(1);
> 
>   structureElements[1].push_back(1);
>   structureElements[1].push_back(1);
>   structureElements[1].push_back(2);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(2);
>   structureElements[1].push_back(1);
> 
>   structureElements[2].push_back(1);
>   structureElements[2].push_back(1);
>   structureElements[2].push_back(1);
>   structureElements[2].push_back(2);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(2);
> 
>   structureElements[3].push_back(2);
>   structureElements[3].push_back(1);
>   structureElements[3].push_back(1);
>   structureElements[3].push_back(1);
>   structureElements[3].push_back(2);
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(0);
> 
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(2);
>   structureElements[4].push_back(1);
>   structureElements[4].push_back(1);
>   structureElements[4].push_back(1);
>   structureElements[4].push_back(2);
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(0);
> 
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(2);
>   structureElements[5].push_back(1);
>   structureElements[5].push_back(1);
>   structureElements[5].push_back(1);
>   structureElements[5].push_back(2);
>   structureElements[5].push_back(0);
> 
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(2);
>   structureElements[6].push_back(1);
>   structureElements[6].push_back(1);
>   structureElements[6].push_back(1);
>   structureElements[6].push_back(2);
> 
>   structureElements[7].push_back(2);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(2);
>   structureElements[7].push_back(1);
>   structureElements[7].push_back(1);
>   structureElements[7].push_back(1);
> 
> 
>   bool somethingGotDeleted(true);  
>   while(somethingGotDeleted)
>   {   
>       somethingGotDeleted = false;
126,133c218
< 
<   
<   int count = 1;
<   while(count)
<     {   
<     count = 0;
<     ot.GoToBegin();
<     while( ! ot.IsAtEnd() )
---
>       for (int structrureElem=0; structrureElem<structureElements.size();
++structrureElem)
135,166c220,239
<       if (ot.GetCenterPixel())
<        {
<          PixelType genus;
<          genus  = ot.GetPixel(offset1) + ot.GetPixel(offset2);
<          genus += ot.GetPixel(offset3) + ot.GetPixel(offset4);
<          genus += ot.GetPixel(offset5) + ot.GetPixel(offset6);
<          genus += ot.GetPixel(offset7) + ot.GetPixel(offset8);
<          if (genus != 1)
<           {
<             genus += ot.GetPixel(offset8) * ot.GetPixel(offset1) *
ot.GetPixel(offset2);
<             genus += ot.GetPixel(offset2) * ot.GetPixel(offset3) *
ot.GetPixel(offset4);
<             genus += ot.GetPixel(offset4) * ot.GetPixel(offset5) *
ot.GetPixel(offset6);
<             genus += ot.GetPixel(offset6) * ot.GetPixel(offset7) *
ot.GetPixel(offset8);
<             genus -= ot.GetPixel(offset1) * ot.GetPixel(offset2);
<             genus -= ot.GetPixel(offset2) * ot.GetPixel(offset3);
<             genus -= ot.GetPixel(offset3) * ot.GetPixel(offset4);
<             genus -= ot.GetPixel(offset4) * ot.GetPixel(offset5);
<             genus -= ot.GetPixel(offset5) * ot.GetPixel(offset6);
<             genus -= ot.GetPixel(offset6) * ot.GetPixel(offset7);
<             genus -= ot.GetPixel(offset7) * ot.GetPixel(offset8);
<             genus -= ot.GetPixel(offset8) * ot.GetPixel(offset1);
<             genus -= ot.GetPixel(offset8) * ot.GetPixel(offset2);
<             genus -= ot.GetPixel(offset2) * ot.GetPixel(offset4);
<             genus -= ot.GetPixel(offset4) * ot.GetPixel(offset6);
<             genus -= ot.GetPixel(offset6) * ot.GetPixel(offset8);
<             --genus;
< 
<             if ( genus == 0 )
<              {
<                 ot.SetCenterPixel( genus );
<                 ++count;
<               }
---
>           for (ot.GoToBegin();  ! ot.IsAtEnd();  ++ot)
> 	  {
>               if (ot.GetCenterPixel())
> 	      {
> 	          bool matches(true);
> 	          for (int k=0;  matches && k<8; ++k)
> 		  {
> 		      int n = structureElements[structrureElem][k];
> 		      if (n<2)
> 		      {
> 		          int pixelOnOff = int(ot.GetPixel(offset[k]) > 0);
> 			  matches = (n == pixelOnOff);
> 		      }
> 		  }
> 		  if (matches)
> 		  {
> 		      ot.SetCenterPixel( PixelType(0) );
> 		      somethingGotDeleted = true;
> 		  }
> 	      }
168,170d240
<        }
< 
<       ++ot;
171a242,250
>       
>       // swap order to eliminate bias
>       for(int i=0; i<4; i++)
>       {
>          int num0 = drand48()*3.9999;
> 	 structureElements[num0*2].swap(structureElements[i*2]);
>          structureElements[num0*2+1].swap(structureElements[i*2+1]);
>       }
>   }
173d251
<     }  


Index: itkBinaryPruningImageFilter.txx
===================================================================
RCS file:
/cvsroot/Insight/Insight/Code/Algorithms/itkBinaryPruningImageFilter.txx,v
retrieving revision 1.4
diff -r1.4 itkBinaryPruningImageFilter.txx
118,125d117
<   typename NeighborhoodIteratorType::OffsetType offset1 = {{-1,-1}};
<   typename NeighborhoodIteratorType::OffsetType offset2 = {{-1,0}};
<   typename NeighborhoodIteratorType::OffsetType offset3 = {{-1,1 }};
<   typename NeighborhoodIteratorType::OffsetType offset4 = {{0,1}};
<   typename NeighborhoodIteratorType::OffsetType offset5 = {{1,1}};
<   typename NeighborhoodIteratorType::OffsetType offset6 = {{1,0}};
<   typename NeighborhoodIteratorType::OffsetType offset7 = {{1,-1}};
<   typename NeighborhoodIteratorType::OffsetType offset8 = {{0,-1}};
126a119
>   std::vector< std::vector<int> > structureElements(9);
128,147c121,227
<   
<   unsigned int count = 0;
<   while(count < m_Iteration)
<     {
<     ot.GoToBegin();
<     while( ! ot.IsAtEnd() )
<       {
<       if (ot.GetCenterPixel())
<        {
<          PixelType genus;
<          genus  = ot.GetPixel(offset1) + ot.GetPixel(offset2);
<          genus += ot.GetPixel(offset3) + ot.GetPixel(offset4);
<          genus += ot.GetPixel(offset5) + ot.GetPixel(offset6);
<          genus += ot.GetPixel(offset7) + ot.GetPixel(offset8);
<          if (genus < 2)
<            {
<              genus = 0;
<              ot.SetCenterPixel( genus );
<            }
<        }
---
>   std::vector<typename NeighborhoodIteratorType::OffsetType> offset(8);
>   typename NeighborhoodIteratorType::OffsetType offset0 = {{-1,-1}};
>   offset[0] = offset0;
>   typename NeighborhoodIteratorType::OffsetType offset1 = {{-1,0}};
>   offset[1] = offset1;
>   typename NeighborhoodIteratorType::OffsetType offset2 = {{-1,1}};
>   offset[2] = offset2;
>   typename NeighborhoodIteratorType::OffsetType offset3 = {{0,1}};
>   offset[3] = offset3;
>   typename NeighborhoodIteratorType::OffsetType offset4 = {{1,1}};
>   offset[4] = offset4;
>   typename NeighborhoodIteratorType::OffsetType offset5 = {{1,0}};
>   offset[5] = offset5;
>   typename NeighborhoodIteratorType::OffsetType offset6 = {{1,-1}};
>   offset[6] = offset6;
>   typename NeighborhoodIteratorType::OffsetType offset7 = {{0,-1}};
>   offset[7] = offset7;
> 
>   // 3 4 5
>   // 2   6
>   // 1 8 7
> 
>   structureElements[0].push_back(2);   // o o o
>   structureElements[0].push_back(0);   // o   o
>   structureElements[0].push_back(0);   // x 1 x
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(0);
>   structureElements[0].push_back(2);
>   structureElements[0].push_back(1);
> 
>   structureElements[1].push_back(1);   // o o o 
>   structureElements[1].push_back(2);   // x   o
>   structureElements[1].push_back(0);   // 1 x o
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(0);
>   structureElements[1].push_back(2);
> 
>   structureElements[2].push_back(2);
>   structureElements[2].push_back(1);
>   structureElements[2].push_back(2);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
>   structureElements[2].push_back(0);
> 
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(2);
>   structureElements[3].push_back(1);
>   structureElements[3].push_back(2);
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(0);
>   structureElements[3].push_back(0);
> 
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(2);
>   structureElements[4].push_back(1);
>   structureElements[4].push_back(2);
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(0);
>   structureElements[4].push_back(0);
> 
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(2);
>   structureElements[5].push_back(1);
>   structureElements[5].push_back(2);
>   structureElements[5].push_back(0);
>   structureElements[5].push_back(0);
> 
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(0);
>   structureElements[6].push_back(2);
>   structureElements[6].push_back(1);
>   structureElements[6].push_back(2);
>   structureElements[6].push_back(0);
> 
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(0);
>   structureElements[7].push_back(2);
>   structureElements[7].push_back(1);
>   structureElements[7].push_back(2);
> 
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
>   structureElements[8].push_back(0);
> 
>   int numGotDeleted = 3;  
>   for (int iteration = 0; numGotDeleted > 2 && iteration < m_Iteration;
++iteration )
>   {   
>       numGotDeleted = 0;
149c229,259
<       ++ot;
---
>       for (int structrureElem=0; structrureElem<structureElements.size();
++structrureElem)
>       {
>           for (ot.GoToBegin();  ! ot.IsAtEnd();  ++ot)
> 	  {
>               if (ot.GetCenterPixel())
> 	      {
> 	          bool matches(true);
> 	          for (int k=0;  matches && k<8; ++k)
> 		  {
> 		      int n = structureElements[structrureElem][k];
> 		      if (n<2)
> 		      {
> 		          int pixelOnOff = int(ot.GetPixel(offset[k]) > 0);
> 			  matches = (n == pixelOnOff);
> 		      }
> 		  }
> 		  if (matches)
> 		  {
> 		      ot.SetCenterPixel( PixelType(0) );
> 		      ++numGotDeleted;
> 		  }
> 	      }
>           }
>       }
>       
>       // swap order to eliminate bias
>       for(int i=0; i<9; i++)
>       {
>          int num0 = drand48()*8.9999;
> 	 structureElements[num0].swap(structureElements[i]);
>       }
151,152c261
<     ++count;
<     }  
---
> 


More information about the Insight-users mailing list