I have what I believe should be a relatively easy problem to solve that I have not been able to find an elegant solution for. I need to compare two binary 2D images and count if any of the elements from either image intersect/overlap with the other.

I would like to count how many blobs intersect with quadrilaterals. A blob may intersect with multiple quadrilaterals and each intersection would count, but multiple intersections within the same quadrilateral by the same blob, only count once.

I would like to count the number of quadrilaterals not intersecting with any blobs.

I would like to count the number of blobs not intersecting with any quadrilaterals.

These are the images

I created bounding boxes based on blob images with the following:

CreatePolygon[image_] :=

Module[{BinarizedImage, BoundaryBoxesCoords, Polygons, size},

size = ImageDimensions[image];

BinarizedImage = Binarize[image];

BoundaryBoxesCoords =

Last /@ ComponentMeasurements[

MorphologicalComponents[BinarizedImage], “MinimalBoundingBox”];

Polygons =

Graphics[{Red, Polygon /@ BoundaryBoxesCoords}, ImageSize -> size,

PlotRange -> {{0, First@size}, {0, Last@size}}]]

I tried doing a count of image items by overlapping the elements and counting objects consisting of amalgamated colors, but this doesn’t help with conditions where blobs intersect the same quadrilateral multiple times. Using the inverse is also not helpful in solving the other two problems as I had hoped.

CreateHits[QuadImage_, BlobImage_] :=

Module[{CompositeImage, GrayThreshold, Hits},

CompositeImage =

ColorConvert[

ImageCompose[Binarize[BlobImage], {QuadImage, .5}],

“Grayscale”];

GrayThreshold = {.6, .8};

Hits =

First@Last@

ComponentMeasurements[

MorphologicalComponents[

Binarize[CompositeImage, GrayThreshold]], “Count”]]

CreateHits[Image1, Image2]

I don’t think the ideal solution lies with the approach I’ve tried, however, which is a visual solution. What I’d like is to extract the coordinates for each blob and each quadrilateral area and just compare these object lists to determine overlaps. E.g., Blob 3 shares coordinates with Quadrilaterals 2 & 4. I can’t figure out, however, how to use the output of MorphologicalComponents to find this information to retrieve the coordinates for each object or to store each cluster as a separate item. This is bothersome because MorphologicalComponents has clearly identified those things.

I could brute force the code and create separate images for each blob and/or quadrilateral and do the comparison computation that way, but besides being much more computationally expensive it is, as I said, not particularly elegant.

=================

If you really failed to solve it, then, please, add any relevant code as a starting point/ideas generator.

– Sektor

May 29 ’14 at 16:07

=================

1 Answer

1

=================

ComponentMeasurement can return a Mask for every blob, which is a sparse array containing 1’s at the component pixel locations. So forming the “intersection” between any two blobs is a cheap sparse componentwise multiplication. In code:

(* Load the images, and make sure the “components” are white on black background *)

img1 = ColorNegate[

Binarize[Import[“http://i.stack.imgur.com/kR71u.png”]]];

img2 = Binarize[Import[“http://i.stack.imgur.com/ppyhb.png”]];

(* find masks for both blob sets *)

blobs = ComponentMeasurements[#, “Mask”] & /@ {img1, img2};

(* this calculates the intersection area between every blob in img1 and

every blob in img2, i.e. intersectionArea is a n*m matrix with non-zero

coefficients for every pair of intersecting blobs *)

intersectionArea =

Outer[Total[#1*#2, \[Infinity]] &, blobs[[1, All, 2]],

blobs[[2, All, 2]], 1];

MatrixPlot[intersectionArea]

given that, counting intersections should be trivial, i.e.

Count[intersectionArea, x_?Positive, \[Infinity]]

is the number of total intersections, or

Count[Total /@ intersectionArea, 0]

should be the number of blobs in img1 that don’t intersect any blob in img2.

ADD: I just noticed that you had a similar “brute force” approach in mind, but thought it wasn’t elegant enough. As I said, sparse multiplication should be cheap, and I doubt you’ll have performance problems for normally sized images. But if you really want to avoid the sparse-array way, I would try something like this:

comp1 = MorphologicalComponents[img1];

comp2 = MorphologicalComponents[img2];

sums = Union[Flatten[(Max[comp1] + 1)*comp2 + comp1]]

Which gives a list of “mangled intersecting blob indices”. Using some integer arithmetic, we can get back the original indices:

pairs = Transpose[Through[{Mod, Quotient}[sums, Max[comp1] + 1]]]

Which returns a list of pairs of intersecting blobs (0 means blob X has an intersection with the background of the other image):

{{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {6, 0}, {7, 0}, {8,

0}, {9, 0}, {10, 0}, {11, 0}, {12, 0}, {13, 0}, {14, 0}, {15,

0}, {16, 0}, {17, 0}, {18, 0}, {19, 0}, {20, 0}, {21, 0}, {22,

0}, {23, 0}, {24, 0}, {25, 0}, {26, 0}, {27, 0}, {28, 0}, {29,

0}, {30, 0}, {31, 0}, {32, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0,

5}, {0, 6}, {4, 6}, {0, 7}, {0, 8}, {6, 8}, {0, 9}, {0, 10}, {0,

11}, {0, 12}, {12, 12}, {0, 13}, {0, 14}, {0, 15}, {14, 16}, {14,

17}, {0, 18}, {0, 19}, {14, 20}, {14, 21}, {0, 22}, {14, 22}, {14,

23}, {14, 24}, {14, 25}, {14, 26}, {0, 27}, {0, 28}, {0, 29}, {0,

30}, {0, 31}, {0, 32}, {0, 33}, {19, 33}, {0, 34}, {20, 34}, {0,

35}, {20, 35}, {0, 36}, {0, 37}, {0, 38}, {0, 39}, {0, 40}}

MatrixPlot[SparseArray[# -> 1 & /@ Select[pairs, Min[#] > 0 &]]]

I must say that I find the first “sparse array”-version more elegant and would stick with that unless it’s far too slow.

Always a pleasure to read your answers 🙂 +1

– Sektor

May 30 ’14 at 1:03