Метод квантования цветов медианным сечением

1. Первый шаг состоит в отсечении "краёв" куба, которые не содержат пикселов. К примеру, если у всех пикселов значения красной компоненты не меньше, чем 8 и не больше, чем 250, то отбрасываются части куба от R=0 до R=7 и от R=251 до R=255.

2. Второй шаг заключается в разрезании полученного параллелепипеда на два в срединной точке (медиане) самой длинной стороны. Если самая длинная сторона параллельна оси ‘B’, то компьютер выбирает срединное синее значение из всех синих значений представленных в параллелепипеде (к примеру, 50.000-ое вхождение в отсортированном списке из 100.000 синих значений) и разрезает в этой точке. Теперь параллелепипед разделен на два параллелепипеда меньшего размера, содержащих одинаковое количество пикселов.

3. Весь предыдущий процесс - отсечение пустых "краев" и разрезание самой длинной стороны в срединной точке - повторяется для двух меньших параллелепипедов. Теперь исходный куб разделен на четыре параллелепипеда, содержащих приблизительно одинаковое количество пикселов.

4. Медианное сечение повторно применяется для того, чтобы разделить куб на 8, 16, 32, 64, 128и 256 параллелепипедов (можно остановиться в любой момент, в зависимости от того, сколько цветов в палитре нужно получить). Они содержат примерно одно и то же количество пикселов.

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