利用插值處理計(jì)算機(jī)圖形邊界鋸齒化問題

李 琦

內(nèi)蒙古大學(xué)數(shù)學(xué)科學(xué)學(xué)院

在計(jì)算機(jī)領(lǐng)域，柵格化的逆過程比格柵化過程相對(duì)困難，它主要是對(duì)邊界鋸齒化的處理，而這種處理的方法很多，本文利用插值對(duì)邊界鋸齒化進(jìn)行處理。運(yùn)用的思想是位圖信息矢量化，而圖像的位圖信息是一個(gè)關(guān)于像素的數(shù)字矩陣，本文將這個(gè)位圖信息放在坐標(biāo)系中考慮。位圖的像素信息與原圖的信息有差異，這種差異是由圖像邊界占像素格的多少所決定的，因此計(jì)算機(jī)的位圖信息在邊界上不能代表真實(shí)的圖像信息。本文利用數(shù)值逼近思想，通過Lagrange 插值公式對(duì)問題進(jìn)行數(shù)學(xué)建模，使鋸齒狀的邊界光滑化，使不真實(shí)的位圖信息盡量趨近于真實(shí)圖像。

宏觀世界在我們眼中所展現(xiàn)的圖形的邊界一般是光滑的，圖像信息在計(jì)算機(jī)中保存時(shí)，將圖形轉(zhuǎn)化為像素點(diǎn)矩陣的形式呈現(xiàn)在我們眼前，通過對(duì)像素點(diǎn)矩陣的觀察我們發(fā)現(xiàn)在圖形的邊界上他不是光滑的，而是呈現(xiàn)為鋸齒狀，不具有光滑性，而實(shí)際圖形的邊界不會(huì)出現(xiàn)鋸齒信息，故需要對(duì)鋸齒狀的邊界做平滑處理?？梢钥紤]把這個(gè)位圖信息放在坐標(biāo)系中考慮，由計(jì)算機(jī)知識(shí)可知位圖的像素信息與原圖的信息有差異，這種差異是由圖像邊界占像素格的多少?zèng)Q定的，若所占本像素格的50%以上，則按滿格處理，若不滿50%，則忽略不計(jì)。那么計(jì)算機(jī)的位圖信息在邊界上不能代表真實(shí)的圖像信息（如圖1），為了方便解決問題在這里假定兩種情況出現(xiàn)的概率均為50%，且每個(gè)像素點(diǎn)為一個(gè)質(zhì)點(diǎn)。而我們只有位圖信息（如圖2），需要找出真實(shí)的圖像邊界，而真實(shí)的圖像邊界是千變?nèi)f化的，對(duì)于同一種位圖信息對(duì)應(yīng)許多的真實(shí)邊界，因此可以利用Lagrange 插值公式對(duì)真實(shí)邊界進(jìn)行逼近。

圖1

圖2

名詞解釋

i 代表像素點(diǎn)，i=A,B,C,D,E,F,G；

2.(xi,yi)表示像素點(diǎn)i 點(diǎn)的坐標(biāo)，為了方便書寫將i 記為i=1,2,…,k,…。其中k 代表上述所說(shuō)的像素點(diǎn)。

模型建立

第一步：按兩個(gè)像素點(diǎn)的間距將位圖分為若干段，如圖2。

第二步：找出每個(gè)端點(diǎn)的坐標(biāo)。

第三步：利用Lagrange 插值公式算出逼近函數(shù)。

其中，ωn+1(x)=(x-x0)(x-x1)…(x-xn)

局部效果圖：

模型改進(jìn)

由于把位圖邊界信息分為許多的斷點(diǎn)，如果把這些點(diǎn)依次進(jìn)行Lagrange 插值，會(huì)降低逼近的效果，所以進(jìn)行分段插值，以兩個(gè)段點(diǎn)為一組點(diǎn)進(jìn)行插值。

第一步：按兩個(gè)像素點(diǎn)的間距將位圖分為若干段，如圖2。

第二步：找出每個(gè)端點(diǎn)的坐標(biāo)。

第三步：以兩個(gè)斷點(diǎn)為一組，利用Lagrange 插值公式算出逼近函數(shù)。

第四步：把這些函數(shù)組合成分段函數(shù)表示出來(lái)。

其中，

雖然通過以上算法可以將鋸齒狀的邊界平滑化處理，但由于采用分段函數(shù)算法，故分段函數(shù)的數(shù)量無(wú)法控制在合理的范圍內(nèi)。而且該模型只改進(jìn)了邊界曲線的平滑性，不能完全消除鋸齒狀邊界，故鋸齒狀邊界仍然存在，但這個(gè)問題可以通過高階的插值方法解決，本文不再對(duì)此進(jìn)行詳細(xì)的說(shuō)明。