Compression of an image

Question

I have been calculating the uncompressed and compressed file sizes of an image. This for me has always resulted in the compressed image being smaller than the uncompressed image which I would expect. If an image contains a large number of different colours, then storing the palette takes up a significant amount of space, and more bits are also needed to store each code. However my question is, would it be possible the compression method could potentially result in a larger file than the uncompressed RGB image. What would the size (in pixels) of the smallest square RGB image, containing a total of k different colours, for which this compression method is still useful? So we want to find, for a given value of k, find the smallest integer number n for which an image of size n×n takes up less storage space after compression than the original RGB image.

Answer 1

Let's begin by making a small simplification -- the size of the encoded output depends on the number of pixels (the actual proportion of width vs. height doesn't really matter). Hence, let's generalize the problem to number of pixels N, from which we can always calculate n by taking a square root.

To further simplify the problem, we will also ignore the overhead of any image headers/metadata, such as width, height, size of the palette, etc. In practice, this would generally be some relatively small constant.

---

Problem Statement

Given that we have

• N representing the number of pixels in an image
• k representing the number of distinct colours in an image
• 24 bits per pixel RGB encoding
• L_RGB representing the length of a RGB image
• L_P representing the length of a palette image

our goal is to solve the following inequality

in terms of N.

---

Size of RGB Image

RGB image is just an array of N pixels, each pixel taking up a fixed number of bits given by the RGB encoding. Hence,

---

Size of Palette Image

Palette image consists of two parts: a palette, and the pixels.

A palette is an array of k colours, each colour taking up a fixed number of bits given by the RGB encoding. Therefore,

In this case, each pixel holds an index to a palette entry, rather than an actual RGB colour. The number of bits required to represent k values is

However, unless we can encode fractional bits (which I consider outside the scope of this question), we need to round this up. Therefore, the number of bits required to encode a palette index is

Since there are N such palette indices, the size of the pixel data is

and the total size of the palette image is

---

Solving the Inequality

And finally

---

In Python, we could express this in the following way:

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.)

---