Image scaling
Encyclopedia
Digital image
A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
. Scaling is a non-trivial process that involves a trade-off between efficiency, smoothness and sharpness. As the size of an image is increased, so the pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
s which comprise the image become increasingly visible, making the image appear "soft". Conversely, reducing an image will tend to enhance its smoothness and apparent sharpness.
Apart from fitting a smaller display area, image size is most commonly decreased (or subsampled or downsampled) in order to produce thumbnails. Enlarging an image (upsampling or interpolating
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
) is generally common for making smaller imagery fit a bigger screen in fullscreen mode, for example. In “zooming” an image, it is not possible to discover any more information in the image than already exists, and image quality inevitably suffers. However, there are several methods of increasing the number of pixels that an image contains, which evens out the appearance of the original pixels.
Scaling methods
An image size can be changed in several ways. Consider doubling the size of the following image:
The easiest way of doubling its size is nearest-neighbor interpolation, replacing every pixel with four pixels of the same color:
The resulting image is larger than the original, and preserves all the original detail, but has undesirable jaggedness
Jaggies
"Jaggies" is the informal name for artifacts in raster images, most frequently from aliasing, which in turn is often caused by non-linear mixing effects producing high-frequency components and/or missing or poor anti-aliasing filtering prior to sampling....
. The diagonal lines of the W, for example, now show the characteristic "stairway" shape.
Other scaling methods are better at preserving smooth contours in the image. For example, bilinear interpolation
Bilinear interpolation
In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The interpolated function should not use the term of x^2 or y^2, but x y, which is the bilinear form of x and y.The key idea is to perform linear...
produces the following result:
Linear (or bilinear, in two dimensions) interpolation is typically better than the nearest-neighbor system for changing the size of an image, but causes some undesirable softening of details and can still be somewhat jagged. Better scaling methods include bicubic interpolation
Bicubic interpolation
In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation...
:
For magnifying computer graphics with low resolution and/or few colors (usually from 2 to 256 colors) the best results will be achieved by hqx
Hqx
In image processing, hqx is one of the pixel art scaling algorithms developed by Maxim Stepin, used in emulators such as Nestopia, bsnes, ZSNES, Snes9x, FCE Ultra and many more. There are 3 hqx filters: hq2x, hq3x, and hq4x, which magnify by factor of 2, 3, and 4 respectively...
or other pixel art scaling algorithms. These produce sharp edges and maintain high level of detail. hq2x:
For scaling photos (and raster images with lots of colors) see also anti-aliasing algorithms called supersampling
Supersampling
Supersampling is an antialiasing technique, the process of eliminating jagged and pixelated edges . It is a method of smoothing images rendered in computer games or other programs that generate imagery.-Overview:...
.
Algorithms
Two standard scaling algorithms are bilinearBilinear filtering
Bilinear filtering is a texture filtering method used to smooth textures when displayed larger or smaller than they actually are.Most of the time, when drawing a textured shape on the screen, the texture is not displayed exactly as it is stored, without any distortion...
and bicubic interpolation
Bicubic interpolation
In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation...
. Filters like these work by interpolating pixel color values, introducing a continuous transition into the output even where the original material has discrete transitions. Although this is desirable for continuous-tone images, some algorithms reduce contrast
Display contrast
Contrast in visual perception is the difference in appearance of two or more parts of a field seen simultaneously or successively ....
(sharp edges) in a way that may be undesirable for line art.
Nearest-neighbor interpolation preserves these sharp edges, but it increases aliasing
Aliasing
In signal processing and related disciplines, aliasing refers to an effect that causes different signals to become indistinguishable when sampled...
(or jaggies
Jaggies
"Jaggies" is the informal name for artifacts in raster images, most frequently from aliasing, which in turn is often caused by non-linear mixing effects producing high-frequency components and/or missing or poor anti-aliasing filtering prior to sampling....
; where diagonal lines and curves appear pixelated). Several approaches have been developed that attempt to optimize for bitmap art by interpolating areas of continuous tone, preserve the sharpness of horizontal and vertical lines and smooth all other curves.
Efficiency
Since a typical application of this technology is improving the appearance of fourth-generationHistory of video game consoles (fourth generation)
In the history of computer and video games, the fourth generation began on October 30, 1987 with the Japanese release of Nippon Electric Company's PC Engine...
and earlier video games on arcade
Arcade emulator
An arcade emulator is a program that emulates one or more arcade games on a different computer, such as a PC.The first known arcade emulation available publicly was the Williams Digital Arcade series from Digital Eclipse Software, released for the Macintosh in 1994. This series featured the...
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.
EPX/Scale2×/AdvMAME2×
Eric's Pixel Expansion (EPX) is an algorithm developed by Eric Johnston at LucasArtsLucasArts
LucasArts Entertainment Company, LLC is an American video game developer and publisher. The company was once famous for its innovative line of graphic adventure games, the critical and commercial success of which peaked in the mid 1990s...
around 1992, when porting the SCUMM
SCUMM
Script Creation Utility for Maniac Mansion is a scripting language developed at LucasArts to ease development of the graphical adventure game Maniac Mansion....
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.
The algorithm works as follows:
A --\ 1 2
C P B --/ 3 4
D
IF CA => 1=A
B => 2=B
IF A
IF BD => 4=D
C => 3=C
IF D
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 CA AND C!=D AND A!=B => 1=A
B AND A!=C AND B!=D => 2=B
IF A
IF BD AND B!=A AND D!=C => 4=D
C AND D!=B AND C!=A => 3=C
IF D
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 DB AND D!=H AND B!=F => 1=D
B AND D!=H AND B!=F AND E!=C) OR (B
IF (DF AND B!=D AND F!=H AND E!=A) => 2=B
F AND B!=D AND F!=H => 3=F
IF B
IF (HD 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 (BF AND B!=D AND F!=H AND E!=I) OR (F
H AND F!=B AND H!=D AND E!=C) => 6=F
IF HD AND H!=F AND D!=B => 7=D
H AND F!=B AND H!=D AND E!=G) OR (H
IF (FD AND H!=F AND D!=B AND E!=I) => 8=H
H AND F!=B AND H!=D => 9=F
IF F
Eagle
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 VS
T => 1=S
| IF TU
W => 2=U
| IF VX
Y => 3=X
| IF WZ
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 emulatorEmulator
In computing, an emulator is hardware or software or both that duplicates the functions of a first computer system in a different second computer system, so that the behavior of the second system closely resembles the behavior of the first system...
s, and it has remained fairly popular in this niche. Many of the most popular emulators, including ZSNES
ZSNES
ZSNES is a free software SNES emulator written mostly in x86 assembly with official ports for Linux, MS-DOS, Mac OS X, Windows and an unofficial port for Xbox.-Background:...
and VisualBoyAdvance
VisualBoyAdvance
VisualBoyAdvance is a free emulator of the Game Boy, Game Boy Color, and Game Boy Advance handheld game consoles....
, offer this scaling algorithm as a feature.
Since Kreed released the source code under the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
, 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 that 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 ±0.5, ±1, or ±2 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.hqnx was initially created for the Super Nintendo emulator ZSNES
ZSNES
ZSNES is a free software SNES emulator written mostly in x86 assembly with official ports for Linux, MS-DOS, Mac OS X, Windows and an unofficial port for Xbox.-Background:...
.
The author of bsnes
Bsnes
bsnes is a free SNES emulator for Linux, Mac OS X, and Windows which aims to emulate the original SNES hardware as accurately as possible. As such, bsnes is a low-level emulator.-Background:...
has released a space-efficient implementation of hq2x to the public domain.
RotSprite
RotSprite is a scaling and rotation algorithm for sprites developed by Xenowhirl. It produces far fewer artifacts than nearest-neighbor rotation algorithms, and like EPX, it does not introduce new colors into the image (unlike most interpolation systems).The algorithm first scales the image to 8 times its original size with a modified Scale2× algorithm which treats similar (rather than identical) pixels as matches. It then calculates what rotation offset to use by favoring sampled points which are not boundary pixels. Next, the rotated image is created with a nearest-neighbor scaling and rotation algorithm that simultaneously shrinks the big image back to its original size and rotates the image. Finally, overlooked single-pixel details are restored if the corresponding pixel in the source image is different and the destination pixel has three identical neighbors.
Applications to arcade and console emulators
On sufficiently fast hardware, these algorithms are suitable for gaming and other real-time image processing software. 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 engineGame engine
A game engine is a system designed for the creation and development of video games. There are many game engines that are designed to work on video game consoles and personal computers...
s and game engine recreations like AdvanceMAME, DOSBox
DOSBox
DOSBox is emulator software that emulates an IBM PC compatible computer running MS-DOS. It is intended especially for use with old PC games. DOSBox is free software....
, and ScummVM
ScummVM
ScummVM is a collection of game engine recreations. Originally designed to play LucasArts adventure games that use the SCUMM system , it now also supports a variety of non-SCUMM games by companies like Revolution Software and Adventure Soft. It was originally written by Ludvig Strigeus...
. They have gained wide recognition with gamers, with whom these technologies have encouraged a revival of '80s and '90s gaming experiences.
Such filters are currently used in commercial emulators on Xbox Live
Xbox Live
Xbox Live is an online multiplayer gaming and digital media delivery service created and operated by Microsoft Corporation. It is currently the only online gaming service on consoles that charges users a fee to play multiplayer gaming. It was first made available to the Xbox system in 2002...
, Virtual Console
Virtual console
A virtual console – also known as a virtual terminal – is a conceptual combination of the keyboard and display for a computer user interface. It is a feature of some operating systems such as UnixWare, Linux, and BSD, in which the system console of the computer can be used to switch between...
, and PSN to allow classic low resolution games to be more visually appealing on modern HD
High-definition video
High-definition video or HD video refers to any video system of higher resolution than standard-definition video, and most commonly involves display resolutions of 1,280×720 pixels or 1,920×1,080 pixels...
displays. Recently released games that incorporate these filters include Sonic's Ultimate Genesis Collection
Sonic's Ultimate Genesis Collection
Sonic's Ultimate Genesis Collection, known as the Sega Mega Drive Ultimate Collection in PAL regions, is a compilation of video games developed by Backbone Entertainment for the Xbox 360 and PlayStation 3 consoles...
, Castlevania: The Dracula X Chronicles, Castlevania: Symphony of the Night
Castlevania: Symphony of the Night
Castlevania: Symphony of the Night, known in Japan as , is an action-adventure game developed and published by Konami in 1997. It is the 14th installment of the Castlevania series, the first installment released for the PlayStation, and a direct sequel to Castlevania: Rondo of Blood.Symphony of the...
, and Akumajō Dracula X Chi no Rondo.
See also
- Bicubic interpolationBicubic interpolationIn mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or nearest-neighbor interpolation...
- Bilinear interpolationBilinear interpolationIn mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The interpolated function should not use the term of x^2 or y^2, but x y, which is the bilinear form of x and y.The key idea is to perform linear...
- Lanczos resamplingLanczos resamplingLanczos resampling is an interpolation method used to compute new values for sampled data. It is often used in multivariate interpolation, for example for image scaling , but can be used for any other digital signal...
- Spline interpolationSpline interpolationIn the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. Spline interpolation is preferred over polynomial interpolation because the interpolation error can be made small even...
- Seam carvingSeam carvingSeam carving , is an algorithm for image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Labs , and Ariel Shamir, of the Interdisciplinary Center and MERL...
- SupersamplingSupersamplingSupersampling is an antialiasing technique, the process of eliminating jagged and pixelated edges . It is a method of smoothing images rendered in computer games or other programs that generate imagery.-Overview:...