Czy jest jakaś lista dyskusyjna, mailowa czy forum anglojęzyczne, gdzie
można zapytać się o szczegóły mało znanych algorytmów?
Przykładem jest alternatywa wyszukiwania przecięć odcinków metodą
zamiatania - metoda Balabana rekurencyjnego podziału obszaru na pasy.
Opis jest http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf
i znalazłem implementację w Scali:
https://github.com/mhodovaniuk/segment-intersection
W tej implementacji wyrzuciłem powiązania ze ScalaFX i JavaFX,
poprawiłem to, że nie widział przecięć linii poziomej - bo dla poziomej
nie ustawiał jej flagi że jest pozioma. I dla przykładowych danych, do
10 odcinków działa, choć ta metoda ma taki urok że daje powtarzające się
przecięcia - trzeba je wpisać do listy, posortować i dać uniq.
Ale dla dużych danych , 10 tysięcy odcinków następuje przepełnienie
stosu. Co prawda treeSearch wywołuje się tylko z 15 razy (każde
wywołanie jednak obciąża stos pośrednimi listami) natomiast gdy pas już
jest bardzo wąski woła searchInStrip, które woła siebie bez końca.
Chodzi o to, że zbiór odcinków w pasie dzieli na zbiór nie
przecinających się, obejmujących pas - zwanych schodami i pozostałe.
Problem jest w tym, że metoda ta na wejściu dostaje odcinki, które w
ogóle nie są w pasie, pas to np. współrzędne x=100..x=101 a my mamy ze
sto odcinków leżących po lewej stronie pasa. Wybór schodów powoduje że
jest to zbiór pusty, natomiast zbiór pozostałych to zbiór wejściowy,
wcale nie zmniejszony, więc po podziale metoda znów siebie woła.
Z autorem implementacji w Scali na githubie - mhodovaniuk nie można się
skontaktować, są podane tylko jego projekty a nie kontakt

do góry

W dniu niedziela, 21 grudnia 2014 10:22:02 UTC+1 użytkownik Borneq napisał:
> Czy jest jakaś lista dyskusyjna, mailowa czy forum anglojęzyczne, gdzie
> można zapytać się o szczegóły mało znanych algorytmów?

Na dzień dobry spróbowałbym stackoverflow.

> Przykładem jest alternatywa wyszukiwania przecięć odcinków metodą
> zamiatania - metoda Balabana rekurencyjnego podziału obszaru na pasy.
> Opis jest http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf

Naprawdę potrzebujesz algorytmu działającego
w O(N log[N] + K) bo O ((N+K)log[N]) nie wystarcza?

Znalazłem coś takiego:
https://code.google.com/p/balaban-segments-intersect
ions/

Implementacje tego i innych popularnych algorytmów.
Ale bez szczególnych przypadków.

pzdr
bartekltg

do góry

W dniu 2014-12-21 o 16:25, bartekltg pisze:
> Naprawdę potrzebujesz algorytmu działającego
> w O(N log[N] + K) bo O ((N+K)log[N]) nie wystarcza?

Bardziej niż o logarytmy w wielkim O, chodzi mi o czynnik stały, bo w
metodzie zamiatania mamy operacje na strukturach AVL i kolejce
priorytetowej. Zresztą algorytm też skomplikowany, w zasadzie to już mam
zamiatanie i drzewa AVL, choć nie sprawdzałem prędkości, to jeszcze są
jakieś różnice względem szukania brute-force.

>
> Znalazłem coś takiego:
> https://code.google.com/p/balaban-segments-intersect
ions/

Dzięki za namiary, nie zauważyłem tego.

Pozdrawiam

do góry

W dniu niedziela, 21 grudnia 2014 17:22:38 UTC+1 użytkownik Borneq napisał:
> W dniu 2014-12-21 o 16:25, bartekltg pisze:
> > Naprawdę potrzebujesz algorytmu działającego
> > w O(N log[N] + K) bo O ((N+K)log[N]) nie wystarcza?
>
> Bardziej niż o logarytmy w wielkim O, chodzi mi o czynnik stały, bo w

A skąd wniosek, że ten będzie mieć mniejszą stałą?

> metodzie zamiatania mamy operacje na strukturach AVL i kolejce
> priorytetowej.

AVL to dość szybka struktura. Kolejka piorytetowa
to już w gogole sprinter.

A w tym algorytmie:

"To find Tnt ( So ) we use a collection of vertical
strips on the plane organized in a tree structure,"

Jakieś drzewo masz. Jesteś więć do przodu o co
najwyżej równoważenie.

> Zresztą algorytm też skomplikowany, w zasadzie to już mam
> zamiatanie i drzewa AVL, choć nie sprawdzałem prędkości, to jeszcze są

Twoim celem chyba nie jest wydajne przetwarzanie wielokątów,
tylko jest to pomocniczy algorytm, do pomysłu na wspomaganie
wyszukiwania granic na obrazku, wszytko w celu liczenia komórek.
Nie przekombinowuj na tak głebokim poziomie iteracji.
Ja bym sprawdził choćby brute forcem czy poziom wyzej dostaje
sensowne wielokąty/komórki. Siedizsz nad tym tygodnie, a możę
w ogóle nie tędy droga.

> jakieś różnice względem szukania brute-force.

Znaczy daje inne wyniki. To znaczy conajmniej
jedna implementacje jest sknocona;-)


> >
> > Znalazłem coś takiego:
> > https://code.google.com/p/balaban-segments-intersect
ions/
>
> Dzięki za namiary, nie zauważyłem tego.


Jest tego więcej:
https://www.google.com/search?q=Balabana&ie=utf-8&oe
=utf-8#q=Balaban+algorithm+implementation

przynajmniej u mnie wię wyświatla.

pzdr
bartekltg

do góry

On Sunday, December 21, 2014 5:22:38 PM UTC+1, Borneq wrote:
> W dniu 2014-12-21 o 16:25, bartekltg pisze:
> > Naprawdę potrzebujesz algorytmu działającego
> > w O(N log[N] + K) bo O ((N+K)log[N]) nie wystarcza?
>
> Bardziej niż o logarytmy w wielkim O, chodzi mi o czynnik stały, bo w
> metodzie zamiatania mamy operacje na strukturach AVL i kolejce
> priorytetowej. Zresztą algorytm też skomplikowany, w zasadzie to już mam
> zamiatanie i drzewa AVL, choć nie sprawdzałem prędkości, to jeszcze są
> jakieś różnice względem szukania brute-force.

By się wydawalo, że to tylko przecinanie się odcinków, a tu proszę,
skomplikowane algorytmy.

Czy mogę zapytać, co będzie robił program, w którym używasz detekcji
odcinków? Pytam z czystej ciekawości/próżności.

Pozdrawiam

do góry

W dniu 2014-12-21 o 16:25, bartekltg pisze:
> Znalazłem coś takiego:
> https://code.google.com/p/balaban-segments-intersect
ions/
>
> Implementacje tego i innych popularnych algorytmów.
> Ale bez szczególnych przypadków.

Podoba mi się ten program, zrobiony przez samego twórcę algorytmu.
Mierzy. Np . Bentley-Ottman trwa dłużej niż trivial, za to Balaban
krócej i można jeszcze krócej wykorzystując dwa rdzenie procesora.

do góry

W dniu 2014-12-21 o 17:56, M.M. pisze:
> Czy mogę zapytać, co będzie robił program, w którym używasz detekcji
> odcinków? Pytam z czystej ciekawości/próżności.

Tam gdzie używałem dużej ilości przycinania odcinków to była błędna
ścieżka programu - miał dzielić i łączyć obrysy, wróciłem do pierwotnej
wersji - znajdowania jąder i wokoło m.in. za pomocą Voronoi obrysów.
Program w ogóle ma na folderze około 2500 obrazków rozmiaru 512x512
znajdować podejrzane komórki.
Brute-force działa już znacznie lepiej po szybkim odrzucaniu segmentów,
które ma nie brać w ogóle pod uwagę. A te odcinki - zamiatanie i Balaban
to teraz mniej związane z pracą a bardziej hobbystycznie, mam zamiar
opisać algorytmy i zamieścić kod.

