Czy istnieją algorytmy do obliczania prostokątu prostokątów rysowane na monochromatycznym tle?

Question

Wyobraź sobie prostą prostokątną bitmapę, powiedzmy 1024x768 pikseli wypełnioną bielą. Na mapie bitowej jest kilka (nie nakładających się) ikonek: kółka, kwadraty i trójkąty.

Czy istnieje algorytm (może nawet implementacja C++), który, biorąc pod uwagę bitmapę i kolor, który jest kolorem tła (biały, w powyższym przykładzie), daje listę zawierającą najmniejsze prostokąty ograniczające dla każdego z duszków ?

Oto kilka przykładów: Po lewej stronie widać przykładową mapę bitową, którą podany jest mój kod (wraz z informacją, że "tło" jest białe). Po prawej stronie widać ten sam obraz wraz z prostokąciami ograniczającymi czterech kształtów (na czerwono); algorytm, którego szukam, oblicza geometrię tych prostokątów.

Input picture http://s1.directupload.net/images/111215/ruycwlgl.pngOutput picture http://s1.directupload.net/images/111215/encr84ps.png

niektórych programów malarskich mają similiar funkcji do wyboru kształty: mogą nawet obliczyć pozornie dowolnych wielokątów ograniczenia. Zamiast ręcznego przeciągania prostokąta zaznaczenia można kliknąć "tło" (to, co jest tłem, a co nie jest określone przez pewien próg), a następnie narzędzie automatycznie oblicza kształt obiektu narysowanego na tle. Potrzebuję czegoś takiego, z tym wyjątkiem, że mam całkowitą rację, jeśli mam tylko prostokątne obwiednie obiektów.

Uświadomiłem sobie, że OpenCV; wydaje się to istotne (wydaje się, że jest to biblioteka, która zawiera każdy algorytm graficzny, jaki mogę wymyślić - a potem trochę), ale w dużej ilości informacji nie mogłem znaleźć drogi do algorytmu, o którym myślę. Byłbym zaskoczony, gdyby OpenCV nie mógł tego zrobić, ale obawiam się, że musisz mieć doktorat, aby go użyć. :-)

Answer 1

Oto wielki artykuł na ten temat:

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

myślę, że nie jest wymagane PhD tutaj :)

Answer 2

Są to moje pierwsze myśli, żadna skomplikowana, z wyjątkiem wykrywania krawędzi

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) 

Właśnie sobie z tego sprawę rozpatrzy białe „dziury” (jak w skrajnym lewym kole w swojej próbie) być to jest własny kształt. Jeśli pierwsza "pętla" jest wypełnieniem powodziowym, nie ma tego problemu, ale będzie znacznie wolniejsza/zajmie znacznie więcej pamięci.

Podstawowa detekcja krawędzi Myślałam o był prosty:

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/

Istnieje sporo przypadki brzegowe nie uważane tutaj: co jeśli zacznie to pojedynczy punkt, jeśli to działa do krawędzi obrazu, co jeśli punkt początkowy ma tylko 1 piksel szerokości, ale ma blobs na dwie strony, prawdopodobnie inne ... Ale podstawowy algorytm nie jest aż tak skomplikowany.