Digital facial engraving

http://www.iro.umontreal.ca/~ostrom/publications/abstracts.html
Victor Ostromoukhov. Digital Facial Engraving, In Proceedings of SIGGRAPH'99, in Computer Graphics Proceedings, Annual Conference Series, pp. 417-424, 1999.

Gouraud shading lines

Test illuminating lines

The height field for a sphere is created by calculating the distance between the light and the vertices of the sphere. The lines are shown as contour lines based on different light position. Next step is to try to make the contour line continuous or long.

Random heights for a sphere.

a sphere
a sphere
a sphere
all illuminating lines
Triangulation for irregular PSLG

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.

Color halftoning and other testings

Look much better than Pang's method and it is fast.



Intensity=128

not good in visualiztion

Intensity tests:

Intensity black pixels percentage

25 27060/30000 90.2%

80 20591/30000 68.64%

100 18248/30000 60.82%

128 14946/30000 49.82%

204 6010/30000 20.03%

Resutls for modified accumulation function

The ordering is based on the distance to the black or the white. Based on my measurement, we have higher MSSIM and Constrast MSE. Our PSNR haver higher values than previous method except cat, tree, bat examples.

The modified weight function

if(error>0)

maxin = max(0.5,(Ii/(5*pow(r,1.0f))));

else

maxin = max(0.5,((255-Ii)/(5*pow(r,1.0f))));

in = min(maxin, 255-Ii);// to maintain the maximum;

ramp image
Good structure for tree and snail images


It seems the structure is better, but the tone looks not that good.

The tone looks fine. Clumping is there.

What do you think the following results?

The cat looks good! It is fast and the running time has the same order as 2009 paper. But our method has annoying patterns and some structure are missed.(No ordering, not both errors, raster order, circular mask, half bottom, Ii/r)

A bad news

Their results for comparison


http://www.iro.umontreal.ca/~ostrom/publications/pdf/SIGGRAPH-ASIA09_saed.pdf

This paper is published in this year SIGGRAPH-ASIA. They did the error diffusion very very fast and have the structure well maintained.

Following the last blog

With sorting pixels by the distance to the two ends

The measurement shows the results have higher contrast similarity and structure similarity than those in last blog without ordering step, but lower tone similarity than them.

the weight function

maxin = max(0.5,(Ii/(5*pow(r,1.0f))));

in = min(maxin, 255-Ii);

Tone similarity(not high, better than 'structure-aware ' paper)Structure similarity(good)
Contrast similarity(good)

Good results in visualization but not high scores in measurement

