利用插值處理計算機圖形邊界鋸齒化問題

李 琦

內蒙古大學數學科學學院

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

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

圖1

圖2

名詞解釋

i 代表像素點，i=A,B,C,D,E,F,G；

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

模型建立

第一步：按兩個像素點的間距將位圖分為若干段，如圖2。

第二步：找出每個端點的坐標。

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

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

局部效果圖：

模型改進

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

第一步：按兩個像素點的間距將位圖分為若干段，如圖2。

第二步：找出每個端點的坐標。

第三步：以兩個斷點為一組，利用Lagrange 插值公式算出逼近函數。

第四步：把這些函數組合成分段函數表示出來。

其中，

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