徐浩誠 劉利軍 黃青松

摘 要： 將分層切割的醫(yī)學(xué)圖片緩存到離用戶最近的代理服務(wù)器上能夠減少網(wǎng)絡(luò)的寬帶消耗、減輕服務(wù)器的負(fù)載。基于醫(yī)學(xué)圖像的自適應(yīng)分層切割原理，結(jié)合代理服務(wù)器存在的緩存替代問題，通過對問題進(jìn)行建模分析，論證了醫(yī)學(xué)圖像分層切割圖片的有用性并依此提出DSGC緩存替代策略。同時在仿真實(shí)驗(yàn)中證明其性能優(yōu)于某些傳統(tǒng)的緩存替代算法。

關(guān)鍵詞： 醫(yī)學(xué)圖像自適應(yīng)顯示； 動態(tài)緩存； DICOM醫(yī)學(xué)圖像； 分層切割

中圖分類號： TN911.73?34 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2016）08?0072?04

Cache replacement strategy for medical image adaptive layered cutting in proxy server

XU Haocheng， LIU Lijun， HUANG Qingsong

（Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming 650500， China）

Abstract： To cache the layered cutting medical images into the nearest proxy server from the users can reduce the network bandwidth consumption and server load. In combination with the cache replacement problem existing in proxy server and the modeling analysis of the problem， the effectiveness of the layered cutting picture of medical image is verified based on adaptive layered cutting principle of medical image， and based on the verification， the DSGC cache replacement strategy is proposed. The simulation experiment results prove that its performance is better than that of the traditional cache replacement algorithms.

Keywords： medical image adaptive display； dynamic cache； DICOM medical image； layered cutting

0 引 言

近年來，隨著醫(yī)學(xué)影像成像設(shè)備的高速發(fā)展（X射線、CT、超聲、MR等），醫(yī)學(xué)影像也已經(jīng)逐漸發(fā)展成為一門集診斷、成像等為一體的與計(jì)算機(jī)技術(shù)密切相關(guān)的綜合學(xué)科[1]。符合DICOM標(biāo)準(zhǔn)的醫(yī)學(xué)影像設(shè)備需要保證在大數(shù)據(jù)量、實(shí)時性強(qiáng)、結(jié)構(gòu)化較低的條件下通過PACS系統(tǒng)為醫(yī)生提供高效率的圖像存取和使用服務(wù)，這就使得醫(yī)學(xué)影像的高效傳輸成為重要的問題[2]。

現(xiàn)有的PACS系統(tǒng)中傳輸?shù)脑坚t(yī)學(xué)影像圖像文件格式主要為DICOM（Digital Imaging and Communications in Medicine，醫(yī)學(xué)數(shù)字成像和通信）文件格式，而DICOM文件格式的圖像數(shù)據(jù)動態(tài)范圍過大并且大部分均超出了通用顯示器的動態(tài)顯示范圍，很難一次在通用的顯示器屏幕上將所有的圖像細(xì)節(jié)都顯示出來[3]。不僅如此，互聯(lián)網(wǎng)應(yīng)用的快速增長導(dǎo)致網(wǎng)絡(luò)擁塞和服務(wù)器超載等問題的出現(xiàn)[4]，使得DICOM文件對于代理服務(wù)器的緩存性能提出了越來越高的要求。

