如何优化Android中Flood Fill图像着色算法的耗时问题

当前使用的Flood Fill算法可正常完成单色、纯色及渐变填充，但无论着色区域大小，均需数秒才能完成。现咨询以下问题：

1. 该算法耗时较长的原因是什么？如何进行优化？
2. 在Android应用中使用Java或Kotlin能否实现高性能的Flood Fill？
3. 如何实现1秒内完成任意大小触摸区域的着色？

参考应用：InColor

FloodFill类代码 #

object FloodFill {
    private var floodFillInProgress = false

    suspend fun floodFill(
        bitmap: Bitmap,
        point: Point,
        targetColor: Int,
        shader: Shader?,
        newColor: Int,
        tolerance: Int = 0,
        onProgress: (Bitmap) -> Unit
    ) = withContext(Dispatchers.IO) {
        if (floodFillInProgress) return@withContext

        floodFillInProgress = true

        if (shader == null && targetColor == newColor) {
            floodFillInProgress = false
            return@withContext
        }

        try {
            val width = bitmap.width
            val height = bitmap.height
            val queue = kotlin.collections.ArrayDeque<Point>()
            queue.add(point)

            val fillInterval = if (isHighPerformanceDevice()) 1000 else 1000

            var count = 0

            val visited = BooleanArray(width * height)
            val buffer = IntArray(width * height)
            bitmap.getPixels(buffer, 0, width, 0, 0, width, height)

            val tempBitmap = Bitmap.createBitmap(width, height, Bitmap.Config.ARGB_8888)
            val shaderCanvas = Canvas(tempBitmap)
            val shaderPaint = Paint().apply {
                this.shader = shader
            }
            shaderCanvas.drawRect(0f, 0f, width.toFloat(), height.toFloat(), shaderPaint)

            while (queue.isNotEmpty()) {
                val p = queue.removeFirst()
                val x = p.x
                val y = p.y

                if (x < 0 || y < 0 || x >= width || y >= height) continue

                val index = y * width + x
                if (visited[index]) continue

                val pixelColor = buffer[index]
                if (pixelColor == Color.BLACK || !colorMatch(pixelColor, targetColor, tolerance)) continue

                visited[index] = true

                if (shader != null) {
                    buffer[index] = tempBitmap.getPixel(x, y)
                } else {
                    buffer[index] = newColor
                }

                queue.add(Point(x - 1, y))
                queue.add(Point(x + 1, y))
                queue.add(Point(x, y - 1))
                queue.add(Point(x, y + 1))

                count++
                if (count % fillInterval == 0) {
                    withContext(Dispatchers.Main) {
                        bitmap.setPixels(buffer, 0, width, 0, 0, width, height)
                        onProgress(bitmap)
                    }
                }
            }

            withContext(Dispatchers.Main) {
                bitmap.setPixels(buffer, 0, width, 0, 0, width, height)
                onProgress(bitmap)
            }
        } catch (e: IllegalStateException) {
            Log.e("FloodFill", "Bitmap was recycled during flood fill operation", e)
        } finally {
            floodFillInProgress = false
        }
    }

    private fun colorMatch(pixelColor: Int, targetColor: Int, tolerance: Int): Boolean {
        if (tolerance == 0) {
            return pixelColor == targetColor
        }

        val r = Color.red(pixelColor)
        val g = Color.green(pixelColor)
        val b = Color.blue(pixelColor)
        val targetR = Color.red(targetColor)
        val targetG = Color.green(targetColor)
        val targetB = Color.blue(targetColor)

        return abs(r - targetR) <= tolerance &&
                abs(g - targetG) <= tolerance &&
                abs(b - targetB) <= tolerance
    }

    private fun isHighPerformanceDevice(): Boolean {
        val memoryClass = (Runtime.getRuntime().maxMemory() / (1024 * 1024)).toInt()
        return memoryClass > 256
    }
}

View类调用代码 #

