3

I have a plotter like this one: PloterXY device.

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:

Flower 1 - colors reduction.

Flower 2 - colors reduction.

Flower 3 - colors reduction.

Todor Balabanov
  • 376
  • 3
  • 6
  • 17
  • 2
    google would help you for sure. http://stackoverflow.com/questions/622573/how-do-i-reduce-a-bitmap-to-a-known-set-of-rgb-colours For the conversion to your plotter it will highly depend on what images you have. You would vectorize a character differently from a flower – Piglet Apr 17 '16 at 10:50
  • 2
    you do not need to loose colors use dithering ...The vectorisation depends on what you want ... just outlines or full filing ... also it gretly depends on the image content rel life photo if different then cartoon sketch... if you are not limited to bitmap then you can also use directly 2D vector formats like svg,wmf,emf,dwg,... add image example – Spektre Apr 17 '16 at 11:16
  • I will use real photo images. What I am thinking for is some way of better colors reduction than standard algorithms. For example GIMP has very well implemented colors reduction module, but it is general purpose colors reduction. I will need to do image vectorization and I am wondering is there are ways to achieve better reduced colors related with the specifics of my task. – Todor Balabanov Apr 18 '16 at 06:45
  • As a starter you should explain what _are_ the available drawing instructions... – fjardon Apr 18 '16 at 13:32
  • 1
    I guess the time/cost of changing colours relative to the time to move the plotter head is also a determining factor in how you should plot - so you would need to identify the plotter and its User Manual. – Mark Setchell Apr 22 '16 at 11:31
  • what colors you have and are they combinable (if you draw more colors over the same area do they merge together (aditive (RGB)/subsractive(CMY))? or the last used (top-est) will overwrite the previous? dithering requires a lot of dots which can significantly reduce plotter lifetime and increase rendering time. The amount of color is constant (no PWM valves just centropens)? – Spektre Apr 23 '16 at 12:55
  • Mark Setchell, thnaks for the comment. This is the plotter: http://www.makeblock.cc/xy-plotter-robot-kit/ It is relatively slow device. I will have 16 common colors: https://gchart.googlecode.com/svn/trunk/doc/com/googlecode/gchart/client/doc-files/gchartexample10.png The change of the colors will be very slow process, because the oil paint needs time to dry. Spektre, thanks for the comment. I can draw one color over another. – Todor Balabanov Apr 27 '16 at 11:15

1 Answers1

6

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):

input

Here result image for your source:

result

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 ...

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • @MarkSetchell If you liked this then also take a look at [scalable dithering](http://stackoverflow.com/a/36839144/2521214). Just uploaded new animated GIF there. – Spektre Apr 26 '16 at 09:05
  • Spektre, thank you very much, amazingly good answer. I did not supply too much initila information with purpose. I had wanted to achieve something like brain storming session in order to collect new ideas. Here you can see more details about the way how I am solving the problem until now: https://github.com/TodorBalabanov/EllipsesImageApproximator – Todor Balabanov Apr 27 '16 at 11:25
  • 1
    Nice algo. I like it. It got some flaws (like producing waves), but it's realy simple and allows quite fast execution. – Raffzahn Jan 10 '19 at 12:26
  • @Raffzahn yep ... btw just a slight adjustment of the order of processed pixels can avoid line like artifacts ... like doing squares 8x8 pixels and clearing the accumulated error afterwards ... Its also very good for BW (without any adjustments) see [Python: How to implement Binary Filter on RGB image? (algorithm)](https://stackoverflow.com/a/53812614/2521214) I use this algo for RT GIF encoding ... any of the animated GIF used in my answers has been done by it ... :) – Spektre Jan 10 '19 at 17:26
  • @Spektre Sure, then again, any additional filtering will not only improve the image but also produce a drastic reduction in performance due more complex data fetces and calculation. It **really** like above, as it can be implemented in a few lines of assembly - possibly less than the C code above :)) That's a great archievement to me. – Raffzahn Jan 10 '19 at 17:30
  • @Raffzahn yep especially using the SSE/SIMD instructions like saturated addition ... doing all color channels by single instruction at once :) – Spektre Jan 10 '19 at 17:31
  • @Spektre Naa, not the fancy stuff, real assembly, like 6502 or 8086. Fiting such to modern processors that have been especially made to do so is cheating :)) – Raffzahn Jan 10 '19 at 17:35
  • 1
    @Raffzahn :) ... I remember the Z80 days of coding and translating on paper and then poke into RAM and randomize usr :) ... and hours of searching for the bug in it – Spektre Jan 10 '19 at 17:38
  • 1
    @TodorBalabanov take a look at similar QA [Painting stroke generation algorithm for robot arm](https://stackoverflow.com/a/72907757/2521214) – Spektre Jul 08 '22 at 11:23