You are working on the navigation system of a satellite.
The satellite is on a known orbit around Earth so its position is known. However sometimes its orientation is not known so it must be determined in order to get the satellite in an operational state.
The satellite has an onboard camera that can take a grayscale picture.
Your task is to develop an algorithm that can determine the orientation from a single image taken by the onboard camera. An accurate star catalog is available and you can assume that objects of our solar system won't be visible on the image, only the stars listed in the catalog.
Each star is given by four numbers in the catalog: ID, RA, DEC, MAG. ID is an identifier, RA and DEC are spherical coordinates and MAG is the magnitude of the star.
The RA, DEC coordinate system can be thought of as a projection of the Earth bound longitude, latitude system to the sky.
The magnitude of the star can be modelled by -const1*log(brightness/const2)
(a brighter star has smaller MAG).
For more details see the stars.txt
file.
The input is a grayscale, 1000x1000 pixel png image.
The field of view of the camera is known to be 20 degrees, so 1000 pixel distance on the image means approximately 20 degrees difference in direction.
The output should be two 3d unit length vectors: the first line should hold the direction where the camera looks, the second line is an orthogonal vector that is the upward direction on the image.
The 3d coordinate system oriented so that it is easy to convert between the spherical coordinate system and the 3d one:
The direction of the output vectors must be more precise than 0.01 radian.
Three sample images are provided with reference outputs, so you can calibrate your algorithm: the first one looks at Sirius, the second one looks at (parts of) the Ursa Major constellation, the third one looks to the north.
It turns out it is fairly complicated to determine the directions for navigation in our solar system.
Try to design a better star distribution in a way that navigation is easy (assuming you only want to navigate in a central solar system).
Note that the Galaxy Building Project has limited budget so you should use as few stars as possible.
You may use 1000 stars at most, with magnitude in the range [0,10]. Prepare a star catalog in the same format as in the previous task (ID should be an integer in [1,1000]).
Once you submitted a star catalog, shortly you will get 10 images taken in your newly designed galaxy.
To complete this task successfully you have to send back the orientation for each image similarly to the previous task, but with a short timelimit.
You have to submit your solutions to the Galaxy designer task to a special submission server that uses a binary protocol. During a successful submission, using a single TCP connection, you will:
To send a file, you send its length as a 4-byte integer, then the file itself. To receive one, you first read its length as a 4-byte integer, then the file itself. The score is also sent as a 4-byte integer. All integers (so the sent and received lengths, and the received score) are in network byte order (see htonl(), ntohl() or similar).
If there is any error during this procedure (such as a protocol error, or an internal error), the server will just close the connection. If the cause is unclear, please ask an organizer (and tell them the exact time of the submission).
After you send your star catalog, the server will render 10 test images (this may take a bit of time, up to a minute), and send them back to you. After the server starts sending the images, you have 30 seconds to calculate the orientations and send them back as a single file (concatenated in order).
This is a scaled problem. An accepted submission is worth
SCORE = 200 + 800(5 - N/M)/4where N is the number of entries in the star catalog and M is the best submission so far. This means a good submission is worth 200 points, but there is a large bonus if your catalog is short compared to other teams.
For wrong answers the penalty is -5 points.