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

297

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?

Terceiro exemplo

LuisEspinoza
fonte
9
A fórmula de contraste de cores do w3c pode fazer parte da resposta. Meus próprios testes empíricos mostram que essa fórmula é usada pelo MS Word para decidir sua fonte de cor automática. Procure por "brilho cor é determinada pela seguinte fórmula" [fórmula contraste de cor W3C] [1] [1]: w3.org/TR/AERT#color-contrast
bluedog
@ Bluedog, acho que você está certo. Eu tentei muitas capas do meu álbum e sempre a fonte tem contraste suficiente com o fundo para vê-la claramente.
LuisEspinoza
1
Outra coisa a se notar é que parece diferir entre o Mac OS e o Windows: twitter.com/grimfrog/status/275187988374380546
Tom Irving
2
Eu poderia imaginar que talvez não apenas a quantidade de cores, mas também seus valores de saturação façam parte do cálculo: minhas experiências me levaram a conclusões, que destacam que as cores geralmente são escolhidas como cor de fundo, embora ocorram em poucas áreas do imagem. É por isso que acredito que olhar para o histograma da imagem da capa e seus picos pode ser útil e, com base em alguns parâmetros ajustados, a cor é escolhida.
Raffael
2
Veja outra resposta em panic.com/blog/2012/12/itunes-11-and-colors
Mark Ransom

Respostas:

423

Exemplo 1

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

Saída 1

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

Saída final

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

Mais exemplos

Seth Thompson
fonte
3
OK @Seth Thompson, parece muito promissor. Vou tentar por mim mesmo, vai demorar alguns dias, por favor, seja paciente.
LuisSpinoza
6
Solução bastante impressionante. Agora, precisamos de uma porta do Mathematica para o Objective-C, que é uma luta difícil.
loretoparisi 3/12/12
1
+1 para esta resposta muito detalhada!
Marius Schulz
1
@cormullion LUV (e LAB) ambos buscam uniformidade perceptiva. No entanto, não encontrei nenhuma referência explícita ao uso de distâncias euclidianas em qualquer espaço de cores. Meu palpite é que, se nada mais, ambos seriam melhores que RGB.
Seth Thompson
6
Isto é o que eu gosto de chamar de "Chuck Norris Resposta"
MCKapur
44

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.

Screenshot_Mona

LuisEspinoza
fonte
2
+1 - Material muito legal, e um grande exemplo de como algoritmo de desenvolvimento e desenvolvimento de aplicações tanto pode ser muito interessante em seu próprio direito
Yuval Karmi
1
+1 para verificar o contraste.
Brianmearns
É legal, mas como você está arredondando os valores de hash para cada cor? Acho que poderia quebrar esse algoritmo facilmente, simplesmente adicionando um pequeno logotipo "Explícito" em preto e branco no canto inferior direito, e você realmente está adicionando um foco para preto e branco. De qualquer forma, este algoritmo poderia funcionar melhor para imagens com base clip-art, mas se você tem a imagem em 36x36 aqueles falhar casos serão feitos mais raros pelo anti-aliasing
Jack Franzen
Uma palavra: FANTÁSTICO!
Teddy
16

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.

Mike Akers
fonte
15

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).

Matthias
fonte
sim, eu já verifiquei. Infelizmente parece mal documentado.
LuisEspinoza
O comentário importante no ColorTunes é a referência ao (algoritmo de quantização de corte mediano) [ leptonica.com/papers/mediancut.pdf] . Eu apenas implementei isso em python em cerca de 2 horas, apenas forme a descrição no artigo e prefiro a minha implementação do algoritmo de Seth acima. Gosto dos resultados um pouco melhor, mas o mais importante é que é um pouco mais rápido (é claro, eu poderia ter implementado o algoritmo de Seth incorretamente).
Brianmearns
@ sh1ftst0rm você tem sua implementação python no github ou em algum outro lugar? Cheers
Anentropic
@ Anentropic Desculpe, eu não. Fazia parte de um projeto particular no qual eu estava trabalhando, e ainda não o extraí. Se eu tiver uma chance, tentarei publicá-lo em algum lugar, mas provavelmente não será tão cedo.
Brianmearns
5

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.

Maël Nison
fonte