Task 068: Halftoning for a Laser Printer

Your task is to implement a halftoning algorithm for a laser printer with a resolution of 1200dpi. You should use frequency modulation dithering ("FM dithering"), which uses random placement of equally sized dots on paper: darker areas of the image get more dots, while lighter ones get fewer.

FM dithering

Principle

Black dots are placed on the paper such that their density matches the brightness of the input image. Black (image value of 0) corresponds to the maximum density of dots in the printed area, so that the paper is completely covered by toner. White areas (image value 255) have no dots, so that completely white paper remains.

If one is placing dots for use on a high-quality laser printer, it is necessary to maintain a certain minimum distance between points (if they are not so densely spaced that they have to touch). For instance, you could use a version of Don Mitchell's algorithm'.

Result

The result will be tested on a laser printer with a resolution of 1200dpi (eg. HP LaserJet 1320 or P2015), with dot sizes of 1x1 and 10x10.

Overview

The template application 068laser from the repository grcis serves as the basis of this project. This is an application which can load an image, and which automatically runs the method Dither.TransformImage() that calculates a transformed output image. You have to implement your technique in the file Dither.cs between the comment brackets:

  // !!!{{
  // !!!}}

Demo Application

as long as no image is loaded, an in-built test image is used instead.
creation of an image instance in the fixed format Format1bppIndexed (with a two-element palette that only contains black and white)
the output image is assembled as individual bits, so it is necessary to use bit operations to write it
quick access to binary pixel data - using the method Bitmap.LockBits() and unsafe blocks, locked memory areas are accessed
calculation in a separate thread - in order to be able to terminate the computations it is necessary to frequently (e.g. once per scanline) check the global variable Form1.cont - if that is set to false, it means the computation should be abandoned.
Drag & Drop of input images - input images can be moved to the application via D&D
a few simple techniques are already implemented:
1. density-driven sample generation: a monochrome version of the image is generated (FloatImage), and via the method FloatImage.GetSample a random location in the image is generated. The demo application only draws dots (Dot1bpp(), the dot size is controlled via the text parameter 'dot') without further checks.
2. random dispersion of large dots: during a pass over the entire image, a random generator decides about dot placement. The actual dots are also done via the Dot1bpp() function.
3. random dispersion of individual pixels: this is similar to B., only that individual pixels are generated as output. Dot size ('dot') must be zero in this case.

Technical Details

The input image is passed to your method via the parameters Bitmap input, and fast data access can be used. Two numerical parameters indicate the desired output resolution. The output image is returned via the output parameter out Bitmap output. The user-specified text parameter string param is used to retrieve the following parameters in the demo application:

scale: scaling factor for the input image (fractional number)
gamma: gamma coefficient, to use on the output. Set to zero for linear output.
dot: dot size (in actual 1200dpi printer pixels) to use as output primitive. This is used for techniques A and B; for C, it has to be set to zero.
rnd: random factor for decisions made by all the algorithms. Zero means deterministic behaviour, one totally random.
sampling: boolean value, "true" enables technique A.

Reading the grey level of the input bitmap (including interpolation between neighbouring pixels) is done via the method Dither.GetGray(), but you have to use quick access to the fixed bitmap memory.

In case of Mitchell sampling you need quick searches for neighbouring pixels. To accelerate this, we recommend that you use some search data structure for 2D, such as e.g. grids, Point-quadtrees or KD-trese, which will be explained in the practical exercise.

Initialisation of parameters: in order to have all relevant code nicely grouped in a single location, you can initialise your application parameters in the function InitParams(). It is called during application start-up.

In the last parameter field out string name please write your full name (as well as in the comments on the first line of the source file). This will make it easier to perform automatic evaluations of the results.

What to hand in

As solution of the problem, you have to send us the file Dither.cs (and only that). If controlling your chosen algorithm uses any parameters, you have to properly document these in your submission mail.

Deadline

Hand in the assignment until: 22. 12. 2016

Points

Basic: 10 points for a functioning algorithm, plus a potential bonus of 1-5 points for efficiency and high quality output.

Project

Visual Studio project: 068laser.

Source file

Modify and hand in the source file: Dither.cs
As a comment in the first line, please include your name!

Test data

You can use images from the repository data, and can also use frozentree.png, cate1600x1200bw.png or egsr1.png.