Discussion idea - giving StarTools stdev data from stack?

[admin]

Ok, I had a play with your latest data. Feeding the (now linear) stdev to the Tracking algorithms shows promise.

image_blink.gif (670.48 KiB) Viewed 13068 times

The above image is deconvolved in both instances (same parameters). No further noise reduction was applied (which would make things look *really* nice!).

WIth the stddev data added to the Tracking algorithm, noise is reduced across the board - particularly in places where read noise is most prevalent. More detail is made available in both instances by deconvolution, but with the stdev-tracked data the added detail is less noisy/jagged. I'm pretty confident I can get better results using the stddev data than shown here though - this is just a quick and dirty evaluation.

Now the big question... There is a lot more experimenting I could do with this (and I suspect I could eke far better results out of this than displayed so far), but the trouble is that this data is hard to come by as not a single stacker produces this data (except yours!). So... Fancy writing a stacker?

I'm thinking though that for deep sky images, phase correlation might not always be the most suited algorithm and star detection/triangle matching would be a better solution (it's what PI and DSS use afaik).

What do you reckon?

[khyperia]

Fancy writing a stacker?

I'm thinking though that for deep sky images, phase correlation might not always be the most suited algorithm and star detection/triangle matching would be a better solution (it's what PI and DSS use afaik).

What do you reckon?

That looks stunningly awesome!

I definitely agree that star detection/triangle matching would be better than phase correlation for alignment. The reason I'm doing phase correlation right now is because it's incredibly easy to implement.

Now, I do have a question:

Because it looks like I'm actually going to release this sometime, what language/libraries do you think would be best suited for portability? (it needs a rewrite anyway if I'm going to flip from phase correlation to star detection, as that's the majority of the program) - perhaps, what is ST written in, and what libraries are you using? (if you want to disclose that)

[admin]

I definitely agree that star detection/triangle matching would be better than phase correlation for alignment. The reason I'm doing phase correlation right now is because it's incredibly easy to implement.

