ELEN0450 · Multimedia Systems

Lecture 2

Graphics and image data representation

How a picture becomes numbers:

sampling, bit depth, and file formats

www.viulab.be

Recap: where we are in the pipeline

2

Last lecture: one media signal from capture to display, in five stages.

Acquisition (Capture), Representation (Digitization), Compression (Storage),

Distribution (Transmission), Display (Render).

This lecture: the synthesis and representation (digitization) stage, for the image signal.

Representation

Digitization

Acquisition Capture

Compression Storage

Distribution Transmission

Display

Render

Scope of the course

3

What you'll be able to do after today's class

4

Explain image sampling and intensity quantization.

Compute storage from resolution and bit depth

Distinguish 1-bit, gray, 24-bit and indexed color

Build a palette with median-cut and dither an image

Compare raster with vector and the main file formats

Table of content

5

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF

An optical signal is 2D continuous

6

Lights in the physical scene is continuous in 3 dimensions and time.

A camera projects that 3D continuous light on a 2D continuous sensor (more on this is Session 4 and 5)

An optical signal is 2D continuous

7

Digital sensors filter and sample the 2D continuous signal

8

The image sensor filter samples the continuous 2D signal into a discretized 2D signal.

Single elements integrate the signal within it (“counting photons”).

An image is a grid of pixels

9

An image is a function

10

Representations of images

11

Digitization is sampling plus quantization

12

Sampling: read the value at regular instants (discretize TIME).

Quantization: round each sample to a finite level set (discretize AMPLITUDE).

Quantization and sampling are steps that lose information.

Spatial sampling: onto a grid

13

The real scene is continuous; the sensor measures one value per grid cell.

One value per cell is one pixel. A finer grid gives higher spatial resolution.

Intensity quantization

14

Image properties: resolution, aspect ratio, and density

Spatial resolution: how many pixels, width by height, in pixels (e.g., 1920 by 1080).

Aspect ratio: width to height ratio (e.g., 4:3 for early TV, 16:9 for HD).

Pixel density: pixels per inch on a device (also called dpi (dots per inch) for printers).

Color resolution: how many levels per pixel (bit depth).

Spatial and color resolutions cost storage.

Upsampling and downsampling the spatial resolution

16

Theoretically optimal upsampling: first reconstruct the underlying continuous signal through a filter, with potential anti-aliasing, and then resample at a desired, higher rate.

Original signal

Upsampled points

Underlying continuous signal

Upscaling = reducing frequency + upsampling

17

First “stretch” the underlying signal into a wider domain, which reduces the signal frequency

Then we sample that lower frequency signal with more samples.

This makes later reconstruction (e.g., by a display) easier in theory.

Naïve upsampling

18

Nearest neighbor

“Zero-upsampling”

Visualization of upsampling strategies

19

Nearest neighbors

Bilinear

Cubic

Image source: https://en.wikipedia.org/wiki/Bicubic_interpolation

Downscaling = Increasing frequency + downsampling

20

Simply dropping samples/pixels? Why is that bad?

• Dropping pixels is equivalent to sampling the original continuous signal using a lower rate. It would make later reconstruction harder and may lead to aliasing.
• First “squeeze” the underlying signal into a narrower domain, which increases the signal frequency.
• Then we sample that higher frequency signal with fewer samples.

Displaying the image at the downsampled resolution is very hard: it is equivalent to reconstructing a higher frequency signal from fewer samples.

A warning: sampling artifacts

21

Sample a pattern finer than the grid and you get moire (aliasing).

Same cause as audio aliasing: undersampling.

Cameras add an optical low-pass filter to fight it.

Note

Table of content

22

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF

The image types at a glance

23

Bit depth relates to color precision. More bits give more colors but require more storage.

1-bit images

24

1 bit per pixel: black or white only (a binary or monochrome image).

Used in fax, line art, some video games, printers, and masks.

Smallest possible; needs dithering for tone (later).

1-bit video games

25

8-bit gray-level images

26

Bit-planes: where do the structure live?

24-bit color images

Higher bit-depth: medical and multispectral

8-bit indexed color

Image source: « Le Labo du Jeu Video » David Louapre

