Topics
features
Publications
Issue Archive
Algorithm for Detecting a Bright Spot in an Image
 Created on Saturday, 01 August 2009
Corrections for background intensity and dark current are included.
An algorithm processes the pixel intensities of a digitized image to detect and locate a circular bright spot, the approximate size of which is known in advance. The algorithm is used to find images of the Sun in cameras aboard the Mars Exploration Rovers. (The images are used in estimating orientations of the Rovers relative to the direction to the Sun.) The algorithm can also be adapted to tracking of circular shaped bright targets in other diverse applications.
The first step in the algorithm is to calculate a darkcurrent ramp — a correction necessitated by the scheme that governs the readout of pixel charges in the chargecoupleddevice camera in the original Mars Exploration Rover application. In this scheme, the fraction of each frame period during which dark current is accumulated in a given pixel (and, hence, the darkcurrent contribution to the pixel imageintensity reading) is proportional to the pixel row number. For the purpose of the algorithm, the darkcurrent contribution to the intensity reading from each pixel is assumed to equal the average of intensity readings from all pixels in the same row, and the factor of proportionality is estimated on the basis of this assumption. Then the product of the row number and the factor of proportionality is subtracted from the reading from each pixel to obtain a darkcurrentcorrected intensity reading.
The next step in the algorithm is to determine the best location, within the overall image, for a window of N × N pixels (where N is an odd number) large enough to contain the bright spot of interest plus a small margin. (In the original application, the overall image contains 1,024 by 1,024 pixels, the image of the Sun is about 22 pixels in diameter, and N is chosen to be 29.)
The window is placed at a given position within the overall image. A weighted average of the intensities of the 4N – 4 outer pixels of the window is taken as an estimate of background intensity and subtracted from a weighted average of the intensities of the remaining inner (N – 2) × (N – 2) pixels of the window to obtain a backgroundcorrected weighted sum of pixel intensities for the window. The weighted averages are simply pixelintensity averages multiplied by common denominators so as to obviate floatingpoint arithmetic operations and thereby accelerate computations. The window is then moved to an adjacent column position, and weighted averages for the new position are calculated from the previous weighted averages by adding the appropriate values for the new outer and inner pixels and subtracting the corresponding values for the pixels that have been left behind or changed in status between the inner and the outer. This process is repeated until the computations have been performed for all possible window positions. The position that yields the highest backgroundcorrected weighted sum of pixel intensities is assumed to contain the bright spot of interest (the image of the Sun in the original application), and the window is then used to locate the bright spot more precisely as described next.
Within the inner (N – 2) × (N – 2) portion of the window, the position of the bright spot is determined by means of a simple centroid calculation, using the backgroundcorrected pixel intensities. Because the window position selected as described above may not necessarily be the optimum one, the centroid calculation is performed twice in an iterative process: For the second centroid calculation, the window is recentered on the centroid determined by the first centroid calculation.
This work was done by Carl Christian Liebe of Caltech for NASA’s Jet Propulsion Laboratory.
The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 3952322. Refer to NPO41801.
White Papers

