Tuesday, October 3, 2017

VP9 ELI5 Part 3

For this part, I'll need to define how the input image data (what we're encoding) is stored.

Pixels and color storage methods

Up until now, I only said that image data is not RGB, but rather YUV. But that doesn't tell you anything about how it's stored on the computer. The image, as you know, is 960x540 pixels. That means 960 pixels wide by 540 pixels high. When it was taken by the camera and when it's shown on your screen, it is merely a 2-dimensional array of pixels. It was not subdivided because it's just a plain image, not yet encoded with VP9.

Let's zoom in so you can get an idea of the individual pixels in the B/W image.



If you use the eyedropper tool in MS Paint, you can pick up a color from an image. You can see just what that color's RGB value is by going into Edit Colors.



As you can see, white is 255, 255, 255. As we discussed earlier, pixel values in VP9 follow a similar system but with YUV. Shades of gray, which is what the B/W YUV image is made up of, can be made in RGB by setting all three numbers to the same value.

Most importantly, why do you think MS Paint is limited to 255? It's because colors on a computer are almost always 8 bits (bits means 0's and 1's) per channel. On a computer screen, channels are RGB, hence MS Paint's use of RGB instead of YUV.

If you have 8 bit fields capable of holding 0 or 1, you can think of it as a row of light switches. How many combinations of On and Off can you come up with by flipping 8 light switches? The answer is 2 raised to the 8th power, or 256. That's because you have 2 states (On/Off) and you have 8 places that can be set to either state. But if you have 10 light switches, that would be 2 to the 10th, or 1024.

You can't reach 256 with 8 bits because 256 is how many states you have. One of them is 0. It would be like having 60 minutes in an hour but ending each hour on a clock at 60 instead of 59.

In this tutorial we will be dealing with 10-bit pixels, capable of ranging in value from 0 to 1023 instead of the usual 8-bit values you may be familiar with that range from 0-255. This is because it's a proven fact that 10-bit video carries higher quality at a given bitrate than 8-bit video. I'm not joking when I say that a 10-bit 1080p video at 1 Mbps can actually look a lot better than an 8-bit 1080p video at 2 Mbps.

Understanding RAW image data

You may have heard of RAW images taken by expensive DSLR cameras, but that's not what we're talking about here. In video, RAW data is a bit different.

A common format for RAW video data is YUV420p. 8 bits per value is implied because a bit depth wasn't specified. You can export to this format using a tool called FFmpeg. I'll describe how YUV420p files are structured before we move on because although we won't be using YUV420p, we will be using YUV420p10LE which is quite similar but more complicated.

In a RAW YUV420p video file, each frame is stored one after the other with no separators. It is simply the Y (B/W image), U and V. Then it repeats for the next frame.

You're probably familiar with the fact that computer data is stored as bytes, and that bytes are 8 bits each. Therefore, a byte can represent any number from 0 to 255. In a readable text file, each letter or other character is simply a number (usually less than 128) that your text reader knows corresponds to a letter or character. But if you've ever opened an image or program in a text editor, you know that they contain weird random characters. That's because the bytes in the file are storing numbers that don't correspond to readable characters.

(A PNG file opened in Notepad)

In a YUV420p video, we first store the B/W image pixel-by-pixel in raster scan fashion, meaning left to right and top to bottom. Note that there is no subdivision here. The raster scan does the whole image line by line.


So you see, raster scanning begins at the absolute top-left pixel, scans to the right until the end, goes down one, jumps back to the left, and goes again.

