On Fast Matched Filter for Streak Detection and Ranking

Background
The matched filter is an exceedingly popular method in many fields. Its properties are well known, and it is widely used. In optical astronomy, the common application includes matching streak templates of various lengths and orientations (shape hypotheses). Traditionally, most attention is given to reducing the shape hypotheses' size, while little attention was given to the possible speeding up of filtering itself. We present a matched filter modification suitable for shorter streaks (less than ca. 100 [px]) faster than current state-of-the-art approaches. A logistic regression model validates an image sequence of streaks.

Method
We have developed a method based on steerable filters. An input image is represented by responses to K spherical quadrature filters (SQF). This representation allows computing response to streak filters of arbitrary orientation linearly w.r.t. K. This representation allows dynamic computation of length hypothesis without impacting the time complexity. Overall, if the number of pixels is N, the number of angular hypotheses is A, and the number of length hypotheses is L, then the complexity is O(NKA), where K is a function of (1) PSF, and (2) maximal desired length of the matched streaks (we show that K and maximal desired length are similar in value). Compared to standard spatial complexity O(NMAL), where M is the number of pixels in the template (M >> K), our method is always superior. Frequency-domain complexity is O(Nlog(N)AL), and our method is better by the log(N) factor. The preprocessing time of our method is O(NK). The memory requirements for SQF representation are O(NK). We propose streak detection and validation based on this representation. We used real background images with synthetic streaks (semi-synthetic data).

Experiment
We constructed a series of numeric experiments to show comparative advantages. We compared our method with the spatial domain convolution (used for short streaks), and frequency-domain convolution (used for long streaks). We use a large synthetic dataset (> 10000) and real data (~1000) for our experiments. Simulated streaks have length 2-100 [px], while K ≅ 2-50. The validation is tested on a manually annotated dataset of real streaks. We tested all three filtering approaches for the purpose of validation.

Results
We have shown that our method is superior to spatial domain convolution (more than 100 folds) and frequency-domain convolution (approximately 30 folds). Furthermore, we show that the choice of the method (SQF, spatial/frequency-domain convolution) has no influence on the precision/recall for the real dataset.

Conclusion
The presented method has a favorable trade-off between memory and speed. Results are directly applicable to a wide class of methods that rely on the convolution of short/medium steerable streaks. Furthermore, the SQF representation is suitable for a subpixel accuracy search and offers access to additional information beyond the ridge response.