Szybkie odpowiedzi na indywidualne pytania
Co robisz, jeśli twój obraz nie ma tego samego rozmiaru na każdej osi?
W pracy wykorzystano kwadratowe obrazy o bokach o sile 2. Jest to dla ułatwienia wyjaśnienia, ale nie jest konieczne do działania algorytmu. Sekcja 3.1:
Bez utraty ogólności możemy założyć, że n jest potęgą 2.
Oznacza to, że założenie to nie jest wymagane do działania algorytmu.
Czy możliwe jest uruchamianie JFA na każdej osi osobno i nadal uzyskiwanie przyzwoitych wyników?
Działa na każdej osi oddzielnie może dać więcej nieprawidłowych wyników pikseli, i trwać dłużej działać w większości przypadków. W skrajnych przypadkach, gdy jedna z długości boków obrazu jest mniejsza niż 8 (liczba kierunków skoku), może być szybsza, ponieważ algorytm traktuje te 8 kierunków sekwencyjnie, ale w przypadku szerszego obrazu oddzielenie osi traci przewagę równolegle.
W mojej sytuacji idealnie staram się wspierać zarówno nasiona jednopunktowe, jak i nasiona o dowolnym kształcie
W artykule wspomniano o nasionach o dowolnym kształcie w sekcji 6 pod podpozycją „Ogólny schemat Voronoi”:
... nasze algorytmy traktują tak uogólnione nasiona jako zbiory nasion punktowych, a zatem oczekują odziedziczenia dobrej wydajności uzyskanej dla nasion punktowych.
Więc pod warunkiem, że pasuje do Twojego celu modelowania dowolnych kształtów jako zbiorów pikseli, nie musisz dostosowywać algorytmu. Po prostu wprowadź teksturę, która oznaczy wszystkie piksele w nasionach o dowolnym kształcie tym samym numerem nasion, ale w różnych lokalizacjach.
Prawdopodobnie nawet ważone nasiona, w których odległość do nasion jest regulowana przez mnożnik i / lub sumator, aby dać większy lub mniejszy wpływ
W przypadku „ważenia nasion, takich jak multiplikatyw i dodatek”, w dokumencie wspomniano jedynie o możliwości przejścia w rozdziale 8, jako potencjalnej przyszłej pracy. Jednak powinno to być łatwe do wdrożenia, pod warunkiem, że pożądana waga może być zawarta w danych początkowych przekazywanych z piksela na piksel.
Bieżący algorytm przechodzi, <s, position(s)>aby określić ziarno i jego pozycję, i tylko jedno ziarno jest zapisywane na piksel jednocześnie. Rozszerzenie tej funkcji do przechowywania <s, position(s), weight(s)>zapewnia wszystkie informacje wymagane do ważenia funkcji odległości i obliczenia, czy nowe ziarno przekazywane do piksela jest bliżej niego niż to, które obecnie przechowuje.
Możesz nawet dołączyć dwie wagi, jedną multiplikatywną i jedną addytywną, i po prostu ustaw multiplikatywną na 1, a addytywną na 0, gdy nie jest to wymagane. Wówczas twój algorytm obejmowałby możliwość zastosowania do nasion o wielokrotnym ważeniu, nasion o dodatnim ważeniu, a nawet kombinacji obu jednocześnie lub niektórych z nich. To by tylko potrzebowało
<s, position(s), multiplicative(s), additive(s)>
a obecny algorytm byłby równoważny z tym nowym algorytmem używającym
<s, position(s), 1, 0>
Szczegółowe wyjaśnienie dlaczego
Jak w artykule, wszystkie zastosowania log() odnoszą się do logarytmu podstawowego 2.
Algorytm nie musi być dostosowywany do różnych długości boków
Jeśli długości boków nie są równe i nie są potęgami 2, nie ma potrzeby dostosowywania algorytmu. Zajmuje się już pikselami na krawędzi obrazu, dla których niektóre kierunki skoku prowadzą poza obraz. Ponieważ algorytm już pomija informację o ziarnie dla kierunków, które prowadzą poza obraz, szerokość lub wysokość, która nie jest potęgą 2, nie będzie problemem. W przypadku obrazu o szerokości W i wysokości H maksymalny wymagany skok będzie wynosił
2⌈log(max(W,H))⌉−1
W przypadku równej szerokości i wysokości N zmniejsza się do
2⌈log(N)⌉−1
W przypadku długości boku N, która jest potęgą 2, zmniejsza się do
2log(N)−1=N/2
zgodnie z opisem w artykule.
Mówiąc bardziej intuicyjnie, zaokrąglij maksymalną długość boku do następnej potęgi 2, a następnie zmniejsz ją o połowę, aby uzyskać maksymalny rozmiar skoku.
To zawsze wystarcza, aby pokryć każdy piksel na obrazie z każdego innego piksela na obrazie, ponieważ przesunięcie do dowolnego piksela będzie w zakresie od 0 do N-1, jeśli najdłuższa długość boku wynosi N. Kombinacje mocy 2 z Od 0 do N / 2 obejmie każdą liczbę całkowitą do N-1, jeśli N jest potęgą 2, a jeśli N nie jest potęgą 2, objęty zasięg może być większy niż wymagany, ze względu na przyjęcie pułapu logarytmu ( zaokrąglając w górę do następnej potęgi 2).
Obrazy z bokami nieprzekraczającymi potęgi 2 nie będą drastycznie mniej wydajne
Liczba skoków zależy od najdłuższej długości boku, powiedzmy L. Jeśli L jest potęgą 2, liczba skoków wynosi . Jeśli L nie jest potęgą 2, liczba skoków wynosi . W przypadku dość dużego obrazu nie będzie to duża różnica.log(L)⌈log(L)⌉
Na przykład obraz 1024 na 1024 będzie wymagał 10 iteracji skoków. Obraz 512 na 512 będzie wymagał 9 iteracji skoków. Wszystko między tymi dwoma rozmiarami będzie wymagało 10 powtórzeń. Nawet w najgorszym przypadku obrazu o sile nieco większej niż 2, jak na przykład obraz 513 na 513, będzie wymagał tylko 1 dodatkowej iteracji, która w tej skali jest o około 11% większa (10 zamiast 9).
Obrazy niekwadratowe są mniej wydajne na obszar
Ponieważ liczba wymaganych iteracji zależy od najdłuższej długości boku, czas potrzebny na zdjęcie 1024 na 1024 będzie takie samo jak na zdjęcie 1024 na 16. Kwadratowy obraz pozwala objąć większy obszar tą samą liczbą iteracji.
Rozdzielenie osi może obniżyć jakość
Rozdział 5 artykułu opisuje możliwe błędy. Ścieżka z każdego innego piksela jest osiągalna dla każdego piksela, ale niektóre ścieżki nie przynoszą poprawnego najbliższego ziarna, ponieważ ziarno nie jest najbliższe poprzedniemu pikselowi na ścieżce. Piksel, który nie pozwala na rozmnażanie się nasion, mówi się, że „zabił” to ziarno. Jeśli najbliższe ziarno od piksela zostanie zabite na wszystkich ścieżkach do tego piksela, wówczas piksel zapisze inne ziarno i na ostatecznym obrazie pojawi się niepoprawny kolor.
Musi istnieć tylko jedna ścieżka, która nie zabija ziarna, aby ostateczny wynik był poprawny. Niepoprawne kolory występują tylko wtedy, gdy wszystkie ścieżki od prawidłowego ziarna do danego piksela są zablokowane.
Jeśli ścieżka obejmuje naprzemienne skoki w poziomie i pionie, oddzielenie osi uniemożliwi tę ścieżkę (wszystkie skoki w poziomie zostaną wykonane przed wszystkimi skokami w pionie, co uniemożliwi przemianę). Skoki po przekątnej nie będą w ogóle możliwe. Tak więc każda ścieżka, która zmienia się lub zawiera skośne skoki, zostanie wykluczona. Każdy piksel nadal będzie miał ścieżkę do każdego innego piksela, ale ponieważ jest teraz mniej ścieżek, istnieje większe prawdopodobieństwo, że dany piksel zostanie zablokowany przed otrzymaniem właściwego ziarna, więc ostateczny wynik będzie bardziej podatny na błędy.
Rozdzielenie osi prawdopodobnie wydłuży algorytm
Skuteczność zostałaby prawdopodobnie zmniejszona przez oddzielenie osi, ponieważ zalewanie nie byłoby już wykonywane równolegle, ale zamiast tego powtarza się dla każdej osi. W przypadku 2D zajęłoby to prawdopodobnie około dwa razy więcej, a w przypadku 3D około 3 razy dłużej.
Może to być nieco złagodzone przez brak skoków po przekątnej, ale nadal oczekiwałbym ogólnego zmniejszenia wydajności.