undvd gets smarter scaling

March 8th, 2008

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.

:: random entries in this category ::