Count colors in image: `NSCountedSet` and `colorAtX` are very slow

Question

I'm making an OS X app which creates a color scheme from the main colors of an image.

As a first step, I'm using NSCountedSet and colorAtX to get all the colors from an image and count their occurrences:

func sampleImage(#width: Int, height: Int, imageRep: NSBitmapImageRep) -> (NSCountedSet, NSCountedSet) {
    // Store all colors from image
    var colors = NSCountedSet(capacity: width * height)
    // Store the colors from left edge of the image
    var leftEdgeColors = NSCountedSet(capacity: height)
    // Loop over the image pixels
    var x = 0
    var y = 0
    while x < width {
        while y < height {
            // Instruments shows that `colorAtX` is very slow
            // and using `NSCountedSet` is also very slow
            if let color = imageRep.colorAtX(x, y: y) {
                if x == 0 {
                    leftEdgeColors.addObject(color)
                }
                colors.addObject(color)
            }
            y++
        }
        // Reset y every x loop
        y = 0
        // We sample a vertical line every x pixels
        x += 1
    }
    return (colors, leftEdgeColors)
}

My problem is that this is very slow. In Instruments, I see there's two big bottlenecks: with NSCountedSet and with colorAtX.

So first I thought maybe replace NSCountedSet by a pure Swift equivalent, but the new implementation was unsurprisingly much slower than NSCountedSet.

For colorAtX, there's this interesting SO answer but I haven't been able to translate it to Swift (and I can't use a bridging header to Objective-C for this project).

My problem when trying to translate this is I don't understand the unsigned char and char parts in the answer.

What should I try to scan the colors faster than with colorAtX?

• Continue working on adapting the Objective-C answer because it's a good answer? Despite being stuck for now, maybe I can achieve this later.

• Use another Foundation/Cocoa method that I don't know of?

• Anything else that I could try to improve my code?

TL;DR

colorAtX is slow, and I don't understand how to adapt this Objective-C answer to Swift because of unsigned char.

Sjambok

Answer 1

The fastest alternative to colorAtX() would be iterating over the raw bytes of the image using let bitmapBytes = imageRep.bitmapData and composing the colour yourself from that information, which should be really simple if it's just RGBA data. Instead of your for x/y loop, do something like this...

let bitmapBytes = imageRep.bitmapData
var colors = Dictionary<UInt32, Int>()

var index = 0
for _ in 0..<(width * height) {
    let r = UInt32(bitmapBytes[index++])
    let g = UInt32(bitmapBytes[index++])
    let b = UInt32(bitmapBytes[index++])
    let a = UInt32(bitmapBytes[index++])
    let finalColor = (r << 24) + (g << 16) + (b << 8) + a   

    if colors[finalColor] == nil {
        colors[finalColor] = 1
    } else {
        colors[finalColor]!++
    }
}

You will have to check the order of the RGBA values though, I just guessed!

The quickest way to maintain a count might just be a [Int, Int] dictionary of pixel values to counts, doing something like colors[color]++. Later on if you need to you can convert that to a NSColor using NSColor(calibratedRed red: CGFloat, green green: CGFloat, blue blue: CGFloat, alpha alpha: CGFloat)

Blunt

Thank you for your insight. I believe this is the technique used in the Objective-C answer I was referring to? But I'm stuck for now because I don't understand how to translate the unsigned char parts to Swift. – Sjambok

Sorry but I don't understand how to use your answer. :/ What is "index++"? And how to apply this analysis to each pixel if I can't loop over bitmapBytes? It looks promising, though, I'm just totally confused... – Sjambok

I've updated, does that all make sense? I'm not near a Mac so I can only verify that it compiles on SwiftStub, but it should give you an idea! – Blunt

Thank you very much, now I understand what's happening here. :) Unfortunately sampling the image with this solution is much slower than before when using my standard 600x600 test image. – Sjambok

Can you profile and find which part of the above is slow? The byte-walking bit should be blazing fast, although you might have to play with Swift's optimization levels a bit. – Blunt

Following your comment I ran a test with the scheme set to "release" instead of "debug". Now your solution is actually a bit faster than with colorAtX, it's a win! Thank you. :D – Sjambok

Awesome! But 40ms to do a 600x600 image seems really slow still, maybe its the dictionary? Have you tried using NSCountedSet with a UInt32 key? Profiling the calls in the method itself might be the only way. – Blunt

Good news: I've discovered a bias in the tests I ran earlier today (I had x += 10 instead of x += 1 ...). Once fixed, and once I've made the tests closer to the real app usage and set the compiler to Release, my original code takes 6.5 secs to process a batch of ten 600x600 images while your version takes 0.4 secs to process the same batch. :) Thanks again for this answer, it helped a lot. – Sjambok