Reduce to points?

[3DTOPO]

Greetings,

I could be wrong, but I think I remember reading of a way to reduce areas of an image to a single pixel using ImageMagick.

I am trying to achieve something like the results of the right hand image:



Any suggestions would be greatly appreciated!

[fmw42]

One way it to convert the image to b/w and use -morphology. For example:

convert point-example.png -fill black +opaque white point-example2.png
convert point-example2.png -morphology dilate:35 square point-example_d35.png

This erodes black (same as dilate white) making it smaller each iteration. Unfortunately, if both are not the same size, then one will disappear before the other. So you may want to split the image into two parts -- one for each color. iterate eroding black (dilate white) until you just get one pixel left or right before it goes all white. Then recombine the two images, use them for a mask over your original image to put the color back.

Anthony knows more about this than I, but you may be able to use distance measures in -morphology to simply locate the centroids of each of the two figures. But try this and you will see the idea:

convert point-example2.png -negate -morphology distance:-1 Euclidean -auto-level point-example2_neg_dist_al.png

[anthony]

The major problem is --- what point! What do you want the point for?

If any point would do, simplest is just grab the first point you find. That is want most programs do!

If you want some sort of center you have a much harder time. Objects like you have presented are 'convex' that is they don't have any concave angles or 'holes' in them. But what if your shape is say... two overlapping circles? What if the object has a hole in it.

What point do you want in that case. Some points are hard to find than others.

---

For most objects, the fastest method is to use a distance function (and one that will be faster when a 2-pass distance function is implemented). That is just apply some distance function, and then pick the highest 'peak'.

Remember you may have mutliple peaks in a single shape. A non-convex shape like you gave will only have one peak.

Because of multiple peaks you may have to separate and handle each shape individually, to ensure you only get one peak per object.
http://www.imagemagick.org/Usage/morphology/#distance

Another method is known as 'last erode' that is erode the object (assuming it is white on black) and grab the last pixel(s) that disappear. This should actually produce a similar result to the distance function. Last erode is NOT implemented

You could get a rough but much better 'center' of the shape by averaging the location and height of all the peaks. However that point may not be in the original shape!

---

Note these produce a point(s) that is furthest from any edge. That point is not necessary the centroid which for any given shape is a unique single point. However you must remember the centroid of a non-convex shape may not actually be inside the shape. A donuts centroid is in the middle of the hole. It is also why those balancing bird sculptures act so weird as it arranges for the 'gravitation centroid' to fall in a strange place.

It is also posible to get two separate and distinct objects to have the same centroid!

I have no idea at this point how to get a centroid of a random shape.

---

Another method that is slow but which would generate a single point for any shape that contains no holes is to generate a skeleton of the shape
http://www.imagemagick.org/Usage/morpho ... g_skeleton
And then prune it until you only have just a couple of points left
http://www.imagemagick.org/Usage/morpho ... ng_pruning

However that would be VERY very slow.

---

Other ideas welcome. Examples welcome. This could make a good addition to IM Examples 'morphology'.

[fmw42]

Anthony,

I am not sure how you have implemented morphology, but could you not make a special 3x3 square shape (binary) erode that tests if the center white pixel is isolated (surrounded by 8 black pixels) and then not erode that last pixel away? Then iterate until no changes occur between iterations.

Probably only meaningful for convex objects. Don't know how it would work if two diamonds are touching at vertices (like a figure 8 shape)


Fred

[anthony]

but could you not make a special 3x3 square shape (binary) erode that tests if the center white pixel is isolated (surrounded by 8 black pixels) and then not erode that last pixel away? Then iterate until no changes occur between iterations.

Except tha that would be specific to a particular kernel. As such it would be a specialised routine.

howeever the technique is called 'Last Erode' but I have not found any information on how to implement it for a general kernel.

BUT for that specific case doing a distance transform with a Chebyshev Distance function, than look for any peak pixel using hit and miss will find those points. However non-convex shapes will generate multiple peaks, and even convex shapes may generate a ridge or 4 pixel peak instead of single points. A little more processing may be needed to reduce those last few pixels down to a single point

An example of doing this was in a previous topic that involved generating 'little people' standing in a way to spell out letters on a large foot ball field... It required reducing small round dots to simple pixel points.... It used a 'thinning overkill', to do the task of point reduction, so is VERY slow, but for the small dots it was acceptable. This technique is equivalent to the pruning of a skeleton to a single point or loop (if a hole is present in the shape), I mentioned previously. Though the example given does the skeleton thin, and end of line pruning at the same time.

Hmmm... Found it "A Fun experience in IM"
viewtopic.php?f=1&t=17259

Code: Select all

convert anthony_dots.gif -threshold 80% \
          -morphology Thinning:-1 'LineEnds;Corners;Edges' anthony_pixels.gif

I am open to better methods though.

[fmw42]

My suggestions was for one specific shape, namely, a 3x3 square, so that one single pixel results. Not suggesting it would be necessarily easy to implement, but it might be a start for such as time permits. But it certainly merits more research into last erode methods.

Fred

[anthony]

A much more important method that needs to be added in the shape labeling. Make each shape a unique greyscale value or unique color. This is like a specialized flood fill but has two 'neighbourhood' modes.