1、research on cerebral aneurysm detectionbased on opta algorithmjian wu, guangming zhang, jie xia, and zhiming cuiproceedings of the 2009 international symposium on information processinghuangshan, p. r. china, august 21-23, 2009, pp. 037-040基于opta細化算法的有關腦動脈瘤檢測的研究吳建，張廣明，謝杰，崔志明2009年8月21日 23日中國黃山2009年信息

2、處理國際研討會論文集 037頁040頁摘 要在腦動脈瘤識別系統中，這是能夠準確、快速地在圖像中定位出腦動脈瘤位置的關鍵步驟。經過了腦動脈瘤的形態特征的詳細分析后，本文提出了一種新的腦動脈瘤檢測方法，這種檢測方法是基于改進了的細化算法。在這種新的檢測方法中，首先利用opta細化算法提取出血管的骨架，然后根據血管的骨架信息來檢測腦動脈瘤。經過大量實驗之后發現，腦動脈瘤識別過程在以這種新的檢測方法為前提的情況下，可以很好的檢測到腦動脈瘤的位置。關鍵詞： opta， 細化算法， 腦動脈瘤檢測， 模板匹配.前言腦血管疾病，尤其是腦動脈瘤，是導致成年人生病最后死亡的關鍵因素之一，它嚴重威脅著人們得生命安全

3、。隨著計算機技術的不斷發展和成熟，信息技術和醫學成像技術結合而產生的cad(應用計算機輔助診斷)系統在腦血管疾病的檢測與治療中起到越來越重要的作用，它已經成為了醫學成像上的一個研究重點。腦血管瘤一般位于血管的交叉位置，尤其是在腦動脈周圍。原因是血液的流動對血管交叉位置的影響很大。腦血管的影響類似于河流形成的網絡，會出現許多分支的動脈血管。一般來說，血管是對稱的，它的兩側的血管壁是相互平行的。而腦動脈瘤是由于血管壁損壞而導致的突出的部分。腦動脈瘤的示意圖如圖1所示。圖1 腦動脈瘤的示意圖如圖1，圖中用方格標志的地方就是腦動脈瘤。正常的血管出已經形成了突出的部分，大致平行的血管壁被破壞了。被破壞的

4、位置明顯是在交叉處。所以我們可以確定腦動脈瘤的位置應該在血管骨架結構的交叉處。在基于dsa(數字減法血管造影術)的腦動脈瘤cad系統中，它是特征提取及識別的前提和重要步驟，應用在檢測腦動脈瘤位置的dsa中。本文分析了腦動脈瘤的形態特征，包括通過細化算法得到的血管骨架的拓撲結構，然后對骨架樹進行深度優先遍歷，最后定位出腦動脈瘤的位置。.opta算法opta(一次通過細化算法)是一種典型的基于模板的圖像細化算法，其核心是通過應用消去和保留模板實現細化過程。opta是一個迭代的過程。如果當前的點滿足消去模板同時不滿足保留模板，那么這個點就被消去，否則，保留此點。不斷遍歷原始圖片，直到再沒有點滿足上述

5、要求。對opta算法的主要改進的地方就在于根據原算法的效果和速度增加了消去和保留模板。其中最典型的參考文件是13。文獻1的作者發現原始的opta算法細化的不完整，有一定的缺陷，細化出的圖像有毛刺且不夠平滑。改進的算法中已經將消去和保留模板進行了改善。圖2和圖3是改進了的消去和保留模板。其中有陰影的方格是當前點。圖2 消去模板1圖3 保留模板1從文獻1可以看出，在原始算法中，保留模板太松弛了，分析圖像可以得知，會容易產生右斜線，且使迭代次數會增加，速度會變慢。因此，在文獻1的基礎上突出了新的保留模板，并增至9個。從圖4可以看出，保留模板的條件變得更加嚴格，從而解決了右斜線的問題，速度也有明顯的改