目前大多數(shù)DICOM文件是以一個整體進(jìn)行緩存，隨著數(shù)據(jù)量的不斷增加可能會對服務(wù)器造成一定的負(fù)載并影響PACS系統(tǒng)的整體性能[5]。在此注意到一個DICOM文件中的醫(yī)學(xué)圖像對于用戶來說并不都存在使用價值，用戶的瀏覽可能只針對圖像的某一部分進(jìn)行操作，即DICOM文件中的醫(yī)學(xué)圖像存在一定的特殊性：醫(yī)生在查看一組腦部CT圖像時并沒有完全關(guān)注整個腦部的圖像而是重點(diǎn)關(guān)注了腦部CT圖像出現(xiàn)病變的部位。本文依據(jù)此特點(diǎn)，借鑒文獻(xiàn)[6]中提出的：GIS瓦片模式切圖算法對地理影響數(shù)據(jù)分割存儲、按需傳輸?shù)乃枷?，移植醫(yī)學(xué)圖像分層切割的原理到代理服務(wù)器的緩存置換策略中。通過對比傳統(tǒng)的經(jīng)典緩存算法自主改進(jìn)緩存置換策略，提出了動態(tài)策略計(jì)數(shù)（Dynamic Stratey Generation Count，DSGC）算法，在保證醫(yī)學(xué)影像不失真的前提下，使用代理服務(wù)器對DICOM文件中的醫(yī)學(xué)圖像進(jìn)行自適應(yīng)的動態(tài)緩存置換。經(jīng)過實(shí)驗(yàn)證明采用自適應(yīng)的分層切割方法有效地將用戶請求DICOM圖像準(zhǔn)確率提高了49%。DSGC算法相對于LRU?K，LFU等算法也提高了平均4.8%和3.7%的緩存命中率，并且DSGC算法在結(jié)合了醫(yī)學(xué)影像自適應(yīng)分層切割方法后更進(jìn)一步提升了8.5%的緩存命中率。

1 DICOM文件分層傳輸與緩存研究

DICOM圖像數(shù)據(jù)源的數(shù)據(jù)量巨大是其最大特點(diǎn)。醫(yī)院每天產(chǎn)生的圖像和信息數(shù)據(jù)量從幾十MB到幾GB不等。其中DICOM文件90%以上是圖像數(shù)據(jù)。如此巨大的數(shù)據(jù)量使得圖像存取速度成為需要重點(diǎn)考慮的問題[7]。目前國內(nèi)主要采用對圖像進(jìn)行壓縮處理、建立圖像緩沖池和分層存儲管理等幾種方法來解決醫(yī)學(xué)圖像的快速存取問題。

分層存儲管理大多是通過在線和離線相結(jié)合的方式來進(jìn)行的。在線存儲的首選設(shè)備通常為大容量的磁盤列陣，而該分層存儲管理方法雖然考慮到了磁盤列陣具有速度高、存取方便、可靠性好、價格較低等特點(diǎn)，但由于現(xiàn)有的醫(yī)學(xué)圖像切割都是靜態(tài)切割，有可能不適用。應(yīng)該考慮引入自適應(yīng)機(jī)制將圖片分層以后再進(jìn)行切割緩存方法的適用性。而緩沖池中的數(shù)據(jù)采用LRU算法保存，減少了網(wǎng)絡(luò)通信量和數(shù)據(jù)存儲壓力，在DICOM文件中存在著緩存調(diào)度、緩存文件大小和使用頻率不等的問題。因此現(xiàn)有的緩存策略可能不適用于DICOM文件。本文基于圖像分層存儲的思想引入DICOM圖像自適應(yīng)分層切割方法，并且在LRU算法的基礎(chǔ)上進(jìn)行改進(jìn)，使得DICOM文件的緩存命中率有了明顯的提升。

2 動態(tài)策略計(jì)數(shù)算法

2.1 基于DICOM的代理服務(wù)器

如圖1所示給出了基于代理技術(shù)的DICOM醫(yī)學(xué)圖像服務(wù)模型。若用戶需要的DICOM數(shù)據(jù)在代理服務(wù)器中沒有被緩存的話，那么DICOM數(shù)據(jù)需要通過WAN從PACS系統(tǒng)中獲取，而從PACS系統(tǒng)中獲取的數(shù)據(jù)可以直接或者間接通過代理服務(wù)器的形式發(fā)送給需求不同的用戶。由于代理服務(wù)器的緩存空間有限，對調(diào)度緩存內(nèi)容的大小十分敏感，所以其性能的好壞直接影響著該模型的性能。本文在代理服務(wù)器端使用的緩存策略為部分緩存和整體緩存或者兩者相結(jié)合的方式，并且輔之以分層切割醫(yī)學(xué)影像的方法提高緩存查找性能。用于改善基于DICOM文件PACS系統(tǒng)的服務(wù)性能。

