A collection of half tone algorithems. More...

Macros
#define	RIGHTWARD 0

#define	DOWNLEFTWARD 1

#define	DOWNWARD 2

#define	DOWNRIGHTWARD 3

Functions
void	sliding_halftone_get (struct halftone_converter *cnv)

void	sliding_halftone_put (struct halftone_converter *cnv)

void	move_in_next_line (struct halftone_converter *cnv, const unsigned char raw[cnv->pixel_count])

void	move_in_empty_line (struct halftone_converter *cnv, signed short val)

static signed int	quantize_grey_pixel (const struct halftone_converter *cnv, signed int v)

static signed short	diffuse (signed int pix_in, signed int q_err, signed int factor)

static signed int	random_number_create (void)

static void	error_diffusion_randomness_calc (signed int error, signed int random[4])

static void	error_diffusion_right_to_left (struct halftone_converter *cnv)

static void	error_diffusion_left_to_right (struct halftone_converter *cnv)

void	halftone_line_with_error_diffusion (struct halftone_converter *cnv)

void	halftone_line_ordered (struct halftone_converter *cnv)

void	halftone_line_no_dither (struct halftone_converter *cnv)

Detailed Description

A collection of half tone algorithems.

This is a collection of functions to run half-tone algorithms on the raster data prior it is printed.

Each algorithm needs two lines of input data with the raster data. They are always processed at once and - important - gets both changed by the algorithms. Raw raster data is expected in shades of grey and in the format of a signed short per pixel. move_in_next_line() does this required conversation (unsigned char to signed short).

After the algorithm has processed the lines, the first line can be printed. Based on the signed short pixel value result, the printer driver needs to chose a corresponding print pattern ("to dot, or not to dot?").

After that, the second line from the previous call needs to be the first line in the next call, while the second line then contains fresh data from the next raw raster line. You can think of the algorithm slides from the top to the bottom of the raster. move_in_next_line() does this required line swap.

So: to start at the top of the image, you need both lines filled with data, run the half tone algorithm, then print the top line from the sliding half tone structure. Then you are in the flow until you hit the bottom line of your image. In order to process and print it, you need to fill an empty line (via move_in_empty_line()), run the half tone algorithm and again print the top line from the sliding half tone structure. Then you're done.

Macro Definition Documentation

◆ DOWNLEFTWARD

#define DOWNLEFTWARD 1

Value for the downleftward pixel. Just to avoid anonymous numbers

◆ DOWNRIGHTWARD

#define DOWNRIGHTWARD 3

Value for the downrightward pixel. Just to avoid anonymous numbers

◆ DOWNWARD

#define DOWNWARD 2

Value for the downward pixel. Just to avoid anonymous numbers

◆ RIGHTWARD

#define RIGHTWARD 0

Value for the rightward pixel. Just to avoid anonymous numbers

Function Documentation

◆ diffuse()

static signed short diffuse	(	signed int	pix_in,
		signed int	q_err,
		signed int	factor
	)

static

Calculate a pixel value according to "Floyd-Steinberg error diffusion" formula

Parameters

[in]	pix_in	the plain pixel to quantize
[in]	q_err	the quantization error
[in]	factor	one of the factors of the algorithm

Returns: Quantized pixel

Calculation done here is: result = pix_in + ((q_err * factor) / 16)

◆ error_diffusion_left_to_right()

static void error_diffusion_left_to_right ( struct halftone_converter * cnv )

static

Apply error diffusion from left to right

Parameters

[in,out] cnv The converter structure to use

   ------------------> processing direction
   |  N     *   7/16 | <-- cnv->sliding_lines[0]
   | 3/16  5/16 1/16 | <-- cnv->sliding_lines[1]

N previous pixel, * current pixel to process (e.g. X/Y position)

◆ error_diffusion_randomness_calc()

static void error_diffusion_randomness_calc	(	signed int	error,
		signed int	random[4]
	)

static

Calculate some randomness for the error diffusion to avoid visible pattern

Parameters

[in]	error	The current quantization error
[out]	random	Random offset for the four surrounding pixel

The larger the quantization error is, the larger the random offsets will be.

◆ error_diffusion_right_to_left()

static void error_diffusion_right_to_left ( struct halftone_converter * cnv )

static

Apply error diffusion from right to left

Parameters

[in,out] cnv The converter structure to use

   <------------------ processing direction
   | 7/16   *    N   | <-- cnv->sliding_lines[0]
   | 1/16  5/16 3/16 | <-- cnv->sliding_lines[1]

N previous pixel, * current pixel to process (e.g. X/Y position)

◆ halftone_line_no_dither()

void halftone_line_no_dither ( struct halftone_converter * cnv )

Quantize the top line without any half tone algorithm

Parameters

[in,out] cnv The converter structure to use

Returns: The quantized line in halftone_converter::sliding_lines[0]

http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/average_dithering.html

◆ halftone_line_ordered()

void halftone_line_ordered ( struct halftone_converter * cnv )

Quantize the top line according to an "ordered dithering matrix"

Parameters

[in,out] cnv The converter structure to use

