0%

iOS用扫描线种子填充算法实现涂鸦的功能

Posted on In

扫描线种子填充算法基本步骤:

  1. 初始化一个空栈用于存放种子点，将种子点（x,y）入栈
  2. 判断栈是否为空，如果栈为空则算法结束，否则取出栈顶元素作为当前扫描线的种子点（x,y）,y 是当前的扫描线
  3. 从种子点（x,y）出发，沿当前扫描线向左向右两个方向填充，直到边界。分别标记区段的左右端点为 xLeft，xRight
  4. 分别检查与当前扫描线相邻的 y-1 和 y+1 两条扫描线在区间[xLeft,xRight]中的像素，从 xLeft 开始 xRight 方向搜索，若存在非边界且未填充的像素点，则找出这些相邻像素点中最右边的一个，并将其作为种子点入栈，然后返回第 2 步（注：一条扫描线上可能存在多个种子点）

涂鸦效果

效果图.gif

iOS 中如何实现扫描线种子填充算法

  1. 扫描的是什么东东？

    扫描的是图片上所有的像素点的集合，而常用的 png，jpg 是压缩过的位图，所以首先要把 png，jpg 图片进行解压缩

  2. 在 iOS 中如何把 UIImage 转成像素点的集合？

    主要利用 CGContext 的下面三个 API

    1
    //初始化 CGContext
    2
    public init?(data: UnsafeMutableRawPointer?, width: Int, height: Int, bitsPerComponent: Int, bytesPerRow: Int, space: CGColorSpace, bitmapInfo: UInt32)
    3
    //将位图也就是像素点的集合绘制到上下文中
    4
    public func draw(_ image: CGImage, in rect: CGRect)
    5
    //得到上下文中的位图
    6
    public func makeImage() -> CGImage?

    主要解释一下第一个方法的各个参数的含义
    data：存放像素点的指针
    width,height:位图的宽高
    bitsPerComponent：颜色空间中每个通道占用的 bit；（注，此单位是 bit）
    bytesPerRow：位图的每一行使用的字节数（注，此单位是 byte，1byte=8bit）大小等于 width*height*每个像素占用的大小，在 iOS 里颜色空间是 RGB 时，每个像素占用的大小是 32
    space:像素点的颜色空间
    bitmapInfo：位图的布局信息，主要包含了 alpha 的信息；颜色分量是否为浮点数；像素格式的字节顺序

    1
    let image = UIImage(named: "test")
    2
    if let imageRef = image?.cgImage  {
    3
            let width = imageRef.width
    4
            let height = imageRef.height
    5
            var pixels = Array<UInt32>(repeating: 0, count: width * height)
    6
            let colorSpace = CGColorSpaceCreateDeviceRGB() //像素点的颜色空间
    7
            let bitsPerComponent = 8 //颜色空间每个通道占用的bit
    8
            let bytesPerRow = width * 4 //位图的每一行使用的字节数
    9
            let bitmapInfo = CGImageAlphaInfo.premultipliedLast.rawValue
    10
            if let context = CGContext(data: &(pixels), width: width, height: height, bitsPerComponent: bitsPerComponent,
    11
                                       bytesPerRow: bytesPerRow, space: colorSpace, bitmapInfo: bitmapInfo) {
    12
                context.draw(imageRef, in: CGRect(x: 0, y: 0, width: width, height: height))
    13
            }
    14
    }

  3. 如何把触摸在 imageView 上的坐标转换为 UIImage 上的种子点

    由于 UIImageView 的大小也 UIImage 得大小是不一样的，所以当我们获取手势在 ImageView 上的坐标的时候，要经过变换得到 UIImage 上的坐标，把此点作为种子点入栈

1
//注，self是UIImageView的子类
2
 override func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?) {
3
        if touches.count == 1 , let touch = touches.first , let imageRef = self.image?.cgImage{
4
            let point = touch.location(in: self)
5
            let width = imageRef.width
6
            let height = imageRef.height
7
            let widthScale = CGFloat(width) / bounds.width
8
            let heightScale = CGFloat(height) / bounds.height
9
            //把相对于view的touch point 转换成image的像素点的坐标点
10
            let realPoint = CGPoint(x: point.x * widthScale, y: point.y * heightScale)
11
        }
12
    }

  1. 实现扫描线种子填充算法

    核心代码如下，以下代码是写在自定义的 UIImageView 的子类中
1
 //MARK: private method
2
    /// 填充颜色
3
    ///
4
    /// - Parameters:
5
    ///   - point: 种子点
6
    ///   - color: 填充颜色
7
    private func floodFill(from point:CGPoint) {
8
        if let imageRef = image?.cgImage  {
9
            let width = imageRef.width
10
            let height = imageRef.height
11
            let widthScale = CGFloat(width) / bounds.width
12
            let heightScale = CGFloat(height) / bounds.height
13
            //把相对于view的touch point 转换成image的像素点的坐标点
14
            let realPoint = CGPoint(x: point.x * widthScale, y: point.y * heightScale)
15
            scanedLines = [:]
16
            imageSize = CGSize(width: width, height: height)
17
            pixels = Array<UInt32>(repeating: 0, count: width * height)
18
            let colorSpace = CGColorSpaceCreateDeviceRGB() //像素点的颜色空间
19
            let bitsPerComponent = 8 //颜色空间每个通道占用的bit
20
            let bytesPerRow = width * 4 //image每一行所占用的byte
21
            let bitmapInfo = CGImageAlphaInfo.premultipliedLast.rawValue
22
            if let context = CGContext(data: &(pixels), width: width, height: height, bitsPerComponent: bitsPerComponent,
23
                                       bytesPerRow: bytesPerRow, space: colorSpace, bitmapInfo: bitmapInfo) {
24
                context.draw(imageRef, in: CGRect(x: 0, y: 0, width: width, height: height))
25
                let pixelIndex = lrintf(Float(realPoint.y)) * width + lrintf(Float(realPoint.x))
26
                let newColorRgbaValue = newColor.rgbaValue
27
                let colorRgbaValue = pixels[pixelIndex]
28
                //如果点击的黑色边框，直接退出
29
                if isBlackColor(color: colorRgbaValue) {
30
                    return
31
                }
32
                //如果点击的颜色和新颜色一样，退出
33
                if compareColor(color: colorRgbaValue, otherColor: newColorRgbaValue, tolorance: colorTolorance) {
34
                    return
35
                }
36
                //存放种子点的栈
37
                seedPointList.push(realPoint)
38
                while !seedPointList.isEmpty {
39
                    if let point = seedPointList.pop() {
40
                        let (xLeft,xRight) = fillLine(seedPoint: point, newColorRgbaValue: newColorRgbaValue,
41
                                                      originalColorRgbaValue: colorRgbaValue)
42
                        scanLine(lineNumer: Int(point.y) + 1, xLeft: xLeft, xRight: xRight, originalColorRgbaValue: colorRgbaValue)
43
                        scanLine(lineNumer: Int(point.y) - 1, xLeft: xLeft, xRight: xRight, originalColorRgbaValue: colorRgbaValue)
44
                    }
45
                }
46
                if let cgImage = context.makeImage() {
47
                    image = UIImage(cgImage: cgImage, scale: image?.scale ?? 2, orientation: .up)
48
                }
49
            }
50
        }
51
    }
52
53
    /// 通过种子点向左向右填充
54
    ///
55
    /// - Parameters:
56
    ///   - seedPoint: 种子点
57
    ///   - newColorRgbaValue: 填充的新颜色的值
58
    ///   - originalColorRgbaValue: 触摸点颜色的值
59
    /// - Returns: 种子点填充的左右区间 都是闭区间
60
   private  func fillLine(seedPoint:CGPoint,newColorRgbaValue:UInt32,originalColorRgbaValue:UInt32) -> (Int,Int) {
61
        let imageW = Int(imageSize.width)
62
        let currntLineMinIndex = Int(seedPoint.y) * imageW
63
        let currntLineMaxIndex = currntLineMinIndex + imageW
64
        let currentPixelIndex = currntLineMinIndex + Int(seedPoint.x)
65
        var xleft = Int(seedPoint.x)
66
        var xright = xleft
67
        if pixels.count >= currntLineMaxIndex {
68
            var tmpIndex = currentPixelIndex
69
            while tmpIndex >=  currntLineMinIndex &&
70
                  compareColor(color: originalColorRgbaValue, otherColor: pixels[tmpIndex], tolorance: colorTolorance){
71
                pixels[tmpIndex] = newColorRgbaValue
72
                tmpIndex -= 1
73
                xleft -= 1
74
            }
75
            tmpIndex = currentPixelIndex + 1
76
            while tmpIndex < currntLineMaxIndex &&
77
                  compareColor(color: originalColorRgbaValue, otherColor: pixels[tmpIndex], tolorance: colorTolorance){
78
                pixels[tmpIndex] = newColorRgbaValue
79
                tmpIndex += 1
80
                xright += 1
81
            }
82
        }
83
        return (xleft + 1,xright)
84
    }