6、善。圖4 保留模板2通過深入的改進，由袁梅和其他作者發現的右斜線的影響已經被文獻2中的算法很好的解決了，且速度有了很大的提升。由于增強了的保留條件，使得圖像出現了斷點。從而導致了拓撲結構和原始圖像被破壞了，細化算法也被減弱了。在以上分析的基礎上，袁梅和其他的作者提出了組合模板的概念，利用文獻1的消去模板，放棄其中的保留模板，并且結合了對當前點的判斷，判斷當前點是否符合消去模板，符合的話保留它相鄰點的位置。圖5是當前點以及他的鄰接點的示意圖。圖5 點p的鄰接點基于組合模板的細化算法不需要匹配保留模板的操作。每個消去模板對應著一種情況，并且每個消去模板利用“&”和“|”操作來完成判斷當前點

7、是否要被保留。下面的8個條件式對應圖2中ah的8個消去模板。如果該點滿足消去模板以及消去條件，則消去此點。否則暴力此點。(q4=0 & q5=0 & q6=0 & q7=0) | (q5=1 & q6=1 & q12=0 & q13=0 & q14=0) (1)(q2=1 & q4=0 & q7=0 & q9=1 & q11=0) | (q2=0 & q9=0 & q12=0 & q13=0) (2)(q5=0 & q6=1 & q7=0 & q11=0) (

8、3)(q2=0 & q9=1 & q13=0 & q14=0) (4)(q8=1 & q10=0 & q13=0 & q14=0) | ( q8=0 & q10=1 & q12=0) (5)(q3=0 & q4=0 & q7=0 & q10=1) | (q3=1 & q7=0 & q10=0 & q11=0) |(q8=1 & q10=0 & q13=0 & q14=0) | (q8=0 & q10=1 & q13=0 & q14=0)

9、 (6) (q3=0 & q4=0 & q7=0 & q10=1 & q11=0) | ( q3=1 & q7=0 & q10=0 & q11=0) (7)p=1 (8) 其中，p是當前點，圖5顯示了q1q15。雖然目前，改進的opta算法只應用于指紋圖像的識別，文獻18。本文應用上述的公式和改進的opta來進行腦血管圖像骨架的提取。通過實驗發現，通過原opta算法細化的圖像有一些毛刺，因此不能用于腦動脈瘤的檢測。文獻1的效果更佳，但是細化速度不是很理想。盡管文獻2中的細化算法的速度有了明顯的提高，但細化血管過程中斷點容易產生。衡量了各種

10、因素，我們決定以組合模板的改進opta算法來實現腦血管骨架的提取。由此方法得到的血管骨架有很高的質量，同時，速度也得到了加強。.基于骨架樹的腦動脈瘤的檢測在通過細化腦血管圖像得到的骨架樹后，原本具有一定寬度的血管變成只有一個像素寬度的骨架，同時腦血管圖像變成了單像素寬度的曲線。通過提取骨架結構元素，腦動脈瘤的檢測就是基于骨架樹中分支元素的寬度。a. 骨架結構元素的提取1)關鍵點元素的提取關鍵點體現在骨架特征發生變化的地方，包括分叉點和端點。端點就是骨架樹的某部分的起始點，當前點p的8個鄰接點只有一個是骨架中的點，那么此點p就是端點，像圖6中的點a，c，d和f。分叉點就是骨架樹的不同部分的交點，

11、當前點p的8個鄰接點只有三個或者更多的點是骨架中的點，那么此點p就是交叉點，像圖6中的點b，e。圖6 骨架元素的表示2)分支元素的提取分支元素是骨架段，它連接著兩個關鍵點，并且不通過骨架中的第三個關鍵點。如果關鍵點不是端點，那么它叫做內部分支點，否則叫做外部分支點。本文中，我們討論的分支元素是外部分支點。分支元素的提取方法是從端點開始：先找到端點，跟蹤此點，直到下一個分叉處。從端點開始到分叉處結束的骨架元素即是分支元素。b. 基于分支元素的腦動脈瘤的檢測通過分析腦動脈瘤的形態得出結論：如何提取腦血管骨架的分支結構是檢測腦動脈瘤的關鍵。腦動脈瘤，毛刺和普通血管分別會使骨骼圖像出現三種分支結構。所

