摘 要:針對由樣本集直接建立的三維查找表數(shù)據(jù)不均勻，不能滿足ICC Profile 規(guī)范要求的問題，提出了反向均勻化的解決方法。重點討論了反向均勻化過程中快速定位四面體、色域邊界點外推技術(shù)以及色域邊界外點的色域匹配等幾個關(guān)鍵技術(shù)。根據(jù)LAB空間采樣數(shù)據(jù)特點給出了一種快速定位四面體的算法，利用圖像邊界處理的外推思想得出了色域邊界點插值模型，提高了插值的校正速度;討論了色域匹配的裁剪匹配算法并提出了利用二維查找表來提高算法效率的思想，縮短了判斷時間，降低了算法復(fù)雜度。最后通過實驗驗證了反向均勻化算法，給出了實驗效果圖。

關(guān)鍵詞:反向均勻化; 三維插值; 外推技術(shù); 色域匹配

中圖分類號:TP391 文獻標(biāo)識碼:A

文章編號:1004-373X(2010)12-0125-04

Key Technologies on Inverse Uniformity for Three Dimensional Interpolation

LI Xiang-wei

(Xi’an Institute of Post Telecommunications， Xi’an 710121， China)

Abstract:The inverse uniformity method is proposed to solve the problem that 3D look-up table created directly by color patch sample is usually not uniform， which can not meet the ICC Profile specification. Three key technologies are discussed in detail: fast searching tetrahedron， extrapolation of gamut boundary points and gamut mapping. A fast searching tetrahedron algorithm is given based on the characteristics of LAB spatial sampling data. The interpolation model of gamut boundary points is provided by extrapolation ideas of image boundary treatment ideas， the corrected speed of interpolation is improved. The matching cut algorithm of gamut mapping is studied， and the thinking of using two-dimensional look-up table to improve the efficiency of algorithm are stated， which shortened the time to determine and reduce the complexity of the algorithm. The inverse uniformity algorithm is verified by experiments， and itsexperimental results figures are given finally.

Keywords:inverse uniformity; three dimensional interpolation; extrapolation; gamut mapping

0 引 言

為解決各種成像設(shè)備如顯示器、打印機等等之間成像色彩的一致性， 色彩管理技術(shù)通過引入與設(shè)備無關(guān)的顏色空間，建立設(shè)備的彩色特性描述，并按用戶要求進行顏色空間轉(zhuǎn)換、色域匹配(彩色增強)、以及非線性特性校正等軟件技術(shù)方法來彌補現(xiàn)有硬件設(shè)備的不足，使其可給出用戶滿意的高品質(zhì)、與設(shè)備無關(guān)(所見即所得)的彩色再現(xiàn)[1-2]。彩色校正的主要任務(wù)是補償外設(shè)非線性產(chǎn)生的偏差，其實現(xiàn)方法可以劃分為多重回歸、三維插值、神經(jīng)網(wǎng)絡(luò)和模糊邏輯等[1，3-4]。

作為三維插值的一種算法，四面體插值算法由于其在實現(xiàn)代價和計算速度上的優(yōu)勢已廣泛應(yīng)用于實際的設(shè)備校正中[1]。色彩校正前，通常需要一樣本集來描述設(shè)備特性。然而通過樣本集直接建立起來的三維查找表是不均勻的，即是非均勻的三維查找表。ICC Profile[5]規(guī)范要求最后的數(shù)據(jù)的源色彩空間必須是均勻的。所以直接建立起的三維查找表數(shù)據(jù)不能直接利用，必須經(jīng)過四面體插值算法得到均勻的數(shù)據(jù)。即在正向查找表的基礎(chǔ)上建立反向查找表，這一過程稱為反向均勻化。

1 反向均勻化

由于在CMYK空間均勻采樣獲得的樣本集在CIELAB空間的分布極不均勻，所以從CMYK空間到LAB空間建立的三維查找表(正向查找表)不能在色彩再現(xiàn)時用于直接插值計算CMYK值[1]。否則會出現(xiàn)兩個問題:

