7

I created this extension for "bucket fill" (flood fill) of touch point:

extension UIImageView {

    func bucketFill(startPoint: CGPoint, newColor: UIColor) {
        var newRed, newGreen, newBlue, newAlpha: CUnsignedChar

        let pixelsWide = CGImageGetWidth(self.image!.CGImage)
        let pixelsHigh = CGImageGetHeight(self.image!.CGImage)
        let rect = CGRect(x:0, y:0, width:Int(pixelsWide), height:Int(pixelsHigh))

        let bitmapBytesPerRow = Int(pixelsWide) * 4


        var context = self.image!.createARGBBitmapContext()

        //Clear the context
        CGContextClearRect(context, rect)

        // Draw the image to the bitmap context. Once we draw, the memory
        // allocated for the context for rendering will then contain the
        // raw image data in the specified color space.
        CGContextDrawImage(context, rect, self.image!.CGImage)

        var data = CGBitmapContextGetData(context)
        var dataType = UnsafeMutablePointer<UInt8>(data)

        let newColorRef = CGColorGetComponents(newColor.CGColor)
        if(CGColorGetNumberOfComponents(newColor.CGColor) == 2) {
            newRed = CUnsignedChar(newColorRef[0] * 255) // CUnsignedChar
            newGreen = CUnsignedChar(newColorRef[0] * 255)
            newBlue = CUnsignedChar(newColorRef[0] * 255)
            newAlpha = CUnsignedChar(newColorRef[1])
        } else {
            newRed = CUnsignedChar(newColorRef[0] * 255)
            newGreen = CUnsignedChar(newColorRef[1] * 255)
            newBlue = CUnsignedChar(newColorRef[2] * 255)
            newAlpha = CUnsignedChar(newColorRef[3])
        }
        let newColorStr = ColorRGB(red: newRed, green: newGreen, blue: newBlue)

        var stack = Stack()

        let offset = 4*((Int(pixelsWide) * Int(startPoint.y)) + Int(startPoint.x))
        //let alpha = dataType[offset]
        let startRed: UInt8 = dataType[offset+1]
        let startGreen: UInt8 = dataType[offset+2]
        let startBlue: UInt8 = dataType[offset+3]

        stack.push(startPoint)

        while(!stack.isEmpty()) {

            let point: CGPoint = stack.pop() as! CGPoint

            let offset = 4*((Int(pixelsWide) * Int(point.y)) + Int(point.x))
            let alpha = dataType[offset]
            let red: UInt8 = dataType[offset+1]
            let green: UInt8 = dataType[offset+2]
            let blue: UInt8 = dataType[offset+3]

            if (red == newRed && green == newGreen && blue == newBlue) {
                continue
            }

            if (red.absoluteDifference(startRed) < 4 && green.absoluteDifference(startGreen) < 4 && blue.absoluteDifference(startBlue) < 4) {

                dataType[offset] = 255
                dataType[offset + 1] = newRed
                dataType[offset + 2] = newGreen
                dataType[offset + 3] = newBlue

                if (point.x > 0) {
                    stack.push(CGPoint(x: point.x - 1, y: point.y))
                }

                if (point.x < CGFloat(pixelsWide)) {
                    stack.push(CGPoint(x: point.x + 1, y: point.y))
                }

                if (point.y > 0) {
                    stack.push(CGPoint(x: point.x, y: point.y - 1))
                }

                if (point.y < CGFloat(pixelsHigh)) {
                    stack.push(CGPoint(x: point.x, y: point.y + 1))
                }
            } else {

            }
        }

        let colorSpace = CGColorSpaceCreateDeviceRGB()
        let bitmapInfo = CGBitmapInfo(rawValue: CGImageAlphaInfo.PremultipliedFirst.rawValue)
        let finalContext = CGBitmapContextCreate(data, pixelsWide, pixelsHigh, CLong(8), CLong(bitmapBytesPerRow), colorSpace, bitmapInfo)

        let imageRef = CGBitmapContextCreateImage(finalContext)
        self.image = UIImage(CGImage: imageRef, scale: self.image!.scale,orientation: self.image!.imageOrientation)
    }
}

Now I would like to improve performance. How can I make this algorithm work faster? UInt8.absoluteDifference extension is my attempt to include almost same colors to flood fill and it's working but this could be really improve and I know it but I don't know how.

extension UInt8 {

    func absoluteDifference(subtrahend: UInt8) -> UInt8 {
        if (self > subtrahend) {
            return self - subtrahend;
        } else {
            return subtrahend - self;
        }
    }
}

My Stack class:

class Stack {
    var count: Int = 0
    var head: Node = Node()

    init() {
    }

    func isEmpty() -> Bool {
        return self.count == 0
    }

    func push(value: Any) {
        if isEmpty() {
            self.head = Node()
        }

        var node = Node(value: value)
        node.next = self.head
        self.head = node
        self.count++
    }

    func pop() -> Any? {
        if isEmpty() {
            return nil
        }

        var node = self.head
        self.head = node.next!
        self.count--

        return node.value
    }
}

Thanks for help

Libor Zapletal
  • 13,752
  • 20
  • 95
  • 182
  • "How can I make this algorithm work faster" Step one: use Instruments to find out where you're spending your time. – matt Jun 01 '15 at 18:37
  • Why does this need to be faster? What problem are you seeing and how would you know when it is fast enough? – Jonah Jun 01 '15 at 18:40
  • matt: I know that there are tools which helps and I am going to study them. I was just looking for some tips how to make this better. Maybe change Stack class or absoluteDifference extension. Something that you know could be better without using Instruments. – Libor Zapletal Jun 01 '15 at 18:53
  • Jonah: For bigger areas it took a little longer then I would like to have. It took several seconds for filling big area. If I could made this time to half or less it would be really great. – Libor Zapletal Jun 01 '15 at 18:58
  • 2
    For micro-optimizations, you really want to use a profiler. That said, at a broad overview kind of level, you'd be better off using an array-based contiguous structure rather than a linked list for your stack. Also, a bit more work, but ideally you want to exploit spatial locality in the image. So you want to fill rows (scanlines) horizontally and only go up and down when you've finished a scanline. Another minor thing is to put less stress on your stack -- instead of pushing to the stack unwanted neighbors and then skipping the iteration after popping, just don't push those pixels at all. –  Jun 01 '15 at 19:18
  • I am trying to understand this nice bucketFill, method or yours, but I get a few error messages, the first one being: Value of type 'UIImage' has no member 'createARGBBitmapContext' Since I have no experience with extensions I may well be doing something wrong. – Michel Oct 23 '15 at 17:57
  • Did you ever get this optimised any further. I've adapted it for my app and would be interested in your results before I dive into optimising myself. – tonyedwardspz Nov 25 '15 at 13:29

0 Answers0