快捷導(dǎo)航

VB.NET中使用種子填充算法實(shí)現(xiàn)給圖片著色的例子

更新時(shí)間：2014年07月16日 11:07:04 投稿：junjie

這篇文章主要介紹了VB.NET中使用種子填充算法實(shí)現(xiàn)給圖片著色的例子,在開(kāi)發(fā)一個(gè)畫(huà)圖工具時(shí)遇到的問(wèn)題,需要的朋友可以參考下

某人最近在使用C#寫(xiě)一個(gè)類(lèi)似Windows的畫(huà)圖工具，在填色的部分卡住了。勞資要他使用種子填充算法著色（不要調(diào)用Windows提供的API，否則還鍛煉個(gè)毛線），現(xiàn)在我把這個(gè)功能實(shí)現(xiàn)了，程序的效率很高。現(xiàn)在在這里大概寫(xiě)一下實(shí)現(xiàn)方法。

程序是用VB.NET寫(xiě)的，C#寫(xiě)法類(lèi)似（而且還不需要使用Marshal類(lèi)訪問(wèn)非托管資源，更加方便）。程序的運(yùn)行結(jié)果如下：

　種子填充算法說(shuō)白了就是寬度優(yōu)先搜索算法（BFS），如果你不知道這是什么東西，那說(shuō)明你數(shù)據(jù)結(jié)構(gòu)根本就沒(méi)有學(xué)，請(qǐng)自行補(bǔ)充相應(yīng)的知識(shí)。

　　第一步：實(shí)現(xiàn)“鉛筆”工具

我們定義如下的全局變量（窗體類(lèi)的私有成員），作用是啥一看名字就知道：

復(fù)制代碼代碼如下:

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

　這個(gè)程序中填充的顏色是隨機(jī)決定的（都懶得做一個(gè)選顏色的功能了），可以填充的顏色在_fillColor數(shù)組中。_drawStyle定義當(dāng)前的繪圖模式（Drawing表示使用鉛筆工具，但未按下，F(xiàn)ill表示準(zhǔn)備填充，DrawDragging表示鼠標(biāo)正按下并拖拽）。

　　_imgMain是繪制的圖片，_g是創(chuàng)建在這個(gè)Bitmap上的Graphics對(duì)象。

　　需要注意的是，Drawing和Drawing2D類(lèi)不提供畫(huà)點(diǎn)的方法，我們需要通過(guò)畫(huà)直線或畫(huà)矩形來(lái)模擬。至于_lastPosition的作用，由于鼠標(biāo)拖拽過(guò)程中，如果速度過(guò)快，那么MouseMove事件中的坐標(biāo)點(diǎn)（每次MouseMove事件被觸發(fā)）并不是連續(xù)的，所以我們需要在當(dāng)前點(diǎn)和上一次的鼠標(biāo)位置之間畫(huà)一條直線，否則畫(huà)出來(lái)的線是間斷的。

　　MouseDown、MouseMove和MouseUp實(shí)現(xiàn)鉛筆工具的基本功能，代碼如下：

復(fù)制代碼代碼如下:

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

　　二、正題——種子填充算法的實(shí)現(xiàn)

　　上面說(shuō)了一堆廢話，現(xiàn)在終于可以開(kāi)始實(shí)現(xiàn)填充的算法了。

　　當(dāng)用戶點(diǎn)擊圖片中某一個(gè)點(diǎn)后，需要填充與這個(gè)點(diǎn)相鄰的、顏色相同的其他點(diǎn)。為什么要叫“種子填充”呢？大概是這樣：你在點(diǎn)中的那個(gè)點(diǎn)中播下一顆種子，它開(kāi)花結(jié)果（顏色變成目標(biāo)顏色），然后它又播種出新的種子（與它上下左右相鄰且顏色等于原來(lái)顏色的點(diǎn)）；新種子再開(kāi)花結(jié)果（變顏色），播種新種子…… 如此往復(fù)，直到?jīng)]有地方播種了為止，算法結(jié)束。

　　按照BFS通常的實(shí)現(xiàn)方式，可以使用循環(huán)隊(duì)列作為數(shù)據(jù)結(jié)構(gòu)。對(duì)于BFS算法來(lái)說(shuō)，需要的存儲(chǔ)空間較大，具體需要多少還真不好估算。這里給大家一個(gè)參考，我的這個(gè)程序圖片框大小是832*450，大概是37萬(wàn)像素，循環(huán)隊(duì)列的容量設(shè)置為1600可以滿足需求（全部著色）。如果你的圖片框比較大，可以先取一個(gè)較大的數(shù)值（比如8000），再逐漸縮小，反復(fù)嘗試。

　　實(shí)現(xiàn)這個(gè)循環(huán)隊(duì)列直接定義成一個(gè)一維數(shù)組就可以了，沒(méi)有必要使用ConcurrentQueue類(lèi)，否則性能會(huì)下降，也沒(méi)有這個(gè)必要。

　　首先，由于要向四個(gè)方向填充，為了避免類(lèi)似的代碼反復(fù)寫(xiě)導(dǎo)致程序丑陋無(wú)比，我們可以定義一個(gè)fill_direction數(shù)組：

復(fù)制代碼代碼如下:

Dim fill_direction() As Point = {New Point(-1, 0), New Point(1, 0), New Point(0, -1), New Point(0, 1)}

　這樣，使用一個(gè)For循環(huán)就可以完成四個(gè)方向的操作了。