2.2 醫(yī)學(xué)圖像自適應(yīng)分層切割

由于DICOM文件解析出來的醫(yī)學(xué)圖數(shù)據(jù)動態(tài)范圍過大并且均超出了普通顯示器的動態(tài)顯示范圍，存在資源的浪費(fèi)現(xiàn)象。查看DICOM文件時主要分為移動端查看和網(wǎng)頁端查看。在移動端查看時，由于IP地址變化、會話和登入登出均比較頻繁，需要依據(jù)移動端的操作系統(tǒng)把圖像置換為適合客戶端APP屏幕顯示的大小。在網(wǎng)頁端查看時，依據(jù)分辨率不同每次查看需要的切割圖片不同，但是依據(jù)其IP地址的變化小的特點(diǎn)建立IP地址和顯示器的對應(yīng)關(guān)系自適應(yīng)顯示切割圖片。

本文引用GIS（Geographic Information System，地理信息系統(tǒng)）瓦片地圖的切割原理將醫(yī)學(xué)圖像進(jìn)行分層切割[8]。瓦片式地圖由GIS數(shù)據(jù)的高速共享發(fā)展而來，由原始數(shù)據(jù)的切割存儲和按需傳輸兩部分組成，由Google Maps提出，采用預(yù)切割的方法將圖像進(jìn)行分層切割并存儲于服務(wù)器端，當(dāng)用戶發(fā)出請求時只需從Google Maps服務(wù)器端發(fā)送所需的瓦片到客戶端，在很大程度上提高了訪問速度[9]。為了滿足視覺無損和高效傳輸?shù)男枨螅隚IS瓦片切割思想：將高分辨率的醫(yī)學(xué)圖像預(yù)先分層切割并存儲以滿足“按需傳輸”的要求。采用非固定瓦片格分辨率和固定層數(shù)的方式對源數(shù)據(jù)進(jìn)行模式化處理，根據(jù)醫(yī)學(xué)影像的特點(diǎn)實(shí)現(xiàn)面向用戶瀏覽器的DICOM自適應(yīng)顯示。采用XML文件存儲DICOM文件中的醫(yī)療信息，采用切割圖片顯示醫(yī)學(xué)圖像數(shù)據(jù)，設(shè)計(jì)流程圖如圖2所示。

具體涉及步驟如下：

Step1：用戶登錄，啟動會話，使用歡迎界面獲取用戶屏幕分辨率大小信息并存儲于用戶關(guān)系表中。

Step2：依據(jù)用戶關(guān)系表動態(tài)生成切割圖片。并在會話空閑過程中，緩存服務(wù)器動態(tài)調(diào)整切割圖片的大小。開始時緩存標(biāo)準(zhǔn)DICOM文件，當(dāng)獲取到用戶屏幕大小分辨率進(jìn)行自適應(yīng)調(diào)整之后，丟棄原先的標(biāo)準(zhǔn)DICOM文件，緩存切割好的圖片。

Step3： 在用戶請求的時候發(fā)送和用戶實(shí)際請求大小一致的緩存數(shù)據(jù)。

Step4：緩存大小自動更新機(jī)制。對于移動端：緩存數(shù)據(jù)不變，依據(jù)移動端的APP設(shè)置自動分配DICOM緩存數(shù)據(jù)的大小。對于網(wǎng)頁端，依據(jù)IP地址存在更換的可能性設(shè)定超時機(jī)制，依據(jù)醫(yī)院的交班時間定時清空用戶關(guān)系表。

2.3 DSGC算法

