VB.NET中使用种子填充算法实现给图片着色的例子
某人最近在使用C#写一个类似Windows的画图工具,在填色的部分卡住了。劳资要他使用种子填充算法着色(不要调用Windows提供的API,否则还锻炼个毛线),现在我把这个功能实现了,程序的效率很高。现在在这里大概写一下实现方法。 程序是用VB.NET写的,C#写法类似(而且还不需要使用Marshal类访问非托管资源,更加方便)。程序的运行结果如下: 种子填充算法说白了就是宽度优先搜索算法(BFS),如果你不知道这是什么东西,那说明你数据结构根本就没有学,请自行补充相应的知识。 第一步:实现“铅笔”工具 我们定义如下的全局变量(窗体类的私有成员),作用是啥一看名字就知道: 复制代码 代码如下: Private Enum DrawStyle Drawing = 0 Fill = 1 DrawDragging = 2 End Enum Private _fillColor() As Color = {Color.Blue,Color.Green,Color.Red,Color.LightGray,Color.LightPink,Color.LightSkyBlue,_ Color.GreenYellow,Color.Gold,Color.LightSeaGreen} Private _drawStyle As DrawStyle = DrawStyle.Drawing Private _imgMain As Bitmap Private _g As Graphics Private _lastPosition As Point Private _drawingPen As Pen 这个程序中填充的颜色是随机决定的(都懒得做一个选颜色的功能了),可以填充的颜色在_fillColor数组中。_drawStyle定义当前的绘图模式(Drawing表示使用铅笔工具,但未按下,Fill表示准备填充,DrawDragging表示鼠标正按下并拖拽)。 _imgMain是绘制的图片,_g是创建在这个Bitmap上的Graphics对象。 需要注意的是,Drawing和Drawing2D类不提供画点的方法,我们需要通过画直线或画矩形来模拟。至于_lastPosition的作用,由于鼠标拖拽过程中,如果速度过快,那么MouseMove事件中的坐标点(每次MouseMove事件被触发)并不是连续的,所以我们需要在当前点和上一次的鼠标位置之间画一条直线,否则画出来的线是间断的。 MouseDown、MouseMove和MouseUp实现铅笔工具的基本功能,代码如下: 复制代码 代码如下: Private Sub PictureBox1_MouseDown(sender As Object,e As MouseEventArgs) Handles PictureBox1.MouseDown If CheckBox1.Checked Then _drawStyle = DrawStyle.Fill Else _drawStyle = DrawStyle.Drawing If _drawStyle = DrawStyle.Fill Then Call FillRegion(e.Location,_fillColor(New Random().Next(_fillColor.Count))) Else _drawStyle = DrawStyle.DrawDragging _lastPosition = e.Location End If End Sub Private Sub PictureBox1_MouseMove(sender As Object,e As MouseEventArgs) Handles PictureBox1.MouseMove If _drawStyle = DrawStyle.DrawDragging Then _g.DrawLine(_drawingPen,_lastPosition,e.Location) _lastPosition = e.Location PictureBox1.Image = _imgMain End If End Sub Private Sub PictureBox1_MouseUp(sender As Object,e As MouseEventArgs) Handles PictureBox1.MouseUp _drawStyle = DrawStyle.Drawing End Sub 二、正题――种子填充算法的实现 上面说了一堆废话,现在终于可以开始实现填充的算法了。 当用户点击图片中某一个点后,需要填充与这个点相邻的、颜色相同的其他点。为什么要叫“种子填充”呢?大概是这样:你在点中的那个点中播下一颗种子,它开花结果(颜色变成目标颜色),然后它又播种出新的种子(与它上下左右相邻且颜色等于原来颜色的点);新种子再开花结果(变颜色),播种新种子…… 如此往复,直到没有地方播种了为止,算法结束。 按照BFS通常的实现方式,可以使用循环队列作为数据结构。对于BFS算法来说,需要的存储空间较大,具体需要多少还真不好估算。这里给大家一个参考,我的这个程序图片框大小是832*450,大概是37万像素,循环队列的容量设置为1600可以满足需求(全部着色)。如果你的图片框比较大,可以先取一个较大的数值(比如8000),再逐渐缩小,反复尝试。 实现这个循环队列直接定义成一个一维数组就可以了,没有必要使用ConcurrentQueue类,否则性能会下降,也没有这个必要。 首先,由于要向四个方向填充,为了避免类似的代码反复写导致程序丑陋无比,我们可以定义一个fill_direction数组: 复制代码 代码如下: Dim fill_direction() As Point = {New Point(-1,0),New Point(1,New Point(0,-1),1)} 这样,使用一个For循环就可以完成四个方向的操作了。 按照首先说的思路,程序的实现就很简单了:首先将点击的那个点入队,记录这个点的颜色。然后使用一个循环,取出队首元素,并向四个方向撒种子(颜色相同,且没有越出图片框边界),将每一个种子的颜色改变成目标颜色并入队。如此往复直到队列为空为止。代码如下: 复制代码 代码如下: Private Sub FillRegion2(sourcePoint As Point,destinationColor As Color) Dim new_bitmap As Bitmap = DirectCast(PictureBox1.Image,Bitmap) Dim source_color As Color = new_bitmap.GetPixel(sourcePoint.X,sourcePoint.Y) Dim MIN_X As Integer = 0,MIN_Y As Integer = 0 Dim MAX_X As Integer = PictureBox1.Width - 1,MAX_Y As Integer = PictureBox1.Height - 1 Dim fill_queue(MAX_FILL_QUEUE) As Point Dim fill_direction() As Point = {New Point(-1,1)} Dim queue_head As Integer = 0 Dim queue_tail As Integer = 1 fill_queue(queue_tail) = sourcePoint Do While queue_head <> queue_tail queue_head = (queue_head + 1) Mod MAX_FILL_QUEUE Dim current_point As Point = fill_queue(queue_head) For i As Integer = 0 To 3 Dim new_point_x As Integer = current_point.X + fill_direction(i).X Dim new_point_y As Integer = current_point.Y + fill_direction(i).Y If new_point_x < MIN_X OrElse new_point_y < MIN_Y OrElse new_point_x > MAX_X OrElse new_point_y > MAX_Y Then Continue For If new_bitmap.GetPixel(new_point_x,new_point_y) = source_color Then new_bitmap.SetPixel(new_point_x,new_point_y,destinationColor) queue_tail = (queue_tail + 1) Mod MAX_FILL_QUEUE fill_queue(queue_tail) = New Point(new_point_x,new_point_y) End If Next Loop PictureBox1.Image = new_bitmap End Sub 可能会有一个问题,就是第一个点在入队前应该要先改成目标颜色,但我这里没有改。效果其实是一样的,因为它旁边的点在撒种子的时候发现这个点颜色没变,还是会将它入队(注意:如果只有一个点需要填充,即起始点没有相邻的点,那么会导致这个点不被填充成目标颜色,请自行改进算法)。我们在这里忽略这个小问题。 运行程序,可以发现已经可以实现填充的功能了。
三、提升效率 在运行程序时发现了一个问题,就是如果填色区域过大(比如直接填充整个图片框),程序会很慢,大概需要2秒左右才能填充完。产生这个问题的主要原因是GetPixel和SetPixel的性能不高,每次调用这两个方法时都会做很多额外的操作,在我以前使用汇编语言调用DOS中断画点时就有这个问题。 为此,M$提供了LockBits和UnlockBits方法。LockBits方法可以将图片锁定到内存中,以便通过访问内存直接对这些数据进行修改。在C#中我们可以直接使用指针访问这片数据,但对于VB是不行的,因为VB不允许使用指针,我们可以借助System.Runtime.InteropServices.Marshal类达到直接访问内存的功能。 关于LockBits的详细介绍可以参考这篇日志:http://www.bobpowell.net/lockingbits.htm 其中很重要的一点就是要搞清楚如何计算图片上某一点的内存地址。 如这张图所示(图片来自那篇博文),坐标为(X,Y)的点在内存中的地址就是Scan0 + (Y * Stride) + X * k。k与图片中每个点占用的字节有关,我们这里使用的是32位ARPG,每个像素占4个字节,因此k就是4。另外注意Stride并不一定是n*k(n表示每行存n个像素),因为末尾可能有多余的位使数组对齐(与处理机的字长匹配)。无论如何,我们可以通过BitmapData对象的Stride属性得到。 由于一个ARGB值是4个字节,所以我们需要调用Marshal类的ReadInt32和WriteInt32方法对每个像素点的颜色进行读取和写入。我们要操作的是颜色的ARGB值而不是Color对象。 那么把上面的代码稍加改造,就可以写出如下程序: 复制代码 代码如下: Private Sub FillRegion(sourcePoint As Point,destinationColor As Color) Dim new_bitmap As Bitmap = DirectCast(PictureBox1.Image,Bitmap) Dim source_color_int As Integer = new_bitmap.GetPixel(sourcePoint.X,sourcePoint.Y).ToArgb Dim bitmap_data As BitmapData = new_bitmap.LockBits(New Rectangle(0,PictureBox1.Width,PictureBox1.Height),_ Imaging.ImageLockMode.ReadWrite,new_bitmap.PixelFormat) Dim stride As Integer = Math.Abs(bitmap_data.Stride) Dim scan0 As IntPtr = bitmap_data.Scan0 Dim bytes As Integer = stride * new_bitmap.Height Dim MIN_X As Integer = 1,MIN_Y As Integer = 1 Dim MAX_X As Integer = PictureBox1.Width - 1,MAX_Y As Integer = PictureBox1.Height - 1 Dim fill_queue(MAX_FILL_QUEUE) As Point Dim fill_direction() As Point = {New Point(-1,1)} Dim destination_color_int As Integer = destinationColor.ToArgb Dim queue_head As Integer = 0 Dim queue_tail As Integer = 1 fill_queue(queue_tail) = sourcePoint Do While queue_head <> queue_tail queue_head = (queue_head + 1) Mod MAX_FILL_QUEUE Dim current_point As Point = fill_queue(queue_head) For i As Integer = 0 To 3 Dim new_point_x As Integer = current_point.X + fill_direction(i).X Dim new_point_y As Integer = current_point.Y + fill_direction(i).Y If new_point_x < MIN_X OrElse new_point_y < MIN_Y OrElse new_point_x > MAX_X OrElse new_point_y > MAX_Y Then Continue For Dim offset As Integer = (new_point_y * stride) + new_point_x * 4 Dim current_color_int As Integer = System.Runtime.InteropServices.Marshal.ReadInt32(scan0,offset) If current_color_int = source_color_int Then System.Runtime.InteropServices.Marshal.WriteInt32(scan0,offset,destination_color_int) queue_tail = (queue_tail + 1) Mod MAX_FILL_QUEUE fill_queue(queue_tail) = New Point(new_point_x,new_point_y) End If Next Loop new_bitmap.UnlockBits(bitmap_data) PictureBox1.Image = new_bitmap End Sub 当然,如果你还有其他更好的实现方法,还请多多指教。(啊,不要告诉我使用Windows的API。。。) 现在运行一下程序,发现效率急剧上升。我测试了一下,在我的电脑上,填充37万个像素大概只需要50~60毫秒左右,效率还是令人满意的。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |