Since Maxim Stepin created the HQx interpolation algorithm more than a decade ago, it has been the favored real-time interpolation filter for the emulation scene. The way it works is it looks at each pixel and then compares its color to that of the 8 surrounding adjacent pixels. If it finds a match, the filter then compares the resulting pattern with a predefined lookup table to guess what the original pattern was trying to represent.
For example, if we take a pattern like this:
and scale it up via nearest neighbor--that is, a straight upscale with no interpolation--you end up with this checkerboard pattern:
But, if you use HQ2x, you end up with this:
The algorithm guesses that the original pattern was trying to represent a diagonal line rather than a checkerboard pattern, so it fills in the gaps to compensate.
Recently, a Brazilian programmer by the name of Hyllian (aka Jararaca) developed a new algorithm that actually improves on HQx, known as xBR (stands for "a filter that scales By Rules").
xBR works much the same way as HQx insofar as it is based on pattern recognition, and it would upscale the above pattern with the same result. However, it goes further than HQx by using a 2-stage set of interpolation rules, which better handle more complex patterns such as antialiased lines and curves.
You can read more about Hyllian's algorithm here.
Lets take a look at how they compare on a real-world example (HQ2x on the left, 2xBR on the right; click to embiggen):
As you can see, 2xBR does a much better job on smoothing curves without getting chunky (see Yoshi's nose and the dragon coin). It also does a better job on the 'eyes' of the block, which is represented as a diagonal line with 2xBR compared with the series-of-squares look with HQ2x.
Here's another comparison, using Earthworm Jim's title screen:
And here's a third comparison, using the title screen to Earthworm Jim 2:
HQ2x actually does a slightly better job at getting a smooth gradient around the highlight in Jim's eye, but the rest of the image is a mess. xBR has smoother, straighter lines at every color transition.
Additionally, the xBR algorithm scales to higher scale factors much more easily than the HQx algorithm, making 3-, 4-, 5- and higher versions faster and more effective.
At very high scale factors (5 and higher), the xBR algorithm can obliterate some small details, such as pupils in eyes, dots, and so on, so Hyllian introduced some additional calculation to compensate (5xBR-v3.5a on the left [uncompensated] vs 5xBR-v3.5b on the right [compensated]):
Of course, this compensation comes with its own drawbacks and false-positives, so which version works better varies on a game-by-game basis.
UPDATE: Hyllian has made a third variant that is even more cautious. Here's an animated GIF comparing the way each variant handles text:
this vectorization method that recently made the rounds. xBR manages to maintain detail a bit better than the vectorizer, and it can actually operate in real-time, unlike the vectorizer.
You can download these shaders from my Mediafire repo (most are available in either XML/GLSL or Cg format, both of which are compatible with SSNES). UPDATE: KrossX ported 2xBR-v3.5a to ePSXe format and SimoneT ported 5xBR-v3.5a.
UPDATE: New Cg version of 5x variant. Runs approx. 25% faster. :)
UPDATE: new XML versions of 5xBR-v3.7. This package includes 3 variants (a, b and c), as well as the A-variant+scanlines.
UPDATE: Hyllian has been working on a new version that analyzes an image frame by frame and dynamically decides whether to apply xBR smoothing or Reverse-Anti-aliasing to produce the best picture. It handles text better than any filter/shader I've encountered, and it also excels at digitized, prerendered images and backgrounds. Here's a shot of it with Final Fantasy VI on GBA:
You can download this shader here.
UPDATE (4/19/2013): Another great update from Hyllian, this time adding 3 levels of analysis. This version runs a bit slower in my experience (unsurprisingly), but it now handles jagged edges that earlier versions simply couldn't detect, due to their 2-level analysis pattern. Compare this shot with the ones at the top of the post:
You can download a Cg shader of this new version here, or a 3x scale Kega Fusion plugin here.