Алгоритм подсчета количества уникальных цветов на изображении

Question

Ищите тот, который достаточно быстр и все же изящен с памятью. Изображение является System.Drawing.Bitmap 24bpp.

Answer 1

Если вам нужно точное число, то вам придется перебрать все пиксели. Вероятно, лучше всего сохранить цвет и счет в хэше из-за редкости цветов.

Использование Color.ToArgb () в хэше вместо цветового объекта также, вероятно, будет хорошей идеей.

Кроме того, если скорость имеет большое значение, вы не хотите использовать такую ​​функцию, как GetPixel (x, y) - вместо этого попробуйте обрабатывать порции за раз (строка за раз). Если можете, получите указатель на начало памяти изображений и сделайте это небезопасным.

Answer 2

Никогда не реализовывал что-то подобное раньше, но, как я вижу, примитивная реализация:

Для 24-битного изображения максимальное количество цветов, которое может иметь изображение, составляет минимум (2 ^ 24, количество пикселей изображения).

Вам нужно только записать, был ли подсчитан определенный цвет, а не сколько раз он был подсчитан. Это означает, что вам нужно 1 бит, чтобы записать, считается ли каждый цвет. Это 2 МБ памяти. Итерируйте по пикселям, установите соответствующий бит на вашей карте набора цветов 2 МБ. В конце выполните итерацию по карте набора цветов, считая установленные биты (если вам повезет, у вас будет инструкция POPCNT, чтобы помочь в этом).

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

Answer 3

Большинство людей здесь предложили решения, которые, вероятно, будут быстрыми (на самом деле то, что использует только 2 МБ, вероятно, приемлемо в отношении использования памяти и очень быстрое; решение с хешем может быть даже быстрее, но оно определенно будет использовать больше, чем 2 МБ памяти). Программирование - это всегда компромисс между использованием памяти и временем процессора. Обычно вы можете получать результаты быстрее, если вы хотите «тратить» больше памяти или же вы можете получать результаты медленнее, «тратя» больше времени на вычисления, однако это обычно экономит вам много памяти.

Вот одно решение, которое никто еще не предлагал. Вероятно, это тот, который стоит меньше всего памяти (вы можете оптимизировать его, так что он вряд ли будет использовать больше памяти, чем необходимо для сохранения изображения в памяти, однако изображение будет изменено, хотя вам, возможно, придется сначала скопировать его). Я сомневаюсь, что это может побить решение по хешу или битовой маске по скорости, просто интересно, если память - ваша самая большая проблема.

1. Сортировка пикселей на изображении по цвету. Вы можете легко преобразовать каждый пиксель в 32-разрядное число, и 32-разрядные числа можно сравнить друг с другом, причем одно число меньше другого, больше или равно. Если вы используете быструю сортировку, для сортировки не требуется дополнительного места для хранения, кроме дополнительного стека. Если вы используете Shellsort, дополнительная память вообще не требуется (хотя Shellsort будет работать намного медленнее, чем Quicksort).

   int num = (RED << 16) + (GREEN << 8) + BLUE; </p>

2. После того, как вы отсортировали пиксели подобным образом (что означает, что вы переставили их в пределах изображения), все пиксели одинакового цвета всегда будут рядом друг с другом. Таким образом, вы можете только один раз перебрать изображение и посмотреть, как часто меняется цвет. Например. Вы сохраняете текущий цвет пикселя в (0, 0) и запускаете счетчик со значением 1. Следующий шаг - переход к (0, 1). Если он того же цвета, что и раньше, ничего не делать, переходите к следующему пикселю (0, 2). Однако, если это не то же самое, увеличьте счетчик на единицу и запомните цвет этого пикселя для следующей итерации.

3. Как только вы посмотрите на последний пиксель (и, возможно, снова увеличите счетчик, если он не совпадает со вторым последним пикселем), счетчик содержит количество уникальных цветов.

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

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

Answer 4

var cnt = new HashSet<System.Drawing.Color>();

foreach (Color pixel in image)
    cnt.Add(pixel);

Console.WriteLine("The image has {0} distinct colours.", cnt.Count);

/ EDIT: как сказал Лу, использование .GetArgb() вместо самого значения Color может быть немного быстрее из-за способа, которым Color реализует GetHashCode.

Answer 5

Большинство других реализаций здесь будут медленными. Чтобы это было быстро, вам нужен прямой доступ к линии сканирования и некоторая разреженная матрица для хранения цветовых данных.

Сначала я опишу случай 32bpp, это намного проще:

