<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div></div><div><br></div><div>Conversation reporting the problem:</div><div><br></div><div></div><blockquote type="cite"><div>Date: Sun, 17 Oct 2010 08:16:14 -0400<br>From: Luis Ibanez <<a href="mailto:luis.ibanez@kitware.com">luis.ibanez@kitware.com</a>><br>Subject: Re: [Insight-users] is there a problem in boundary face<br><span class="Apple-tab-span" style="white-space: pre; "> </span>calculator ?<br>To: <a href="mailto:devieill@irit.fr">devieill@irit.fr</a><br>Cc: <a href="mailto:insight-users@itk.org">insight-users@itk.org</a><br>Message-ID:<br><span class="Apple-tab-span" style="white-space: pre; "> </span><<a href="mailto:AANLkTimnydwJcaoaUL=PGJVDmCw0++hyckdPyCdOJFGb@mail.gmail.com">AANLkTimnydwJcaoaUL=PGJVDmCw0++hyckdPyCdOJFGb@mail.gmail.com</a>><br>Content-Type: text/plain; charset="utf-8"<br><br>Hi Francois,<br><br>Thanks for pointing this out.<br><br>You may have found a bug indeed.<br><br>The assumption of the boundary face<br>calculator is that the radius of the<br>neighborhood is smaller than half<br>of the image size.<br><br>Let me attempt to illustrate this in a<br>diagram:<br><br>XXXXXXXXXXXXXXXXXXXX<br>XXXXXXXXXXXXXXXXXXXX<br>HHHOOOOOOOOOOOOOOHHH<br>HHHOOOOOOOOOOOOOOHHH<br>HHHOOOOOOOOOOOOOOHHH<br>HHHOOOOOOOOOOOOOOHHH<br>XXXXXXXXXXXXXXXXXXXX<br>XXXXXXXXXXXXXXXXXXXX<br><br>Here we have the top and<br>bottom faces for a neighborhood<br>whose radius is (3,2) (3 in the<br>horizontal direction, and 2 in the<br>vertical direction).<br><br>Therefore, the "H" colums<br>form faces of width=3<br><br>while the "X" rows form faces<br>of height=2<br><br>Leaving ample room for the<br>central "face" marked by the<br>"O" symbols.<br><br>If we start increasing the values<br>of the radius, the "H" and "X"<br>regions will increase in size,<br>at the same time that the "O"<br>(the inside face) will decrease<br>in size.<br><br>Therefore, it is possible to get<br>to a point where the "O" region<br>is empty, or even further, where<br>the left and right "H" regions<br>start overlapping.<br><br>In your particular case,<br><br>A) You have an image of 4x4 pixels.<br><br>B) You set the radius to 1,1<br> therefore to a neighborhood<br> size of 3x3<br><br>C) You ask the calculator to partition<br> a subregion of the image, defined<br> by<br><br> Index = (1,0)<br> Size = (1,2)<br><br><br>So, in practice, you "image of interest''<br>is only of size 1x2.<br><br><br>Should you have used the full size of<br>the 4x4 image, you should have found<br>faces as in the diagram below:<br><br><br>BBBB<br>CAAD<br>CAAD<br>EEEE<br><br>Where "A" is the inside face,<br>and "B","C","D","E", are the lateral<br>faces<br><br>Since in (3) you limited the region<br>to only the "O"s in the diagram below:<br><br>XOOX<br>XXXX<br>XXXX<br>XXXX<br><br>Then the partition of the "OO" region<br>into faces becomes quite challenging.<br><br>The resulting "inside" region is certainly<br>correct in retuning an empty size.<br><br>As for the other regions, I agree with<br>you in that they are not consistent...<br><br>However,<br>I'm having trouble figuring out what<br>the "correct" answer should have been...<br><br><br>I would be tempted to say that the<br>request is not solvable, and that the<br>calculator should have simply thrown<br>and exception here.<br><br><br>Would you consider that a reasonable<br>behavior for the face calculator ?<br><br><br><br> Regards,<br><br><br> Luis<br><br><br>-----------------------------------------------------<br>On Fri, Oct 1, 2010 at 12:20 PM, <<a href="mailto:devieill@irit.fr">devieill@irit.fr</a>> wrote:<br><br><blockquote type="cite">Hello all,<br></blockquote><blockquote type="cite">the itk documentation state that the boundary face calculator should output<br></blockquote><blockquote type="cite">2N+1 region where N is considered to be the region/image dimension.<br></blockquote><blockquote type="cite">However when creating a itk::Image<double,2> containing 4 pixels and<br></blockquote><blockquote type="cite">running the following simple code :<br></blockquote><blockquote type="cite">____________________________________<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> typedef itk::NeighborhoodAlgorithm::ImageBoundaryFacesCalculator<<br></blockquote><blockquote type="cite">Image2D > FaceCalculatorType;<br></blockquote><blockquote type="cite"> itk::NeighborhoodAlgorithm::ImageBoundaryFacesCalculator< Image2D><br></blockquote><blockquote type="cite">faceCalculator;<br></blockquote><blockquote type="cite"> FaceCalculatorType::FaceListType faceList;<br></blockquote><blockquote type="cite"> itk::NeighborhoodAlgorithm::ImageBoundaryFacesCalculator<<br></blockquote><blockquote type="cite">Image2D>::FaceListType::iterator fit;<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> Image2D::RegionType region;<br></blockquote><blockquote type="cite"> Image2D::IndexType index;<br></blockquote><blockquote type="cite"> Image2D::SizeType size;<br></blockquote><blockquote type="cite"> itk::Size<2> radius;<br></blockquote><blockquote type="cite"> index[0] = 1;<br></blockquote><blockquote type="cite"> index[1] = 0;<br></blockquote><blockquote type="cite"> size[0] = 1;<br></blockquote><blockquote type="cite"> size[1] = 2;<br></blockquote><blockquote type="cite"> region.SetIndex(index);<br></blockquote><blockquote type="cite"> region.SetSize(size);<br></blockquote><blockquote type="cite"> radius[0]=1;<br></blockquote><blockquote type="cite"> radius[1]=1;<br></blockquote><blockquote type="cite"> faceList = faceCalculator(img1, region, radius);<br></blockquote><blockquote type="cite"> std::cout << " face list number " << faceList.size() << std::endl ;<br></blockquote><blockquote type="cite"> for (fit = faceList.begin(); fit!= faceList.end(); ++fit) {<br></blockquote><blockquote type="cite"> std::cout << " current face is " << *fit << std::endl ;<br></blockquote><blockquote type="cite"> }<br></blockquote><blockquote type="cite">_______________________________<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">I have the following output :<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">______________________________<br></blockquote><blockquote type="cite">face list number 4<br></blockquote><blockquote type="cite">current face is ImageRegion (0x25c0f10)<br></blockquote><blockquote type="cite">Dimension: 2<br></blockquote><blockquote type="cite">Index: [1, 1]<br></blockquote><blockquote type="cite">Size: [0, 0]<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">current face is ImageRegion (0x25c0f50)<br></blockquote><blockquote type="cite">Dimension: 2<br></blockquote><blockquote type="cite">Index: [1, 0]<br></blockquote><blockquote type="cite">Size: [1, 2]<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">current face is ImageRegion (0x25c0f90)<br></blockquote><blockquote type="cite">Dimension: 2<br></blockquote><blockquote type="cite">Index: [1, 0]<br></blockquote><blockquote type="cite">Size: [1, 1]<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">current face is ImageRegion (0x25c0fd0)<br></blockquote><blockquote type="cite">Dimension: 2<br></blockquote><blockquote type="cite">Index: [1, 1]<br></blockquote><blockquote type="cite">Size: [1, 1]<br></blockquote><blockquote type="cite">____________________________________<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Despite the fact that there is NOT the right number of regions,<br></blockquote><blockquote type="cite">what bothers me the most is that one gets duplicated pixels, or to put it<br></blockquote><blockquote type="cite">simply the regions given by the algorithm are overlapping.<br></blockquote><blockquote type="cite">Assuming that one build a filter using neighboorhood filters this<br></blockquote><blockquote type="cite">become troublesome (imagine with multithreading...).<br></blockquote><blockquote type="cite">My question are :<br></blockquote><blockquote type="cite">1) is the boundary calculator broken ?<br></blockquote><blockquote type="cite">2) what should be used instead to design fast filters requiring a radius ?<br></blockquote><blockquote type="cite">3) Can one have neuman boundary conditions with it ?<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Regards,<br></blockquote><blockquote type="cite">de Vieilleville Fran?ois<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote></div><div><br></div></blockquote><div><br></div><div></div><div>Conversation fixing the problem:</div><br><blockquote type="cite"><div>Date: Mon, 15 Nov 2010 17:41:28 +1100<br>From: wanlin <<a href="mailto:wanlinzhu@gmail.com">wanlinzhu@gmail.com</a>><br>Subject: Re: [Insight-users] ShapedNeighborhoodIterator problem<br>To: Dawood Masslawi <<a href="mailto:davoud_zzz@yahoo.com">davoud_zzz@yahoo.com</a>><br>Cc: <a href="mailto:insight-users@itk.org">insight-users@itk.org</a><br>Message-ID:<br><span class="Apple-tab-span" style="white-space: pre; "> </span><<a href="mailto:AANLkTinshsf2reaCTjSXHRh61dAp1OVXW0aWq9493jyN@mail.gmail.com">AANLkTinshsf2reaCTjSXHRh61dAp1OVXW0aWq9493jyN@mail.gmail.com</a>><br>Content-Type: text/plain; charset="iso-8859-1"<br><br>For issue 5). I ran cross it before and make some changes in<br>itkNeighborhoodAlgorithm.txx. Here is the patch, For 5x5 image with kernel<br>size 3x3, the output of regions list are<br><br>9<br>ImageRegion (0xb8b830)<br> Dimension: 2<br> Index: [1, 1]<br> Size: [3, 3]<br><br>5<br>ImageRegion (0xb8b870)<br> Dimension: 2<br> Index: [0, 0]<br> Size: [1, 5]<br><br>5<br>ImageRegion (0xb8b8b0)<br> Dimension: 2<br> Index: [4, 0]<br> Size: [1, 5]<br><br>3<br>ImageRegion (0xb8b8f0)<br> Dimension: 2<br> Index: [1, 0]<br> Size: [3, 1]<br><br>3<br>ImageRegion (0xb8b930)<br> Dimension: 2<br> Index: [1, 4]<br> Size: [3, 1]<br><br><br><br><br>On Mon, Nov 15, 2010 at 11:37 AM, Dawood Masslawi <<a href="mailto:davoud_zzz@yahoo.com">davoud_zzz@yahoo.com</a>>wrote:<br><br><blockquote type="cite"><br></blockquote><blockquote type="cite"> - 1) If I'm going to do this type of thing:<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - IteratorType::OffsetType top = {{0,-1}};<br></blockquote><blockquote type="cite"> - IteratorType::OffsetType bottom = {{0,1}};<br></blockquote><blockquote type="cite"> - IteratorType::OffsetType left = {{-1,0}};<br></blockquote><blockquote type="cite"> - IteratorType::OffsetType right = {{1,0}};<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - Then get the pixels with:<br></blockquote><blockquote type="cite"> - iterator[top][0]<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - is there an advantage to using the ShapedNeighborhoodIterator over<br></blockquote><blockquote type="cite"> just a NeighborhoodIterator?<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">You can use offsets for both ShapedNeighborhoodIterator and regular<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">NeighborhoodIterator, the difference is in performance. A regular<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">NeighborhoodIterator would need more pixels to form a rectangular<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">neighborhood (which artificially could be considered as a<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">"ShapedNeighborhoodIterator" using offsets) but a<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">ShapedNeighborhoodIterator would require less pixels in the neighborhood<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">to form a shaped neighborhood, less pixels mean less memory allocation<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">and less boundary checking which could remarkably improve the performance<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">specially for large neighborhoods in large and multidimensional images<br></blockquote><blockquote type="cite">plus,<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">handling shaped neighborhoods is easier with<br></blockquote><blockquote type="cite">the ShapedNeighborhoodIterator.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> - 2) If I do want to use the ShapedNeighborhood style, is this correct:<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - IteratorType::IndexListType::const_iterator indexIterator =<br></blockquote><blockquote type="cite"> iterator.GetActiveIndexList().begin();<br></blockquote><blockquote type="cite"> - while (indexIterator != iterator.GetActiveIndexList().end())<br></blockquote><blockquote type="cite"> - {<br></blockquote><blockquote type="cite"> - std::cout << (int)iterator[*indexIterator][0] << " ";<br></blockquote><blockquote type="cite"> - ++indexIterator;<br></blockquote><blockquote type="cite"> - }<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite">Yes, the following is also a good practice:<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">IteratorType::ConstIterator ci;<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> for (ci = iterator.Begin(); ci != iterator.End(); ci++)<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> {<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> std::cout << ci.get() << std::endl;<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> }<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> - 3) If I loop over the ActiveIndexList using the FaceCalculator, is<br></blockquote><blockquote type="cite"> the idea that in all regions except the 0th region I need to do something<br></blockquote><blockquote type="cite"> like:<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - IteratorType::IndexListType::const_iterator indexIterator =<br></blockquote><blockquote type="cite"> iterator.GetActiveIndexList().begin();<br></blockquote><blockquote type="cite"> - while (indexIterator != iterator.GetActiveIndexList().end())<br></blockquote><blockquote type="cite"> - {<br></blockquote><blockquote type="cite"> - bool valid;<br></blockquote><blockquote type="cite"> - iterator.GetPixel(*indexIterator,valid);<br></blockquote><blockquote type="cite"> - if(valid) { do something }<br></blockquote><blockquote type="cite"> - ++indexIterator;<br></blockquote><blockquote type="cite"> - }<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - Alternatively, I could use 4 separate loops (one for each face<br></blockquote><blockquote type="cite"> region) where I know which neighbor isn't valid. I would have to modify the<br></blockquote><blockquote type="cite"> ActiveIndexList to reflect this missing pixel before each loop.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Usually for neither of face calculator or neighborhood iterator you need to<br></blockquote><blockquote type="cite">perform<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">the boundary check yourself (notice that the iterator itself has to iterate<br></blockquote><blockquote type="cite">over the<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">boundary to check for its validity), the face calculator splits the image<br></blockquote><blockquote type="cite">into boundary<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">and non-boundary regions for the iterator to not to check for all of the<br></blockquote><blockquote type="cite">pixels and<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">only perform the boundary checking for pixels in the face region (pixels<br></blockquote><blockquote type="cite">with distance<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">from the image boundary equal or less than the neighborhood radius). This<br></blockquote><blockquote type="cite">would also<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">improve the performance specially for large datasets.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> - 4) I believe<br></blockquote><blockquote type="cite"> - iterator[top][0]<br></blockquote><blockquote type="cite"> - is equivalent to but faster than iterator.GetPixel(top). Is this<br></blockquote><blockquote type="cite"> correct?<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite">I'm not sure about this since I haven't seen a significant performance<br></blockquote><blockquote type="cite">difference.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> ------------------------------<br></blockquote><blockquote type="cite"> - 5) Am I correct that the face calculator returns overlapping regions?<br></blockquote><blockquote type="cite"> If I use a 5x5 image with a 3x3 kernel, it returns regions of size<br></blockquote><blockquote type="cite"> - 9<br></blockquote><blockquote type="cite"> - 5<br></blockquote><blockquote type="cite"> - 5<br></blockquote><blockquote type="cite"> - 5<br></blockquote><blockquote type="cite"> - 5<br></blockquote><blockquote type="cite"> -<br></blockquote><blockquote type="cite"> - totaling 29, when there are only 25 pixels. I don't see any functions<br></blockquote><blockquote type="cite"> to turn on/off this overlap. How is this usually handled?<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">------------------------------<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">To the best of my knowledge this is still an unsolved issue which was<br></blockquote><blockquote type="cite">brought up<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">by other users in the list as well. Usually the face calculator assumes<br></blockquote><blockquote type="cite">that the<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">face region is far smaller than the non-boundary region which could be an<br></blockquote><blockquote type="cite">issue<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">for small images or very large neighborhoods.<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Regards,<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Dawood<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">_____________________________________<br></blockquote><blockquote type="cite">Powered by <a href="http://www.kitware.com/">www.kitware.com</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Visit other Kitware open-source projects at<br></blockquote><blockquote type="cite"><a href="http://www.kitware.com/opensource/opensource.html">http://www.kitware.com/opensource/opensource.html</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Kitware offers ITK Training Courses, for more information visit:<br></blockquote><blockquote type="cite"><a href="http://www.kitware.com/products/protraining.html">http://www.kitware.com/products/protraining.html</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Please keep messages on-topic and check the ITK FAQ at:<br></blockquote><blockquote type="cite"><a href="http://www.itk.org/Wiki/ITK_FAQ">http://www.itk.org/Wiki/ITK_FAQ</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">Follow this link to subscribe/unsubscribe:<br></blockquote><blockquote type="cite"><a href="http://www.itk.org/mailman/listinfo/insight-users">http://www.itk.org/mailman/listinfo/insight-users</a><br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite"><br></blockquote>-------------- next part --------------<br>An HTML attachment was scrubbed...<br>URL: <<a href="http://www.itk.org/pipermail/insight-users/attachments/20101115/93d58843/attachment-0001.htm">http://www.itk.org/pipermail/insight-users/attachments/20101115/93d58843/attachment-0001.htm</a>><br>-------------- next part --------------<br>A non-text attachment was scrubbed...<br>Name: itkNeighborhoodAlgorithm.txx.patch<br>Type: text/x-patch<br>Size: 2375 bytes<br>Desc: not available<br>URL: <<a href="http://www.itk.org/pipermail/insight-users/attachments/20101115/93d58843/attachment-0001.bin">http://www.itk.org/pipermail/insight-users/attachments/20101115/93d58843/attachment-0001.bin</a>><br></div></blockquote><div><br></div></body></html>