Давайте начнем с небольшого упрощения - размер закодированного вывода зависит от количества пикселей (фактическое соотношение ширины и высоты на самом деле не имеет значения). Поэтому давайте обобщим задачу на количество пикселей N , из которого мы всегда можем вычислить n , взяв квадратный корень.
N = n \times n \ \text{pixels}">
Чтобы еще больше упростить задачу, мы также будем игнорировать издержки любых заголовков / метаданных изображения, таких как ширина, высота, размер палитры и т. Д. На практике это обычно будет относительно небольшая константа.
Постановка задачи
Учитывая, что у нас есть
- N , представляющее количество пикселей в изображении
- k представляет количество различных цветов в изображении
- 24 бит на пиксель в кодировке RGB
- L RGB представляющий длину изображения RGB
- L P представляющий длину изображения палитры
наша цель - решитьследующее неравенство
L_{\text{RGB}} > L_{\text{P}}">
с точки зрения N .
Размер изображения RGB
RGB-изображение - это просто массив из N пикселей, каждый пиксель занимает фиксированное количество бит, заданное кодированием RGB. Следовательно,
L_{\text{RGB}} = \left( N \times 24 \right) \ \text{bits}">
Размер изображения палитры
Изображение палитры состоит из двух частей: палитры и пикселей.
L_{\text{P}} = L_{\text{palette}} + L_{\text{pixels}}">
Палитра - это массив k цветов, каждый цвет занимает фиксированное количество битов, заданное кодированием RGB. Следовательно,
L_{\text{palette}} = \left( k \times 24 \right) \ \text{bits}">
В этом случае каждый пиксель содержит индекс для записи палитры, а не фактический цвет RGB. Число битов, необходимых для представления значений k , равно
\log_{2}{k} \ \text{bits}">
Однако, если только мы не можем кодировать дробные биты (что я рассматриваю за рамками этого вопроса)нам нужно округлить это. Следовательно, количество битов, необходимых для кодирования индекса палитры, составляет
\left \lceil{\log_{2}{k}}\right \rceil \ \text{bits}">
Поскольку существует N таких индексов палитры, размер данных пикселя равен
L_{\text{pixels}} = \left( N \times \left \lceil{\log_{2}{k}}\right \rceil \right) \ \text{bits}">
, а общий размер изображения палитры составляет
L_{\text{P}} = \left( k \times 24 \right) + \left( N \times \left \lceil{\log_{2}{k}}\right \rceil \right) \ \text{bits}">
Решение неравенства
L_{\text{RGB}} > L_{\text{P}}">
\left( N \times 24 \right) > \left( k \times 24 \right) + \left( N \times \left \lceil{\log_{2}{k}}\right \rceil \right)">
\left( N \times 24 \right) - \left( N \times \left \lceil{\log_{2}{k}}\right \rceil \right) > \left( k \times 24 \right)">
\left( N \times \left( 24 - \left \lceil{\log_{2}{k}}\right \rceil \right) \right) > \left( k \times 24 \right)">
И, наконец,
N > \frac{k \times 24}{24 - \left \lceil{\log_{2}{k}}\right \rceil}">
В Python мы можем выразить это следующим образом:
import math
def limit_size(k):
return (k * 24.) / (24. - math.ceil(math.log(k, 2)))
def size_rgb(N):
return (N * 24.)
def size_pal(N, k):
return (N * math.ceil(math.log(k, 2))) + (k * 24.)
