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

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

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

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

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

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

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

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

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

1 規(guī)則曲線裁剪

1.1 二值化

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

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

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

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

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

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

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

Bezier曲線表達(dá)式為:

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

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

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

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

B樣條曲線:給定m+n+1個(gè)頂點(diǎn)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)，可寫成:

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

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

3 裁剪流程框圖

流程圖見圖7.

4 結(jié)語

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

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

［2］曲毅，李存華.二維線段裁剪算法的分析與探索［J］.計(jì)算機(jī)應(yīng)用與軟件，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］.西南交通大學(xué)學(xué)報(bào)，2004，39(1):64－68.

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

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

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

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

(責(zé)任編輯莊紅林)

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.

曲靖師范學(xué)院青年項(xiàng)目(2009QNO28).

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