Como o algoritmo para colorir a lista de músicas no iTunes 11 funciona? [fechadas]

O novo iTunes 11 tem uma visão muito boa da lista de músicas de um álbum, escolhendo as cores das fontes e do fundo em função da capa do álbum. Alguém descobriu como o algoritmo funciona?

Aproximei o algoritmo de cores do iTunes 11 no Mathematica, dada a capa do álbum como entrada:

Como eu fiz isso

Por tentativa e erro, criei um algoritmo que funciona em ~ 80% dos álbuns com os quais o testei.

Diferenças de cores

A maior parte do algoritmo lida com a localização da cor dominante de uma imagem. Um pré-requisito para encontrar cores dominantes, no entanto, é calcular uma diferença quantificável entre duas cores. Uma maneira de calcular a diferença entre duas cores é calcular a distância euclidiana no espaço de cores RGB. No entanto, a percepção de cores humana não combina muito bem com a distância no espaço de cores RGB.

Portanto, escrevi uma função para converter cores RGB (no formulário {1,1,1}) em YUV , um espaço de cores muito melhor na aproximação da percepção de cores:

_{(EDIT: @cormullion e @Drake apontaram que os espaços de cores CIELAB e CIELUV integrados do Mathematica seriam tão adequados ... parece que eu reinventei a roda um pouco aqui)}

convertToYUV[rawRGB_] :=
    Module[{yuv},
        yuv = {{0.299, 0.587, 0.114}, {-0.14713, -0.28886, 0.436},
            {0.615, -0.51499, -0.10001}};
        yuv . rawRGB
    ]

Em seguida, escrevi uma função para calcular a distância da cor com a conversão acima:

ColorDistance[rawRGB1_, rawRGB2_] := 
    EuclideanDistance[convertToYUV @ rawRGB1, convertToYUV @ rawRGB2]

Cores dominantes

Descobri rapidamente que a função interna do Mathematica DominantColorsnão permite controle refinado suficiente para aproximar o algoritmo usado pelo iTunes. Eu escrevi minha própria função ...

Um método simples para calcular a cor dominante em um grupo de pixels é coletar todos os pixels em intervalos de cores semelhantes e encontrar o maior intervalo.