對于緩存對象及其數(shù)據(jù)單元的大小，在第2.2節(jié)已對緩存數(shù)據(jù)進(jìn)行了預(yù)處理，在本節(jié)中希望通過對緩存調(diào)度算法的更改，使得進(jìn)一步提高緩存的性能。將LRU算法和LFU算法的思想和醫(yī)學(xué)圖像使用的特殊性相結(jié)合運(yùn)用到DICOM醫(yī)學(xué)影像的緩存中是符合實(shí)際的。例如：一張CT圖像，醫(yī)生在圖像剛生成的一段時間內(nèi)看了幾次以后，由于某種原因在以后的治療中再也沒有查看過這張CT圖像。這時基于關(guān)鍵特征和代價的替換算法就無法起到作用，而LRU算法認(rèn)為的最近使用的資源具有很高的未來使用價值、LFU算法認(rèn)為的資源使用頻率與未來的使用價值成正比。緩存替換策略的運(yùn)用首先需要給當(dāng)前的緩存對象一個訪問熱度和訪問時間的綜合排名，即是綜合使用效率的排名。然后再依據(jù)使用效率的高低替換出使用效率最低的緩存內(nèi)容，而其中效率函數(shù)的設(shè)計(jì)是重要的一環(huán)，它對于緩存命中率的高低有著直接的影響。

圖片的局部訪問原理對于使用效率的影響是最大的，局部訪問原理指的是在最近時間區(qū)間內(nèi)被訪問過的切割圖片在隨后的一段時間內(nèi)可能被再次訪問的概率比較高。該原理對于緩存技術(shù)和預(yù)取技術(shù)有著比較重大的影響。LRU算法認(rèn)為最近被使用的圖片存在著很高的未來使用價值，其價值函數(shù)為：

[μit=1t-tL] （1）

式中：[μit]表示在t時刻資源i的未來使用價值；t為緩存資源i的時間；[tL]為緩存資源最近一次訪問的時間。LFU算法認(rèn)為最近被訪問次數(shù)最多的資源在未來會擁有很高的使用價值；但其存在緩存污染的問題，所以考慮訪問頻率和訪問的最近時間點(diǎn)采用LRU?K算法。估計(jì)文件i在首次使用后進(jìn)入緩存后會被使用到的概率為[Pit]，而[Pit]的估計(jì)采用類似LRU，LFU和LRU?K等的函數(shù)設(shè)計(jì)方法。由于未來切割圖片訪問的不可預(yù)知性，只能依據(jù)切割圖片i的歷史訪問記錄來估計(jì)[Pit]的概率。圖3為切割圖片i的歷史訪問序列。

圖3中，自從t1時刻以來，t2，t3時刻的訪問量明顯增加，自t4時刻以后訪問量逐漸下降。并且由于訪問時間間隔與訪問時間的分布滿足泊松分布。而該問題在參考文獻(xiàn)[10]已經(jīng)給出證明。對于任意圖片i的訪問獨(dú)立且服從泊松分布[11]，那么[Pit]的概率估計(jì)公式如下：

[Pi=kt=e-λλitkk！] （2）

[λit]值的確定：以LRU?K為代表，從某一時間開始的高頻率的資源訪問量意味著在這一個時間點(diǎn)后該資源的未來訪問頻率近似滿足泊松分布。其[λit]的估計(jì)公式為：

[λit=kn=1ktin] （3）

設(shè)定切割圖片的最后第n次訪問時間為[tin]，其最后一次的訪問時間為[ti1]。設(shè)定切割圖片在緩存中的平均存活時間為：

[ti=i=1nT-tinn] （4）

式中，T為目前的緩存系統(tǒng)時間。由此將式（4）代入式（3）中可以推導(dǎo)出[λit]估計(jì)公式為：

[λit=km=1kti] （5）

式中，k為常數(shù)1時，滿足LRU策略在相對時間下的[λit]估計(jì)公式[12]，依據(jù)式（2）推導(dǎo)出：

[Pi=kt=e-λm=1ki=1nT-tinnkk！] （6）

假定在某一層上緩存切割圖片的集合為PictureGather（t）={1，2，…，N} ，表示切割圖片{1，2，…，N}在t時刻的存儲。設(shè)定Size（i）為文件PictureGather（t）的大小，i越大說明該層緩存的切割數(shù)量也越多。

依據(jù)集合PictureGather（t）={1，2，…，N}，求出集合內(nèi)緩存切割圖片的平均緩存時間為：

[Meant=n=1NSLn-SFnN] （7）

