view release on metacpan or  search on metacpan

src/Source/FreeImage/Halftoning.cpp  view on Meta::CPAN

// ==========================================================
// Bitmap conversion routines
// Thresholding and halftoning functions
// Design and implementation by
// - Hervé Drolon (drolon@infonie.fr)
// - Dennis Lim (dlkj@users.sourceforge.net)
// - Thomas Chmielewski (Chmielewski.Thomas@oce.de)
//
// Main reference : Ulichney, R., Digital Halftoning, The MIT Press, Cambridge, MA, 1987
//
// This file is part of FreeImage 3
//
// COVERED CODE IS PROVIDED UNDER THIS LICENSE ON AN "AS IS" BASIS, WITHOUT WARRANTY
// OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, WITHOUT LIMITATION, WARRANTIES
// THAT THE COVERED CODE IS FREE OF DEFECTS, MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE
// OR NON-INFRINGING. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE COVERED
// CODE IS WITH YOU. SHOULD ANY COVERED CODE PROVE DEFECTIVE IN ANY RESPECT, YOU (NOT
// THE INITIAL DEVELOPER OR ANY OTHER CONTRIBUTOR) ASSUME THE COST OF ANY NECESSARY
// SERVICING, REPAIR OR CORRECTION. THIS DISCLAIMER OF WARRANTY CONSTITUTES AN ESSENTIAL
// PART OF THIS LICENSE. NO USE OF ANY COVERED CODE IS AUTHORIZED HEREUNDER EXCEPT UNDER
// THIS DISCLAIMER.
//
// Use at your own risk!
// ==========================================================

#include "FreeImage.h"
#include "Utilities.h"

static const int WHITE = 255;
static const int BLACK = 0;

// Floyd & Steinberg error diffusion dithering
// This algorithm use the following filter
//          *   7
//      3   5   1     (1/16)
static FIBITMAP* FloydSteinberg(FIBITMAP *dib) {

#define RAND(RN) (((seed = 1103515245 * seed + 12345) >> 12) % (RN))
#define INITERR(X, Y) (((int) X) - (((int) Y) ? WHITE : BLACK) + ((WHITE/2)-((int)X)) / 2)

	int seed = 0;
	int x, y, p, pixel, threshold, error;
	int width, height, pitch;
	BYTE *bits, *new_bits;
	FIBITMAP *new_dib = NULL;

	// allocate a 8-bit DIB
	width = FreeImage_GetWidth(dib);
	height = FreeImage_GetHeight(dib);
	pitch = FreeImage_GetPitch(dib);
	new_dib = FreeImage_Allocate(width, height, 8);
	if(NULL == new_dib) return NULL;

	// allocate space for error arrays
	int *lerr = (int*)malloc (width * sizeof(int));
	int *cerr = (int*)malloc (width * sizeof(int));
	memset(lerr, 0, width * sizeof(int));
	memset(cerr, 0, width * sizeof(int));

	// left border
	error = 0;
	for(y = 0; y < height; y++) {
		bits = FreeImage_GetScanLine(dib, y);
		new_bits = FreeImage_GetScanLine(new_dib, y);

		threshold = (WHITE / 2 + RAND(129) - 64);
		pixel = bits[0] + error;
		p = (pixel > threshold) ? WHITE : BLACK;
		error = pixel - p;
		new_bits[0] = (BYTE)p;
	}
	// right border
	error = 0;
	for(y = 0; y < height; y++) {
		bits = FreeImage_GetScanLine(dib, y);
		new_bits = FreeImage_GetScanLine(new_dib, y);

		threshold = (WHITE / 2 + RAND(129) - 64);
		pixel = bits[width-1] + error;
		p = (pixel > threshold) ? WHITE : BLACK;
		error = pixel - p;
		new_bits[width-1] = (BYTE)p;
	}
	// top border
	bits = FreeImage_GetBits(dib);
	new_bits = FreeImage_GetBits(new_dib);
	error = 0;
	for(x = 0; x < width; x++) {
		threshold = (WHITE / 2 + RAND(129) - 64);
		pixel = bits[x] + error;
		p = (pixel > threshold) ? WHITE : BLACK;
		error = pixel - p;
		new_bits[x] = (BYTE)p;
		lerr[x] = INITERR(bits[x], p);
	}

	// interior bits
	for(y = 1; y < height; y++) {
		// scan left to right
		bits = FreeImage_GetScanLine(dib, y);
		new_bits = FreeImage_GetScanLine(new_dib, y);

	    cerr[0] = INITERR(bits[0], new_bits[0]);
		for(x = 1; x < width - 1; x++) {
			error = (lerr[x-1] + 5 * lerr[x] + 3 * lerr[x+1] + 7 * cerr[x-1]) / 16;
			pixel = bits[x] + error;
			if(pixel > (WHITE / 2)) {		
				new_bits[x] = WHITE;
				cerr[x] = pixel - WHITE; 
			} else {
				new_bits[x] = BLACK;
				cerr[x] = pixel - BLACK; 
			}
		}
		// set errors for ends of the row
		cerr[0] = INITERR (bits[0], new_bits[0]);
		cerr[width - 1] = INITERR (bits[width - 1], new_bits[width - 1]);

		// swap error buffers
		int *terr = lerr; lerr = cerr; cerr = terr;
	}

	free(lerr);
	free(cerr);

	return new_dib;
}

// ==========================================================
// Bayer ordered dispersed dot dithering
//

// Function taken from "Ordered Dithering, Stephen Hawley, Graphics Gems, Academic Press, 1990"
// This function is used to generate a Bayer dithering matrice whose dimension are 2^size by 2^size
//
static int dithervalue(int x, int y, int size) {
	int d = 0;
	/*
	 * calculate the dither value at a particular
	 * (x, y) over the size of the matrix.
	 */
	while (size-->0)	{
		/* Think of d as the density. At every iteration,
		 * d is shifted left one and a new bit is put in the
		 * low bit based on x and y. If x is odd and y is even,
		 * or x is even and y is odd, a bit is put in. This
		 * generates the checkerboard seen in dithering.
		 * This quantity is shifted left again and the low bit of
		 * y is added in.
		 * This whole thing interleaves a checkerboard bit pattern
		 * and y's bits, which is the value you want.
		 */
		d = (d <<1 | (x&1 ^ y&1))<<1 | y&1;
		x >>= 1;
		y >>= 1;
	}
	return d;
}

// Ordered dithering with a Bayer matrix of size 2^order by 2^order
//
static FIBITMAP* OrderedDispersedDot(FIBITMAP *dib, int order) {
	int x, y;
	int width, height;
	BYTE *bits, *new_bits;
	FIBITMAP *new_dib = NULL;

	// allocate a 8-bit DIB
	width = FreeImage_GetWidth(dib);
	height = FreeImage_GetHeight(dib);
	new_dib = FreeImage_Allocate(width, height, 8);
	if(NULL == new_dib) return NULL;

	// build the dithering matrix
	int l = (1 << order);	// square of dither matrix order; the dimensions of the matrix
	BYTE *matrix = (BYTE*)malloc(l*l * sizeof(BYTE));
	for(int i = 0; i < l*l; i++) {
		// according to "Purdue University: Digital Image Processing Laboratory: Image Halftoning, April 30th, 2006
		matrix[i] = (BYTE)( 255 * (((double)dithervalue(i / l, i % l, order) + 0.5) / (l*l)) );