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 struct caps_dot_grey raw[cnv->pixel_count])

void	move_in_empty_line (struct halftone_converter *cnv, conv_type val)

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

static conv_type	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

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.

Todo:: Fix the algorithm, due to required clipping! Refer halftone support in libcapsdriver.

Macro Definition Documentation

◆ RIGHTWARD

#define RIGHTWARD 0

◆ DOWNLEFTWARD

#define DOWNLEFTWARD 1

◆ DOWNWARD

#define DOWNWARD 2

◆ DOWNRIGHTWARD

#define DOWNRIGHTWARD 3

Function Documentation

◆ 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 dithering 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

◆ move_in_next_line()

void move_in_next_line	(	struct halftone_converter *	cnv,
		const struct caps_dot_grey	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.

◆ move_in_empty_line()

void move_in_empty_line	(	struct halftone_converter *	cnv,
		conv_type	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.

◆ 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

halftone_converter::dotval[1]	if v is above halftone_converter::threshold
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'

◆ diffuse()

static conv_type 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)

◆ 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).

◆ 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)

◆ 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)

◆ 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

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

◆ 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

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_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

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

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ RIGHTWARD

◆ DOWNLEFTWARD

◆ DOWNWARD

◆ DOWNRIGHTWARD

Function Documentation

◆ sliding_halftone_get()

◆ sliding_halftone_put()

◆ move_in_next_line()

◆ move_in_empty_line()

◆ quantize_grey_pixel()

◆ diffuse()

◆ random_number_create()

◆ error_diffusion_randomness_calc()

◆ error_diffusion_right_to_left()

◆ error_diffusion_left_to_right()

◆ halftone_line_with_error_diffusion()

◆ halftone_line_ordered()

◆ halftone_line_no_dither()