12、以腦動脈瘤可以通過從三種分支結構中判斷是否是由腦動脈瘤引起的分支檢測出來。在本文中，通過深度遍歷骨架樹，分支的像素寬度是檢測的基礎。具體步驟如下進行。(1) 從根部遍歷骨架樹，標記訪問過的像素；(2) 一旦遇到分叉點p，則按垂直方向逆時針訪問它8領域中的鄰接點，把沒有訪問的點放入棧中。(3) 從棧中獲取一個元素作為開始點，以上述方法繼續遍歷骨架樹中的像素，直到所有點都遍歷完。同時用變量s來計算從開始到結束所訪問的像素數。如果s大于閾值t1小于閾值t2，則曲線的位置就是腦動脈瘤的一部分，如果s小于t1，則認為是毛刺，s大于t2則認為是普通的血管。(4) 重復上述過程，直到棧空為止。則骨架樹就遍歷

13、完了。上述過程中，分支位置的檢測方法是以當前點為中心，檢查它的8鄰域中目標點和未被訪問的點數。根據經驗值，t1設置為8，t2設置為16，這樣在某種程度上就可以消去毛刺，同時可以消去對檢測腦動脈瘤的干擾。可以獲得最好的效果。.實驗與分析系統運行的硬件環境用的是cpu：p(r)4 2.8兆赫；內存：512m；顯卡：128m。開發環境是vc 6.0。腦血管dsa圖像的實驗數據是蘇州大學第一附屬醫院提供的符合dicom 3.0標準的圖像。通過運用開發軟件架構dicom，每一幅dsa圖像都被分成dsa圖像序列，保存為bmp格式。在實驗中，我們先對圖1(a)和圖1(b)原始圖像做二值化，然后運用改進的細化

14、算法來獲得圖像的骨架，最后利用基于骨架分支的腦動脈瘤檢測算法來檢測整個骨架圖。最后用方格標記疑似腦動脈瘤的區域。普通腦血管圖像的血管結構相對簡單，并且圖像邊緣相對平滑，如圖7(a)；圖7(b)中顯示的血管結構圖，由于圖像的復雜和模糊度導致了血管不平滑，且有噪音干擾。圖7 原始圖像二值化效果圖圖8是分支檢測和基于分支特征的腦動脈瘤檢測方法的最終結果圖。圖8 腦動脈瘤的檢測結果圖本文采用了基于改進了的組合模板的細化算法來檢測二值圖像的分支，它有效的避免了毛刺的出現。這是一種效果較好的算法，圖8是不同效果的對比，圖8(a)毛刺較少，圖8(b)毛刺較多。經過大量的實驗，發現，不理想的二值化效果以及噪聲

15、的影響和其他原因導致了容易出現毛刺。由于毛刺會出現在相同的分支結構中，因此，它大大影響了腦動脈瘤檢測的精度。如圖8所示，用方格標記的位置是檢測到的腦動脈瘤的位置。圖8(a)中的檢測效果很好，圖8(b)中檢測出的區域有兩處是錯誤的。本文中的基于腦動脈瘤骨架特征檢測的方法基本上可以定位出腦動脈瘤的位置。盡管基于分支長度的檢測會遇到干擾，最后導致出現不正確的檢測，但是腦動脈瘤檢測的意義是在于減少目標數量并為識別過程提供有用的信息。如何進行有效的二值化，為骨架提取提供基礎，同時減少毛刺對腦動脈瘤檢測的比利影響將是今后研究的重點。.結論本文分析了腦動脈瘤的形態特征，有關opta算法以及改進的算法的深入研

