[Printers] Quick detection and measurement of dot patterns using FFT

[Ralf Muschall]

I just tried some math in order to start automatic detection of the
patterns (for the C5016N).

After scanning some image (color, 600dpi) and storing (as PGM-raw) the
"K" layer of the CMYK-separation mentioned earlier, I ran it thru the
program appended at the end of this posting (which takes as arguments
the input and output filenames).

The programm essentially computes the spectrum (i.e. FFT of data),
takes the norm (i.e. ||x||^2), then the FFT of that.

The lines autocorr[:,0]=0, autocorr[0,:]=0 and the 16th root serve to
avoid the swamping of the output by the fact that "nothing correlates
highly with nothing (which is what almost the whole picture consists
of)" and that everything perfectly correlates with itself (i.e. at
shift=0).  As output greymap, one gets a rectangular pattern of bright
spots.  The 18th (and 36th etc.)  spot-column are particularly bright,
and the horizontal distance between adjacent spots is about 18 pixels,
which coincides with the yellow dot raster.

The vertical display which I saw was wrong due to a bug in the program
found only after being away from the machine.

################ save as something.py ################

import sys
import Image
import numarray
import numarray.fft

def slurp_greymap(fn):
    im=Image.open(fn)
    si1=im.size[1] # height
    si0=im.size[0] # width
    return numarray.array(im.getdata(),shape=(si1,si0)) # rows first

def write_greymap(ivals2,fn):
    size=numarray.shape(ivals2)
    im2=Image.new("L",(size[1],size[0])) # swapped as above
    mi=ivals2.min()
    ma=ivals2.max()
    val_offset=offset=-mi*255.0/(ma-mi)
    val_scale=255.0/(ma-mi)
    im2.putdata(numarray.reshape(ivals2,(-1,)),
                offset=val_offset,scale=val_scale)
    im2.save(fn)

def work(fn_in,fn_out):
    gm=slurp_greymap(fn_in)
    gm_ft=numarray.fft.fft(numarray.fft.fft(gm,axis=0),axis=1)
    gm_pwr=gm_ft*numarray.conjugate(gm_ft)
    autocorr=numarray.abs(numarray.fft.fft(gm_pwr))
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    for i in xrange(4):
        autocorr=numarray.sqrt(autocorr)
    autocorr[0,:]=0
    autocorr[:,0]=0
    write_greymap(autocorr,fn_out)

work(sys.argv[1],sys.argv[2])

################ end of something.py ################

Be warned that the program eats lots of memory - for a whole A4 page,
my 2GB machine started swapping (which might be avoided by smarter
coding, but I wanted it to see ASAP).

PS: The line marked #^^^^^^^^ is buggy - I should have done 2 FFTs
(one for each dimension, as 2 lines above), but I can't check that now
(I'm away from that machine).  This should explain the very strange
things I saw vertically.

The goal of this kind of program is as following:

1. detect the raster size as precisely as possible

2. detect the size of the pattern (e.g. 18x23)

3. (todo): cut the whole picture into rectangles of the size
   determined in (2) and average them (or do something smarter than
   the average, e.g. removing dirt or even the content of a real
   picture over which the yellow dots are distributed)

4. detect the dots and output them as a table of 0/1

Ralf
-- 
GS d->? s:++>+++ a+ C++++ UL+++ UH++ P++ L++ E+++ W- N++ o-- K-
w--- !O M- V- PS+>++ PE Y+>++ PGP+ !t !5 !X !R !tv  b+++ DI+++
D? G+ e++++ h+ r? y?