GNU Astronomy Utilities - Tasks: task #15713, Make quad structure with hashes...
You are not allowed to post comments on this tracker with your current authentication level.
task #15713: Make quad structure with hashes and store in kd-tree
Submitter: | Sachin Kumar Singh <sks_15> | ||
Submitted: | Tue 30 Jun 2020 10:10:28 PM UTC | ||
Should Start On: | Tue 30 Jun 2020 12:00:00 AM UTC | Should be Finished on: | Tue 30 Jun 2020 12:00:00 AM UTC |
Category: | New program | Priority: | 5 - Normal |
Item Group: | New feature | Status: | Done |
Privacy: | Public | Assigned to: | sks_15 |
Percent Complete: | 0% | Open/Closed: | Closed |
Effort: | 0.00 |
Jump to the original submission
Mon 10 Aug 2020 10:32:55 PM UTC, comment #30: |
Sachin Kumar Singh <sks_15> |
Sat 01 Aug 2020 02:18:00 AM UTC, comment #29: Great! I look forward to the next steps (correct me if I am wrong):
|
Mohammad Akhlaghi <makhlaghi> |
Sat 01 Aug 2020 12:21:29 AM UTC, comment #28: The function to find the farthest stars and assigning them as A and B is done and pushed on gitlab. Also, the result seems much better than before.
|
Sachin Kumar Singh <sks_15> |
Thu 30 Jul 2020 12:09:49 PM UTC, comment #27: This is great! Nice work ;-)!
|
Mohammad Akhlaghi <makhlaghi> |
Thu 30 Jul 2020 11:39:28 AM UTC, comment #26: After using the 0.5 and 0.75 quartiles for the stars C and D, the result seems much cleaner and shaped like a polygon. Below are the images of all the quads and 2 random quads from them.
|
Sachin Kumar Singh <sks_15> |
Wed 29 Jul 2020 05:57:00 PM UTC, comment #25: I change the dimension to 10 and also included sorting in the region file making function.
|
Sachin Kumar Singh <sks_15> |
Wed 29 Jul 2020 12:38:01 AM UTC, comment #24: Indeed, its great that the polygons are now distributed over the full field :-D.
|
Mohammad Akhlaghi <makhlaghi> |
Wed 29 Jul 2020 12:06:59 AM UTC, comment #23: The function for visualizations is done. For the function, I assumed that the array will be sorted, but is it okay or should I explicitly sort the array for every polygon and then display. Which one would be better?
|
Sachin Kumar Singh <sks_15> |
Sat 18 Jul 2020 11:56:01 PM UTC, comment #22: I had a fast look and I am impressed by the comments! Very nice! I really enjoyed reading them to get a good feeling without having to invest a lot of mental energy in understanding the coding. This is how a good code should look like! Good work!
|
Mohammad Akhlaghi <makhlaghi> |
Sat 18 Jul 2020 10:55:35 PM UTC, comment #21: The KD-tree implementation is done and pushed here. You can see the main function to get a feel of how it works(a little test). Links to all the resources are included to get a better idea of the procedures involved.
|
Sachin Kumar Singh <sks_15> |
Sat 18 Jul 2020 12:36:25 AM UTC, comment #20: Thanks for a nice review of the problem Sachin.
|
Mohammad Akhlaghi <makhlaghi> |
Fri 17 Jul 2020 11:56:31 PM UTC, comment #19: For the kd-tree, I have a bit dilemma on choosing the type of implementation. In one implementation(as given in its Wikipedia) it uses median to build the tree. But in another, it is also possible to build a tree without median(using only the axis to determine the next child). Also, it is mentioned in its Wikipedia page that,
|
Sachin Kumar Singh <sks_15> |
Thu 16 Jul 2020 07:19:41 PM UTC, comment #18: Thanks for defining bug #58773.
|
Mohammad Akhlaghi <makhlaghi> |
Thu 16 Jul 2020 07:02:07 PM UTC, comment #17: Ok, will do that:-)
|
Sachin Kumar Singh <sks_15> |
Thu 16 Jul 2020 06:45:11 PM UTC, comment #16: Good progress Sachin!
|
Mohammad Akhlaghi <makhlaghi> |
Thu 16 Jul 2020 06:28:56 PM UTC, comment #15: The final formation of hash codes is done along with the major implementation of kd-tree. For implementation, I'll be using similar implementation as done in this Wikipedia of kd-tree.
|
Sachin Kumar Singh <sks_15> |
Wed 15 Jul 2020 11:08:24 AM UTC, comment #14: Great, I am happy to see the progress ;-)!
|
Mohammad Akhlaghi <makhlaghi> |
Wed 15 Jul 2020 12:53:52 AM UTC, comment #13: The code is pushed here. I removed the unwanted function and struct and have used indexes for all-purpose as discussed.
|
Sachin Kumar Singh <sks_15> |
Tue 14 Jul 2020 03:33:18 PM UTC, comment #12: Thanks, Raul. This will certainly give users flexibility. I'll try to implement it alongside.
|
Sachin Kumar Singh <sks_15> |
Tue 14 Jul 2020 06:54:44 AM UTC, comment #11: Really good job Sachin. Yesterday I was talking with Mohammad and it just come to my mind that in Astrometry you are able to choose the number of objects to be considered as a quad. I thought it was in the solving step, but I was wrong. It is actually in the step of creating the catalogue indexes (with the program `build-astrometry-index'. Anyway, I just wanted to let you know this to make the code more general from the beginning. It may be useful to have this possibility in the future. You can have a look at this webpage: http://astrometry.net/doc/build-index.html
|
Raul Infante-Sainz <infantesainz> |
Sat 11 Jul 2020 02:58:24 PM UTC, comment #10: The quads were made by firstly doing a search for all points and calculating the distance from every other point and filtering out those which were less than the helpix resolution(theta-pix as given in the documentation). It took an O(n^2) time and O(n) space complexity.
|
Sachin Kumar Singh <sks_15> |
Sat 11 Jul 2020 12:42:04 AM UTC, comment #9: Great! No problem, paperwork is always the most important thing ;-).
|
Mohammad Akhlaghi <makhlaghi> |
Sat 11 Jul 2020 12:28:32 AM UTC, comment #8: Sorry, it took so to reply back. Some college work came up and had to finish it first. But the good thing is, the task is (hopefully) done and pushed here. All the requirements are satisfied. There is still room of improvement to improve time complexity fo k nearest neighbours searches by using heaps to make it logarithmic, but that would complicate it further in the very initial stage and hence is marked for later.
|
Sachin Kumar Singh <sks_15> |
Mon 06 Jul 2020 08:05:14 PM UTC, comment #7: Perfect ;-)!
|
Mohammad Akhlaghi <makhlaghi> |
Mon 06 Jul 2020 06:11:59 PM UTC, comment #6: The resolution part is where I had a doubt about. In astrometry.net, they have written in their paper that:
|
Sachin Kumar Singh <sks_15> |
Mon 06 Jul 2020 05:46:12 PM UTC, comment #5: There is another major problem with selecting the three nearest points:
|
Mohammad Akhlaghi <makhlaghi> |
Mon 06 Jul 2020 05:25:04 PM UTC, comment #4: Very good! But just one thing: probably using the 3 nearest neighbors isn't too good (there will be too many repetitions and thus too few quads for the fit).
|
Mohammad Akhlaghi <makhlaghi> |
Mon 06 Jul 2020 03:47:55 PM UTC, comment #3: Thanks for the review:-) I'll make all changes accordingly.
|
Sachin Kumar Singh <sks_15> |
Sun 05 Jul 2020 07:42:30 PM UTC, comment #2: I enjoyed looking through the blog, nice work!
|
Mohammad Akhlaghi <makhlaghi> |
Sun 05 Jul 2020 06:52:03 PM UTC, comment #1: Summarised the task in this blog. Please point any error in methods or otherwise. |
Sachin Kumar Singh <sks_15> |
Tue 30 Jun 2020 10:10:28 PM UTC, original submission:
After the completion of task #15700, we now have a HEALPix map of the catalogue with the brightest objects in each map. Next step is the implementation of the quad structure that will take many permutations of these objects and make a unique hash of all these to be stored and later on compared with the query images and make relative matches.
|
Sachin Kumar Singh <sks_15> |
Depends on the following items: None found
Items that depend on this one: None found
There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.
Follow 19 latest changes.
Date | Changed by | Updated Field | Previous Value | => | Replaced by |
---|---|---|---|---|---|
2020-08-10 | sks_15 | Status | In Progress | Done | |
Open/Closed | Open | Closed | |||
2020-08-01 | makhlaghi | Summary | Make quad structure to make unique hashes of 4 objects | Make quad structure with hashes and store in kd-tree | |
2020-08-01 | sks_15 | Attached File | - | Added Screenshot@from@2020-08-01@05-41-55.png, #49593 | |
2020-07-30 | sks_15 | Attached File | - | Added Screenshot@from@2020-07-30@17-05-56.png, #49581 | |
Attached File | - | Added Screenshot@from@2020-07-30@17-06-25.png, #49582 | |||
Attached File | - | Added Screenshot@from@2020-07-30@17-05-32.png, #49583 | |||
2020-07-29 | sks_15 | Attached File | - | Added Screenshot@from@2020-07-29@21-26-28.png, #49575 | |
2020-07-29 | sks_15 | Attached File | - | Added Screenshot@from@2020-07-29@05-27-22.png, #49565 | |
Attached File | - | Added Screenshot@from@2020-07-29@05-26-54.png, #49566 | |||
Attached File | - | Added Screenshot@from@2020-07-29@05-27-03.png, #49567 | |||
Attached File | - | Added polygon.reg, #49568 | |||
2020-07-15 | sks_15 | Attached File | - | Added Screenshot@from@2020-07-15@06-13-05.png, #49485 | |
Attached File | - | Added Screenshot@from@2020-07-15@06-13-19.png, #49486 | |||
Attached File | - | Added Screenshot@from@2020-07-15@06-13-50.png, #49487 | |||
2020-07-11 | sks_15 | Attached File | - | Added polygon.reg, #49469 | |
Attached File | - | Added final-quads.reg, #49470 | |||
2020-07-11 | sks_15 | Attached File | - | Added Screenshot@from@2020-07-11@05-47-05.png, #49460 | |
Attached File | - | Added Screenshot@from@2020-07-11@05-47-37.png, #49461 |
Powered by Savane 3.13-d3ae.
Corresponding source code
The quad structure is done. The final quads(first 5 only) that are calculated for `gaia-in-img.fits` are:
For now only Cx, cy, dx, dy columns will be finally made to be used as the input to be used by the kd-tree. Relative brightness will later be used to choose the quad out the all the possible quad candidates.
You can check all the code here.
With all this done this task can be closed now:-)