Assignment 2: Awesome Image Format

In this assignment you will implement a program to manipulate AIF (Amazing Image Format) files.

Getting started

Create a new directory for this assignment, change to this directory, and fetch the provided code by running

mkdir -m 700 aif
cd aif
1521 fetch aif

You should write your code inside aif-tools.c.

You can fetch the example files used by autotest by running

1521 aif-examples

Background

How computers display images

The same image at 200x200, 50x50 and 10x10 pixels.

Images, like a computer screen, is arranged into a grid of ‘pixels’. Each pixel is assigned a color value and by combining these pixels you can form an image. The more pixels the more defined the image may look.

When we refer to the width or the height of an image, we are generally referring to the number of pixels in each row and the number of pixels in each column. For example 640x500 means 640 columns and 500 rows of pixels.

Color Depth

As computers have developed they have been able to display images of increasing color depth. Color depth refers to the amount of bits used to represent color where more bits = a bigger range of color values.

The following 500x500 image at 8-bit rgb, 16 color (4-bit palette) and 4 color (2-bit palette) depths

Notice how at lower (250x250) resolutions the difference is more pronounced.

This is due to dithering where at a larger distance colors can merge together and combine!

Color Formats

In this assignment you only have to worry about two ways of storing color.

8-bit RGB

One of the most common color formats where each pixel is made up of 8-bits of red, green and blue and can be stored as a 24-bit value. Each pixel is 3 bytes. Each pixel will look like RR GG BB in memory.

By mixing red, green and blue we can make 2^24 different colors! For example FF FF FF is white, 00 00 00 is black, FF 00 00 would be a bright red and FF FF 00 would be a bright yellow!

Often web and graphic designers will work with colors in a hex format such as #ff00ff and these correspond to 8-bit RGB.

8-bit Grayscale

Each pixel is an 8-bit value where 0 is black, 255 is white and inbetween are shades of gray. Each pixel is 1 byte.

Storing Pixels

When working with images, pixels are generally stored in rows of color values. Each row will be the at least the width of the image.

AIF (Amazing Image Format) Format

Header

Magic

Magic values are used to identify the format of a file and verify that the header has not been corrupted. We use file extensions too (e.g. png and jpg ), but magic fields allow a file format to be identified even if this extension is missing or changed.

Checksum

The AIF format involves a simple checksum to make sure the image data is valid. A checksum is a value calculated from a larger piece of data (in our case an image) which can be used to check for corrupted data.

We use a simple Fletcher’s checksum to verify our image. Its calculation works as follows:

1. We have two sums, sum1 and sum2 start at 0
2. Assume the checksum value in the image header is 0
3. Read in the first byte starting from the header
4. Add the byte value to sum1 and take sum1 % 256
5. Add the new value for sum1 to sum2 and take sum2 % 256
6. Read in next byte and repeat until EOF

Finally, we place both sum1 and sum2 in a 16-bit integer by left shifting sum2 by 8 and adding the two values together.

Pixel Format

AIF_FMT_RGB8 - Each pixel is a 24-bit RGB value

AIF_FMT_GRAY8 - Each pixel is an 8-bit shade of gray

Compression

AIF_COMPRESSION_NONE - Uncompressed

AIF_COMPRESSION_RLE - RLE (Run length encoding compression, see below)

Width, Height

width refers to the number of pixels (columns) in each row

height refers to the number of rows

Pixel Data Offset

How many bytes from the start of the file the pixel data begins.

Viewing AIF Images

Run 1521 aif-convert to convert an AIF image to a PNG and have a look at what your program did!

$ 1521 aif-convert aif-examples/cat.aif 

You can then open this png in vscode!

Stage 0

Get Information About Given Image File

<aif-examples/cat.aif>:
File-size: 120020 bytes
Checksum: 7c 9c
Pixel format: 8-bit RGB
Compression: none
Width: 200 px
Height: 200 px

Stage 1

Verify the width and height

$ aif-tools info aif-examples/invalid-width.aif
<aif-examples/invalid-width.aif>
File-size: 20 bytes
Checksum: d9 e7
Pixel format: 8-bit RGB
Compression: none
Width: 0 px INVALID
Height: 2 px

Verify the pixel format

$ aif-tools info aif-examples/invalid-format.aif
<aif-examples/invalid-format.aif>:
File-size: 24 bytes
Checksum: 5d 2d
Pixel format: Invalid
Compression: none
Width: 2 px
Height: 2 px

Verify the image checksum

$ aif-tools info aif-examples/invalid-checksum.aif
<aif-examples/invalid-checksum.aif>:
File-size: 320 bytes
Checksum: 67 67 INVALID, calculated 5d f9
Pixel format: 8-bit RGB
Compression: none
Width: 10 px
Height: 10 px

Stage 2

Accessing Pixel Data

Pixel data is stored in rows meaning you access the pixels across. Carefully consider how you read and write pixel data to make accessing different color formats and compressed/uncompressed images easier!

