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

Question

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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 6

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

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

Answer 7

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

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

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

Answer 8

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

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

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

   int num = (RED < < 16) + (ЗЕЛЕНЫЙ < < 8) + BLUE;

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

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

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

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

Answer 9

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

Сначала я опишу случай 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-битным int, остальное все равно.

Answer 10

Современная популярная реализация color quantization использует структуру данных octree. Обратите внимание на страницы википедии, содержание довольно хорошее. Преимущество octree заключается в том, что оно ограничено памятью, так как вы можете пробовать весь образ и выбирать свою палитру без дополнительной памяти.Понимая концепцию, перейдите по ссылке 1996 Dr Dobb's journal article's source code.

Поскольку это вопрос с C#, см. Статью MSDN от мая 2003 года Optimizing Color Quantization for ASP.NET Images, в которую входит некоторый исходный код.