Color Look-Up Tables (LUTs)

Example of color by number

32

Use case of LUTs and palette animation: the Game Boy

33

https://www.youtube.com/watch?v=GWvGjD7GpKs&t=172s

Devising a LUT: the median-cut algorithm

Example of the median cut algorithm

35

Example on a real image

36

Images in JPEG format support 16 million colors, a good approximation to the natural range of human vision.

The same image in GIF format, which supports only 256 colors. You can see bands of flat color where regions have been reduced to an average for a range.

Image source: Gabriel Ytterberg on Medium

Storage for different bit depth

Table of content

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF

Dithering (Halftone printing)

A 1-bit printer has only ink or no-ink yet is able to show grey photos.

• Halftone dither: vary dot size.
• Ordered dither: vary dot density.

Dithering trades intensity resolution for spatial resolution.

Dithering in classic games

40

https://www.youtube.com/watch?v=pgPDGIOJZd4&t=33s

Dithering

Ordered dithering

• ORDERED-DITHER(I, D, n)
• for x=0 to xmax do
• for y=0 to ymax do
• i = x mod n
• j = y mod n
• // I(x,y) rescaled to the range 0 .. n²
• if I(x,y) > D(i,j) then
• O(x,y) = 1 // white
• else
• O(x,y) = 0 // black

Error diffusion dithering

Round each pixel, then push the rounding ERROR onto neighbors not yet processed.

Errors cancel on average, so there is no fixed pattern and the result looks finer.

Ordered vs error diffusion

Ordered: fast, fixed pattern, tileable, good for print and hardware.

Error diffusion: slower, adaptive, best quality, good for on-screen.

Both fake tone the device cannot natively show.

Color depth in practice

Early computers climbed from 1-bit to 16 colors to the 256-color VGA palette.

'True color' is 24-bit; '32-bit' is 24-bit plus an 8-bit alpha channel.

Modern displays use 10 to 12 bits per channel (revisited with video).

Note

Table of content

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF

Raster vs vector

Raster files are images built from pixels, tiny color squares that, in great quantity, can form highly detailed images such as photographs.

Vector files use mathematical equations, lines, and curves with fixed points on a grid to produce an image. There are no pixels in a vector file.

Vector primitives in 2D

Vector primitives store control points and equations: lines, curves, polygons, fills.

Resolution-independent: rendered ('rasterised') on demand at any size.

Fonts, metafiles and SVG

Fonts store glyph outlines as curves, so text scales to any size.

• Windows WMF and EMF are vector metafiles: recorded Windows GDI drawing calls.
• SVG is the open XML vector format of the web.

Parametric curve

50

Bezier curve

51

Bezier curve: is a kind of parametric curve expressed as a weighted sum of a set of control points.

Weights are given by the Bernstein polynomial.

Quadratic Bezier curve

52

Nth order Bezier curve

53

Basis functions: Bernstein polynomials

When to use which image representation

Raster: photographs, anything with continuous tone or texture.

Vector: logos, icons, text, diagrams, maps, anything that must scale.

Many real files mix both (a PDF page can do both).

Reminder: 2D data representation

55

Images and videos have a unique representation

Videos

Images

Various 3D data representation

56

Unlike spatial 2D data (images, video), spatial 3D data can be represented in many ways

Point clouds

Voxel grid

Meshes

Signed distance function

RGB-D

Multi-view

Each representation is best suited for a particular tasks and geometric structures

Voxel grid representation

57

Voxel grid representation is a method for modeling 3D objects where the space is divided into a regular grid of cubes, known as voxels (volume elements).

• Each voxel in the grid can store information such as color, density, or material properties.

Zhengren Wang. 3D Representation Methods: A Survey

Point cloud representation

58

Problems:

• Often noisy due to the capture method
• Difficult to draw in undersampled regions
• No easy simplification or subdivision
• No smooth rendering
• No topological information

Mesh representation

59

Mesh represents objects by their boundaries with either triangles or quads

• Modular representation: can be subsampled to only keep the overall shape
• At the basis of any modern rendering pipeline and game engine
• Can use Bezier surfaces

