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的特点是不单单是去筛选中出现颜色最多的。而是从使用角度出发，通过六种模式，如活力色彩，柔和色彩等，筛选出更符合人眼筛选视觉焦点的颜色。如夜晚中的霓虹灯，白色背景的产品照。同时，也可以自定义筛选模式，输入自己的筛选规则，得到目标颜色。下面将逐步分析一下每个步骤。

(1)压缩图片，遍历图片像素，引出颜色直方图的概念。并将不同的颜色存入新的颜色数组。

    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，留在后面进行判断。

(2)判断颜色种类是否大于设定的最大颜色数。

最大颜色数在设计上可以设计为接收入参，满足不同使用者的需要，默认值为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步。

(3)通过VBox分裂的方式，找到代表平均颜色的Swatch。

        _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。

(4)找到某一种模式下得分最高的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;
}

(5)Palette算法OC化效果展示。

图上红框部分即是筛选出来的主题色。

4.最后

该算法已经运用在了飞猪发现广场的时景项目中（Android版本）。下一期，iOS端也会切换成这种提取算法。并且将这套算法沉淀在基础线，只需要使用UIImage+Palette的接口即可调用。考虑到它的使用场景，会尽快沉淀为SDK，供集团内其它App使用。