Returns: The quantized line in halftone_converter::sliding_lines[0]

This is a simple algorithm with a 2x2 "ordered dithering matrix":

   | 1/10  3/10 | <-- cnv->sliding_lines[0]
   | 4/10  2/10 | <-- cnv->sliding_lines[1]

http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/ordered_dithering.html

Precondition: halftone_converter::sliding_lines[0] and halftone_converter::sliding_lines[1] must be valid

◆ halftone_line_with_error_diffusion()

void halftone_line_with_error_diffusion ( struct halftone_converter * cnv )

Quantize the top line according to the "Floyd-Steinberg error diffusion" and distribute the error around

Parameters

[in,out] cnv The converter structure to use

Returns: The quantized line in halftone_converter::sliding_lines[0]

From: http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1/floyd_steinberg_dithering.html

   |  N     *   7/16 | <-- cnv->sliding_lines[0]
   | 3/16  5/16 1/16 | <-- cnv->sliding_lines[1]

N previous pixel, * current pixel to process (e.g. X/Y position)

Precondition: halftone_converter::sliding_lines[0] and halftone_converter::sliding_lines[1] must be valid; At least three pixels must be in the lines

◆ move_in_empty_line()

void move_in_empty_line	(	struct halftone_converter *	cnv,
		signed short	val
	)

Move in an empty line into the process

Parameters

[in,out]	cnv	The converter structure to use
[in]	val	'Empty' value (0…255)

'Empty' means val must have a value which should not print anything. For example COLOUR_VAL_BRIGHT.

◆ move_in_next_line()

void move_in_next_line	(	struct halftone_converter *	cnv,
		const unsigned char	raw[cnv->pixel_count]
	)

Move in the next line with raw raster data into the process

Parameters

[in,out]	cnv	The converter structure to destroy
[in]	raw	Buffer with raw pixel data (grey scale) in bytes

Throw away the content of the current top line, move all lines below one line up and fill the bottom line with new content from the given raw line.

Currently there are only two lines in the calculation buffer, so "moving" means "swapping" instead.

The byte based pixel data is copied into the sliding half tone structure and gets converted to signed short to be able run the half tone algorithm afterwards.

Note: In order to be able to calculate the bottom line of the image, you need to input an empty line instead. Empty means: it must contain a value, which isn't printed. Refer move_in_empty_line() for details

Precondition: raw must point to a buffer with halftone_converter::pixel_count bytes.

◆ quantize_grey_pixel()

static signed int quantize_grey_pixel	(	const struct halftone_converter *	cnv,
		signed int	v
	)

static

Return the printer's possible value for a given pixel's grey value, e.g. quantize it

Parameters

[in]	cnv	The converter structure to use
[in]	v	The grey value from CUPS raster or any dither algorithm

Return values

Upper	halftone_converter::dotval[1] if v is above halftone_converter::threshold
Lower	halftone_converter::dotval[0] if v is below halftone_converter::threshold

From the Ghostscript/CUPS raster perspective:

we receive a '255' value for an unprinted dot, which means the colour of the paper is visible and this usually means 'white'
we receive a '0' value for a printed dot, which means the colour of the ink or toner should be visible which usually means 'black'
so, with an decreasing value we get a more black pixel

Todo:
Ensure the returned value fits into a 'signed short'

◆ random_number_create()

static signed int random_number_create ( void )

static

Create some random number

Returns: Some pseudo random number, positive and negative

stdlib.h defines RAND_MAX to 2147483647 (same as INT_MAX). By substracting (RAND_MAX / 2) the result should always swing around zero with +/- (RAND_MAX / 2).

Precondition: The srandom() call should be done outside this library. Else, the same pseudo-random values are used over and over again on every run (which might be a good idea for testing).

◆ sliding_halftone_get()

void sliding_halftone_get ( struct halftone_converter * cnv )

Prepare the sliding line buffers

Parameters

[in,out] cnv The converter structure to initialiaize

In order to run some kind of half-tone processing we need signed values per pixel which must be larger than the incoming pixels data. Incoming pixels are of type 'unsigned char' with their grey values. Due to this conversion we do not need to honor any kind of saturation while calculating the dithered output.

Note: Does not return in case of memory failure

Precondition: halftone_converter::pixel_count must be already set and not '0'

◆ sliding_halftone_put()

void sliding_halftone_put ( struct halftone_converter * cnv )

Clean up image processing via sliding line buffers

Parameters

[in,out] cnv The converter structure to destroy

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ DOWNLEFTWARD

◆ DOWNRIGHTWARD

◆ DOWNWARD

◆ RIGHTWARD

Function Documentation

◆ diffuse()

◆ error_diffusion_left_to_right()

◆ error_diffusion_randomness_calc()

◆ error_diffusion_right_to_left()

◆ halftone_line_no_dither()

◆ halftone_line_ordered()

◆ halftone_line_with_error_diffusion()

◆ move_in_empty_line()

◆ move_in_next_line()

◆ quantize_grey_pixel()

◆ random_number_create()

◆ sliding_halftone_get()

◆ sliding_halftone_put()