Dither a Grayscale Image

Question

Dither a grayscale image into pure black and white with your own algorithm.

Guidelines: You must come up with your own new algorithm. You cannot use pre-existing algorithms (ex. Floyd-Steinburg) but you can use the general technique. Your program must be able to read an image and produce an image the same size. This is a popularity contest, so whoever produces the best (closest to original) and most creative (determined by votes) wins. Bonus if the code is short, though this is not necessary.

You can use whatever grayscale image you want as input, it should be larger than 300x300. Any file format is fine.

Example input:

Example output:

This is a pretty good job, but there still are visible lines and patterns.

Answer 1

GraphicsMagick/ImageMagick

Ordered Dither:

magick B2DBy.jpg -gamma .45455 -ordered-dither [all] 4x4 ordered4x4g45.pbm

Before complaining about my using an "established algorithm" please read the ChangeLog for GraphicsMagick and ImageMagick for April 2003 where you'll see that I implemented the algorithm in those applications. Also, the combination of "-gamma .45455" with "-ordered-dither" is new.

The "-gamma .45455" takes care of the image being too light. The "all" parameter is only needed with GraphicsMagick.

There's banding because there are only 17 graylevels in a 4x4 ordered-dither image. The appearance of banding can be reduced by using an 8x8 ordered-dither which has 65 levels.

Here are the original image, the 4x4 and 8x8 ordered dithered output and the random-threshold output:

I prefer the ordered-dither version, but am including the random-threshold version for completeness.

magick B2DBy.jpg -gamma .6 -random-threshold 10x90% random-threshold.pbm

The "10x90%" means to render below 10 percent intensity pixels as pure black and above 90 percent as pure white, to avoid having a few lonely specks in those areas.

It's probably worth noting that both are as memory-efficient as they can possibly be. Neither does any diffusion, so they work one pixel at a time, even when writing ordered-dither blocks, and don't need to know anything about the neighboring pixels. ImageMagick and GraphicsMagick process a row at a time, but it's not necessary for these methods. The ordered-dither conversions take less than .04 second real time on my old x86_64 computer.

Answer 2

I apologize for the code style, I threw this together using some libraries we just built in my java class, and it has a bad case of copy-paste and magic numbers. The algorithm picks random rectangles in the image, and checks if the average brightness is greater in the dithered image or the original image. It then turns a pixel on or off to bring the brightnesses closer in line, preferentially picking pixels that are more different from the original image. I think it does a better job bringing out thin details like the puppy's hair, but the image is noisier because it tries to bring out details even in areas with none.

public void dither(){
    int count = 0;
    ditheredFrame.suspendNotifications();
    while(count < 1000000){
        count ++;
        int widthw = 5+r.nextInt(5);
        int heightw = widthw;
        int minx = r.nextInt(width-widthw);
        int miny = r.nextInt(height-heightw);



            Frame targetCropped = targetFrame.crop(minx, miny, widthw, heightw);
            Frame ditherCropped = ditheredFrame.crop(minx, miny, widthw, heightw);

            if(targetCropped.getAverage().getBrightness() > ditherCropped.getAverage().getBrightness() ){
                int x = 0;
                int y = 0;
                double diff = 0;

                for(int i = 1; i < ditherCropped.getWidth()-1; i ++){
                    for(int j = 1; j < ditherCropped.getHeight()-1; j ++){
                        double d = targetCropped.getPixel(i,  j).getBrightness() - ditherCropped.getPixel(i, j).getBrightness();
                        d += .005* targetCropped.getPixel(i+1,  j).getBrightness() - .005*ditherCropped.getPixel(i+1, j).getBrightness();

                        d += .005* targetCropped.getPixel(i-1,  j).getBrightness() - .005*ditherCropped.getPixel(i-1, j).getBrightness();

                        d += .005* targetCropped.getPixel(i,  j+1).getBrightness() -.005* ditherCropped.getPixel(i, j+1).getBrightness();

                        d += .005* targetCropped.getPixel(i,  j-1).getBrightness() - .005*ditherCropped.getPixel(i, j-1).getBrightness();

                        if(d > diff){
                            diff = d;
                            x = i;
                            y = j;
                        }
                    }
                    ditherCropped.setPixel(x,  y,  WHITE);
                }

            } else {
                int x = 0;
                int y = 0;
                double diff = 0;

                for(int i = 1; i < ditherCropped.getWidth()-1; i ++){
                    for(int j = 1; j < ditherCropped.getHeight()-1; j ++){
                        double d =  ditherCropped.getPixel(i, j).getBrightness() -targetCropped.getPixel(i,  j).getBrightness();
                        d += -.005* targetCropped.getPixel(i+1,  j).getBrightness() +.005* ditherCropped.getPixel(i+1, j).getBrightness();

                        d += -.005* targetCropped.getPixel(i-1,  j).getBrightness() +.005* ditherCropped.getPixel(i+1, j).getBrightness();

                        d += -.005* targetCropped.getPixel(i,  j+1).getBrightness() + .005*ditherCropped.getPixel(i, j+1).getBrightness();

                        d += -.005* targetCropped.getPixel(i,  j-1).getBrightness() + .005*ditherCropped.getPixel(i, j-1).getBrightness();



                        if(d > diff){
                            diff = d;
                            x = i;
                            y = j;
                        }
                    }
                    ditherCropped.setPixel(x,  y,  BLACK);
                }
            }


    }
    ditheredFrame.resumeNotifications();
}

