2006sep: An email or two corrects a problem or two with the code. Jump to the end of this article for details.

This article details a bitmap to vector algorithm I created for a larger program (not discussed here). This algorithm may already exist in a purer state elsewhere, it may be flawed, incomplete, or otherwise mutated. I make no claim to its functionality or efficiency; other algorithms probably exist that are better, faster, stronger. If you are stupid enough to put this algorithm into some sort of medical care device without checking the math and it kills someone, it's your problem, not mine. Also this applies to transportation, the military, and anything that could generate a lawsuit with me sitting on the wrong end of the barrel. It's not going to happen, cholly. Your frivolous "wrongful death" suit has been disclaimed.

If you want something that estimates curves, creates splines, etc, then you should definitely go look somewhere else. Maybe I will need to add this in the future, like a year from now. I doubt it.

But, if you are looking for something that encodes a bitmap into a straight-line vector table, then this algorithm will maybe help you.

I wouldn't count on this page being here forever, even though I have no intention of removing it. If you are remotely interested, grab it now and store it on your little hard drive. There's also a note at the end, someone sent in an email correcting a problem. I had heard there was a problem with the algorithm years ago, but I never got around to checking it. So I'm guessing this email fixes that problem. I haven't checked it either.

There are other algorithms for bitmap-to-vector processing. I have not used them because they are either patented or oddly useless. An example of the former, Patent #4,740,904, is available via either the IBM patent server or the U.S. patent server. Perhaps you would like to license this from Mr. Nagle or Autodesk. Perhaps it is more robust for your computational needs. More "macho". I cannot say at this time.

Sample code is included which looks suspiciously like Delphi Pascal with a lot of the variable declarations and frilly shit removed. There is also a full version of the sample code with declarations and all that so you don't have to cut and paste from this page.

The vectors are encoded as an array of records; there are better ways to do this (this is completely obvious, but so I can avoid answering any questions about this, a "better way" and probably the "best" way would be "linked lists"), but with this method it is easier to understand and follow along in your own songbook.

There are three main procedures.

The first is "Create Vector". The bitmap is translated to vector notation as soon as possible. That is, each single bit is converted into four directional vectors, joined as a square.

The second is "Simplify Vector". The vector field is simplified by checking for duplicates and removing the vectors that are lying on top of each other (these would be adjacent bits in the bitmap). This is done by referring to the links to the identical vectors and merging these, much like one would remove an item from a linked list.

The third and last is "Lengthen Vector". The algorithm goes through the modified vector field looking for joined parallel vectors and turns these multiple vectors into a single vector.

Hell, you could probably write your own program now.

We (you and I) will now consider each of these procedures, and their associated subroutines, in turn.


Create Vector.

The bitmap is represented as an array "a" that is MAXSIZEX by MAXSIZEY in dimension.

For each bit in the bitmap that is turned on, you will want to create a representational square vector for it.

procedure createvector;

for j := 1 to MAXSIZEX do    
  for k := 1 to MAXSIZEY do
    if a[j,k] = 1 then
      addsquarevector(j,k);

Addsquarevector.

V is declared as an array of records, each representing a vector. Each record has fields for the starting (sx,sy) and ending (ex,ey) points, and pointers to both the previous (prev) and next (next) vectors. Each vector also has a status field indicating whether the vector is alive (0) or dead (negative). Vnum stands for the the total number of vectors.

procedure addsquarevector(j,k: integer);

var
  m: integer;

begin
  Vnum := Vnum + 1;

  V[Vnum].prev := Vnum + 3;
  V[Vnum].sx := j;     V[Vnum].sy := k;
  V[Vnum].ex := j + 1; V[Vnum].ey := k;
  V[Vnum].next := Vnum + 1;
  V[Vnum].status := 0;

  Vnum := Vnum + 1;

  V[Vnum].prev := Vnum - 1;
  V[Vnum].sx := j + 1; V[Vnum].sy := k;
  V[Vnum].ex := j + 1; V[Vnum].ey := k + 1;
  V[Vnum].next := Vnum + 1;
  V[Vnum].status := 0;

  Vnum := Vnum + 1;

  V[Vnum].prev := Vnum - 1;
  V[Vnum].sx := j + 1; V[Vnum].sy := k + 1;
  V[Vnum].ex := j;     V[Vnum].ey := k + 1;
  V[Vnum].next := Vnum + 1;
  V[Vnum].status := 0;

  Vnum := Vnum + 1;

  V[Vnum].prev := Vnum - 1;
  V[Vnum].sx := j;     V[Vnum].sy := k + 1;
  V[Vnum].ex := j;     V[Vnum].ey := k;
  V[Vnum].next := Vnum - 3;
  V[Vnum].status := 0;
end;

Simplify Vector.

