[Insight-users] Patch for bug in itkCannyEdgeDetectionImageFilter.txx

[Zachary Pincus]

Hello,

There is a subtle but problematic bug in  
itkCannyEdgeDetectionImageFilter.txx (in Code/BasicFilters).

Basically, Hysteresis Thresholding (the third or fourth step of Canny  
edge finding, depending on how you count it) fails in this  
implementation.

Here's the important loop of FollowEdge (line 431) as it is. This loop  
is supposed to follow edges until they dip below a lower bound. The  
problem is that every time a new node is pushed onto the stack, it is  
immediately popped off, so no actual following goes on.

  while(!m_NodeList->Empty())
     {
     node = m_NodeList->Front();
     cIndex = node->m_Value;
     oit.SetLocation(cIndex);
     uit.SetIndex(cIndex);
     uit.Value() = 1;

     for(int i = 0; i < nSize; i++)
       {
       nIndex = oit.GetIndex(i);
       uit.SetIndex(nIndex);
       if(InBounds(nIndex))
         if(oit.GetPixel(i) > m_LowerThreshold && uit.Value() != 1  )
           {
           node = m_NodeStore->Borrow();
           node->m_Value = nIndex;
           m_NodeList->PushFront(node); // NEW NODE PUSHED HERE

           uit.SetIndex(nIndex);
           uit.Value() = 1;
           }
       }

     m_NodeList->PopFront(); // AND IMMEDIATELY POPPED!
     m_NodeStore->Return(node);

     }

That PopFront() command at the second-to-last line is the problem.  
Every time a new node is pushed to the search stack in the "if" block  
above, it is immediately popped off. (This pop is meant to simply free  
the original node grabbed at the top of the while loop.)
My solution is to do the PopFront command at the top of the loop, and  
*then* push the new node (stored in a temp variable to avoid problems  
with the Return(node) statement at the end).
Here's the diff:
%diff  
ITK-CVS-src/Insight/Code/BasicFilters/ 
itkCannyEdgeDetectionImageFilter.txx  
NEWCannyEdgeDetectionImageFilter.txx

437c437
<   ListNodeType * node;
---
 >   ListNodeType * node, *tempNode;
454a455
 >     m_NodeList->PopFront();
467,469c468,470
<           node = m_NodeStore->Borrow();
<           node->m_Value = nIndex;
<           m_NodeList->PushFront(node);
---
 >           tempNode = m_NodeStore->Borrow();
 >           tempNode->m_Value = nIndex;
 >           m_NodeList->PushFront(tempNode);
476d476
<     m_NodeList->PopFront();



Zach Pincus

Department of Biochemistry and Program in Biomedical Informatics
Stanford University School of Medicine