Skiing over Easter is something of a tradition and the Swedish resort Åre is the ideal place for it. It is not only the largest and most popular resort in Sweden, drawing in people from all over the country, you'll also spot skiers from Norway, Finland, Estonia, even Russia.

This year's trip was blessed with excellent weather, which always makes a big difference in the mountains. Here's a bunch of pictures from the resort (hosted on deviantart).

There's also a short clip of me skiing down the slopes (hosted on youtube).

Now that's a way to spend Easter! :star:

The big new change in undvd 0.4.0 was a dynamically set bitrate based on the bits-per-pixel (bpp) value. That addition not only completely changed the way undvd deals with bitrates, it also made possible further improvements.

The guiding principle of undvd remains be smart if possible, don't bother the user. A brand new feature is a smarter way to determine how to scale the video. This is another under-the-hood improvement which improves the program without introducing any more bloat or changing the user interface.

How do we scale?

To motivate the issue, let's consider an example. Until now, undvd scales to 2/3 of the original width.

For a 720x576 (5:4) dvd movie this gives target dimensions 480x384, for a total of 184,320 pixels. For a 2 hour movie (25 fps), this gives results in a video 771mb (plus the size of the audio, some 140mb).

480 * 384 * 25 * 0.195 * 7200 / 1024² / 8 = 771mb

But for a movie of different dimensions, a constant scale factor would yield a smaller number of pixels per frame. Suppose another movie has dimensions 720x480 (3:2). This would give target dimensions 480x320, a total of 153,600 pixels. The video size would, of course, be proportionally smaller as well.

480 * 320 * 25 * 0.195 * 7200 / 1024² / 8 = 642mb

This is probably not what you want. You give up the same proportion of pixels in both cases, but for a movie of smaller dimensions it would be nice to get the same frame size, ie. keep a greater portion of the frame. In the extreme case, for a movie with dimensions 720x224 you would probably want to keep the frame intact (161,280 pixels) and you would still get a smaller file.

Scaling by frame size, not width

So the obvious solution is to consider the number of pixels in a frame, not just along the width. As with the bpp in the previous increment, what used to be the default becomes the starting point for interpolation. So 720x576 will still scale to 480x384. But 720x480 becomes 528x352 (185,856 pixels) and 720x224 would not be downscaled at all.