Phase correlation is actually still very useful for planetary stuff (where there can be absolutely no confusion as to what needs to be correlated - it's that bright disk thingy )

Because it looks like I'm actually going to release this sometime

, what language/libraries do you think would be best suited for portability? (it needs a rewrite anyway if I'm going to flip from phase correlation to star detection, as that's the majority of the program) - perhaps, what is ST written in, and what libraries are you using? (if you want to disclose that)

For *absolute* portability and *absolute* performance, good old C is where it's at. This is what StarTools is written in and is also the reason why it runs on, for example, Android without any problems.
I'm actually not using any libraries (every little thing is written from scratch - to me, the only way to truly understand things to the core and, maybe, improve on them), except the code for LZ4 and NanoJPEG. That's probably not the route most people would take, but I would still very much recommend C (or perhaps C++) for the bulk of the work. There are plenty of frameworks (e.g. Qt) for a cross-platform UI, or you could build your own and use SDL 2.0 (sticking to the latter would even allow you to run your code in the browser through something like Emscripten). This stuff is very CPU intensive and being as close to the metal as you can get is quite important.

I should also add that I'm happy to help by detailing any algorithms found in StarTools that you might need for this.

[Amaranthus]

Wow, that result is impressive!

A stacker incorporated into ST would really make it a one-stop-shop for me... Just sayin'

[Cheman]

While I don't understand the technical part of this discussion, It sounds like the possible end result would be,,,,,,AWESOME
Che

[khyperia]

Some updates from my stacker:

I tried writing it in C++, and it's just not going so hot. It's a lot more difficult for me to write correct, fast code in it - I've found that python/scipy is actually faster than my C++ implementation, because they have spent years optimizing and getting the algorithms just right, whereas my C++ one is not so great. In any case, runtime is a 10-20 seconds for a 10 1000x1000 images, so it's not too big of a deal, since it's an all-automated process that you can start then tab away and do something else.

I did some experimenting with phase correlation, though... I got it working pretty robustly, although all I've tested is my data.

Basically, I run a preprocessing filter over it, and then run it through FFT/etc. The preprocessing filter extracts the brightish stars and zeroes everything else out. Then, because everything is zeroed out, a misalignment (matching wrong star pairs) is very unlikely to happen. Even if two stars happen to line up, all the other stars will be paired with zeroes and will multiply to zero, causing that result to be near-zero. Only the correct alignment, where all stars are paired with each other and not zeroes, will the result have a high value (and therefore easily findable).

This magical "preprocessing filter" has some issues, though. What I'm doing right now is doing this psudocode:
starImage = image - percentile_filter(image, 10%, 10px)
zeroIdx = starImage < max(starImage) / 32
image[zeroIdx] = 0
Essentially, the percentile filter does a crude "background extraction" that is sort of like "wipe" in ST, making the floor be zero on a very localized basis (but allowing major local anomalies like stars to survive). The divide by 32 is sort of like deep sky stacker's "star threshhold" variable, I'm looking for a way to make that dynamic without requiring user input (as the optimal value varies depending on the SNR of the image).
Then I take
image = log(image + 1)
to normalize stars to give them sort of equal weight, so the brightest star doesn't dominate the alignment.

The issues with that, though, is that percentile_filter is slow (on the order of 0.25 - 0.5 seconds for a 1000x1000 image), and the "32" constant that I'd rather just be automatic, and finally the fact that I don't think it's particularly robust - it gives good results for my data, but I'm not sure about others.

So I was going to take you up on your offer and ask you how either the ST auto-star-mask works, or the wipe module

Edit: Actually... Taking the FFT, zeroing out the corners in a 5px box, doing IFFT, then thresholding with (image < mean(image) * 8) works pretty well. There's still a nasty constant there that I really don't like, but removing low-frequency data via FFT is a lot more... analytical-y than a percentile filter (and I like analytical mathy stuff), as well as more resilient to fat stars that might be bigger than the filter size.

Double edit: I just went through the pains of implementing a star finder, and just using "closest point" for the matching algorithm (so it can't drift that much - but my test data is very well tracked, so I just shoved that 'till later), and it looks like it's much, much more accurate than FFT, simply because I'm fitting 100 gaussians and averaging, not just one. Looks like I've convinced myself it's better, haha - now time to implement triangle similarity matching. I'll be gone tonight and tomorrow (US time), so I'll probably have a release for you to use in two days or so.

Speaking of, what OS are you on? I can prebuild the python into a (rather large) binary, but it's platform-specific executables, obviously.

[admin]

You're a machine!

Speaking of, what OS are you on? I can prebuild the python into a (rather large) binary, but it's platform-specific executables, obviously.

Linux Mint 14 / x86_64

[khyperia]

Okay, my stacker *nearly* ready for release, here's the to-do list for registration:

Locate general positions of stars: Completed, via FFT -> kill low-frequency data -> IFFT -> threshhold
Locate exact positions of stars: Completed, via fitting a 2d gaussian via calculating moments then doing a least-squares optimization routine to perfect the fit.
Match star pairs between reference and processing image: TODO
Find an exact translation/rotation/scaling: Completed, via some surprisingly simple matrix math (the matrix math has the assumption that all star points are paired exactly with their corresponding star in the other image).

So, my only step left is the star pair matching. I've thought of a hundred different possible algorithms for this, and I'm not sure what to use. Triangle similarity seems like my best option right now, but it seems very hackish and error-prone.

I have a feeling that linear algebra has a solution, but as I've only taken a semester on the subject, I don't have the knowledge necessary to find the answer

Here's my matrix logic for the last step, to possibly get an idea going for a better idea. It's based off of this - http://en.wikipedia.org/wiki/Transforma ... formations - specifically, the following:

Code: Select all

[rx1,rx2,rx3,rx4,   [cos(theta), sin(theta), sx,   [x1,x2,x3,x4,
 ry1,ry2,ry3,rx4, = -sin(theta), cos(theta), sy, *  y1,y2,y3,y4,
   1,  1,  1,  1]    0         , 0         , 1]     1, 1, 1, 1]

where the left matrix is star positions of the reference matrix, the right matrix is the star positions of the target image, and the middle matrix is the linear transformation to match them to each other. Let's call these Reference, Transform, and Target. We then have

Code: Select all

Reference = Transform * Target

Doing some matrix rearranging and we have

Code: Select all

Reference * pinv(Target) = Transform

so just calculate the left hand side and poof! We have our transformation matrix! I just take the top left 2x2 corner as a parameter to scipy's image affine transformation function, and the right column first two elements as the offset, discarding the bottom row (in practice, it's very very close to 0,0,1, something like 10^-15 for the zeroes and 1 for the 1, which agrees with our theoretical transform)

Of course, there's one issue. rx1&ry1 and x1&y1 need to be the same star, same for 2, etc. So basically, the two matrices need to be shuffled and elements discarded to make them match up. The overall match order doesn't matter, however, as long as each star is correctly corresponding. I have no idea how to do this in a robust way - but I think that something to do with least squares (and matricies) has got to be the solution somehow

[admin]

Man... That's some impressive progress...
You've grasped the mathematics involved very quickly.

The big issue is performance when matching the stars as there are many, many combinations possible.
The best idea I've come up with is to create a subset of the stars detected, based on two criteria;

• a measure of accuracy for the star detection (e.g. how certain are we that this is a star, not some other feature, not noise)
• closest distance to a point in a list of points generated by, for example, Bridson’s algorithm for Poisson-disc sampling.

Based on a score that factors in both criteria, we only evaluate the top n candidates.

The first criterion makes sure that the thing we're evaluating is truly a star. This criterion can be enhanced by, for example, giving priority to 'fat' stars.
The second criterion makes sure that, where possible, we evaluate stars across the whole reference image evenly, so that all pixels in an area have been 'roughly' considered.

The same list of points generated by the Poission disc sampling could generate a triangle mesh, where each point is associated with the closest (in distance) star for which a transformation was computed. Once all points in the mesh have a transformation associated with them, we can do a simple affine 'texturemapping' transformation of the whole triangle mesh. There's potential for GPU acceleration here as well.

This is what I would do, and I have no idea what others do or if this would even work...

[Amaranthus]

I think I read that DSS uses n = 8 for its stacking algorithm.