private suspend fun paint(x: Int, y: Int) {
    Log.d("ColorPaintView", "paint called at: $x, $y")
    val bmp = bitmap ?: return
    if (bmp.isRecycled) return
    if (x < 0 || y < 0 || x >= bmp.width || y >= bmp.height) return
    val targetColor = bmp.getPixel(x, y)
    Log.d("ColorPaintView", "targetColor: $targetColor")
    if (targetColor == Color.BLACK) return

    val shader: Shader? = when (gradientType) {
        GradientType.NONE -> null
        GradientType.LINEAR -> {
            val angle = 235.0
            val angleInRadians = Math.toRadians(angle)
            val length = sqrt((bmp.width * bmp.width + bmp.height * bmp.height).toDouble()).toFloat()

            val startX = x.toFloat()
            val startY = y.toFloat()
            val endX = (x + length * cos(angleInRadians)).toFloat().coerceAtMost(bmp.width - 1f)
            val endY = (y + length * sin(angleInRadians)).toFloat().coerceAtMost(bmp.height - 1f)

            LinearGradient(startX, startY, endX, endY, gradientColors, gradientPositions, Shader.TileMode.MIRROR)
        }
        GradientType.RADIAL -> {
            RadialGradient(x.toFloat(), y.toFloat(), (bmp.width.coerceAtLeast(bmp.height) / 2).toFloat(), gradientColors, gradientPositions, Shader.TileMode.CLAMP)
        }
    }

    Log.d("ColorPaintView", "Starting flood fill")
    addLastAction(Bitmap.createBitmap(bmp))

    FloodFill.floodFill(bmp, Point(x, y), targetColor, shader, paintColor, 25) { updatedBitmap -> 
        Log.d("ColorPaintView", "Flood fill completed")
        bitmap = updatedBitmap
        invalidate()
    }
}

1. 耗时原因及优化方案 #

耗时原因 #

• 对象频繁创建与GC：使用ArrayDeque<Point>存储坐标，每次入队都创建新的Point对象，触发频繁垃圾回收。
• 低效的渐变像素获取：每次填充渐变时调用tempBitmap.getPixel(x,y)，该方法是单像素读取，性能极低。
• 冗余的线程切换：每处理1000个像素就切换到主线程更新Bitmap，线程切换本身开销大，且fillInterval的判断逻辑无效（高低性能设备都设为1000）。
• 额外内存与判断开销：使用BooleanArray visited标记已访问像素，增加内存占用和判断步骤；colorMatch方法每次都重复解析目标颜色的RGB值。
• 低效的队列操作：ArrayDeque的removeFirst()虽然是O(1)，但频繁的入队出队结合对象创建，累积开销大。

优化方案 #

• 替换Point对象为原始类型：用两个IntArray分别存储x、y坐标，或者将坐标打包为x + y * width的整数存入队列，完全避免对象创建。
• 预计算渐变像素：将Shader绘制的tempBitmap一次性读取到IntArray中，后续直接从数组取像素，避免重复调用getPixel。
• 移除频繁的线程更新：仅在填充完成后更新UI；若需要进度提示，改为每处理N行后再更新，减少线程切换次数。
• 用颜色标记已访问：直接将填充后的颜色写入buffer，后续判断时若像素等于填充色则跳过，无需额外的visited数组。
• 预计算目标颜色RGB：在方法开头解析目标颜色的R、G、B值，避免colorMatch中重复解析。
• 改用扫描线填充算法：扫描线填充（Scanline Flood Fill）可以一次性处理一行连续的像素，大幅减少队列操作次数，效率远高于普通BFS。
• 优化设备性能判断：根据CPU核心数、GPU性能调整fillInterval，或者直接去掉中间更新，优先保证填充速度。

2. Java/Kotlin能否实现高性能Flood Fill #

完全可以。Java/Kotlin作为Android的原生开发语言，结合Android提供的高性能API，足以实现毫秒级的Flood Fill：

• 可以通过优化算法（如扫描线填充）、减少内存开销、避免GC来提升纯Kotlin/Java实现的性能；
• 还可以利用Android的RenderScript框架，将填充操作放到GPU执行，大幅加速像素处理；
• 若性能要求极高，也可以通过JNI调用C++实现的高效Flood Fill，但纯Kotlin/Java优化后已能满足大部分场景需求。

3. 实现1秒内完成任意大小区域着色的方案 #

结合以下措施可实现目标：

1. 切换到扫描线填充算法：扫描线填充通过一次性处理连续行像素，将队列操作次数从O(N)降到O(行数)，性能提升数倍。
2. 使用RenderScript加速：编写自定义RenderScript内核处理Flood Fill，利用GPU并行处理像素，即使是大尺寸Bitmap也能在毫秒级完成。
3. 预计算所有渐变数据：将Shader生成的渐变像素一次性读取到数组，填充时直接写入，避免单像素读取的开销。
4. 避免不必要的UI更新：仅在填充完成后更新Bitmap并调用invalidate()，去掉中间的进度更新，减少主线程开销。
5. 使用可变Bitmap：创建Bitmap时指定Bitmap.Config.ARGB_8888并设置为可变，避免Bitmap复制的开销。
6. 优化颜色匹配逻辑：将颜色匹配的判断逻辑内联，避免方法调用开销；若允许，使用RGB565格式Bitmap减少像素处理的计算量。

内容的提问来源于stack exchange，提问作者Rasool Muhammad