Nowy, dosyć oryginalny programik

[Piotr Brych]

Chciałbym zaprezentować szanownym koleżankom i kolegom pewien odprysk z moich badań nad automatyczną analizą obrazów nieba.

Wielu z Was zna program AFA który orientuje się na zdjęciu po wskazaniu mu dwóch obiektów o znanych współrzędnych. Niektórzy z Was widzieli na zlocie w Bieszczadach program (nieupubliczniony) który po podaniu wyłącznie dokładnej skali zdjęcia potrafił powiedzieć jaki obszar nieba jest objęty zdjęciem.

Tym razem przedstawiam program o roboczej nazwie IG który lokalizuje na niebie zdjęcie o którym NIC nie wiadomo - nie potrzeba już znać nawet skali w jakiej zostało zrobione. Program w pełni działa jednak tylko teoretycznie bo ilość obliczeń jaka musi być wykonywana przerasta możliwości współczesnych komputerów. Ale jeżeli zadamy na poszukiwania pewne warunki ograniczające np. jasność lub obszar poszukiwań to program całkiem nieźle sobie radzi. Tak więc jak ktoś ma jakieś zdjęcia na których zapomniał już co się na nich znajduje to proponuję skorzystać.

 

Program dostępny jest na http://astronomia.brych.com.pl

[Darek_B]

Arcyciekawe, ale zdajesz sobie sprawę że tym programem "zabiłeś" wszystkie przyszłe zagadki na forum?

[skrzypas]

Ciekawy programik. Możesz coś napisać o algorytmie jaki zastosowałeś?

[Piotr Brych]

Rzeczywiście, zagadki mogą tutaj polec. Ale dzięki temu będzie motywacja do wymyślania jeszcze ciekawszych zagadek.

Co do algorytmu:

