Digital Video Lession #4 - Compression

There are two methods of compression lossless and lossy.

Lossless is a process in which the compressed data and be restore 100% identical to the original uncompressed data. An example being a ZIP file where you compress data to save space but when you uncompress it you need it to be exactly the same as the original files.

Lossy is different in that the compression results in a good aproximation of the original data. You can never go from a compressed file to the original as data has just been losted (deemed expendable) in the compression process.

You may be wondering why the heck you would ever use a lossy compression method when you can never revert to the original data? Well it turns out making a good lossless compression algorithm is extremely difficult and chances are you won't get much better than 2:1 ration (1meg file compressed to 1/2 a meg file) where as a lossy algorithm can have incredibly high ratios. It is not uncommon for a 50:1 ratio in video compression. Think of the previous example where an hour video took 100gigs of space. Now we can have an hour stored in 5 gigs and thus able to fit on a DVD disc. For the average person chances are if they were shown the original uncompressed directly next to the lossy compressed DVD they would not be able to tell any significant differences. This is where the advantage of lossy compression lies in extremely high ratios and being able to produce a final product that is a very good aproximation of the original.


Now, I'll present you with how "I believe" the current algorithms work in compression video images (like mpeg2/mpeg4 DVD/HDDVD) actually work.

A keyframe is the basis of a compressed video. The keyframe is a single image (of course a video normally contains thousands if not millions of keyframes) that other images can be mathmatically derived from.

Let's say you have a keyframe that contains mountains, grass, trees, sky, and clouds.
Now let's say the next frame of the video contains all the elements in the keyframe except a red house.

Well, since they're very similar we can say for this frame use the keyframe + 1 red house and now we have our image. Granted it's significantly more complicated in terms of math but that's the general idea. Find an image that is similar enough that we can mathmatically create it from a keyframe.

Project-Lesson #3 Number bases revisited

I reviewed my binary explanation and wanted to push a few more points I may not have been clear with.

Say we have the number (in base10) 9876
You can do the math in this fashion
(9 x 10^3) + (8 x 10^2) + (7 x 10^1) + (6 x 10^0)
(9 x 1000) + (8 x 100) + (7 x 10) + (6 x 1)
because
10^3=one thousand 10^2=one hundred 10^1=one ten 10^0=one one

so
9000 + 800 + 70 + 60 = 9876

In English we say nine thousand eight hundred seventy six
With each value (except the ones place) we have a specific way of identifying the power of ten
If you think of numbers in these terms it's easy to understand how each base is related


In binary (base2) say we have the number 1101 (equates to 13 in base10)
(1 x 2^3) + (1 x 2^2) + (0 x 2^1) + (1 x 2^0)
(1 x 8) + (1 x 4) + (0 x 2) + (1 x 1)
because
2^3=8 2^2=4 2^1=2 2^0=1
8 + 4 + 0 + 1 = 13


In hexadecimal (base16) say we have the number F3 (equates to 243 in base10 and 11110011 in base2)
(F x 16^1) + (3 x 16^0)
(15 x 16) + (3 x 1)
240 + 4 = 243

The nice thing about hexadecimal is that you can take any group of 4 bits (binary) into a single hexadecimal number

For example take 11110011 from above
1111 = 16(base10) = F(base16)
0011 = 3(base10) = 3(base16)

So 11110011(base2/binary) = F3(base16/hexadecimal)

Now the reason we use hexadecimal in the first place is because when you start getting into extremely large binary numbers it's just too insane to look at and manipulate directly.

For example the binary number
111111101101110010111010100110000111011001010100001100100001
equates to the hexadecimal value of
FEDCBA987654321

The other reason is with computers there is very little reason to work with anything smaller than 1 byte (8bits)
because you can really do much with less than 256 values. A single byte can be represented by a single hexadecimal number.


The reason I am trying to explain all this is because when I manipulate my video data I will be doing so on a byte for byte basis and will generally express my changes in hexadecimal notation.

Project-Lesson #2 The Pixel

In the computer world a monitor (or any display device) is made up of a grid of pixels. Think of a light bright. It's the same thing, a but they are much smaller and can be changed much much faster.

Let's revist the example I gave in the binary section with the 3 bits for RED, GREEN and BLUE

Now picture your monitor as a light bright. It has rows and columns of lights and we just want to turn them on of off according to what colors we want. Say we want to display an entire picture at once.

Using the example above we would need 3bits for each pixel. If we have 100 rows and 100 columns of pixels we would need
3bits x 100 rows x 100 columns = 30,000 bits in total

