1.背景

在發(fā)現(xiàn)百日大戰(zhàn)時(shí)景項(xiàng)目中烫止。有一個(gè)創(chuàng)新玩法，就是通過篩選圖片主色調(diào)來(lái)顯示如紅色系戳稽，藍(lán)色系照片馆蠕。這就涉及到了圖片主色調(diào)的提取。技術(shù)選型為客戶端進(jìn)行圖片顏色提取惊奇，上傳到服務(wù)端互躬。但是由于項(xiàng)目時(shí)間限制，iOS和Android的圖片色調(diào)提取算法不一樣颂郎。Android采用的是Google官方推出的Palette算法吼渡，為了統(tǒng)一，在這一期我去研究了一下Palette算法乓序，并將它OC化寺酪。

2.Google Palette算法簡(jiǎn)介

Palette算法是Android Lillipop中新增的特性。它可以從一張圖中提取主要顏色竭缝，然后把提取的顏色融入的App的UI之中》课現(xiàn)在在很多設(shè)計(jì)出彩的泛前端展示屆非常普遍，如知乎等抬纸。大致效果如下:

可以看出來(lái)Android在Material Design上下了一番功夫咙俩。在很多Android官方的demo里，各種炫酷效果層出不窮湿故。那我們就順勢(shì)站在巨人的肩膀上阿趁，將他人拿手之處，為我所用坛猪！

3.Palette算法分析

相比于很多傳統(tǒng)的圖片提取算法脖阵，Palette的特點(diǎn)是不單單是去篩選中出現(xiàn)顏色最多的。而是從使用角度出發(fā)墅茉，通過六種模式命黔，如活力色彩，柔和色彩等就斤，篩選出更符合人眼篩選視覺焦點(diǎn)的顏色悍募。如夜晚中的霓虹燈，白色背景的產(chǎn)品照洋机。同時(shí)坠宴，也可以自定義篩選模式，輸入自己的篩選規(guī)則绷旗，得到目標(biāo)顏色喜鼓。下面將逐步分析一下每個(gè)步驟副砍。

(1)壓縮圖片，遍歷圖片像素庄岖，引出顏色直方圖的概念豁翎。并將不同的顏色存入新的顏色數(shù)組。

    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算法為了減少運(yùn)算量顿锰，加快運(yùn)算速度谨垃。一共做了兩個(gè)事情，第一是將圖片壓縮硼控。第二個(gè)是將RGB888顏色空間的顏色轉(zhuǎn)變成RGB555顏色空間，這樣就會(huì)使整個(gè)直方圖數(shù)組以及顏色數(shù)組長(zhǎng)度大大減小胳赌，又不會(huì)太影響計(jì)算結(jié)果牢撼。

顏色直方圖的概念可以想象成一個(gè)顏色柱狀分布圖，某一柱越高疑苫，這柱代表的顏色在圖片中也就越多熏版。它本質(zhì)上是一個(gè)int類型的一維數(shù)組。

    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++;
        }
    }
    

將不同的顏色存進(jìn)distinctColors捍掺，留在后面進(jìn)行判斷撼短。

(2)判斷顏色種類是否大于設(shè)定的最大顏色數(shù)。

最大顏色數(shù)在設(shè)計(jì)上可以設(shè)計(jì)為接收入?yún)⑼ξ穑瑵M足不同使用者的需要曲横，默認(rèn)值為16。這個(gè)值不宜過大不瓶，因?yàn)槿绻^大的話禾嫉，圖片顏色會(huì)分的很散，圖片顏色比較分散的時(shí)候蚊丐，得出來(lái)的顏色可能會(huì)偏向某一小部分顏色熙参，而不是從整體上來(lái)綜合判斷。而當(dāng)圖片篩選出來(lái)的顏色種類小于MaxColorNum的時(shí)候麦备，整個(gè)流程會(huì)簡(jiǎn)單很多孽椰。

        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];
        }

