胃上皮肿瘤边界跟踪算法的实现

ComputerEngineeringandApplications计算机 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 与应用 2007,43(4) 1 概述 在医学图像处理过程中,边界跟踪是图像识别的基础工 作,它为病理医生最终对病灶的定性判别起着关键性的作用。 本文研究工作的背景就是基于数字图像处理技术的“胃上皮肿 瘤病理诊断分析系统”。系统的设计流程是:采集胃上皮组织切 片的数字图像→图像预处理→图像分割→边界跟踪→特征提 取→分类识别。考虑采集图像中噪声点多,故图像预处理首先 对图像进行平滑运算,然后再中值滤波,图像分割选择基于迭 代的松弛分割算法,以把预处理后的图像分割为一幅 3值图 像,3值分别对应细胞核、细胞浆和背景像素值;在图像分割的 基础之上就可进一步对目标(细胞或胞核)进行边界跟踪了,文 中重点介绍边界跟踪算法的设计。 2 边界跟踪算法的设计 2.1 邻域简介 邻域分为4邻域和8邻域两种[1]。假设当前点是p=f(x,y), f代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 图像,则它在图像中的四邻域点分别是 f(x,y-1)、f(x,y+ 1)、f(x-1,y)和 f(x+1,y);假设当前点仍是 p=f(x,y),f代表图 像,则它在图像中的 8邻域点分别是 f(x,y-1)、f(x,y+1)、f(x- 1,y)、f(x+1,y)、f(x-1,y-1)、f(x-1,y+1)、f(x+1,y-1)和 f(x+1, y+1)。算法中使用的两种形式的邻域定义如图 1,其中 4邻域 遵循顺时针方向检索,主要跟踪目标物体的外边界[2]。而8邻域 遵循逆时针方向检索,主要跟踪目标物体的内边界[2](如内部 空洞)。 2.2 区域标号算法设计 在对图像进行边界跟踪之前,首先需要把位于同一闭合区 域的像素都标识为相同的标号。文献[1]中介绍了序贯算法[3],该 算法只对图像进行1次扫描可以完成区域标号,但该算法需要 额外的数据结构用来存放标号等价表,且在标号过程中对每 1 像素点的左上、上、左、右上 4个点的标号值两两分别进行比 较,以选择最小值,故要进行 6次标号比较,算法效率受到影 胃上皮肿瘤边界跟踪算法的实现 张红斌,甘 岚,李广丽 ZHANGHong-bin,GANLan,LIGuang-li 华东交通大学 信息工程学院,南昌 330013 InformationEngineeringSchool,EastChinaJiaotongUniversity,Nanchang330013,China E-mail:zhbdog@tom.com ZHANGHong-bin,GANLan,LIGuang-li.Realizationofboundarytrackingalgorithm totracestomachepidermistumor. ComputerEngineeringandApplications,2007,43(4):231-233. Abstract:Presentsanewmodifiedboundarytrackingalgorithm,ittakesthedirectionprioritysearchingasitssearchingpolicyto findboundarypointsbasedonthelabelingalgorithm.Intheprocessofboundarytrackingwenotonlyrecordtheboundary points,butalsorevisetheareathatthepointbelongsto,andaccordingtothisalgorithm,designsakindoftwo-dimensionalchain tabletorecordtheboundarypoints. Keywords:stomachepidermistumor;boundarytracking;labeling;two-dimensionalchaintable 摘 要:提出了一种修正型的边界跟踪算法,该算法基于区域标号算法,并以外法线方向作为优先搜索方向来确定边界点,在边界 跟踪过程中不但记录目标物体的边界点,而且还将校正像素点的归属区域。针对该算法,设计了一个 2维链表的数据结构用来保 存跟踪的边界点。 关键词:胃上皮肿瘤;边界跟踪;标号;2维链表 文章编号:1002-8331(2007)04-0231-03 文献标识码:A 中图分类号:TP391.4 基金项目:2006江西科技厅工业攻关项目。 作者简介:张红斌(1979-),男,华东交通大学信息工程学院讲师,主要研究方向:图像处理、多媒体技术;甘岚(1965-),女,华东交通大学信息工程 学院教授,硕士生导师,主要研究方向:图像处理、智能决策;李广丽(1978-),女,华东交通大学信息工程学院研究生,主要研究方向:多 媒体数据库。 231 ComputerEngineeringandApplications计算机工程与应用2007,43(4) 响。从减少数值比较次数的角度出发,本文借鉴文献[4]中的标 签处理算法[4]提出了一种快速区域标号算法,算法描述如下: (1)如果当前点的左边点的像素值和上方点的像素值相等 且为物体点,并且上方点和左边点的标号相同,则当前点的标 号同左边点或上方点; (2)如果当前点的左边点是物体点,上方点是背景点,则当 前点的标号同左边点; (3)如果当前点的左边点是背景点,上方点是物体点,则当 前点的标号同上方点; (4)如果当前点的左边点和上方点都是背景点,则当前点 的标号为新标号; (5)如果当前点的左边点的像素值和上方点的像素值相等 且为物体点,并且上方点和左边点的标号不相同,在左边点和 上方点两者中标号较小者赋值给当前点,同时修正左边点或上 方点的标号值。 该算法只要判断当前点的左边点和上方点的标号值及像 素值,以选择合适的标号值给当前点。可知当前点必属上述 5 种情况之一,故数值比较 2至 3次即可,且不需要额外的数据 结构存储标号等价表,算法运行速度得到了提高。实验中发现 它也存在缺陷:当对于凹凸或锯齿形闭合区域标识时存在偏 差,不过,这些都可以通过 2.3节中的修正型边界跟踪算法加 以消除。 2.3 修正型边界跟踪算法的设计 2.3.1 算法概述 修正型边界跟踪算法的核心是“边跟踪边修正”,即在跟踪 过程中修正当前边界点的区域标号值,使得位于同一闭合区域 边界上的点的标号值最小且完全相同,并记录被修正的标号 值,因为其他区域中相同标号的像素点的标号同样要修正。 2.3.2 下一相邻边界点的确定 边界跟踪过程中下一邻接边界点的确定对于正确计数边 界点个数以及成功完成跟踪都非常重要,算法中使用外法线方 向优先[5]的扫描方式。算法描述如图2所示。 2.3.3 修正型边界跟踪算法伪代码设计 算法将主要完成边界点的跟踪、保存、下一相邻边界点的 确定以及区域标号的修正,其伪码描述如下(以 4邻域跟踪 为例): While(所有区域未跟踪完毕) {获取新区域的起点,并记录当前点坐标 CurrentX和 CurrentY// 新区域跟踪开始 While(TRUE) {If(当前区域边界跟踪回到了起点) Break;//退出当前区域边界跟踪 Else {//令i为下一个边界点跟踪的起始方向 If(当前点横坐标==前一点横坐标&&当前点纵坐标== 前一点纵坐标+1) i=3//外法线优先,参照图1(a) If(当前点横坐标==前一点横坐标&&当前点纵坐标== 前一点纵坐标-1) i=1//外法线优先,参照图1(a) If(当前点横坐标==前一点横坐标&&当前点纵坐标== 前一点纵坐标-1) i=0//外法线优先,参照图1(a) If(当前点横坐标==前一点横坐标&&当前点纵坐标== 前一点纵坐标-1) i=2//外法线优先,参照图1(a) While(TRUE) {If(当前外法线优先方向的点是边界点) {把当前点加到当前区域的边界序列中 //保存当前点 PrevX=CurrentX //更新前一点坐标 PrevY=CurrentY CurrentX=当前点的X坐标; //更新当前点坐标 CurrentY=当前点的Y坐标 If(这个点的区域标号<前一点的区域标号) {记录原标号被前一点区域标号替代//更新其他区域相 同标号校正这个点的区域标号//标号校正 } Break;//当前点的下一点找到,退出当前点的下一点搜索 } Else i=(i+1)%4 //下一优先方向,8邻域则为i=(i+1)%8 }}} 切换到下一个封闭区域//准备新的区域跟踪 } 在算法执行过程中需要即时更新当前点坐标(用 CurrentX 和CurrentY表示)和前一点坐标(PrevX和 PrevY),主要是为了 正确地选择下一边界点。同时,在发现了下一边界点之后,还需 要对比当前边界点和前一边界点的区域标号,如果不相等则需 要记录这两个标号均标识相同区域,取两者中的最小者替代原 标号。由于算法对图像的扫描方向为自左向右、自上向下,所以 后续点的标号始终是正确的且值最小。 2.3.4 算法中数据结构的设计 考虑到细胞的形态特征参数的提取,所以,需要把每个区 域的边界保存到相应的数据结构中,为了节约内存,并提高数 据检索效率,笔者考虑采用 2维链表结构,链表数据结构定义 如下: structBoudary //该链表存放每一个闭合区域的坐标点集合,它 是次链表 {intx; //每个边界点的横坐标 inty; //每个边界点的纵坐标 Boudary*next; //指向边界跟踪得到的下一个边界点 }; structBoud_List//该链表将多个闭合区域链接起来,它不存储实 际数据,是主链表 232 ComputerEngineeringandApplications计算机工程与应用 2007,43(4) (上接178页) [4]SavasereA,OmiecinskiE,NavatheS.Anefficientalgorithmformin- ingassociationrulesinlargedatebases[C]//Proc1995IntConfVery LargeDataBases(VLDB’95),Zurich,Switzerland,1995:432-443. [5]HanJ,PeiJ,YinY.Miningfrequentpatternswithoutcandidate generation[C].//Proc2000ACMSIGMODIntConfManagementof Data(SIGMOD’00),Dallas,TX,2000:1-12. [6]CheungW,ZaianeOR.IncrementalMiningofFrequentPatterns WithoutCandidateGenerationorSupportConstraint[C]//ProcIDEAS 2003,HongKong. [7]ZhuY,SunZ,JiX.Incrementalupdatingalgorithmbasedonfrequent patterntreeofminingassociationrules[J].ChineaseJournalof Computers,2003,26(1):91-96. [8]MaXiu-li,TongYun-hai.Efficientincrementalmaintenceoffrequent patternswithFP-Tree[J].ComputerScienceandTechnology,2004, 19(6),876-884. [9]AgrawalR,ShaferJC.Parallelminingofassociationrules[J].IEEE TransactiononKnowledgeandDataEngineering,1996,8(6): 962-969. [10]HanEH,KarypisG,KumarV.Scalableparalleldataminigfor associationrules[C]//ProcACM SIGMODInternationalConference onManagementofData(SIGMOD’97),1997:277-288. {Boudary*phead; //指向该闭合区域头结点 Boud_List*lnext; //指向下一个闭合区域 }; 在边界跟踪过程中,当发现有新的边界的起点时,此时在 Boud_List中创建一个新的结点 T,同时创建一个 Boudary类型 的结点 P,令 T->phead=P,并将已经得到的新边界的第 1个边 界点坐标存放到P中,然后再根据2.3.3小节中的边界跟踪算 法逐一地将该闭合区域的边界点以 Boudary类型链接起来,当 发现新的边界点的坐标和 P完全相同时,该区域边界跟踪完 成。链表的数据结构如图3所示。 3 实验结果 应用本算法对图 4(a)中的胃上皮肿瘤切片图像进行了处 理,其中图4(b)是经过松弛迭代分割后的3值数字图像,图4(c) 是4邻域跟踪的结果,图4(d)是8邻域跟踪的结果。由图4可 以发现,本算法能够较好地区分出细胞、细胞核以及背景,为下 一步细胞的形态参数的计算创造了条件。 4 结论 实验结果证明了算法的正确性和可用性,故对本文提出的 算法的主要特点 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 如下: (1)该算法能正确地跟踪封闭的目标物体(细胞和细胞核) 的边界轮廓,并对不同区域进行标识,实验中该算法还有效地 避免了死循环和遗漏小凸部,此外,轮廓宽度只有 1个像素(见 图2)。 (2)算法中边界跟踪的起点也是边界跟踪的终点,同时,在 跟踪过程中必须随时记录边界当前点和前一点,从而正确确定 外法线方向(见2.3.3小节中的算法伪码)。 (3)在跟踪过程中采用二维链表的数据结构保存边界点, 为图像的特征参数提取做好了准备(见图3)。 (4)算法的运行结果能够满足“细、准、连”的边界跟踪准 则。其中 4邻域跟踪时间短,但边界不细腻,而8邻域跟踪边界 细腻清晰,但跟踪时间较长。 (5)算法效率得到提升,其一在区域标号过程中,一次循环 完成区域的快速标号;其二在边界跟踪过程中以外法线优先方 向作为第一搜索方向,避免逐一比较的烦琐。 本算法具有较强的通用性,现已经运用到了基于数字图像 处理技术的“胃上皮肿瘤病理诊断分析系统”中,对于细胞肿瘤 级别的识别起到了关键性的作用。(收稿日期:2006年5月) 参考文献: [1]崔枫魁,张丰收.二值图像目标邻域点法边界跟踪算法[J].洛阳工学 院学报,2001,22(1):28-30. [2]刘相滨,向坚持.基于八邻域边界跟踪的标号算法[J].计算机工程与 应用,2001,37(23):125-126. [3]宋培华,高敦岳.边界跟踪与序贯算法在二值连通区域标记中的应 用[J].计算机科学,2002,29(3):108-109. [4]李云,鲍苏苏.二值图像中物体区域的选定及外边缘跟踪技术[J].华 南师范大学学报:自然科学版,2000,3:26-29. [5]柳稼航,杨建峰.一种基于优先搜索方向的边界跟踪算法[J].遥感技 术与应用,2004,19(3):209-213. 张红斌,甘 岚,李广丽:胃上皮肿瘤边界跟踪算法的实现 233