Wielkość tajemnicy księżyca

Jestem pewien, że słyszałeś, że księżyc zmienia swój rozmiar. Kiedy jesteś zakochany i masz szczęście, księżyc ma prawie dwa razy większy rozmiar niż normalne sytuacje. Niektórzy twierdzą, że przyczyną jest atmosfera, która działa jak soczewka. Inni uważają, że to tylko kwestia porównania z innymi obiektami, takimi jak drzewa w pobliżu. Każde wyjaśnienie, które przeczytasz, jest dość subiektywne.

Wielkość nauki o księżycu

Ok, jesteśmy programistami, prawda? Opieramy się na faktach, prawda? Oto eksperyment:

1. Weź ładny aparat, który ręcznie ustawia czas i przysłonę.
2. Ustaw aparat na maksymalny poziom powiększenia.
3. Wyjdź, zrób kilka zdjęć księżyca, aby wykryć najlepsze ustawienia, aby księżyc był ostry, a oświetlenie w porządku.
4. Zapamiętaj ustawienia
5. Rób zdjęcia księżyca z tymi ustawieniami za każdym razem, gdy uważasz, że księżyc jest duży lub mały.
6. Oblicz rozmiar księżyca w pikselach

Aparat nie kłamie, prawda? Licząc jasne piksele, możemy skutecznie zmierzyć rozmiar księżyca - przynajmniej w pikselach.

Jeśli rozmiar jest taki sam na wszystkich zdjęciach, oznacza to błąd w naszym mózgu. Jeśli rozmiar się różni, jest miejsce na spekulacje

• księżyc naprawdę rośnie (ale co je?)
• występuje efekt soczewki atmosferycznej
• księżyc ma łuk eliptyczny i czasami jest bliżej, a czasem dalej od ziemi
• ...

Ale zostawię to otwarte, dopóki twoje zadanie nie zostanie ukończone. Oczywiście chcesz z góry wiedzieć, czy twoje oprogramowanie może dokładnie obliczyć rozmiar księżyca.

Zadanie

Biorąc pod uwagę kilka zoptymalizowanych zdjęć Księżyca, proszę obliczyć jego rozmiar. Optymalizacja jest następująca: piksele są czarne lub białe. Nic pomiędzy. Bez antyaliasingu. To sprawia, że ​​jest to łatwe, prawda?

Zastrzeżenie: księżyc nie zawsze jest pełny, wiesz ... może być sierpem! Ale nawet w kształcie sierpa rozmiar księżyca jest większy. Proszę obliczyć pełny rozmiar.

• Twój program pobiera PNG jako dane wejściowe, np. Jako argument wiersza polecenia nazwy pliku, przesyłany do stdinlub jako obiekt Bitmap (standardowej biblioteki frameworka), jeśli napiszesz funkcję zamiast programu.
• Twój program działa z dowolną rozsądną wielkością bitmapy wejściowej, niekoniecznie kwadratową. Gwarantowana jest minimalna szerokość i wysokość 150 pikseli.
• Pełnia księżyca pokrywa co najmniej 25% zdjęcia.
• Twój program wyświetla obliczony rozmiar księżyca w pikselach, tak jakby był pełnią księżyca.
• Zakładamy, że księżyc jest idealną kulą.
• Dokładny rozmiar jest zawsze liczbą całkowitą, ale możesz podać liczbę dziesiętną, jeśli obliczenia ją zwrócą.
• Dokładność powinna wynosić od 98% do 102%. (To raczej zgadywanie niż coś, co mógłbym zagwarantować, że będzie możliwe do osiągnięcia. Jeśli uważasz, że jest to zbyt trudne do osiągnięcia, zostaw komentarz).

Aktualizacja :

• Środek księżyca niekoniecznie musi znajdować się na środku zdjęcia.
• Minimalny widoczny obszar to 5% księżyca lub 1,25% całkowitej liczby pikseli.
• Zdjęcie jest zrobione w taki sposób, aby cały księżyc pasował do obrazu, tj. Całkowita liczba pikseli jest górną granicą wielkości księżyca.
• Księżyc nie zostanie przycięty / obcięty.

