Существуют ли алгоритмы для вычисления ограничивающих рядов спрайтов, нарисованных на монохромном фоне?

Question

Представьте себе простое прямоугольное растровое изображение, скажем, 1024x768 пикселей, заполненное белым. На растровом изображении нарисовано несколько (не перекрывающихся) спрайтов: круги, квадраты и треугольники.

Существует ли алгоритм (возможно, даже реализация C ++), который, учитывая растровое изображение и цвет, являющийся цветом фона (белый, в приведенном выше примере), дает список, содержащий наименьшие ограничивающие прямоугольники для каждого из спрайтов?

Вот пример: на левой стороне вы можете увидеть пример растрового изображения, в котором указан мой код (вместе с информацией о том, что «фон» белый). На правой стороне вы можете увидеть то же изображение вместе с ограничивающими прямоугольниками четырех фигур (красным); алгоритм, который я ищу, вычисляет геометрию этих прямоугольников.

Входное изображение http://s1.directupload.net/images/111215/ruycwlgl.png Выходное изображение http://s1.directupload.net/images/111215/encr84ps.png

Некоторые программы рисования имеют похожую функцию для выбора форм: они могут даже вычислять, казалось бы, произвольные ограничивающие полигоны. Вместо того, чтобы перетаскивать прямоугольник выбора вручную, вы можете щелкнуть «фон» (какой фон, а какой нет, определяется некоторым порогом), а затем инструмент автоматически вычисляет форму объекта, нарисованного на фоне. Мне нужно что-то вроде этого, за исключением того, что у меня все отлично, если у меня есть прямоугольные ограничивающие области для объектов.

Мне стало известно о OpenCV ; он кажется уместным (кажется, что это библиотека, которая включает в себя все графические алгоритмы, которые я могу придумать, а затем и некоторые), но из-за быстрого количества информации я не смог найти путь к алгоритму, о котором я думаю. Я был бы удивлен, если бы OpenCV не смог сделать это, но я боюсь, что вам нужен доктор, чтобы использовать его. : -)

Answer 1

Вот отличная статья на эту тему:

http://softsurfer.com/Archive/algorithm_0107/algorithm_0107.htm

Я думаю, что PhD здесь не требуется:)

Answer 2

Это мои первые мысли, ничего сложного, кроме определения края

For each square, 
   if it's not-white
       mark as "found"
       if you havn't found one next to it already
           add it to points list
for each point in the points list
    use basic edge detection to find outline
    keep track of bounds while doing so
    add bounds to shapes list
remove duplicates from shapes list. (this can happen for concave shapes)

Я только что понял, что белые дыры (как в крайнем левом круге в вашем образце) будут иметь свою собственную форму. Если первый «цикл» представляет собой заливку, у него нет этой проблемы, но он будет намного медленнее / займет намного больше памяти.

Базовое обнаружение ребер, о котором я думал, было простым:

given eight cardinal directions left, downleft, etc...
given two relative directions cw(direction-1) and ccw(direction+1)
starting with a point "begin"
set bounds to point
find direction d, where the begin+d is not white, and begin+cw(d) is white.
set current to begin+d
do 
    if current is outside of bounds, increase bounds
    set d = cw(d)
    while(cur+d is white or cur+ccw(d) is not white)
        d = ccw(d)
    cur = cur + d;
while(cur != begin

http://ideone.com/

Существует довольно много краевых случаев, которые здесь не рассматриваются: что, если начало - это одна точка, что, если она проходит к краю изображения, что, если начальная точка имеет ширину всего 1 пиксель, но имеет сгустки с двух сторон, вероятно, другие ... Но основной алгоритм не так уж сложен.