What is a good algorithm to make halftone images (like this)? A quick google search brings up a bunch of papers on the subject, but it's difficult to judge which are good, efficient, etc. Is there a best choice to do this sort of thing?
+11
A:
- Filter down to the resolution you want the "dots" separated by.
- Get the average intensity of the pixel group in that area.
- Draw the dot such that the surface area of the dot is equal to the percent from white to Black of the average intensity.
Think of the Pixels groups as a hexagonal grid. Use a circle function to decide which pixels go into the group. You can tune the overlap of the circles to adjust the black/saturation of the output. This is really designed for hi-resolution output such as print. If you are doing this to display on screen as a visual effect make sure you use an anti-aliased circle drawing routine to compensate for the low-resolution of the display. (Compared to print, even HD isn't really that high.)
If you are doing this because you like the effect, that's cool. But if you just want to dither down to a black and white image consider using a "Floyd-Steinberg" dither. It provides high quality results and distributes the error across the image. http://en.wikipedia.org/wiki/Floyd-Steinberg_dithering
NoMoreZealots
2009-08-11 01:35:02
http://en.wikipedia.org/wiki/Dither
kenny
2009-08-20 00:42:35
They have a good example of "floyd-stienberg." It's given me the best results in the past.
NoMoreZealots
2009-08-20 01:26:53
The "draw the dot" algorithm outlined here does achieve the "black-dot-only" effect on the cited example web page. But constructing a screen and tuning the dot shape for the "black-dot-only" effect will be faster at runtime.
Liudvikas Bukys
2009-08-25 16:43:05
After looking one more time at the example image: All of its dots are well-formed circles, even at the sharp edges of the image. Therefore one can conclude that it was not produced with a threshold screen. A threshold screen would deform the dots to make straight sharp edges. It was in fact formed using the algorithm suggested above by NoMoreZealots.P.S. Interesting related presentation on "Artistic Screening" at http://www.cs.mcgill.ca/~cs767/student_pres/eric_ArtisticScreening.pdf
Liudvikas Bukys
2009-08-27 15:56:42
Actually in this case, I'd say the algorithm was form from viewing the image. I typically use more of a dithering methodology myself cause I don't find the news print look very visually appealing. I just looked at the image and asked myself how I would do it provided I actually wanted to.
NoMoreZealots
2009-08-27 16:44:40
A:
The easiest way to do this, is to go pixel by pixel and use randomness: for each pixel, probability of coloring it back = darkness of the original color.
That can give you a two-line dithering algorithm. It's not going to look as nice as Floyd-Steinberg (because that one keeps track of the errors), or as artistic as the "tile and then put disks in each tile so that fraction of black = average darkness in the original tile", but it works quite well in practice.
redtuna
2009-08-11 08:49:55
This does result in something where output density appoximates input grey level, but it doesn't achieve the clustered dot appearance of the specific example cited.
Liudvikas Bukys
2009-08-25 16:41:05
Halftone means (to quote wikipedia) "Halftone is the reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size or in spacing." The sample he showed varies size, mine varies spacing. Both hare halftones, though I'm certainly not going to pretend that mine looks as good as the example: as said, the value of this answer is that it's extremely simple to implement.
redtuna
2009-08-25 16:56:13
hare -> are (oops, sorry about the typo! I wish I could edit my comments)
redtuna
2009-08-25 16:57:24
+1
A:
Halftoning is very efficient.
Single-level halftone: Input: Pixels from your image; preconstructed "screen" containing threshold values. At runtime: For each color channel, for each pixel, select one threshold value (index into threshold array modulo the array dimensions). One comparison between the pixel and the threshold determines whether the output value is on or off.
It generalizes to multi-level output as well, by using multiple screens.
The interesting part is construction of the screens (threshold arrays). There are many variations -- clustered dot (AM), stochastic (FM), many variations and hybrids including blue noise and green noise (AM/FM). And you usually want a different screen for each color channel. The traditional clustered dot screens lay their dots out in rectangular grids that can be described by their frequency (low frequency = big dots) and angle (typically 15° for Cyan, 75° for Magenta, 90° for Yellow and 45° for Black).
If you want to experiment, the Photoshop Bitmap with Halftone Screen Method (see this tutorial) has an internal screen generator and will screen a greyscale image into a bitmap just like your example.
The dithering methods suggested by others involve more per-pixel computation, and the output doesn't resemble your clustered dot screened halftone example.
Liudvikas Bukys
2009-08-25 16:14:12