Table of content

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF

What is an image format?

61

An image file format is a way of storing digital pictures using specific rules for compression, color, and data structure.

Anatomy of an image file

Header (e.g., size, bit depth, color type), then pixel data (often compressed), then metadata.

RAW format

63

High-quality digital image format used in professional photography as it captures all the unprocessed data directly from a camera sensor.

• Preserve maximal details, color depth and dynamic range, ideal for post-processing.
• But it is large in size and require specialized software to be read and visualized.

The simplest format: Netpbm (PBM / PGM / PPM)

PBM (Portable Bit Map) is a bitmap, PGM (Portable Gray Map) a graymap, PPM (Portable PixMap) a pixmap; an open family (Unix).

• A plain-text PPM header: P1/P3, then width height, then 255, then R G B triples.
• ASCII or raw binary; no real compression, but easy to read and write.

Windows BMP

Microsoft's native bitmap (also called DIB): header, optional palette, pixel rows.

Uses run-length encoding or is stored uncompressed.

Found on Windows; a poor choice for the web due to large file size.

Animated GIF format

Stores multiple images, so used for animation

8-bit indexed; a global color map, with optional local maps per image.

Pixel indices compressed with LZW (dictionary coding, see ELEN0060).

Only 256 colors per frame, which is why GIFs of photos look posterized.

PNG: the modern lossless format

PNG: gray, indexed or true color, up to 16 bits per channel (48-bit).

A full alpha channel and Lossless so used for keeping sharp details (e.g., logos, icons, etc.).

More in Session 9

TIFF and JPEG

TIFF: a flexible, tag-based container; originally lossless. Supports multiple layers.

JPEG: lossy, DCT-based, the photo standard; built in Sessions 9.

But, much more efficient than PNG for real images!

Looses details

EXIF: the metadata

EXIF records camera metadata inside JPEG files.

Book fields: exposure, light source and flash, white balance, scene type.

Cameras add more (aperture, ISO, lens, date, GPS); the GPS tag is a privacy point.

HEIF: still images from a video codec

HEIF is the still-image version of HEVC (H.265); Apple uses it to replace JPEG.

A flexible container: image sequences, depth, thumbnails, audio; up to 14-bit; transparency.

About half the size of JPEG at almost imperceptible quality change.

Newer formats: WebP and AVIF

Note

WebP (2010): lossy and lossless, alpha and animation in one format. Fast loading for the web thanks to its high compression rate.

AVIF (2019): still images built on the AV1 video codec, very small files.

Better prediction and entropy coding underneath.

SVG and EPS

72

Scalable Vector Graphics (SVG) is a vector graphic format. Images are stored as mathematical shapes, not individual pixels. Remain sharp at any size.

Encapsulated PostScript (EPS). Similar to SVG. Can support both vector and bitmap elements. Replaced by PDF. Remains used in high-resolution printing.

Choosing a format

Photograph? Use JPEG or HEIF.

Sharp graphics, text or alpha? Use PNG or SVG.

Animation? GIF or WebP.

Must not lose data? PNG or TIFF.

Ask yourself : continuous-tone or not, need transparency, need to scale?

Formats at a glance

➤ Photos: JPEG or HEIF. Graphics and alpha: PNG. Animation: GIF. Archival: TIFF.

Summary

An image is a sampled grid (space) of quantized values (amplitude)

Bit depth: 1, 8, 24 bits; indexed color with a median-cut LUT saves about 3 times storage

Dithering fakes tone; raster differs from vector, which scales

Raster versus vector images

Formats package it: PPM, BMP, GIF, PNG, TIFF, JPEG, HEIF, plus EXIF, PS/PDF, PTM

Image: where each stage lands

76

Table of content

Images as sampled signals

– Pixels and I(x,y)

– Sampling and quantization

– Resolution

– Upsampling and downsampling

Image types and bit depth

– 1 / 8 / 24-bit images

– Indexed color and LUTs

Dithering

– Ordered and error diffusion

Raster vs vector

– Two ways to describe a picture

– Bezier curves

– 3D data

File formats

– PPM, GIF, PNG, TIFF, JPEG, HEIF