Как работает алгоритм раскраски списка песен в iTunes 11? [закрыто]

297

Новый iTunes 11 имеет очень хороший вид для списка песен альбома, выбирая цвета для шрифтов и фона в функции обложки альбома. Кто-нибудь разобрался, как работает алгоритм?

Третий пример

algorithm user-interface itunes LuisEspinoza
источник
9
Формула цветового контраста w3c может быть частью ответа. Мои собственные эмпирические тесты показывают, что эта формула используется MS Word, чтобы решить, что это авто-цветной шрифт. Поиск "Яркость цвета определяется по следующей формуле" [формула цветового контраста w3c] [1] [1]: w3.org/TR/AERT#color-contrast
bluedog
@bluedog, я думаю, что ты прав. Я перепробовал много обложек моих альбомов, и всегда шрифт достаточно контрастировал с фоном, чтобы его было ясно видно.
ЛуисЭспиноза
1
Следует также отметить, что в Mac OS и Windows он различается: twitter.com/grimfrog/status/275187988374380546
Том Ирвинг,
2
Я мог бы предположить, что, возможно, не только количество цветов, но также и их значения насыщенности являются частью расчета: мои эксперименты привели меня к выводу, что выделенные цвета часто выбираются как цвет фона, хотя они встречаются в нескольких областях образ. Вот почему я считаю, что просмотр гистограммы изображения обложки и его пиков может быть полезен, и на основании некоторых точно настроенных параметров выбирается цвет.
Рафаэль
2
Смотрите другой ответ на panic.com/blog/2012/12/itunes-11-and-colors
Марк Рэнсом

Ответы:

423

Пример 1

Я приблизил цветовой алгоритм iTunes 11 в Mathematica с учетом обложки альбома:

Выход 1

Как я это сделал

Методом проб и ошибок я придумал алгоритм, который работает на ~ 80% альбомов, с которыми я его тестировал.

Цветовые различия

Основная часть алгоритма связана с поиском доминирующего цвета изображения. Однако предварительным условием для нахождения доминирующих цветов является расчет количественной разницы между двумя цветами. Один из способов расчета разницы между двумя цветами - это вычисление их евклидова расстояния в цветовом пространстве RGB. Однако восприятие цвета человеком не очень хорошо согласуется с расстоянием в цветовом пространстве RGB.

Поэтому я написал функцию для преобразования цветов RGB (в форме {1,1,1}) в YUV , цветовое пространство, которое намного лучше приближает восприятие цвета:

(РЕДАКТИРОВАТЬ: @cormullion и @Drake указали, что встроенные в Mathematica цветовые пространства CIELAB и CIELUV были бы такими же подходящими ... похоже, я немного заново изобрел колесо)

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
    ]

Далее я написал функцию для вычисления цветового расстояния с помощью приведенного выше преобразования:

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

Доминирующие цвета

Я быстро обнаружил, что встроенная функция Mathematica DominantColorsне позволяет достаточно детально управлять, чтобы приблизиться к алгоритму, который использует iTunes. Я написал свою собственную функцию вместо ...

Простой метод вычисления доминирующего цвета в группе пикселей состоит в том, чтобы собрать все пиксели в группы одинаковых цветов и затем найти наибольшую группу.

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

Обратите внимание, что .1допуск на то, как разные цвета должны рассматриваться как отдельные. Также обратите внимание, что хотя входные данные представляют собой массив пикселей в необработанном триплетном виде ( {{1,1,1},{0,0,0}}), я возвращаю RGBColorэлемент Mathematica, чтобы лучше аппроксимировать встроенную DominantColorsфункцию.

Моя действительная функция DominantColorsNewдобавляет возможность возврата к nдоминирующим цветам после фильтрации данного другого цвета. Он также предоставляет допуски для каждого сравнения цветов:

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
    ]

Остальная часть алгоритма

Сначала я изменил размеры обложки альбома ( 36px, 36px) и уменьшил детализацию с помощью двустороннего фильтра

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

iTunes выбирает цвет фона, находя доминирующий цвет по краям альбома. Однако он игнорирует узкие границы обложки альбома, обрезая изображение.

thumb = ImageCrop[thumb, 34];

Затем я нашел доминирующий цвет (с новой функцией выше) вдоль самого внешнего края изображения с допуском по умолчанию .1.

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

Наконец, я вернул 2 доминирующих цвета на изображении в целом, указав функции также отфильтровать фоновый цвет.

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

Вышеуказанные значения допуска: .1минимальная разница между «отдельными» цветами; .2минимальная разница между многочисленными доминирующими цветами (более низкое значение может вернуть черный и темно-серый, тогда как более высокое значение обеспечивает большее разнообразие доминирующих цветов); .5минимальная разница между доминирующими цветами и фоном (более высокое значение даст более контрастные цветовые комбинации)

Вуаля!

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

Окончательный вывод

Ноты

