计算机图形学 | 区域填充

区域填充算法详解从种子填充到多边形域填充前言在计算机图形学中区域填充是将指定区域内的所有像素置为新颜色的过程。这是图形处理、图像编辑、游戏开发等领域的基础操作。根据区域的定义方式区域填充主要分为两种类型1. 内定义区域区域内所有像素颜色相同区域外像素是另一种颜色。这种填充称为泛填充如图1所示。2. 边界定义区域区域边界像素是特定颜色区域内像素不取这个特定颜色。这种填充称为边界填充如图2所示。区域连通性种子填充算法要求区域具有连通性因为只有在连通区域中才可能将种子像素的颜色扩展到区域内的所有像素。根据区域的连通性可以将区域分为4连通区域像素在水平或垂直方向相邻8连通区域像素在水平、垂直或对角线方向相邻本文主要讨论边界定义的四连通区域填充算法。3.1 种子填充算法种子填充算法是从区域内的一个点称为种子开始由内向外扩展到整个区域的填充过程。该方法适用于交互绘图。3.1.1 简单种子填充算法算法步骤种子像素坐标入栈当栈非空时取出栈顶像素坐标栈空时结束将出栈像素置成填充色检查出栈像素的左、上、右、下4个相邻像素如果像素不在边界上或未被置为区域颜色则将其坐标入栈重复步骤24例3.1 详细推演设种子像素坐标为(3,2)填充过程如下种子像素(3,2)入栈出栈(3,2)并着色。入栈(2,2)、(3,3)、(4,2)、(3,1)出栈(3,1)并着色。入栈(2,1)、(4,1)出栈(4,1)并着色。入栈(4,2)此前已入栈此处为重复入栈出栈(4,2)并着色出栈(2,1)并着色。入栈(2,2)此前已入栈出栈(2,2)并着色。入栈(1,2)、(2,3)出栈(2,3)并着色。入栈(3,3)此前已入栈此处为重复入栈出栈(3,3)并着色出栈(1,2)并着色出栈(4,2)并着色此前已出栈着色此处为重复处理出栈(4,3)并着色此前已出栈着色此处为重复处理出栈(2,2)并着色此前已出栈着色此处为重复处理栈空结束算法分析从以上过程可以看出此方法可以实现带内孔的平面区域填充但其缺点是会把一些像素重复入栈降低了算法的效率。出现重复入栈的情况是因为一些已入栈的像素未及时着色后续检测时仍会被判定为未处理而重复入栈。3.1.2 改进的简单种子填充算法为了消除重复入栈可在入栈前为像素着色提前标记为已处理。算法步骤种子像素坐标入栈并着色当栈非空时取出栈顶像素坐标栈空时结束检查出栈像素的左、上、右、下4个相邻像素如不在边界上或未被置为区域内颜色则将其坐标入栈并立即着色重复步骤2和3例3.1 改进算法推演种子像素(3,2)入栈并着色出栈(3,2)。入栈(2,2)、(3,3)、(4,2)、(3,1)并着色出栈(3,1)。入栈(2,1)、(4,1)并着色出栈(4,1)出栈(2,1)出栈(4,2)出栈(3,3)。入栈(2,3)并着色出栈(2,3)出栈(2,2)。入栈(1,2)并着色出栈(1,2)栈空结束算法对比特性简单种子填充改进的简单种子填充入栈次数13次10次重复入栈有无入栈像素数大于区域像素数等于区域像素数存储空间较大较大但更优可以看出改进算法中入栈像素的个数就是区域内像素的个数没有重复入栈。但此方法仍要求较大的存储空间以实现栈结构。3.1.3 简单种子填充算法程序设计简单种子填充算法的步骤是一个递归过程可以采用递归调用设计填充函数。// 参数(xz,yz)为种子坐标InColor为区域填充颜色EdgeColor为区域边界颜色voidFill1(CDC*p,intxz,intyz,COLORREF InColor,COLORREF EdgeColor){BOOL ttrue;// 检查当前像素是否为边界颜色或已填充if(p-GetPixel(xz,yz)!EdgeColorp-GetPixel(xz,yz)!InColor){p-SetPixel(xz,yz,InColor);// 填充当前像素// 递归检查四个相邻像素Fill1(p,xz-1,yz,InColor,EdgeColor);// 左Fill1(p,xz,yz-1,InColor,EdgeColor);// 上Fill1(p,xz1,yz,InColor,EdgeColor);// 右Fill1(p,xz,yz1,InColor,EdgeColor);// 下}}3.1.4 扫描线种子填充算法上述的简单种子填充算法是孤立地对单个像素进行搜索未考虑像素间的连贯性。如果一个像素在区域内其左右像素也可能在区域内直到遇到边界像素为止。所以在一个连贯的水平区段内只需找一个像素点。这里的区段是指区域内相邻像素在水平方向的组合它的两端以具有边界颜色值的像素为边界其中间不包括具有边界颜色值的像素。对于区域内的每一像素段可以只保留其最右或左端的像素作为种子像素。因此区域中每一个未被填充的水平像素段至少有一个像素是保存在栈中。扫描线种子填充算法适用于边界定义的区域区域可以是凹型或凸型也可以包含一个或多个孔。算法步骤种子像素入栈。当栈非空时栈顶像素出栈否则结束。沿扫描线对出栈像素及左边和右边像素填充直到遇到左记为 xl、右记为 xr边界为止。在 [xl, xr] 区间内检查与当前扫描线相邻的上、下两条扫描线中是否存在非边界或未填充的像素如果存在则将每一区间段的最右边或最左边的像素取作种子入栈。用此算法填充例 3.1 区域时栈的深度最大为 3从而解决了简单种子填充算法存在的大栈深度问题。C 代码实现voidFull3(CDC*p,intxz,intyz,COLORREF InColor,COLORREF EdgeColor){inttop0,z[500][2],x0,y0,xr,xl,xn,flag;z[top][0]xz,z[top][1]yz;// 种子像素入栈while(top0){xzz[top][0],yzz[top][1],top--;// 栈顶像素出栈x0xz,y0yz;p-SetPixel(x0,y0,InColor);// 填充当前像素// 向种子像素右边填充while(p-GetPixel(x01,y0)!EdgeColorp-GetPixel(x01,y0)!InColor){x0;p-SetPixel(x0,y0,InColor);}xrx0;// 记录右边界// 向种子像素左边填充x0xz;while(p-GetPixel(x0-1,y0)!EdgeColorp-GetPixel(x0-1,y0)!InColor){x0--;p-SetPixel(x0,y0,InColor);}xlx0;// 记录左边界// 检查上、下相邻扫描线将每段未填充区间的种子入栈flag1;// 标记是否向上传入栈xnxl;y0yz-1;// 扫描上一行while(xnxr){// 在上一行寻找未填充像素段将最右像素入栈while(xnxr(p-GetPixel(xn,y0)EdgeColor||p-GetPixel(xn,y0)InColor))xn;if(xnxr){flag1;while(xnxrp-GetPixel(xn,y0)!EdgeColorp-GetPixel(xn,y0)!InColor)xn;top;z[top][0]xn-1;// 段最右像素入栈z[top][1]y0;}while(xnxr(p-GetPixel(xn,y0)EdgeColor||p-GetPixel(xn,y0)InColor))xn;}// 扫描下一行逻辑同上y0yz1;xnxl;while(xnxr){while(xnxr(p-GetPixel(xn,y0)EdgeColor||p-GetPixel(xn,y0)InColor))xn;if(xnxr){while(xnxrp-GetPixel(xn,y0)!EdgeColorp-GetPixel(xn,y0)!InColor)xn;top;z[top][0]xn-1;z[top][1]y0;}while(xnxr(p-GetPixel(xn,y0)EdgeColor||p-GetPixel(xn,y0)InColor))xn;}}}例3.2 扫描线种子填充用扫描线种子填充算法填充图 3-8 所示的区域。该区域为12×12网格的C形带缺口布局种子⑩位于(4,6)共有35个边界像素、38个内部像素。步骤1出栈(4,6)沿扫描线向左填充至(4,3)向右填充至(4,10)。填充行4 [3,10]覆盖⑦⑧⑨⑩⑪⑫⑬⑭共8个像素。在 [3,10] 区间内检查上行行3发现未填充段[4,9]将最右像素(3,9)入栈下行行5发现两个未填充段[3,4]入栈(5,4)、[8,10]入栈(5,10)栈状态(3,9) ← (5,4) ← (5,10)。步骤2出栈(5,10)沿扫描线向左填充至(5,8)向右填充至(5,11)。填充行5 [8,11]覆盖⑱⑲⑳21共4个像素。在 [8,11] 区间内检查上行已填充下行行6发现未填充段[9,11]将最右像素(6,11)入栈栈状态(3,9) ← (5,4) ← (6,11)。步骤3出栈(6,11)沿扫描线向左填充至(6,9)向右填充至(6,11)。填充行6 [9,11]覆盖25 26 27共3个像素。在 [9,11] 区间内检查上行已填充下行行7发现未填充段[9,10]将最右像素(7,10)入栈栈状态(3,9) ← (5,4) ← (7,10)。步骤4出栈(7,10)沿扫描线向左填充至(7,9)向右填充至(7,10)。填充行7 [9,10]。在 [9,10] 区间内检查上行已填充下行行8发现未填充段[9,10]将最右像素(8,10)入栈栈状态(3,9) ← (5,4) ← (8,10)。步骤5出栈(8,10)沿扫描线向左填充至(8,5)向右填充至(8,10)。填充行8 [5,10]。在 [5,10] 区间内检查上行行7发现未填充段[5,5]将(7,5)入栈下行已填充或边界栈状态(3,9) ← (5,4) ← (7,5)。步骤6出栈(7,5)沿扫描线向左填充至(7,2)向右填充至(7,5)。填充行7 [2,5]。在 [2,5] 区间内检查上行行6发现未填充段[2,4]将最右像素(6,4)入栈下行已填充栈状态(3,9) ← (5,4) ← (6,4)。步骤7出栈(6,4)沿扫描线向左填充至(6,2)向右填充至(6,4)。填充行6 [2,4]。在 [2,4] 区间内检查上行行5发现未填充段[2,4]将最右像素(5,4)入栈下行已填充栈状态(3,9) ← (5,4) ← (5,4)。注意此时栈中有两个(5,4)分别来自步骤4的下行检查和本步骤的上行检查。步骤8出栈(5,4)沿扫描线向左填充至(5,2)向右填充至(5,4)。填充行5 [2,4]覆盖⑯⑰两格注意⑰已被前一步骤填充过此行实际新增填充仅为⑯。在 [2,4] 区间内检查上行已填充下行已填充栈状态(3,9) ← (5,4)。步骤7入栈的另一个(5,4)仍在栈中。步骤9出栈(5,4)填充行5 [4,4]。但此行⑰位置已全部被填充故此行无新填充。栈状态(3,9)。步骤10出栈(3,9)沿扫描线向左填充至(3,4)向右填充至(3,9)。填充行3 [4,9]覆盖①②③④⑤⑥共6个像素。在 [4,9] 区间内检查上行行2全为边界下行行4已填充无新种子入栈。栈空填充结束。共10次出栈38个内部像素全部着色。图3-10 扫描线种子填充最终结果对比简单种子填充算法每次只填一个像素需38次出栈扫描线种子填充算法将每个水平连续段作为一个处理单元将出栈次数从38次减少到10次效率提升约4倍适用于大面积区域填充。3.2 多边形域填充多边形域可以是凸型或凹型也可以内带孔。常用的填充方法是按扫描线顺序先计算扫描线与多边形的相交区间再用要求的颜色显示这些区间的像素即完成填充称为扫描线填充算法。区间的端点是扫描线与多边形边界线的交点。该方法适用于自动填充。3.2.1 多边形域的填充步骤计算扫描线与多边形边的交点后必须把交点序列按x值递增或递减顺序重新排列才能正确得到每个需要填充的区间。对于一条扫描线填充过程分为以下4个步骤求交计算扫描线与多边形各边的交点排序把所有交点按x值递增顺序排序交点配对将第1个与第2个、第3个与第4个等交点两两配对每对交点代表扫描线与多边形的一个相交区间区间填色把这些相交区间内的像素置为多边形的颜色3.2.2 顶点交点异常处理当用间隔为1个像素的多个扫描线填充多边形域时扫描线一定会与多边形顶点相交这时会出现异常情况。异常情况分析如图3-10所示扫描线2与多边形的B、G、H、N相交。当计算扫描线2与多边形各边的交点时B会被计算两次导致扫描线2与多边形的交点序列为B、B、N与GH线段重合有无穷的交点不计入。按前述算法对交点按x值进行排序后再两两配对时会误将区间[B, B]取多边形颜色而真正的[B, N]多边形内部区间的像素反而未填充。解决方案1取舍交点个数从出现的异常情况来看当扫描线与多边形顶点相交时设相同的交点只取1个。这样扫描线2与多边形边的交点序列就变成B、N符合预期。然而如果按此规定扫描线4与多边形的交点序列会变为O、F、I、P这将导致错把[F, I]区间判定为多边形外部。为了正确地进行取点必须对上述两种情况区别对待当共享顶点的两条边落在扫描线上下两侧时交点只算1个当共享顶点的两条边落在扫描线同一侧时交点算作0个或2个具体实现时只需检查顶点两边的另外两个端点扫描线2交于顶点B由于共享该顶点的两条边的另外两个顶点分别高于和低于扫描线2故交点B取1次扫描线4在F处共享该顶点的两条边的另外两个顶点都高于扫描线4故取交点F 2次或0次在I处共享该顶点的两条边的另外两个顶点均低于扫描线4所以扫描线4与之相交时交点I取2次或0次解决方案2扫描线抬高0.5方法在进行交点计算时如果扫描线都不经过多边形顶点则交点配对时不会出现异常情况。因此在判断扫描线与多边形边是否有交点时将扫描线抬高或降低0.5个单位如图3-11中的点虚线所示。具体实现当判断扫描线4与多边形各边是否有交点时用扫描线4.5进行判断可得出与AB、DE、EF、FA四条边有交点即4个交点当计算4个交点的坐标值时再将扫描线4.5还原为扫描线4计算出的4个交点排序后为O、F、P、I与前面取舍交点个数的方法结果一致再看扫描线2用扫描线2.5进行判断得出与AB、DE、GH、HI这4条边有交点当计算AB边的交点时使用扫描线2进行计算就可计算出交点为B与前面取舍交点个数的方法结果一致该算法的实现比较简单避免了复杂的顶点判断逻辑。3.2.3 直接求扫描线填充算法为计算每条扫描线与多边形各边的交点最直接的方法是把多边形的所有顶点坐标存入数组然后按顺序计算每条边与扫描线的交点。算法步骤建立边表(ET)将多边形的所有边按最小y值排序建立活动边表(AET)存储当前扫描线相交的边扫描线从上到下处理将y值等于当前扫描线的边从ET移到AET对AET中的边按x值排序填充交点之间的像素更新AET中边的x值根据斜率移除y_max等于当前扫描线的边算法复杂度分析时间复杂度O(n k)其中n为多边形边数k为填充像素数空间复杂度O(n)用于存储边表和活动边表课后习题习题3区域说明图为12×12网格种子⊕⑤位于(5,6)。共有13个边界像素红色圆圈和8个内部像素①④、⑥⑨其中⑤⊕为种子。四连通邻接关系如下像素左上右下①边界边界②④②①边界③⑤③②边界边界⑥④边界①⑤⑧⑤④②⑥边界⑥⑤③边界边界⑦边界边界⑧边界⑧⑦④边界⑨⑨边界⑧边界边界图3-32(b) 四邻域连通关系已知边界定义四连通区域如图3-32所示写出用改进后的简单种子填充算法填充该区域的入栈、填充、出栈的步骤种子像素为⑤像素入栈顺序为左、上、右、下。参考答案改进算法入栈即着色步骤操作栈内容顶→底已着色像素1种子⑤入栈并着色⑤⑤2出栈⑤④入栈着色、②入栈着色、⑥入栈着色④ ← ② ← ⑥②④⑤⑥3出栈⑥③入栈着色④ ← ② ← ③②③④⑤⑥4出栈③四邻均已着色/边界④ ← ②②③④⑤⑥5出栈②①入栈着色④ ← ①①②③④⑤⑥6出栈①四邻均已着色/边界④①②③④⑤⑥7出栈④⑧入栈着色⑧①②③④⑤⑥⑧8出栈⑧⑦入栈着色、⑨入栈着色⑦ ← ⑨①②③④⑤⑥⑦⑧⑨9出栈⑨四邻均已着色/边界⑦①②③④⑤⑥⑦⑧⑨10出栈⑦四邻均已着色/边界空①②③④⑤⑥⑦⑧⑨共10 步9 个内部像素全部着色栈空结束。画出用扫描线种子填充算法填充图3-32的过程种子为⑤像素入栈顺序为上、下。参考答案步骤1从种子⑤所在行5列6开始。向左填充至④列5向右填充至⑥列7。当前填充行5区间[5,7]④⑤⑥。检查上行行4在[5,7]范围内存在未填充段①②③将最右像素③入栈。检查下行行6在[5,7]范围内列5处有⑧未填充⑦在列4不在区间内将⑧入栈。栈状态③ ← ⑧。步骤2出栈⑧(6,5)。向左填充至⑦(6,4)遇边界止向右遇边界止。当前填充行6区间[4,5]⑦⑧。检查上行行5已填充。检查下行行7在[4,5]范围内列5处⑨未填充将⑨入栈。栈状态③ ← ⑨。步骤3出栈⑨(7,5)。左右均遇边界。填充行7 [5,5]⑨。检查上行行6已填充。检查下行全边界。无新种子入栈。栈状态③。步骤4出栈③(4,7)。向左填充至②(4,6)、①(4,5)遇边界止向右遇边界止。当前填充行4区间[5,7]①②③。检查上行行3全边界。检查下行行5已填充。无新种子入栈。栈空结束。共4 步4 次出栈9 个内部像素全部着色。总结算法对比算法类型优点缺点适用场景简单种子填充实现简单可处理带孔区域重复入栈效率低小区域交互填充改进种子填充无重复入栈效率较高仍需栈结构存储需求大中等区域填充扫描线种子填充效率高减少递归深度实现复杂大面积区域填充多边形扫描线填充适合自动填充效率高需要预处理边表多边形自动填充选择建议交互式应用选择种子填充算法实现简单响应快大面积填充选择扫描线种子填充或多边形扫描线填充效率高多边形填充选择扫描线填充算法支持凹凸多边形和带孔多边形实时应用考虑使用改进的种子填充或扫描线种子填充未来发展方向并行化填充利用GPU并行处理能力加速填充过程抗锯齿填充结合反走样技术提高填充质量渐变填充支持颜色渐变和纹理填充智能填充结合图像分割技术实现智能区域选择区域填充算法是计算机图形学的基础掌握这些算法对于图形编程、图像处理和游戏开发都至关重要。通过理解算法的原理和实现细节可以更好地选择和应用适合的填充方法。