Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Подскажите алгоритм для хитрой квантизации  (Прочитано 8919 раз)
0 Пользователей и 1 Гость смотрят эту тему.
ABel
Гость
« : 28-11-2003 04:15 » 

Вот такая вот возникла проблема:
Имеется полноцветное изображение, из которого вытащена 256-цветовая палитра (алгоритмом Median Cut Хекберта).
Задача заключается в том, чтобы для некоторого небольшого фрагмента исходного изображения (скажем, квадратика 8 на 8 точек) выбрать три наилучших приближения одним, двумя и четырмя цветами из полученной палитры.

С одним цветом - тут понятно. Берём среднее по всем точкам и ищем ближайший цвет в палитре. А вот как лучше поступить с двумя и четырмя цветами?
Подскажите, пожалуйста, может быть уже есть соответствующие алгоритмы или хотя бы статьи, рассматривающие этот вопрос (не квантизацию вообще, а именно вот такую квантизацию с ограничениями).
Записан
Lex
Специалист

ru
Offline Offline

WWW
« Ответ #1 : 28-11-2003 09:46 » 

ABel, не совсем понятно про приближения 2 и 4 цветами.
Т.е. как я понимаю в выбранном тобой фрагменте исходные цвета заменяются на 2 или 4 цвета или фрагмент заливается 2, 4 цветами?
Записан

Megabyte be with you!
grozny
Гость
« Ответ #2 : 28-11-2003 10:45 » 

Решение в общем случае - квантизация по собственному базису в цветовом пр-ве даст тебе ответ для любого количества цветов.

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

В твоём случае корзины (палитра) уже заданы, вполне может быть неоптимальной. Это так, к слову.

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

2. Считаем расстояния между полученными цветами.

3. Выбираем пару цветом с минимальным расстоянием и заменяем их либо на один из цветов из пары (грубо), либо ищем по палитре цвет с минимальным расстоянием от среднего цвета пары.

4. Повторяем процесс пока не останется требуемое кол-во цветов.

ВИдел статью в ACM Transactions on Graphics. Ни автора, ни года/номера ессно не помню, увы.
Записан
ABel
Гость
« Ответ #3 : 28-11-2003 14:44 » 

Lex, имелась в виду замена исходных цветов на 2 (или 4) искомых цвета.

grozny, благодарю за совет.

Оптимальность исходной палитры в моём случае не очень требуется. Всё дело в том, что приходится работать не с одним статическим изображением, а с последовательными видео-кадрами. При этом палитра - общая.
Главное, чтобы приближение фрагментов изображения малым количеством цветов работало как можно быстрее.
Записан
grozny
Гость
« Ответ #4 : 28-11-2003 21:06 » 

вспомнил фамилиё - Сяолин Ву, вот тебе код:

Код:

/**********************************************************************
   C Implementation of Wu's Color Quantizer )v. 2:
   )see Graphics Gems vol. II, pp. 126-133:

Author{ Xiaolin Wu
Dept. of Computer Science
Univ. of Western Ontario
London, Ontario N6A 5B7
wu@csd.uwo.ca

Algorithm{ Greedy orthogonal bipartition of RGB space for variance
  minimization aided by inclusion-exclusion tricks.
  For speed no nearest neighbor search is done. Slightly
  better performance can be expected by more sophisticated
  but more expensive versions.

The author thanks Tom Lane at Tom_Lane@G.GP.CS.CMU.EDU for much of
additional documentation and a cure to a previous bug.

Free to distribute, comments and suggestions are appreciated.
**********************************************************************/


http://www.csd.uwo.ca/~wu/cq.c
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines