Distinguishing between triangles, squares, pentagons in binary images

toffersan · August 7, 2018, 10:42am

Hello there,
I am trying to categorize polygons (triangles, squares & polygons with more than 5 edges) within a binary image based on their shape using the BioVoxxel toolbox and the shapefilter. Has someone done this before or can someone provide the certain parameter which help to distinguish between these forms? The particles are sometimes not perfect triangles, but represent more the shape of a triangle than that of a square.

At first glance I could separate squares from other polygons by using the Circularity Parameter (see image)
although I dont know how to seperate triangles from multi-edge-polygons!

Thanks for ideas and help!

anon96376101 · August 7, 2018, 11:19am

Good day Christof,

your task sounds interesting!
(It reminds me of a competition in the late 1970s.)

Would you mind posting a typical raw image in the original TIF- or PNG-format. No JPG-format though, because JPG introduces artifacts! You may also post images as Zip-archives.

If possible post an image version before binarization!

Regards

Herbie

Added after the OP made the image accessible:
Please post the original image, not a screen shot.

toffersan · August 7, 2018, 11:49am

Hello Herbie,

thanks for your answer, the original image is the digital photo pf soil structures I want to investigate.

Due to large noise in this image I traced the polygons by hand which resulted in the two color photo.

original

squared%20polygons_3000px_29px-1m_31_07_18_contrast_filled3

Thanks

anon96376101 · August 7, 2018, 3:55pm

Indeed, Christof,

the original gray-scale photo appears rather difficult to binarize without manual intervention but thank you anyway.

Maybe someone “fluent” in WEKA could try an approach for automatic segmentation and binarization …

Meanwhile I shall have a look at the binarized image.

Regards

Herbie

anon96376101 · August 7, 2018, 3:53pm

Christof,

I’ve tried various classifiers for the first 100 shapes of your binary sample image using the following set of four features (Shape descriptors that are provided by plain ImageJ):
Circularity
Aspect ratio
Roundness
Solidity

4 classes were considered:
Triangle
Quadrilateral
Pentagon
Polygon

The result is disappointing because the best recognition rate was slightly above 50%.

With this result we can conclude that we need more or better separating features to obtain acceptable classification.

Regards

Herbie

toffersan · August 7, 2018, 3:52pm

Wow Herbie thank you anyway for your help! I will keep trying. I thought about counting edges of each particle, although this could also be dissappointing, since the shapes are not that of perfect geometric bodies.

Cheers,

Christof

bogovicj · August 7, 2018, 5:48pm

Hi @toffersan,

Another idea is to try to find and count corners per object, using for example, the old school Harris Corner Detector.

afaik, there isn’t an implementation built into Fiji / ImageJ (maybe cell profiler has one?),
but the Hessian matrix implementation by @hanslovsky in imglib2 gets most of the way there (the traditional corner detector uses the structure tensor, not the hessian matrix).

There is an skimage implementation that is worth a try.

Yea, this could cause trouble even if the corner detection is perfect

John

anon96376101 · August 7, 2018, 6:05pm

Good day John,

in fact I tried counting corners and ultimate points (after some preprocessing) but especially obtuse angles pose difficulties.

Regards

Herbie

gabriel · August 7, 2018, 6:33pm

A simple way you may want to try: compute the skeleton of the image, then count the number of extreme points of each skeleton. (Those pixels having a connection to only one other pixel). Corners often end up being extreme points of a skeleton.

Another method: Do a dilation without merging and then count the number of neighbours.

None of these will be perfect (for the same reason that you cannot detect reliably a n-side polygon out of arbitrarily sized binary regions).

biovoxxel · August 8, 2018, 7:40am

To complement @gabriels’ point, I tried to run the neighbor analysis from the BioVoxxel Toolbox over your image with various different starting setup but it also ends up not separating the shapes as of interest since particle size and border position influences the amount of neighbors found.

Just to test an idea, I run an opening to eliminate corners and subtracting the result from the binary original with the following macro:

run("Set Measurements...", "display redirect=None decimal=3");

originalImage = getTitle();

run("Analyze Particles...", "clear add");
roiManager("Show None");
run("Duplicate...", "title=binary-opening");
binaryDuplicate = getTitle();
run("EDM Binary Operations", "iterations=6 operation=open");
imageCalculator("Subtract create", binaryDuplicate , originalImage);
cornerImage = getTitle();

for(r=0; r<roiManager("count"); r++) {
	roiManager("select", r);
	run("Find Maxima...", "noise=254 output=Count");
	
}

However, this also does not give you a reliable outcome. specifically because it will skip all corners with an inside kink. Seems a tricky task.

anon96376101 · August 9, 2018, 10:05am

Good day dear colleagues,

as I’ve written before, the problem of the OP is not that he can’t classify certain polygons but, as Jan Brocher has just confirmed, that he can’t classify the polygons that are present in his image.

As I’ve noted before and as later suggested by Gabriel, there are indeed good approaches to classify certain polygons.

Here is a binary image with six polygons that can be perfectly classified:
testPatterns

Here is an ImageJ macro that returns the number of sides of each polygon:

// imagej-macro "polySides" (Herbie G., 07. August 2018)
setBatchMode(true);
run("Make Binary");
run("Variance...", "radius=7");
run("Variance...", "radius=7");
run("Analyze Particles...", "add");
n = roiManager("count");
run("Ultimate Points");
setThreshold(7, 255);
run("Make Binary");
for ( i=0; i<n; i++ ) { 
   roiManager("select", i);
   run("Find Maxima...", "noise=0 output=Count light");
}
run("Select None");
run("Revert");
setBatchMode(false);
exit();
// imagej-macro "polySides" (Herbie G., 07. August 2018)

This macro doesn’t work with the OP’s image but if the individual polygons of his image are isolated and enlarged it may work.

Have fun

Herbie

anon96376101 · August 8, 2018, 5:35pm

Good day Christof,

here is the best classification I could get from your sample image:

red: triangle
green: quadrilateral
blue: pentagon
white: polygon > 5 sides

Of course there are still wrong classifications.
Most of them are due to the insufficient spatial resolution of the sample image or to large obtuse angles of particles. Some are rather strange and I can’t explain them yet (e.g. particles #27 and #267).

HTH

Herbie

toffersan · August 9, 2018, 8:23am

Hello Herbie,

thank you, this is far the best result! Did you used the macro you posted before?

anon96376101 · August 9, 2018, 10:06am

Well Christof,

even after rather extensive experimenting the results don’t get much better.

The first reason is that on one hand you like to be tolerant towards certain shape deviations and on the other hand this tolerance leads to errors.
As mentioned before, the second reason is the spatial resolution of the image.
Also mentioned before and partially related to 2., the third reason are large obtuse angles of particles.
Other reasons that are not resolved yet …

Here is the ImageJ-macro that I’ve used:

// imagej-macro "polySides" (Herbie G., 08. August 2018)
setBatchMode(true);
run("Make Binary");
run("Analyze Particles...", "add");
cnt = roiManager("count");
for ( i=0; i<cnt; i++ ) { 
   roiManager("select", i);
   n = polySides();
   if (n<4) roiManager("Set Fill Color", "red"); 
   if (n==4) roiManager("Set Fill Color", "green");
   if (n==5) roiManager("Set Fill Color", "blue");
   if (n>5) roiManager("Set Fill Color", "white");
}
run("Select None");
run("Labels...", "color=white font=12");
run("Invert LUT");
setBatchMode(false);
exit();
function polySides() {
   run("Duplicate...", " ");
   run("Make Inverse");
   run("Set...", "value=0");
   run("Select None");
   w = getWidth()+150;
   h = getHeight()+150;
   run("Canvas Size...", "width=[w] height=[h] position=Center zero");
   run("Variance...", "radius=7");
   run("Variance...", "radius=7");
   run("Ultimate Points");
   setThreshold(7, 255);
   run("Make Binary");
   getRawStatistics(N, mn);
   close();
   return round(mn*N/255);
}
// imagej-macro "polySides" (Herbie G., 08. August 2018)

Regards

Herbie

toffersan · August 9, 2018, 12:05pm

Thanks for your effort and for the macro Herbie!
I will use this macro for a rough classification and then do the corrections by hand, still helped me a lot
otherwise I could idealize certain shapes by hand and than analyze it again with probably better results.

Greetings
Christof

anon96376101 · August 10, 2018, 7:11am

To end this thread from my side, here are three results obtained with a different approach and with increasing shape-tolerance:

best fidelity

Result_LaPlace-Gauss2d5-Squared-Thresh9d03000×3718 196 KB
slight shape-tolerance

Result_LaPlace-Gauss2d5-Squared-Thresh8d03000×3718 195 KB
increased shape tolerance

Result_LaPlace-Gauss2d5-Squared-Thresh7d03000×3718 194 KB

Again the color coding is:
red: triangle
green: quadrilateral
blue: pentagon
white: polygon > 5 sides

The approach is now based on the classic curvature-extraction of corners.

Regards

Herbie

DickGordonCan · June 3, 2019, 5:50pm

I’d like to classify and count kinds of polygons and their areas in light micrographs of Archaea. Have about 150 images of diverse qualities. As their sizes are 0.5 to 10 µm, with light microscopy resolution of 0.5 µm, images are all blurred. Most images only have a few polygonal cells amongst many coccoid and/or rod shaped cells. So this data set has all of the problems discussed here, and thensome.