Przykłady

Jeśli chcesz, możesz wygenerować własne próbki przy użyciu pliku mieszania . Stworzyłem dla ciebie następujące zdjęcia. Możesz policzyć piksele w pliku PNG za pomocą WhitePixelCounter.exe (wymaga .NET), aby sprawdzić, czy obraz zawiera tylko czarno-białe piksele i ile z nich.

Poniższe obrazy 256 x 256 pikseli różnią się ilością białych pikseli, ale wszystkie powinny mieć obliczony rozmiar księżyca wynoszący 16416 pikseli.

Te obrazy 177 x 177 pikseli powinny zwracać 10241 pikseli. Obrazy są w zasadzie takie same, ale tym razem zastosowano aparat o innej ogniskowej.

Próbki niekwadratowe i niecentrowane z wynikiem 9988:

Och, na razie nie mam implementacji referencyjnej, a nawet nie wiem, czy mogę coś zaimplementować. Ale w moim umyśle istnieje silne przekonanie, które mówi mi, że musi to być matematyczne rozwiązanie.

Zasady

To jest Code Golf. Najkrótszy kod na 30.03.2015 zostanie zaakceptowany.

Mathematica 126 119 109 bajtów

Mathematica może mierzyć wydłużenie elementu na obrazie. Księżyc w pełni, będąc idealnie symetrycznym, ma wydłużenie 0, w skali od 0 do 1.

Słabnący księżyc staje się coraz bardziej wydłużony, maksymalnie do około 0,8.

0.998 -0.788 x-0.578 x^2 był empirycznie ustalonym modelem (opartym na dużych zdjęciach) do „przewidywania pełni księżyca (według obszaru), biorąc pod uwagę jego wydłużenie.

Dostosowałem model 1- 0.788 x -0.578 x^2tak, aby przy dokładnie zerowym wydłużeniu (pełnia księżyca) model zwrócił 1 dla współczynnika skali pikseli. Oszczędza 4 bajty i nadal pozostaje w granicach dokładności.

Ten model jest używany do obrazów o dowolnym rozmiarze. Obraz księżyca nie musi być wyśrodkowany. Nie musi też obejmować stałej części zdjęcia.

Oto punkty danych (wydłużenie, displayMoonPixels / fullMoonPixels) dla dużych obrazów i model paraboliczny, który został wygenerowany w celu dopasowania danych. Modele liniowe pasują dobrze, ale model kwadratowy jest martwy, w granicach (patrz poniżej).

Tutaj dane pochodzą z dużych zdjęć. Podobnie jest z modelem

Poniżej dane (czerwone punkty) pochodzą z małych zdjęć. Model (niebieska krzywa) to model generowany przez duże obrazy, taki sam jak pokazano powyżej.

Najmniejszy półksiężyc ma 7,5% powierzchni księżyca w pełni. (Najmniejszy półksiężyc wśród dużych zdjęć to 19% pełni księżyca.) Gdyby model kwadratowy był oparty na małych zdjęciach, dopasowanie poniżej byłoby lepsze, tylko dlatego, że pomieściło mały półksiężyc. Wytrzymały model, który wytrzymałby szeroki zakres warunków, w tym bardzo małe półksiężyce, byłby lepiej wykonany z większej liczby zdjęć.

Bliskość dopasowania pokazuje, że model nie został na stałe zakodowany dla podanych zdjęć. Możemy być całkiem pewni, że wydłużenie księżyca jest niezależne od wielkości zdjęcia, jak można się spodziewać.

fpobiera obraz ijako dane wejściowe i wyjściowe przewidywanego rozmiaru pełni księżyca w pikselach. Działa w przypadku ujęć poza środkiem.

Jak pokazują poniższe dane, są to wszystkie przypadki testowe z wyjątkiem jednego. Księżyce były ułożone od pełnych do najbardziej pomniejszonych.