What complicates the issue somewhat is the need to pick dimensions such that it comes to an even number of 16x16 pixel blocks (I'm not sure how crucial this actually is, but the absolute of majority of video files obey this rule). This reduces the number of possible dimensions for a movie of a given aspect ratio.

For instance, take dimensions 720x272. This gives a frame size just over the desired 184,320 pixels. But the next possible option is 256x96, which is tiny. Here undvd does the "smart" thing and picks the dimensions closest to the target size (in this case leaving it intact).

The nitty gritty

Deciding on a scaling factor is quite simple. Starting from the equations to scale the width and height separately,

width * factor = scaled_width

height * factor = scaled_height

we obtain a formula to find the number of pixels in a frame.

width * height * factor² = framesize

Assuming we know how many pixels we want in a frame irrespective of the dimensions, we can derive a formula to find the scaling factor.

factor = sqrt( framesize / (width * height) )

To reuse the example of the 720×480 movie, we find

0.730 = sqrt( 184,320 / (720 * 480) )

Scaling by this factor we get the target dimensions of the video.

720 * 0.730 = 525.813

480 * 0.730 = 350.542

It may not surprise you to know that the new dimensions do not divide evenly by 16. The nearest dimensions satisfying the multiples-of-16 rule are 480x320 and 528x352, but the latter is closer to our starting point.

Multiples of 16

Finding the width and height is a bit more hairy because we have to find two values that correspond. I don't think there is a formulaic solution to the problem because it amounts to solving this set of equations:

width * height = framesize

width = ratio * height (where ratio is known)

width = a * 16

height = b * 16

framesize = c * 16

The last three equations do not help, because they do not relate any two of the variables (width, height, framesize) to each other. And so we have the top two equations of three unknowns, which is not going to work. Intuitively, we know this is true, because we expect there are many sets of (width, height, framesize) that are possible solutions, so this set of equations will not give us a solution.

But it can be solved with an algorithm:

local ratio="$orig_height/$orig_width"

step=-1
unset completed
while [ ! "$completed" ]; do
	step=$(( $step + 1 ))

	local up_step=$(( $width + ($step * 16) ))
	local down_step=$(( $width - ($step * 16) ))
	for x_step in $down_step $up_step; do
		local x_width=$(( $x_step - ($x_step % 16) ))
		local x_height=$( echo "scale=0; $x_width*$ratio/1" | bc )
		if (( ($x_width % 16) + ($x_height % 16) == 0 )); then
			completed="y"
			width=$x_width
			height=$x_height
		fi
	done
done

Here step is the distance from our starting point, each time used to set the values up_step and down_step to successive upwards and downwards increments of 16 respectively (525+16, 525-16). For each of these we run the inner loop, setting x_width to the value that divides 16 within the range [x_step, x_step-16]. We now have a valid value for the width. We now use the ratio to find the corresponding height while preserving the aspect ratio, stored in x_height. If both x_width and x_height are multiples of 16, we have found dimensions for the video.

If we were to apply the Pareto principle to fit the world of software development, I would suggest the following translation.

Building 80% of the product takes 20% of the effort.

It's not surprising. A little code goes a long way. Typically problems we attack have a wide frontier we can cover with little effort. That is why we choose them. And while no software really can be said to be 100% complete in a mathematical sense, it certainly takes a great deal of effort to "finish it off" by handling all those special circumstances and corner cases.

What is wrong with 80% completion anyway? Isn't that good enough? Often it is. But there is that little voice in your head that says since you've already done "almost all of it", why not finish it? After all, there is a sense of accomplishment at stake, and since you've already attacked the problem, there is that urge to solve it completely.

undvd was 80% complete by version 0.2.2, with packages for Gentoo, Ubuntu and Fedora. Version 0.3.x added things I didn't plan to include at all when I started this project. The new features made it possible to set an output size (and thus indirectly set the bitrate), set 2 pass encoding, and set scaling. I was wary about compromising the key principle: undvd should be obvious and easy to use. But the new goodies were tucked into an "advanced" menu and so I don't think they did a lot of damage.

Since 0.3.0 there has been a host of tweaks and small fixes for small problems. One such problem was that undvd worked well on terminals with a black/dark background, but was not tested on a white/light background. That is unfortunate, given how gnome-terminal and konsole both use a light background by default. These kinds of fixes are enjoyable in that they improve the overall user experience in subtle ways, but without changing anything in the way you have to use the software.

Preparing to leap again

Having said that, one technical aspect I wasn't entirely pleased with was how undvd sets the bitrate. This is something of a black art, and I had done pretty intensive testing before deciding that 900kbps seemed ideal for h264 video. But debating the ideal bitrate is like debating the ideal size for a jpeg image. At the very least, it matters what the dimensions are. I had been scaling the image to 480 pixels wide in my tests, and so with greater dimensions the result wouldn't be as good.

I came across a very helpful article that deals with bitrates and also contrasts the h264 and xvid codecs. Discussing bitrate is pointless, because bitrate isn't a constant, it's a function of other quantities. What we need is a constant to standardize on.

Going back to the jpeg example, let's start with a frame of video. 480x384 gives 184,320 pixels, if we use one bit to store each pixel we come up with a quantity that is bits per pixel, abbreviated to bpp. So we're using 184,320 bits (180 kilobits, or 22 kilobytes) to store this one frame.

Let's take the single frame and another however many frames that fit into one second of video (25 is a common number). So now we have 25 of those 480x384 frames. If we now use one bit to store one pixel we need 25 bits for the job.

To complete the illustration, say we take our 480x384 frame 25 times per second, for a total of 2 hours (7200 seconds). If we used one bit per pixel, we used 25 pixels for 7200 seconds, which gives 180,000 bits per pixel in the movie. Multiply that by the number of pixels in one frame and we find 33,177,600,000 bits (30 gigabits, or 3.8 gigabytes).

Where does the bitrate come in? The bitrate is bits per seconds, so now that we have the number of bits, we divide by the number of seconds and find 4,608,000 (4500 kbps). If it isn't clear yet why the bitrate isn't a useful measure, it soon will be.

Getting it right

To formalize our deductions we draw up some equations. First, as we said, bpp is bits per pixel:

bpp = bits / pixel

To calculate the size (in bits) of the movie we took the bpp, the framerate (frames per second), the length (in seconds) and the dimensions (in pixels).

size = bpp * fps * length * width * height

And the bitrate (bits per second) is now the size divided by the length of the movie:

bitrate = size / length

We can also solve this equation for size, and substitute the formula into the previous one, which gives a different equation for the bitrate:

bitrate = bpp * fps * width * height

It should now be clear what the problem is with the bitrate as a measure of quality. It not only encapsulates the bpp, it also subsumes the dimensions and the frame rate of the movie!

Still not clear? Let's solve the equation for bpp.

bpp = bitrate / (width * height * fps)

Now let's assume we use the bitrate as a measure of quality. As mentioned, undvd up to version 0.3.x sets a constant bitrate of 900kbps (921,600 bits). Let's try that on a couple of examples.

0.200 = 921600 / (480 * 384 * 25)

When we plug the bitrate into the equation we find the bpp is 0.2.

But now suppose the user does not want any video scaling and the dimensions of the output video are 720x576.

0.088 = 921600 / (720 * 576 * 25)

Now we have less than half the space to store one pixel than we did in the first case, because we have more than twice the number of pixels in every frame. Clearly, the same number of bits to store this movie, spread across more pixels, will allow less for each pixel, and thus lower the quality.

Therefore, the bitrate needs to vary depending on the dimensions and the length of the movie. It is thus a function, not a constant! On the other hand, bpp is a constant, and so if we want a measure of quality we should use that instead.

Getting practical

The equations are easy. The question at hand is what value to set for the bpp. As shown in the example, 900kbps at the dimensions frequently used gives about 0.2 bpp, which is known to work well. Thanassis Tsiodras suggests that 0.2 bpp is enough for xvid, while h264 can be encoded at just 0.125 bpp. But considering that undvd is a one-size-fits-all solution, and therefore should encode any video well (even at the cost of filesize in cases where it's unnecessary), I would rather overshoot the target size a bit and play it safe. Therefore, based on my results, the default bpp is set to 0.195. In case of two pass encoding, we trade processing time for filesize, and the value is set to 0.150. For xvid the corresponding values are 0.250 and 0.200.

As before, these defaults can be overridden by setting the output filesize.

The best thing about this new functionality is that it doesn't invalidate any existing assumptions. For a default rip the result will be the same as always, which is supposed to be very good. But now it scales to custom video dimensions as well.

Something missing?

Pleased as I was that undvd now has a mathematical underpinning for deciding the bitrate, I was still not quite satisfied. It's nice and all that we now use a constant to determine the quality, but what is bpp anyway? How do we relate to it? And how do we know what a good value of bpp is?

To make this more tangible, I decided it can't just be a value in a calculation, it has to be made visible. undvd now has a "dry run" option -D, which shows all the parameters of the video to be encoded. The bpp value is highlighted, because that is our measure of quality. This image shows title 01 is chosen for ripping. The dimensions will be scaled to 480x384, the frame rate is 25 fps, the length is 148 minutes, the bpp is .195, the bitrate is thus calculated to 877kbps, we are using one pass encoding, and the h264 codec. The output size is estimated at 1122mb.

Short of showing the bpp for a title we are about to encode, it would also be useful to inspect videos we have encoded in the past, wouldn't it? That would give us an idea of what to expect.

For this there is a new tool vidstat, which displays the same information about any file or dvd title (much like stat displays information about a file on the filesystem) .

Here we see the first 60 seconds of title 01 (from above) being ripped. Then we run vidstat on the output file to examine it. Here we see that mencoder decided to use 809kbps instead of 877 as it was instructed to.

The bpp value is highlighted in yellow, red or green depending on whether undvd thinks it's unnecessarily high (above the single pass bpp default) or low (below the two pass bpp default), or just right (within the two).