Three styles

Triangle testing

Using area constraint: Triangle -a50zBP based on http://www.cs.cmu.edu/~quake/triangle.html by Shewchuk
Man-made heights
Triangluation

Halftoning almost-final report

The influence of mask size
The variant method
The basic method dealing with one kind of leftout and without dealing the leftout from isolated pixelsThe basic method dealing with both kinds of leftout

PSNR
MSSIM

The variant method(6 out of 12 better than Pang method in tone matching and 12 out of 12 better in structure matching):

Dealing with the two kinds of residue: 1: some leftout from fully-filled pixels after several-time distributions in the mask and 2: leftout from isolated pixels

Using a map to store the residues, when a pixel is popped up from the heap, it will check the mask to find out if there are some residues in this mask; if there are it will carry these residues on the current error. Then the modified error will be distributed in the mask based the weight strategy.

Parameters: k1 = 1; k2 = 2; masksize 7 by 7; takes 4.625 seconds(*********This speed is not better than SAED method with the same size of mask, but better if considering the quality)

************************SAED speed analysis *******************

Kernel size CPU GPU

4 × 4 1.18 0.04

8 × 8 2.27 0.23

16 × 16 6.74 0.75----their best tradeoff

32 × 32 26.31 15.09

*****************************************************************

The basic method(10 out of 12 better than Pang method in tone matching and 9 out of 12 better in structure matching) :

Without ordering and processing it by raster scanning order, deal with the first class residue only. The isolated situation is ignored. If dealing with the isolated situation, the artefacts are very clear.

Parameters: k1 = 20; k2 = 2.25; masksize 7 by 7; takes 0.864 seconds

Results from processing the residue twice

Red dots are isolated pixels. There are so many of them, which affects the tone and structure a lot(The variant method)

BasicVariant

After distributing the residue once, then the residue left is distributed again based on the weight function without spreading the error on those pixels attaining black or white. It turns out the tone matching is getting better, the structure matching is getting lower. Basic method is 11 out of 12 better than Pang's method for PSNR, but 4 out of 12 for MSSIM. The variant is 6 out of 12 better than Pang's method for PSNR and 11 out of 12 for MSSIM.

Deal with the leftout

The basic method
The variant

A lefout map is used to store the residue for each done pixel no matter it is an isolated pixel or not. Next time, before calculating the total weights for a chosen pixel, find the total leftout(T_leftout) around the chosen pixel and the new error = error + T_leftout. There is no global leftout and others are same as before. The tone PSNR has a tiny improvement for both basic and variant method. For example, for variant usually 5 out of 12 examples better than Pang's method, right now it is 6 out of 12. For basic method 10 out of 12 better than Pang's method, right now it is 11 out of 12. But the MSSIM for the basic method is not good anymore. Look at the ramp for both method. This modification improves the variant method, but brings some wrong matching for the basic method.

The wrong matching comes from the decision for drawing white or black after adding the total leftout.