李紅林，蘭美輝，張順吉，楊 莉

(1.曲靖師范學院計算機科學與工程學院，云南 曲靖655011;2.云南中醫(yī)學院現(xiàn)代教育技術中心，云南 昆明650200)

基于投影法實現(xiàn)矩形窗口的任意曲線裁剪

李紅林1，蘭美輝1，張順吉1，楊 莉2

(1.曲靖師范學院計算機科學與工程學院，云南 曲靖655011;2.云南中醫(yī)學院現(xiàn)代教育技術中心，云南 昆明650200)

對含有任意曲線的圖像進行二值化后，針對某一矩形區(qū)域，對曲線上的點進行水平和垂直投影，投影后若在該矩形區(qū)域內(窗口內)，給予顯示;否則在窗口外，裁剪掉(即不顯示).該方法能動態(tài)的定義矩形窗口大小，能對任意規(guī)則曲線(如圓)和不規(guī)則曲線(如Bezier曲線、B樣條曲線)進行裁剪.該方法簡單、高效.

投影;矩形窗口;曲線;裁剪

裁剪問題是計算機圖形學的基本問題之一.裁剪是裁去窗口之外物體的一種操作.裁剪的目的是判斷圖形元素是否在所考慮的區(qū)域內，如在區(qū)域內，則進一步求出區(qū)域內的那一部分［1］.常用的直線裁剪算法有Cohen－Sutherland算法［2］、中點裁剪算法、梁友棟－barskey算法［3］.工程中常用到的曲線有2種:一種是規(guī)則曲線，可以用曲線方程式來表示，例如:圓、橢圓、拋物線、雙曲線、正弦余弦曲線等;另一種是不規(guī)則曲線(也稱自由曲線)，此類曲線形狀較復雜，不能確切給出描述整個曲線的方程，它們通常是實際測量得到的一系列離散點用曲線擬合方法來逼近的.如B樣條曲線、Bezier曲線、Hermite樣條曲線等.目前，研究直線、曲線、多邊形的裁剪方法比較多［4－7］，但大多數(shù)方法都要求與窗口邊界的交點，計算量較大，方法較復雜.本文提出基于矩形窗口的曲線裁剪方法，思想較簡單，能實現(xiàn)任意的直線、曲線的準確裁剪.

1 規(guī)則曲線裁剪

1.1 二值化

假定:曲線的顏色為ForeColor，背景的顏色為BackClor.從上到下，從左到右逐行、逐列掃描圖像中的每個像素點，分2種情況:一是該像素點的顏色是ForeColor，則分別統(tǒng)計其在水平、垂直方向上的像素個數(shù)，即為水平、垂直方向的投影值，如果該點的水平、垂直投影都在指定的矩形窗口內，則此點就是曲線上且在窗口內的點，應保留(不改變顏色)，否則應裁剪掉，把該點的顏色變?yōu)锽ackColor;二是該像素點的顏色不是ForeColor，那么說明該點不是曲線上的點，把其顏色置為BackColor.

1.2 投影法實現(xiàn)圓裁剪

常見的曲線裁剪的基本思想是:假設矩形窗口的最左邊為RLeft，最右邊為RRight，最上邊為RTop，最下邊為RBottom.對曲線進行裁剪，若當前點的值為RValue，根據(jù)曲線方程，判斷該點是否在曲線上，如果不在，則不考慮;如果在，且RBottom≤RValue≤RTop，RLeft≤RValue≤RRight同時滿足，那么說明此點在曲線上且在窗口之內，保存之;若RVuale＜RBottom或RValue＞RTop或RValue＜RLeft或RValue＞RRight，則此點在曲線上但在窗口之外，應去除;此方法，實現(xiàn)方法非常簡單，但是需要逐點判斷一個點是否在曲線上，計算量大且比較費時.

目前關于矩形窗口的圓裁剪問題常用的方法是判斷一個圓是否完全在窗口內(完全可見)或是否完全在窗口外(完全不可見).如果是，則算法結束;如果不是，則把圓按一定的順序對各邊界進行裁剪［8］.此方法每進行一個窗口邊就要計算該窗口邊與圓的交點，并判斷其是否在該邊界上還是在延長線上，計算量大.孫巖等［9］結合此方法，充分利用矩形和圓的對稱性提出了矩形窗口的曲線裁剪算法，能減少圓與窗口邊界求交的次數(shù)，與文獻［8］的方法相比，計算量一定程度上減少了.但是，此方法仍然要與窗口邊界求交.本文提出的基于投影法實現(xiàn)矩形窗口的任意曲線的裁剪，方法簡單，準確率高，同時不用計算曲線與窗口邊界的交點.

投影法是沿著圖像某個方向截面的灰度值累加計算量的集合.投影分為水平投影和垂直投影.對圖1(a)中的圓進行水平、垂直投影分別為圖1(b)、(c)，圖1(a)與矩形窗口的位置關系如圖2(a)，此時若圓上的某點的值為RValue，且RBottom≤RValue≤RTop，RLeft≤RValue≤Rright，則說明該點是在矩形窗口內的點，應該顯示(即保留)，否則，該點是窗口外的點，不顯示(即裁剪掉).圖2(b)為圓被矩形窗口裁剪后的結果圖.

