2

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.

Community
  • 1
  • 1
Fidel90
  • 1,828
  • 6
  • 27
  • 63

2 Answers2

5

Finally I successfully went with the other option as markE described (although it's a bit modified). I'm using the Marching Squares Algorithm (MSA) and the Floodfill Algorithm (FFA) to achieve this. Simplifying the resulting points is done via Ramer–Douglas–Peucker Algorithm (RDPA).

I put everything together in this jsFiddle.

Steps:

  1. get path object after user finished free drawing
  2. create image from path via base64 dataURL
  3. convert to binary image (only 0 and 255 pixel, no transparency)
  4. apply FFA on position 0,0 with random color, save color
  5. go to next pixel
  6. if pixel has known floodfill color or path color (black), move on to next
  7. otherwise floodfill with new random color, save color
  8. move over all pixels, repeating 5.-7.
  9. remove saved color on index 1 (it's the color surrounding the path contour (padding), so it's neither the path nor a hole)
  10. for all other colors apply MSA and simplify resulting points (with DPA)
  11. Either create polygons from simplified points OR ...
  12. ... smooth points and create path
  13. add to canvas, remove input path
  14. DONE :)

For simpler code my random color at the moment only creates shades of grey. R=G=B and A=255 allows for simpler checks. On the other hand this solution limits the contour to have max. 254 holes (256 shades of grey - path color (0) - padding color (no hole)). If one needs more it's no problem to extend the code to create random values for R, G, B and even A. Don't forget to adopt the color checks accordingly ;)

The whole algorithm may not be optimized for performance but honestly I see no need to do so at the moment. It's fast enough for my use-case. Anyway, if someone has a hint regarding optimization I'm glad to hear/read about :)

Mike 'Pomax' Kamermans
  • 49,297
  • 16
  • 112
  • 153
Fidel90
  • 1,828
  • 6
  • 27
  • 63
  • 2
    Nice job doing an unusual, interesting task! :-) Optimization? Cast the R,G,B,A data as a single 32-bit number rather than as 4 8-bit numbers – one single get, compare & put rather than 4 gets, 4 compares & 4 puts. To cast 4x8bit as 1x32bit you can use a [DataView](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/DataView). Most browsers are littleEndian, but you need to check. You would also have to teach MSA & FFA to work with single numbers. If you're using a reduced color palette (256) then you could even use a Uint8Array with tokens for each color. Cheers! – markE Aug 30 '16 at 02:29
  • 1
    @markE: Yeah, TypedArrays would be a nice approach. If I have more image processing to do in the future I surely will consider using them. One thing that's bothering me: Is it better to first simplify and then smooth the path (like I do atm) or to do it the other way round (smooth, then simplify)? – Fidel90 Aug 30 '16 at 05:08
  • 1
    Smoothing algorithms often replace vertices (path-points) with splines. MSA over-produces vertices which gives splines problems. So you might simplify then smooth. Keep in mind that doing both simplification & smoothing may lose tolerance to the original MSA points. The simple-smooth spline may not represent the blob(s) as truly as the MSA points -- so you have a balancing decision which often is decided by design considerations. Good luck with your project! :-) – markE Aug 30 '16 at 05:37
  • @markE: Thanks mate :) So for now this seems to work good. But as you said I have to find the balance between simplifying/smoothing and accuracy according to the original path. – Fidel90 Aug 30 '16 at 07:05
2

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

Graham
  • 7,431
  • 18
  • 59
  • 84
markE
  • 102,905
  • 11
  • 164
  • 176
  • Hi markE :) The technic you describe is what I'm trying to build at the moment. Your answer shows me that I'm on the right path (pun not intended). I already have the MSA and the FFA running, now I'm on my way to put things together. I'll post a fiddle as soon as I'm done. – Fidel90 Aug 29 '16 at 05:13
  • 1
    Cool -- glad to help! One additional thought: It's less of a problem with pure b&w pixels, but canvas might still anti-alias curves -- so your floodfill might not get all the path's interior cleared. In particular, you might have pockets of anti-aliasing around the perimeter of the path. Eliminate the anti-aliasing on path perimeter by stroking the discovered path with `globalCompositeOperation = 'destination-out'` after you floodfill the bulk of the path interior. Using a stroked lineWidth of 4 should clear out the anti-aliasing bits. – markE Aug 29 '16 at 05:22
  • I'm done, see my answer. Thanks for your help again :) If you have some ideas for optimization just let me know. – Fidel90 Aug 29 '16 at 12:33