Welcome, guest | Sign In | My Account | Store | Cart

Floyd-Steinberg dithering is an image dithering algorithm (see http://en.wikipedia.org/wiki/Floyd-Steinberg for more details). While the algorithm is mainly for image manipulation, I use it to create random locations for sensor networt devices.

Python, 69 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#!/usr/bin/env python

""" Floyd-Steinberg Dithering algorithm, see:
    http://en.wikipedia.org/wiki/Floyd-Steinberg
"""

import sys
import os

from math import sqrt
from Numeric import *

fs_coeffs = [7.0,3.0,5.0,1.0]

class Dither:

    def __init__(self,pixels,xl,yl):

        self.pixels = pixels
        self.xl = xl
        self.yl = yl

        self.fs_dither()

    def _find_closest_palette_color(self, oldpixel): 
        return int(oldpixel + 0.5)

    def fs_dither(self):

        A,B,G,S = map(lambda x : float(x)/16.0, fs_coeffs)

        for y in xrange(self.yl):
            for x in xrange(self.xl):
                oldpixel = self.pixels[x][y]
                newpixel = self._find_closest_palette_color(oldpixel)
                self.pixels[x][y] = float(newpixel)
                quant_error = float(oldpixel - newpixel)
                if (x < self.xl - 1):
                    self.pixels[x+1][y] += (A * quant_error)
                if (x > 0) and (y < self.yl - 1):
                    self.pixels[x-1][y+1] += (B * quant_error)
                if (y < self.yl - 1):
                    self.pixels[x][y+1] += (G * quant_error)
                if (x < self.xl - 1) and (y < self.yl - 1):
                    self.pixels[x+1][y+1] += (S * quant_error)


if __name__=='__main__':

    """ Form an xl-by-yl array """
    xl = yl = 20
    initpixels = reshape((0.5,) * xl * yl ,[xl,yl])

    """ Dither """
    D = Dither(initpixels,xl,yl)
    print D.pixels

    """ Import the R stats package libraries
        and create a matrix of the dither pixels
    """
    import rpy as R
    z_lst = []
    [z_lst.extend(i) for i in D.pixels]
    z = R.r.matrix(z_lst, byrow=R.r.FALSE, ncol=xl)
            
    """ Create a plot of the dithered image """
    R.r.pdf("dither_plot.pdf")
    R.r.image(range(xl),range(yl),z)
    R.r.dev_off()

In this example, the "image" is just a flat 50% grey scale surface. The dithered output yields a chequered pattern.

1 comment

Agnius Vasiliauskas 13 years, 5 months ago  # | flag

Nice script, also should be good to have ordered dithering algorithm sample.