14

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?

Improve this question
1
  • Is there something more to your question that you would like answered? More details?
    – NoMoreZealots
    Commented Aug 12, 2009 at 0:26

4 Answers 4

Reset to default
17
  • 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

Improve this answer
4
  • They have a good example of "floyd-stienberg." It's given me the best results in the past.
    – NoMoreZealots
    Commented Aug 20, 2009 at 1:26
  • 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
    Commented Aug 25, 2009 at 16:43
  • 2
    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 cs.mcgill.ca/~cs767/student_pres/eric_ArtisticScreening.pdf
    – Liudvikas Bukys
    Commented Aug 27, 2009 at 15:56
  • 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
    Commented Aug 27, 2009 at 16:44
5

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.

Improve this answer
0
2

There are many open source implementations of algorithms to create halftone images. You can take a look at the source codes. Below are presented a few implementations developed in Java using Marvin Image Processing Framework.

input image:
enter image description here

Error Diffusion (source):
enter image description here

Rylanders (source):
enter image description here

Dithering (source):
enter image description here

Circles (source):
enter image description here

Improve this answer
1

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.

Improve this answer
3
  • 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
    Commented Aug 25, 2009 at 16:41
  • 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
    Commented Aug 25, 2009 at 16:56
  • hare -> are (oops, sorry about the typo! I wish I could edit my comments)
    – redtuna
    Commented Aug 25, 2009 at 16:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.