2 不規(guī)則曲線裁剪

2.1 投影法實現(xiàn)三次Bezier曲線裁剪

Bezier曲線表達式為:

三次Bezier曲線，由4個點P0，P1，P2，P3可定義1條三次Bezier曲線，即n=3.可寫成:

Bezier曲線方法具有很強的幾何特征，在計算數(shù)學中起重要作用［10］.對圖3(a)中的三次Bézier曲線，進行水平、垂直投影分別為圖3(b)、(c).

基于如圖4(a)的矩形窗口，直接對三次Bezier曲線進行水平、垂直投影，如圖4(b)所示，投影區(qū)域分別為 RH，RV，若RLeft≤RV≤ RRight，且RBottom≤RH≤RTop，即該區(qū)域在窗口之內，把該區(qū)域所對的點恢復顯示出來.否則，該區(qū)域不在窗口內，應去除，處理后如圖4(c)所示.此方法不需要逐點判斷是否在曲線上，方法簡單，運行速度比較快.

2.2 投影法實現(xiàn)三次B樣條曲線裁剪

B樣條曲線:給定m+n+1個頂點Pi(i=0，1，2，…，m+n)，可以定義 m+1段n次參數(shù)曲線:

其中:Pk，n(t) 為第 k 段 n 次 B 樣條曲線段(k=0，1，…，m);Fi，n(t) 為 n 次 B 樣條基函數(shù)，其形式為:

三次 B 樣條曲線(即 n=3，i=0，1，2，3)，可寫成:

對圖5(a)中的B樣條曲線進行水平、垂直投影分別如圖5(b)、(c)所示.

對圖5(a)關于某一矩形窗口(矩形窗口的大小可以隨機輸入)進行水平、垂直投影，投影后在窗口內的部分說明是應保留的，顯示出來;反之，在窗口外的部分應被裁剪掉，不顯示.圖5(a)基于某一矩形窗口的上下邊界內的部分的水平投影如圖6(a)所示;左右邊界內的部分的垂直投影如圖6(b)所示，投影值既在上下邊界內又在左右邊內的部分，即為在窗口內的部分(裁剪結果)，應顯示，如圖6(c)所示.

3 裁剪流程框圖

流程圖見圖7.

4 結語

本文提出的方法，除了能對圓、Bezier曲線、B樣條曲線裁剪外，還能裁剪任意曲線、多邊形等復雜圖形，同時可以動態(tài)地輸入窗口的大小.方法簡單，速度快，裁剪的準確率高.但是，此方法只適合于裁剪的窗口為矩形.下一步研究的重點是實現(xiàn)關于任意窗口的曲線裁剪.

［1］銀紅霞，杜四春，蔡立軍，等.計算機圖形學［M］.北京:中國水利水電出版社，2009.

［2］曲毅，李存華.二維線段裁剪算法的分析與探索［J］.計算機應用與軟件，2006，23(7):113－114.

［3］LIANG Y D，BARSKY B A.A new concept and method for line clipping［J］.ACM Trans On Graphics，1984，3(1):1 －22.

［4］MAILLOT P G.A new，fast method for 2D polygon clipping:analysis and software implementation［J］.ACM Trans On Graphics，1992，11(15):276 －290.

［5］LIANG Y D，BARSKY B A.An analysis and algorithm for polygon clipping［J］.Communication of the ACM，1983，26(11):868 －877.

［6］趙平，馮春，李柏林.一般多邊形窗口的有效線裁剪算法［J］.西南交通大學學報，2004，39(1):64－68.

［7］杭后俊，孫麗萍.任意多邊形窗口的圓裁剪算法［J］.計算機技術與發(fā)展，2009，19(5):235－241.

［8］劉勇奎.計算機圖形學的基本算法［M］.北京:科學出版社，2001，62－70.

［9］孫巖，唐棣.矩形窗口的曲線裁剪算法［J］.計算機應用與軟件，2003，(05):35－36.

［10］于巍.隨機函數(shù)的Bezier逼近問題［J］.云南民族大學學報:自然科學版，2009，18(2):117－119.

(責任編輯莊紅林)

Random Clipping of Curves in Rectangular Windows Based on the Projection Method

LI Hong-lin1，LAN Mei-hui1，ZHANG Shun-ji1，YANG Li2
(1.School of Compute Science and Engineering，Qujing Normal University，Qujing 655011，China;2.Modern Education Technology Center，Yunnan University of Traditional Chinese Medicine，Kunming 650200，China)

Images with curves are binarized，and then horizontal and vertical projections are done to the points of the curves to a certain rectangular window.It aims to test whether the points are inside the rectangular region(or inside the window)or not after the projections.If they are inside the window，they should be displayed，otherwise，they should be clipped(not to be displayed).In this way the size of the rectangular window can dynamically be defined，and clipping can be done to any regular curves(for example，circles)or irregular curves(for example，Bezier curves，B － Spline curves).This method is simple and efficient.

projection;rectangular window;curve;clipping

TP 391.41

A

1672－8513(2011)02－0132－04

10.3969/j.issn.1672 －8513.2011.02.014

2010－09－16.

曲靖師范學院青年項目(2009QNO28).

李紅林(1980－)，女(彝族)，講師，碩士.主要研究方向:計算機圖像處理與模式識別.