16、究，并且利用它們成功提取出了圖像的骨架。提出了一種基于骨架信息的腦動脈瘤檢測方法，它是通過分支結果元素長度來實現檢測的。實驗結果顯示，通過從骨架中提取分支元素后，用此方法可以檢測出腦動脈瘤的區域。此外，檢測效果還與腦血管分割效果和骨架的提取有關。怎樣克服這些缺點，提高檢測的成功率是今后工作的重點。聲明這次研究由中國自然科學基金會(60673092)以及江蘇省現代信息技術應用軟件工程研究中心no.sx200803贊助的。參考文獻1 feng xing-kui, li lin-yan, yan zu-quan, “a new thinning algorithm for fingerprint i

17、mage,” journal of image and graphics, 1999, 4(10):835-838.2 wang jia-long, guo cheng-an, “an improved image template thinning algorithm,” journal of image and graphics, 2004, 3(9):297-301.3 mei yuan, sun huai-jiang, xia de-shen, “an improved template-based rapid thinning algorithm,” journal of image

18、 and graphics, 2006, 11(9):1306-1311.4 tan tai-zhe, ning xin-bao, yin yi-long, “a method for singularity detection in fingerprint images,” journal of software, 2003, 14(6):1082-1088.5 liang guang-min, cai xue-jun, “improvement of opta algorithm and its application in fingerprint images thinning,” co

19、mputer engineering and design, 2006,27(23):4607-4608.6 zhang yu-jin, image engineering (ii): image analysis(second edition), beijing:tsinghua university press, 2005.7 xu gang-feng, wang ping, shen zhen-kang,“recognition of main-runway of airport based on skeleton,” infrared and laser engineering, 20

20、06,35(6):717-721.8 zhang jin-yang, sun mao-hang, “study on algorithm for skeleton features extraction of hand vein image,”journal of computer applications, 2007, 27(1):152-154.research on cerebral aneurysm detectionbased on opta algorithmabstractit is the key step of the cerebral aneurysm recognitio

21、n system to locate the cerebral aneurysm accurately and fast onto the image. a new detection method of cerebral aneurysm, which is based on the improved thinning algorithm, is proposed after analyzing the morphological characteristics of cerebral aneurysm fully in the paper. in this new detection me

22、thod, the improved opta algorithm is used to get the skeleton tree of blood vessel firstly, and then cerebral aneurysms are detected by searching the skeleton tree. after doing lots of experiments, the cerebral aneurysm can be detected well by using this new method, which provides a premise for cere

23、bral aneurysm recognition.index termsopta, thinning algorithm, cerebral aneurysm detection, template matchingi. introductioncerebral vascular disease, especially cerebral aneurysm is one of the key factors leading to disease and death in adults, which threaten the health and life of human badly. wit

24、h the development and the unceasing maturation of computer technology, cad(computeraided diagnosis) system resulting from the combination of information technology and medical imaging technology plays a more and more important role in detecting and treating cerebral vascular disease, and it has alre

25、ady become a research focus in medical imaging. the cerebral aneurysm usually was located in the bifurcation position of vessel, especially the cerebral artery circulus, and the reason is that the impact of blood flow has great influence on the bifurcation position. cerebral vascular image is simila

26、r to river network, and there exists artery and many other branch vessels. generally, vessel is approximately symmetric, whose two edge contours are approximately mutual parallel. but cerebral aneurysm is the projecting part of the vessel edge caused by lesion. the schematic diagram of cerebral aneu

27、rysm is showed in figure 1. from figure 1, the position marked by pane is cerebral aneurysm. the projecting part has appeared in the normal vessel and the approximately parallel of two edge contours is broken. the lesion site was manifested as obvious branch structure. so we can ascertain the lesion

28、 site of cerebral aneurysm by detecting the branch structure in vessel skeleton tree.figure 1. the schematic diagram of cerebral aneurysmin the cerebral aneurysm cad system based on dsa(digital subtracted angiography), it is the premise and important step of feature extraction and recognition to det

