Найти круги, содержащие только нули в произвольной двоичной матрице

Question

Учитывая двоичную матрицу произвольного размера, мне нужно найти круги, которые вписываются в эту матрицу и охватывают только поля «0» и не имеют «-1» -полей.

В этом примере

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 

Я хочу, чтобы найти следующий максимальный круг (обозначаемый в +)

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

На самом деле это не круг, только приближение к ней. Поиск прямоугольников в такой двоичной матрице может быть выполнен с помощью гистограмм, см. here. Кроме того, я пытаюсь найти меньшие круги, как это:

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 

ли кто-нибудь есть умные идеи (например, гистограммы-подход к прямоугольникам) о том, как определить эти круги (или дискретные приближения, соответственно)?

Answer 1

Выполните nearest neighbour search, для каждого 0 элемента find the closest1 элемента, используя евклидово расстояние и создать другую матрицу, хранящую расстояние от каждого до ближайшего 1 (или просто отслеживать самые большие).

Пространство, которое может соответствовать наибольшей окружности, будет задаваться элементом с наибольшим расстоянием до ближайшего соседа, а расстояние для каждого элемента будет определять размер круга, который может вписываться в пространство, центрированное на этом элементе (расстояние 1, означает один +, расстояние двух означает простой крест и т. д.).

Обратите внимание, что это работает только для кругов, центрированных на заданный элемент. Он не будет обрабатывать круги, центрированные на части между одним элементом и другим.

Answer 2

Шаг 1: начать итерации через один за другим элементам

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