Walk through the vector list. For each vector, look at the remainder of the vector list, and if there are any duplicates, remove them.

procedure simplifyvector;

var
  m,m2: integer;

begin
  for m := 1 to Vnum do
    for m2 := m + 1 to Vnum do
      if equalvectors(m,m2) then
        removevectors(m,m2);

end;

Equalvectors. Check the current vector to make sure it's not dead. If not, compare the points of the vector. If the vectors are exactly the same, or if the first vector is the exact reverse of the second vector, the vectors are equal.

function equalvectors(m,m2: integer): boolean;

var
  msx,msy,mex,mey,m2sx,m2sy,m2ex,m2ey: integer;
  r: boolean;

begin
  r := false;
  if (V[m].status <> -1) then
    begin
      msx := V[m].sx; msy := V[m].sy;
      mex := V[m].ex; mey := V[m].ey;
      m2sx := V[m2].sx; m2sy := V[m2].sy;
      m2ex := V[m2].ex; m2ey := V[m2].ey;

      if equalpoints(msx,msy,m2sx,m2sy) and
         equalpoints(mex,mey,m2ex,m2ey) then
         r := true;

      if equalpoints(msx,msy,m2ex,m2ey) and
         equalpoints(mex,mey,m2sx,m2sy) then
         r := true;
     end;


  equalvectors := r;
end;

Equalpoints. Determine if two pairs of points passed are equal.

function equalpoints(p1x,p1y,p2x,p2y: integer): boolean;

var
  r: boolean;

begin
  r := false;
  if (p1x = p2x) and (p1y = p2y) then
    r := true;
  equalpoints := r;
end;

Removevectors. In Simplifyvector, if the vectors are equal, this procedure is called. Because we have two squares next to each other and we want to remove the common line between them, we need to process each endpoint of the common vector. After this is done, we set each vector's status to "dead".

procedure removevectors(m,m2: integer);

begin
  removevector(m,m2);
  removevector(m2,m);

  V[m].status := -1;
  V[m2].status := -1;

end;

Removevector. This is the sticky bit of the whole Simplifyvector step. To remove the common vectors, we work around them. For vector mm, we hold the vector just before it (p), and then change p's next vector to be mm2's next vector. Then, we hold mm2's next vector (n), and make n's previous vector to be p. This would be much easier to explain with a diagram, perhaps I'll draw one someday.

procedure removevector(mm,mm2: integer);

var
  p,n: integer;

begin
  p := V[mm].prev;
  V[p].next := V[mm2].next;

  n := V[mm2].next;
  V[n].prev := p;
end;

Lengthenvector. What we have now is a series of joined vectors, but the problem is that any line with a length greater than one "unit" on a side is represented by a series of vectors and not one vector. This procedure examines where two joined vectors (the current vector and the previous vector) lie on the plane. If they are in a line, the link between them is removed and the extraneous vector is set "dead".

procedure lengthenvector;

var
  m,m2: integer;
  
begin
  for m := 1 to Vnum do
    if (V[m].prev <> 0) and (V[m].status > -1) then
    if (V[V[m].prev].sx = V[m].ex) or
       (V[V[m].prev].sy = V[m].ey) then
       begin
         V[V[m].prev].ex := V[m].ex;
         V[V[m].prev].ey := V[m].ey;
         V[V[m].prev].next := V[m].next;
         V[V[m].next].prev := V[m].prev;
         V[m].status := -1;
       end;
end;

2006sep. Here is the second correction I receievd.

Hello, I've had a look at your vectorizing algorithm. It looks nice from its simplicity. However, I guess the lenghtenvectors procedure is not OK: see below. Thanks anyway for posting your code

procedure lengthenvector;
  for m := 1 to Vnum do
    if (V[m].prev <> 0) and (V[m].status > -1) then

    if (V[V[m].prev].sx = V[m].ex) or
       (V[V[m].prev].sy = V[m].ey) then

!!! I guess the statement above should be:
!!! if (V[V[m].prev].EX = V[m].SX) AND
       (V[V[m].prev].EY = V[m].SY) then

       begin
         V[V[m].prev].ex := V[m].ex;
         V[V[m].prev].ey := V[m].ey;
         V[V[m].prev].next := V[m].next;
!!!         V[V[m].next].prev := V[m].prev;
!!! I think the previous statement should be removed
         V[m].status := -1;
       end;
end;

Thanks. Here's what I found. I'm not 100% sure, but the inner loop in procvector must be changed to "for m2 := m + 1 to Vnum + 1 do". Otherwise a bitmap like the one below

MAXSIZEX = 4; // arbitrary
MAXSIZEY = 4; // abritrary

0100
0100
0100
0100

will have 8 vectors instead of 4. I'm using PHP, not Pascal. - Rubem P.