Медианный разрез — это алгоритм сортировки данных произвольного числа измерений в серии наборов путем рекурсивного разрезания каждого набора данных в медианной точке вдоль самого длинного измерения. Медианный разрез обычно используется для квантования цвета . Например, чтобы уменьшить 64k-цветное изображение до 256 цветов, медианный разрез используется для поиска 256 цветов, которые хорошо соответствуют исходным данным. [1]
Предположим, у нас есть изображение с произвольным числом пикселей , и мы хотим сгенерировать палитру из 16 цветов. Поместите все пиксели изображения (то есть их значения RGB ) в ведро . Выясните, какой цветовой канал (красный, зеленый или синий) среди пикселей в ведро имеет наибольший диапазон, затем отсортируйте пиксели в соответствии со значениями этого канала. Например, если синий канал имеет наибольший диапазон, то пиксель со значением RGB (32, 8, 16) меньше пикселя со значением RGB (1, 2, 24) , потому что 16 < 24. После сортировки ведра переместите верхнюю половину пикселей в новое ведро. (Именно этот шаг дает название алгоритму медианного разреза; ведра делятся на два по медиане списка пикселей.) Этот процесс можно повторить для дальнейшего разделения набора пикселей: выберите ведро для разделения (например, ведро с наибольшим диапазоном в любом цветовом канале) и разделите его на два. После создания необходимого количества сегментов усредните пиксели в каждом сегменте, чтобы получить окончательную цветовую палитру.