基于阿爾法形態(tài)的三維色域體積快速算法

孫 婧，徐 巖，李桂苓

（天津大學 電子信息工程學院，天津 300072）

基于阿爾法形態(tài)的三維色域體積快速算法

孫 婧，徐 巖，李桂苓

（天津大學 電子信息工程學院，天津 300072）

隨著各種寬色域顯示設(shè)備的出現(xiàn)，越來越需要高效準確的色域比較評價方法。三維色域由于包含了亮度信息，與二維色域相比，能夠更全面地展示、比較色域差異。但由于其形狀不規(guī)則，三維色域的計算較困難，高計算復雜度限制了三維色域評價在實時性要求較高的工程領(lǐng)域的應(yīng)用。實現(xiàn)了基于阿爾法形態(tài)的三維色域體積計算方法。實驗結(jié)果表明，通過仔細選擇半徑參數(shù)，能夠以較低計算復雜度準確計算不規(guī)則三維色域體積。與基于準蒙特卡洛的體積計算方法相比，基于阿爾法形態(tài)的方法更適合實時應(yīng)用。

三維色域；體積計算；阿爾法形態(tài)

目前通常用二維空間色域表示顯示器能夠重顯的色彩范圍，而色彩實際上是一個三維的量，各種可用來表示顏色的色空間（如XYZ，RGB，Luv，Lab）都是三維色空間。在二維空間計算色域及色域覆蓋率忽略了亮度級別對色域范圍的影響，所得結(jié)果不能充分反映色彩重顯特性。因此，需要在包含亮度信息的三維空間中計算色域及色域覆蓋率。目前已有一些計算三維色域體積的算法被提出。Bangyong Sun等[1]提出了CIE LAB色空間的液晶顯示器色域描述算法。該算法在CIE LAB色空間利用Delaunay（德洛涅）三角剖分技術(shù)將色域邊界面分割成小三角形。取中心點并將其與表面劃分的三角形相連形成四面體，求所有四面體之和得到三維色域體積。Andreas Willert等[2]分別在CMY及CMYK色空間按亮度將色域體積均分成一系列薄片，在每個薄片上劃分網(wǎng)格計算其色域大小。況盛坤等[3]采用基于空間區(qū)域分割的四面體網(wǎng)格剖分算法實現(xiàn)數(shù)字輸出設(shè)備色域的三維立體再現(xiàn)和色域體積的求取。該算法將色度坐標數(shù)據(jù)轉(zhuǎn)化為球面坐標，分別將色相角和仰角均分成N份，從而將整個顏色空間分成N×N個子區(qū)域進行計算。李超等[4]根據(jù)Delaunay理論在三維空間的擴展，將不規(guī)則的顏色空間立體分解為多個四面體網(wǎng)格進行色域體積的計算。該算法將分解得到的所有四面體體積相加，并沒有考慮到色域立體表面的凹凸程度可能與分割成的四面體網(wǎng)格表面不一致?，F(xiàn)有這些求三維體積快速算法多針對凸包，將色域表面作為光滑的凸面進行處理。實際上，從實測數(shù)據(jù)重構(gòu)出的顯示器三維色域立體可以看出，在設(shè)備無關(guān)色空間，顯示器三維色域是凸包與凹坑相混合的不規(guī)則立體，用已有算法進行計算多會產(chǎn)生誤差，結(jié)果并不準確。

本文致力于開發(fā)一種高效的色域體積計算方法。

1 阿爾法形態(tài)（Alpha Shapes）算法

對于一組給定的無序樣點，阿爾法形態(tài)算法能夠高效地提取離散點的輪廓并重構(gòu)其幾何形狀。設(shè)二維空間中的有限點集合S，阿爾法形態(tài)算法的基本思想是將一個半徑為α的圓圍繞給定的離散點集S滾動，如圖1所示[5]。

圖1 阿爾法形態(tài)算法原理示意圖

S的輪廓是一個多邊形，由S和半徑參數(shù)α決定。α控制多邊形輪廓的精細程度。當α取值適當，這個圓就不會滾到S的內(nèi)部，與圓相交的點就是S的邊緣輪廓點，其滾動的痕跡就是S的邊界線[5]。當α足夠大時，所得多邊形將為S的凸包。當α接近0時，S的邊界線會通過S中的每一點。α取值對所得輪廓的影響如圖2所示。

圖2 半徑參數(shù)對輪廓的影響示意圖

設(shè)S中有n個點，可連接成n（n-1）/2條線，需要在其中找到位于邊界的線。Edelsbruuner等[6]于1983年給出了阿爾法形態(tài)模型判斷準則，根據(jù)這一準則可以確定邊界線。判斷條件如下：在點集S內(nèi)任取兩個點 p1和 p2，過這兩點繪制半徑為α的圓，若圓內(nèi)沒有其他點，則可認為 p1p2是邊界線。Edelsbruuner等[7]于1994年從幾何學的角度給出了三維阿爾法形態(tài)的原理，為其在工程領(lǐng)域的應(yīng)用奠定了基礎(chǔ)。Tomasz J.Cholewo等[8]于1999年提出一種基于阿爾法形態(tài)算法的面向彩色打印設(shè)備和彩色圖像的色域邊界提取算法。

