1 of 34

It’s all bits!

Acknowledgment and Disclaimer: This presentation is supported in part by the National Science Foundation under Grants 1240841, 1225680, 1225719, 1225745, 1225976, and 1226216. Any opinions, findings, and conclusions or recommendations expressed in these materials are those of the authors and do not necessarily reflect the views of the National Science Foundation.

2 of 34

Run-Length Encoding (RLE)

  • RLE compression
  • # white pixels, # blacks, # whites, …
    • 16: Row 1 has 16 white pixels
    • 12, 3, 1 : Row 2 has 12 white, 3 black, 1 white

3 of 34

Run-Length Encoding (RLE)

  • RLE is a lossless compression technique.
  • Good for images with lots of whitespace.
    • E.g., Fax images
  • Used in BMP (bitmap) images

4 of 34

Lossless vs. Lossy Compression

  • Lossless: original image can be perfectly reconstructed from the compressed data.
    • Good for medical, archival images.
    • Used in BMP (bitmap) images

​

  • Lossy: some data may be lost during compression
    • Ok for camera images where the lost data cannot be perceived by the human eye.
    • For example, JPEG

5 of 34

How much data?

256 pixels

16 by 16

62 numbers

​

RLE

​

Original Image

​

6 of 34

How much data?

How much? Depends on how many bits per pixel

256 pixels

16 by 16

62 numbers

​

RLE

​

Original Image

​

7 of 34

Monochrome Image

  • 1 bit per pixel
  • 256 pixels requires 256 bits
  • 1 = white, 0 = black
  • Old technique, 1960s

8 of 34

Monochrome: How much data?

Original

Image

Compressed

Image

​

9 of 34

Monochrome: How much data?

256 pixels

1 bit/pixel

256 bits

Original

Image

Compressed

Image

​

10 of 34

Monochrome: How much data?

256 pixels

1 bit/pixel

256 bits

62 numbers

8 bits/number

496 bits

Original

Image

Compressed

Image

​

11 of 34

Monochrome: How much data?

256 pixels

1 bit/pixel

256 bits

62 numbers

8 bits/number

496 bits

Original

Image

Compressed

Image

​

>

12 of 34

8-bit Color Image

  • Old technique, 1980s
  • Red, Green, Blue (RGB)
  • 8 bits per pixel
  • 3 R, 3 G, 2 B

​

0 1 2 3 4 5 6 7

R R R G G G B B

1 1 1 0 0 0 1 1

​

  • 0000 0000 = black (0)
  • 1111 1111 = white (255)

​

13 of 34

Modified RLE

If there are more than 2 colors, RLE needs two numbers per run: the color and the run length

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

14 of 34

Modified RLE

If there are more than 2 colors, RLE needs two numbers per run: the color and the run length

Twice as many numbers

124 numbers

8 bits/number

992 bits

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

15 of 34

Modified RLE

Original

Image

Compressed Image

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

16 of 34

Modified RLE

256 pixels

8 bits/pixel

2048 bits

Original

Image

Compressed Image

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

17 of 34

Modified RLE

256 pixels

8 bits/pixel

2048 bits

Original

Image

Compressed Image

124 numbers

8 bits/number

992 bits

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

18 of 34

Modified RLE

Original

Image

Compressed Image

124 numbers

8 bits/number

992 bits

256 pixels

8 bits/pixel

2048 bits

<

255,16

255,12, 0,3 255,1

255,10, 0,5, 255,1

255,9, 0,2, 255,1, 0,3, 255,1

255,8, 0,6, 255,2

255,7, 0,2, 255,1, 0,4, 255,2

255,6, 0,7, 255,3

255,3, 0,5, 255,1, 0,4, 255,4

255,4, 0,7, 255,5

255,5, 0,5, 255,6

255,4, 0,5, 255,7

255,2, 0,2, 255,1, 0,1, 255,1, 0,2, 255,7

255,1, 0,2, 255,1, 0,1, 255,3, 0,1 255,7

255,1, 0,1, 255,1, 0, 2, 255, 11

255,0, 0,4, 255,12

255,0, 0,2, 255,14

​

19 of 34

24-bit Color Image

  • Red, Green, Blue (RGB)
  • 24 bits per pixel
    • 8 R, 8 G, 8 B
  • 224 = 16,777,216 colors
  • More than we can see

​

​

  • 3 numbers for each pixel
  • 0,0,0 = black
  • 255,255,255 = white
  • 255, 0, 200 =

​

20 of 34

24-bit Color Image

Four times as many numbers

248 numbers with 8 bits/number

1984 bits

255,255,255,16

255,255,255,12, 0,0,0,3 255,255,255,1

​

…

​

​

255,255,255,0, 0,0,0,4, 255,255,255,12

255,255,255,0, 0,0,0,2, 255,255,255,14

​

21 of 34

24-bit Color Image

Compressed Image

Original

Image

255,255,255,16

255,255,255,12, 0,0,0,3 255,255,255,1

​

…

​

​

255,255,255,0, 0,0,0,4, 255,255,255,12

255,255,255,0, 0,0,0,2, 255,255,255,14

​

22 of 34

24-bit Color Image

Compressed Image

Original

Image

255,255,255,16

255,255,255,12, 0,0,0,3 255,255,255,1

​

…

​

​

255,255,255,0, 0,0,0,4, 255,255,255,12

255,255,255,0, 0,0,0,2, 255,255,255,14

​

256 pixels

24 bits/pixel

6,144 bits

23 of 34

24-bit Color Image

Compressed Image

Original

Image

255,255,255,16

255,255,255,12, 0,0,0,3 255,255,255,1

​

…

​

​

255,255,255,0, 0,0,0,4, 255,255,255,12

255,255,255,0, 0,0,0,2, 255,255,255,14

​

256 pixels

24 bits/pixel

6,144 bits

248 numbers

8 bits/number

1984 bits

24 of 34

24-bit Color Image

Compressed Image

Original

Image

248 numbers

8 bits/number

1984 bits

256 pixels

24 bits/pixel

6,144 bits

255,255,255,16

255,255,255,12, 0,0,0,3 255,255,255,1

​

…

​

​

255,255,255,0, 0,0,0,4, 255,255,255,12

255,255,255,0, 0,0,0,2, 255,255,255,14

​

<

25 of 34

Amount of RLE Compression?

  • Depends on # bits/pixel
  • But, even more importantly...
  • ...Depends on # of different colors in the image

​

The more colors,the more color changes, the more numbers needed.

26 of 34

We’ve seen binary used to

​

  • represent numbers
  • represent colors
  • represent machine language

27 of 34

So,...

What does this bit sequence represent?

​

​

0100 0001

​

28 of 34

So,...

What does this bit sequence represent?

​

​

0100 0001

Is it the number 65?

​

29 of 34

So,...

What does this bit sequence represent?

​

​

0100 0001

Is it the number 65?

Is it the letter ‘A’

30 of 34

So,...

What does this bit sequence represent?

​

​

0100 0001

Is it the number 65?

Is it the letter ‘A’

Is it the color

​

31 of 34

It Depends!

on how

​

0100 0001

​

is used

in an Image?

a Text Message?

a Spreadsheet?

a machine language code?

​

32 of 34

It’s all bits!

33 of 34

Representing Character Data

  • American Standard Code for Information Interchange (ASCII), 1960s
  • 7-bit code, 128 characters

34 of 34

Representing Character Data

  • ASCII, Some Common Codes

​

Binary

Hex

Decimal

Character

0010 0000

20

32

Space

0011 0000

30

48

0

0100 0001

41

65

A

0110 0001

61

97

a

​

​

​

​