hqx

In image processing, hqx ("hq" stands for "high quality" and "x" stands for magnification) is one of the pixel art scaling algorithms developed by Maxim Stepin, used in emulators such as Nestopia, FCEUX, higan, Snes9x, ZSNES and many more. There are three hqx filters: hq2x, hq3x, and hq4x, which magnify by factor of 2, 3, and 4 respectively. For other magnification factors, this filter is used with nearest-neighbor scaling .

Image enlarged 3× with the nearest-neighbor interpolation 
Image enlarged by 3× with hq3x algorithm 

Algorithm

First, the color of each of the 8 pixels around the source pixel is compared to the color of the source pixel. Shapes are detected by checking for pixels of similar color according to a threshold. This gives total of 28 = 256 combinations of similar or dissimilar neighbors. To expand the single pixel into a 2×2, 3×3, or 4×4 block of pixels, the arrangement of neighbors is looked up in a predefined table which contains the necessary interpolation patterns.

The interpolation data in the lookup tables are constrained by the requirement that continuity of line segments must be preserved, while optimizing for smoothness. Generating these lookup tables is relatively slow, and is the major source of complexity in the algorithm: the render stage is very simple and fast, and designed to be capable of being performed in real time.

A description from the original author

A brief description of the implementation taken from the original hqx Library README ( see original hqx project at the external links section )

The first step is an analysis of the 3x3 area of the source pixel. At first, we calculate the color difference between the central pixel and its 8 nearest neighbors. Then that difference is compared to a predefined threshold, and these pixels are sorted into two categories: "close" and "distant" colored. There are 8 neighbors, so we are getting 256 possible combinations.
For the next step, which is filtering, a lookup table with 256 entries is used, one entry per each combination of close/distant colored neighbors. Each entry describes how to mix the colors of the source pixels from 3x3 area to get interpolated pixels of the filtered image.
The present implementation is using YUV color space to calculate color differences, with more tolerance on Y (brightness) component, then on color components U and V. That color space conversion is quite easy to implement if the format of the source image is 16 bit per pixel, using a simple lookup table. It is also possible to calculate the color differences and compare them to a threshold very fast, using MMX instructions.
Creating a lookup table was the most difficult part - for each combination the most probable vector representation of the area has to be determined, with the idea of edges between the different colored areas of the image to be preserved, with the edge direction to be as close to a correct one as possible. That vector representation is then rasterised with higher (3x) resolution using anti-aliasing, and the result is stored in the lookup table.
The filter was not designed for photographs, but for images with clear sharp edges, like line graphics or cartoon sprites. It was also designed to be fast enough to process 256x256 images in real-time.

See also


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.