VB.NET中使用种子填充算法实现给图片着色的例子

页面导航:首页 > 软件编程 > vb.net > VB.NET中使用种子填充算法实现给图片着色的例子

VB.NET中使用种子填充算法实现给图片着色的例子

来源:互联网 作者:脚本宝典 时间:2015-07-28 19:21 【

某人最近在使用C#写一个类似Windows的画图工具,在填色的部分卡住了。劳资要他使用种子填充算法着色(不要调用Windows提供的API,否则还锻炼个毛线),现在我把这个功能实现了,程序

某人最近在使用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, 0), New Point(0, -1), New Point(0, 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, 0), New Point(1, 0), New Point(0, -1), New Point(0, 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, 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, 0), New Point(1, 0), New Point(0, -1), New Point(0, 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毫秒左右,效率还是令人满意的。


Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<