I have a bunch of solid-black and white images with various text and shapes on them. My goal is to convert each image into a set of polygons(defined as a set of vertices) that surround the black area (in the same way that a magic-wand tool can select areas in photo editing software).
I would prefer to implement this in JavaScript, but I am most interested in conceptually how I might go about doing this. Thanks!
When only the perimeter must be scanned, one can produce a 'right hand on the wall' algorithm.
Step 1: traverse along the image right to find the first pixel of opposite color.
Step 2: Search all neighbouring pixels of the current one in clockwise order.
Step 3: Move to first available pixel. Store the pixel index
Step 4: Repeat steps 2-3 until the current pixel is the starting pixel in step 1
Step 5: Detect patterns from the stored pixels e.g.
Runs of LLLLLLLLLL, [Left] Up,Right or Down,
Patterns of form
RRRRRRR U RRRRRRR U RRRRRRRR U RRRRRRR U ...
<-N---> <--N--> <--N+1-> <--N-->
can be modelled by a line, although it is not that easy to do "inverse bresenham" to detect the best possible starting and ending points of a line segment.
A brute force approach can be anyway used to draw a line from current pixel to N previous pixels and test if bresenhams algorithm produces exactly the same pixels.
The way magic wand works in simple bitmap editors is:
Let color C be the color of the original point selected. Let last color LC be any color.
First, let me explain what an "edge" is.
An edge is the virtual line between two contiguous pixels.
+---+---+
| A | B | // The middle line is the edge between pixel A and pixel B
+---+---+
Edges have a starting point and an end point, and so are oriented upward, downward, "left going" or "right going".
In order to handle polygons crossing image boundaries, we gonna add a 1 pixel white border around our image.
Here is the algorithm:
For each row of our image {
For each pixel of the row except the last one {
If current pixel is white and next pixel is black {
Create a new upward edge between the two pixels and add it to
the global edge list.
}
Else if current pixel is black and next pixel is white {
Create a new downward edge between the two pixels and add it to
the global edge list.
}
}
}
For each column of our image {
For each pixel of the column except the last one {
If current pixel is white and next pixel is black {
Create a new "left going" edge between the two pixels and add it to
the global edge list.
}
Else if current pixel is black and next pixel is white {
Create a new "right going" edge between the two pixels and add it to
the global edge list.
}
}
}
For each edge of the global edge list {
Find the edge starting from the point where your current edge ends
(for now on, we gonna call it next_edge).
Connect the two edges to form a linked list
(edge->next = next_edge; next_edge->previous = edge;)
}
While there is edges in the global edge list {
Create a new polygon and add it to the polygon list
Take the first edge of the list (for now on, we gonna call it first_edge)
For each edge in the linked list starting at first_edge {
Remove edge from global edge list
Add edge to polygon's edge list
}
}
Done, you have a list of polygons.
EDIT
Of course, you have to optimize it a little before using it, but it's really easy : consecutive edges with the same orientation can be replaced with a single, longer edge.
