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

 


   

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.

Subscribe to our newsletter.

We will send mail once in a week about latest updates on open source tools and technologies. subscribe our newsletter



Related Articles

Angular Service Workers Usage Guide

  • angular service-worker offline-app

Web developers come across scenarios like web application completely breaks when workstation goes offline. Likewise to get into our application, every time we need to open a browser and then access it. Instead if it is in app, it will be easy to access for end-user. Push notifications similar to email client need to be done through web application. All these are addressed by a magic called service worker.

Read More


COVID19 Stats using Angular Material Design

  • angular material-design covid covid-stats

Material design is inspired from the real world building architecture language. It is an adaptable system of guidelines, components, and tools that support the best practices of user interface design. Backed by open-source code, Material streamlines collaboration between designers and developers, and helps teams quickly build beautiful products. In this article, we will build COVID stats using Angular Material design.

Read More


Laravel eCommerce Platform - Bagisto

  • ecommerce shopping laravel php

Nowadays on the web, Shopping is one of the most popular activities. Everyone can shop at their recess, anytime from anywhere. However, this is interesting that anyone can have their pages built to display their favourite products and services.

Read More


Desktop Apps using Electron JS with centralized data control

  • electronjs couchdb pouchdb desktop-app

When there is a requirement for having local storage for the desktop application context and data needs to be synchronized to central database, we can think of Electron with PouchDB having CouchDB stack. Electron can be used for cross-platform desktop apps with pouch db as local storage. It can sync those data to centralized database CouchDB seamlessly so any point desktop apps can recover or persist the data. In this article, we will go through of creation of desktop apps with ElectronJS, PouchDB and show the sync happens seamlessly with remote CouchDB.

Read More


Scene.js - Library to Create Timeline-Based Animation

  • scenejs css timeline javascript animation motion

Scene.js is a JavaScript timeline-based animation library for creating animation websites. As an animated timeline library, it allows you to create a chronological order of movements and positions of objects.

Read More



Leaflet and Keyhole Markup Language (KML)

  • leaflet kml maps

Leaflet, a open-source JavaScript library for interactive maps. It is a well-documented API and extended with lot of plugins. It is also designed with simplicity, performance and usability.

Read More


Holistic usage guide for OpenSSL

  • openssl security certificate tools

OpenSSL is a general purpose cryptographty toolkit that provides an open source implementation of Transport Layer Security(TLS) and Secure Socket Layer(SSL) protocols. It is written in C,assembly and Perl language but wrappers are available in all languages. This article explains about OpenSSL commands.

Read More


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


Apache OpenNLP - Document Classification

  • opennlp natural-language-processing nlp document-classification

Apache OpenNLP is a library for natural language processing using machine learning. In this article, we will explore document/text classification by training with sample data and then execute to get its results. We will use plain training model as one example and then training using Navie Bayes Algorithm.

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


Best open source Text Editors

  • text-editor editor tools dev-tools

Text editors are mainly used by programmers and developers for manipulating plain text source code, editing configuration files or preparing documentation and even viewing error logs. Text editors is a piece of software which enables to create, modify and delete files that a programmer is using while creating website or mobile app.In this article, we will discuss about top 7 all-round performing text editors which is highly supportive for programmers.

Read More


Getting started with Apache OpenNLP

  • apache-opennlp machine-learning java nlp natural-language-processing

The Apache OpenNLP library is a machine learning based toolkit for the processing of natural language text. OpenNLP also includes entropy and perceptron based machine learning. . It contains several components for natural language processing pipeline like sentence detector, tokenizer, name finder, document categorizer, part-of-speech tagger, chunker, parser, co-reference resolution.

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