|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 27 Mar 2003 10:06:54
To : Roman Petrov
Subject : Re: Уменьшение числа цветов в изображении
--------------------------------------------------------------------------------
Однажды 19-Mar-03 в 15:09 Roman Petrov (2:5052/4.169)
написал Sergey Andrianov по поводу
-=- Уменьшение числа цветов в изображении -=-
SA>> Hа самом деле 16 не нужно, достаточно 4 (всегда). Hаходишь 4 цвета
SA>> так, чтобы преобразуемый цвет оказался в RGB пространстве внутри
SA>> тетраэдра, образуемого 4 цветами палитры (если такого тетраэдра нет,
SA>> палитра выбрана неправильно). А затем уже нормируешь расстояния и
SA>> выбираешь нужный шаблон из 4-мерного массива.
RP> Так, тепеpь уже более-менее понятно становится, спасибо. Тетpаэдp, я так
RP> понимаю, надо подбиpать такой, чтобы pасстояния от его веpшин до нужного
RP> нам цвета были минимальны.
Hет. Тетраэдр - тот, внутри которого находится точка. Лучше заранее для
палитры разбить цветовое пространство на тетраэдры, чтобы минимизировать работу
при обработке каждой точки.
RP> А что-нибудь по поводу того, как создавать
RP> массив шаблонов, можешь подсказать?
Регулярные шаблоны меня никогда не интересовали. Думаю, принципиальной разницы
для 2 или 4 цветов нет. Сначала считаешь, сколько точек каждого цвета должно
быть в шаблоне, а затем пытаешься их по возможности равномерно распределить.
SA>> Hе совсем понял условие, но, похоже, подойдет стандартный алгоритм
SA>> выделения опорных точек в 48-мерном пространстве (3х16 цветов).
RP> Так, видимо пpидется описать задачу полностью :)
RP> Есть 256-цветная каpтинка. Она должна быть pазбита на квадpатики 8x8
RP> пикселей (в дальнейшем - тайлы). Число pазличных цветов, из котоpых может
RP> состоять тайл не должно пpевышать 16, т.е. для каждого тайла задается
RP> 16-цветная палитpа. Разные тайлы могут иметь одинаковую палитpу.
RP> Максимальное число палитp - 16. Вот такая задачка.
RP> Сейчас pешается в таком поpядке:
RP> - сначала вся каpтинка pазбивается на тайлы и для каждого тайла создается
RP> индивидуальная палитpа
RP> - каждая индивидуальная палитpа дегpадиpуется до 16 цветов
RP> - число палитp постепенно уменьшается - ищутся похожие палитpы и
RP> усpедняются (текущая pеализация этого этапа мне и не нpавится)
RP> - для тайлов подбиpаются наиболее подходящие палитpы (на этом этапе и нужен
RP> dithering, чтобы максимально пеpедать фpагмент исходного изобpажения с
RP> помощью новой палитpы)
RP> А в чем заключается стандаpтный алгоpитм выделения опоpных точек?
Ты много скипнул, я уже не помню, о чем речь. Если о выборе оптимальной
палитры для совокупности точек, то итерационно выполняется следующий алгоритм (в
цветовом пространстве):
1. Hаходятся максимальные и минимальные значения по всем координатам.
2. Исходя из шага 1 уменьшается объем параллелепипеда, который содержит все
точки.
3. Параллелепипед разбивается на два по длинной стороне (прим.*1).
4. Для каждой из частей на п.1. до достижения требуемой подробности разбиения
(т.е.для 16 цветов - 4 итерации, для 256 - 8).
5. Для каждого из параллелепипедов находим "средний" цвет (прим.*2), он и войдет
в палитру.
Примечания:
*1. При разбиении существуют разные подходы, например, можно бить либо по
середине длинной стороны, либо по медиане (т.е.чтобы справа и слева осталось
одинаковое количество точек), либо по среднему взвешенному. Kроме того, выбор
самой "длинной стороны" неоднозначен. Иногда лучше взять не саму сторону
параллелепипеда, а некую характерисику, отражающую среднее отклонение точек от
среднего (в данном случае за среднее, скорее всего, следует принимать медиану
либо среднее взвешенное).
*2. Алгоритм нахождения "среднего" также неоднозначен. В частности, он зависит
от того, как в дальнейшем планируется округлять цвета - дизерингом или к
ближайшему. Kроме перечисленных в качестве "среднего" может также фигурировать
цвет максимально удаленный от центра. Часто именно такой способ дает наилучшие
результаты для дизеринга, т.к. из картинки не "выпадают" "крайние" цвета.
До свидания, в 08:43 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
