• Stars
    star
    959
  • Rank 47,674 (Top 1.0 %)
  • Language
    Swift
  • License
    MIT License
  • Created almost 10 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

Finding dominant colors of an image using k-means clustering

DominantColor

Finding the dominant colors of an image using the CIE LAB color space and the k-means clustering algorithm.

Algorithm

Color Space

The RGB color space does not take human perception into account, so the CIELAB color space is used instead, which is designed to approximate human vision [1].

Conversion from RGB

The conversion from RGB values to LAB values requires first transforming the RGB values to an absolute color space like sRGB[2]. On iOS, this conversion is not necessary because sRGB is the native device color space[3]. On OS X, the conversion can be performed using -[NSColorSpace sRGBColorSpace].

Once the colors have been converted to sRGB, they are first converted to linear sRGB values and then to CIE XYZ values[4]. Finally, they are converted to the CIE LAB color space[5] using a D65 standard illuminant[6][7].

Color Difference

A color difference algorithm is used to group similar colors. API consumers can choose between the CIE 76[8], CIE 94[9], and CIE 2000[10] algorithms for low, medium, and high color grouping accuracy, respectively. The default algorithm is CIE 94, as it provides results that are close to CIE 2000 with a negligible performance impact in comparison to CIE 76.

Clustering (k-means)

Pixels are grouped into clusters of dominant colors using a standard k-means clustering algorithm[11][12][13].

Choosing K

The k-value was originally chosen based on the rule of thumb k = sqrt(n/2)[14] but this resulted in k-values that were too large to run in a reasonable amount of time for large values of n. Right now, I'm using a magic value of 16 because empirical testing showed that it yielded the best results for many different images but I'm still looking into a number of more data-driven alternate approaches.

Selecting Initial Centroids

The initial centroids are currently selected on a random basis. An alternative approach is to use the k-means++ algorithm, in which after the first centroid is selected randomly, the subsequent centroids are selected with probability proportional to the distance from the randomly selected centroid.

Downsampling

The k-means algorithm has a worst case runtime that is super-polynomial in the input size[15], so sampling large numbers of pixels is a problem. Images are automatically downsampled such that the total number of pixels is less than or equal to a specified maximum number of pixels to sample. The value I've been using is 1000, which is a good balance between accurate results and runtime.

Implementation