PSNR(low scores, in most time better than Pang's method)
MSSIM(not always high scores)

Contrast similarity based on the contrast image and do the same as the PSNR measurement(high scores)
No ordering and do other procedure we have.

Seems we nail down the clumping

A result with jittering the intensities

Little improvement

A result with jittering the centers
A result without jittering

Jittering the centers to ruin the patterns from the mask. It seems it works, but also introduces some clumping. I should try to do something when ordering the pixels.

It turns out we can use the same function for weight calculations because we are choosing the distance between two ends to sort the orders. There are something I am not sure if I am doing correctly. First, I always maintain the updated value(maybe called intensity) in the range 0 to 255. If it is more than 255 or less than 0, the leftout(residue) will transport to the next chosen pixel. Second, the decision of black or white pixels are affected by both the current intensity and the carry-on residue from last chosen pixels.

The method like the error diffusion

The orders are based on the distance(the intensity) to the two ends(0 and 255). When a pixel is chosen, based on the closer ends choose white or black to draw the pixels. Then find the error between the original intensity and the black or white and distribute it into the mask based the weight function we are choosing. In each mask with radius 2, the weight function is as follows(same as the previous blog),

maxin = max(0.5,(Ii/(5*pow(r,3.0f))));

in = min(maxin, 255-Ii);

Some results

our method
error diffusion

The orders are based on the intensities and it use the circular mask with radius 5. Based on the normalization for each mask to distribute the intensity(or called errors).

For each mask, weights using function as follows:

maxin = max(0.5,(Ii/(5*pow(r,4.0f))));

in = min(maxin, 255-Ii);

less clumping but more patterns maxin = max(0.5,(Ii/(5*pow(r,3.0f))-Ii/(50*pow(r,3.0f)));

in = min(maxin, 255-Ii);

I cannot see many improvements after correcting the boundary conditions.

maxin = max(0.5,(Ii/(5*pow(r,3.0f))));

in = min(maxin, 255-Ii);

A little bettern results than others both for clumping and for patterns. Comparing with the results from error diffusion, still more patterns and more clumping in inbetween intensities(around 100-150). maxin = max(0.5,(Ii/(5*pow(r,2.0f))));

in = min(maxin, 255-Ii);

More clumping, especially for the hats.

Visulization for orders

I=80
I=150
I=5
I = 128
I = 5 ,80,128,192,250



It seems the orders work fine.

Error diffusion with orders based on intensities

From the traditional methodFrom the modified method

It is almost the same method as the error diffusion method but based on the orders to do the error diffusion.

Larger radius

More clumping

Here are results based on the fixed circle mask and normalization

Problems:

1. Still clear patterns

2. The dark areas are too light and the white areas have too many pixels chosen.

3. Clumping

The radius of the mask is 3.

Ci is the contrast.

The chosen function is as follows.

maxin = max(0.5,((1-Ci)*I0 * (pow(Ii,0.4f)/(pow(255,0.4f))))/(3*r));

detI = min(maxin, 255-Ii);

MSSIM testing

MSSIM(A,OUR) = 0.1700

PSNR(A,OUR) = 13.2743
MSSIM(A,C)=0.3243

PSNR(A,C)=10.4887
MSSIM(A,255-A) = -0.1978

PSNR(A,255-A) = 6.8434
MSSIM(A,A) = 1

Error diffusion

Some patterns can be created.

These patterns are created by partially choosing some pixels around the center not to be updated by the function. But the tone matching is still not good.

Kind of smudging effects

I am not sure if this is what are called smearing effects. But for me, it smudges the images. It did not do a good job for images with textures.

About clumping

When two spirals are mixed together, this situation will raise the inbetween pixel vlaues. When we allow the spirals to have large size, actually the inbetween areas will be hit a lot of times, not few times as I guessed. In my testing, the hitting usually reaches around 20 times. The highest hitting times once was 37 times in my testing. Thus, to make sure the inbetween pixels will be our next choice. The accumulation function has to be tricky. It has to drop very quickly from the center to the boundary to make sure the inbetween pixels are only raised a little values. It kind of avoids some clumpings. It turns out our guess is correct. The clumping ruins the tone matching. Right now I got very good tone matching based on PSNR measurement, better than the error diffusion method. But the structure similarity is not matched well and the visual effects are not very good either. Now I am adjustting the settings to want to get higher vlaues in both PSNR and MSSIM measurements. But right now I did not get that yet.

Another thing about clumping, after checking the results from the error diffusion, they have clumping too. But their clumping happens in vertical or diagonal direction. It seems in visualization the eyes can identify more quickly when two pixels are sticked together in a horizonal direction than the vertical ways. But right now I cannot avoid the horizonal situations.

the ramp image

MSSIMPSNR

Some experiences

I tried the regular mask by using the same process. It turns out the regular mask will bring more artefacts than the spiral mask. In visualization, the same function will have similar effects. The differences are in different patterns introduced by different masks.

I also tried the floating points to store the values. Right now it gives more control for each step, but I cannot say what the other advantages are.

Right now it seems the limit of the size of the mask has a great effect on ruining tone.

The size of the mask has some influence in visual effects.

Performance: 512 by 512 takes 113 seconds.

I am going to put the tone down and try to find some interesting patterns from our method. Right now how to control patterns seems a mystry.

A few steps for running

The left side has 100 value in intensity and the right side has 200 value.

2000 stipples
3000 stipples
5000 stipples10000stipples
final

Strange effects

using the regular mask

using the spiral mask

A little better than the Pang's method in tone

Worse than the Ostromoukhov's mehtod and the error diffusion in tone match



The MSSIM comparison by 2003 Zhou Wang(matlab codes from their page)

http://www.ece.uwaterloo.ca/~z70wang/research/ssim/
The PSNR comparison(matlab codes from matlab central)

http://www.mathworks.com/matlabcentral/fileexchange/135
Use the Gaussian filter first for both images(11 by 11 window)

Measurement for halftoning

Do not know how they display the radially averaged power spectrum as the paper.

grayness = 0.75 copy the image from the paper and calculate it again.

grayness = 192
MSSIM to measure the structure simliarity

For(1-*) group
For(2-*)group
For(3-*)group

PSNR measurement for tone similariy

For(1-*) group
For(2-*) group
For(3-*) group
(01-cat)
(02-cat)
(03-cat)
(01-tree)
(02-tree)
(03-tree)
(01-a1)
(02-a1)
(03-a1)

Use the fixed length(20) to test all of images

It did a very good job for textures.

Set up a maximum cutout for each pixel based on the minimum length of the spiral

The minimum length is changable based on the center intensity.

The fixed length(10) is used always.
The fixed length(20) is used always.
The fixed length(25) is used always.
The fixed length(60) is used always.

Artefacts from the uniform region

the intensity value is 250.

Another thought

Arbitrarily to reduce the influence around the chosen spiral based on the distance and reordering is based on the distance and the intensity.

(5) Similar to (4) but with partial reordering

Do reordering when the intensity greater than 200; otherwise, no reordering.

All of four modifications have some change for the visual effect.

But the change is not very clear.

(1)Non-linearly reduce the influence based on the length of the sprial

Always reordering

length is the length of the spiral.

if(Ii>Tii)

in = 255-Ii;

else

{

in = 255 - Ii;

in = in * pow((double)(length+1),-0.2);// influence slow down based on the length

}

(2)Non-linearly reduce the influence based on the radius

Always reordering

r is the distance between the pixel and the center of the mask

if(Ii>Tii)

in = 255-Ii;

else

{

in = 255 - Ii;

in = in * pow((double)(r+1),-0.2);// (-0.5,-0.2,-0.01)non-linear;//influence slow down }

(3)Linearly reduce the influence based on the radius

Alway reordering

r is the distance between the pixel and the center of the spiral mask.

if(Ii>Tii)

in = 255-Ii;

else

{

in = 255 - Ii;

in = in * (1 - 0.03 * r);// linear

}

(4)LAHE always with reordering

http://en.wikipedia.org/wiki/Histogram_equalization

Their results(strucutre-aware halftoning) for comparison

Better results by compromise

By compromise, we can choose some pixels to do the reordering when the intensity reduced and others will not change the order during the whole process. It means we try to avoid the clumping where there is a brighter area since we think the clumping at the edges (assumed there are darkness) won't have much artefacts.

reordering when the original intensity greater than 150reordering when the original intensity greater than 100
reordering when the reduced intensity greater than 150
reordering when the reduced intensity greater than 200

Using the same order in the whole previous algorithm

Finally the tone is matched after dealing with the first pixel

The spiral masks are used.

Better for tone change but artefacts are too clear.

Algorithms:

1. Sort each pixels based on the brightness into a heap.

2. For each pixel grows the spiral

%% accum is the accumulation; target is the goal; counter is

%%for a long spiral over the limit

(1): initial states: accum = 0; target = 255; counter = 0;

(2): grow the spiral( for each step the real codes as follows)

%% full; stop

if(accum >= target) break;

Ii = ppTemp[v.y][v.x].GetGreyscaleValue ();

%% return the increase based on the accumulation function

out = accumulate(I0,Ii, m_ppDoneMap[v.y][v.x]);

accum = accum + out;%% accumulation

%% update the original image and the done map

in = min(255,Ii + out);

ppTemp[v.y][v.x] = COLOR(in, in, in);

m_ppDoneMap[v.y][v.x] =0;// flag for used pixels

%% the error at the last pixel

if (accum > target)

{

in = Ii-(accum-out-target);%% too much

ppTemp[v.y][v.x] = COLOR(in,in, in);

}

%% counter for the length of the spiral

counter++;

%% too long and cut it out; might have a problem

if(counter>spiralmask.size ()) break;

---------------------------------------------

%% the accumulation function

int accumulation(...)

{

Ti = 80;

if(255-Ii less than Ti)

in = 255 - Ii;

else

in = Ti;

return in;

}

---------------------------

Intensity response diagram based on the ramp image
Some results

Still no luck

intensity = 200intensity = 50

I guess this is the effect we want, but still has issues.

It seems the method catches the constrast or maybe we can say it obeys the edges. But it does not follow the tone correctly.

It seems the artefacts are from the function I chosen. But right now I do not know how to avoid them.

Strange effects

Effect 1

Effect 2

The threshold is based on the accumulation and the discontinuous increase for the chosen function.

Still not good