Now, a computer doesn't know anything about organization it only knows bits. So for a computer it doesn't worry about rows or columns. It just needs 30,000 bits for one picture. In reality a single picture is just a number. it's a large number but it really is just a number.

The computer then passes this number onto the monitor and the monitors job is to take that number and turn off/on the right pixels.

Now let's get into a real world example. The human eye can distingish around 16million color values and it turns out we need about 24bits per pixel to do this. To makes things simple we break each pixel into three 8bit (256 values) sections for RED, GREEN, and BLUE intensity values giving us 16,777,216 distinct color values.

Now let's say we are creating an image for television having the resolution of 720x480 (standard for TV in America).

720 x 480 x 24bpp = 8,294,400bits per image

TV runs at just under 30 frames per second.

So if we animated these images we need

720 x 480 x 24bpp x 30FPS x 60seconds x 60mins

or 895,795,200,000bits for an hour long video (NO SOUND!)

Now, to put that number in perspective
8bytes=1bit
1024bytes=1kilobyte
1024kilobytes=1megabyte
1024megabytes=1gigabyte

1CD = 700megabytes
1DVD SINGLE LAYER (DVR-Rs) =4.7gigabytes
1DVD DUAL LAYER (Films you buy) = 8.5gigabytes
For our hour long video we need just over 104Gigabytes of space! We'd need over 12 DVDs not including sound!

My next post I'll talk about how compression and how I believe it works and how it affects your video

Project-Lesson #1 Binary

I'm sure you've heard the word binary but might not have a good understanding of what it means. In order to understand my project you really need to understand how data is stored on a computer so I'll attempt to explain binary as best I can.

First, binary is really just all about numbers. When we use numbers in our everyday life it's all about base10. Binary is base2. So what's the difference?

Base10 = 10 values per digit. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Base2 = 2 values per digit. 0 and 1

You can have any base you want. In fact base16 is also very important in computers
Base16 (Hexadecimal) = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

The total number of values you can have in any base is equal to this formal
number of digits to the base power

So in base 10 if you have 2 digits (00 to 99) you have 100 possible values or 10^2
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 ... 99
In base 2 if you have 2 digits (00 to 11) you have 4 possible values or 2^2
00, 01, 10, 11
In base 16 if you have 2 digits you have (00 to FF) you have 256 possible values or 16^2
00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 0A, 0B, 0C, 0D, 0E, 0F, 10, 11, 12 .. FF

All general math works with any base
in base 10 01 + 09 = 10 10-09 = 01
in base 2 01 + 01 = 10 10-01 = 01
in base 16 01 + 0F = 10 10-0F = 01

If you don't understand think back to "carrying the one". 9 + 1 =10.. IN base10, 9 is the highest value you can have before you have to return to 0 and carry the one
In base2, 1 is the highest value you can have before you have to return to 0 and carry the one
In base16, F is the highest value you can have before you have to return to 0 and carry the one


Now you might be asking why the heck do we even bother to use binary? It seems to complicate things not make things simpler. Well the truth is base2 is as simply as we can get it. Think of binary in terms of FALSE and TRUE. Using FALSE/TRUE in conjunction can produce some very complicated results.

How you ask? Well let's take 3 bits and combine them. Think of each bit as either true or false.
We can have
FFF, FFT, FTF, FTT, TFF, TFT, TTF, TTT OR ALSO KNOWN AS
000, 001, 010, 011, 100, 101, 110, 111

8 Total combinations (2^3 = 8)

Now let's assume the three digits correspond to HAS RED, HAS GREEN, HAS BLUE
If we have FFF (000) we have black
if we have FFT (001) we have blue
if we have FTF (011) we have green
if we have FTT (100) we have cyan (GREEN AND BLUE)
if we have TFT (101) we have purple(RED AND BLUE)
if we have TTF (110) we have yellow (RED AND GREEN)
if we have TTT (111) we have white (RED, GREEN AND BLUE)

This is all your computer does. It takes large combinations of bits and interprets them based on very specific meanings for each bit. See the next post for a more detailed example on how a computer can create an image
from bits.

Project overview

I've decided to use the medium of digital video to work with on my project. My goal is to have a better understanding on how it works.

I intend to modify several video files (in various different formats like MPEG, quicktime etc etc) at the bit level in order to maniplate the image. Think of it almost as taking some film and scratching the grain off. However instead of just scratching the grain off I want to be able to add grain, and change the denisty of the grain as well.

In order to explain what I am doing I'm going to be presenting you with a breif overview of how a computer works and how the most simplistic of digital video works.