Pozdrawiam

do góry

On Sunday, December 21, 2014 8:06:27 PM UTC+1, Borneq wrote:
> W dniu 2014-12-21 o 17:56, M.M. pisze:
> > Czy mogę zapytać, co będzie robił program, w którym używasz detekcji
> > odcinków? Pytam z czystej ciekawości/próżności.
>
> Tam gdzie używałem dużej ilości przycinania odcinków to była błędna
> ścieżka programu - miał dzielić i łączyć obrysy,
Rozumiem że chodzi o ścieżkę rozwoju programu. W programie została użyta metoda, z
której potem trzeba było zrezygnować na rzecz innej metody.

> wróciłem do pierwotnej
> wersji - znajdowania jąder i wokoło m.in. za pomocą Voronoi obrysów.
Brzmi ciekawie, żałuję że nie mam czasu, aby zainteresować się szczegółami
algorytmu.

> Program w ogóle ma na folderze około 2500 obrazków rozmiaru 512x512
Rozumiem, że 2500 obrazków to dużo, więc program działa zbyt wolno i
szukasz lepszych algorytmów/implementacji. Ciekawi mnie jak wyglądają
obrazki. To są zdjęcia z aparatu? Sekwencje zdjęć z kamery? Czy są
generowane jakimś automatem? Możesz podać link do kilku obrazków?


> znajdować podejrzane komórki.
Jakie komórki są podejrzane?


> Brute-force działa już znacznie lepiej po szybkim odrzucaniu segmentów,
> które ma nie brać w ogóle pod uwagę. A te odcinki - zamiatanie i Balaban
> to teraz mniej związane z pracą a bardziej hobbystycznie, mam zamiar
> opisać algorytmy i zamieścić kod.
Chodzi o pracę naukową czy zawodową?

Pozdrawiam

do góry

W dniu 2014-12-22 o 16:44, M.M. pisze:
> Rozumiem że chodzi o ścieżkę rozwoju programu. W programie została użyta metoda, z
której potem trzeba było zrezygnować na rzecz innej metody.

tak,

> obrazki. To są zdjęcia z aparatu? Sekwencje zdjęć z kamery? Czy są
> generowane jakimś automatem? Możesz podać link do kilku obrazków?

http://slajdy.meditest.pl/
tylko teraz nie działa, przykład http://i.imgur.com/sEWFHfY.jpg
Jest to duże zdjęcie o boku 25-30 tysięcy pocięte na kawałki np. 55x55
kawałków o boku 512. Zdjęcie wykonane przez aparaturę powiększającą
obraz jak mikroskop.

>> znajdować podejrzane komórki.
> Jakie komórki są podejrzane?

Duże, niejednorodne jądra, dzielące się jądra i tego typu przypadki.

> Chodzi o pracę naukową czy zawodową?

Zawodową


Pozdrawiam

do góry

On Monday, December 22, 2014 4:53:37 PM UTC+1, Borneq wrote:
> http://slajdy.meditest.pl/
> tylko teraz nie działa, przykład http://i.imgur.com/sEWFHfY.jpg
> Jest to duże zdjęcie o boku 25-30 tysięcy pocięte na kawałki np. 55x55
> kawałków o boku 512. Zdjęcie wykonane przez aparaturę powiększającą
> obraz jak mikroskop.
Jakbym gdzieś coś podobnego już widział... ale niestety nie przypominam
sobie co jest pod mikroskopem?


> Duże, niejednorodne jądra, dzielące się jądra i tego typu przypadki.
Duże w względem średniej wielkości jądra? Niejednorodne
pod względem kształtu, koloru, jednego i drugiego?


Jakie masz efekty na chwilę obecną? Jaka jaki procent podejrzanych
wychwytujesz? Jak często niepodejrzaną klasyfikujesz jako podejrzaną?


> > Chodzi o pracę naukową czy zawodową?
> Zawodową
Fajna praca.

Pozdrawiam

do góry