Editing Hqx (algorithm)

{{About|[[image scaling]] filter|.hqx files|BinHex}}

{{lowercase title}}

{{Infobox software
| title = hqx
| developer = Maxim Stepin
| released = {{Start date and age|2003|7|25|df=no}}
| latest release version = 1.1
| latest release date = {{Start date and age|2003|9|29|df=no}}
| programming language = [[C++]]
| genre = [[Pixel-art scaling algorithm]]
| license = [[LGPL 2|LGPL 2.1]]
| website = {{URL|https://www.gimp.org/|gimp.org}}
}}

'''hqx''' ("high quality scale") is a set of 3 image upscaling algorithms developed by Maxim Stepin. The algorithms are '''hq2x''', '''hq3x''', and '''hq4x''', which magnify by a factor of 2, 3, and 4 respectively. It was initially created in 2003 for the Super NES emulator [[ZSNES]],<ref>{{Cite web |date=2013-12-05 |title=HiEnd3D |url=http://www.hiend3d.com/hq2x.html |access-date=2023-02-12 |archive-url=https://web.archive.org/web/20131205091805/http://www.hiend3d.com/hq2x.html |archive-date=2013-12-05 }}</ref> and is used in [[emulator]]s such as [[Nestopia]], [[FCEUX|F. CEUX]]Snes9x., and [[Snes9x]].

==Algorithm==

The source image's pixels are iterated through from top-left to bottom-right. For each pixel, the surrounding 8 pixels are compared to the color of the source pixel. Shapes are detected by checking for [[pixel]]s of similar color according to a [[YUV]] threshold. hqx uses the [[YUV color space]] to calculate color differences, so that differences in brightness are weighted higher in order to mimic human perception.<ref name="grom358">{{cite journal |last1=Zemek |first1=Cameron |date=6 May 2019 |title=hqx README (grom358 port) |url=https://github.com/grom358/hqx/blob/master/README |journal=Github}}</ref> This gives a total of <math>2^8 = 256</math> 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.<ref name="grom358"/>

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 256-filter 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 on a [[MMX (instruction set)|MMX]]-capable CPU.<ref name="grom358"/>

In the source code, the interpolation data is represented as preprocessor [[Macro (computer science)|macros]] to be inserted into [[switch case]] statements, and there is no [[source code]] leading to the generation of a lookup table. The author describes the process of generating a look-up table as:<ref name="grom358"/>
<blockquote>... 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.</blockquote>

{{Gallery
|align=center
|width=350
|File:Test nn.png
|Image enlarged 3× with [[nearest-neighbor interpolation]]
|File:Test hq3x.png
|Image enlarged by 3× with hq3x
}}

==Implementations==

* The original algorithm has been ported to [[DevIL]] (but kept in the C language).<ref name="grom358"/>
* Ports to Java and C# languages are available. These implementations expand the macros.<ref>{{cite web |last1=Garcia |first1=Edu |title=hqx-java |url=https://github.com/Arcnor/hqx-java/ |website=GitHub |date=6 March 2019}}</ref><ref>{{cite web |author1=Tamschi |title=hqxsharp |url=https://github.com/Tamschi/hqxSharp |website=GitHub}}</ref>
* A [[C++]] port by byuu, the author of [[bsnes]], which encodes the LUT in a space-efficient way. Byuu exploited the symmetry of patterns to make such an encoding, and wrote some notes on interpreting the original look up tables.<ref name=byuu>Byuu. [http://nesdev.parodius.com/bbs/viewtopic.php?p=82770#82770 Release announcement] {{Webarchive|url=https://web.archive.org/web/20110930163308/http://nesdev.parodius.com/bbs/viewtopic.php?p=82770#82770 |date=2011-09-30 }} Accessed 2011-08-14. [https://pastebin.com/YXpmqvW5 public domain implementation released on pastebin]</ref>
* [[libretro]] implements two families of shaders in Slang/[[HLSL]], [[GLSL]], and [[Cg (programming language)|Cg]]:
** The '''hqx''' family, which is true hqx.<ref>{{cite web |title=hqx |url=http://docs.libretro.com/shader/hqx/ |website=Libretro Docs}}</ref> As it runs on modern [[GPU]]s, lookup tables are substituted by textures.<ref name="hqx_inc">{{cite web |last1=Blok |first1=Jules |title=hqx-shader |url=https://github.com/Armada651/hqx-shader |website=GitHub |date=12 April 2019}}</ref> The textures were generated by interrogating a modified version of hqx for its switch/case.
** The '''scalehq''' family, which is frequently confused with hqx. It is not related to hqx, but is rather a generic upscaling-smoothing algorithm.<ref>{{cite web |last1=K |first1=Hunter |title=Filthy Pants: A Computer Blog: True Hq2x Shader Comparison With xBR |url=http://filthypants.blogspot.com/2014/06/true-hq2x-shader-comparison-with-xbr.html |website=Filthy Pants |date=20 June 2014}}</ref>
* hqx has also been implemented in [[ffmpeg]] for upscaling images and videos 2x, 3x, or 4x. An account of the production of the translation for ffmpeg is [http://blog.pkh.me/p/19-butchering-hqx-scaling-filters.html here] and usage may be something like: <code>ffmpeg -i %1 -filter_complex hqx=2 hqx2-%1</code> to produce a 2x image or video.

==See also==
* [[Image scaling]]
* [[Pixel-art scaling algorithms]]
* [[Pixel art]]

==References==
{{Reflist}}

==External links==
* [https://web.archive.org/web/20131205091805/http://www.hiend3d.com/hq2x.html hq2x], [https://web.archive.org/web/20131114143602/http://www.hiend3d.com/hq3x.html hq3x], and [https://web.archive.org/web/20131216092117/http://www.hiend3d.com/hq4x.html hq4x] at the [[Wayback Machine]]
* [https://github.com/grom358/hqx/ Port of original project using DevIL] A command line tool and C library
* [https://github.com/Tamschi/hqxSharp hqxSharp project] a port of hqx with added support for transparency, custom tolerances and seamless tiling (C#)
* [https://code.google.com/p/2dimagefilter/ 2d image filter project] at code.google.com including the hqx filters and more (C#)
* [https://github.com/Arcnor/hqx-java/wiki/Usage hqx-java project] Arcnor project - a free Java port of hqxSharp with a demo of usage (Java)
** [https://github.com/VincenzoLaSpesa/hqxcli-java HqxCli-Java] A command line tool that use the Arcnor implementation (Java)
* [http://blog.pkh.me/p/19-butchering-hqx-scaling-filters.html ffmpeg implementation story] ffmpeg -i %1 -filter_complex hqx=2 hqx2-%1 to produce a 2x image or video.

[[Category:Image processing]]