[You don't need to know the following formulas unless you choose to follow along. If you're just reading then you'll be fine without them]

That will take up (width * height) bytes, since each pixel takes one byte. Then we need to store the U and V images. Well, since the width and height of those are 1/2 the dimensions of the B/W image, the data for U and V will each be ((width / 2) * (height / 2)) bytes. Since we must copy U and V like this, that will be 2 * ((width / 2) * (height / 2)) bytes.

So now we have (width * height) + (2 * ((width / 2) * (height / 2)) bytes of data for just one frame. With an image size of 960x540, that comes out to 777,600 bytes total.

So for each frame in our YUV420p RAW video, the first 518,400 bytes will be the B/W image, the next 129,600 bytes will be the U image, and the remaining 129,600 bytes will be the V image.

Understanding YUV420p10le RAW image data

YUV420p only handles values from 0 to 255 because it's an 8-bit format. Since we want to work with 10-bit image data, we need a way to store values from 0 to 1023. This is where YUV420p10le comes in.

Since files are stored as bytes and bytes are multiples of 8 bits, we can't easily store 10-bit values because we'd have a fraction of a byte left over after almost every 10-bit value we write. This is why YUV420p10le stores the 10-bit values inside a larger 16-bit value. Since 16-bit numbers can range from 0 to 65,535 it will easily store our 0-1023 values.

So now we have to store 2 bytes for each value (16 bits = 2 bytes). The file structure stays the same so our file size doubles to 1,555,200 bytes or 1.48 MiB.

By now you may have guessed that having a higher range of available values makes for a higher-quality image. In a normal PC image, for example, 8 bits per color channel times 3 channels (RGB) equals 24 bits per pixel overall, or 24.7 million different colors. But what if you only have 256 colors at your disposal? The image will look quite bad.

(The image in only 256 colors. Click to enlarge and see how bad it is)

Videos encoded with 8-bit YUV420p look great. In fact, it's the bit depth that all YouTube videos are encoded with, even the ones that claim to be HDR which is at least 10-bit. But 10-bit video is better because you can express a far greater range of light and dark. Converting from 8-bit to 10-bit increases the range by simply multiplying the values to bring them up to the 10-bit range, but there will not be any increase in actual quality because you can't get information that was never there to begin with.

If that sounds confusing, let's say you have a gradient of 8-bit pixels: {15, 16, 17, 18, 19}. Now if you wanted to convert them to 10-bit, you would multiply each entry by 4 to get {60, 64, 68, 72, 76}. But notice that you don't have any values in-between whole multiples of 4. If you had recorded the video with a 10-bit camera you could have any value in the 10-bit range (theoretically), but since you converted from 8-bit you will only have the 256 different 8-bit levels spread evenly within 1024 total levels.

When you convert an 8-bit video to 10-bit, this is all you're doing.

This means that in our case the only purpose of converting to 10-bit is so we can have 10-bit values for our VP9 encoder to work with.

Opening RAW videos in a hex editor

Let's see what RAW video data looks like in a hex editor. What you're looking at in these hex screenshots are the pixel values at the beginning of the file, the first few pixels in the top row of the B/W image. These are shades of gray expressed as numbers, but if that doesn't make sense then I'll try to explain.

Here is what the 8-bit image looks like in a hex editor:

On the left we have hex digits and on the right, bytes as they'd be seen in a text editor

And this is the image in 10-bit format:

In this 10-bit example, each pixel value takes up 2 bytes.

There is an annoying quirk you have to watch out for on multi-byte numbers. Most computers read and write them as Little Endian which means byte-reversed.

Let's take the example of 255 which is 0xFF in hex. Hex works by using 0-9 and A-F to make a base-16 number system. 2 hex digits make a byte.

If we have a hex byte of 0xFF (255 decimal) and add 1 to make 256, it would "overflow" and we would get 2 hex bytes: 0x01 0x00. On Windows Vista and up, you can try setting Windows calculator to Programmer and use the Hex mode to enter 0100, then click Dec and it will say 256.

So now that we've established that, let's say you wanted to record that number in a file. You know about place value in the decimal system (tens, hundreds, etc) so you'd expect to just write 0x0100 to your file, right? Well, it turns out that due to a computer quirk carried from the 1970's, the computer would prefer it if you did it in reverse as 0x00 0x01. This applies even to longer hex numbers like 0xDEADBEEF. Each pair of hex digits must be written in reverse order; do not write the single digits in reverse order. 0xDEADBEEF should become 0xEFBEADDE, not 0xFEEBDAED.

Since this weird reverse notation is called Little Endian, it makes sense that the normal order you'd expect to use is called Big Endian. Keep in mind that the bytes (pairs of hex digits) are what's reversed, never bits or single hex digits.

Little Endian is what the LE in YUV420pLE stands for.

So now let's set our hex editor to group by Words (Word = 16 bits).

By default, it's set to Little Endian so these hex bytes are reversed to Big Endian for proper viewing.

Let's press Ctrl+1 or go to View -> Display As -> Decimal. Now you can see that the values are all normal human-readable numbers and that they never exceed 940.


[Random trivia, not necessary to continue] Why don't the values exceed 940 when we were supposed to convert to a 0-1023 range? Because video of photographic subjects (ie not computer screen captures) customarily ranges not from 0-255 or 0-1023, but rather from 16-235 or from 64-940 (16-235 times 4).

Now you can see what I mean by shades of gray expressed as numbers.

VP9 ELI5 Part 2

Here's the photo split into its 3 YUV components:
The U and V are the color add-on data. Notice how they are 1/4 the size of the B/W image.

Most video formats, VP9 included, depend on both intra and inter frames. An intra frame is a normal picture while an inter frame is just the difference between the current frame and a previous one. Think of it as only saving what moved in the current frame instead of saving the whole picture again.

Obviously we need to start a video with an intra frame, also known as a key frame, so that we can build future inter frames based on it.

Unlike BMP's, we don't save VP9 images pixel-by-pixel in order. Instead, we divide the image on several levels. The first, highest level of division is into 64x64 superblocks.

64x64 is a very large subdivision size. In MP4 (H.264), the largest size available is 16x16. Notice the difference below:

16x16

64x64

The superblocks are processed in raster order. That means left to right, top to bottom. In other words, each horizontal line of superblocks is processed from left to right, in order from top to bottom.

Each superblock is then optionally subdivided further. Here are some possible subdivisions:



Notice what subdivisions are allowed. Shown from left to right, we can split a superblock:
  • Vertically to make 16x32,
  • Horizontally to make 32x16, or
  • Four ways to make 4 32x32 blocks

After that, we can split the 32x32 blocks the same way or we could leave them alone. However, we may not further split one of the non-square sizes. Any non-square split is final in VP9. Also note that 4x4 is technically as small as we can get but things get messy at that size so for this tutorial we will not go smaller than 8x8.

This is just the first level of subdivision. The next level is the transform level and is more interesting.

VP9 ELI5 Part 1

Welcome to my VP9 Explain Like I'm 5 series. I'm going to explain the VP9 codec so anyone can understand it and perhaps even create their own encoder.

What is VP9 and why should I care?

First things first, let's establish what VP9 is. It's a video codec created by Google and it's what almost all YouTube videos are saved as on the server. Previously, YouTube videos were all MP4 (specifically, H.264). There were two problems with that. The first is that it's patented and copyrighted, so you have to pay the MPEG group. Second, it takes a lot of data for any given quality level. Mobile consumers aren't the only ones who pay by the gigabyte for their data usage; businesses have to pay for that as well to serve people. Normally video has a tradeoff: you can have higher quality for more data usage, or less data usage with bad quality. VP9, amazingly enough, allows Google to pack higher quality into less data, achieving both benefits at once. Unfortunately, only Google and Netflix use VP9; everyone else still uses MP4.

Video definition

You probably already know it's a series of still pictures called frames. If you took pictures really fast with your still picture camera, you could play them quickly to see a crude video. Video is merely a set of still pictures played one after the other really fast.

What are these pictures composed of?

You may be thinking, "A picture is simply dots (pixels). Each one has an RGB (red, green, blue) color value. I know because I've done pixel art in MS Paint." Well, I've got to tell you, that's not how images work in a video.

To explain this, I'll need to give a brief history lesson. You see, video frames could easily use RGB colors like you might have assumed. However, the US TV system was defined near the beginning of World War II and only carried black-and-white video until the 1950's. So instead of red, green, and blue, the old TV system only carried brightness values (shades of gray). You can approximate that in MS Paint by using the same number for red, green, and blue.

In the 50's, they wanted to add color to TV without breaking compatibility with existing TV's. They weren't willing to go the 2009 route and make everyone buy a new TV. What they did was mix a small amount of color data onto the existing black-and-white signal. That way, old TV's would still decode it while color TV's would add the color info on top of the black-and-white picture.

The FCC had allocated 6 MHz bandwidth for TV channels. The engineers couldn't add too much extra color without the signal bleeding onto other channels, so they devised a system of saving only a low-res copy of the image in color format while saving the full-res image in B/W format. The low-quality color image was enlarged and super-imposed over the B/W image, making good color because the human eye sees more brightness than color.

Even though NTSC is nearly dead, this system lives on in computers as YUV 4:2:0. If you want to read more, check out the YUV Wikipedia page.

Let's get started

For this series, we'll be working with the following 960x540 color photo. In case you didn't know, that's 1/4 the size of 1920x1080.

Credit: Lt. Zachary West, 100th MPAD, Flickr, CC BY 2.0

This wasn't actually 960x540 but I cropped and resized so it would be a nice easy size.

If you want to follow along, you can download the image.

Monday, September 18, 2017

OpenCodecDev Discord channel

I just created a new Discord channel called OpenCodecDev, for the purpose of discussing open-source media codecs. It's public so anyone can join. We also have a voice channel.

Here's what it will look like in the Discord desktop app. I'm under Admin, and Foxx is a newcomer.


Notable features of Discord include:

  • Posting images, whether photos or pasting from PrintScreen.
  • Blog URL's become a block with an excerpt from the post
  • YouTube URL's are expanded into a player in the chat history
  • Unlimited backlog which is stored on the server. You don't miss out on messages that happened while you were logged out, unlike IRC, and no past message is ever lost.
  • The backlog is searchable.
This will be more convenient than the Google group, and it has a better GUI than IRC.

Monday, August 14, 2017

Root-Raised Cosine

Yesterday I finally figured out the root-raised cosine. I've been trying to understand it for about a year. It's very necessary for transmitting PSK signals because merely mixing a square wave with a carrier wave makes a wave with sharp transitions that cause lots of spurious signals. The clean, narrow PSK signals you may have seen are all using the root-raised cosine.

Here is the resource that I found yesterday to explain it properly: Pulse Shaping with raised cosine filters.

I found it confusing at first for two reasons. The first is that I didn't know if Wikipedia's formula was for time or frequency domain, and the second is that I had no idea that the RRC is centered on each PSK symbol, meaning that a time of 0 is the center.

Here is the time-domain formula from the University of Stuttgart's Webdemo (linked above):
[REF] Stephan ten Brink, "Pulse Shaping," webdemo, Institute of Telecommunications, University of Stuttgart, Germany, Aug. 2017. [Online] Available: http://webdemo.inue.uni-stuttgart.de

Why to use it

If I told you to multiply a square wave with a cosine and sine wave to make a QPSK signal, you'd get a result similar to the top stereo track shown below.


Those are some sharp transitions. This is what I got when I first tried to make my own QPSK signals. It seems well and good, right? We have our digital wave mixed with I (cosine) and Q (sine) to make an IQ signal playable in an SDR program. Well, yes, but there's a slight problem...


[Vertical is frequency, horizontal is time]
This isn't what QPSK is supposed to look like. See all the spurious signals splattering everywhere? Satellites like Inmarsat have neat and narrow QPSK, so why does mine look so bad?

It turns out that we've simply placed a square wave (which is full of harmonics) into the RF spectrum by mixing with a carrier.

Now, notice the bottom stereo track. It is the same QPSK signal, but smoothed out using a root-raised cosine filter.


Notice how narrow it becomes:


The signal is also good enough that Signals Analyzer can lock onto the 80 kBit bitrate:


I initially made the mistake of entering 40000 in the BR (bitrate) field because it's 40 kHz QPSK, and with QPSK the bitrate is twice the symbol rate.

(Below) SA can also lock onto the bitrate of the unfiltered QPSK, which means that although it's undesirable for transmitting, it is nonetheless a valid signal (although I did have to zoom out the bottom-left constellation window a bit).



How to use it

The formula generates "taps", which means an array of values to be used on the signal you want to process. In our case, we multiply the taps by our signal.

Here are the variables:

t: time, in fractions of a second, since the center of the symbol.
T: length of half a symbol, in seconds (1 / (2*symbol rate)). (Why not 1/symbol rate? Pitfall explained below)
alpha: roll-off factor, ranges from 0 to 1 (1=wide, 0=brick wall filter)

To maintain the parameters of the signals shown earlier, let's assume we want a QPSK signal with a symbol rate of 40 kHz (80 kbit/sec) and we'll have it in an IQ file sampled at 1 MHz.

Our variables would be:
t: x/sample rate (in our case, x/1000000). x is the FOR loop variable.
T: 0.0000125
alpha: 0.1 (very high roll-off)

40 kHz is a convenient value since we want an odd number of taps. Since 1,000,000/40,000 = 25, it will take 25 samples to make one symbol and so we need 25 taps.

The center value will be 12 (base 0) or 13 if you prefer base 1. We want to start at 0 so we can do our time values properly, so we want a FOR loop to go backwards from 12 to 0.

Pseudocode:
---------------------------------------
for (x = 12; x >= 1; x--) {
    taps[12 - x] = [The formula depicted above, substituting (x/1,000,000) for t]
}

taps[12] = 1

for (x = 1; x <= 12; x++) {
    taps[12 + x] = [The formula depicted above, substituting (x/1,000,000) for t]
}
---------------------------------------

This code will give you 25 taps. Think of it as a matrix with just one column; you would use matrix multiplication to multiply each point by a corresponding point in time on an unfiltered QPSK signal. Just make sure to align this so that the taps begin at the beginning of the QPSK symbol, otherwise it won't filter properly. Here's a crude ASCII drawing of what I mean:

|     Taps       |        |   QPSK   |
|   Matrix       |   *   |       IQ       |
|                   |        |   samples |

Note that both matrices are only ONE symbol long; the taps repeat at the start of each symbol.

Pitfall

The pitfall I was referring to is that 0 is the center. This is what my first RRC taps looked like when I calculated starting from 0:


I mistakenly thought that was the whole filter but it's only the right half. Again, here is the right half of another RRC filter:

And finally, here is the output of this mistake. I applied the right half of an RRC filter to the QPSK starting at the beginning of each symbol, which kept the ends from matching properly. When it's done right, the ends meet perfectly. I eventually found out it needed to be mirrored and applied with 0 being the center of the symbol.


This is why we use 1/(2 * bitrate). If you use 1/bitrate, then the right half will span the entire symbol time when you only want it to span half. With 1/(2 * bitrate), each half will cover half the symbol.

I hope this helped if you had no idea how to program the RRC. Use the comment section below if you have any questions or if I left something out.


Tuesday, August 8, 2017

UTSC v1 Packet Specification

After showing the spec to Foxx, wordsun, and Corrosive, only Corrosive had a suggestion and it was to allow embedding a list of ID's in the packets to facilitate pay-per-view. In other words, broadcasters could include a list of ID's of various decoder boxes so only specific paying viewers can see a channel. This is in contrast to my current method of handling encryption like Wi-Fi, using a single password for the channel. I told him his one-key-per-viewer idea most likely wasn't feasible since the packets need to be small.

Here is a link to the document: utsc_finished_release_r1.txt

License:

The UTSC name and specification are Copyright 2017 Designing on a Juicy Cup. The specification may be freely implemented by anyone for any purpose as long as this copyright notice is displayed in the license. The UTSC name may be used in products implementing this standard as long as attribution is made to Designing on a Juicy Cup.

Monday, August 7, 2017

UTSC v1 Standard Finalized

Since 2016, I've been working on a way to transmit digital TV in the 900 MHz Part 15 band. The main focus is on reliability, because ATSC fails miserably in that department. The second focus is on unlicensed operation, because broadcasting is a near-monopoly.

The format officially consists of a 1 Mbit data stream containing VP9 video at about 900 kbits and Opus audio at 48 kbits. Opus is extremely resilient and can withstand high loss, similar to analog TV's sound. It also sounds amazing at that bitrate. Other services, such as audio or data, could be conveyed as well.

My proposed standard is called UTSC. The acronym means nothing, officially. It is designed to be expansible like WAV, meaning that new features can be added without breaking compatibility with the first receivers. My current research suggests that I can fit 32 channels in the band in any given area.

The standard can accommodate any video codec, resolution, and frame rate in theory, but VP9 960x540 @ 30.000 fps is suggested.

I finalized the standard today and I'm documenting it here as proof that I devised this first. If someone else claims to have been first, you can verify with the Wayback Machine that no site before this date carried this info.

The encoder and air interface are proprietary and will not be released yet. However, I'm planning to release the packet format for public review. I'm submitting it privately to Foxx, Corrosive, and wordsun for a pre-review.