Witam,
Czy słyszał ktoś o algorytmie, który dopełnia kontury obiektów na obrazie? Nie wiem jak to opisać, zdjęcia wszystko wyjaśniają:
MAM:
CHCĘ (czerwonym kolorem dopełniłem kontury):
Nie wiem w jaki sposób coś takiego zrobić. Proszę o pomoc: hasła, linki, opis algorytmu, naprowadzenie.
bounding box obiektu pozniej wypelnienie i tak bedzie dazylo po kolku a raczej krqawedziach bounding box'a wystarczy znhalezc luki i polaczyc wektorami
Cepa, wypukła otoczka się nie nadaje, bo obiekty mogą być wklęsłe.
Komorkowy_dzony, na razie nie bardzo mogę się wczuć w to co napisałeś, ale jeszcze pomyślę. W tej chwili oboje podsunęliście mi pewien pomysł. Znaleźć bounding box obiektu, wyznaczyć jego środek, posortować piksele względem kąta i po prostu łączyć niepołączone piksele sąsiednie. Na razie nie wiem co z tego wyjdzie, ale może coś sensownego (jakieś przeciwwskazania?).
W międzyczasie poszperałem w necie i już wiem, że słowo kluczowe to edge linking/contour closing, ale ciężko znaleźć jakiś algorytm - trafiam na naukowe matematyczne opisy, z których ciężko korzystać.
Dzięki za pomoc i czekam na kolejne pomysły/opinie :)
a ile masz zrobione? ja widzę to co najmniej trzy fazy problemu.
Problem można ugryźć tak: (MarekR22 napisał co trzeba zrobić, ale nie napisał jak to zrobić :) )
*******
*A*****
**BCDE*
***FGH*
***IJK*
*******
to kolejno punkty: EDCBABFIJKH
-----A A'-----
\ /
B B'
/ \
-----C C'`code>punkty B i B' to są te najbliższe 2 punkty które będziemy łączyć. Nowa obwiednia (już jeden wielokąt):`
-----A A'-----
\ /
B===B'
/ \
-----C C'-----
nowa obwiednia idzie kolejno przez punkty: ..., A, B, B', A', ..., C', B', B, C, ...
ale nie może iść tak: ..., A, B, B', C', ..., A', B', B, C, ... bo będzie się krzyżować.
Jak to wykonać:
Dalej już wiesz po której stronie są kąty zewnętrzne/wewnętrzne. Przykładowo jeśli idąc od A do B zewnętrze jest po prawej stronie to wędrujesz po wierzchołkach w kierunku A, B, C itd:
liczysz kąt ABC (gdzie B i C to kolejne wierzchołki w obranym kierunku), jeśli mniejszy niż 180* usuwasz wierzchołek kąta, jeśli nie to przechodzisz do następnego punktu. I tak w kółko aż przejdziesz dookoła. Jeśli byś szedł w przeciwnym kierunku trzeba sprawdzać odwrotnie, czy kąty są większe niż 180*.
Kąty 0*/360* to zawsze kąty wypukłe, nie przyrównuj ich do 180*. Nawet ich nie licz, sprawdź czy ramiona kąta się pokrywają.
Oczywiście wszędzie jest mowa o kątach lewoskrętnych.
Punkty 1 i 2 można połączyć.
Kąt ABC jest większy od 180* jeśli (Ax-Bx)(Cy-By)<(Ay-By)(Cx-Bx), dzięki tej zależności można działać na liczbach całkowitych! Chyba wszystkie obliczenia da się przeprowadzić na liczbach całkowitych, korzystaj z iloczynu skalarnego i wektorowego, własności funkcji trygonometrycznych.
Same proste rzeczy, w tym przepisie nie ma przynajmniej żadnych abstrakcji ;)
MarekR22, czego ile zrobione? Na razie wstępnie oczyściłem obraz i zatrzymałem się na tym.
Chwilowo muszę się zająć czymś innym, więc podejmę próbę rozwiązania tego problemu za jakiś czas.
Adf88, przeczytałem to co napisałeś i brzmi sensownie, jednak będę musiał się w to mocniej zagłębić ;)
Dzięki wszystkim za pomoc. Jak się uda coś zrobić to wrzucę wynik :P
Wpadłem na jeszcze lepszy pomysł. Sporo upraszczają się punkty 3 i 4, eliminowane są owe "pułapki". Ważna kwestia leży w sposobie wyznaczania obwiedni. Trzeba ją wyznaczyć tak, aby mieć zawsze ten sam kierunek - lewoskrętny czyli idąc wzdłuż obwiedni zewnętrze mamy po prawej stronie. Jako, że nie pamięta jak się algorytm nazywał (coś z mrówką chyba, a może się nie nazywa :) ) podam o co w nim chodzi. Mamy plamę, przykładowo taką jak poprzednio:
ABCDEFG
1*******
2*X*****
3**XXXX*
4***XXX*
5***XXX*
6*******
Algorytmem floodfill znaleźliśmy pierwszą parę pikseli wnętrza 3D oraz zewnętrza 2D. Teraz lewoskrętnie szukamy sąsiada 3D zaczynając od 2D:
2C - nie
3C - tak, mamy kolejny punkt obwiedni
Teraz szukamy lewoskrętnie sąsiada 3C zaczynając od poprzedniego sąsiada czyli 3D:
2D - nie
2C - nie
2B - tak, mamy kolejny punkt obwiedni
I znowu szukamy lewoskrętnie sąsiada 2B zaczynając od poprzedniego sąsiada czyli 3C:
2C, 1C, 1B, 1A, 2A, 3A, 3B - nie
3C - tak, mamy kolejny punkt obwiedni
I tak dalej dopóki nie powtórzy się sekwencja pierwszy-drugi czyli w naszym przypadku dopóki nie powtórzy się sekwencja 3D-3C (jej już nie dublujemy).
Uwaga! Plama z jednego piksela zapętliłaby algorytm, trzeba sprawdzić czy pierwszy piksel plamy nie jest otoczony samą bielą.
Również w celu uproszczenia polecam na czas obliczeń dodać z każdego brzegu obrazka jeden piksel białego odstępu, nie będziesz musiał sprawdzać, czy nie wychodzisz poza granice obrazka.
Wracając do punktu 3 czyli łączenia wielokątów. Poprzedni sposób nie był dobry, zawierał pewną lukę, ale zostawmy go.
Zaczynamy tak samo od wyszukania dwóch najbliższych punktów różnych plam, które są dostatecznie blisko. Wiedząc, że obie obwiednie są lewoskrętne wystarczy połączyć je tak, aby skrętność została zachowana. W przykładzie który przedstawiłem fragmenty lewoskrętnych obwiedni figur to:
...->C->B->A->... oraz ...->A'->B'->C'->...
Łączymy w punktach B i B', aby zachować skrętność (kolejność punktów) musimy połączyć je tak:
...->C->B->B'->C'->...->A'->B'->B->A->...
I to wystarczy.
Wracając do punktu 4, nie wyznaczamy zewnętrza gdyż wiemy gdzie ono jest, znamy skrętność obwiedni. Wystarczy iść wzdłuż obwiedni i sprawdzać, czy kąty są mniejsze od 180* (wariant pierwszy).
No, sytuacja sporo się uprościła, teraz już nie będzie to takie trudne, nie trzeba liczyć żadnych kątów, prostych, przecięć itp., wszystko da się zrobi na liczbach całkowitych.