计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (29): 24-26.

• 博士论坛 • 上一篇    下一篇

基于改进搜索策略的Live-Wire医学图像分割算法

王阳萍1,党建武1,李 强2,李 莎3   

  1. 1.兰州交通大学 电子与信息工程学院,兰州 730070
    2.中科院 近代物理研究所,兰州 730000
    3.兰州军区总医院,兰州 730020
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-11 发布日期:2007-10-11
  • 通讯作者: 王阳萍

Live-wire algorithm for medical image segmentation based on improved search strategy

WANG Yang-ping1,DANG Jian-wu1,LI Qiang2,LI Sha3   

  1. 1.School of Electronic & Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China 2.Institute of Modern Physics,Chinese Academy of Sciences,Lanzhou 730000,China 3.Lanzhou Generation Hospital Lanzhou Command,Lanzhou 730020,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-10-11 Published:2007-10-11
  • Contact: WANG Yang-ping

摘要: Live-Wire 分割算法提供了一种精确的、可再现的交互式医学图像分割方法。Live-Wire算法中最优路径的搜索通常采用Dijkstra算法,其时间复杂度为O[n2]。提出从两个方面对Live-Wire医学图像分割算法的搜索策略进行改进以提高Live-Wire算法的实时性:(1)在最短路径的搜索过程中应用二叉堆排序,使算法的时间复杂度从原来的O[n2]降为O[n ln n];(2)在最短路径搜索中加入到达目标节点即停止的限制条件,可明显减少搜索节点数,使算法的时间复杂度远小于O[n ln n]。经算法分析及实验表明,搜索策略的改进可显著提高Live-Wire算法的运行效率。

关键词: 医学图像, 交互式分割, Live-Wire 算法, Dijkstra算法, 搜索策略, 堆排序

Abstract: Live-wire segmentation algorithm provides an accurate,reproducible and interactive boundary extraction tool for the object segmentation in the medical images.Dijkstra algorithm with the complexity of the calculation time O[n2] is generally used for searching optimal path in Live-wire.The paper improves the search strategy of Live-Wire algorithm in two aspects:Heap sort is used for searching the globally optimal path from the start node to the goal node.The complexity of the calculation time can be reduced from O[n2] to O[n ln n] by the algorithm;The restriction condition that search ends namely with the finding of the goal node,is set up to greatly reduce searched nodes.Thus the complexity of the calculation time is much smaller than O[n ln n].Algorithm analysis and experiments indicate that the presented search strategy can evidently improve the efficiency of Live-Wire algorithm.

Key words: medical image, interactive segmentation, Live-Wire algorithm, Dijkstra algorithm, search strategy, heap sort