Top 3 color quantization algorithms

  •        0
  

We aggregate and tag open source projects. We have collections of more than one million projects. Check out the projects section.



I have been writing on the desktop image processing application. At the version 1.0, I use the octree color quantization algorithm to reduce image to 256 colors, which is highly memory efficient with each pixel assigned the color at the center of the octree bin in which it falls. On the other hand, generates the palette using the distribution of colors in the image, but it does not consider the frequency of color. This means that if an image is composed of similar colors overall but has many different low-frequency colors or noise, octree’s results can be very poor.

Original photo:

Then I find an article called "Convert 32 bit PNGs to high quality 8 bit PNGs with C#" after googling. It adapted an algorithm developed by Xiaolin Wu. Xialoin Wu's fast optimal color quantizer, which is one of the most effective color quantization methods, provides excellent results. However, low frequency colors in the original image tend to be excluded during the histogram counting process. On top of that, the quantized image in areas of smooth color gradients, in the form of false edges, are clearly visible. Reduced 256 colors by  Xiaolin Wu. Xialoin Wu's fast optimal color quantizer without dithering:

Next I tried the NeuQuant Neural-Net Quantization Algorithm from pngnq which shows excellent results with most images. The results are very natural and have a low MAE and MSE because it spontaneously considers the distribution of colors. However, the speed is quite slow to achieve the best quality. More importantly, high frequency colors are learned many times, so they update the weights many times. This means that high frequency colors influence neighbor nodes much more. In particular, the loss of original color increases when it uses a small number of boxes to quantize the image with a small number of colors.

Reduced to 256 colors by NeuQuant Neural-Net Quantization Algorithm:

To reduce such artifacts, a subsequent dithering step is typically employed after quantization as learnt from Dennis lee v3 color quantization. Dithering distributes quantization errors into neighboring pixels, helping to hide the false edges. Thus, to complement these disadvantages, a better color quantization algorithm that is effective even when it uses only a small number of colors by using the Fast pairwise nearest neighbor based algorithm. This algorithm was only supporting RGB only. I enhanced it to fully support the alpha layer by image transparency detection. It was using RGB555 to filter original colors into 16 bit high color. I change it to use RGB565 for image without transparency, ARGB1555 for image without semi transparency, ARGB4444 for image with semi transparency to digest original colors for the quantization process.

 Reduced to 256 colors by Pairwise Nearest Neighbor Quantization Algorithm: 

To reduce the effect of the color shifted, the fast pairwise nearest neighbor based algorithm with CIELAB color space is established. The CIELAB color space is one of the approximately uniform color spaces recommended for device-independent color representation in electronic color image systems. If colors are represented by the CIELAB space, the axes of lightness L* and chromaticities a* and b* have to be suitably quantized. The largest color quantization steps are always found at the border of the color spaces. Much smaller variations appear if the new color difference formula CIE 2000, DE* 00 is used. In this formula, quantization steps of chroma are valued much less if chroma values are high.

To quantize the image to 32 colors or less, the following quantization algorithms produces better result.

Original image

Fast pairwise nearest neighbor based algorithm with CIELAB color space with 16 colors High quality and fast

Efficient, Edge-Aware, Combined Color Quantization and Dithering with 16 colors High quality for 32 or less colors but slower

Spatial color quantization with 16 colors High quality for 32 or less colors but the slowest

All in all, the top 3 color quantization algorithms for 256 colors are:

  1. Fast pairwise nearest neighbor based algorithm
  2. Xialoin Wu's fast optimal color quantizer
  3. NeuQuant Neural-Net Quantization Algorithm

 

The top 3 color quantization algorithms for 32 colors or less are:

  1. Fast pairwise nearest neighbor based algorithm with CIELAB color space
  2. Efficient, Edge-Aware, Combined Color Quantization and Dithering algorithm
  3. Spatial color quantization algorithm

 

The above sample images are referenced from

https://github.com/mcychan/nQuant.j2se

https://github.com/mcychan/nQuantCpp

 

The source code is ready for the following github projects:

Visual C++ https://github.com/mcychan/nQuantCpp/

C#              https://github.com/mcychan/nQuant.cs

Java           https://github.com/mcychan/nQuant.j2se

Android      https://github.com/mcychan/nQuant.android

 


Sponsored:
To find embedded technology information about MCU, IoT, AI etc Check out embedkari.com.


   

I've been programming for 15 years - started in C language during tertiary education - then to C++ and C# and now Java. I got a BSc degree in Business Information System. I enjoy in learning and excelling at new technologies as needed. I am familiar with the major J2EE frameworks such as Spring, Struts, EJB. Also I am an expert of jquery and javascript according to my teammates.




Related Articles

Exonum Blockchain Framework by the Bitfury Group

  • blockchain bitcoin hyperledger blockchain-framework

Exonum is an extensible open source blockchain framework for building private blockchains which offers outstanding performance, data security, as well as fault tolerance. The framework does not include any business logic, instead, you can develop and add the services that meet your specific needs. Exonum can be used to build various solutions from a document registry to a DevOps facilitation system.

Read More


JWT Authentication using Auth0 Library

  • java jwt authentication security

Json Web Token shortly called as JWT becomes defacto standard for authenticating REST API. In a traditional web application, once the user login credentials are validated, loggedin user object will be stored in session. Till user logs out, session will remain and user can work on the web application without any issues. Rest world is stateless, it is difficult to identify whether the user is already authenticated. One way is to use authenticate every API but that would be too expensive task as the client has to provide credentials in every API. Another approach is to use token.

Read More


AbanteCart - Easy to use open source e-commerce platform, helps selling online

  • e-commerce ecommerce cart

AbanteCart is a free, open source shopping cart that was built by developers with a passion for free and accessible software. Founded in 2010 (launched in 2011), the platform is coded in PHP and supports MySQL. AbanteCart’s easy to use admin and basic layout management tool make this open source solution both easy to use and customizable, depending on the skills of the user. AbanteCart is very user-friendly, it is entirely possible for a user with little to no coding experience to set up and use this cart. If the user would be limited to the themes and features available in base AbanteCart, there is a marketplace where third-party extensions or plugins come to the rescue.

Read More


Univention Corporate Server - An open source identity management system

  • ucs identity-management-system

Univention Corporate Server is an open source identity management system, an IT infrastructure and device management solution and an extensible platform with a store-like App Center that includes tested third party applications and further UCS components: This is what Univention combines in their main product Univention Corporate Server, a Debian GNU/Linux based enterprise distribution. This article provides you the overview of Univention Corporate Server, its feature and installation.

Read More


SeoToaster: easy, fast and efficient open source CMS for top SEO performance

  • cms content-management-system seo ecommerce

SeoToaster is a free Open Source CMS & Ecommerce solution to build, manage and market websites optimized for for top search engine performance. As the name implies, Seo Toaster is to date the only content management system (CMS) to truly integrate SEO execution and web marketing automation technology in full compliance with the search engines industry’s best practices.

Read More