143
京東網上商城
Google Palette算法詳解以及OC化
1.背景
在發現百日大戰時景項目中。有一個創新玩法，就是通過篩選圖片主色調來顯示如紅色係，藍色係照片。這就涉及到了圖片主色調的提取。技術選型為客戶端進行圖片顏色提取，上傳到服務端。但是由於項目時間限製，iOS和Android的圖片色調提取算法不一樣。Android采用的是Google官方推出的Palette算法，為了統一，在這一期我去研究了一下Palette算法，並將它OC化。最終將作為一個兩端統一的技術方案，提供SDK到海納平台上。
2.Google Palette算法簡介
Palette算法是Android Lillipop中新增的特性。它可以從一張圖中提取主要顏色，然後把提取的顏色融入的App的UI之中。現在在很多設計出彩的泛前端展示屆非常普遍，如知乎等。大致效果如下:
可以看出來Android在Material Design上下了一番功夫。在很多Android官方的demo裏，各種炫酷效果層出不窮。那我們就順勢站在巨人的肩膀上，將他人拿手之處，為我所用！
3.Palette算法分析
相比於很多傳統的圖片提取算法，Palette的特點是不單單是去篩選中出現顏色最多的。而是從使用角度出發，通過六種模式，如活力色彩，柔和色彩等，篩選出更符合人眼篩選視覺焦點的顏色。如夜晚中的霓虹燈，白色背景的產品照。同時，也可以自定義篩選模式，輸入自己的篩選規則，得到目標顏色。下麵將逐步分析一下每個步驟。
unsigned int pixelCount;
unsigned char *rawData = [self rawPixelDataFromImage:_image pixelCount:&pixelCount];
if (!rawData){
return;
}
NSInteger red,green,blue;
for (int pixelIndex = 0 ; pixelIndex < pixelCount; pixelIndex++){
red = (NSInteger)rawData[pixelIndex*4+0];
green = (NSInteger)rawData[pixelIndex*4+1];
blue = (NSInteger)rawData[pixelIndex*4+2];
red = [TRIPPaletteColorUtils modifyWordWidthWithValue:red currentWidth:8 targetWidth:QUANTIZE_WORD_WIDTH];
green = [TRIPPaletteColorUtils modifyWordWidthWithValue:green currentWidth:8 targetWidth:QUANTIZE_WORD_WIDTH];
blue = [TRIPPaletteColorUtils modifyWordWidthWithValue:blue currentWidth:8 targetWidth:QUANTIZE_WORD_WIDTH];
NSInteger quantizedColor = red << 2*QUANTIZE_WORD_WIDTH | green << QUANTIZE_WORD_WIDTH | blue;
hist [quantizedColor] ++;
}
Palette算法為了減少運算量，加快運算速度。一共做了兩個事情，第一是將圖片壓縮。第二個是將RGB888顏色空間的顏色轉變成RGB555顏色空間，這樣就會使整個直方圖數組以及顏色數組長度大大減小，又不會太影響計算結果。
顏色直方圖的概念可以想象成一個顏色柱狀分布圖，某一柱越高，這柱代表的顏色在圖片中也就越多。它本質上是一個int類型的一維數組。
NSInteger distinctColorCount = 0;
NSInteger length = sizeof(hist)/sizeof(hist[0]);
for (NSInteger color = 0 ; color < length ;color++){
if (hist[color] > 0 && [self shouldIgnoreColor:color]){
hist[color] = 0;
}
if (hist[color] > 0){
distinctColorCount ++;
}
}
NSInteger distinctColorIndex = 0;
_distinctColors = [[NSMutableArray alloc]init];
for (NSInteger color = 0; color < length ;color++){
if (hist[color] > 0){
[_distinctColors addObject: [NSNumber numberWithInt:color]];
distinctColorIndex++;
}
}
將不同的顏色存進distinctColors，留在後麵進行判斷。
最大顏色數在設計上可以設計為接收入參，滿足不同使用者的需要，默認值為16。這個值不宜過大，因為如果過大的話，圖片顏色會分的很散，圖片顏色比較分散的時候，得出來的顏色可能會偏向某一小部分顏色，而不是從整體上來綜合判斷。而當圖片篩選出來的顏色種類小於MaxColorNum的時候，整個流程會簡單很多。
for (NSInteger i = 0;i < distinctColorCount ; i++){
NSInteger color = [_distinctColors[i] integerValue];
NSInteger population = hist[color];
NSInteger red = [TRIPPaletteColorUtils quantizedRed:color];
NSInteger green = [TRIPPaletteColorUtils quantizedGreen:color];
NSInteger blue = [TRIPPaletteColorUtils quantizedBlue:color];
red = [TRIPPaletteColorUtils modifyWordWidthWithValue:red currentWidth:QUANTIZE_WORD_WIDTH targetWidth:8];
green = [TRIPPaletteColorUtils modifyWordWidthWithValue:green currentWidth:QUANTIZE_WORD_WIDTH targetWidth:8];
blue = [TRIPPaletteColorUtils modifyWordWidthWithValue:blue currentWidth:QUANTIZE_WORD_WIDTH targetWidth:8];
color = red << 2 * 8 | green << 8 | blue;
TRIPPaletteSwatch *swatch = [[TRIPPaletteSwatch alloc]initWithColorInt:color population:population];
[swatchs addObject:swatch];
}
這裏引出了一個新的概念，叫Swatch(樣本)。Swatch是最終被作為參考進行模式篩選的數據結構，它有兩個最主要的屬性，一個是Color，這個Color是最終要被展示出來的Color，所以需要的是RGB888空間的顏色。另外一個是Population，它來自於hist直方圖。是作為之後進行模式篩選的時候一個重要的權重因素。但是如果顏色個數超出了最大顏色數，則需要進行第3步。
_priorityArray = [[TRIPPaletteVBoxArray alloc]init];
_colorVBox = [[VBox alloc]initWithLowerIndex:0 upperIndex:distinctColorIndex colorArray:_distinctColors];
[_priorityArray addVBox:_colorVBox];
// split the VBox
[self splitBoxes:_priorityArray];
//Switch VBox to Swatch
self.swatchArray = [self generateAverageColors:_priorityArray];
VBox是一個新的概念，它理解起來稍微抽象一點。可以這樣來理解，我們擁有的顏色過多，但是我們隻需要提取出例如16種顏色，需要需要用16個“筐”把顏色相近的顏色筐在一起，最終用每個筐的平均顏色來代表提取出來的16種主色調。它的屬性如下:
@interface VBox :NSObject
@property (nonatomic,assign) NSInteger lowerIndex;
@property (nonatomic,assign) NSInteger upperIndex;
@property (nonatomic,strong) NSMutableArray *distinctColors;
@property (nonatomic,assign) NSInteger population;
@property (nonatomic,assign) NSInteger minRed;
@property (nonatomic,assign) NSInteger maxRed;
@property (nonatomic,assign) NSInteger minGreen;
@property (nonatomic,assign) NSInteger maxGreen;
@property (nonatomic,assign) NSInteger minBlue;
@property (nonatomic,assign) NSInteger maxBlue;
@end
其中lowerIndex和upperIndex指的是在所有的顏色數組distinctColors中，VBox所持有的顏色範圍。Population代表的是這個顏色範圍中，一共有多少個像素點。其它的則代表R,G,B值各自的最大最小值。
它決定了該VBox的Volume。範圍越大，Volume越大，當分裂VBox的時候，總是分裂當前隊列中VBox裏Volume最大的那個。
- (void)splitBoxes:(TRIPPaletteVBoxArray*)queue{
//queue is a priority queue.
while (queue.count < maxColorNum) {
VBox *vbox = [queue objectAtIndex:0];
if (vbox != nil && [vbox canSplit]) {
// First split the box, and offer the result
[queue addVBox:[vbox splitBox]];
// Then offer the box back
[queue addVBox:vbox];
}else{
NSLog(@"All boxes split");
return;
}
}
}
VBox的分裂規則是像素中點分裂，從lowerIndex遞增到upperIndex，如果某一個點讓整個像素個數累加起來大於了VBox像素個數的一半，則這個點就是splitPoint。而優先隊列的排序規則是，隊首永遠是Volume最大的VBox，從大概率上來講，這總是代表像素個數最多的VBox。當VBox個數大於最大顏色個數的時候，則return，獲得優先隊列中每個VBox的平均顏色。並生成平均顏色，之後將每個VBox轉換成了一個一個的Swatch。
在Palette算法裏，“模式”對應的數據結構是target。它對顏色的識別和篩選不是使用的RGB色彩空間，而采用的是HSL顏色模型。它的主要屬性如下:
@interface TRIPPaletteTarget()
@property (nonatomic,strong) NSMutableArray *saturationTargets;
@property (nonatomic,strong) NSMutableArray *lightnessTargets;
@property (nonatomic,strong) NSMutableArray* weights;
@property (nonatomic,assign) BOOL isExclusive; // default to true
@property (nonatomic,assign) PaletteTargetMode mode;
@end
Target主要保存了飽和度和明度以及權重的數組。數組裏保存了最小值，最大值，和目標值。這些參數都是後麵用來給HSL顏色值評分用的。這些值是經過Google的團隊進行調優之後，篩選出來的值。可以說是整套算法中最有價值的參數。
- (TRIPPaletteSwatch*)getMaxScoredSwatchForTarget:(TRIPPaletteTarget*)target{
CGFloat maxScore = 0;
TRIPPaletteSwatch *maxScoreSwatch = nil;
for (NSInteger i = 0 ; i<_swatchArray.count; i++){
TRIPPaletteSwatch *swatch = [_swatchArray objectAtIndex:i];
if ([self shouldBeScoredForTarget:swatch target:target]){
CGFloat score = [self generateScoreForTarget:target swatch:swatch];
if (maxScore == 0 || score > maxScore){
maxScoreSwatch = swatch;
maxScore = score;
}
}
}
return maxScoreSwatch;
}
通過這些已經經過調優的參數，可以得出每一項的得分：飽和度得分，明度得分，像素Population得分，將三項得分加起來，可以得到該Target評估得分最高的Swatch，也就是我們最終要提取的對應顏色值。分值具體的具體方法如下:
- (CGFloat)generateScoreForTarget:(TRIPPaletteTarget*)target swatch:(TRIPPaletteSwatch*)swatch{
NSArray *hsl = [swatch getHsl];
float saturationScore = 0;
float luminanceScore = 0;
float populationScore = 0;
if ([target getSaturationWeight] > 0) {
saturationScore = [target getSaturationWeight]
* (1.0f - fabsf([hsl[1] floatValue] - [target getTargetSaturation]));
}
if ([target getLumaWeight] > 0) {
luminanceScore = [target getLumaWeight]
* (1.0f - fabsf([hsl[2] floatValue] - [target getTargetLuma]));
}
if ([target getPopulationWeight] > 0) {
populationScore = [target getPopulationWeight]
* ([swatch getPopulation] / (float) _maxPopulation);
}
return saturationScore + luminanceScore + populationScore;
}
圖上紅框部分即是篩選出來的主題色。
4.最後
該算法已經運用在了飛豬發現廣場的時景項目中（Android版本）。下一期，iOS端也會切換成這種提取算法。並且將這套算法沉澱在基礎線，隻需要使用UIImage+Palette的接口即可調用。考慮到它的使用場景，會盡快沉澱為SDK，供集團內其它App使用。
最後更新：2017-04-24 10:30:40