¿Cómo funciona el algoritmo para colorear la lista de canciones en iTunes 11? [cerrado]

El nuevo iTunes 11 tiene una vista muy agradable para la lista de canciones de un álbum, eligiendo los colores para las fuentes y el fondo en función de la portada del álbum. ¿Alguien descubrió cómo funciona el algoritmo?

Aproximé el algoritmo de color iTunes 11 en Mathematica dada la portada del álbum como entrada:

Como lo hice

A través de prueba y error, se me ocurrió un algoritmo que funciona en ~ 80% de los álbumes con los que lo he probado.

Diferencias de color

La mayor parte del algoritmo trata de encontrar el color dominante de una imagen. Sin embargo, un requisito previo para encontrar colores dominantes es calcular una diferencia cuantificable entre dos colores. Una forma de calcular la diferencia entre dos colores es calcular su distancia euclidiana en el espacio de color RGB. Sin embargo, la percepción del color humano no coincide muy bien con la distancia en el espacio de color RGB.

Por lo tanto, escribí una función para convertir colores RGB (en la forma {1,1,1} ) a YUV , un espacio de color que es mucho mejor para aproximar la percepción del color:

_{(EDITAR: @cormullion y @Drake señalaron que los espacios de color CIELAB y CIELUV integrados de Mathematica serían igual de adecuados ... parece que reinventé un poco la rueda aquí)}

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
    ]

A continuación, escribí una función para calcular la distancia de color con la conversión anterior:

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

Colores dominantes

Rápidamente descubrí que la función incorporada de Mathematica DominantColors no permite suficiente control preciso para aproximar el algoritmo que utiliza iTunes. Escribí mi propia función en su lugar ...

Un método simple para calcular el color dominante en un grupo de píxeles es recolectar todos los píxeles en cubos de colores similares y luego encontrar el cubo más grande.

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

_{Tenga en cuenta que .1es la tolerancia de cómo los diferentes colores deben ser considerados por separado. También tenga en cuenta que aunque la entrada es una matriz de píxeles en forma de triplete sin formato ( {{1,1,1},{0,0,0}}), devuelvo un RGBColorelemento de Mathematica para aproximar mejor el incorporadoDominantColors función incorporada.}

Mi función real DominantColorsNewagrega la opción de volver a nlos colores dominantes después de filtrar otro color. También expone tolerancias para cada comparación de color:

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
    ]

El resto del algoritmo

Primero cambié el tamaño de la portada del álbum ( 36px, 36px) y reduje los detalles con un filtro bilateral

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

iTunes elige el color de fondo al encontrar el color dominante en los bordes del álbum. Sin embargo, ignora los bordes estrechos de la portada del álbum al recortar la imagen.

thumb = ImageCrop[thumb, 34];

A continuación, encontré el color dominante (con la nueva función anterior) a lo largo del borde más externo de la imagen con una tolerancia predeterminada de .1.

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

Por último, devolví 2 colores dominantes en la imagen en su conjunto, diciéndole a la función que también filtre el color de fondo.

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

_{Los valores de tolerancia anteriores son los siguientes: .1es la diferencia mínima entre colores "separados"; .2es la diferencia mínima entre numerosos colores dominantes (un valor más bajo puede devolver negro y gris oscuro, mientras que un valor más alto asegura más diversidad en los colores dominantes); .5es la diferencia mínima entre los colores dominantes y el fondo (un valor más alto producirá combinaciones de colores de mayor contraste)}

Voila!

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

Notas

El algoritmo se puede aplicar de manera muy general. Ajusté la configuración anterior y los valores de tolerancia hasta el punto en que trabajan para producir colores generalmente correctos para ~ 80% de las portadas de álbumes que probé. Algunos casos extremos ocurren cuandoDominantColorsNew no se encuentran dos colores para los resaltados (es decir, cuando la portada del álbum es monocromática). Mi algoritmo no aborda estos casos, pero sería trivial duplicar la funcionalidad de iTunes: cuando el álbum produce menos de dos resaltados, el título se vuelve blanco o negro dependiendo del mejor contraste con el fondo. Luego, las canciones se convierten en el único color de resaltado si hay uno, o el color del título se desvaneció un poco en el fondo.

Más ejemplos

Con la respuesta de @ Seth-thompson y el comentario de @bluedog, construyo un pequeño proyecto Objective-C (Cocoa-Touch) para generar esquemas de color en función de una imagen.

Puedes consultar el proyecto en:

https://github.com/luisespinoza/LEColorPicker

Por ahora, LEColorPicker está haciendo:

1. La imagen se escala a 36x36 px (esto reduce el tiempo de cálculo).
2. Genera una matriz de píxeles a partir de la imagen.
3. Convierte la matriz de píxeles en espacio YUV.
4. Reúna los colores como lo hace el código de Seth Thompson.
5. Los conjuntos de colores se ordenan por recuento.
6. El algoritmo selecciona los tres colores más dominantes.
7. El más dominante se asigna como fondo.
8. La segunda y tercera mayoría de los dominantes se prueban utilizando la fórmula de contraste de color w3c, para verificar si los colores tienen suficiente contraste con el fondo.
9. Si uno de los colores del texto no pasa la prueba, entonces se asigna a blanco o negro, dependiendo del componente Y.

Eso es por ahora, revisaré el proyecto ColorTunes ( https://github.com/Dannvix/ColorTunes ) y el proyecto Wade Cosgrove para nuevas características. También tengo algunas ideas nuevas para mejorar el resultado del esquema de color.

Wade Cosgrove de Panic escribió una buena publicación de blog describiendo su implementación de un algoritmo que se aproxima al de iTunes. Incluye una implementación de muestra en Objective-C.

También puede consultar ColorTunes, que es una implementación HTML de la vista del álbum de Itunes que utiliza el algoritmo MMCQ (mediana de cuantización del color de corte).

Con la respuesta de @ Seth, implementé el algoritmo para obtener el color dominante en los dos bordes laterales de una imagen usando PHP e Imagick.

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

Se está utilizando para llenar el fondo de las fotos de portada en http://festea.com.br

Acabo de escribir una biblioteca JS implementando aproximadamente el mismo algoritmo que el descrito por @Seth . Está disponible gratuitamente en github.com/arcanis/colibrijs y en NPM como colibrijs.

Hice la misma pregunta en un contexto diferente y fui señalado a http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/ para un Algoritmo de aprendizaje (k significa) que hace lo mismo de manera áspera utilizando puntos de partida aleatorios en la imagen. De esa manera, el algoritmo encuentra colores dominantes por sí mismo.