　　按照首先說(shuō)的思路，程序的實(shí)現(xiàn)就很簡(jiǎn)單了：首先將點(diǎn)擊的那個(gè)點(diǎn)入隊(duì)，記錄這個(gè)點(diǎn)的顏色。然后使用一個(gè)循環(huán)，取出隊(duì)首元素，并向四個(gè)方向撒種子（顏色相同，且沒(méi)有越出圖片框邊界），將每一個(gè)種子的顏色改變成目標(biāo)顏色并入隊(duì)。如此往復(fù)直到隊(duì)列為空為止。代碼如下：

復(fù)制代碼代碼如下:

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

　可能會(huì)有一個(gè)問(wèn)題，就是第一個(gè)點(diǎn)在入隊(duì)前應(yīng)該要先改成目標(biāo)顏色，但我這里沒(méi)有改。效果其實(shí)是一樣的，因?yàn)樗赃叺狞c(diǎn)在撒種子的時(shí)候發(fā)現(xiàn)這個(gè)點(diǎn)顏色沒(méi)變，還是會(huì)將它入隊(duì)（注意：如果只有一個(gè)點(diǎn)需要填充，即起始點(diǎn)沒(méi)有相鄰的點(diǎn)，那么會(huì)導(dǎo)致這個(gè)點(diǎn)不被填充成目標(biāo)顏色，請(qǐng)自行改進(jìn)算法）。我們?cè)谶@里忽略這個(gè)小問(wèn)題。

　　運(yùn)行程序，可以發(fā)現(xiàn)已經(jīng)可以實(shí)現(xiàn)填充的功能了。

備注：如果目標(biāo)顏色和起始點(diǎn)的顏色相同，且起始點(diǎn)有相鄰的、相同顏色的點(diǎn)，那么會(huì)導(dǎo)致相同的點(diǎn)反復(fù)入隊(duì)，最終導(dǎo)致隊(duì)列溢出。此時(shí)隊(duì)首指針等于隊(duì)尾指針，程序會(huì)認(rèn)為隊(duì)列為空而終止填充，因此最終結(jié)果沒(méi)有變化（如果不是采用循環(huán)隊(duì)列，會(huì)導(dǎo)致程序死循環(huán)）。為了避免這種情況，應(yīng)該在進(jìn)行填充前判斷目標(biāo)顏色是否和原點(diǎn)顏色相同，相同時(shí)直接結(jié)束。在這里我沒(méi)有進(jìn)行這樣的判斷。
　　

三、提升效率

　在運(yùn)行程序時(shí)發(fā)現(xiàn)了一個(gè)問(wèn)題，就是如果填色區(qū)域過(guò)大（比如直接填充整個(gè)圖片框），程序會(huì)很慢，大概需要2秒左右才能填充完。產(chǎn)生這個(gè)問(wèn)題的主要原因是GetPixel和SetPixel的性能不高，每次調(diào)用這兩個(gè)方法時(shí)都會(huì)做很多額外的操作，在我以前使用匯編語(yǔ)言調(diào)用DOS中斷畫(huà)點(diǎn)時(shí)就有這個(gè)問(wèn)題。

　　為此，M$提供了LockBits和UnlockBits方法。LockBits方法可以將圖片鎖定到內(nèi)存中，以便通過(guò)訪問(wèn)內(nèi)存直接對(duì)這些數(shù)據(jù)進(jìn)行修改。在C#中我們可以直接使用指針訪問(wèn)這片數(shù)據(jù)，但對(duì)于VB是不行的，因?yàn)閂B不允許使用指針，我們可以借助System.Runtime.InteropServices.Marshal類(lèi)達(dá)到直接訪問(wèn)內(nèi)存的功能。

　　關(guān)于LockBits的詳細(xì)介紹可以參考這篇日志：http://www.bobpowell.net/lockingbits.htm

　　其中很重要的一點(diǎn)就是要搞清楚如何計(jì)算圖片上某一點(diǎn)的內(nèi)存地址。

如這張圖所示（圖片來(lái)自那篇博文），坐標(biāo)為(X,Y)的點(diǎn)在內(nèi)存中的地址就是Scan0 + (Y * Stride) + X * k。k與圖片中每個(gè)點(diǎn)占用的字節(jié)有關(guān)，我們這里使用的是32位ARPG，每個(gè)像素占4個(gè)字節(jié)，因此k就是4。另外注意Stride并不一定是n*k（n表示每行存n個(gè)像素），因?yàn)槟┪部赡苡卸嘤嗟奈皇箶?shù)組對(duì)齊（與處理機(jī)的字長(zhǎng)匹配）。無(wú)論如何，我們可以通過(guò)BitmapData對(duì)象的Stride屬性得到。

　　由于一個(gè)ARGB值是4個(gè)字節(jié)，所以我們需要調(diào)用Marshal類(lèi)的ReadInt32和WriteInt32方法對(duì)每個(gè)像素點(diǎn)的顏色進(jìn)行讀取和寫(xiě)入。我們要操作的是顏色的ARGB值而不是Color對(duì)象。

　　那么把上面的代碼稍加改造，就可以寫(xiě)出如下程序：

復(fù)制代碼代碼如下:

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

　當(dāng)然，如果你還有其他更好的實(shí)現(xiàn)方法，還請(qǐng)多多指教。（啊，不要告訴我使用Windows的API。。。）　　現(xiàn)在運(yùn)行一下程序，發(fā)現(xiàn)效率急劇上升。我測(cè)試了一下，在我的電腦上，填充37萬(wàn)個(gè)像素大概只需要50~60毫秒左右，效率還是令人滿意的。

您可能感興趣的文章: