How to detect thin extrusions from a polygon?

Question

I want to create a minimal polygon which approximates the boundary of an arbitrary (semi-random) shape.

By "minimal" I mean, "as few points as possible".

The original shape (to be bounded) is in bitmap format, with simple coloring.

The complication is that the shape may have lines (i.e. long thin areas/shapes) coming out of it. What algorithm can you suggest I use for detecting these lines?

For example, I want to detect lines which are no more than five pixels wide; the lines might be on a diagonal, or curved.

I'd prefer an algorithm, which I can implement, rather than a pre-implemented third-party tool or library.

For example, here is a sample simple shape (hand-drawn using Paint):

a shape

Note that it has a semi-random line coming out of it.

Here's the result of the shape-processing that I've implemented so far:

• The red pixels show a boundary traced around the shape
• The green pixels on the red boundary show a fairly minimal polygon, where the boundary changes shape.

boundary of the shape

An expanded version to make each pixel more visible:

enter image description here

The green pixels represent the polygon that I want, except that I'd like to cut off the tail shape at the bottom (so that basically just a square remains), because its maximum width makes it too thin to be interesting.

enter image description here

Given this data, what algorithm would detect that there's a thin shape coming out of the bottom?

Re. the performance requirements, the bitmap is likely to be say 1000 pixels square; the bounding polygon might have a couple of hundred points in total; and the algorithm is being run on a PC.

• Darien: Two similar questions (and answers): "What is a good algorithm for tracing around the edge of a 2D polyline", "What are Definition, Algorithms and Practical Solutions for Concave Hull?".
• ChrisW: This isn't the same question: "tracing around the edge" is what I already implemented (shown in red, above, using Moore Neighbor Contour Tracing Algorithm); and "concave hull" is an altogether different problem.
• Caleth: You want to discard the "tail" of the q, and keep the "step" along the top?
• ChrisW: @Caleth I don't care much either way, about the step at the top (after all, that step is only one pixel). I want to detect the tail, i.e. the boundary of the tail, i.e. the portion of the boundary which bounds the tail, in order to discard it; because (including its red border) that tail no more than e.g. 5 pixels wide.

Answer 1

How about this general approach? (Assuming your starting-point is the black outline as shown)

Create a mask by:

1. Filling the outline with black. (store as 8-bit greyscale)
2. Putting the filled shape through a low-pass (blur) filter. (convolution)
3. Creating a bitmap of every pixel lower than a threshold value in the blurred shape.
4. Possibly contour-growing that bitmap by a margin of a few pixels.
5. Retaining your original outline only where it falls within the bitmap mask.

Answer 2

The most straightforward algorithm is probably comparing the distances between the points in the figure. Those that are close can be merged, deleting intermediate vectors.

However, you do run the risk of deleting a whole figure, which you might want to keep, as a separate object. In this case, keep the "thin sticks" as a separate figure, and measure the maximum width at each pixel row to determine if you want to keep it. You might say that if either the width or height is below a minimum, discard the figure.

• ChrisW: Does "comparing the distances" means measuring every pair of points (i.e. every pair of red pixels, not just every pair of green pixels)? If a point is close to several others, do I merge it with its nearest neighbour (only)? Exclude pairs which are already connected by a short line? Will this round-off the corners of the square? Will it result in a long thin line, which (by merging its borders) has been squashed to like zero pixels wide instead of like 5 pixels wide? If I move a point (to merge it), does that create new border pixels (to retain the moved pixel's connection to its neighbours)?
• Frank Hileman: @ChrisW I assumed you had already converted from pixels to point coordinates or a set of vectors from point to point. Keep in mind that you can also look at what you are cutting off, and determine if it is a "tail" like set of points -- the vector distance is long with a "tail".