Witam,
pisze program rysujący obrys na obrazku,
obrazki są średnich rozmiarów, około 100x70.
Zapewne powinienem wykorzystać to, że krawedzie obrazu wyznaczyłem algorytmem Sobela, ale sądzę, że uzyskałem O(n^3+), albo o wiele, wiele więcej.
Mam obraz z 256 możliwościami kolorów, gdzie wyższy oznacza jaśniejszy.
Zadanie to wyznaczenie najjaśniejszej ścieżki z punktów, których początki są wyznaczone przez algorytm-sobel'a.
Innymi słowy, mam:
•plik oryginalny w pamieci - obraz A
•maskę przedstawiającą wynik pracy algorytmu sobela dla obrazu A
•złożoność O(n^3+)
Czy mogę liczyć na jakąś wskazówkę? Algorytm ma być zmodyfikowanym algorytmem Dijkstry,
mógłby mi ktoś udzielić jakiejś wskazówki?
PS •Próbowałem, przy uzyciu dijkstry liczyć jasność ścieżki na podstawie iloczynu czynników, które są niejako procentowymi odwrotnościami jasności, tj. jeśli przechodzę przez pole najjaśniejsze, tj. wartość, to mnożę "cechę aktualnie rozważanej ścieżki" przez 100-(jasnosc+1)/255, gdzie jasnosc to kolor piksela. Doszedłem jednak do wniosku, że nawet double nie pomieści tak szczegółowych liczb.
Teraz piszę ten algorytm w opraciu o to, że będę szedł tak długo, jak mogę po 'zabitowanej' masce sobela, aż znajdę się najbliżej punktu docelowego. Jeśli do niego nie dojdę, to będę uruchamiał zwykłą dijkstrę na pikselach, a w momencie natknięcia się na kolejną "plamę zabitowanych pixeli" na masce Sobel'a, przejdę nią tak długo, aż znajdę najbliższy i najjaśniejszy punkt w okolicach punktu docelowego.
Z wielką przyjemnością przeczytam każdą uwagę lub pomysł.
EDIT
mógłby mi ktoś powiedzieć, czy algorytm wyznaczania działów wodnych może pomóc w tym zadaniu? proszę również o jakieś wskazówki gdzie mogę znaleźć więcej informacji o nich - wyglądają na bardzo ciekawe, ale, jest (chyba?) mało publikacji o nich