85
86
87
    /// 从xLeft到xRight的扫描第lineNumer行
88
    ///
89
    /// - Parameters:
90
    ///   - lineNumer: 行数
91
    ///   - xLeft: 扫描线的最左侧
92
    ///   - xRight: 扫描线的最右侧
93
    ///   - originalColorRgbaValue:  触摸点颜色的值
94
   private func scanLine(lineNumer:Int,xLeft:Int,xRight:Int,originalColorRgbaValue:UInt32) {
95
        if lineNumer < 0 || CGFloat(lineNumer) > imageSize.height - 1{
96
            return
97
        }
98
        var xCurrent = xLeft //当前被扫描的点的x位置
99
        let currentLineOriginalIndex = lineNumer * Int(imageSize.width)
100
        var currentPixelIndex = currentLineOriginalIndex + xLeft //当前被扫描的点的所在像素点的位置
101
        var currntLineMaxIndex = currentLineOriginalIndex + xRight //当前扫描线需要扫描的最后一个点的位置
102
        //此处是对种子扫描线算法的一点小优化
103
        var leftSpiltIndex:Int?
104
        if var scanLine = scanedLines[lineNumer] {
105
            if scanLine.xLeft >= xRight || scanLine.xRight <= xLeft {//没有相交，什么也不做
106
            }else if scanLine.xLeft <= xLeft && scanLine.xRight >= xRight { //旧扫描与新扫描的范围关系是包含
107
                return
108
            }else if scanLine.xLeft <= xLeft && scanLine.xRight <= xRight {//旧扫描与新扫描的范围关系是左包含右被包含
109
                xCurrent = scanLine.xRight + 1
110
                currentPixelIndex = currentLineOriginalIndex + scanLine.xRight + 1
111
                scanLine.xRight = xRight
112
                scanedLines[lineNumer] = scanLine
113
            }else if scanLine.xLeft >= xLeft && scanLine.xRight >= xRight {//旧扫描与新扫描的范围关系是左被包含右包含
114
                currntLineMaxIndex = currentLineOriginalIndex + scanLine.xLeft - 1
115
                leftSpiltIndex = currentLineOriginalIndex + scanLine.xLeft
116
                scanLine.xLeft = xLeft
117
                scanedLines[lineNumer] = scanLine
118
            }else if scanLine.xLeft >= xLeft && scanLine.xRight <= xRight {//旧扫描与新扫描的范围关系是被包含
119
                scanLine.xLeft = xLeft
120
                scanLine.xRight = xRight
121
                scanedLines[lineNumer] = scanLine
122
            }
123
        }else {
124
            scanedLines[lineNumer] = FillLineInfo(lineNumber: lineNumer, xLeft: xLeft, xRight: xRight)
125
        }
126
        while currentPixelIndex <= currntLineMaxIndex {
127
            var isFindSeed = false
128
            //找到此区间的种子点，种子点是存在非边界且未填充的像素点，这些相邻的像素点中最右边的一个
129
            while currentPixelIndex < currntLineMaxIndex &&
130
                  compareColor(color: originalColorRgbaValue, otherColor: pixels[currentPixelIndex], tolorance: colorTolorance) {
131
                isFindSeed = true
132
                currentPixelIndex += 1
133
                xCurrent += 1
134
            }
135
136
            if isFindSeed {
137
                //如果找到种子点，需要判断while循环的退出条件是什么
138
                //如果是到区间最右边的倒数第二个点，则需要判断最右边的点是否和originalColorRgbaValue颜色一样，如果一样，则最右边的入栈，否则把上一个点入栈
139
                //如果是碰到了边界点退出的，则把当前点的上一个点入栈
140
                if compareColor(color: originalColorRgbaValue, otherColor: pixels[currentPixelIndex], tolorance: colorTolorance) &&
141
                   currentPixelIndex == currntLineMaxIndex {
142
                    //若当旧扫描与新扫描的范围关系是左被包含右包含，需要扫描的范围应该是新扫描范围的左点到旧扫描范围的左点的上一个点
143
                    //此时若扫描范围内的最右点颜色与originalColorRgbaValue一样，并且旧扫描范围的左点的颜色也与originalColorRgbaValue一样，则不需要入栈
144
                    if leftSpiltIndex == nil ||
145
                       !compareColor(color: originalColorRgbaValue, otherColor: pixels[leftSpiltIndex!], tolorance: colorTolorance){
146
                        seedPointList.push(CGPoint(x: xCurrent, y: lineNumer))
147
                    }
148
                }else {
149
                    seedPointList.push(CGPoint(x: xCurrent - 1, y: lineNumer))
150
                }
151
            }
152
            currentPixelIndex += 1
153
            xCurrent += 1
154
        }
155
    }