Алгоритм может применяться очень широко. Я настроил вышеуказанные настройки и значения допусков до такой степени, что они работают для получения в целом правильных цветов для ~ 80% обложек альбомов, которые я тестировал. Несколько крайних случаев возникают, когда DominantColorsNewне удается найти два цвета для выделения (например, когда обложка альбома монохромная). Мой алгоритм не учитывает эти случаи, но было бы тривиально дублировать функциональность iTunes: когда альбом дает менее двух бликов, заголовок становится белым или черным в зависимости от лучшей контрастности с фоном. Тогда песни становятся одним цветом подсветки, если он есть, или цвет заголовка немного исчезает на заднем плане.

Больше примеров

Больше примеров

Сет Томпсон
источник
3
ОК @ Сет Томпсон, кажется очень многообещающим. Я собираюсь попробовать это сам, это займет у меня пару дней, пожалуйста, будьте терпеливы.
ЛуисЭспиноза
6
Довольно классное решение. Теперь нужен порт от Mathematica до Objective-C, это тяжелая борьба.
Лоретопариси
1
+1 за этот очень подробный ответ!
Мариус Шульц
1
@cormullion LUV (и LAB) оба стремятся к единообразию восприятия. Однако я не нашел явных ссылок на использование евклидовых расстояний ни в одном цветовом пространстве. Я думаю, что если бы ничего другого, они оба были бы лучше, чем RGB.
Сет Томпсон
6
Это то, что я люблю называть «
Ответом
44

С ответом @ Seth-thompson и комментарием @bluedog я создаю небольшой проект Objective-C (Cocoa-Touch) для генерации цветовых схем в зависимости от изображения.

Вы можете проверить проект по адресу:

https://github.com/luisespinoza/LEColorPicker

На данный момент LEColorPicker делает:

  1. Изображение масштабируется до 36x36 пикселей (это сокращает время вычислений).
  2. Он генерирует массив пикселей из изображения.
  3. Преобразует массив пикселей в пространство YUV.
  4. Собирайте цвета, как это делает код Сета Томпсона.
  5. Наборы цветов отсортированы по количеству.
  6. Алгоритм выбора трех наиболее доминирующих цветов.
  7. Самым доминирующим является Фон.
  8. Второе и третье доминанты тестируются с использованием формулы цветового контраста w3c, чтобы проверить, достаточно ли цветов контрастирует с фоном.
  9. Если один из цветов текста не проходит тест, он назначается белым или черным, в зависимости от компонента Y.

На данный момент я буду проверять проект ColorTunes ( https://github.com/Dannvix/ColorTunes ) и проект Wade Cosgrove на наличие новых функций. Также у меня есть несколько новых идей для улучшения результата цветовой схемы.

Screenshot_Mona

LuisEspinoza
источник
2
+1 - Очень крутая штука и отличный пример того, как разработка алгоритмов и разработка приложений могут быть очень интересными сами по себе
Юваль Карми
1
+1 за проверку контраста.
brianmearns
Да, круто, но как вы округляете значения хеш-функции для каждого цвета? Я думаю, что я мог бы легко сломать этот алгоритм, просто добавив небольшой черно-белый логотип «Явный» в правом нижнем углу, вы действительно добавили фокус для черного и белого. В любом случае, этот алгоритм будет работать лучше для изображений на основе клип-арта, но если у вас есть изображение с разрешением 36x36, эти случаи сбоев будут делаться сглаживанием реже
Джек Францен,
Одним словом: FANTASTIC!
Тедди
16

Уэйд Косгроув из Panic написал хороший пост в блоге, описывающий его реализацию алгоритма, который приближается к алгоритму в iTunes. Он включает пример реализации в Objective-C.

Майк Акерс
источник
15

Вы также можете ознакомиться с ColorTunes, который представляет собой HTML-реализацию представления альбома Itunes, использующего алгоритм MMCQ (квантование среднего цвета среза).

Матиас
источник
да я это уже проверю. К сожалению, кажется, едва документированы.
ЛуисЭспиноза
Важным комментарием в ColorTunes является ссылка на (алгоритм квантования среза медианы) [ leptonica.com/papers/mediancut.pdf] . Я только что реализовал это в python примерно за 2 часа, просто сформировал описание в статье и предпочел это моей реализации алгоритма Сета выше. Мне нравятся результаты немного лучше, но самое главное, они немного быстрее (конечно, я мог неправильно реализовать алгоритм Сета).
brianmearns
@ sh1ftst0rm у тебя есть реализация на python на github или где-то еще? ура
Anentropic
@Anentropic Извините, нет. Это был частный проект, над которым я работал, и я его вообще не извлекал. Если у меня будет возможность, я постараюсь опубликовать это где-нибудь, но, вероятно, не скоро.
brianmearns
5

Я только что написал библиотеку JS, реализующую примерно тот же алгоритм, который описан @Seth . Он свободно доступен на github.com/arcanis/colibrijs и на NPM as colibrijs.

Мэл Нисон
источник
4

Я задал тот же вопрос в другом контексте и был указан на http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/ для алгоритм обучения (k означает), что грубо делает то же самое, используя случайные начальные точки на изображении. Таким образом, алгоритм сам находит доминирующие цвета.

Thomi
источник