Everything is implemented in Swift except for the functions that convert between color spaces, which use GLKit and thus must be written in C (since Swift doesn't support C unions at this time).

Apps

The project includes Mac and iOS apps that can be used to see the results of the algorithm and to run a simple benchmark.

Mac app iOS app

Contact

License

Licensed under the MIT License.

References

1 http://en.wikipedia.org/wiki/Lab_color_space#Advantages
2 http://en.wikipedia.org/wiki/Lab_color_space#RGB_and_CMYK_conversions
3 https://developer.apple.com/library/ios/documentation/GraphicsImaging/Reference/CGColorSpace/index.html
4 http://en.wikipedia.org/wiki/SRGB#The_forward_transformation_.28CIE_xyY_or_CIE_XYZ_to_sRGB.29
5 http://en.wikipedia.org/wiki/Lab_color_space#CIELAB-CIEXYZ_conversions
6 http://en.wikipedia.org/wiki/Illuminant_D65
7 http://www.easyrgb.com/index.php?X=MATH&H=15#text15
8 http://en.wikipedia.org/wiki/Color_difference#CIE76
9 http://en.wikipedia.org/wiki/Color_difference#CIEDE2000
10 http://en.wikipedia.org/wiki/Color_difference#CIEDE2000
11 http://en.wikipedia.org/wiki/K-means_clustering
12 http://users.eecs.northwestern.edu/~wkliao/Kmeans/
13 http://cs.smu.ca/~r_zhang/code/kmeans.c
14 http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set#cite_note-1
15 http://en.wikipedia.org/wiki/K-means%2B%2B

More Repositories

1

InAppViewDebugger

A UIView debugger (like Reveal or Xcode) that can be embedded in an app for on-device view debugging
Swift
1,871
star
2

CocoaMarkdown

Markdown parsing and rendering for iOS and OS X
Objective-C
1,200
star
3

INAppStoreWindow

NSWindow subclass with a highly customizable title bar and traffic lights
Objective-C
1,064
star
4

MarkdownTextView

Rich Markdown editing control for iOS
Swift
686
star
5

SwiftAutoLayout

Tiny Swift DSL for Autolayout
Swift
655
star
6

SNRHUDKit

Code drawn AppKit HUD interface elements
Objective-C
326
star
7

swiftrsrc

Resource code generation tool for Swift
Swift
290
star
8

INDANCSClient

Objective-C Apple Notification Center Service Client
Objective-C
252
star
9

INPopoverController

A customizable popover controller for OS X
Objective-C
196
star
10

SNRSearchIndex

SearchKit backed search for Core Data
Objective-C
190
star
11

Unzip

iOS 8 Action Extension for browsing ZIP files
Objective-C
165
star
12

NSUserNotificationPrivate

Private API showcase for NSUserNotification on OS X
Objective-C
152
star
13

SNRMusicKit

All-in-one framework for browsing and playing music from various sources on iOS and OS X
Objective-C
150
star
14

WWDC-2014

Scholarship submission for WWDC 2014
Objective-C
146
star
15

Ares

Zero-setup P2P file transfer between Macs and iOS devices
Swift
133
star
16

INDockableWindow

A window to which other views can be "docked" to and separated into their own windows
Objective-C
114
star
17

INDLinkLabel

A simple, no frills UILabel subclass with support for links
Swift
82
star
18

SNRFetchedResultsController

Automatic Core Data change tracking for OS X (NSFetchedResultsController port)
Objective-C
81
star
19

INDSequentialTextSelectionManager

Sequential text selection for NSTextViews
Objective-C
74
star
20

OEGridView

High performance Core Animation-based grid view, originally from OpenEmu.
Objective-C
72
star
21

INDGIFPreviewDownloader

[iOS] Retrieves preview images for GIFs by downloading only the first frame
Objective-C
60
star
22

Chip8

CHIP-8 emulator and disassembler written in Swift
Swift
53
star
23

pdfcat

OS X utility for concatenating PDF files
Swift
49
star
24

ReactiveXPC

Signals across process boundaries
Swift
36
star
25

ObjectiveKVDB

Objective-C wrapper for kvdb (https://github.com/dinhviethoa/kvdb)
Objective-C
33
star
26

SwiftTableViews

Type-safe Table Views with Swift
Swift
33
star
27

AlamofireRACExtensions

ReactiveCocoa Swift extensions for Alamofire
Swift
32
star
28

Dial

The beginnings of a replacement Contacts app for iOS.
Objective-C
30
star
29

ReactiveBLE

ReactiveCocoa wrapper for communicating with BLE devices using CoreBluetooth
Objective-C
29
star
30

INSOCKSServer

SOCKS5 proxy server implementation in Objective-C
Objective-C
27
star
31

LiveWebPreview

Web development tool for automatically refreshing a page when the content changes.
Objective-C
20
star
32

SNRLastFMEngine

[DEPRECATED] A modern block-based Objective-C interface to the Last.fm API
Objective-C
19
star
33

AttributedString.swift

Swift library that adds type safety and string interpolation support to NSAttributedString
Swift
18
star
34

INKeychainAccess

[DEPRECATED] Objective-C Keychain Services Wrapper for OS X and iOS
Objective-C
17
star
35

tecs

Projects for The Elements of Computing Systems by Nisan and Schocken
Assembly
15
star
36

INTrafficLightsDisabler

SIMBL plugin to hide the traffic lights on Mac OS X
Objective-C
14
star
37

pebble-lifx

Pebble controller for LIFX bulbs. UAlberta CompE Club Hackathon 2014 project.
Objective-C
11
star
38

xcode-themes

Color themes for Xcode 4 and 5
6
star
39

radars

Apple Radars filed for OS X and iOS.
Objective-C
5
star
40

indragiek.github.com

http://indragie.com
HTML
3
star
41

arduino-copter

Copter game for Arduino + Adafruit TFT
C++
2
star
42

writing

Things that I write
2
star
43

advent-of-code-2020

My Rust solutions for https://adventofcode.com
Rust
1
star
44

bootstrap-no-responsive

Compiled Bootstrap with responsive features disabled
1
star