• HashSet: разреженная матрица цветов
• ImageData: использовать BitmapData объект напрямую доступ к основной памяти
• PixelAccess: используйте int * для ссылки память как целые, которые вы можете перебрать

Для каждой итерации просто создайте hashset.add этого целого числа. В конце просто посмотрите, сколько ключей в HashSet, и это общее количество цветов. Важно отметить, что изменение размера HashSet действительно болезненно (O (n), где n - количество элементов в наборе), и поэтому вы можете захотеть создать разумный размер HashSet для начала, возможно, что-то вроде imageHeight * imageWidth / 4 было бы хорошо.

В случае 24bpp PixelAccess должен быть байтом *, и вам нужно перебрать более 3 байтов для каждого цвета, чтобы построить int. Для каждого байта в наборе 3 первые биты сдвигаются влево на 8 (один байт) и добавляют его к целому числу. Теперь у вас есть цвет 24bpp, представленный 32-битным целым, остальное все то же самое.

Answer 6

Вы точно не определили уникальные цвета. Если вы на самом деле имеете в виду действительно уникальные кодовые значения (в отличие от визуально одинаковых), то единственное точное решение - фактически подсчитать их, используя один из методов, описанных в других ответах.

Если вы ищете визуально похожих цветов, это быстро переходит к проблеме отображения палитры, когда вы ищете 256 лучших уникальных цветов, которые можно использовать для наиболее точного представления оригинального полного динамического цвета. Диапазон изображения. Для большинства изображений просто удивительно, насколько хорошо изображение, уменьшенное с 24 бит и до 16 миллионов различных цветов, можно сопоставить с изображением, имеющим только 256 уникальных цветов, когда эти 256 цветов выбраны правильно. Оптимальный выбор этих правильных 256 цветов (для этого примера), как доказано, является NP-полным, но есть практические решения, которые могут быть очень близки. Поиск работ парня по имени Шиджи Ван и материалов, созданных на его работе.

Если вы ищете приближение к числу цветов значений кода в изображении, я бы сжал изображение, используя схему сжатия без потерь. Коэффициент сжатия будет напрямую зависеть от количества уникальных кодовых значений в изображении. Вам даже не нужно сохранять сжатые выходные данные, просто накапливайте количество байтов по пути и отбрасывайте фактические выходные данные. Используя набор образцов изображений в качестве эталона, вы можете построить таблицу соответствия между степенью сжатия и количеством различных кодовых значений в изображении. Опять же, этот последний метод, хотя и довольно быстрый, определенно будет приблизительным, но он должен достаточно хорошо коррелировать.

Answer 7

Максимальное количество уникальных цветов в изображении равно количеству пикселей, так что это предсказуемо с самого начала процесса. Тогда использование метода HashSet, предложенного Конрадом, представляется разумным решением, поскольку размер хэша не должен превышать количество пикселей, в то время как использование подхода растрового изображения, предложенного JeeBee, потребовало бы 512 МБ для 32-разрядного изображение (если есть альфа-канал, и это определено, чтобы способствовать уникальности цвета)

Производительность подхода HashSet, тем не менее, скорее всего будет хуже, чем у подхода «бит на цвет» - вы можете попробовать оба варианта и выполнить некоторые тесты, используя множество разных изображений

Answer 8

Это зависит от того, какие типы изображений вы хотите проанализировать. Для 24-битных изображений вам потребуется до 2 МБ памяти (поскольку в худшем случае вам придется обрабатывать каждый цвет). Для этого лучше всего использовать растровое изображение (у вас есть растровое изображение размером 2 МБ, где каждый бит соответствует цвету). Это было бы хорошим решением для изображений с большим количеством цветов, которые могут быть реализованы в O (#pixels). Для 16-битных изображений вам понадобится только 8 кБ для этого растрового изображения с использованием этой техники.

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

Answer 9

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

Answer 10

Современная популярная реализация цветового квантования использует структуру данных octree . Обратите внимание на страницы википедии, содержание довольно хорошее. Преимущество octree заключается в том, что он настолько ограничен, насколько вы хотите, поэтому вы можете сэмплировать все изображение и выбирать свою палитру без особой дополнительной памяти. Как только вы поймете эту концепцию, перейдите по ссылке на 1996 исходный код статьи доктора Добба в журнале .

Поскольку это вопрос C #, см. Статью MSDN за май 2003 года Оптимизация квантования цвета для изображений ASP.NET , в которую входит некоторый исходный код.