Converting BMP image to set of instructions for a

Question

I have a plotter like this one:

The task which I have to implement is conversion of 24 bits BMP to set of instructions for this plotter. In the plotter I can change 16 common colors. The first complexity which I face is the colors reduction. The second complexity which I face is how to transform pixels into set of drawing instructions.

As drawing tool brush with oil paint will be used. It means that plotter drawing lines will not be so tiny and they will be relatively short.

Please suggest algorithms which can be used for solving this image data conversion problem?

Some initial results:

Answer 1

Dithering

Well I got some time for this today so here the result. You did not provide your plotter color palette so I extracted it from your resulting images but you can use any. The idea behind dithering is simple our perception integrates color on area not individual pixels so you have to use some accumulator of color difference of what is rendered and what should be rendered instead and add this to next pixel ...

This way the area have approximately the same color but only discrete number of colors are used in real. The form of how to update this info can differentiate the result branching dithering to many methods. The simple straightforward is this:

1. reset color accumulator to zero
2. process all pixels
   1. for each pixel add its color to accumulator
   2. find closest match of the result in your palette
   3. render selected palette color
   4. substract selected palette color from accumulator

Here your input image (I put them together):

Here result image for your source:

The color squares in upper left corner is just palette I used (extracted from your image).

Here code (C++) I do this with:

picture pic0,pic1,pic2;
    // pic0 - source img
    // pic1 - source pal
    // pic2 - output img
int x,y,i,j,d,d0,e;
int r,g,b,r0,g0,b0;
color c;
List<color> pal;
// resize output to source image size clear with black
pic2=pic0; pic2.clear(0);
// create distinct colors pal[] list from palette image
for (y=0;y<pic1.ys;y++)
 for (x=0;x<pic1.xs;x++)
    {
    c=pic1.p[y][x];
    for (i=0;i<pal.num;i++) if (pal[i].dd==c.dd) { i=-1; break; }
    if (i>=0) pal.add(c);
    }
// dithering
r0=0; g0=0; b0=0;   // no leftovers
for (y=0;y<pic0.ys;y++)
 for (x=0;x<pic0.xs;x++)
    {
    // get source pixel color
    c=pic0.p[y][x];
    // add to leftovers
    r0+=WORD(c.db[picture::_r]);
    g0+=WORD(c.db[picture::_g]);
    b0+=WORD(c.db[picture::_b]);
    // find closest color from pal[]
    for (i=0,j=-1;i<pal.num;i++)
        {
        c=pal[i];
        r=WORD(c.db[picture::_r]);
        g=WORD(c.db[picture::_g]);
        b=WORD(c.db[picture::_b]);
        e=(r-r0); e*=e; d =e;
        e=(g-g0); e*=e; d+=e;
        e=(b-b0); e*=e; d+=e;
        if ((j<0)||(d0>d)) { d0=d; j=i; }
        }
    // get selected palette color
    c=pal[j];
    // sub from leftovers
    r0-=WORD(c.db[picture::_r]);
    g0-=WORD(c.db[picture::_g]);
    b0-=WORD(c.db[picture::_b]);
    // copy to destination image
    pic2.p[y][x]=c;
    }
// render found palette pal[] (visual check/debug)
x=0; y=0; r=16; g=pic2.xs/r; if (g>pal.num) g=pal.num;
for (y=0;y<r;y++)
 for (i=0;i<g;i++)
  for (c=pal[i],x=0;x<r;x++)
   pic2.p[y][x+(i*r)]=c;

where picture is my image class so here some members:

• xs,ys resolution
• color p[ys][xs] direct pixel access (32bit pixel format so 8 bit per channel)
• clear(DWORD c) fills image with color c

The color is just union of DWORD dd and BYTE db[4] for simple channel access.

The List<> is my template (dynamic array/list>

• List<int> a is the same as int a[].
• add(b) add b to it at the end of list
• num is number of items in list

Now to avoid too many dots (for the lifespan of your plotter sake) you can use instead different line patterns etc but that needs a lot of trial/error ... For example you can count how many times a color is used in some area and from that ratio use different filling patterns (based on lines). You need to choose between quality of image and speed of rendering/durability ...

Without more info about your plotter capabilities (speeds, method of tool change,color combination behavior) is hard to decide best method of forming control stream. My bet is you change the colors manually so you will render each colors at once. So extract all pixels with the color of first tool merge adjacent pixels to lines/curves and render ... then move to next tool color ...