式中：[SLn]表示切割圖片的最后一次訪問時間；[SFn]為切割圖片的首次存儲時間。每一塊切割圖片存在于緩存區(qū)域的時間不同，那么對未來的使用價值也一定不同。對于在某一個緩存溢出時間點(diǎn)所要進(jìn)行替換的切割圖片也不盡相同。設(shè)定緩存區(qū)的容量大小為V。在[i=1Nδit×Sizei≈V]的約束條件下，其中[i=1Nδit]，[δit∈（0，1）]，0表示切割圖片i在t時刻沒有存在于緩存中；1表示圖片i在t時刻存在于緩存中。理想的緩存替代策略算法動態(tài)策略代數(shù)（Dynamic Strategy GenerationCount，DSGC）為：

[DSGC=1t-tL?n=1NSLn-SFnN?e-λm=1ki=1nT-tinnkk！] （8）

即，[DSGC=μit×Meant×Pit]。然后依照DSGC的值非遞增排序PictureGather（t）={1，2，…，N}中的元素，在非遞增排序完成后從最小的值開始將切割圖片剔除出緩存，直到達(dá)到指定的緩存剩余空間為止。

3 實(shí)驗(yàn)與評價

實(shí)驗(yàn)一：在英特網(wǎng)內(nèi)完成了自適應(yīng)機(jī)制和傳統(tǒng)用戶請求準(zhǔn)確率的對比測試。代理服務(wù)器端的硬件配置為HPWorkStation2100（CPU：Pentium Ⅳ 2.0 GHz×2，內(nèi)存1 GB）。客戶端則是英特網(wǎng)內(nèi)100臺型號不一的計(jì)算機(jī)和100臺操作系統(tǒng)不完全一樣的移動終端。在實(shí)際網(wǎng)絡(luò)環(huán)境下測試自適應(yīng)機(jī)制下移動端和網(wǎng)頁端的準(zhǔn)確率和傳統(tǒng)機(jī)制下的準(zhǔn)確率。實(shí)驗(yàn)結(jié)果如表1所示。

表1 準(zhǔn)確率 %

實(shí)驗(yàn)說明緩存大小和用戶實(shí)際請求基本吻合。而采用原始DICOM數(shù)據(jù)由于文件不能與屏幕相適應(yīng)產(chǎn)生大量的浪費(fèi)，使得請求的準(zhǔn)確率與用戶的實(shí)際請求之間產(chǎn)生了巨大差異。由此可以得出自適應(yīng)所調(diào)度的緩存資源和用戶請求的資源是一致的，這樣就減少了大量的數(shù)據(jù)浪費(fèi)，使得緩存中的數(shù)據(jù)浪費(fèi)得到明顯的改善。

實(shí)驗(yàn)二：本文還采用 Web 緩存替換算法常用的衡量標(biāo)準(zhǔn)進(jìn)行實(shí)驗(yàn)，固定使用100臺手機(jī)端進(jìn)行緩存考察算法中的切割圖片的命中率。切割圖片命中率指緩存中命中的請求對象與總請求對象的百分比。實(shí)驗(yàn)采用網(wǎng)站的真實(shí)數(shù)據(jù)進(jìn)行仿真。首先對訪問的DICOM醫(yī)學(xué)圖像進(jìn)行基于自適應(yīng)的圖片切割數(shù)據(jù)預(yù)處理，選取數(shù)據(jù)集的[35]構(gòu)造算法模型。另外[25]作為測試數(shù)據(jù)，結(jié)合緩存替換算法計(jì)算切割圖片的命中率進(jìn)行仿真實(shí)驗(yàn)。DSGC，LRU?K和LFU算法的試驗(yàn)結(jié)果如表2所示。

DSGC/LRU?K/LFU算法命中率對比圖如圖4所示。

DSGC/LRU?K/LFU沒中率對比圖如圖5所示。

