N-Dimensional Path Optimization: The Implementation of a Novel Algorithm in ITK
Abstract
Using the path framework we previously added to ITK, we implemented a novel algorithm for n-dimensional path optimization, which we call the ND Swath (NDS). NDS uses dynamic programming to globally optimize the placement of a path within an image, subject to several constraints and a user-supplied merit function. The NDS algorithm is presented in this paper along with a description of how it was implemented using ITK.
Keywords
Source Code and Data
File
Image
Image
Select a file to preview
Reviews
Ingmar Bitter
Friday 9 September 2005
Summary: The paper presents a novel N-dimensional path optimization algorithm called NDS.
Hypothesis: That the new NDS algorithm can find optimal path given reasonably close initial paths.
Evidence: A description of the algorithm, a description of itâs implementation, complexity analysis and a single 2D example. No higher dimensional examples were provided.
Open Science: No source code, nor executables, nor input/output data are available.
Reproducibility: The paper does not facilitate reproducing the work described within. Adding the described work as extensions to ITK as was done with the underlying path classes would make reproduction easy.
Use of Open Source Software: The work is based on and extends ITK.
Open Source Contributions: No code was provided.
Code Quality: No code was provided.
Applicability to other problems: The method would apply to may problems.
Suggestions for future work: The method seems to be very similar to the Dijkstra method for optimal shortest paths. Please add a comparison to that algorithm to the paper. Especially for open paths from source to sink you may find equivalence in the optimal path. I used Dijkstra and a special merit function to find optimal chain-code path centerlines and skeletons in a 2001 TVCG paper called âPenalized-Distance Volumetric Skeleton Algorithmâ. It is not clear what you mean when you talk about âscale spaceâ. Please add a reference.
Requests for additional information from authors: Please provide more examples, including higher dimensional ones, as you claim the method does work in N dimensions.
Additional Comments: I assume that by design this only works for chain-code paths, not for parametric paths. In case it can work for both, please clarify in the paper.
Conclusions: This paper does not adhere to open science standards, and is lacking some evidence that it will work on a variety of inputs of different dimensionality. It also could improve its background analysis. Once those things are ironed out it will be applicable to a wide range of problems.
Luis Ibanez
Monday 19 September 2005
Summary: This paper presents an algorithm for optimizing a path through pixels in an image. The algorithm is based on dynamic programing and accepts a user-provided optimization criterion. The paper provides a nice description of the mathematical principles behind the optimization approach, and a brief description of how those principles are implemented in an open source software.
Hypothesis: The paper presents the hypothesis that dynamic programming methods are suitable for optimizing paths on digital images.
Evidence: The paper does not provide evidence for the hypothesis.
Open Science: The paper does not satisfy the criteria of open science since no material is provided that will allow the readers to verify the claims in the paper.
Reproducibility: The paper did not provided enough elements for enabling reproducibility. The paper is too focused on the mathematical description of the algorithm and not enough on its implementation and usability.
Use of Open Source Software: The authors used the Insight Toolkit as development platform.
Open Source Contributions: The authors mention that their code was implemented in the form of ITK classes, but do not indicate where the reader can find these classes, or whether they are available.
Code Quality: There was no code available that would have allowed the reviewer to verify the quality.
Applicability to other problems: An algorithm for path optimization will have a wide range of applications. In particular on segmentation of anatomical structures.
Suggestions for future work: The reviewer encourage the authors to provide more examples of the use of their code.
Requests for additional information from authors: The reviewer will appreciate if the authors address more details on how their classes where implemented and how they can be used by others in order to foster their research.
Additional Comments: It is remarkable that the authors adopted the N-Dimensional philosophy of the Insight Toolkit. Implementing N-D algorithms require a significant amount of effort, but also provides a significant amount of return, since the algorithm can be applied to a larger set of problems.