(1) 速度慢。查找時需要遍歷所有的立方體或四面體來確定插值點位置，這一操作的運算量非常大，如果用此方法來校正一幅圖象，需要的時間太長，將不能滿足實際需求。

(2) 對于色域邊界的處理會變得非常復(fù)雜。因為在色域邊界存在某些點不在任何四面體中的情況，所以不能直接通過三維插值獲得其對應(yīng)的CMYK值。對于色域邊界特殊情況的處理使得三維插值方法不能簡單高效地執(zhí)行。

在正向查找表的基礎(chǔ)上建立從LAB到CMYK的查找表(反向查找表)，這一過程稱為反向均勻化。步驟如下:

(1) 在CIELAB空間的打印機色域范圍內(nèi)均勻采樣;

(2) 查找正向查找表，計算樣點對應(yīng)的CMYK值;

(3) 如果某樣點位于色域外部，則第二步不能計算得到CMYK值，在此使用外推技術(shù)計算其CMYK值;

(4) 建立反向查找表。

這樣對于任一輸入的LAB值，就可以迅速確定其所在的四面體，從而實現(xiàn)快速插值，得到CMYK值。

2 關(guān)鍵技術(shù)

2.1 四面體的快速定位

樣本集生成的時候不知道設(shè)備特性，所以均勻分色樣本集在設(shè)備無關(guān)色彩空間中是不均勻的，也就是說，即使樣本集的CMYK數(shù)據(jù)是有規(guī)律的，其對應(yīng)的LAB數(shù)據(jù)在LAB空間也是不均勻。所以CMYK的空間中的立方體在LAB空間中就變成了一個變形的六面體[6-7]。因此，從LAB到CMYK的插值過程中，不能一次定位到需要插值點所在的四面體位置[8]。為此，需要找到快速定位(搜索)四面體的算法來均勻化數(shù)據(jù)。

快速定位算法的思想是:在均勻采樣LAB空間進行反向均勻化的時候，對LAB空間采樣的數(shù)據(jù)是按照LAB高維到低維的順序存放的，相鄰兩個LAB數(shù)據(jù)至多在一個維上變化，也就說，這兩個值是相近的[9]。基于上述原因，如果已經(jīng)查到一個LAB所在四面體，那么下一個LAB就應(yīng)該在這個四面體的一個鄰域中可以找到。

快速定位算法的形式化描述如下:

Algorithm LocalSearching

{

for(i=0;i

{

if (不是第一查找的LAB)

{

for (j=StartI; abs(j-StartI)<εTetra; j++)

//在鄰域εTetra中查找

if Search_TetraList_Interpolation()

StartI=j; //若在鄰域εTetra中，記錄查到四面體的位置

else //若未在鄰域εTetra中查找到，則查找所有四面體

break;

}

else //記錄第一次查找位置

for(j=0;j

if Search_TetraList_Interpolation()

StartI=j; //記錄第一次查到四面體的位置

}

for(j=0;j

if Search_TetraList_Interpolation()

StartI=j;//記錄查到四面體的位置}

其中，NL為LAB需要插值的數(shù)目，即Profile數(shù)據(jù)的數(shù)目;NT為四面體的數(shù)目。

2.2 外推技術(shù)

打印機色域邊界是不規(guī)則的，所以在反向均勻化時，均勻取樣的LAB點可能不在色域內(nèi)部，也即在幾何體插值時立方體或四面體的部分頂點不在色域內(nèi)部，這意味著在進行正向插值時，這些點的值無法通過校正得到[10]。為使校正方法具有一致性并提高校正速度，必須得到這些點的值。這可以通過外推技術(shù)實現(xiàn)。

如圖1所示，色域邊界是不規(guī)則的，均勻取樣(如圖網(wǎng)格點)后對色域內(nèi)部的點(如P)可以用其所在的立方體或四面體的頂點插值計算;而對于色域邊界附近的點(如點O)，利用其所在立體頂點進行插值，則不能得到正確結(jié)果。圖1中O所在的立方體，至少有點A，B不在色域內(nèi)部，也就是說，點A，B在表中沒有合法的輸出。這就是無法對點O的輸出進行快速插值的原因。

將圖像邊界處理的外推思想引入，利用外推策略處理色域邊界。如圖1所示，如果需賦予點A，B輸出值，只要插值計算出的色域內(nèi)部的點的輸出正確，就能夠用其外推出A，B值。

圖1 色域邊界外推

如圖2所示，立方體T被色域外殼分成兩部分，頂點A，B在色域內(nèi)部，其他頂點均在色域以外。如果能夠得到色域外的頂點所對應(yīng)的查找表輸出(如C點輸出記為F(C))，就能夠?qū)β湓诖肆⒎襟w以內(nèi)的色域內(nèi)的點進行插值。因為外頂點的輸出需要滿足色域內(nèi)部點的插值要求，所以其輸出要根據(jù)色域內(nèi)部點的輸出來確定，F(xiàn)(C)應(yīng)該是F(A)和F(B)的函數(shù)。

圖2 色域外頂點

文中使用了簡單的線性函數(shù)來確定色域外的頂點輸出。如圖2所示，連接線段AC，BC，線段同色域外殼的交點分別為E，F(xiàn)?？疾炀€段AC，根據(jù)簡單線性函數(shù)，下式成立:

|AE||AC|=|F(A)F(E)||F(A)F(C)| (1)

式中:|F(A)F(E)|表示A，E所對應(yīng)的輸出的點所連接線段的長度。其中F(A)，F(xiàn)(E)都可以求出，根據(jù)式(1)可以計算得到FA(C)。用色域內(nèi)頂點B亦能夠得到頂點C的輸出FB(C)，如果用兩者的算術(shù)平均值，誤差會相應(yīng)減小:

F(C)= FA(C)+FB(C) 2(2)

這樣，根據(jù)立方體落在色域內(nèi)部的點(包含頂點)的輸出，就能夠?qū)⒙湓谏蛲獾牧⒎襟w頂點的輸出計算出來。外推擺脫了對色域不規(guī)則邊界部分的繁瑣的處理，大大提高了處理速度。

2.3 色域匹配技術(shù)

外推技術(shù)解決了色域內(nèi)邊界點的處理問題，而色域外的點需要先映射到色域內(nèi)，然后再處理，即必須先進行色域匹配。本文采用了一種改進的裁減匹配算法。

判斷點在色域內(nèi)外的思想是:從色域內(nèi)的參考點R向該點P引一條射線，求該射線同色域外殼(用三角形面片描述)的交點，然后判定交點同點P的位置關(guān)系，從而判斷點P在色域內(nèi)外。

射線同色域外殼的交點即射線同色域外殼某一三角形面片的交點，求交點的過程即是判定射線與哪一個三角形面片所決定的平面的交點在該三角形面片的內(nèi)部。

如圖3所示，任意一三角形面片ABC，其外接圓的圓心為CP，半徑為R。如果要判定射線l與三角形面片是否相交，可以首先計算圓心CP到射線l的距離d，如果d大于R，則三角形面片不可能與射線相交，否則再進一步計算射線同三角形面片所在平面的交點并判定該交點是否在三角形面片上。

圖3 裁剪匹配

設(shè)射線L的方向向量為 s ，點M為射線L上任意一點，則圓心CP到射線L上的距離為:

d= |CPM × s | | s |(3)

如果d≤R，而且射線L同三角形面片所在平面F不平行，將射線參數(shù)方程代入平面F的方程，可以得到交點Q的坐標(biāo)。設(shè)三角形ABC，ACQ，ABQ，BCQ的面積分別為Δ，Δ1，Δ2，Δ3，如果:

Δ1+Δ2+Δ3>Δ (4)

成立，則點Q在三角形面片的內(nèi)部。其中Δi(如三角形ABC)的計算公式為:

Δi=|AB ×AC | (5)

在最壞的情況下，對色域外殼的n個三角形面片都要進行第一步(時間復(fù)雜度為O(n))的判定;對符合條件的三角形面片進行第二步(約40步乘法和35次加法)判定。第二步的判定雖然比較復(fù)雜，但是由于經(jīng)過第一步運算剔除了大部分不符合要求的面片，所以總的算法復(fù)雜度不大。

對圖像的每一像素顏色都執(zhí)行這種判斷操作在時間上不能滿足要求。為了快速地判斷每一顏色與色域的內(nèi)外關(guān)系可以建立二維查找表。該查找表分別以色調(diào)角α和經(jīng)過參考點和該點的線段與L*的夾角β為地址進行查表。利用該二維查找表，可快速插值計算|RP′|，在通過比較|RP′|與|RP|的大小，即可判定P點在色域內(nèi)外。

3 實驗及結(jié)論

反向均勻化后，在應(yīng)用三維查找表進行彩色校正時都可以一步定位查找點的位置，所以反向均勻化的步長對校正速度的影響非常小，但是對校正的精度影響仍然較大。由實驗知，當(dāng)三維查找表級數(shù)為9時可以獲得較好的精度[2]。

應(yīng)用反向均勻化建立的三維查找表，綜合了色域匹配和色彩校正的功能，對于任何屬于原色域的輸入都可以快速校正輸出。圖4是應(yīng)用了反均勻化三維插值技術(shù)進行彩色轉(zhuǎn)換的校正效果圖。主要硬件實驗環(huán)境是主頻為733 MHz的PC 機和HP DeskJet 880C彩色噴墨打印機，軟件環(huán)境是Visual C++6.0企業(yè)版和Photoshop。

圖4 實驗結(jié)果

4 結(jié) 語

本文對反向均勻化過程中如何快速定位非均勻空間的三維查找表的四面體、邊界點的外推處理和色域匹 配等幾個關(guān)鍵問題做了研究，給出了解決辦法。利用圖像邊界處理的外推思想得出了色域邊界點插值模型，提高了插值的校正速度;討論了色域匹配的裁剪匹配算法并提出了利用二維查找表來提高算法效率的思想，縮短了判斷時間，降低了算法復(fù)雜度。最后通過實驗驗證了反向均勻化算法，給出了實驗效果圖。

參考文獻

[1]喬新亮，曾平.使用3D-LUT的黑色生成算法[J].計算機工程，2002，28(6):222-223.

[2]楊懌菲.一種基于圖像特征的圖像分類方法[J].現(xiàn)代電子技術(shù)，2009，32(14):81-86.

[3]KANG H R. Printer-related color processing techniques[ J] . Proceedings of SPIE，1995， 2413: 410-419.

[4]修曉杰，王小華，朱文華.打印機顏色管理模型方法研究.寧波大學(xué)學(xué)報:理工版，2004，17(2):207-210.

[5]International Color Consortium. ICC Profile Specification[ M] . USA:ICC， 2001.

[6]史瑞芝.用查表插值法實現(xiàn)CIEL*a*b*與CMYK顏色空間的轉(zhuǎn)換[J].測繪學(xué)院學(xué)報，2002，19(3):224-229.

[7]SONKA M， HLAVAC V， BOYLE R. Image processing， analysis， and machine vision[ M] . 2nd Version. Bejing: PPTPH Thomson Learning， 2002.

[8]黃慶梅，趙達尊.一種彩色打印機標(biāo)定的預(yù)測查找方法[ J] .北京理工大學(xué)學(xué)報，2003，23(5):601-603.

[9]丁二銳，曾平.非均勻三維查找表的快速查找技術(shù)[J].計算機科學(xué)，2007，34(2):258-276.

[10]CHOLEWO T J. Black generation using lightness scaling[ J] .SPIE， 2000(3963): 323-328.