如圖4、圖5、表2所示，引入切割圖片的有用性和在函數(shù)價值計(jì)算中是否存在意義，是本文所關(guān)注的問題。DSGC算法比較LRU?K算法和LFU算法的性能比較可以證明其有效性。說明了訪問頻率和訪問局部性存在的有效性。如圖4所示，隨著緩存容量的增大LRU?K，LFU算法和DSGC算法的性能也在逐漸的增加，但是DSGC算法的緩存命中率始終要比LRU?K和LFU的命中率高。從此情況分析出帶來這一良好性能的優(yōu)勢取決于對于價值函數(shù)的設(shè)計(jì)：主要關(guān)注切割圖片自適應(yīng)緩存策略帶來的價值，而不是從整張圖片的價值入手進(jìn)行算法設(shè)計(jì)。

4 結(jié) 語

本文討論并研究了醫(yī)療信息系統(tǒng)中代理服務(wù)器的緩存替代問題，并且關(guān)注了該問題模型的特殊性，提出了針對醫(yī)學(xué)圖像分層切割圖片的有用性并將其用于改進(jìn)和設(shè)計(jì)緩存的替代算法中。仿真實(shí)驗(yàn)表明：在自適應(yīng)機(jī)制下本文所提出的DSGC算法的性能優(yōu)于LRU?K等算法。而在未來的工作中將著手于引入BP神經(jīng)網(wǎng)絡(luò)的原理來更進(jìn)一步優(yōu)化DSGC算法。

注：本文通訊作者為黃青松。

參考文獻(xiàn)

[1] 楊明，劉斌，楊小慶，等.Pacs系統(tǒng)在醫(yī)學(xué)影像學(xué)教學(xué)及實(shí)踐教學(xué)體系改革中的作用[J].中國高等醫(yī)學(xué)教育，2007（1）：41?42.

[2] 梁存升，馮驥.DICOM標(biāo)準(zhǔn)分析及其應(yīng)用[J].中國醫(yī)學(xué)裝備，2006（2）：18?20.

[3] 喬梁，宋文強(qiáng).基于DICOM圖像的Web瀏覽與傳輸?shù)难芯亢蛯?shí)現(xiàn)[J].中國醫(yī)療設(shè)備，2007，22（12）：15?17.

[4] 毛應(yīng)爽，鄭永春，耿曉中.Web緩存替換算法的研究與改進(jìn)[J].信息技術(shù)與信息化，2014（5）：215?216.

[5] 鐘克吟.ASP緩存策略探討[J].現(xiàn)代計(jì)算機(jī)（專業(yè)版），2006（9）：68?71.

[6] 杜振偉，王之，霍達(dá)，等.瓦片式算法在家庭網(wǎng)絡(luò)環(huán)境實(shí)現(xiàn)高分辨率醫(yī)學(xué)影像實(shí)時瀏覽與傳輸?shù)难芯縖J].中國數(shù)字醫(yī)學(xué)，2012，7（12）：54?57.

[7] 辜麗川，尹家生，周健.DICOM圖像存儲和管理中的關(guān)鍵問題和技術(shù)[C]//首屆國際醫(yī)學(xué)影像學(xué)暨介入醫(yī)學(xué)學(xué)術(shù)會議.北京：中國聲學(xué)會，2005：53?55.

[8] 陳樺，李艷明，朱美正.一種支持大量并發(fā)用戶的瓦片緩存方案研究[J].計(jì)算機(jī)工程與科學(xué)，2012，34（12）：144?149.

[9] SHEN H L， MA D F， ZHAO Y W， et al. MIAPS： a Web?based system for remotely accessing and presenting medical images [J]. Computer methods & programs in biomedicine， 2014， 113（1）： 266?283.

[10] TSYBAKOV B， GEORGANAS N D. Overflow and losses in a network queue with a self?similar input [J]. Queueing systems， 2000， 35（1）： 201?235.

[11] 肖明忠，李曉明，劉翰宇，等.基于流媒體文件字節(jié)有用性的代理服務(wù)器緩存替代策略[J].計(jì)算機(jī)學(xué)報，2004，27（12）：1633?1641.

[12] FLEMING C， PETERSON P， KLINE E，et al. Data tethers： preventing information leakage by enforcing environmental data access policies [C]// Proceedings of 2012 IEEE International Conference on Communications. Ottawa： IEEE， 2012： 835?840.