Pixel art scaling algorithms

It has been suggested that this article or section be merged into Image scaling. (Discuss)

An image scaled with nearest-neighbor scaling (left) and 2×SaI scaling (right).

Pixel art scaling algorithms are image scaling algorithms specifically designed to upsample (enlarge) low-resolution pixel and line art that contains thin lines, solid areas of colour rather than gradient fills or shading, and has not been anti-aliased.

Motivation

Two standard scaling algorithms are bilinear and bicubic interpolation. Since they work by interpolating pixel colour values, and usually set each pixel to a value interpolated between four input pixel values, they introduce some blur into the output (a form of box blur). Although this is acceptable for continuous-tone images, it destroys contrast (sharp edges) and is often seen as ruining the appearance of line art.

Nearest neighbour interpolation preserves these sharp edges, but it introduces aliasing (or jaggies; where diagonal lines and curves appear pixelated). Thus, the ideal algorithm for enlarging line art would be one that would interpolate areas of continuous tone, preserve the sharpness of orthogonal lines and smooth (ideally with anti-aliasing) diagonal lines and curves. Several attempts have been made to accomplish this.

Efficiency

Since a typical application of this technology is improving the appearance of fourth-generation and earlier video games on arcade and console emulators, many are designed to run in real time for sufficiently small input images.

Many work only on specific scale factors: 2× is the most common, with 3× and 4× also present.

Algorithms

EPX/Scale2×/AdvMAME2×

Eric's Pixel Expansion (EPX) is an algorithm developed by Eric Johnston at LucasArts around 1992^[1], when porting the SCUMM engine games from the IBM PC (which ran at 320×200×256 colors) to the early color Macintosh computers, which ran at more or less double that resolution.^[2] The algorithm works as follows:

  A    --\ 1 2
C P B  --/ 3 4
  D 
 IF C==A => 1=A
 IF A==B => 2=B
 IF B==D => 4=D
 IF D==C => 3=C
 IF of A, B, C, D, 3 or more are identical: 1=2=3=4=P

Later implementations of this same algorithm (as AdvMAME2× and Scale2×, developed around 2001) have a slightly more efficient but functionally identical implementation:

  A    --\ 1 2
C P B  --/ 3 4
  D 
 1=P; 2=P; 3=P; 4=P;
 IF C==A AND C!=D AND A!=B => 1=A
 IF A==B AND A!=C AND B!=D => 2=B
 IF B==D AND B!=A AND D!=C => 4=D
 IF D==C AND D!=B AND C!=A => 3=C

The AdvMAME4×/Scale4× algorithm is just EPX applied twice to get 4× resolution.

Scale3×/AdvMAME3×

The AdvMAME3×/Scale3× algorithm is not the same as EPX, but is similar in a mathematical sense.

A B C --\  1 2 3
D E F    > 4 5 6
G H I --/  7 8 9
 1=E; 2=E; 3=E; 4=E; 5=E; 6=E; 7=E; 8=E; 9=E;
 IF D==B AND D!=H AND B!=F => 1=D
 IF (D==B AND D!=H AND B!=F AND E!=C) OR (B==F AND B!=D AND F!=H AND E!=A) 2=B
 IF B==F AND B!=D AND F!=H => 3=F
 IF (H==D AND H!=F AND D!=B AND E!=A) OR (D==B AND D!=H AND B!=F AND E!=G) 4=D
 5=E
 IF (B==F AND B!=D AND F!=H AND E!=I) OR (F==H AND F!=B AND H!=D AND E!=C) 6=F
 IF H==D AND H!=F AND D!=B => 7=D
 IF (F==H AND F!=B AND H!=D AND E!=G) OR (H==D AND H!=F AND D!=B AND E!=I) 8=H
 IF F==H AND F!=B AND H!=D => 9=F

Eagle

Eagle works as follows: for every in pixel we will generate 4 out pixels, first, set all 4 to the colour of the in pixel we are currently scaling (like nearest neighbor), next lets look at the pixels up and to the left, if they are the same colour as each other set the top left pixel to that colour, continue doing the same for all four pixels, and then move to the next one.^[3]

Assume an input matrix of 3×3 pixels where the center most pixel is the pixel to be scaled, and an output matrix of 2×2 pixels (i.e., the scaled pixel)

first:        |Then 
. . . --\ CC  |S T U  --\ 1 2
. C . --/ CC  |V C W  --/ 3 4
. . .         |X Y Z
              | IF V==S==T => 1=S
              | IF T==U==W => 2=U
              | IF V==X==Y => 3=X
              | IF W==Z==Y => 4=Z

Thus if we have a black pixel on a white background it will vanish. This is a bug in the Eagle algorithm, but is solved by its successors such as 2xSaI and HQ3x.

2×SaI

2×SaI, short for 2× Scale and Interpolation engine, was inspired by Eagle. It was designed by Derek Liauw Kie Fa, also known as Kreed, primarily for use in console and computer emulators, and it has remained fairly popular in this niche. Many of the most popular emulators, including ZSNES and VisualBoyAdvance, offer this scaling algorithm as a feature.

Since Kreed released^[4] the source code under the GNU General Public License, it is freely available to anyone wishing to utilize it in a project released under that license. Developers wishing to use it in a non-GPL project would be required to rewrite the algorithm without using any of Kreed's existing code.

Super 2×SaI and Super Eagle

Several slightly different versions of the scaling algorithm are available, and these are often referred to as Super 2×SaI, 2×SaI, and Super Eagle. Super Eagle which is also written by Kreed, is similar to the 2×SaI engine, but does more blending. Super 2×SaI which is also written by Kreed is a filter which smooths the graphics, but it blends more than the Super Eagle engine.

hqnx family

Maxim Stepin's hq2x, hq3x and hq4x are for scale factors of 2:1, 3:1 and 4:1 respectively. Each works by comparing the colour value of each pixel to those of its eight immediate neighbours, marking the neighbours as close or distant, and using a pregenerated lookup table to find the proper proportion of input pixels' values for each of the 4, 9 or 16 corresponding output pixels. The hq3x family will perfectly smooth any diagonal line whose slope is ±1:2, ±1:1 or ±2:1 and which is not anti-aliased in the input; one with any other slope will alternate between two slopes in the output. It will also smooth very tight curves. Unlike 2xSaI, it anti-aliases the output.^[5]

Image enlarged 3× with the nearest neighbor interpolation

Image enlarged in size by 3× with hq3x algorithm

hqnx was initially created for the Super Nintendo emulator ZSNES.

Applications to arcade and console emulators

On sufficiently fast hardware, these algorithms allow resizing suitable for real-time applications such as games. These highly optimized algorithms provide sharp, crisp graphics while minimizing blur. Scaling art algorithms have been implemented in a wide range of emulators, 2D game engines and game engine recreations, for example in AdvanceMAME, DOSBox, and ScummVM. They have gained wide recognition with gamers, with whom these technologies have encouraged a revival of the gaming experiences of the '80s and '90s.

Nowadays such filters are used in commercial emulators on Xbox Live, Virtual Console, and PSN to allow classic low resolution games to be more visually appealing on modern HD displays. Retail games that used filters recently are the Sonic's Ultimate Genesis Collection, Castlevania: The Dracula X Chronicles, Castlevania: Symphony of the Night, and Akumajō Dracula X Chi no Rondo emulation.

References

External links

• Updated version of 2xSaI algorithm with 32bpp support
• Scale2x homepage
• hq3x project (Windows utilities available)