29、ect the position of cerebral aneurysm in dsa. this paper analyzes morphological characteristics of cerebral aneurysm, obtains the topological skeleton tree via the improved thinning algorithm, then does depth-first traversal search on skeleton tree, and lastly detects the position of cerebral aneury

30、sm.ii. opta algorithmopta(one-pass thinning algorithm) is a typical template-based image thinning algorithm, whose core is thinning processing by the application of elimination template and preservation template. opta is an iterative process. if the current point satisfies the elimination template a

31、nd doesn't satisfy preservation template, it will be eliminated. otherwise, it will be preserved. the original image is traversalled continuously until no point satisfies the above condition. the main improvement upon opta is proposing new elimination template and preservation template according

32、 to the defect of thinning effect and thinning speed of original algorithm. among them, the most typical documents are 13. it is found by the authors of document 1 that original opta has the disadvantages of incomplete thinning, more burr and inadequate smooth. much improvement has been undergone on

33、 elimination template and preservation template in the improved algorithm. figure 2 and figure 3 are the improved elimination template and preservation template respectively, among which shadow pane is current point.figure 2. the elimination template of document 1figure 3. the preservation template

34、of document 1because the condition for preservation template in the algorithm of document 1 is too loose, the effect of right oblique line produces easily while analyzing the images, which made iteration times increase and the speed slow. therefore, new preservation template was proposed on the basi

35、s of document 1 and they were increased to 9. from figure 4, the condition of preservation template becomes more strictly, which solved the effect of right oblique line well, and the speed has been improved immensely.figure 4. the preservation template of document 2with the development to the depth,

36、 mei yuan and other authors found that the effect of right oblique line was solved well by the algorithm of document 2 and the speed has been improved immensely. but because of its enhanced preservation condition, the breakpoints appeared. as a result, the topology and connectivity of original image

37、 has been destroyed and the thinning effect decreased. on the basis of the above analysis, mei yuan and other authors proposed the concept of composition template, which took advantage of the elimination template of document 1, abandoned the preservation template and combined the judgment whether th

38、e point satisfied the elimination template will be preserved with the situation of its neighborhood point. figure 5 is the schematic diagram about the neighborhood of current point.figure 5. the neighborhood diagram of point pthe thinning algorithm based on improved composition template doesn't

39、need matching operation for preserve template. every elimination template corresponds to one case of every neighborhood points' pixel value, and it uses logical operation “&” and “|” to complete the judgment whether current point will be preserved. the following 8 conditions correspond to 8e

40、limination template marked with ah in figure2. if it satisfies elimination template and corresponding elimination condition, this point will be deleted. otherwise, it will be preserved.(q4=0 & q5=0 & q6=0 & q7=0) | (q5=1 & q6=1 & q12=0 & q13=0 & q14=0) (1)(q2=1 & q4=0

41、 & q7=0 & q9=1 & q11=0) | (q2=0 & q9=0 & q12=0 & q13=0) (2)(q5=0 & q6=1 & q7=0 & q11=0) (3)(q2=0 & q9=1 & q13=0 & q14=0) (4)(q8=1 & q10=0 & q13=0 & q14=0) | ( q8=0 & q10=1 & q12=0) (5)(q3=0 & q4=0 & q7=0 & q10=1) | (q3=1

42、 & q7=0 & q10=0 & q11=0) |(q8=1 & q10=0 & q13=0 & q14=0) | (q8=0 & q10=1 & q13=0 & q14=0) (6) (q3=0 & q4=0 & q7=0 & q10=1 & q11=0) | ( q3=1 & q7=0 & q10=0 & q11=0) (7)p=1 (8) among them, p is the current point and figure 5 shows q115. t

43、hough at present, improved opta is only applied to the thinning of fingerprint image 48. this paper applied the above and improved opta to skeleton extraction of cerebral vascular image. by many experiments, we found that the burr of vascular skeleton extracted by original opta is a bit more, so it

44、cannot be used in the detection of cerebral aneurysm. the effect of document 1 is much better, but the thinning speed is not ideal. though the thinning speed of document 2 wasincreased significantly, the breakpoint phenomenon produces easily while thinning vessel. through weighing various factors, w

45、e determine that our work of extracting cerebral vascular skeleton was carried out on the basis of improved opta using composition template. the vascular skeleton gained by this algorithm has high quality; meanwhile, the speed is also enhanced.iii. detection of cerebral aneurysm based on skeleton tr

46、eeafter obtaining the skeleton tree by thinning the cerebral vascular image, a certain width of the blood vessel becomes only a pixel width of the skeleton and cerebral vascular image becomes a curve of single pixel. through the extraction of skeleton structure elements, thedetection of cerebral ane

47、urysm is based on the length of branch element on skeleton tree.a. extraction of skeleton structure elements1) extraction of key point elementkey points present to the places where dramatic changes have been taken place in skeleton characteristics, which includes endpoint and bifurcation. endpoint i

48、s the starting point on the part of skeleton tree, and p is endpoint if there has only one skeleton point in the eight neighborhood of the current point p, just as a,c,d and f shown in figure 6. bifurcation is the converging point of different parts of skeleton tree, and p is bifurcation if there ha

49、s three or more skeleton points in the eight neighborhood of the current point p, just as b and eshown in figure 6.figure 6. skeleton structure elements representation2) extraction of branch elementbranch element is the skeleton segment, which connects two key points and does not pass by the third k

50、ey point of the skeleton. if the key points are not endpoint, it is called inner branch, otherwise, outer branch. in this paper, branch element we discussed is outer branch. the extraction method of branch element starts with endpoint: find a endpoint firstly, and track italong until the next point

51、is bifurcation. the skeleton segment which starts with endpoint and ends with bifurcation is the branch element. b. detection of cerebral aneurysm based on branch elementa conclusion gained by analyzing the morphology of cerebral aneurysm: how to detect the branch structure of cerebral vascular skel

52、eton is the key to the detection of cerebral aneurysm. there are three kinds of branch structure of skeleton map which are caused by cerebral aneurysm, burr and normal blood vessels respectively. so cerebral aneurysm can be detected from the three kinds of branch structures by judging branch structu

53、re caused by cerebral aneurysm. in this paper, by doing depth-first traversal search on skeleton tree, the pixel length of branches will be the basis of detection.the specific steps was conducted as follows.(1) traverse the entire skeleton tree from the root of skeleton tree, and mark the pixels whi

54、ch have been visited;(2) once encountering the bifurcation point p, visit each adjacent point of its 8 neighborhood in anticlockwise order from the vertical direction and put the points which are not visited into stack;(3) retrieve an element from the stack as a beginning point, continue to traverse

55、 pixels of skeleton tree with the above method, until there is no point that can be visited. simultaneously use variable s to count the pixels which have been visited from the beginning point to the end. if the s is more than threshold t1 and less than threshold t2, the location of the curve is the

56、part of cerebral aneurysm, and it can be considered as burr if s is less than t1, normal blood vessels branch if s is more than t2;(4) repeat the above process until the stack is empty. then the cerebral vascular skeleton tree traversal is finished.during the above process, the extraction method of

57、bifurcation position is central with this point to examine the number of 8 neighborhood pixel point that is the objective and wasn't visited. according to empirical value, t1 is set to 8 and t2 is set to 16, which can eliminate the burr to some extent and the interference to the detection of cer

58、ebral aneurysm from normal vessel branch. this can obtain the best effect.iv. experiments and analysisthe hardware environment used in the experiment is cpu: p (r) 4 2.8ghz; memory: 512 m; display card: 128 m. the development environment is vc 6.0. experimental data of cerebral vascular dsa images, whose format accords with dicom 3.0 standard, are provided by the first affiliated hospital of suzhou university. by using dicom software developed by ourinstitute, each dsa imag