丘赟立,蔣先剛,范德營
(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌 330013)
多種搜索算法在醫(yī)學(xué)圖片彩色遷移上的應(yīng)用與分析
丘赟立,蔣先剛,范德營
(華東交通大學(xué)基礎(chǔ)科學(xué)學(xué)院,江西南昌 330013)
通過對(duì)真彩圖像與灰色MRI(核磁共振圖像)切片在亮度及紋理等特征上進(jìn)行配準(zhǔn)而實(shí)現(xiàn)灰度MRI切片的彩色化,可以得到有效的符合真實(shí)人體器官組織的真彩仿真圖片。對(duì)多種搜索算法如窮舉法、隨機(jī)法、粒子群算法和遺傳算法與點(diǎn)鄰域亮度分布紋理和局部顏色結(jié)構(gòu)分布相結(jié)合并應(yīng)用于Welsh圖像彩色化的算法進(jìn)行研究和分析。著重分析和修正遺傳算法在Welsh彩色化上的應(yīng)用。該算法將源圖像塊和目標(biāo)圖像塊的亮度特征以及紋理特征構(gòu)成適應(yīng)度函數(shù),并依據(jù)代數(shù)的增加而降低交叉和變異的概率以減少進(jìn)化后期的跳躍性。其搜索的彩色特征種群經(jīng)過選擇、交叉和變異等操作后逐代進(jìn)化而得到最終彩色化圖像點(diǎn)。最終彩色化的MRI切片的三維重構(gòu)模型能多層次清晰地反映器官組織的分布和構(gòu)造。
彩色模型;顏色遷移;遺傳算法;適應(yīng)度函數(shù)
在現(xiàn)實(shí)生活中,人體的器官組織都是三維彩色實(shí)體,而醫(yī)學(xué)上常用的成像技術(shù)所產(chǎn)生的圖像都是灰色或區(qū)域性偽彩色。如果希望通過計(jì)算機(jī)仿真來協(xié)助手術(shù)的進(jìn)行,就不能只靠直接生成的灰色切片圖像,而必須將這些切片轉(zhuǎn)換成彩色圖像并由此構(gòu)造相應(yīng)的三維仿真模型。在灰色圖像中,人體器官的不同組織也有可能呈現(xiàn)相同的灰度。如果想要得到符合人體的彩色圖像,就必須在真彩圖像和灰色圖像間建立起亮度、紋理和幾何的映射關(guān)系,并借此映射關(guān)系將真彩圖像中的顏色遷移到灰色圖像中。最后對(duì)彩色化的灰色圖像進(jìn)行三維重構(gòu)。這樣的三維模型具有多層次性,并且能對(duì)彩色遷移算法進(jìn)行校驗(yàn)和修正。
為了將彩色圖像中的顏色遷移至灰色圖像中,首先要為灰色圖像中的每個(gè)像素點(diǎn)尋找與彩色圖像相符合的像素點(diǎn)。對(duì)兩幅圖像的點(diǎn)進(jìn)行配準(zhǔn)的特征和方法有許多種,采用點(diǎn)鄰域和彩色分布的特征,以及窮舉法、隨機(jī)法、遺傳算法和粒子群算法等搜索方法,還對(duì)不同的特征和不同的搜索算法進(jìn)行了組合、對(duì)比和分析。
灰色圖像的彩色化技術(shù)主要有兩種,包括偽彩色法以及顏色遷移。通常情況下,偽彩色的實(shí)現(xiàn)方法有兩種,分別是強(qiáng)度分層和灰度級(jí)-彩色變換。前者把灰色圖像的灰度由原來的256個(gè)等級(jí)重新分為N個(gè)區(qū)間Ri,i=1,2,…,N,并給每個(gè)區(qū)間Ri定義一種顏色,由此得到一幅基于原來灰色圖像的偽彩色圖像;后者在偽彩色的顏色增強(qiáng)上比前者更為有效。而彩色遷移是在真彩圖像和灰色圖像間建立映射關(guān)系并將真彩圖像中的顏色遷移至灰色圖像中的技術(shù)。為了合理地將顏色從真彩圖像中遷移至灰色圖像中,要為灰色圖像中每一個(gè)像素點(diǎn)在彩色圖像中尋找一個(gè)亮度等特征最相近的像素點(diǎn),然后才將相應(yīng)的顏色遷移至灰色圖像。為了從圖片中提取亮度和紋理等特征,本文先將圖片從RGB空間中轉(zhuǎn)換到Lαβ空間,在顏色遷移完畢之后,再從Lαβ空間轉(zhuǎn)換到RGB空間。
本文所使用的真彩圖像來自美國國家醫(yī)學(xué)圖書館。這些真彩圖像是一系列由數(shù)碼攝像而得到的人體間隔0.33~1.00 nm的二維真彩圖像,并且能夠真實(shí)有效地反映人體器官在各個(gè)切面的分布情況。本文在對(duì)真彩切片和灰色圖片在亮度和紋理特征的配準(zhǔn)的基礎(chǔ)上進(jìn)行顏色遷移,主要步驟包括遍歷灰色圖像中每個(gè)像素點(diǎn),并為灰色圖像中每個(gè)像素點(diǎn)對(duì)彩色圖像的像素塊逐個(gè)掃描并選擇最匹配的像素塊,最后將相應(yīng)的像素塊的顏色遷移至灰色圖像中。圖1(a)是人體腿部切片真彩圖像;圖1(b)是由MRI(核磁共振圖像)掃描得到的腿部切片灰色圖像,由于MRI切片和人體真彩圖像的成像效果不一樣,前者跟被檢對(duì)象的密度密切相關(guān),后者則跟血液滲透程度和人體組織的自然構(gòu)成成份密切相關(guān),如脂肪在MRI切片中亮度低而在真彩圖像中亮度較高,所以要先將它們?cè)诹炼确植忌线M(jìn)行映射變換;圖1(c)是MRI切片在灰度拉伸變換后得到的圖像;圖1(d)為對(duì)圖1(c)進(jìn)行顏色遷移得到的圖像。
圖1 一張人體腿部灰度圖片彩色化的過程圖Fig.1 Color transfer process of a grey image of a human leg
本文采用的方法是Welsh彩色化算法[1-2],并著重研究和修正遺傳算法[3-4]以應(yīng)用于Welsh彩色化算法。Welsh彩色化算法的原理是輸入一幅需要彩色化的灰色圖像和一幅彩色圖像;將兩幅圖像從RGB顏色空間轉(zhuǎn)換到各分量和亮度與顏色參數(shù)間相關(guān)性較小的Lαβ[5-6]顏色空間,該空間由Reinhard等人在1998年提出,然后利用遺傳算法對(duì)彩色圖像和灰色圖像的像素塊的亮度和紋理特征進(jìn)行配準(zhǔn),將匹配的像素塊的顏色遷移至灰色圖像中,最后再將圖像從Lαβ空間轉(zhuǎn)換到RGB空間,得到彩色化后的圖像。
下面將介紹從RGB顏色空間轉(zhuǎn)換到Lαβ顏色空間的過程。
1)將RGB顏色空間轉(zhuǎn)換到基于人眼視覺特性定義的LMS顏色空間
式中:LLMS為長波通道;M為中波通道;S為短波通道。
2)將LMS空間轉(zhuǎn)換到對(duì)數(shù)空間,以消除空間的歪斜性(Skew)3
)將LMS空間轉(zhuǎn)換到Lαβ空間
式中:LLαβ是非彩色的亮度通道,α和β分別表示顏色的紅綠通道和黃藍(lán)通道。
將Lαβ顏色空間轉(zhuǎn)換到RGB顏色空間則可以通過上述方法的逆過程方便得到。
遺傳算法是一種模擬生物進(jìn)化理論的自然選擇和遺傳機(jī)理的進(jìn)化過程的計(jì)算智能模型,通過模擬自然界的進(jìn)化過程而得到的搜索最優(yōu)解的方法。該算法首先生成初始種群,用設(shè)計(jì)好的適應(yīng)函數(shù)對(duì)每一代種群的個(gè)體進(jìn)行評(píng)價(jià),適應(yīng)函數(shù)是遺傳算法的擇優(yōu)標(biāo)準(zhǔn),然后按照一定的概率執(zhí)行選擇操作、交叉操作和變異操作來產(chǎn)生新的種群,種群經(jīng)過若干代進(jìn)化后使得算法收斂,得到問題的最優(yōu)解。遺傳算法主要考慮的問題包括初始種群的產(chǎn)生、適應(yīng)函數(shù)的確定、遺傳算子(選擇算子、交叉算子和變異算子)的選取。遺傳算法的匹配點(diǎn)搜索方式包括2種,分別是在整幅彩色圖像中的全局搜索和在隨機(jī)選取的N個(gè)點(diǎn)中的局部搜索。
將遺傳算法應(yīng)用到對(duì)彩色匹配點(diǎn)的搜索中能夠快速有效地得到最佳的顏色值。遺傳算法的初始種群的規(guī)模和分布對(duì)該算法的性能和收斂情況能產(chǎn)生很大的影響,初始種群在空間的均勻分布既可以提高算法的性能又能夠保證種群的多樣性以便得到全局最優(yōu)解。設(shè)置該算法的初始的代數(shù)計(jì)數(shù)器t=0,最大的進(jìn)化代數(shù)T=10,并隨機(jī)生成M=200個(gè)個(gè)體作為初始種群。該算法的目的就是保留每一代中最優(yōu)的個(gè)體,而其他個(gè)體則參與交叉和變異過程并由此產(chǎn)生新的一代??紤]到搜索的有序性,本文將整幅彩色圖像分為n×n個(gè)子塊,并在每個(gè)子塊里產(chǎn)生一個(gè)初始的個(gè)體。與一般遺傳算法不同的地方是使用二進(jìn)制格雷碼代替普通的二進(jìn)制編碼以減少普通二進(jìn)制編碼在基因變化的時(shí)候造成坐標(biāo)的突變。
選擇操作是將選擇算子應(yīng)用到種群中,其目的是在種群中保留優(yōu)秀的個(gè)體。選擇算子采用賭輪選擇法,即把適應(yīng)度反序排列的個(gè)體按累積適應(yīng)度篩選。交叉操作是將交叉算子應(yīng)用到種群中,其目的是使得新一代群體繼承上一代的群體。使用單點(diǎn)交叉算子,交叉概率設(shè)為0.5。隨機(jī)生成數(shù)字,若小于交叉概率,則執(zhí)行交叉操作。為了使個(gè)體變化程度不致太大而偏離最優(yōu)解,使用的交叉算子只在低位上發(fā)生變化。變異操作是將變異算子應(yīng)用到種群中,其目的是防止算法陷入局部最優(yōu)解。將變異概率設(shè)為0.005,即當(dāng)隨機(jī)數(shù)小于0.005時(shí),對(duì)個(gè)體執(zhí)行變異操作。為了防止群體的適應(yīng)度在進(jìn)化后期出現(xiàn)太大的跳躍性,對(duì)交叉概率和變異概率按公式(4)進(jìn)行適當(dāng)?shù)恼{(diào)整。
式中:pt為修正后的交叉或變異概率;p0為初始的交叉或變異概率;t為進(jìn)化代數(shù);cp=0.9為修正系數(shù)。
當(dāng)群體的進(jìn)化代數(shù)達(dá)到預(yù)先設(shè)定的最大代數(shù)或適應(yīng)度值達(dá)到指定程度的時(shí)候,算法終止進(jìn)化,并將適應(yīng)度最高的個(gè)體相應(yīng)的顏色值輸出。
適應(yīng)函數(shù)必須能夠有效地定量地反映每個(gè)個(gè)體在整個(gè)進(jìn)化過程中的適應(yīng)程度,在本文的研究中就是反映灰色圖像和彩色圖像的像素點(diǎn)在某一局部特征[7-8]的匹配相似程度。點(diǎn)鄰域分布特征采用亮度和紋理來衡量,以減小顏色在匹配的過程中產(chǎn)生的誤差。
本文對(duì)點(diǎn)鄰域分布的亮度特征定義為
式中:ΔL為亮度偏差;l0為彩色圖像中某像素點(diǎn)的鄰域的亮度平均值,σ0為彩色圖像中某像素點(diǎn)的鄰域的亮度標(biāo)準(zhǔn)差,l1為灰色圖像中某像素點(diǎn)的鄰域的亮度平均值,σ1為灰色圖像中某像素點(diǎn)的鄰域的亮度標(biāo)準(zhǔn)差,λ1和λ2分別是兩幅圖像的亮度均值偏差和標(biāo)準(zhǔn)差偏差的權(quán)重。而紋理特征則采用k=0.000 1的均勻性紋理特征。式中:F為適應(yīng)度;α1為亮度參數(shù)的權(quán)重,α2為紋理參數(shù)的權(quán)重,且α1+α2=1。
考慮到匹配的彩色點(diǎn)往往與彩色源圖上的點(diǎn)的彩色局部分布具有一定的類似性而不必用窮舉的方法進(jìn)行匹配搜索,且這種基于彩色局部分布樣本的方法[9]將更適應(yīng)于快速的彩色遷移的匹配搜索。由于轉(zhuǎn)換后的彩色圖片的匹配首先從待匹配的點(diǎn)的左上角的點(diǎn)向右下進(jìn)行,對(duì)應(yīng)于當(dāng)前點(diǎn)的轉(zhuǎn)換后彩色圖片的左上部分是已彩色化的區(qū)域,這個(gè)點(diǎn)P的左、上鄰域部分A0,B0,C0,D0的彩色分布與彩色源圖的一些區(qū)域具有類似性,故從對(duì)應(yīng)于P點(diǎn)的彩色源圖像的點(diǎn)的右下角的點(diǎn)相鄰的點(diǎn)A開始進(jìn)行搜索,如果對(duì)應(yīng)的局部結(jié)構(gòu)點(diǎn)的相應(yīng)適應(yīng)度(彩色值)小于一個(gè)閾值,則為彩色結(jié)構(gòu)類似的搜索結(jié)果,否則依次搜索待匹配的點(diǎn)的上面,右上角,和左邊的點(diǎn)。如圖2所示,該方法首先根據(jù)A0和P的相對(duì)位置關(guān)系選取A2并計(jì)算A2的適應(yīng)度,如果該適應(yīng)度值小于指定閾值,則P的匹配目標(biāo)點(diǎn)為A2。否則,依次判斷B2,C2,D2的適應(yīng)度,如果滿足條件,則這個(gè)點(diǎn)選為匹配目標(biāo)點(diǎn),如果A2,B2,C2,D2的適應(yīng)度值都大于指定的閾值,則要進(jìn)行全局搜索或者隨機(jī)搜索。
用遺傳算法應(yīng)用于隨機(jī)選取的N個(gè)點(diǎn)彩色適配值的搜索將比隨機(jī)選取的N個(gè)點(diǎn)的窮舉方式搜索的運(yùn)算效率高,通過在彩色源圖上隨機(jī)選擇N=300點(diǎn),將這300個(gè)點(diǎn)以適應(yīng)度綜合函數(shù)公式(5)計(jì)算并排序,基因編碼選擇這個(gè)序號(hào),彩色源圖像與灰色圖像的點(diǎn)適應(yīng)度差越小表示它們?cè)狡ヅ?。基因組群體個(gè)數(shù)為10,進(jìn)化代數(shù)為6,交叉概率仍然取為0.5,變異率仍然選擇為0.005。也就是在遺傳算法循環(huán)計(jì)算的每代中從這300個(gè)顏色中選擇10個(gè)彩色得到這一代的最優(yōu)值,下一代的適配值的選取是有序有理的選擇而不是窮舉和隨機(jī)的,同時(shí)每個(gè)遺傳算法的運(yùn)算次數(shù)是被彩色化的灰色圖像點(diǎn)的個(gè)數(shù),故隨機(jī)定點(diǎn)選取與遺傳算法相結(jié)合將有效提高彩色遷移的運(yùn)算效率。
圖2 基于彩色局部分布搜索匹配點(diǎn)的方法Fig.2 Searching method based on local color distribution
實(shí)驗(yàn)系統(tǒng)中的開發(fā)平臺(tái)采用Delphi 7,計(jì)算機(jī)的硬件運(yùn)行環(huán)境是intel酷睿2雙核p8700,2.53 GHz的CPU,4 GB的內(nèi)存。顏色遷移實(shí)驗(yàn)圖片的分辨率為256×256,彩色遷移算法的效率比較實(shí)驗(yàn)的匹配特征包括用匹配點(diǎn)的亮度的鄰域的紋理統(tǒng)計(jì)和用已搜索彩色分布樣本兩種,搜索方法包括窮舉,彩色點(diǎn)隨機(jī)選擇,粒子群算法和遺傳算法和這些方法的組合。這些特征和搜索方法的比較都用Welsh算法的全局彩色化的算法進(jìn)行。
通過實(shí)驗(yàn)可知,在灰色圖像彩色化的算法中利用彩色分布特征選取待上色點(diǎn)的匹配目標(biāo)點(diǎn),不僅能保證算法的有效性,還可以大幅度提高算法的效率。窮舉算法所需要的時(shí)間最長,隨機(jī)算法是通過在彩色源圖上隨機(jī)采樣N個(gè)點(diǎn)而代表彩色源圖的彩色種類,在這N個(gè)點(diǎn)中選取最佳適應(yīng)度點(diǎn)的顏色值,其顏色傳遞的真實(shí)性和耗時(shí)取決于采樣點(diǎn)的多少,本實(shí)驗(yàn)中取隨機(jī)采樣點(diǎn)數(shù)N=300。而智能算法中包括粒子群算法和遺傳算法,其效率更高。粒子群算法也屬于全局優(yōu)化方法,它沒有遺傳操作如交叉和變異,而是根據(jù)自己的速度來決定搜索。對(duì)不同特征和搜索算法的比較中可知,隨機(jī)取點(diǎn)搜索算法結(jié)合遺傳算法的搜索效率是最高的。而且由于算法是用Delphi實(shí)現(xiàn)的,跟國內(nèi)外大部分利用Matlab進(jìn)行的研究相比,具有更強(qiáng)的靈活性和更高的效率。結(jié)合不同彩色分布特征和不同的搜索算法得到如表1所示的顏色遷移的效率比較。
為了顯示基于灰色切片和彩色切片的不同的三維重構(gòu)比較效果,在灰度切片重構(gòu)的直接體繪制中采用亮度傳遞函數(shù)傳遞,而在彩色切片重構(gòu)中采用與彩色向量及梯度相關(guān)的傳遞函數(shù)為
表1 基于不同特征和搜索方法的顏色遷移的效率比較Tab.1 Efficiency comparison of color transfer based on different features and search method
式中:T是一個(gè)控制閾值;ω是考慮顏色的梯度的權(quán)衡的一個(gè)調(diào)節(jié)參數(shù);c和g表示點(diǎn)的顏色向量和梯度;光學(xué)模型中傳遞函數(shù)o表達(dá)為數(shù)據(jù)場中的一點(diǎn)的顏色和梯度等對(duì)重構(gòu)模型的影響程度。
圖3(a)是基于灰度切片的重構(gòu)模型,圖3(b)是基于顏色遷移后的強(qiáng)調(diào)紅黃色和灰白色偏肌肉和骨結(jié)構(gòu)彩色要素的重構(gòu)模型,圖3(c)是基于顏色遷移后的強(qiáng)調(diào)灰白色偏骨質(zhì)的彩色要素的重構(gòu)模型,由此可見彩色切片在顏色向量和梯度值取不同權(quán)重的條件下更能多層次、多選擇地反映人體組織器官的客觀構(gòu)造和人們所需的器官三維細(xì)節(jié)。
圖3 基于灰色和強(qiáng)調(diào)不同彩色要素切片的三維重構(gòu)效果圖Fig.3 Reconstructed 3D color model of slices based on grey and other colors
國內(nèi)外有許多關(guān)于遺傳算法的文章,但大部分都是由Matlab實(shí)現(xiàn)的,許多參數(shù)是不可調(diào)的,算法的實(shí)現(xiàn)和調(diào)用方式也不能修改,而且沒有應(yīng)用到醫(yī)學(xué)研究上。本文的原創(chuàng)性主要體現(xiàn)在實(shí)驗(yàn)工程是由Delphi編碼實(shí)現(xiàn)的,而且跟醫(yī)學(xué)研究緊密結(jié)合。實(shí)驗(yàn)工程中的每一個(gè)算法的參數(shù)都是可調(diào)的,而且相應(yīng)的實(shí)現(xiàn)和調(diào)用方式也可以根據(jù)實(shí)際需要進(jìn)行相應(yīng)的修改。本文將遺傳算法引入圖像彩色化中,利用圖像塊的亮度和紋理特征值構(gòu)成的適應(yīng)度函數(shù)并對(duì)此進(jìn)行匹配顏色搜索,進(jìn)行顏色遷移后得到彩色化的圖像,在匹配方法的選擇上,隨機(jī)選擇N個(gè)樣本點(diǎn)比窮舉方法明顯提高了10倍左右的搜索效率,且基本含蓋所有的匹配彩色總類,采用粒子群算法的彩色遷移速度是隨機(jī)匹配算法的3倍左右,粒子群算法在一定程度上是反映了遺傳算法的思想,而隨機(jī)匹配算法是在有限彩色分群基礎(chǔ)上的窮舉方法,如果用遺傳算法求解隨機(jī)匹配算法中的最優(yōu)值,其匹配顏色搜索的速度是最快的,它將是粒子群算法的1倍左右,進(jìn)一步的研究將放在粒子群算法和遺傳算法組合求解匹配顏色搜索上,在這些彩色仿真切片的基礎(chǔ)上,通過彩色向量和梯度相關(guān)的傳遞函數(shù)得到方便可調(diào)的三維模型,并使得上色后的醫(yī)學(xué)器官的組織在顏色和空間分布上的連續(xù)性和自然性。
[1]陳倩.一種改進(jìn)的Welsh灰度圖像彩色化算法[J].武漢理工大學(xué)學(xué)報(bào),2009,31(22):151-153.
[2]LIU X P,WAN L,LIN S,et al.Intrinsic colorization[J].ACM Trans on Graphics,2008,27(5):1521-1529.
[3]牛曉霞,胡正平,劉博.競爭選擇多彩色圖像自適應(yīng)顏色遷移算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,19(1):119-200.
[4] KOZA J R.Genetic programming:on the programming of computers by means of natural selection[M].Cambridge,USA:MIT Press,1992:45-49.
[5] REINHARD E,ASHIKHMIN M.Color transfer between images[J].IEEE Computer Graphics and Applications,2001,21(5):34-40.
[6]TAMURA H,MORI S,YAMAWAKI T.Textural features corresponding to visual perception[J].IEEE Trans on System Man and Cybernetics,1978,8(6):460-472.
[7]吳曉燕,劉希玉,徐慶.基于改進(jìn)遺傳算法的分形圖像編碼[J].計(jì)算機(jī)工程,2010,36(5):205-206.
[8]朱黎博,孫韶媛,谷小婧.基于彩色擴(kuò)散與彩色傳遞的圖像著色算法[J].中國圖像圖形學(xué)報(bào),2010,15(2):200-205.
[9]李建明,葉飛,于守秋.一種快速灰度圖像彩色化算法[J].中國圖象圖形學(xué)報(bào),2007,12(3),536-537.
Application andAnalysis of Multi-searchingAlgorithms to Color Transter between Medical Images
Qiu Yunli,Jiang Xiangang,F(xiàn)an Deying
(School of Basic Sciences,East China Jiangtong University,Nanchang 330013,China)
This paper researches transferring a gray MRI slice into a colorful one that is valid and matches the human organs through registering the features of brightness and textures between the true colorful and the gray images.This paper probes a Welsh color transfer algorithm based on the combination of several searching methods,and the features of brightness within the neighborhood of a pixel and local color distribution.It particularly analyzes and modifies GA to adapt to the Welsh color transfer algorithm.This method will use the brightness and texture features of source and target images as the fitness function,and decrease the probability of crossover and mutation when the population evolves to avoid the mutation of the fitness of the population in later stage of evolution.The population which is used for searching by color features evolves through selection,crossover and mutation to get the fittest individual.3D color model reconstructed from the colorized slices can clearly reveal multi-level structure and distribution of human organs.
color model;color transfer;genetic algorithm;fitness function
TP391.41
A
1005-0523(2012)03-0061-06
2012-02-21
丘赟立(1987-),男,碩士研究生,主要研究方向?yàn)閿?shù)字圖像處理與三維重構(gòu)。