How to convert a solid black and white image to a collection of polygons?

Question

I have a bunch of solid black and white images with various texts and shapes. My goal is to convert each image into a set of polygons (defined as a set of vertices) that surround a black area (just like a magic wand tool can select areas in photo editing software).

I would prefer to implement this in JavaScript, but I'm most interested in conceptually how I can do this. Thanks!

Answer 1

How to use a magic wand in simple raster image editors:

Let color C be the color of the selected starting point. Let the last color LC be any color.

• Get the selected point (x, y)
• If color (x, y) = C and pixel are not visited
  • Save coordinates in array
  • Repeat the algorithm for (x + 1, y), (x-1, y), (x, y + 1), (x, y-1)
• Save a pixel in an array of visited pixels.
• If color (x, y)! = LC
  • Mark pixel as border pixel in array
  • Set LC = color (x, y)

Answer 2

When you need to check only the perimeter, you can create the algorithm of the "right hand on the wall."

Step 1: Scroll right through the image to find the first pixel of the opposite color.
Step 2. Find all neighboring pixels of the current clockwise. Step 3: go to the first available pixel. Saving Pixel Index
Step 4: Repeat steps 2-3 until the current pixel becomes the starting pixel in step 1

Step 5: Detect patterns from stored pixels, e.g.
Starts LLLLLLLLLL, [Left] Up, Right, or Down,

Form templates

RRRRRRR U RRRRRRR U RRRRRRRR U RRRRRRR U ... <-N---> <--N--> <--N+1-> <--N--> 

can be modeled by a line, although it is not so simple to make a “reverse breech” to detect the best possible start and end points of a segment.

The brute force approach can be used to draw a line from the current pixel to the N previous pixels and check if the Bresenhams algorithm produces exactly the same pixels.

Answer 3

First, let me explain what a land is.

An edge is a virtual line between two adjacent pixels.

 +---+---+ | A | B | // The middle line is the edge between pixel A and pixel B +---+---+ 

The edges have a start point and an end point, and therefore are oriented up, down, left, or right.

To process polygons crossing the borders of images, we will add 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 edge list } } 

Done, you have a list of polygons.

EDIT

Of course, you need to optimize it a bit before using it, but it is very simple: consecutive edges with the same orientation can be replaced with one longer edge.