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

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (29): 24-26.

• 博士论坛 • Previous Articles Next Articles

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

WANG Yang-ping¹,DANG Jian-wu¹,LI Qiang²,LI Sha³

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医学图像分割算法

王阳萍¹,党建武¹,李强²,李莎³

1.兰州交通大学电子与信息工程学院,兰州 730070
2.中科院近代物理研究所,兰州 730000
3.兰州军区总医院,兰州 730020

通讯作者: 王阳萍

Abstract

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

摘要： 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算法, 搜索策略, 堆排序

WANG Yang-ping¹,DANG Jian-wu¹,LI Qiang²,LI Sha³. Live-wire algorithm for medical image segmentation based on improved search strategy[J]. Computer Engineering and Applications, 2007, 43(29): 24-26.

王阳萍¹,党建武¹,李强²,李莎³. 基于改进搜索策略的Live-Wire医学图像分割算法[J]. 计算机工程与应用, 2007, 43(29): 24-26.

[1]	ZHANG Xiaoli, ZHANG Kuixing, JIANG Mei, WEI Benzheng, CONG Jinyu. Review of Image Classification Technology for Lymphoma [J]. Computer Engineering and Applications, 2021, 57(6): 1-9.
[2]	LI Yuqi, LIU Zhiqian, CHENG Ningyi, WANG Yingying, ZHU Chunli. Path Planning of UAV Under Multi-constraint Conditions [J]. Computer Engineering and Applications, 2021, 57(4): 225-230.
[3]	PENG Jing, LUO Haoyu, ZHAO Gansen, LIN Chengchuang, YI Xusheng, CHEN Shaojie. Survey of Medical Image Segmentation Algorithm in Deep Learning [J]. Computer Engineering and Applications, 2021, 57(3): 44-57.
[4]	GAO Shuang, XU Qiaozhi. Review of Application of Transfer Learning in Medical Image Field [J]. Computer Engineering and Applications, 2021, 57(24): 39-50.
[5]	LU Wei, LIU Dan, SHAO Min, WU Yangdong. Application of Improved Mask R-CNN Network in Medical Image Recognition and Segmentation [J]. Computer Engineering and Applications, 2021, 57(24): 234-241.
[6]	ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan. Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search [J]. Computer Engineering and Applications, 2021, 57(21): 270-277.
[7]	LI Ying. Review of Application of Transfer Learning in Medical Image Analysis [J]. Computer Engineering and Applications, 2021, 57(20): 42-52.
[8]	LI Jiasheng, GUO Shuxu, ZHANG Lei, ZHENG Shuang, ZHANG Huimao, QIU Yunhai, LI Xueyan. Research of Segmentation and Detection of Liver Metastases from CT Images Based on Deep Network [J]. Computer Engineering and Applications, 2021, 57(2): 191-197.
[9]	LI Xiangxia, XIE Xian, LI Bin, YIN Hua, XU Bo, ZHENG Xinwei. Application of Generative Adversarial Networks in Medical Image Processing [J]. Computer Engineering and Applications, 2021, 57(18): 24-37.
[10]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[11]	GUO Yanfen, CUI Zhe, YANG Zhipeng, PENG Jing, HU Jinrong. Research Progress of Medical Image Registration Technology Based on Deep Learning [J]. Computer Engineering and Applications, 2021, 57(15): 1-8.
[12]	WANG Xiuli, ZHOU Peng, HOU Jingnan, WANG Shijun, LIN Xia. Research on Algorithm of Inspection Path Planning for Substation Robot [J]. Computer Engineering and Applications, 2021, 57(14): 245-250.
[13]	CHEN Shaojie, ZHAO Gansen, LIN Chengchuang, PENG Jing, HUANG Kaixin, LI Zhuangwei, HUANG Runhua, DU Jiahua, FAN Xiaomao. Survey of Application of Deep Learning in Chromosome Segmentation [J]. Computer Engineering and Applications, 2021, 57(11): 46-56.
[14]	ZHOU Tao, LU Huiling, HUO Bingqiang. Survey of Deep Belief Network [J]. Computer Engineering and Applications, 2020, 56(9): 24-32.
[15]	YE Yingshi, WEI Fuyi, CAI Xianzi. Research on Fast Dijkstra Algorithm Based on Parallel Computing [J]. Computer Engineering and Applications, 2020, 56(6): 58-65.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics