視頻顯示器四基色有序平滑顯示算法研究

吳偉琦

(1．廣西工業(yè)職業(yè)技術學院建筑工程系, 中國 南寧 530001；2．桂林師范高等?？茖W校數(shù)學與計算機科學系,中國 桂林 541001；3．百色學院科研處，中國 百色 533000)

在計算機視頻監(jiān)示器和電視機視頻顯示中的色彩是通過紅(R)、綠(G)、藍(B)3種基色來具體體現(xiàn)的，每種基色各有0～255共256種色階，3種基色的色階的每種組合代表一種顏色，改變視頻監(jiān)視器中某個顏色寄存器的值,在監(jiān)視器中即可產生出相應的可顯示顏色.

隨著視頻顯示技術的不斷發(fā)展,視頻顯示器上所能顯示的顏色也將會越來越多,基色的種數(shù)也將不局限于3種,各種基色的色階的取值范圍也將不局限在0～255之間.

文獻[1]討論了三基色的色彩的有序平滑顯示算法,且只研究了每種基色取值范圍都是0～255的情形，文獻[2]討論了三基色的基色色階的取值范圍不同時的有序平滑顯示算法．本文利用圖論的方法從理論上討論基色種數(shù)為4種且每種基色的色階取值范圍不同的情形下的有序平滑顯示算法.

1 基本概念

類似于文獻[1]給出下列基本概念：

定義1稱C(g1,g2,g3,g4)為色彩函數(shù)，其中g1,g2,g3,g4為色彩的4種基色的色階,C(g1,g2,g3,g4)是由4種基色G1,G2,G3,G4的取值組合成的色彩值. 稱C(g1,g2,g3,g4)組成的集合為色彩集,記作

C={C(g1,g2,g3,g4)|0≤gj≤rj,(gj,rj是正整數(shù),j=1,2,3,4)}.

定義2對于色彩集C中的任意兩個不同的元素Cx=Cx(g1x,g2x,g3x,g4x)和Cy=Cy(g1y,g2y,g3y,g4y),定義函數(shù)關系：Φ(Cx,Cy)=|g1x-g1y|+|g2x-g2y|+|g3x-g3y|+|g4x-g4y|,若Φ(Cx,Cy)=1,則稱色彩值Cx和Cy是1-相鄰的, 此時稱Φ為色彩值1-相鄰規(guī)則.

對于色彩集C,根據(jù)色彩值1-相鄰規(guī)則,可以構造一個色彩值1-相鄰點對集：

D(C)={(Cx,Cy)|Cx,Cy∈C,且Cx≠Cy,Φ(Cx,Cy)=1}.

定義3對于任意的Cx,Cy∈D(C),構造一條邊連結Cx,Cy兩點,記為e(Cx,Cy),稱e(Cx,Cy)為色彩值1-相鄰規(guī)則Φ下的色彩相鄰邊.

顯然,所有色彩相鄰邊e(Cx,Cy)可構成一集合,記為E,即E={e(Cx,Cy)|Cx,Cy∈D(C)且Cx≠Cy}.

由以上三定義,可得到一種特殊的圖的定義.

定義4由色彩集C,色彩相鄰邊集E以及色彩值1-相鄰規(guī)則Φ構成的三元有序數(shù)組G=(C,E,Φ)稱為基于G1,G2,G3,G4的四基色的色彩圖,簡稱色彩圖.

顯然，以上定義的色彩圖與圖論中圖的概念是完全一致的，相應的色彩顯示問題就轉換成了圖論上著名的Hamilton圈存在性問題，也即在色彩圖上是否存在Hamilton圈. 于是，對于以上定義的色彩圖,若在其上存在Hamilton圈，則存在一個全部色彩的計算機平滑循環(huán)顯示算法.

本文以G1,G2,G3,G4為坐標軸構造四維空間坐標系,設g1,g2,g3,g4的取值范圍分別為: 0≤gj≤rj,(j=1,2,3,4),由此構造一個四維立方體,對該立方體施以長為1的劃分,則可形成一個四維立體圖G,由于色彩函數(shù)值C(g1,g2,g3,g4)與四基色G1,G2,G3,G4的取值是一一對應的,于是可將四維立方體上的點(g1,g2,g3,g4),(0≤gj≤rj,j=1,2,3,4),與色彩值C(g1,g2,g3,g4)相對應,顯然,四維立方體圖G與色彩圖是同構的,從而討論色彩圖的Hamilton圈的存在性,只需討論四維立方體圖G的Hamilton圈的存在性.

2 主要結果及證明

引理1[3]一個簡單無向圖為偶圖的充要條件是不含奇圈.

引理2[3]若G是Hamilton圖,則對V(G)的每個非空真子集S,均有ω(G-S)≤|S|. 其中ω(G-S)是圖(G-S)的連通分支數(shù).

定理1設四維立方體圖G=(C,E,Φ)中的頂點(g1,g2,g3,g4)各分量的取值范圍為: (0≤gj≤rj,j=1,2,3,4),則G存在Hamilton圈的充要條件是r1,r2,r3,r4中至少有一個為奇數(shù).

證必要性的證明，因為四維立方體圖G=(C,E,Φ)的頂點數(shù)等于(r1+1)(r2+1) (r3+1)(r4+1). 如果所有rj(j=1,2,3,4)為偶數(shù),則(r1+1)(r2+1) (r3+1)(r4+1) 為奇數(shù).又由于四維立方體圖G=(C,E,Φ)不存在奇圈,所以由引理3.1知它是偶圖,設此偶圖的二分類為{S1,S2},因|S1|+|S2|=(r1+1)(r2+1) (r3+1)(r4+1) 為奇數(shù),于是不妨設|S1|>|S2|,由偶圖的性質知G-S2=S1是G的獨立集,所以ω(G-S2)=|S1|>|S2|,根據(jù)引理3.2,四維立方體圖G=(C,E,Φ)不是Hamilton圖.

充分性的證明,若ri(i=1,2,3,4)中至少有一個為奇數(shù),不妨設r3是奇數(shù),此時只需在四維立方體圖G中找出一個Hamilton圈即可.現(xiàn)將G的頂點列成表1.

表1 四維立方體圖G的頂點

續(xù)表

續(xù)表

圖1 G中的一個Hamilton圈示意圖

顯然,表中任意相鄰的兩個頂點在圖G中也是相鄰的.因為r3是奇數(shù),所以表1排列的頂點共有偶數(shù)行,于是易找出四維立方體圖G的Hamilton圈,例如,如圖1所示的連接方式就構成四維立方體圖G中的一個Hamilton圈.

推論1[1]三維“格子籠”圖G=(V,E),其中

V={(r,g,b)|0≤r,g,b≤n且r,g,b和n是整數(shù),n≥1}

E={((rx,gx,bx),(ry,gy,by))||rx-ry|+|gx-gy|+|bx-by|=1}

則圖G存在Hamilton圈的充要條件是n為奇數(shù).

推論2[2]設三維“格子籠”圖G=(V,E)，其中

V={(r,g,b)|0≤r≤n1,0≤g≤n2,0≤b≤n3且r,g,b和ni是整數(shù),ni>1(i=1,2,3)},

E={((rx,gx,bx),(ry,gy,by))||rx-ry|+|gx-gy|+|bx-by|=1}.

則圖G存在Hamilton圈的充要條件是ni(i=1,2,3)中至少有一個為奇數(shù).

3 結束語

顯示技術從最初的單基色顯示、雙基色顯示到現(xiàn)今普遍使用的三基色顯示，且隨著科學技術的發(fā)展而不斷提高．目前對多基色顯示技術也在廣泛討論和研究，像四基色，六基色的LED顯示已開始應用了，本文討論的四基色平滑顯示算法為多基色技術提供了一個平滑顯示的理論依據(jù)．

參考文獻：

[1] 郭常忠, 王 敏. 一種基于RGB三基色的計算機色彩的有序顯示算法[J]. 計算機研究與發(fā)展, 1997, 34(4): 312-315.

[2] 李 政, 王 敏.“格子籠”圖的Hamilton圈問題[J]. 大學數(shù)學, 2007, 23(1): 147-150.

[3] BONDY J A, MURTY U S. Graph theory with applications[M]. London: Mac Millan Press, 1976.

[5] 唐干武, 唐高華, 王 敏. Erd?s-Sos猜想的一個結果[J]. 西南師范大學自然科學學報, 2009, 34(1): 24-27.

[6] WANG M, FANG X G. Parking a pair of graphs {(p,p-1),(p,p)} and slater’s problems[J]. J Chinese Syst Sci Math Sci, 1989, 9(2): 133-137.

[7] 唐干武，王 敏.包裝(p,p-2)圖和不含K3的(p,p+1)圖[J]. 江西師范大學自然科學學報,2005, 29(3): 220-223.

[8] YIN J H, LI J S. The Erd?s-Sòs conjecture for graphs whose complements contain noC4[J]. Acta Math Appl Sinica, 2004, 20(3): 397-400.

[9] WANG M, LI G J. On the a tree of orderpwith a (p,p+1)-graph[J]. J Syst Sci Comp, 2003, 16(1): 122-132.

[10] 方新貴, 王 敏. 包裝{(p,p-1),(p,p)}圖對和Slater問題[J]. 系統(tǒng)科學與數(shù)學, 1989, 9(2): 133-137.

[11] 唐干武, 王 敏. 一類圖的哈密頓分類[J]. 純粹數(shù)學與應用數(shù)學, 2009, 4(25): 711-715.

[12] 張智勇, 張遠平. 一些具有非固定步循環(huán)圖中生成樹的個數(shù)[J]. 湖南師范大學自然科學學報, 2007, 30(3): 18-21.