Find circles containing only zeros in an arbitrary binary matrix

Question

Given a binary matrix of arbitrary size, I need to find circles which fit into this matrix and only cover "0"-fields and no "-1"-fields.

For this example

1 0 0 0 0 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 1 1

I want to find the following maximal circle (denoted in +)

1 0 0 + 0 1 1
1 0 + + + 0 1
1 + + + + + 1
1 0 + + + 0 1
1 0 0 + 0 1 1

Actually this is no circle, only an approximation of it. Finding rectangles in such a binary matrix can be done with the help of histograms, see here. Additionally, I try to find smaller circles like this one:

1 0 + 0 0 1 1                1 0 0 0 0 1 1
1 + + + 0 0 1                1 0 0 0 0 0 1
1 0 + 0 0 0 1   or this one  1 0 0 + 0 0 1
1 0 0 0 0 0 1                1 0 + + + 0 1
1 0 0 0 0 1 1                1 0 0 + 0 0 1

Does anybody have a smart idea (like the histogram-approach for rectangles) of how to identify these circles (or its discrete approximations, respectively)?

Should your circles be approximations of "real" (round) circles or just diamonds as in your examples? — M Oehm, Dec 08 '16 at 06:54
Actually, they should be approximations of round "real" circles. — Kapa11, Dec 08 '16 at 07:01

score 3 · Accepted Answer · edited May 23 '17 at 12:30

Perform a nearest neighbour search, for each 0 element to find the closest 1 element, using Euclidean distance and create another matrix storing the distance from each to the nearest 1 (or just keep track of the largest).

The space that can fit the largest circle will be given by the element with the largest distance to the nearest neighbour, and the distance for each element will specify the size of the circle that can fit in the space centered on that element (distance of 1, means a single +, distance of two means a simple cross, etc).

Note this only works for circles that are centered on a given element. It won't handle circles that are centered part-way between one element and another.

score -1 · Answer 2 · answered Dec 08 '16 at 06:46

Step1: start iteration through one by one elements

1.1 : If the element is 0
     1.1.1 : check if it in the border , ie,  row = 0 or row = max_row or col = 0 or col = max_col
     1.1.2 : if not so, check if bottom , top, left and right elements are 0
     1.1.3 : if all are 0, increment radius 
       1.1.4 : else break;
       1.1.5: now check bottom-1, top+1, left-1; right+1 to see if they are 0
       1.1.6: if they are also 0, again increment radius

       1.1.7: repeat the above steps till you break
 1.2 : check all elements of matrix

But using this algorithm will lead to a shape looking like a cross, and not like a circle (since you only check for bottom-1, top+1, left-1, right+1 and not e.g. top-left). — Kapa11, Dec 08 '16 at 08:04

Find circles containing only zeros in an arbitrary binary matrix

2 Answers2