Current version

v1.10.4 (stable)

Navigation

Main page
Archived news
Downloads
Documentation
   Capture
   Compiling
   Processing
   Crashes
Features
Filters
Plugin SDK
Knowledge base
Contact info
 
Other projects
   Altirra

Archives

Blog Archive

Introducing "warp resize"

In an earlier blog entry on video shaders I introduced an algorithm called warpedge as an example. It's a hybrid warpsharp+resize algorithm that attempts to make edges as crisp as possible. The algorithm's output has proven interesting enough that I made a VirtualDub video filter out of it:

Warp resize, version 1.1
Warp resize, version 1.1 source code

Only works when enlarging a video, and requires a lot of CPU power. Read on for the algorithm description.

The basic "warp sharp" algorithm

Warp sharp is the name of an algorithm that I originally found coded as a filter for an image editing application called "The GIMP." It's based on the idea that if you can identify the edges in an image, you can warp the image to shrink the edges and thus make them appear sharper. I don't remember how the original code worked, but here's one way to implement such an algorithm:

Problems with warp sharp

The first problem with warp sharp is that the length of the displacement map vectors is dependent upon the height of the bump map, which is in turn dependent upon the contrast of the original image. This means that the amount of narrowing of edges varies with local contrast, which produces uneven edges.

A second problem has to do with the warp. If the warp is done using straight interpolation, the algorithm will never output a pixel that is not in the infinitely interpolated version of the original image. In practice this means you can get "bumpiness" in edges the warped image, since the warp interpolator doesn't do edge-directed interpolation. You can often see this in near-horizontal or near-vertical lines, where the interpolator creates gray pixels when the line straddles a scan line boundary. Unfortunately, while there are edge-directed interpolation algorithms, they usually don't produce continuous output. For example, the Xin-Li New Edge Directed Interpolation (NEDI) algorithm only produces a rigid 2:1 enlargement. This doesn't help with a displacement-map based warp, which requires fine perturbations in the sampling location.

A third problem is that since warp sharp essentially narrows transition regions, it has a tendency to crystallize images into discrete regions such that it resembles a Voronoi diagram. Blurring the bump map decreases the filter's sensitivity to noise and helps this somewhat.

The warp resize algorithm

To solve the luminance sensitivity, warp resize normalizes the gradient vectors produced in the second pass. This has the downsides of amplifying noise and failing on (0,0) vectors, so the normalization scale factor is lerped toward 1.0 as the vector becomes very short. Also, the gradient vectors are computed on the full-size version of the image, so that the normalization occurs after resampling. Otherwise, the resampling operation would denormalize gradient vectors, which would introduce artifacts into the warp on original pixel boundaries.

The issue with the warp interpolation is corrected using the following ugly hack: We know that the problem becomes worst between pixel boundaries, where the interpolator is "most inaccurate" with regard to edges. So what we do is compute the difference between the warped pixel and the interpolated pixel, and re-add some of that difference to emphasize it. The difference is greater where the slope of the edge is higher, and thus this tends to flatten out edges and make borders crisper.

Throw in a liberal amount of high-powered, slightly-expensive interpolation to taste.

Thus, the algorithm used by the CPU version of the algorithm is as follows:

The source code is a bit of a mess because it interleaves the first six passes together as a bank of row filters in order to increase cache locality. If you are looking into reimplementing the algorithm, I highly recommend either working from the description above or starting with the HLSL code for the original GPU filter, which is much easier to understand.

As you might guess, the warp resize algorithm is better suited to cartoon-style imagery than natural images, although it can help on the latter too. There is also an issue with the filter sometime introducing a gap in the center of edges, which splits edges into two; I haven't figured exactly what causes this, but it is sometimes caused by the displacement vectors being too strong. What's weird is that the effect is sometimes very limited, such as a hair-width gap being seen in a 20-pixel wide edge after 4x enlargement. I think this may have to do with the gradient vector swinging very close to (0,0) as the current pixel position crosses the true center of an edge, at which point the filter can't do anything to the image.

The CPU version is approximately one-sixth of the speed of the GPU version, even with MMX optimizations. This is comparing a Pentium M 1.86GHz against a GeForce Go 6800, so it's a little bit unbalanced; a Pentium 4 or Athlon 64 would probably narrow this gap a bit. Also, the GPU version does nasty hacks with bilinear texture sampling hardware to get the final three passes running fast enough and with a low enough instruction count to fit in pixel shader 2.0 limits, so its accuracy suffers compared to the CPU version. If you look closely, you can see some speckling and fine checkerboard patterns that aren't present in the output of the CPU filter. Increasing the precision of the GPU filter to match would narrow the gap further.

Comments

This blog was originally open for comments when this entry was first posted, but was later closed and then removed due to spam and after a migration away from the original blog software. Unfortunately, it would have been a lot of work to reformat the comments to republish them. The author thanks everyone who posted comments and added to the discussion.