Adjust image brightness

In this subset take the given image and brighten it by a given percentage.

$ aif-tools brighten cat.aif bright-cat.aif 20

$ aif-tools brighten cat.aif dark-cat.aif -15

For any given ‘RGB’ color it can be useful to find the chroma (how deep the color is) and the luminance (how bright the color is). By finding and manipulating this luminance we can brighten or darken the image!

Luckily, this is done for you, in brighten_rgb , however you should read below to see how it works! The color value is passed as a 24-bit integer and a new adjusted color value is returned.

uint32_t old_pixel = ...
uint32_t new_pixel = brighten_rgb(old_pixel, amount);
// write the new pixel to the output image...

For gray images we can just do pixel * (100 + amount) / 100 . However, you must make sure if the color value overflows (goes above 255) that it gets capped to 255.

brighten_rgb

To brighten or darken an RGB color, we must split each pixel into its color components (r, g, b). For a gray image we can ignore this step.

We then get the midpoint of the brightest and darkest color component:

// For an rgb image
r = pixel[0];
g = pixel[1];
b = pixel[2];
lightest = max(r, g, b)
darkest = min(r, g, b)
luminance = (brightest + darkest) / 2

// For a gray image
uint8_t pixel;
luminance = pixel;

We then get the ‘chroma’ (intensity of the color) by subtracting the brightest and darkest

chroma = brightest - darkest

We can then use luminance and chroma to find the base ‘lightness’ of the color. This ‘lightness’ is a constant value added to each r, g, b component. We can find it as such:

lightness = luminance - chroma / 2

By manipulating the luminance value we increase or decrease this constant ‘lightness’ and can brighten and darken the color!

Stage 3

Convert between colour formats

Convert the image to grayscale

Converting from RGB to Grayscale

When we want to convert an RGB color value to grayscale, its not at simple as just taking the average of the red green and blue values. The eye perceives green to be brighter than blue and we need to take this into account when converting to gray.

This gives us the following formula to calculate the luma of a given RGB color.

red = pixel[0]
green = pixel[1]
blue = pixel[2]
gray = (red * 299 + green * 587 + blue * 114) / 1000

This will become our new 1-byte pixel value!

Converting from 8-bit grayscale to RGB

In order to convert back, we can just duplicate a given value across red, green and blue.

GG -> GG GG GG

i.e. A value of 128 (0x80) will become 80 80 80 .

red = gray
green = gray
blue = gray
pixel = {red, green, blue}

Stage 4

Run-length encoding decompression

Decompress the provided image file.

aif-tools decompress cat-compressed.aif cat.aif

To compress AIF images we use a simple compression method called run-length encoding. In subset 4 you only need to worry about decompression.

RLE involves simply specifying a number of times to repeat the following sequence of bytes. This looks like the following:

[NNNN] [XX] pixel_value_repeated
[NNNN] [00] [XX] pixel_value00 pixel_value01 ... pixel_valueXX

NNNN - number of bytes in row
XX - number of pixels
pixel_value_repeated - pixel repeated XX times
pixel_value00 ... pixel_valueXX - part of a non-repeating sequence of pixels

For example, with an rgb image we have 3 bytes per pixel. For the following pixel values (as hex numbers):

000000  000000  000000  ff5555  ff5555  fcfcfc  000000  670067

First of all we need to give the number of total bytes in the row. We can leave this as zero now and come back to it once we are done.

You can see that 00 00 00 is repeated 3 times, so this becomes 03 00 00 00 meaning we want to repeat the color 00 00 00 (black) 3 times!

00 00 03 00 00 00

Then we repeat ff 55 55 twice giving 02 ff 55 55.

00 00 03 00 00 00 02 ff 55 55

As you can see the next 3 pixels repeat, so we use zero to indicate no repeating. We have 3 non-repeating pixels giving us 00 03 fc fc fc 00 00 00 67 00 67 .

00 00 03 00 00 00 02 ff 55 55 00  03 fc fc fc  00 00 00  67 00 67

We have now written 0x13 (19) bytes so we write it (as a little endian value) giving us our final row:

13 00 03 00 00 00 02 ff 55 55 00 03 fc fc fc 00 00 00 67 00 67

As you might notice this works great for simple images, such as graphics and screenshots but often actually increases the file-size of most normal photos! More advanced formats have varying ways of dealing with this, such as JPEG which can reduce image detail in order to greatly improve compression.

Stage 5

RLE Compression

Implement RLE compression for AIF images.

$ aif-tools compress cat.aif cat-compressed.aif

Assumptions

• A single pixel value should be encoded with 00 01 <pixel> , i.e. a single 00 00 FF becomes 00 01 00 00 FF
• If a sequence of pixels exceeds 255, write 255 <pixel> and start a new sequence
• Rows will not exceed 65535 bytes.

Update subsets 2 and 3 to support compression

Update subsets 2 and 3 to support compressed images. If the input is compressed the output should also be compressed.