DominantColorSimple[pixelArray_] :=
    Module[{buckets},
        buckets = Gather[pixelArray, ColorDistance[#1,#2] < .1 &];
        buckets = Sort[buckets, Length[#1] > Length[#2] &];
        RGBColor @@ Mean @ First @ buckets
    ]

_{Observe que .1é a tolerância de como as cores diferentes devem ser consideradas separadas. Observe também que, embora a entrada seja uma matriz de pixels na forma tripla bruta ( {{1,1,1},{0,0,0}}), eu retorno um RGBColorelemento Mathematica para aproximar melhor a DominantColorsfunção interna.}

Minha função real DominantColorsNewadiciona a opção de retornar às ncores dominantes após filtrar uma determinada outra cor. Também expõe tolerâncias para cada comparação de cores:

DominantColorsNew[pixelArray_, threshold_: .1, n_: 1, 
    numThreshold_: .2, filterColor_: 0, filterThreshold_: .5] :=
    Module[
        {buckets, color, previous, output},
        buckets = Gather[pixelArray, ColorDistance[#1, #2] < threshold &];
        If[filterColor =!= 0, 
        buckets = 
            Select[buckets, 
                ColorDistance[ Mean[#1], filterColor] > filterThreshold &]];
        buckets = Sort[buckets, Length[#1] > Length[#2] &];
        If[Length @ buckets == 0, Return[{}]];
        color = Mean @ First @ buckets;
        buckets = Drop[buckets, 1];
        output = List[RGBColor @@ color];
        previous = color;
        Do[
            If[Length @ buckets == 0, Return[output]];
            While[
                ColorDistance[(color = Mean @ First @ buckets), previous] < 
                    numThreshold, 
                If[Length @ buckets != 0, buckets = Drop[buckets, 1], 
                    Return[output]]
            ];
            output = Append[output, RGBColor @@ color];
            previous = color,
            {i, n - 1}
        ];
        output
    ]

O resto do algoritmo

Primeiro redimensionei a capa do álbum ( 36px, 36px) e reduzi os detalhes com um filtro bilateral

image = Import["http://i.imgur.com/z2t8y.jpg"]
thumb = ImageResize[ image, 36, Resampling -> "Nearest"];
thumb = BilateralFilter[thumb, 1, .2, MaxIterations -> 2];

O iTunes escolhe a cor de fundo encontrando a cor dominante ao longo das bordas do álbum. No entanto, ignora as margens estreitas da capa do álbum cortando a imagem.

thumb = ImageCrop[thumb, 34];

Em seguida, encontrei a cor dominante (com a nova função acima) ao longo da borda mais externa da imagem com uma tolerância padrão de .1.

border = Flatten[
    Join[ImageData[thumb][[1 ;; 34 ;; 33]] , 
        Transpose @ ImageData[thumb][[All, 1 ;; 34 ;; 33]]], 1];
background = DominantColorsNew[border][[1]];

Por fim, retornei duas cores dominantes na imagem como um todo, dizendo à função para filtrar também a cor de fundo.

highlights = DominantColorsNew[Flatten[ImageData[thumb], 1], .1, 2, .2, 
    List @@ background, .5];
title = highlights[[1]];
songs = highlights[[2]];

_{Os valores de tolerância acima são os seguintes: .1é a diferença mínima entre cores "separadas"; .2é a diferença mínima entre várias cores dominantes (um valor mais baixo pode retornar preto e cinza escuro, enquanto um valor mais alto garante mais diversidade nas cores dominantes); .5é a diferença mínima entre cores dominantes e o plano de fundo (um valor mais alto produzirá combinações de cores com maior contraste)}

Voila!

Graphics[{background, Disk[]}]
Graphics[{title, Disk[]}]
Graphics[{songs, Disk[]}]

Notas

O algoritmo pode ser aplicado de maneira muito geral. Ajustei as configurações acima e os valores de tolerância ao ponto em que eles trabalham para produzir cores geralmente corretas para ~ 80% das capas de álbuns que testei. Alguns casos extremos ocorrem quando DominantColorsNewnão há duas cores para retornar aos destaques (ou seja, quando a capa do álbum é monocromática). Meu algoritmo não trata desses casos, mas seria trivial duplicar a funcionalidade do iTunes: quando o álbum produz menos de dois destaques, o título fica branco ou preto, dependendo do melhor contraste com o fundo. Em seguida, as músicas se tornam a cor de destaque, se houver, ou a cor do título desbotou um pouco o fundo.

Mais exemplos

Com a resposta de @ Seth-Thompson e o comentário de @ bluedog, construo um pequeno projeto Objective-C (Cocoa-Touch) para gerar esquemas de cores em função de uma imagem.

Você pode verificar o projeto em:

https://github.com/luisespinoza/LEColorPicker

Por enquanto, o LEColorPicker está fazendo:

1. A imagem é dimensionada para 36 x 36 px (isso reduz o tempo de computação).
2. Ele gera uma matriz de pixels a partir da imagem.
3. Converte a matriz de pixels em espaço YUV.
4. Reúna cores conforme o código de Seth Thompson.
5. Os conjuntos de cores são classificados por contagem.
6. O algoritmo seleciona as três cores mais dominantes.
7. O mais dominante é atribuído como plano de fundo.
8. O segundo e o terceiro dominantes são testados usando a fórmula de contraste de cores w3c, para verificar se as cores já contrastam com o fundo.
9. Se uma das cores do texto não passar no teste, ela será atribuída ao branco ou ao preto, dependendo do componente Y.

Por enquanto, vou verificar o projeto ColorTunes ( https://github.com/Dannvix/ColorTunes ) e o projeto Wade Cosgrove para novos recursos. Também tenho algumas idéias novas para melhorar o resultado do esquema de cores.

Wade Cosgrove, do Panic, escreveu um bom post descrevendo sua implementação de um algoritmo que se aproxima do do iTunes. Inclui uma implementação de amostra no Objective-C.

Você também pode fazer o check-out do ColorTunes, que é uma implementação HTML da visualização do álbum Itunes, que usa o algoritmo MMCQ (quantização mediana das cores cortadas).

Com a resposta de @ Seth, implementei o algoritmo para obter a cor dominante nas duas bordas laterais de uma imagem usando PHP e Imagick.

https://gist.github.com/philix/5688064#file-simpleimage-php-L81

Está sendo usado para preencher o plano de fundo das fotos da capa em http://festea.com.br

Acabei de escrever uma biblioteca JS implementando aproximadamente o mesmo algoritmo que o descrito por @Seth . Está disponível gratuitamente em github.com/arcanis/colibrijs e no NPM como colibrijs.

Fiz a mesma pergunta em um contexto diferente e fui apontado para http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/ para uma algoritmo de aprendizagem (k significa) que rouco faz a mesma coisa usando pontos de partida aleatórios na imagem. Dessa forma, o algoritmo encontra cores dominantes por si só.