Bierzemy dwie gwiazdy na zdjęciu i wszystkie możliwe pary gwiazd z katalogu Tycho2 (jest ich tylko nieco ponad 6 bilionów). Robimy selekcję czy dana para spełnia warunek założonej skali. Np. jeżeli dwie gwiazdy leżą w odległości 10° od siebie a na zdjęciu wskazaliśmy gwiazdy nr 1 i 2 których wzajemna odległość wynosi 1/4 szerokości zdjęcia, to aby tą parę gwiazd uznać za godną dalszej analizy musimy zgodzić się, że szerokość zdjęcia wynosi 4x10=40°. Jeżeli taka wielkość jest dopuszczalna limitem szerokości zdjęcia to do każdej pary która przejdzie ten warunek próbujemy dopasować trzecią, czwartą i piątą gwiazdę z katalogu ale już na zasadzie wzajemnych odległości między gwiazdami. Program poszukuje takiej piątki gwiazd (a jest ich w katalogu tycho2 ok. 100.000.000.000.000.000.000.000.000.000.000 (sto kwintylionów) których wszystkie wzajemne odległości a jest ich 10 (1-2,1-3,1-4,1-5,2-3,2-4,2-5,3-4,3-5,4-5) są proporcjonalne do wzajemnych odległości gwiazd zaznaczonych na zdjęciu przy przyjęciu odległości 1-2 za jednostkę. Inaczej mówiąc szukamy piątki gwiazd w katalogu takiej, że jak na zdjęciu gwiazda 2 leży (mierząc piksele) od gwiazdy 3 dwa razy dalej niż gwiazda 2 od gwiazdy 1 to w wybranej piątce w katalogu też ma być taka zależność w każdej z 10 wzajemnych odległości między gwiazdami.

Jak widać z przytoczonych liczb, konieczne jest nałożenie jakichś ograniczeń na warunki początkowe. Np. jak mamy zdjęcia szerokiego nieba (takie na powiedzmy 10° stopni) to jest niemal pewne, że pięć najjaśniejszych gwiazd na tym zdjęciu ma jasność większą od 6 mag. A więc można obszar poszukiwać zmniejszyć z 2.500.000 wszystkich gwiazd katalogu Tycho2 do ok. 3.000 gwiazd o jasności większej niż 6 mag. Wtedy ilość kombinacji spada z 100.000.000.000.000.000.000.000.000.000.000 do zaledwie 243.000.000.000.000.000.000 a to już postęp znakomity. Jak wstawimy że brane są pod uwagę tylko pary z półkuli północnej z nieba zimowego to mamy już ze 50.000x mniej kombinacji, jak wstawimy jeszcze, że rozmiar zdjęcia leży między 5 a 20° to liczba kombinacji znowu gwałtownie spada do ilości akceptowalnej przez moc obliczeniową komputera.

Edytowane 29 Czerwca 2008 przez Piotr Brych

[szuu]

dobre

 

to mi przypomina że kiedyś zastanawiałem się czy możliwe jest znalezienie na niebie mini-gwiazdozbiorów przedstawiających inicjały dowolnej osoby. teoretycznie chyba to możliwe? zwiększając powiększenie sięgamy to coraz większej ilości gwiazd i w końcu się trafi odpowiedni układ? oczywiście to musiałby robić jakiś program automatycznie. i trochę innym algorytmem: bo nie jest tu ważne idealne dopasowanie do zadanego kształtu, tylko tak żeby było widać że najjaśniejsze gwiazdy w okolicy układają się w odpowiednie literki.

jakbyś coś takiego zrobił to możesz uruchomić astro-SMS - "wyślij swoje inicjały na numer 74XX (4 zł + VAT) a dostaniesz gwiazdkę z nieba (a raczej jej współrzędne)"

[narwik]

Dzięki za wykład. Swoją drogą, to jest ciekawe, jak człowiek rozpoznaje gwiazdozbiory, ot tak, w sekundę po spojrzeniu w górę.

 

A właśnie, w pracy przykładowo mam 4 procesory w kompie, jak widzisz szanse na skompilowanie tej wyszukiwarki tak aby korzystała z wszystkich dobrodziejstw płyt wieloprocesorowych?

Edytowane 30 Czerwca 2008 przez narwik

[grzybu]

To się nazywa przetwarzenie równoległe

[MaPa]

Programik działa pięknie. Wlasnie go przetestowałem na nieopublikowanym zdjęciu z poprzedniej nocy

[skrzypas]

A właśnie, w pracy przykładowo mam 4 procesory w kompie, jak widzisz szanse na skompilowanie tej wyszukiwarki tak aby korzystała z wszystkich dobrodziejstw płyt wieloprocesorowych?

Przy podanym algorytmie nie powinno być z tym raczej problemu.

[JaLe]

U mnie szuka i nic nie znajduje

[ansmann]

A jak to jest z krzywizną pola?

Zdjęcie musi być idealnie "płaskie", czy program sobie z tym radzi?

 

Pozdrawiam

[Piotr Brych]

A jak to jest z krzywizną pola?

 

Krzywizna pola zwiększa błąd i może spowodować, że rozwiązanie nieprawidłowe będzie bardziej pasowało do zdeformowanego obrazu niż prawidłowe. Ale jeżeli błąd wynikły z krzywizny pola nie przekroczy zadanej w procentach tolerancji to rozwiązanie prawidłowe powinno się znaleść wśród wyników.

[Piotr Brych]

U mnie szuka i nic nie znajduje

I dlatego myślę nad zoptymalizowaniem algorytmu i nawet mam już pomysł. Gorzej z wolnym czasem.

A nie znajdywać może z różnych powodów:

- jedna z gwiazd nie jest z Tycho2 (może być np. planetoidą)

- zdjęcie zbyt zdeformowane w stosunku do zadanej tolerancji

- dwie z gwiazd zaznaczonych leżą zbyt blisko siebie (zalecam min. 300 pikseli)

[Piotr Brych]

I dlatego myślę nad zoptymalizowaniem algorytmu

I wymyśliłem!

Jak już napisałem w innym poście program przyśpieszył znakomicie, dzięki czemu jest już możliwe rzeczywiste przeszukiwanie - obejmujące całe niebo. Program najlepiej działa na ciasnych, jasnych gromadach otwartych. Tam gdzie jest kilka jasnych gwiazd skupionych na małym obszarze. Takie zdjęcia, gdzie w kole o średnicy 1° mamy kilka gwiazdek np. do 8.0 mag program lokalizuje w przeciągu minuty bez podania jakichkolwiek danych dodatkowych.

[Mariusz Wołoszyn]

I wymyśliłem!

Jak już napisałem w innym poście program przyśpieszył znakomicie, dzięki czemu jest już możliwe rzeczywiste przeszukiwanie - obejmujące całe niebo. Program najlepiej działa na ciasnych, jasnych gromadach otwartych. Tam gdzie jest kilka jasnych gwiazd skupionych na małym obszarze. Takie zdjęcia, gdzie w kole o średnicy 1° mamy kilka gwiazdek np. do 8.0 mag program lokalizuje w przeciągu minuty bez podania jakichkolwiek danych dodatkowych.

 

To pochwal się na czym polega ta optymaliacja algorytmu, to znaczy w jaki sposób wykorzystujesz skupiska gwiazd do zwiększenia wydajności algorytmu.

 

p.s. a myślałeś np. o odpowiednim poindeksowaniu tych wszystkich par wcześniej?

Edytowane 11 Sierpnia 2008 przez Mariusz Wołoszyn

[Marand]

Program do rozpoznawania gwiazd na niebie powstał również w Pracowni Komet i Meteorów na potrzeby Polskiej Sieci Bolidowej (PFN). Rozpoznaje on automatycznie bez podawania kierunku jakie gwiazdy znajdują się na obrazkach z meteorami. Istnieje możliwość by znalazł również pole widzenia ale trochę to trwa więc przy redukcjach tylko na początku pracuje w takim modzie a dalej podajemy już rozpoznany rozmiar dla danej kamery. Identyfikacja gwiazd przy danym polu widzenia trwa od 2 do 10 sekund w zależności od ilości obiektów wykrytych na obrazku.

 

W naszych obserwacjach polach widzenia sięgają 90 stopni tak więc problemy z dystorsjami są spore ale przy odpowiednio szerokich widełkach szukania pasujących gwiazd program daje radę. Zasięgi naszych kamer ograniczone są mniej więcej do 4-5 mag w zależności od warunków więc gwiazd do sprawdzenia nie są miliony a tysiące.

 

Mój program szuka nie par a od razu trójkątów, a dalej podobnie, szukanie kolejnych pasujących.

 

Pozdrawiam

Marand

[Piotr Brych]

Program do rozpoznawania gwiazd na niebie powstał również w Pracowni Komet i Meteorów

Chętnie zapoznam się z tym programem. A problem jest właśnie w ilości gwiazd. Bo 6-7 mag to mój program wychwytuje w ułamku sekundy (+3 sekundy na wczytanie katalogu). Natomiast znalezienie na niebie układu gwiazd 8-9 mag zaczyna zajmować mu już minuty a 10-11 mag - godziny.

 

Algorytm zoptymalizowałem w ten sposób, że skoro program wie że zdjęcie zajmuje np. 4° to dzieli sobie niebo na komórki zajmujące obszar o takiej średnicy i szuka układu w każdej komórce osobno. Jeżeli jakaś operacja zajmuje czas proporcjonalny do drugiej potęgi z ilości elementów na jakiej się odbywa (a tak z grubsza jest w tym przypadku), to przy 1.000.000 elementów zajmuje to 10^12 jednostek czasu. Ale jeżeli ten zbiór podzielimy na 10.000 komórek po 100 elementów w każdej to zajmie to 10.000 x 100^2 = 10^8 a więc dziesięć tysięcy razy szybciej. W przypadku obliczeń na niewielkiej liczbie elementów (na gwiazdach do 6 mag) zysk z takiej optymalizacji jest zżerany przez dodatkowe operacje które trzeba wykonać na takim bardziej skomplikowanym algorytmie (podział na komórki itp.) ale przy dużej liczbie gwiazd (8-12 mag) zysk ten staje się bardzo widoczny i operacje rzeczywiście wykonują się tysiące razy szybciej (nie sprawdzałem dokładnie ile bo w starej wersji program praktycznie stał w miejscu).

 

Ponadto zmniejszyłem o ok. połowę ilość obliczeń dla każdej piątki gwiazd, wykonywane są tylko niektóre sprawdzenia które równie dobrze selekcjonują piątki gwiazd jak pełne i dopiero gdy one dają poprawny wynik to sprawdzanie wykonywane jest kompletnie ale to już tylko na bardzo nielicznych przypadkach.

[Marand]

Chętnie zapoznam się z tym programem. A problem jest właśnie w ilości gwiazd. Bo 6-7 mag to mój program wychwytuje w ułamku sekundy (+3 sekundy na wczytanie katalogu). Natomiast znalezienie na niebie układu gwiazd 8-9 mag zaczyna zajmować mu już minuty a 10-11 mag - godziny.

 

Te ułamki sekund robią wrażenie. A na jakiej maszynie?

 

Moje przyśpieszacze są raczej specyficzne ze względu na charakter danych. Zwykle jest kilkaset obrazków z jednej kamery które puszczane są serią.

 

Główną optymalizacją jest stworzenie bazy wszelkich trójkątów jakie wynikają z katalogu na starcie programu. zajmuje to dłuższą chwilę i sporo miejsca w pamięci ale potem nie muszę wielokrotnie liczyć odległości między gwiazdami co ze względu na kilka funkcji trygonometrycznych na pewno trochę czasu procesorowi zajmuje. Katalog trójkątów ograniczam od dołu i góry to znaczy boki nie mogą być większe niż rozmiar pola widzenia i nie mniejsze niż 1/20 pola widzenia. Zupełnie odwrotnie do tego co u ciebie, pisałeś że skupiska gwiazd wykorzystujesz do przyśpieszania szukania. W pewnym sensie ograniczenia spełniają rolę podziału nieba na sektory. Przy rozmiarze pola wielkości 1/8 sfery dałem sobie spokój z dzieleniem nieba na kawałki.

 

Spowalniaczem u mnie jest dystorsja. Przy polach 90 stopniowych muszę dawać tolerancję odległości między gwiazdami na poziomie >1 stopnia by program znalazł gwiazdy po brzegi. Duża tolerancja sprawia że przy pierwszych gwiazdach wiele jest pasujących układów i do każdego trzeba niezależnie dodawać kolejne gwiazdy i sprawdzać która rozpoznana kombinacja najlepiej pasuje. Często jest tak że do 3 gwiazd na obrazku pasuje nawet kilkadziesiąt trójkątów z katalogu. Szukając czwartej tych pasujących też potrafi być kilka. dla kolejnych jest co raz więcej boków do sprawdzenia ale i mniej wyników niejednoznacznych.

 

Przy wąskich widełkach program śmiga ale zbyt często zdarzało mu sie pominąć właściwe gwiazdy i wynik był zły. Lepiej niech liczy dłużej ale prawie zawsze trafia. z doświadczenia wyszło że zdarza mu się pomylić gdy ponad połowa obrazka jest w chmurach. na dobrych obrazkach nie myli się.

 

Mariusz

[Piotr Brych]

Zupełnie odwrotnie do tego co u ciebie, pisałeś że skupiska gwiazd wykorzystujesz do przyśpieszania szukania.

Coś się nie zrozumieliśmy. Program nie korzysta ze skupisk jasnych gwiazd do czegokolwiek. Skupiska jasnych gwiazd się po prostu szybciej znajdują bo algorytm działa szybciej jeżeli:

- komórka (rozrzut gwiazd) jest mała (do 1°)

- gwiazdy są jasne (ograniczamy ilość elementów kombinacji)

 

Te ułamki sekund robią wrażenie. A na jakiej maszynie?

Core 2 Quad 6600 - 2,4GHz - 4GB RAM

 

Spowalniaczem u mnie jest dystorsja. Przy polach 90 stopniowych muszę dawać tolerancję odległości między gwiazdami na poziomie >1 stopnia by program znalazł gwiazdy po brzegi. Duża tolerancja sprawia że przy pierwszych gwiazdach wiele jest pasujących układów i do każdego trzeba niezależnie dodawać kolejne gwiazdy i sprawdzać która rozpoznana kombinacja najlepiej pasuje. Często jest tak że do 3 gwiazd na obrazku pasuje nawet kilkadziesiąt trójkątów z katalogu. Szukając czwartej tych pasujących też potrafi być kilka. dla kolejnych jest co raz więcej boków do sprawdzenia ale i mniej wyników niejednoznacznych.

I to jest przyczyna dla której ograniczyłem w programie rozrzut gwiazd do 10°. Poza tym stwierdziłem, że jak zdjęcie ma 20-30° to już człowiek bez pomocy oprogramowania powinien się zorientować co jest na zdjęciu.

 

A jakby ktoś się pytał dlaczego trzeba wskazać pięć gwiazd to odpowiadam, że przy 2,5 mln gwiazd jakie rozpoznaje program praktycznie dopiero układy pięciu gwiazd są niepowtarzalne (w tolerancji odchyłek w rozmiarach rzędu 1%), to znaczy - nie ma na niebie do 12 mag dwóch takich samych (z dokładnością do stałej mnożącej wszystkie odległości) piątek gwiazd. Układów złożonych z 4 gwiazd (spośród 2,5 mln) może być wiele przy takich samych proporcjach odległości, a trójkątów to już chyba miliardy (wszystkich możliwych do utworzenia trójkątów z 2,5 mln gwiazd jest ponad 5 trylionów). Mówiąc inaczej - dopiero przy wskazaniu 5 gwiazd program generuje zazwyczaj jeden wynik w granicach zadanej tolerancji. Gdybyśmy wskazywali tylko 4 gwiazdy - program wyłapał by wiele czwórek które były by b. podobne do tej na zdjęciu. Co innego przy gwiazdach jasnych (do 6 mag). Tutaj czwórka gwiazd by w zupełności wystarczyła.

Edytowane 11 Sierpnia 2008 przez Piotr Brych

[Piotr Brych]

p.s. a myślałeś np. o odpowiednim poindeksowaniu tych wszystkich par wcześniej?

Przyznam się, że nie myślałem jeszcze o takich metodach, nie wiem czy były by one skuteczne ale jest to jakiś pomysł. Choć na pierwszy rzut oka zindeksowanie trylionów trójkątów to masakra - samo odczytanie takiej bazy trwało by dłużej niż poszukiwanie układów tradycyjnie.

Edytowane 11 Sierpnia 2008 przez Piotr Brych

[Marand]

Choć na pierwszy rzut oka zindeksowanie trylionów trójkątów to masakra - samo odczytanie takiej bazy trwało by dłużej niż poszukiwanie układów tradycyjnie.

 

przy trylionach sortowanie faktycznie długo by trwało. u mnie są miliony. Jak baza jest poindeksowana to sprawdzam tylko wstępnie podobne trójkąty a nie całą bazę. Oczywiście baza wstępnie policzona i poindeksowana ma sens jak się rozpoznaje setki obrazków a nie jeden.

 

Czy dobrze zrozumiałem? U ciebie ręcznie zaznacza się 5 gwiazd i program szuka opierając się tylko o te 5 gwiazd?

 

Co do rozpoznawania co to za gwiazdozbiór jest na obrazku przy dużych polach. Spróbuj powiedzieć co jest w tle np tutaj

http://www.pkim.org/?q=pl/node/946

Da się rozpoznać w sekundę?

Edytowane 12 Sierpnia 2008 przez Marand

[Piotr Brych]

Czy dobrze zrozumiałem? U ciebie ręcznie zaznacza się 5 gwiazd i program szuka opierając się tylko o te 5 gwiazd?

Dokładnie tak.

 

Spróbuj powiedzieć co jest w tle

Wizualnie nie mogę załapać co to za rejon nieba. A algorytm mojego programu nie jest dostosowany do takich szerokich ujęć - wynik prawdziwy ginie w stosie fałszywych. Tak więc widać, że programy choć zbliżone w swym zastosowaniu jednak obejmują różne zakresy rozmiarów zdjęć. Ja swój polecam przy zdjęciach :

- poniżej 1° z gwiazdami do 12 mag

- od 1° do 4° z gwiazdami do 10 mag

- od 4° do 10° z gwiazdami do 8 mag.

[Marand]

Dokładnie tak.

No to jeszcze nie automat. Spróbój dodać by program sam znajdował gwiazdy na obrazku i podejmował decyzję które wybrać jako te 5. U mnie właśnie tak jest, żadnej obsługi. Przy czym mnie interesuje nie tylko stwierdzenie w którą stronę "skierowany" jest obrazek a zidentyfikowanie możliwie wszystkich gwiazd na nim. Szukanie nie kończy się na 5, tylko idzie tak długo aż wszystkie gwiazdy zostaną powiązane z katalogiem. Przy okazji robi sie prosta fotometria aperturowa dla zidentyfikowanych obiektów, ale to już inna historia.

 

Na tych obrazkach co podałem link automat daje radę znaleźć i zidentyfikować po kilkanaście gwiazd mimo że ja widzę na nich co najwyżej kilka. Komputery nas pokonują

 

Mariusz

[Mariusz Wołoszyn]

No to jeszcze nie automat. Spróbój dodać by program sam znajdował gwiazdy na obrazku i podejmował decyzję które wybrać jako te 5. U mnie właśnie tak jest, żadnej obsługi. Przy czym mnie interesuje nie tylko stwierdzenie w którą stronę "skierowany" jest obrazek a zidentyfikowanie możliwie wszystkich gwiazd na nim. Szukanie nie kończy się na 5, tylko idzie tak długo aż wszystkie gwiazdy zostaną powiązane z katalogiem. Przy okazji robi sie prosta fotometria aperturowa dla zidentyfikowanych obiektów, ale to już inna historia.

 

Na tych obrazkach co podałem link automat daje radę znaleźć i zidentyfikować po kilkanaście gwiazd mimo że ja widzę na nich co najwyżej kilka. Komputery nas pokonują

 

Mariusz

 

No tak, tylko Twój soft jest do obrazu z kamerek na którym z założenia widać niewiele gwiazd.

IG jest do ręcznej identyfikacji trudniejszych przypadków (wąskie pole, masa gwiazd).

[Piotr Brych]

Spróbój dodać by program sam znajdował gwiazdy na obrazku i podejmował decyzję które wybrać jako te 5.

Takie coś już działa tylko nie było upubliczniane. Na zlocie w Bieszczadach pokazywałem program do seryjnej obróbki zdjęć (ale z podaną skalą która wynikała wprost z użytego sprzętu). Program w 15 sekund identyfikował wszystkie gwiazdy na zdjęciu, opisywał je, podawał środek zdjęcia, kąt pozycyjny oraz listę obiektów które nie pasowały do katalogu (nowe, planetoidy, hot-piksele). Program ma wpisane procedury wyławiania hot-pikseli (odróżnia je od obiektów rzeczywistych).