156
157
   /// 判断颜色是否是黑色
158
   ///
159
   /// - Returns: true 是 or false 不是
160
   private func isBlackColor(color:UInt32) -> Bool {
161
        let colorRed = Int((color >> 0) & 0xff)
162
        let colorGreen = Int((color >> 8) & 0xff)
163
        let colorBlue = Int((color >> 16) & 0xff)
164
        let colorAlpha = Int((color >> 24) & 0xff)
165
166
        if colorRed < colorTolorance &&
167
            colorGreen < colorTolorance &&
168
            colorBlue < colorTolorance &&
169
            colorAlpha > 255 - colorTolorance{
170
            return true
171
        }
172
        return false
173
    }
174
175
    /// 是否是相似的颜色
176
    ///
177
    /// - Returns: true 相似 or false 不相似
178
    private func compareColor(color:UInt32, otherColor:UInt32, tolorance:Int) -> Bool {
179
        if color == otherColor {
180
            return true
181
        }
182
        let colorRed = Int((color >> 0) & 0xff)
183
        let colorGreen = Int((color >> 8) & 0x00ff)
184
        let colorBlue = Int((color >> 16) & 0xff)
185
        let colorAlpha = Int((color >> 24) & 0xff)
186
187
        let otherColorRed = Int((otherColor >> 0) & 0xff)
188
        let otherColorGreen = Int((otherColor >> 8) & 0xff)
189
        let otherColorBlue = Int((otherColor >> 16) & 0xff)
190
        let otherColorAlpha = Int((otherColor >> 24) & 0xff)
191
192
        if abs(colorRed - otherColorRed) > tolorance ||
193
           abs(colorGreen - otherColorGreen) > tolorance   ||
194
           abs(colorBlue - otherColorBlue) > tolorance ||
195
           abs(colorAlpha - otherColorAlpha) > tolorance {
196
            return false
197
        }
198
        return true
199
    }
200
    extension UIColor {
201
    /// 获取颜色的UInt32表示形式
202
    fileprivate var rgbaValue:UInt32 {
203
        var red:CGFloat = 0
204
        var green:CGFloat = 0
205
        var blue:CGFloat = 0
206
        var alpha:CGFloat = 0
207
        getRed(&red, green: &green, blue: &blue, alpha: &alpha)
208
        return UInt32(red * 255) << 0 | UInt32(green * 255) << 8 | UInt32(blue * 255) << 16 | UInt32(alpha * 255) << 24
209
    }
210
}

  1. 做此功能的一些其他收获

    • UIScrollView 很容易实现视图的缩放功能，只要在代理方法中返回需要缩放的视图即可，UIScrollView 是如何实现子视图的缩放的？

      UIScrollView 是通过改变子视图的 transform 来实现缩放的

    • 当使用 transform 把视图缩放后，frame 和 bounds 会如何变化，该视图的子视图的 frame 和 bounds 又会如何变化

      frame 会同比缩放，而 bounds 不会变化，子视图的 frame 和 bounds 都不变
      原因猜测(纯属猜测)如下：frame.size 代表的是视图的大小，这个大小是逻辑大小，而不是真正的像素大小。而 bounds 也是逻辑大小。以 iphone6 举例，在无缩放的情况下，frame.size.width = 1 代表着 2 个像素点，在缩放的过程中。当前缩放的视图的 frame.size 每个逻辑大小对应的像素点不变，而 bounds.size 每个逻辑大小对应的像素点则同比缩放，对于子视图来说，frame.size 每个逻辑大小对应的像素点等于父视图的 bounds.size 每个逻辑大小对应的像素点，bounds.size 每个逻辑大小对应的像素点则等于父视图的 bounds.size 每个逻辑大小对应的像素点和自身的缩放的乘积

    • 当使用 transform 把视图放大之后，触摸点 point 的范围是否会放大，也就是说如果放大之前视图的大小为 375*373，point 的范围为(0,0)-(375,375),那么放大 2 倍后，point 的范围是(0,0)-(375,375)还是(0,0)-(750，750)

      范围还是(0,0)-(375,375)，原因猜测如下：手势获取坐标的时候是基于视图的 bounds 的

  2. demo 的 GitHub 地址

  3. 参考文章