久热精品香蕉在线视频,亚洲日本一区二区三区在线,欧美一区二区三区性

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

程序是用VB.NET寫的，C#寫法類似（而且還不需要使用Marshal類訪問非托管資源，更加方便）。程序的運行結果如下：

VB.NET中使用種子填充算法實現給圖片著色的例子

　種子填充算法說白了就是寬度優先搜索算法（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

　　其中很重要的一點就是要搞清楚如何計算圖片上某一點的內存地址。

VB.NET中使用種子填充算法實現給圖片著色的例子

如這張圖所示（圖片來自那篇博文），坐標為(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