Answer 3

Fortran

Okay, I'm using an obscure image format called FITS which is used for astronomy. This means there is a Fortran library for reading and writing such images. Also, ImageMagick and Gimp can both read/write FITS images.

The algorithm I use is based on "Sierra Lite" dithering, but with two improvements:
a) I reduce the propagated error by a factor 4/5.
b) I introduce a random variation in the diffusion matrix while keeping its sum constant.
Together these almost completely elminiate the patterns seen in OPs example.

Assuming you have the CFITSIO library installed, compile with

gfortran -lcfitsio dither.f90

The file names are hard-coded (couldn't be bothered to fix this).

Code:

program dither
  integer              :: status,unit,readwrite,blocksize,naxes(2),nfound
  integer              :: group,npixels,bitpix,naxis,i,j,fpixel,un
  real                 :: nullval,diff_mat(3,2),perr
  real, allocatable    :: image(:,:), error(:,:)
  integer, allocatable :: seed(:)
  logical              :: anynull,simple,extend
  character(len=80)    :: filename

  call random_seed(size=Nrand)
  allocate(seed(Nrand))
  open(newunit=un,file="/dev/urandom",access="stream",&
       form="unformatted",action="read",status="old")
  read(un) seed
  close(un)
  call random_seed(put=seed)
  deallocate(seed)

  status=0
  call ftgiou(unit,status)
  filename='PUPPY.FITS'
  readwrite=0
  call ftopen(unit,filename,readwrite,blocksize,status)
  call ftgknj(unit,'NAXIS',1,2,naxes,nfound,status)
  call ftgidt(unit,bitpix,status)
  npixels=naxes(1)*naxes(2)
  group=1
  nullval=-999
  allocate(image(naxes(1),naxes(2)))
  allocate(error(naxes(1)+1,naxes(2)+1))
  call ftgpve(unit,group,1,npixels,nullval,image,anynull,status)
  call ftclos(unit, status)
  call ftfiou(unit, status)

  diff_mat=0.0
  diff_mat(3,1) = 2.0 
  diff_mat(1,2) = 1.0
  diff_mat(2,2) = 1.0
  diff_mat=diff_mat/5.0

  error=0.0
  perr=0
  do j=1,naxes(2)
    do i=1,naxes(1)
      p=max(min(image(i,j)+error(i,j),255.0),0.0)
      if (p < 127.0) then
        perr=p
        image(i,j)=0.0
      else
        perr=p-255.0
        image(i,j)=255.0
      endif
      call random_number(r)
      r=0.6*(r-0.5)
      error(i+1,j)=  error(i+1,j)  +perr*(diff_mat(3,1)+r)
      error(i-1,j+1)=error(i-1,j+1)+perr*diff_mat(1,2)
      error(i  ,j+1)=error(i ,j+1) +perr*(diff_mat(2,2)-r)
    end do
  end do

  call ftgiou(unit,status)
  blocksize=1
  filename='PUPPY-OUT.FITS'
  call ftinit(unit,filename,blocksize,status)
  simple=.true.
  naxis=2
  extend=.true.
  call ftphpr(unit,simple,bitpix,naxis,naxes,0,1,extend,status)
  group=1
  fpixel=1
  call ftppre(unit,group,fpixel,npixels,image,status)
  call ftclos(unit, status)
  call ftfiou(unit, status)

  deallocate(image)
  deallocate(error)
end program dither

Example output for the puppy image in OPs post:

OPs example output:

Answer 4

Ghostscript (with little help of ImageMagick)

Far from being my 'own new algorithm', but, sorry, could not resist it.

convert puppy.jpg puppy.pdf && \
convert puppy.jpg -depth 8 -colorspace Gray -resize 20x20! -negate gray:- | \
gs -q -sDEVICE=ps2write -o- -c \
    '<</Thresholds (%stdin) (r) file 400 string readstring pop 
       /HalftoneType 3 /Width 20 /Height 20
     >>sethalftone' \
    -f puppy.pdf | \
gs -q -sDEVICE=pngmono -o puppy.png -

Of course it works better without 'same size' restraint.

Answer 5

JAVA

Here is my submission. Takes a JPG image, calculates pixel per pixel luminosity (thanks to Bonan in this SO question) and then check it against a random pattern for knowing if the resulting pixel will be black or white. Darkerst pixels will be always black and brightest pixels will be always white to preserve image details.

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;

import javax.imageio.ImageIO;

public class DitherGrayscale {

    private BufferedImage original;
    private double[] threshold = { 0.25, 0.26, 0.27, 0.28, 0.29, 0.3, 0.31,
            0.32, 0.33, 0.34, 0.35, 0.36, 0.37, 0.38, 0.39, 0.4, 0.41, 0.42,
            0.43, 0.44, 0.45, 0.46, 0.47, 0.48, 0.49, 0.5, 0.51, 0.52, 0.53,
            0.54, 0.55, 0.56, 0.57, 0.58, 0.59, 0.6, 0.61, 0.62, 0.63, 0.64,
            0.65, 0.66, 0.67, 0.68, 0.69 };


    public static void main(String[] args) {
        DitherGrayscale d = new DitherGrayscale();
        d.readOriginal();
        d.dither();

    }

    private void readOriginal() {
        File f = new File("original.jpg");
        try {
            original = ImageIO.read(f);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void dither() {
        BufferedImage imRes = new BufferedImage(original.getWidth(),
                original.getHeight(), BufferedImage.TYPE_INT_RGB);
        Random rn = new Random();
        for (int i = 0; i < original.getWidth(); i++) {
            for (int j = 0; j < original.getHeight(); j++) {

                int color = original.getRGB(i, j);

                int red = (color >>> 16) & 0xFF;
                int green = (color >>> 8) & 0xFF;
                int blue = (color >>> 0) & 0xFF;

                double lum = (red * 0.21f + green * 0.71f + blue * 0.07f) / 255;

                if (lum <= threshold[rn.nextInt(threshold.length)]) {
                    imRes.setRGB(i, j, 0x000000);
                } else {
                    imRes.setRGB(i, j, 0xFFFFFF);
                }

            }
        }
        try {
            ImageIO.write(imRes, "PNG", new File("result.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

Other examples:

Also works with full color images:

Answer 6

CJam

lNl_~:H;:W;Nl;1N[{[{ri}W*]{2/{:+}%}:P~}H*]z{P}%:A;H{W{I2/A=J2/=210/[0X9EF]=I2%2*J2%+m>2%N}fI}fJ

95 bytes :)
It uses the ASCII PGM (P2) format with no comment line, for both input and output.

The method is very basic: it adds up squares of 2*2 pixels, converts to the 0..4 range, then uses a corresponding pattern of 4 bits to generate 2*2 black-and-white pixels.
That also means that the width and height must be even.

Sample:

And a random algorithm in only 27 bytes:

lNl_~*:X;Nl;1N{ri256mr>N}X*

It uses the same file format.

Sample:

And finally a mixed approach: random dithering with a bias towards a checkerboard pattern; 44 bytes:

lNl_~:H;:W;Nl;1NH{W{ri128_mr\IJ+2%*+>N}fI}fJ

Sample:

Answer 7

Python

The idea is following: The image gets divided in to n x n tiles. We calculate the average colour each of those tiles. Then we map the colour range 0 - 255 to the range 0 - n*n which gives us a new value v. Then we colour all pixels from that tile black, and randomly colour v pixels within that tile white. It is far from optimal but still gives us recognizable results. Depending on the resolution, it works usually best at n=2 or n=3. While in n=2 you can already find artefacts from the 'simulated colour depth, in case n=3 it can already get somewhat blurry. I assumed that the images should stay the same size, but you can of course also use this method and just double/triple the size of the generated image in order to get more details.

PS: I know that I am a bit late to the party, I remember that I did not have any ideas when the challenge started but now just had this brain wave=)

from PIL import Image
import random
im = Image.open("dog.jpg") #Can be many different formats.
new = im.copy()
pix = im.load()
newpix = new.load()
width,height=im.size
print([width,height])
print(pix[1,1])

window = 3 # input parameter 'n'

area = window*window
for i in range(width//window):     #loop over pixels
    for j in range(height//window):#loop over pixels
        avg = 0
        area_pix = []
        for k in range(window):
            for l in range(window):
                area_pix.append((k,l))#make a list of coordinates within the tile
                try:
                    avg += pix[window*i+k,window*j+l][0] 
                    newpix[window*i+k,window*j+l] = (0,0,0) #set everything to black
                except IndexError:
                    avg += 255/2 #just an arbitrary mean value (when were outside of the image)
                                # this is just a dirty trick for coping with images that have
                                # sides that are not multiples of window
        avg = avg/area
        # val = v is the number of pixels within the tile that will be turned white
        val = round(avg/255 * (area+0.99) - 0.5)#0.99 due to rounding errors
        assert val<=area,'something went wrong with the val'
        print(val)
        random.shuffle(area_pix) #randomize pixel coordinates
        for m in range(val):
            rel_coords = area_pix.pop()#find random pixel within tile and turn it white
            newpix[window*i+rel_coords[0],window*j+rel_coords[1]] = (255,255,255)

new.save('dog_dithered'+str(window)+'.jpg')

Results:

n=2:

n=3:

Answer 8

Java (1.4+)

I am not sure as to whether I am re-inventing the wheel here but I think it may be unique...

With limited random sequences

Pure random dithering

City image from Averroes's answer

The algorithm uses the concept of localized luminosity energy and normalizing to retain features. The initial version then used a random jitter to produce a dithered look over areas of similar luminosity. However it was not that visually appealing. To counter this, a limited set of limited random sequences are mapped to raw input pixel luminosity and samples are used iteratively and repeatedly yielding dithered looking backgrounds.

import java.awt.image.BufferedImage;
import java.io.File;
import javax.imageio.ImageIO;

public class LocalisedEnergyDitherRepeatRandom {

    static private final float EIGHT_BIT_DIVISOR=1.0F/256;
    private static final int KERNEL_SIZE_DIV_2 =4;
    private static final double JITTER_MULTIPLIER=0.01;
    private static final double NO_VARIANCE_JITTER_MULTIPLIER=1.5;
    private static final int RANDOM_SEQUENCE_LENGTH=10;
    private static final int RANDOM_SEQUENCE_COUNT=20;
    private static final boolean USE_RANDOM_SEQUENCES=true;

    public static void main(String args[]) throws Exception
    {
        BufferedImage image = ImageIO.read(new File("data/dog.jpg"));
        final int width = image.getWidth();
        final int height = image.getHeight();
        float[][][] yuvImage =convertToYUVImage(image);
        float[][][] outputYUVImage = new float[width][height][3];
        double circularKernelLumaMean,sum,jitter,outputLuma,variance,inputLuma;
        int circularKernelPixelCount,y,x,kx,ky;
        double[][] randomSequences = new double[RANDOM_SEQUENCE_COUNT][RANDOM_SEQUENCE_LENGTH];
        int[] randomSequenceOffsets = new int[RANDOM_SEQUENCE_COUNT];

        // Generate random sequences
        for (y=0;y<RANDOM_SEQUENCE_COUNT;y++)
        {
            for (x=0;x<RANDOM_SEQUENCE_LENGTH;x++)
            {
                randomSequences[y][x]=Math.random();
            }
        }

        for (y=0;y<height;y++)
        {
            for (x=0;x<width;x++)
            {
                circularKernelLumaMean=0;
                sum=0;
                circularKernelPixelCount=0;

                /// calculate the mean of the localised surrounding pixels contained in 
                /// the area of a circle surrounding the pixel.
                for (ky=y-KERNEL_SIZE_DIV_2;ky<y+KERNEL_SIZE_DIV_2;ky++)
                {
                    if (ky>=0 && ky<height)
                    {
                        for (kx=x-KERNEL_SIZE_DIV_2;kx<x+KERNEL_SIZE_DIV_2;kx++)
                        {
                            if (kx>=0 && kx<width)
                            {
                                double distance= Math.sqrt((x-kx)*(x-kx)+(y-ky)*(y-ky));

                                if (distance<=KERNEL_SIZE_DIV_2)
                                {
                                    sum+=yuvImage[kx][ky][0];
                                    circularKernelPixelCount++;
                                }
                            }
                        }
                    }
                }

                circularKernelLumaMean=sum/circularKernelPixelCount;

                /// calculate the variance of the localised surrounding pixels contained in 
                /// the area of a circle surrounding the pixel.
                sum =0;

                for (ky=y-KERNEL_SIZE_DIV_2;ky<y+KERNEL_SIZE_DIV_2;ky++)
                {
                    if (ky>=0 && ky<height)
                    {
                        for (kx=x-KERNEL_SIZE_DIV_2;kx<x+KERNEL_SIZE_DIV_2;kx++)
                        {
                            if (kx>=0 && kx<width)
                            {
                                double distance= Math.sqrt((x-kx)*(x-kx)+(y-ky)*(y-ky));

                                if (distance<=KERNEL_SIZE_DIV_2)
                                {
                                    sum+=Math.abs(yuvImage[kx][ky][0]-circularKernelLumaMean);
                                }
                            }
                        }
                    }
                }

                variance = sum/(circularKernelPixelCount-1);

                if (variance==0)
                {
                    // apply some jitter to ensure there are no large blocks of single colour
                    inputLuma=yuvImage[x][y][0];
                    jitter = Math.random()*NO_VARIANCE_JITTER_MULTIPLIER;
                }
                else
                {
                    // normalise the pixel based on localised circular kernel
                    inputLuma = outputYUVImage[x][y][0]=(float) Math.min(1.0, Math.max(0,yuvImage[x][y][0]/(circularKernelLumaMean*2)));
                    jitter = Math.exp(variance)*JITTER_MULTIPLIER;
                }

                if (USE_RANDOM_SEQUENCES)
                {
                    int sequenceIndex =(int) (yuvImage[x][y][0]*RANDOM_SEQUENCE_COUNT);
                    int sequenceOffset = (randomSequenceOffsets[sequenceIndex]++)%RANDOM_SEQUENCE_LENGTH;
                    outputLuma=inputLuma+randomSequences[sequenceIndex][sequenceOffset]*jitter*2-jitter;
                }
                else
                {
                    outputLuma=inputLuma+Math.random()*jitter*2-jitter;
                }


                // convert 8bit luma to 2 bit luma
                outputYUVImage[x][y][0]=outputLuma<0.5?0:1.0f;
            }
        }

        renderYUV(image,outputYUVImage);
        ImageIO.write(image, "png", new File("data/dog.jpg.out.png"));
    }

      /**
       * Converts the given buffered image into a 3-dimensional array of YUV pixels
       * @param image the buffered image to convert
       * @return 3-dimensional array of YUV pixels
       */
      static private float[][][] convertToYUVImage(BufferedImage image)
      {
        final int width = image.getWidth();
        final int height = image.getHeight();
        float[][][] yuv = new float[width][height][3];
        for (int y=0;y<height;y++)
        {
          for (int x=0;x<width;x++)
          {
            int rgb = image.getRGB( x, y );
            yuv[x][y]=rgb2yuv(rgb);
          }
        }
        return yuv;
      }

      /**
       * Renders the given YUV image into the given buffered image.
       * @param image the buffered image to render to
       * @param pixels the YUV image to render.
       * @param dimension the
       */
      static private void renderYUV(BufferedImage image, float[][][] pixels)
      {
        final int height = image.getHeight();
        final int width = image.getWidth();
        int rgb;

        for (int y=0;y<height;y++)
        {
          for (int x=0;x<width;x++)
          {

            rgb = yuv2rgb( pixels[x][y] );
            image.setRGB( x, y,rgb );
          }
        }
      }

      /**
       * Converts a RGB pixel into a YUV pixel
       * @param rgb a pixel encoded as 24 bit RGB
       * @return array representing a pixel. Consisting of Y,U and V components
       */
      static float[] rgb2yuv(int rgb)
      {
        float red = EIGHT_BIT_DIVISOR*((rgb>>16)&0xFF);
        float green = EIGHT_BIT_DIVISOR*((rgb>>8)&0xFF);
        float blue = EIGHT_BIT_DIVISOR*(rgb&0xFF);

        float Y = 0.299F*red + 0.587F * green + 0.114F * blue;
        float U = (blue-Y)*0.565F;
        float V = (red-Y)*0.713F;

        return new float[]{Y,U,V};
      }

      /**
       * Converts a YUV pixel into a RGB pixel
       * @param yuv array representing a pixel. Consisting of Y,U and V components
       * @return a pixel encoded as 24 bit RGB
       */
      static int yuv2rgb(float[] yuv)
      {
        int red = (int) ((yuv[0]+1.403*yuv[2])*256);
        int green = (int) ((yuv[0]-0.344 *yuv[1]- 0.714*yuv[2])*256);
        int blue = (int) ((yuv[0]+1.77*yuv[1])*256);

        // clamp to 0-255 range
        red=red<0?0:red>255?255:red;
        green=green<0?0:green>255?255:green;
        blue=blue<0?0:blue>255?255:blue;

        return (red<<16) | (green<<8) | blue;
      }

}

Answer 9

Dyalog APL

This is an implementation of ordered dither with a special dither array.

The input format is a restricted form of raster PGM while it is also the default style produced by Netpbm programs that requires no comment line, file header separated by newline character rather than arbitrary whitespace, and assumes "maxval" to be 255, so the file can be handled easily with APL's ⎕MAP system function.

The output format satisfies raster PBM specification.

This program can dither images as large as 3000×2000 in very short time, however for larger image it needs more than default workspace size.

∇img←readpgm file;data;size
 data←83 ¯1 ⎕MAP file
⍝ drop magic
 data←(⊢↓⍨⍳∘10)data
 size←⌽⍎⎕UCS ¯1↓(⊢↑⍨⍳∘10)data
 img←size⍴256|(⊢↓⍨⍳∘10)⍣2⊢data
∇

∇img writepbm file;data;size;h;s;tie
 tie←file(⎕NCREATE⍠'IfExists' 'Error')0
 h←10,⍨⎕UCS'P4 ',⍕size←⌽⍴img
 tie ⎕ARBOUT h
 s←8×⌈8÷⍨⊃size
 data←,⍉s↑⍉img
 data←2⊥⍉data⍴⍨8,⍨8÷⍨≢data
 tie ⎕ARBOUT data
 ⎕NUNTIE tie
∇

da←1 8⍴51 25 61 10 45 57 8 16
da⍪←58 6 34 23 1 36 49 30
da⍪←44 32 29 14 41 62 20 12
da⍪←2 21 60 52 47 4 24 55
da⍪←50 9 18 7 38 28 15 40
da⍪←37 56 26 43 59 11 53 35
da⍪←46 13 31 3 48 22 5 63
da⍪←0 19 33 54 17 39 27 42

dither←{
    ⎕IO←0
    x y←⍴⍵
    a b←⍴⍺
    (63×⍵÷255)<(,⍺)[(x y⍴y⍴⍳b)+⍉y x⍴x⍴b×⍳a]
}

'out.pbm' writepbm⍨ da dither readpgm 'input.pgm'

Answer 10

Any file format you want is fine.

Let's define a very compact, theoretical file format for this question as any of the existing file formats have too much overhead to write a quick answer for.

Let the first four bytes of the image file define the width and height of the image in pixels, respectively:

00000001 00101100 00000001 00101100
width: 300 px     height: 300 px

followed by w * h bytes of grayscale values from 0 to 255:

10000101 10100101 10111110 11000110 ... [89,996 more bytes]

Then, we can define a piece of code in Python (145 bytes) that will take this image and do:

import random
f=open("a","rb");g=open("b","wb");g.write(f.read(4))
for i in f.read():g.write('\xff' if ord(i)>random.randint(0,255) else '\x00')

which "dithers" by returning white or black with probability equal to the grayscale value of that pixel.

---

Applied on the sample image, it gives something like this:

It's not too pretty, but it does look very similar when scaled down in a preview, and for just 145 bytes of Python, I don't think you can get much better.

Answer 11

Cobra

Takes a 24-bit or 32-bit PNG/BMP file (JPG produces output with some greys in it). It is also extensible to files containing color.

It uses speed-optimized ELA to dither the image into 3-bit color, which will return as black/white when given your test image.

Did I mention that it's really fast?

use System.Drawing
use System.Drawing.Imaging
use System.Runtime.InteropServices
use System.IO

class BW_Dither

    var path as String = Directory.getCurrentDirectory to !
    var rng = Random()

    def main
        file as String = Console.readLine to !
        image as Bitmap = Bitmap(.path+"\\"+file)
        image = .dither(image)
        image.save(.path+"\\test\\image.png")

    def dither(image as Bitmap) as Bitmap

        output as Bitmap = Bitmap(image)

        layers as Bitmap[] = @[ Bitmap(image), Bitmap(image), Bitmap(image),
                                Bitmap(image), Bitmap(image), Bitmap(image),
                                Bitmap(image)]

        layers[0].rotateFlip(RotateFlipType.RotateNoneFlipX)
        layers[1].rotateFlip(RotateFlipType.RotateNoneFlipY)
        layers[2].rotateFlip(RotateFlipType.Rotate90FlipX)
        layers[3].rotateFlip(RotateFlipType.Rotate90FlipY)
        layers[4].rotateFlip(RotateFlipType.Rotate90FlipNone)
        layers[5].rotateFlip(RotateFlipType.Rotate180FlipNone)
        layers[6].rotateFlip(RotateFlipType.Rotate270FlipNone)

        for i in layers.length, layers[i] = .dither_ela(layers[i])

        layers[0].rotateFlip(RotateFlipType.RotateNoneFlipX)
        layers[1].rotateFlip(RotateFlipType.RotateNoneFlipY)
        layers[2].rotateFlip(RotateFlipType.Rotate270FlipY)
        layers[3].rotateFlip(RotateFlipType.Rotate270FlipX)
        layers[4].rotateFlip(RotateFlipType.Rotate270FlipNone)
        layers[5].rotateFlip(RotateFlipType.Rotate180FlipNone)
        layers[6].rotateFlip(RotateFlipType.Rotate90FlipNone)

        vals = List<of List<of uint8[]>>()
        data as List<of uint8[]> = .getData(output)
        for l in layers, vals.add(.getData(l))
        for i in data.count, for c in 3
            x as int = 0
            for n in vals.count, if vals[n][i][c] == 255, x += 1
            if x > 3.5, data[i][c] = 255 to uint8
            if x < 3.5, data[i][c] = 0 to uint8

        .setData(output, data)
        return output

    def dither_ela(image as Bitmap) as Bitmap

        error as decimal[] = @[0d, 0d, 0d]
        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadWrite, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            for i in 3
                error[i] -= bytes[position + i]
                if Math.abs(error[i] + 255 - bytes[position + i]) < Math.abs(error[i] - bytes[position + i])
                    bytes[position + i] = 255 to uint8
                    error[i] += 255
                else, bytes[position + i] = 0 to uint8

        Marshal.copy(bytes, 0, pointer, image_data.stride * image.height)
        image.unlockBits(image_data)
        return image

    def getData(image as Bitmap) as List<of uint8[]>

        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadOnly, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pixels as List<of uint8[]> = List<of uint8[]>()
        for i in image.width * image.height, pixels.add(nil)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        count as int = 0
        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            if pfs == 4, alpha as uint8 = bytes[position + 3]
            else, alpha as uint8 = 255
            pixels[count] = @[
                                bytes[position + 2], #red
                                bytes[position + 1], #green
                                bytes[position],     #blue
                                alpha]               #alpha
            count += 1

        image.unlockBits(image_data)
        return pixels

    def setData(image as Bitmap, pixels as List<of uint8[]>)
        if pixels.count <> image.width * image.height, throw Exception()
        rectangle as Rectangle = Rectangle(0, 0, image.width, image.height)
        image_data as BitmapData = image.lockBits(rectangle, ImageLockMode.ReadWrite, image.pixelFormat) to !
        pointer as IntPtr = image_data.scan0
        bytes as uint8[] = uint8[](image_data.stride * image.height)
        pfs as int = Image.getPixelFormatSize(image.pixelFormat) // 8
        Marshal.copy(pointer, bytes, 0, image_data.stride * image.height)

        count as int = 0
        for y as int in image.height, for x as int in image.width
            position as int = (y * image_data.stride) + (x * pfs)
            if pfs == 4, bytes[position + 3] = pixels[count][3] #alpha
            bytes[position + 2] = pixels[count][0]              #red
            bytes[position + 1] = pixels[count][1]              #green
            bytes[position] = pixels[count][2]                  #blue
            count += 1

        Marshal.copy(bytes, 0, pointer, image_data.stride * image.height)
        image.unlockBits(image_data)

Answer 12

Java

Low level code, using PNGJ and a noise addition plus basic diffusion. This implementation requires a grayscale 8-bits PNG source.

import java.io.File;
import java.util.Random;

import ar.com.hjg.pngj.ImageInfo;
import ar.com.hjg.pngj.ImageLineInt;
import ar.com.hjg.pngj.PngReaderInt;
import ar.com.hjg.pngj.PngWriter;

public class Dither {

    private static void dither1(File file1, File file2) {
        PngReaderInt reader = new PngReaderInt(file1);
        ImageInfo info = reader.imgInfo;
        if( info.bitDepth != 8 && !info.greyscale ) throw new RuntimeException("only 8bits grayscale valid");
        PngWriter writer = new PngWriter(file2, reader.imgInfo);
        ImageLineInt line2 = new ImageLineInt(info);
        int[] y = line2.getScanline();
        int[] ye = new int[info.cols];
        int ex = 0;
        Random rand = new Random();
        while(reader.hasMoreRows()) {
            int[] x = reader.readRowInt().getScanline();
            for( int i = 0; i < info.cols; i++ ) {
                int t = x[i] + ex + ye[i];
                y[i] = t > rand.nextInt(256) ? 255 : 0;
                ex = (t - y[i]) / 2;
                ye[i] = ex / 2;
            }
            writer.writeRow(line2);
        }
        reader.end();
        writer.end();
    }

    public static void main(String[] args) {
        dither1(new File(args[0]), new File(args[1]));
        System.out.println("See output in " + args[1]);
    }

}

(Add this jar to your build path if you want to try it).

As a bonus: this is extremely efficient in memory usage (it only stores three rows) so it could be used for huge images.

Answer 13

Python

The code is quite bad, so I'll try to explain the algorithm. For each pixel, it stores the brightness of the pixel in the variable brightness, and changes brightness based on the values of x % 2 and y % 2, where x and y are coordinates of that pixel. This creates a typical two by two regular dithering pattern. Then, brightness is randomly changed by some amount to hide banding and strongly visible patterns created by the dithering algorithm.

Finally, brightness is changed by the difference between the average brightness of the current pixel and the average brightness of the pixel around it. This makes details and outlines more visible, since small groups of pixels that are very different from their surroundings are more likely to get a different color than their surroundings. The brightness is then rounded to 0 (black) or 1 (white).

The program has four parameters that can be changed to change the result: dither_details, which determines how likely pixels with a different brightness than their surroundings are to get a different color than their surroundings; dither_regular, which determines how strong the typical two by two dithering pattern is, dither_random, which determines the strength of the random dithering; and s, which determines how big an area of its surrounding the pixels are compared to.

When dither_details equals 999 and s equals 2, the program gives a result quite similar to @Moogie's submission (the rectangle-like patterns are likely a product of image compression):

import matplotlib.image as mplimg
import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy

image = mplimg.imread("pup.png")

new_im = [
    [0 for x in range(len(image[0]))]
for y in range(len(image))]

def avg(x, y, f):
    sum_ = 0
    n = 0
    
    for x1 in range(x, x + f):
        for y1 in range(y, y + f):
            
            if x1 < 0 or x1 >= len(image[0]) or y1 < 0 or y1 >= len(image):
                continue
            
            n += 1
            sum_ += image[y1][x1]

    return sum_ / n

dither_details = 3.0
dither_regular = 0.15
dither_random = 0.03
s = 3

for x in range(len(image[0])):
    for y in range(len(image)):
        
        brightness = image[y][x]
        
        if x % 2 == 0 and y % 2 == 0:
            brightness += dither_regular
        elif x % 2 == 1 and y % 2 == 1:
            brightness += dither_regular / 2
        elif x % 2 == 0 and y % 2 == 1:
            brightness -= dither_regular
        elif x % 2 == 1 and y % 2 == 0:
            brightness -= dither_regular / 2
        
        brightness += numpy.random.normal(scale = dither_random)
        
        average_brightness = avg(x - s, y - s, s * 2 + 1)
        brightness += image[y][x] * dither_details - average_brightness * dither_details
        
        new_im[y][x] = 0 if brightness < 0.5 else 1
    
dpi = 16
mpl.rcParams['savefig.dpi'] = dpi * 16
plt.figure(figsize=(len(image[0]) / dpi, len(image) / dpi), dpi = dpi * 16)
plt.axis("off")
plt.imshow(new_im, cmap = "gray", interpolation = "nearest")
plt.savefig("dither.png", bbox_inches="tight")
plt.show()

Answer 14

Java

Just a simple RNG-based algorithm, plus some logic for dealing with color images. Has probability b of setting any given pixel to white, sets it to black otherwise; where b is that pixel's original brightness.

import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;

import javax.imageio.ImageIO;


public class Ditherizer {
    public static void main(String[]a) throws IOException{
        Scanner input=new Scanner(System.in);
        Random rand=new Random();
        BufferedImage img=ImageIO.read(new File(input.nextLine()));
        for(int x=0;x<img.getWidth();x++){
            for(int y=0;y<img.getHeight();y++){
                Color c=new Color(img.getRGB(x, y));
                int r=c.getRed(),g=c.getGreen(),b=c.getBlue();
                double bright=(r==g&&g==b)?r:Math.sqrt(0.299*r*r+0.587*g*g+0.114*b*b);
                img.setRGB(x,y,(rand.nextInt(256)>bright?Color.BLACK:Color.WHITE).getRGB());    
            }
        }
        ImageIO.write(img,"jpg",new File(input.nextLine()));
        input.close();
    }
}

Here's a potential result for the dog image:

Answer 15

JavaScript (Node.js), 28 bytes

x=>x.map(t=>t>Math.random())

Try it online!

Trying to golf one