2 三維色域體積計算

根據(jù)對多種不同寬色域顯示設(shè)備的三維色域的觀察，其形狀均為不規(guī)則的凸包和凹坑的組合。其中一種在Luv空間的三維色域如圖3所示（大部分色域是凸包，而在紫、紅、黃、白區(qū)域為凹坑）。

圖3 Luv空間顯示器色域

已知三維色域同時具有凸包和凹坑的特征，需要使用能同時適應(yīng)兩種情況的算法來計算其體積。如第1節(jié)所述，阿爾法形態(tài)法從原理上適用于凹坑和凸包兩種情況。將阿爾法形態(tài)法擴展至三維[7-8]，即可用來計算三維色域體積。

1）使用規(guī)范色域測試樣本測試得到待測顯示器的色域表面散點數(shù)據(jù)集S，S中的散點均為分布在三維色域表面上的點，集合S確定了該顯示器的三維色域邊界。

2）對點集S進行三角剖分，建立三維Delaunay三角網(wǎng)，得到N行4列的矩陣，N為分割的四面體的個數(shù)，矩陣的每行為分割成的四面體頂點的索引值。

3）利用Alpha Shapes算法原理對四面體進行篩除。對每一個單純形四面體計算其外接圓半徑R；對于給定的Alpha Shapes半徑參數(shù)α，僅保留R＜α的四面體；經(jīng)過篩除之后，所剩小四面體的外邊界面即為三維色域體積的邊界面。

4）可視化步驟3）所得三維色域的邊界面，即可視化篩除后所剩小四面體的外界面，通過改變α的大小，控制得到的邊界面的精細程度。若邊界面有空洞不連續(xù)，表示當前α值過小，增大α值，重復步驟3）；若邊界面連續(xù)但空間位置位于S中散點之下，表示當前α值仍然過小，增大α值，重復步驟3）；若邊界面連續(xù)但空間位置位于S中散點之上，表示當前α值過大，減小α值，重復步驟3）；調(diào)整α值直至邊界面連續(xù)且與S中散點重合，表明此時所取α值大小正好，其重構(gòu)的邊界面的凹凸程度與實際色域表面的凹凸程度一致。

5）對符合條件的四面體分別計算其體積，再將所有的體積相加即得到三維色域的體積。

3 實驗結(jié)果

根據(jù)課題組對大量顯示設(shè)備的色度測試和三維色域可視化實驗，設(shè)備無關(guān)色空間如Luv中的三維色域邊界面對應(yīng)于RGB色立體的6個面，相鄰面的交線對應(yīng)于RGB色立體的12條邊以及RGB色立體表面上連接白-紅、白-綠、白-藍、黑-黃、黑-青、黑-紫的6條線，共18條線。在實際應(yīng)用中，為減少色度測試樣點，每條邊上取10個測試樣點，形成如圖3所示的三維色域。

應(yīng)用第2節(jié)所述的擴展的阿爾法形態(tài)算法計算Luv空間中三維色域的體積。算法運行于HP 400-021cx臺式電腦（2.9 GHz CPU，4 Gbyte ROM），運行環(huán)境為Win?dows7，MATLAB 2012a。表1給出當α取不同值時計算體積值與所用時間。

表1 α取不同值時計算體積值與所用時間

半徑參數(shù)α取不同值時的實驗結(jié)果如圖4所示，可以看出α值越大，所形成的邊界就越凸。經(jīng)實驗測試，當α＜45時，算法無法重構(gòu)色域表面（出現(xiàn)空洞）；當45＜α＜50，重構(gòu)表面略低于測試樣點；當50＜α＜200，重構(gòu)輪廓與測試樣點一致。

圖4 α取不同值時計算色域體積

由實驗結(jié)果可以看出，通過仔細選取半徑參數(shù)，阿爾法形態(tài)法能夠在較短時間內(nèi)計算出色域體積。

準蒙特卡洛方法是應(yīng)用于多重積分、面積和體積計算的統(tǒng)計方法[9]。為比較基于阿爾法形態(tài)的算法和基于準蒙特卡洛積分的方法，在同一實驗平臺上實現(xiàn)了準蒙特卡洛體積計算算法。準蒙特卡洛算法原理是隨機取采樣點，根據(jù)落在色域內(nèi)的點的比例計算色域體積。本文實驗選取了多個不同隨機采樣點數(shù)N，N服從均勻分布，分別運行10次，取均值作為結(jié)果。實驗結(jié)果如表2所示。實驗中N的最大值為6.7×106，因為更大的N值會導致系統(tǒng)內(nèi)存溢出。

表2 準蒙特卡洛積分計算色域體積

需要指出的是，表2中所列時間不包括將測試數(shù)據(jù)分成12個面、分別對12個面進行曲面擬合，以及找到準蒙特卡洛邊界條件的時間?？紤]到這一點，可以看出基于阿爾法模型的體積計算方法比基于準蒙特卡洛算法的體積計算方法效率高，更適合實時應(yīng)用。而且，準蒙特卡洛算法的精確度與N的平方根成正比、算法復雜度與N成正比，對硬件要求較高，限制了其在普通配置測試平臺上的應(yīng)用。

4 結(jié)論

在三維空間比較色域能比二維色度圖提供更多信息。然而由于在設(shè)備無關(guān)色空間中色域是凸包和凹坑的不規(guī)則組合，高計算復雜度限制了其在實時應(yīng)用領(lǐng)域中的應(yīng)用。本文使用擴展的阿爾法形態(tài)算法計算三維色域體積。實驗結(jié)果表明該方法能高效重構(gòu)邊界輪廓、計算色域體積。集成該方法的三維色域處理平臺可為顯示器生產(chǎn)商和測試機構(gòu)提供高效的三維色域比較、評價手段。

目前，實驗中半徑參數(shù)α的選取仍需人工決定。接下來的工作中將進一步研究能自適應(yīng)選取最佳α值的方案。

[1] SUN B，LIU H，LIW，et al.A color gamut description algorithm for liquid crystal displays in CIELAB space[J].The Scientific World Journal，2014（2014）：1-9.

[2]WILLERT A，F(xiàn)LASPOHLER M，HUBLER A C.Calculating a col?or gamut border using a grid approach[C]//Proc.Conference on Co?lour in Graphics，Imaging，and Vision.[S.l.]:Society for Imaging Science and Technology，2004：156-160.

[3] 況盛坤，王曉紅，呂兆鋒.基于空間區(qū)域分割的四面體網(wǎng)格剖分色域描述算法[J].包裝工程工程版，2014，35（5）：126-130.

[4] 李超，王彩印.基于空間四面體網(wǎng)格的色域計算與比較研究[J].中國印刷與包裝研究，2010（S1）：102-106.

[5] WU Z，QIL，LUO P，et al.Edge-preservingmulti-scale image de?composition based on alpha-shape[C]//Proc.Conference Anthology，IEEE.Beijing:IEEE Press，2013:1-5.

[6] EDELSBRUNNER H，KIRKPATRICK D，SEIDEL R.On the shape of a set of points in the plane[J].IEEE Trans.Information Theory，1983，29（4）:551-559.

[7] EDELSBRUNNER H，MUCKE E P.Three-dimensional alpha shapes[J].ACM Trans.Graphics，1994（13）:43-72.

[8]CHOLEWO T J，LOVE S.Gamut boundary determination using al?pha-shapes[C]//Proc.the 7th Color Imaging Conference.Scottsdale: [s.n.]，1999：200-204.

[9] NIEDERREITER H.Random number generation and quasi monte Carlomethods[M].Philadelphia:SIAM，1992.

3D Color Gamut Volume Calculation A lgorithm Based on Alpha Shapes

SUN Jing,XU Yan,LI Guiling
（School of Electronics Information Engineering,Tianjin University,Tianjin 300072,China）

With the emerging of different kinds of wide color gamut displays,evaluation and comparison of their color gamut are required more.3D color gamut is known as a better way to demonstrate gamut difference and provide more information than conventional 2D color gamut as it incorporates luminance information.Because of its irregular shape,the calculation of 3D color gamut is relatively difficult and complex.High computational complexity restricts its application in real time cases.In this paper,an Alpha shapes algorithm on PC for 3D color gamut volume calculation is implemented.Experiment results show that this method can accurately compute the volume of the irregular shaped gamut with relatively low computational complexity by carefully choosing the radius parameter.Compared with quasi-Monte-Carlo-based method,Alpha-shapes-based method is more suitable for real time cases.

3D color gamut;volume calculation;Alpha shapes

TN873

A

?? 薇

2014-08-11

【本文獻信息】孫婧，徐巖，李桂苓.基于阿爾法形態(tài)的三維色域體積快速算法[J].電視技術(shù)，2014，38（21）.

孫 婧，女，碩士生，主研信息號信息處理、數(shù)字視頻與多媒體技術(shù)；

徐 巖，女，副教授，碩士生導師，主要從事信息號信息處理、數(shù)字視頻與多媒體技術(shù)教學、科研工作；

李桂苓，教授，博士生導師，主要從事信息號信息處理、數(shù)字視頻與多媒體技術(shù)教學、科研工作。