  Identification of linear features (streaks) in astronomical images is
important for several reasons, including: detecting fast-moving near-Earth
asteroids; detecting or flagging faint satellites streaks; and flagging or
removing diffraction spikes, pixel bleeding, line-like cosmic rays and
bad-pixel features. Here we discuss an efficient and optimal algorithm for the
detection of such streaks. The optimal method to detect streaks in astronomical
images is by cross-correlating the image with a template of a line broadened by
the point spread function of the system. To do so efficiently, the
cross-correlation of the streak position and angle is performed using the Radon
transform, which is the integral of pixel values along all possible lines
through an image. A fast version of the Radon transform exists, which we here
extend to efficiently detect arbitrarily short lines. While the brute force
Radon transform requires an order of N^3 operations for an N by N image, the
fast Radon transform has a complexity of the order of N^2 log(N). We apply this
method to simulated images, recovering the theoretical signal-to-noise ratio,
and to real images, finding long streaks of low-Earth-orbit satellites and
shorter streaks of Global Positioning System satellites. We detect streaks that
are barely visible to the eye, out of hundreds of images, without a-priori
knowledge of the streaks' positions or angles. We provide implementation of
this algorithm in Python and MATLAB.
