Search Algorithm and Search Space#
The KBMOD algorithm algorithm performs shift and stack using a grid of potential trajectories. The granularity of this grid is critical to trading off completeness and computational cost. If the grid is too fine, the algorithm will spend a lot of time checking similar trajectories. If the grid is too coarse, the algorithm might miss true objects. Below we discuss the sampling method in more detail.
Search Overview#
KBMOD operates by considering a candidate set of velocities and computing the likelihood of an object for the cross product of each velocity and each starting pixel. This can be viewed as a pair of nested loops (although it is implemented in a parallelized GPU search):
For each starting pixel:
For each velocity in the grid:
Compute the likelihood of this trajectory
Thus the code checks all of the velocities starting starting out of each pixel.
Due to memory limitations, only a set number of trajectories are kept for each starting pixel (configured by the results_per_pixel
configuration parameter with a default of 8). At the end of the search the code will return num_pixels * results_per_pixel
results ranked by their likelihood.
Starting Pixels#
By default KBMOD will attempt to shift and stack using each pixel in the initial image as a potential starting location. If we run KBMOD on an image with width w
and height h
, we get w * h
possible starting locations: all x values [0, w
) crossed with all y values [0, h
). See Data Model for more information on how the images are stored.
KBMOD provides the ability to expand or contract the range of starting pixels using two different methods:
Adding a fixed sized buffer around the edge of the images. This is done using the
x_pixel_buffer
andy_pixel_buffer
parameters to set separate buffers for the x and y dimensions. Ifx_pixel_buffer = 5
the code will add 5 pixels to both sides of the image, using starting pixels from [-5,w
+ 5).Specifying absolute pixel boundaries. This is done using the
x_pixel_bounds
andy_pixel_bounds
parameters. For example you can reduce the size of the search by usingx_pixel_bounds = [10, 100]
, which will search [10, 100) regardless of the image’s width.
Similarly, you can increase the region of the search by setting the bounds outside the image’s area.
Changing the range of starting pixels will also impact the number of results returned. As described above, KBMOD’s core search returns results_per_pixel
results for each starting pixel. Thus we can use a combination of starting pixel bounds and the results_per_pixel
configuration parameter to control the depth of results at each starting pixel. For example, if narrowing in on a particular candidate trajectory, we might choose a very small area of starting pixels but a large number of results per pixel.
Choosing Velocities#
Perhaps the most complex aspect of the KBMOD algorithm is how it defines the grid of search velocities. KBMOD always searches linear trajectories defined by two velocity components: vx
is the velocities along the x dimension and vy
is the velocity along the y dimension. Both velocities are specified in pixels per day.
KBMOD allows you to define custom search strategies to best match the data. These include:
SingleVelocitySearch
- A single predefined x and y velocity.VelocityGridSearch
- An evenly spaced grid of x and y velocities.PencilSearch
- A search in a small cone around a given velocity.EclipticCenteredSearch
- An evenly spaced grid of velocity magnitudes and angles (using a current parameterization) centered on a given or computed ecliptic angle.KBMODV1SearchConfig
- An evenly spaced grid of velocity magnitudes and angles (using the legacy parameterization).RandomVelocitySearch
- Randomly sampled x and y velocities
Additional search strategies can be defined by overriding the TrajectoryGenerator
class in trajectory_generator.py.
The search is selected and configured by a single generator_config
parameter that takes a dictionary. The dictionary must contain a name
entry that matches one of the options above. For example to search a single trajectory with a given vx = 1.0
and vy = -2.0
, we would use:
generator_config = { "name": "SingleVelocitySearch", "vx": 1.0, "vy": -2.0 }
If no generator_config is provided, then KBMOD uses the KBMODV1SearchConfig
search strategy and pulls the configuration parameters from the top level.
Note that all search strategies only define the set of trajectories search from each starting pixel. To further limit the search space, the user can combine these trajectories with the starting pixel bounds parameters, such as x_pixel_bounds
and y_pixel_bounds
described above.
SingleVelocitySearch#
As the name implies the SingleVelocitySearch
generator tests a single trajectory (with given vx
and vy
) per starting pixel.
Parameter |
Interpretation |
|
The velocity in pixels per day in the x-dimension |
|
The velocity in pixels per day in the y-dimension |
VelocityGridSearch#
The VelocityGridSearch
generator searches a uniform grid of x and y velocities.
Parameter |
Interpretation |
|
The number of velocity steps in the x-dimension. |
|
The minimum velocity in the x-dimension (pixels per day). |
|
The maximum velocity in the x-dimension (pixels per day). |
|
The number of velocity steps in the y-dimension. |
|
The minimum velocity in the y-dimension (pixels per day). |
|
The maximum velocity in the y-dimension (pixels per day). |
PencilSearch#
The PencilSearch
generator explores a cone around a given velocity, which allows it to refine the results for a given candidate or to search for a known (but approximate) object. The angles and velocity magnitudes are specified relative to a given center velocity.
Parameter |
Interpretation |
|
The center velocity in pixels per day in the x-dimension |
|
The center velocity in pixels per day in the y-dimension |
|
The maximum offset of a candidate trajectory from the center (in radians). Default: 0.2618 |
|
The step size to explore for each angle (in radians). Default: 0.035 |
|
The maximum offset of the velocity’s magnitude from the center (in pixels per day). Default: 10.0 |
|
The step size to explore for each velocity magnitude (in pixels per day). Default: 0.5 |
This search is most efficient when used in combination with spatial bounds parameters, such as x_pixel_bounds
and y_pixel_bounds
described above.
EclipticCenteredSearch#
The EclipticCenteredSearch
generator defines velocities using a grid of two parameters: a sampling of absolute velocities in pixels per day and a sampling of the velocities’ angles in degrees or radians. Each sampling consists of values defining the range and number of sampling steps.
Given the linear sampling for both velocities and angles, the full set of candidate trajectories is computed as:
for (int a = 0; a < angleSteps; ++a) {
for (int v = 0; v < velocitySteps; ++v) {
searchList[a * velocitySteps + v].xVel = cos(sampled_angles[a]) * sampled_velocities[v];
searchList[a * velocitySteps + v].yVel = sin(sampled_angles[a]) * sampled_velocities[v];
}
}
where sampled_angles
contains the list of angles to test and sampled_velocities
contains the list of velocities.
The list of velocities is created from the given bounds list velocities=[min_vel, max_vel, vel_steps]
. The range is inclusive of both bounds.
Each angle in the list is computed as an offset from the ecliptic angle. KBMOD uses the following ordering for extracting the ecliptic:
If
given_ecliptic
is provided (is notNone
) in the generator’s configuration that value is used directly.If the first image has a WCS, the ecliptic is estimated from that WCS.
A default ecliptic of 0.0 is used.
The angles used are defined from the list angles=[min_offset, max_offset, angle_steps]
and will span [ecliptic + min_offset, ecliptic + max_offset]
inclusive of both bounds. Angles can be specified in degrees or radians (as noted by the angle_units
parameter) but must be consistent among all angles.
Parameter |
Interpretation |
|
A length 3 list with the minimum angle offset,
the maximum offset, and the number of angles to
to search through (angles specified in units given
by |
|
The units to use for angles, such as “rad” or “deg”. |
|
The given value of the ecliptic angle (specified in
units given by |
|
A length 3 list with the minimum velocity (in pixels per day), the maximum velocity (in pixels per day), and number of velocities to test. |
|
The units to use for velocities (e.g. “pix / d”) |
KBMODV1SearchConfig#
The KBMODV1SearchConfig
generator defines velocities using a grid of two parameters: a sampling of absolute velocities (v_arr
) in pixels per day and a sampling of the velocities’ angles (ang_arr
) in radians. Each sampling consists of values defining the range and number of sampling steps.
The velocity array v_arr
uses the format [minimum velocity, maximum velocity, number of steps]. The setting v_arr = [92.0, 526.0, 256]
samples velocities from 92 pixels per day to 526 pixels per day with 256 equally spaced samples.
The complexity of the velocity grid comes from the fact that the angles specified by ang_arr
are not absolute angles in pixel space, but rather offsets from a given suggested angle. The user can specify this suggested angle directly with the parameter average_angle
. If no such parameter is given the code computes a suggested angle based on the ecliptic angle for the images (as defined by their WCS). This allows KBMOD to focus on trajectories around where the most objects are expected to be.
Another important factor is that ang_arr
is defined as [offset for min angle, offset for max_angle, number of steps]. So the settings:
average_angle = 1.0
ang_arr = [0.5, 0.5, 100]
produce a search grid from angle 0.5 (average_angle - ang_arr[0]
) to 1.5 (average_angle + ang_arr[1]
) using 100 steps. Note that the first element of ang_arr
is subtracted from average_angle
to provide the lower bound and the second element is added to average_angle
to provide the upper bound.
Given the linear sampling for both velocities and angles, the full set of candidate trajectories is computed as:
for (int a = 0; a < angleSteps; ++a) {
for (int v = 0; v < velocitySteps; ++v) {
searchList[a * velocitySteps + v].xVel = cos(angles[a]) * velocities[v];
searchList[a * velocitySteps + v].yVel = sin(angles[a]) * velocities[v];
}
}
where angles
contains the list of angles to test and velocities
contains the list of velocities.
Parameter |
Interpretation |
|
A length 3 array with the minimum, maximum and number of angles to search through (in radians) |
|
Overrides the ecliptic angle calculation and instead centers the average search around average_angle (in radians). |
|
A length 3 array with the minimum, maximum and number of velocities. to search through. The minimum and maximum velocities are specified in pixels per day. |
KBMODV1Search#
The KBMODV1Search
generator provides an alternate (more understandable) parameterization of the KBMODV1SearchConfig
search above. Specifically, instead of specifying the angle offsets relative to a reference (average_angle
) this parametrization specifies them directly in pixel space.
Parameter |
Interpretation |
|
The number of velocity steps. |
|
The minimum velocity magnitude (in pixels per day). |
|
The maximum velocity magnitude (in pixels per day). |
|
The number of angle steps. |
|
The minimum angle (in radians). |
|
The maximum angle (in radians). |
RandomVelocitySearch#
The RandomVelocitySearch
randomly selects points within a bounding box of velocities.
Parameter |
Interpretation |
|
The minimum velocity magnitude (in pixels per day). |
|
The minimum velocity magnitude (in pixels per day). |
|
The maximum velocity magnitude (in pixels per day). |
|
The maximum velocity magnitude (in pixels per day). |
|
The maximum number of samples to generate. Used to. avoid infinite loops in KBMOD code. |