Fidel90 Fidel90 - 3 months ago 19
Javascript Question

Create path from (inner and outer) edges of a blob-like image

I'm looking for a way to create a svg like path from a binary image (only black and white pixels). The image itself will be a blob with irregular shape that could have holes in it.

Without holes I only need a bounding path the recreates the border of the blob. When there are holes in the blob, I'm fine with additional paths (as one path alone wont be able to recreate this, I guess). At the end I just need to know which path is the outer one and which are the holes.

I already found these:



Additionally I need the detection of holes. It doesn't really matter to me if the result is a polygon or a path. I just need the points with high enough accuracy that curves keep being curvy :)

It would be great if someone has an idea or even some further sources.

PS: I'm working with canvas and javascript (fabricJS) if this makes any difference.

Answer

Best Option

If you drew the Blobs with your code, then the simplest & best way is to decompose each blob (and sub-blob) into it's component Bezier curves. FabricJS is open source so you can see how they create the curves -- and therefore how you can decompose the curves. The result will be a dozen or so Bezier curves that are easy to redraw or navigate. If you need help navigating Bezier Curves, see this Documentation convering Navigating along a Path.

Other Option

You will need to get the pixel information, so you will need to context.drawImage your Fabric Blob onto a native canvas and use context.getImagedata to fetch the pixel information.

Assuming:

  • All pixels are either white or black.
  • The blob is black: rgba(0,0,0,255)
  • Outside the blob is white: rgba(255,255,255,255)
  • The holes in the blob are white: rgba(255,255,255,255)

A plan to find the blob & hole paths:

  1. Load the imageData: context.getImageData(0,0,canvas.width,canvas.height)

  2. Find a white pixel on the perimeter of the image.

  3. Use a FloodFill Algorithm (FFA) to replace the outer white with transparency.

  4. Use the Marching Squares Algorithm (MSA) find the outermost blob perimeter and save that blob path.

  5. Use a Floodfill Algorithm to fill the blob you've discovered in #4 with transparency. This makes the outer blob "invisible" to the next round of MSA. At this point you only have white holes -- everything else is transparent.

  6. Use the Marching Squares Algorithm (MSA) find the perimeter of the next white hole and save that hole path.

  7. Use a Floodfill algorithm to fill the white hole in #6 with transparency. This makes this hole invisible to the next round of MSA.

  8. Repeat #6 & #7 to find each remaining white hole.

  9. If MSA reports no pixels you're done.

For efficiency, you can repeatedly use the imageData from Step#1 in the subsequent steps. You can abandon the imageData when you have completed all the steps.

Since blobs are curves, you will find your blob paths contain many points. You might use a path point reduction algorithm to simplify those many points into fewer points.