Distance transformations: fast algorithms and applications to medical image processing
Distance transformations: fast algorithms and applications to medical image processing
复制标题
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
O. Cuisenaire
中科院分区：
文献类型：
--
作者：
O. Cuisenaire
医学图像处理是一个对CPU和内存都要求很高的领域。要处理的数据量通常很大（一个典型的MRI数据集需要10兆字节），许多处理工具只有在作为实时应用程序可用时才对医生有用，也就是说，如果它们最多在几秒钟内运行。当然，这些需求中的很大一部分是——而且将是——由更强大的硬件的开发来处理的。另一方面，当面对非线性的计算复杂度时，改进算法的发展显然是最好的解决方案。距离变换是一种强大的图像分析工具，用于许多问题，如图像配准，需要这样的改进。距离图是一种图像，其中每个像素的值是从该像素到属于给定集合或对象的最近像素的距离。距离变换（DT）是一种从表示这组像素的二值图像计算距离图的算法。这个定义是全局的，因为它需要在所有图像像素和所有对象像素之间计算的一组距离上找到最小值。因此，直接应用该定义通常会导致难以接受的计算复杂度。已经提出了许多算法来将这种距离定义定位到最近的像素，并允许更快的DT计算，但到目前为止，没有一种算法将准确性和线性复杂性结合起来。距离变换在图像分析和模式识别中的许多应用已经被报道，而那些与医学图像处理相关的应用将在下面进行探讨。第1章介绍了一些基本概念，距离变换在模式识别中的典型应用，以及产生DT算法的关键挑战。第2章对已发表的算法进行了详尽的评述。讨论了最流行的算法的优缺点，并推导了原始算法的核心原理。第3、5、6、8和10章给出了原始的距离变换算法。每一章都以类似的方式组织起来。首先我们描述算法。然后我们评估它的计算复杂性，并将其与最先进的技术进行比较。第4章、第7章、第9章和第11章分别介绍了使用前一章中开发的算法对医学图像处理中的特定问题的应用。理想情况下，对任何医学图像处理问题的描述都应包括需要自动处理的医学理由、对该领域最新技术的完整回顾、对所提议的处理方法的详细描述，以及对结果的准确性及其医学意义的评估。由于本文的时间和空间限制，这种详尽的工作将仅在第4章中为应用程序提供，而其他应用程序将更简要地描述。第三章描述了一种新的利用有序传播的精确欧氏距离变换。它是基于拉格内尔曼近似欧几里得DT的一种变化。我们使用有限掩模分析近似欧几里得DT的误差模式，并推导出一个规则来定义，对于任何像素位置，保证DT准确性的邻域大小。该算法特别适合于实现数学形态学操作，详细介绍了这一点。在第四章中，我们将第三章的算法应用于坐骨神经显微图像中神经元纤维的分割。特别地，它被用来测定纤维中心周围髓鞘的厚度。这项研究是与伦敦大学学院神经康复工程实验室合作进行的。第五章基于图像Voronoi分割的显式计算，提出了另一种精确的欧氏距离变换。在Voronoi多边形的角落检测到可能的错误位置，并在需要时进行纠正。该算法被证明是迄今为止最快的精确EDT。它接近理论最优复杂度，CPU时间与计算距离的像素数成正比。第6章研究了如何将第3章和第5章的算法扩展到三维图像。它显示了这两种方法的局限性，并提出了一种混合第五章和斋藤的方法的混合算法。在第7章中，将3D欧几里得DT应用于大脑MR图像的配准，其中匹配标准是两个图像中相似物体（皮肤，皮层，心室系统等）表面之间的距离。举例说明，从项目与神经生理学实验室，伦敦大学学院和正电子断层扫描实验室，伦敦大学学院。第8章讨论了距离变换概念的扩展：非凸域上的测地线距离。由于测地线距离是基于路径的概念，因此必须在表示直线的精度和遵循域曲线的方式之间进行权衡。结果表明，无论选择何种权衡，都可以通过传播有效地实现测地线DT。通过回溯测地线距离传播，可以找到目标到起点的最短路径。在第9章中，这被用于规划虚拟内窥镜中摄像机运动的最佳路径，这是与波士顿哈佛医学院外科计划实验室合作完成的工作。第10章将欧氏距离变换从寻找最近的目标像素扩展到寻找k个最近的目标像素。研究表明，这可以在复杂度随k线性增加的情况下完成。在第11章中，k- dt被用作多模态MR成像中不同组织类型之间k近邻（k- nn）分类的快速实现。这是通过伦敦大学学院St-Luc医院放射科通过伦敦大学学院正电子断层扫描实验室提供的T1-T2图像对多发性硬化病变的分类来说明的。最后，得出一般性结论。它回顾了论文的主要贡献，它的应用，并探讨了一些新的领域，他们的应用也可能是有用的。最后，简要回顾了与本论文相关的出版物。
Medical image processing is a demanding domain, both in terms of CPU and memory requirements. The volume of data to be processed is often large (a typical MRI dataset requires 10 MBytes) and many processing tools are only useful to the physician if they are available as real-time applications, i.e. if they run in a few seconds at most. Of course, a large part of these demands are - and will be - handled by the development of more powerful hardware. On the other hand, when faced with non-linear computational complexity, the development of improved algorithms is obviously the best solution. Distance transformations, a powerful image analysis tool used in a number of problems such as image registration, requires such improvements. A distance map is an image where the value of each pixel is the distance from this pixel to the nearest pixel belonging to a given set or object. A distance transformation (DT) is an algorithm that computes a distance map from a binary image representing this set of pixels. This definition is global in the sense that it requires finding the minimum on a set of distances computed between all image pixels and all object pixels. Therefore, a direct application of the definition usually leads to an unacceptable computational complexity. Numerous algorithms have been proposed to localize this definition of distance to the nearest pixel and allow a faster DT computation, but up to now, none of them combines both exactness and linear complexity. Numerous applications of distance transformations to image analysis and pattern recognition have been reported and those related to medical image processing are explored in what follows. Chapter 1 introduces a few basic concepts, a typical application of distance transformations in pattern recognition and the key challenges in producing a DT algorithm. Chapter 2 contains an exhaustive critical review of published algorithms. The strong and weak points of the most popular ones are discussed and the core principles for our original algorithms are derived. Chapters 3, 5, 6, 8 and 10 present original distance transformation algorithms. Each of those chapters is organized in a somewhat similar fashion. First we describe the algorithm. Then we evaluate its computational complexity and compare it to the state of the art. Chapter 4, 7, 9 and 11 each present an application to a particular problem in medical image processing, using the algorithm developed in the previous chapter. Ideally, the description of any medical image processing problem should include a medical justification of the need for an automated processing, a complete review of the state of the art in the field, a detailed description of the proposed processing method, and an evaluation of the accuracy of the results and their medical significance. Because of both time and space constraints in this thesis, such an exhaustive work will only be presented for the application in chapter 4, while the other applications will be described more briefly. Chapter 3 describes a new exact Euclidean distance transformation using ordered propagation. It is based on a variation of Ragnelmam's approximate Euclidean DT. We analyze the error patterns for approximate Euclidean DT using finite masks, and we derive a rule defining, for any pixel location, the size of the neighborhood that guarantees the exactness of the DT. This algorithm is particularly well-suited to implement mathematical morphology operations, which are examined in details. In Chapter 4, we apply the algorithm of chapter 3 to the segmentation of neuronal fibers from microscopic images of the sciatic nerve. In particular, it is used to determine the thickness of the myelin sheath surrounding the center of the fiber. This study was carried out in collaboration with the Neural Rehabilitation Engineering Laboratory, UCL. Chapter 5 proposes another exact Euclidean distance transformation, based on the explicit computation of the Voronoi division of the image. Possible error locations are detected at the corners of the Voronoi polygons and corrected if needed. This algorithm is shown to be the fastest exact EDT to date. It approaches the theoretical optimal complexity, a CPU time proportional to the number of pixels on which the distance is computed. Chapter 6 investigates how the algorithms of chapters 3 and 5 can be extended to 3 dimensional images. It shows the limitations of both approaches and proposes an hybrid algorithm mixing the method of chapter 5 and Saito's. In Chapter 7, the 3D Euclidean DT is applied to the registration of MR images of the brain where the matching criterion is the distance between the surfaces of similar objects (skin, cortex, ventricular system, ...) in both images. Examples are shown, from projects with the Neuro-physiology Laboratory, UCL, and with the Positron Tomography Laboratory, UCL. Chapter 8 discusses an extension of the distance transformation concept: geodesic distances on non-convex domains. Because geodesic distances are based on the notion of paths, a trade-off has to be introduced between the accuracy with which straight lines are represented and the way curves of the domain are followed. It is shown that, whatever the trade-off chosen, there is an efficient implementation of the geodesic DT by propagation. By back-tracking the geodesic distance propagation, one can find the shortest path between a target and a starting point. In chapter 9, this is used to plan the optimal path for the camera movements in virtual endoscopy, a work done in collaboration with the Surgical Planning Laboratory, Harvard Medical School, Boston. Chapter 10 extends the Euclidean distance transformation from finding the nearest object pixel to finding the k nearest object pixels. It is shown that this can be done with a complexity increasing linearly with k. In Chapter 11, the k-DT is used as a fast implementation of the k Nearest Neighbors (k-NN) classification between different tissue types in multi-modal MR imaging. This is illustrated through the classification of multiple sclerosis lesions from T1-T2 images, provided by the Radiology unit, St-Luc Hospital, UCL, via the Positron Tomography Laboratory, UCL. Finally, a general conclusion is drawn. It reviews the main contributions of the thesis, its applications and explores some new domains in which their applications could also be useful. Ultimately, the publications related to this thesis are briefly reviewed.