這里引出了一個(gè)新的概念，叫Swatch(樣本)凛篙。Swatch是最終被作為參考進(jìn)行模式篩選的數(shù)據(jù)結(jié)構(gòu)黍匾，它有兩個(gè)最主要的屬性，一個(gè)是Color鞋诗，這個(gè)Color是最終要被展示出來(lái)的Color膀捷，所以需要的是RGB888空間的顏色。另外一個(gè)是Population削彬，它來(lái)自于hist直方圖全庸。是作為之后進(jìn)行模式篩選的時(shí)候一個(gè)重要的權(quán)重因素秀仲。但是如果顏色個(gè)數(shù)超出了最大顏色數(shù)，則需要進(jìn)行第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是一個(gè)新的概念覆劈，它理解起來(lái)稍微抽象一點(diǎn)保礼。可以這樣來(lái)理解责语，我們擁有的顏色過多炮障，但是我們只需要提取出例如16種顏色，需要需要用16個(gè)“筐”把顏色相近的顏色筐在一起坤候，最終用每個(gè)筐的平均顏色來(lái)代表提取出來(lái)的16種主色調(diào)胁赢。它的屬性如下:

@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

其中l(wèi)owerIndex和upperIndex指的是在所有的顏色數(shù)組distinctColors中，VBox所持有的顏色范圍白筹。Population代表的是這個(gè)顏色范圍中智末，一共有多少個(gè)像素點(diǎn)。其它的則代表R,G,B值各自的最大最小值徒河。
它決定了該VBox的Volume系馆。范圍越大，Volume越大顽照，當(dāng)分裂VBox的時(shí)候由蘑，總是分裂當(dāng)前隊(duì)列中VBox里Volume最大的那個(gè)。

- (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的分裂規(guī)則是像素中點(diǎn)分裂棒厘，從lowerIndex遞增到upperIndex纵穿，如果某一個(gè)點(diǎn)讓整個(gè)像素個(gè)數(shù)累加起來(lái)大于了VBox像素個(gè)數(shù)的一半，則這個(gè)點(diǎn)就是splitPoint奢人。而優(yōu)先隊(duì)列的排序規(guī)則是谓媒，隊(duì)首永遠(yuǎn)是Volume最大的VBox，從大概率上來(lái)講何乎，這總是代表像素個(gè)數(shù)最多的VBox句惯。當(dāng)VBox個(gè)數(shù)大于最大顏色個(gè)數(shù)的時(shí)候，則return支救，獲得優(yōu)先隊(duì)列中每個(gè)VBox的平均顏色抢野。并生成平均顏色，之后將每個(gè)VBox轉(zhuǎn)換成了一個(gè)一個(gè)的Swatch各墨。

(4)找到某一種模式下得分最高的Swatch指孤，也就是獲得了最終的色調(diào)提取值。

在Palette算法里，“模式”對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)是target恃轩。它對(duì)顏色的識(shí)別和篩選不是使用的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主要保存了飽和度和明度以及權(quán)重的數(shù)組叉跛。數(shù)組里保存了最小值松忍，最大值，和目標(biāo)值筷厘。這些參數(shù)都是后面用來(lái)給HSL顏色值評(píng)分用的鸣峭。這些值是經(jīng)過Google的團(tuán)隊(duì)進(jìn)行調(diào)優(yōu)之后，篩選出來(lái)的值酥艳√埽可以說(shuō)是整套算法中最有價(jià)值的參數(shù)。

- (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;
}

通過這些已經(jīng)經(jīng)過調(diào)優(yōu)的參數(shù)充石，可以得出每一項(xiàng)的得分：飽和度得分更扁，明度得分，像素Population得分赫冬，將三項(xiàng)得分加起來(lái)，可以得到該Target評(píng)估得分最高的Swatch溃列，也就是我們最終要提取的對(duì)應(yīng)顏色值劲厌。分值具體的具體方法如下:

- (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化效果展示。

圖上紅框部分即是篩選出來(lái)的主題色听隐。

4.最后

該算法已經(jīng)運(yùn)用在了飛豬發(fā)現(xiàn)廣場(chǎng)的時(shí)景項(xiàng)目中（Android版本）补鼻。下一期，iOS端也會(huì)切換成這種提取算法雅任。并且將這套算法沉淀在基礎(chǔ)線风范，只需要使用UIImage+Palette的接口即可調(diào)用』γ矗考慮到它的使用場(chǎng)景硼婿，會(huì)盡快沉淀為SDK，屆時(shí)會(huì)更新github地址禽车，有需求的同學(xué)保持關(guān)注哦~