i_~c~t_ := Max@ComponentMeasurements[i, t][[All, 2]];
f@i_ := i~c~"Count"/(1 - 0.788 x - 0.578 x^2 /. x -> i~c~"Elongation")

Na zdjęciu może pojawić się więcej niż jeden komponent obrazu. Nawet pojedynczy piksel oddzielony od pozostałych będzie uważany za odrębny składnik. Z tego powodu konieczne jest przeszukanie „wszystkich” komponentów, aby znaleźć ten, który ma większą liczbę pikseli. (Jedno z małych zdjęć ma więcej niż jeden komponent obrazu.)

Duże zdjęcia

Prognozy wielkości księżyca wykonane na dużych zdjęciach były jednakowo dokładne.

{"predicted size of full moon", f[#] & /@ large}
{"accuracy", %[[2]]/16416}

{„przewidywane rozmiary księżyca w pełni”, {16422., 16270.9, 16420.6, 16585.5, 16126.5, 16151,6}}

{„dokładność”, {1.00037, 0.991161, 1.00028, 1.01033, 0.982367, 0.983891}}

Małe zdjęcia

Prognozy wielkości księżyca wykonane z małych zdjęć były jednolite, z jednym wielkim wyjątkiem, ostatecznym zdjęciem. Podejrzewam, że problem wynika z faktu, że półksiężyc jest bardzo wąski.

{"predicted sizes of full moon", f[#] & /@ small}
{"accuracy", %[[2]]/10241}

{„przewidywane rozmiary księżyca w pełni”, {10247.3, 10161., 10265.6, 10391., 10058.9, 7045.91}}
{„dokładność”, {1.00061, 0.992192, 1.0024, 1.01465, 0.982221, 0.68801}}

J, 227 207 bajtów (błąd maksymalny 1,9%)

Moją główną ideą jest to, że jeśli znajdziemy 3 punkty na konturze Księżyca, które również znajdują się na konturze Księżyca w pełni, możemy obliczyć okrąg tych punktów. To koło będzie w pełni księżyca.

Jeśli znajdziemy dwa białe punkty o maksymalnej odległości, zawsze będą to takie punkty, które będą albo prawdziwą przekątną w pełni księżyca, albo punktami końcowymi półksiężyca. Możemy znaleźć parę punktów o największej odległości na dowolnym wykresie, wybierając punkt najdalej od dowolnego punktu początkowego, a następnie wybierając punkt najdalej od wybranego.

Znajdujemy trzeci punkt o maksymalnej wartości iloczynu odległości od poprzednich punktów. To zawsze będzie na obrysie i na zewnętrznej stronie półksiężyca lub większej stronie garbu.

Średnica koła jest obliczana jako długość jednego boku podzielona przez zatokę przeciwnego kąta.

Złożoność czasowa tej metody jest liniowa pod względem wielkości obrazu wejściowego.

Kod

f=.3 :0
load'graphics/png'
i=.readpng y
p=.(,i=_1)#|:,"%.0 1|:,"0/&>/<@i."*$i
s=.%:+/|:*:(-1|.]) (([,],:m@(*&d))(m@d))(m=.p{~(i.>./)@])(d=.+/@:*:@((|:p)-])) 0{p
o.*:-:({.s)%0 o.((+/-2*{.)*:s)%2**/}.s
)

Funkcja oczekuje, że nazwa pliku wejściowego jest ciągiem.

(W przypadku (nieco) bardziej czytelnej wersji sprawdź historię zmian.)

Wyjaśnienie kodu

• p to lista współrzędnych białych pikseli (zwanych punktami w przyszłości)
• funkcja d oblicza odległości między elementami p i danym punktem

• druga część definicji s tworzy listę 3-punktową:

  • A jest najdalszym punktem od pierwszego punktu na liście
  • B jest najdalszym punktem od A
  • C jest punktem o maksymalnej wartości odległości od A razy odległości od B

• s jest bokami trójkąta ABC

• ostatnia linia oblicza obszar koła ABC, którym jest pełnia

Wyniki

Największy błąd wynosi 1,9%.

Obrazy są w tej samej kolejności co w pytaniu.

Output  Accuracy
----------------
  16407 0.999453 NB. Large images
16375.3 0.997523
16223.9 0.988301
16241.5 0.989369
16262.6 0.990654
16322.1 0.994279
10235.3 0.999445 NB. Small images
10235.3 0.999444
10221.2 0.998067
10220.3 0.997978
  10212 0.997169
10229.6  0.99889
9960.42 0.997239 NB. Offset images
9872.22 0.988408
10161.8   1.0174
9874.95 0.988681
 9805.9 0.981768

Matlab 162 156 (niezupełnie na obecnym marginesie błędu)

Po pierwsze: dokładność wynosi poniżej 2% dla wszystkich obrazów oprócz jednego w każdej z dwóch serii, gdzie jest większa (około 5% i 14%). Moje podejście polegało na znalezieniu dwóch pikseli księżyca, które znajdują się najdalej od siebie, a następnie na oszacowaniu średnicy.

a=imread(input(''));                 %read input image
b=a(:,:,1)>0;                        %binarize red channel
s=size(b);                           %get size of the image
[x,y]=meshgrid(1:s(1),1:s(2));       
z=(x+i*y).*b;z=z(z~=0);              %find the coordinates of all white pixels (as a list)
o=ones(size(z(:)))*z(:)';            
disp(max(max(abs(o-o.').^2))*pi/4);  %calculate the maximum of the distance between each possible pair and evaluate area formula

Są to wyniki dokładności (odchylenie względne 1 - (predicted size / real size))

0.0006 0.0025 0.0169 0.0500 0.0521 0.0113 0.0006 0.0006 0.0026 0.0472 0.1383 0.0131

C # - 617

To rozwiązanie nie działa dla wszystkich obrazów, ponieważ na jednym z nich nachylenie (m) staje się nieskończonością.

Zasada została wspomniana wcześniej:

1. Znajdź dwa punkty o maksymalnej odległości (czerwony)
2. Wyobraź sobie linię między nimi (czerwony)
3. Wyobraź sobie linię o prostokątnym kącie pośrodku (zielona)
4. Znajdź białe punkty na zielonej linii
5. Użyj tego, który ma maksymalną odległość od innych punktów (zielony)
6. Oblicz powierzchnię koła z trzech punktów

Problemem jest przypadek, w którym nachylenie ma nieskończoność. Można obejść ten problem, obracając obraz o 90 ° lub w kodzie, yzamiast tego zapętlając wokół osi x.

double A(Bitmap b){var a=new List<P>();for(var y=0;y<b.Height;y++)for(var x=0;x<b.Width;x++)if(b.GetPixel(x,y).R>0)a.Add(new P{x=x,y=y});double c=0.0,d=0.0,e=0.0,f=0.0,g=0.0,n=double.MaxValue;foreach(var h in a)foreach(var i in a){var t=Math.Sqrt(Math.Pow(h.x-i.x,2)+Math.Pow(h.y-i.y,2));if(t>c){d=h.x;f=i.x;e=h.y;g=i.y;c=t;}}c=(f-d)/(e-g);for(int x=0;x<b.Width;x++){int y=(int)(c*x+((e+g)/2-c*(d+f)/2));if(y>=0&&y<b.Height&&b.GetPixel(x,y).R>0){var s=(g-e)/(f-d);var q=(y-g)/(x-f);var j=(s*q*(e-y)+q*(d+f)-s*(f+x))/(2*(q-s));var k=-(j-(d+f)/2)/s+(e+g)/2;var l=(j-d)*(j-d)+(k-e)*(k-e);if(l<n)n=l;}}return Math.PI*n;}

Minimalna dokładność wynosi

• + 1,89% dla obrazów 256 pikseli
• -0,55% dla obrazów 177 pikseli
• -1,66% dla obrazów niekwadratowych