Как определить прелбладающий цвет изображения?
Здравствуйте. Есть проблема: нужно определить цвет, который преобладает на изображении, то есть которого больше всего. Естественно с разбросом RGB±10. Может кто знает как это сделать? Называется это по-моему цвет по [COLOR="Red"]моде[/COLOR].
IMHO, такой теме скорее место в Общих Вопросах Программирования. Первое, что пришло в голову по сабджу: усреднить цвета до нужной точности, после чего посчитать количество пикселей каждого цвета.
ну не вовсем
например цвета
123 456 789 , и больше всего цвета 7, поссчитать +-1
тогда если усреднить получим
222 555 888
тк все 7-ки стали 8-ками выдаем что преобладает 7 цвет. в принципе +-1 не нарушено, но если нужен точный результат не катит
например цвета
123 456 789 , и больше всего цвета 7, поссчитать +-1
тогда если усреднить получим
222 555 888
тк все 7-ки стали 8-ками выдаем что преобладает 7 цвет. в принципе +-1 не нарушено, но если нужен точный результат не катит
теоретически можно представить изо как простой массив, какимто образом отсортировать его (каким? хм..) и равнивать рядомстоящие, подсчитывая макс кол-во подряд идущих цветов с расстоянием не больше ±
сортировать можно например по одной составляющей, если есть несколько одинаков значений одной тогда по второй, потом третьей. (может лучше построить дерево)
потом какже как ищется медиана в обычном массиве - проходим интервалом в 2*д (д - наша точность) по первой составляющей , подсчитываем кол-во цветов в этом интервале , в которых вторая и третья составляющие попадают в ±, записываем куданить максимальную сумму цветов в диапазоне и номер этого максимального диапазона. после прохода всего массива/дерева имея список нужных цветов несложно определить который из них центр (наверно лучше нри проходах сделать интервал чуть больше 2*д, и лишние цвета отбросить на этом последнем этапе)
решение довольно громоздкое и медленное.. походу.. но должно работать . корректно.
сортировать можно например по одной составляющей, если есть несколько одинаков значений одной тогда по второй, потом третьей. (может лучше построить дерево)
потом какже как ищется медиана в обычном массиве - проходим интервалом в 2*д (д - наша точность) по первой составляющей , подсчитываем кол-во цветов в этом интервале , в которых вторая и третья составляющие попадают в ±, записываем куданить максимальную сумму цветов в диапазоне и номер этого максимального диапазона. после прохода всего массива/дерева имея список нужных цветов несложно определить который из них центр (наверно лучше нри проходах сделать интервал чуть больше 2*д, и лишние цвета отбросить на этом последнем этапе)
решение довольно громоздкое и медленное.. походу.. но должно работать . корректно.
ИМХО:
Оцениваем долю составляющего цвета в триаде RGB. В случае, если составляющая превышает определенный порог по отношению к другим основным цветам (к примеру R:150, G:10, B:10), то засчитываем этот пиксел как соответствующий нашим требованиям.
В конце, оцениваем общую долю отобранных пикселей к общему числу пикселей составляющих рисунок. Естественно и тут используем некое пороговое значение.
Наиболее простая как мне кажется реализация тут получается для оценки основных цветов. Т.е. чистого красного, зеленого и синего.
Для оценки содержания скажем желтого или оранжевого, скорей всего придется делать оценочное сравнение с заданным цветом т.е. берем наш цвет в формате RGB и сравниваем с целевым пикселем, с определенным допуском отклонения от оригинала.
Оцениваем долю составляющего цвета в триаде RGB. В случае, если составляющая превышает определенный порог по отношению к другим основным цветам (к примеру R:150, G:10, B:10), то засчитываем этот пиксел как соответствующий нашим требованиям.
В конце, оцениваем общую долю отобранных пикселей к общему числу пикселей составляющих рисунок. Естественно и тут используем некое пороговое значение.
Наиболее простая как мне кажется реализация тут получается для оценки основных цветов. Т.е. чистого красного, зеленого и синего.
Для оценки содержания скажем желтого или оранжевого, скорей всего придется делать оценочное сравнение с заданным цветом т.е. берем наш цвет в формате RGB и сравниваем с целевым пикселем, с определенным допуском отклонения от оригинала.
Ага. Но если мы возьмём изображение японского флага, то сразу же столкнёмся с тем, что сранивать по каналам отдельно - нельзя. Напоминаю, что на флаге Японии преобладающий цвет - белый. Я думаю, было бы действительно лучше отсортировать массив пикселей и найти наиболее часто встречающийся цвет. Сортировать цвета - то же самое, что сортировать числа вида ABCDEFh.
Для чего нужно усреднение? Если говорить о фотографиях в формате JPEG, то в среднем там можно насчитать от 40 до 180 тысяч уникальных цветов (только что проверил по своему архиву). Если фотография состоит всего из 6 миллионов пикселей, то пикселей, окрашенных в доминирующий цвет, окажется не так уж и много - порядка тысяч. В то же время достаточно просто посмотреть на фотографию и уже можно без большого труда сказать, какой цвет действительно преобладает. Поэтому слишком большая точность не нужна. Я думаю, достаточно округлить значение в каждом канале до ближайшего десятка. Заодно это может уменьшит влияние шума на точность определения цвета. на сложность самой сортировки это не повлияет, однако поиск доминирующего цвета в отсортированном массиве пройдёт быстрее.
Для чего нужно усреднение? Если говорить о фотографиях в формате JPEG, то в среднем там можно насчитать от 40 до 180 тысяч уникальных цветов (только что проверил по своему архиву). Если фотография состоит всего из 6 миллионов пикселей, то пикселей, окрашенных в доминирующий цвет, окажется не так уж и много - порядка тысяч. В то же время достаточно просто посмотреть на фотографию и уже можно без большого труда сказать, какой цвет действительно преобладает. Поэтому слишком большая точность не нужна. Я думаю, достаточно округлить значение в каждом канале до ближайшего десятка. Заодно это может уменьшит влияние шума на точность определения цвета. на сложность самой сортировки это не повлияет, однако поиск доминирующего цвета в отсортированном массиве пройдёт быстрее.
Собственно, идея усреднять цвет не влияет на способ поиска доминирующего цвета. Я её предложил потому, что доминирует не какой-то точный цвет, а приблизительный.
[QUOTE=Sanila_san]Я думаю, было бы действительно лучше отсортировать массив пикселей и найти наиболее часто встречающийся цвет. Сортировать цвета - то же самое, что сортировать числа вида ABCDEFh.[/QUOTE]Мне кажется, что по модели RGB сравнивать цвета "больше-меньше" некорректно - сортировки не пройдут (AB CD EF и AC CD EF ведь сходие цвета, но окажутся в противоположных концах результирующего массива). А вот идея выравнивать по сетке мне нравится. Можно использовать реальную сетку для подсчёта количества цветов, попавших в каждый её узел. Для погрешности +-5 получим (255/5)^3 = 51^3 = 132 651 достаточных для расчёта узлов (не зависит от размера картинки), что при sizeof(int) == 4 составит 530 604 байт памяти - не так много. И даже не стоит заморачиваться с деревьями и отложенным созданием узлов.
Но мне кажется, что задачу можно решить элегантней. А что там матстатистика говорит о способах отыскания моды? Специальные учёные по-любому изобрели качественный метод. И, кстати, как там работает кодек BMP при конверсии растровых рисунков в палитровые?
Но мне кажется, что задачу можно решить элегантней. А что там матстатистика говорит о способах отыскания моды? Специальные учёные по-любому изобрели качественный метод. И, кстати, как там работает кодек BMP при конверсии растровых рисунков в палитровые?
Дык сказал же вам ApokALEXIS что для нахождения точного решения сетка не подойдет. И вообще при хорошо подобраном тесте сетка может дать результат очень отличающийся от точного.
Конечно для приблизительного можно использовать.
Меня вот что смущает. Что такое RGB±10 ??
ето (R±10 and G±10 and B±10) или (abs(R-r) + abs(G-g) + abs(B-b)) <= 10 ??
Конечно для приблизительного можно использовать.
Меня вот что смущает. Что такое RGB±10 ??
ето (R±10 and G±10 and B±10) или (abs(R-r) + abs(G-g) + abs(B-b)) <= 10 ??
По поводу "для точного не прокатит" - элементарно: узлы с максимальным количеством цветов бьём на сетку { точность ^ 3 } и повторяем.
Теоретически улучшенный метод: делаем сетку {4 ^ 3} и распределяем по ней возможные цвета. Если цвет совпадает с цветом, соответствующим узлу сетки - добавляем цвет в этот узел. Если плавает "где-то между" соседними - добавляем ещё и в соседние. Для каждого узла с количеством цветов, соответствующим максимальному, повторяем разбиение { 4 ^ 3 } (остальные выбрасываем) и так до достижения нужной точности. Мэджик 4 может быть другим, главное чтоб было больше двух. Оно позволяет добиться оптимального баланса зависимости объёма выделяемой памяти от размера картинки (чем больше изображение, тем больше это число). Последний шаг - вычисление наиболее вероятного точного значения среди найденных приблизительных аналогично высказыванию в первом абзаце.
Можно скомбинироавть с первым, двухшаговым методом: создавать сетку {((256 + точность - 1) / точность) ^ 3}, в узлах по-прежнему хранить количества, а не сами цвета, но ввести фишку с соседними узлами. Вотрой шаг (вычисление точного значения) так же, как и в первом методе, будет использовать весь исходный массив. Что и когда лучше - надо выводить.
Теоретически улучшенный метод: делаем сетку {4 ^ 3} и распределяем по ней возможные цвета. Если цвет совпадает с цветом, соответствующим узлу сетки - добавляем цвет в этот узел. Если плавает "где-то между" соседними - добавляем ещё и в соседние. Для каждого узла с количеством цветов, соответствующим максимальному, повторяем разбиение { 4 ^ 3 } (остальные выбрасываем) и так до достижения нужной точности. Мэджик 4 может быть другим, главное чтоб было больше двух. Оно позволяет добиться оптимального баланса зависимости объёма выделяемой памяти от размера картинки (чем больше изображение, тем больше это число). Последний шаг - вычисление наиболее вероятного точного значения среди найденных приблизительных аналогично высказыванию в первом абзаце.
Можно скомбинироавть с первым, двухшаговым методом: создавать сетку {((256 + точность - 1) / точность) ^ 3}, в узлах по-прежнему хранить количества, а не сами цвета, но ввести фишку с соседними узлами. Вотрой шаг (вычисление точного значения) так же, как и в первом методе, будет использовать весь исходный массив. Что и когда лучше - надо выводить.
Вообще-то для начал неплохо бы определиться, что такое преобладающий цвет и вообще, с какой стороны мы его будем определять: как цвет, занимающий не менее заданного процента от площади изображения или как цвет, имеющий отклонение не выше заданного от "центрального".
В частности, каков будет преобладающий цвет на картинке из 30% красного, 30% оранжевого и 40% зелеого? Красно-оранжевый или зеленый?
Если нам задана (или вычислена) некоторая погрешность, мы можем разбить цветовой куб на зоны, размеры которых примерно соответствуют величине погрешности (например на 10 частей при 10% и 20 частей при 5%) по каждой из цветовых координат.
При 10% получаем примерно 1000 зон (цвет трехмерен).
Далее оцениваем, по сколько в среднем пикселей попадет в одну зону. Например, для рисунка 320х240 - примерно 77 штук. Если это число оказалось меньше нескольких единиц (например 4), вряд ли задача в такой постановке разрешима.
Далее мы выделяем зоны скопления цветов. Обозначив их границы примерно, можно разделить окрестности раниц на более подробные подзоны - для более точного опрелеления. Находим самую представительную зону скопления и принимаем решение о том, как будем вычислять средний по зоне цвет - как максимально удаленный от границ зоны либо как средневзвешенное значение по пикселям, входящим в зону.
В частности, каков будет преобладающий цвет на картинке из 30% красного, 30% оранжевого и 40% зелеого? Красно-оранжевый или зеленый?
Если нам задана (или вычислена) некоторая погрешность, мы можем разбить цветовой куб на зоны, размеры которых примерно соответствуют величине погрешности (например на 10 частей при 10% и 20 частей при 5%) по каждой из цветовых координат.
При 10% получаем примерно 1000 зон (цвет трехмерен).
Далее оцениваем, по сколько в среднем пикселей попадет в одну зону. Например, для рисунка 320х240 - примерно 77 штук. Если это число оказалось меньше нескольких единиц (например 4), вряд ли задача в такой постановке разрешима.
Далее мы выделяем зоны скопления цветов. Обозначив их границы примерно, можно разделить окрестности раниц на более подробные подзоны - для более точного опрелеления. Находим самую представительную зону скопления и принимаем решение о том, как будем вычислять средний по зоне цвет - как максимально удаленный от границ зоны либо как средневзвешенное значение по пикселям, входящим в зону.
Я тут провёл эксперимент в фотошопе, выяснил интересную штуку. Если тупо уменьшить размер картинки до размера 1х1, то она получается примерно того цвета, который преобладает. Метод не претендует на математическую точность, зато заметно совпадает с визуальным восприятием.
Sanila_san,
Для полноты следует ОПРЕДЕЛИТЬ преобладающий цвет как среднее арифметическое значение цветов пикселей картинки.
Для полноты следует ОПРЕДЕЛИТЬ преобладающий цвет как среднее арифметическое значение цветов пикселей картинки.
Sanila_san
Если тупо уменьшить размер картинки до размера 1х1, то она получается примерно того цвета, который преобладает.
опять на примере японского флага - он станет розовый, хотя преобладает белый, а Український прапор буде зелений, хоче там його і близько не лежало
Если тупо уменьшить размер картинки до размера 1х1, то она получается примерно того цвета, который преобладает.
опять на примере японского флага - он станет розовый, хотя преобладает белый, а Український прапор буде зелений, хоче там його і близько не лежало
На украинском флаге и преобладающего цвета нет, как я помню. :) Опять же, что такое преобладающий цвет?
Цитата: Sanila_san
Опять же, что такое преобладающий цвет?
в данном случае
Цитата: infolex
цвет, который преобладает на изображении, то есть которого больше всего. Естественно с разбросом RGB±10.[/COLOR].
тоесть тот которым окрашено больше пикселей
Цитата: Sanila_san
На украинском флаге и преобладающего цвета нет, как я помню. :)
ну флаг конечно это крайность. думаю на практику надо просто выдать какого цвета больше - если одинаково то либо вывести тот который по if'ам раньше/пожже, либо просто табличкой "пятерку лучших"
Цитата: Rebbit
Меня вот что смущает. Что такое RGB±10 ??
ето (R±10 and G±10 and B±10) или (abs(R-r) + abs(G-g) + abs(B-b)) <= 10 ??
ето (R±10 and G±10 and B±10) или (abs(R-r) + abs(G-g) + abs(B-b)) <= 10 ??
Поскольку я так и не понял что такое RGB±10 припускаю что ето (R±10 and G±10 and B±10). Тоесть есть у нас куб RGB в нем есть точка соответствующая некому цвету, а допустимые отклонения лежат в кубе со стороной 21. Также припускаю что розмер куба RGB 256*256*256.
Вот бежим по картинке и щитаем в куб сколько у нас какого цвета. Пощитали. Дальше задача найти такой подкуб со стороной 21 сума елементов которого наибольшая. Извените за розсусоливание, я для ясности вещей.
Как найти максимальний подкуб.
первый шаг. Формируем куб 256*256*(256-21). В каждом его елементе сума елементов первоначального куба от x, y, z до x, y, z + 21. Делается такое за один проход по изначальному кубу.
Дальше из нового куба формируем куб 256*(256-21)*(256-21) где сума щитается от x, y, z до x, y + 21, z из предыдущего куба.Здесь в каждом елементе будет сума цветов уже не в столбце а в площадке 21*21. Дальше похожим образом получаем куб (256-21)*(256-21)*(256-21) где в каждом елементе сума цвеов которые попадают в куб 21*21*21 начинающийся в x, y, z.
В последнем кубе нужно найти максимум.
Тут также есть прикол. Припустим вся картинка окрашена в один цвет. Тогда у нас будет 21*21*21 кубов с максимальной сумой. Но ета проблема легко решается.
Итого сложность O( 256*256*256 )
[QUOTE=Rebbit]Итого сложность O( 256*256*256 )[/QUOTE]Здесь получается, что число 256 ^ 3, скорее всего, во много раз превышает число ширина * высота для картинки (256 ^ 3 == 16 777 216, 1 280 * 1 024 == 1 310 720). Лучше бы, наверное, всё же изначально работать с кубом, имеющим длину ребра (256 / точность) ^ 3 (или [(256 / (2 * точность)] ^ 3 - не важно), а затем уже уточнять результирующие подкубы - сэкономим очень много ресурсов.
Кстати к вопросу о цветах, кубах и количестве пикселей: в моём архиве фотографии размером 3008х2000, что-то около 6 Мп, так вот там в лучшем случае насчитывается 180 000 уникальных цветов. Притом множеств схожих цветов гораздо меньше, может, раз в десять. Поэтому для экономии я бы предложил сначала посчитать количество уникальных цветов, потом считать количество пикселей каждого цвета (если уникальных цветов немного), либо округлить до ближайшего меньшего десятка значение в каждом из каналов и дальше считать пиксели. А куб формировать из фактически имеющихся цветов (то есть не размерностью 256^3, а например 200х180х71)
Цитата: Der Meister
а затем уже уточнять результирующие подкубы - сэкономим очень много ресурсов.
Спорный вопрос. Смутно представляю себе как можно легко уточнять результат после того как цвета искаверкаем запихая их в меньшый куб.
Цитата: Sanila_san
Поэтому для экономии я бы предложил сначала посчитать количество уникальных цветов, потом считать количество пикселей каждого цвета (если уникальных цветов немного), либо округлить до ближайшего меньшего десятка значение в каждом из каналов и дальше считать пиксели. А куб формировать из фактически имеющихся цветов (то есть не размерностью 256^3, а например 200х180х71)
Врезультате получаем гиморой с контролем пропущеных значений по каждой оси (а ето нам нужно для контроля отклонения цвета), который кажысь схавает секономленое время и усложнит алгоритм.
Я предложыл общее решение. Конечно с учетом спецыфики фходных данных его можно усовершенствовать. Вопрос в том стоит ли :)
[QUOTE=Rebbit]Смутно представляю себе как можно легко уточнять результат после того как цвета искаверкаем запихая их в меньшый куб.[/QUOTE]Не-не-не, мы не каверкаем цвета. Просто мы цвет ищем не сразу, а сначала отсеиваем неподходящие.
[QUOTE=Rebbit]Врезультате получаем гиморой с контролем пропущеных значений по каждой оси (а ето нам нужно для контроля отклонения цвета), который кажысь схавает секономленое время и усложнит алгоритм.[/QUOTE]Почему бы вдруг? Зато мы выигрываем в размере куба и в размере диапазона проверок. Контроль отклонения цвета нам всё равно надо делать по каждому каналу, поэтому тут я не вижу проблемы. Просто так мы сразу определяем диапазон возможных значений и работаем только с ним. Другой вопрос, что подсчёт количества цветов тоже сколько-то ресурсоёмкая операция. Но я так понял, что мы всё равно её будем проделывать, так может быть лучше в результате получить неправильный куб и иметь сложность O(x*y*z), где x может быть количеством усреднённых значений. Как бы даунсемплинг куба: не 182х110х79, а 18х11х7. Я округлил в меньшую сторону для сохранения цвета. Для сохранения визуальной точности следовало бы округлить по правилам округления.
ИМХО, в идеале следовало бы вообще округлять до наиболее часто встречающегося значения, тогда доминирующий цвет нашёлся бы наиболее точно.
ИМХО, в идеале следовало бы вообще округлять до наиболее часто встречающегося значения, тогда доминирующий цвет нашёлся бы наиболее точно.