Algorithms

RX Spectral Detection Algorithm

Description

This algorithm uses the color of each pixel to find areas of interest in an image. It takes an average color value across the image and compares this value to every pixel’s color value. The algorithm highlights pixels with color values that are significantly different from the average color value of the image. These pixels are considered to be anomalous and they usually indicate areas of debris or signs of a missing person.

 

Research Paper

The implementation of the RX Spectral Detection Algorithm used in this program was based off of the following research paper:

• Spectral Anomaly Detection with Machine Learning for Wilderness Search and Rescue
  • Authors: Julia Proft, Jesus Suarez, and Robin Murphy

 

Algoritm Parameters

These are the parameters that have the most influence on the analysis results and are available for the user to change.

• RxThreshold — Default: 90
  • This is the threshold value a single pixel must meet in order to flag the entire image as containing a feature of interest. 
  • A lower value will result in more images being flagged.
  • Increase this value to make it harder for images to be flagged as containing a feature of interest.
  • The lowest accepted value is 0.
  • The default was chosen to minimize the number of false negatives when flagging images. The default value flags most, if not all, images as containing some level of features of interest.

• RxChiThreshold — Default: 0.999
  • This value determines the percentage of pixels filtered out as background noise.
  • The default value is 0.999 (99.9%), which means the top 0.1% of pixel values are allowed through.
  • The accepted values range from 0.0 to 1.0.
  • Changing this value does not change whether an image is flagged, It only changes how much detail/noise is allowed in the final heatmap. Decreasing this value will make the heatmap look closer to the original image, but may make finding the features of interest harder.
  • Reducing this value can make it easier to compare the original image and the heatmap image. 
  • The default value was chosen based on the value used in the research paper.

 

Student(s) who implemented the algorithm in the program:

• Travis Stewart

 

 

 

Debris Detection Algorithm

Description

This algorithm uses two different methods to detect debris: an edge detector and a corner detector. The edge detector specifically looks for long and straight lines in the image. These straight lines usually indicate debris, such as downed power lines, branches, or some type of man-made object. The corner detector looks for more general objects by trying to find corners. Objects it detects contain sharp or well defined corners, these usually indicate a pile of debris or man-made objects.

 

Research Paper

The implementation of the Debris Detection Algorithm used in this program was based off of the following research paper:

• Detecting Debris in UAV Imagery of Disasters
  • Authors: Matt Hegarty, Khuoung Nguyen, Robin Murphy

 

Algorithm Parameters

These are the parameters that have the most influence on the analysis results and are available for the user to change.

• LineGaussianIter — Default: 0
  • The kernel standard deviation in both the X and Y directions. If left at 0, these values are calculated by the application and applied automatically. The larger the value, the higher the degree of smoothing when applying a Gaussian Blur on the image. This value should be a positive number. NOTE: this values only applies to the “Line Detection” portion of the algorithm.

• LineDilationIter — Default: 1
  • Dilation is used to add an extra layer of pixels on the edges of lines, making them stand out more. This variable determines the number of iterations that the dilation is applied to the image. The higher the number, the more pronounced edges will be. This value should be an integer greater than 0. Also, the higher the number, the longer the application will take to process images. NOTE: this values only applies to the “Line Detection” portion of the algorithm.

• LineBilatBlurColor — Default: 75
  • This value filters sigma in the color space. A larger value means that farther colors within the pixel neighborhood (determined by LineBilatBlurSpace) will be mixed together, resulting in larger areas of semi-requal color. The higher the number, the more differing colors are grouped when applying a bilateral filter.
  • For simplicity, this value should be the same as LineBilatBlurSpace. If both these values are small ( < 10), then the filter will not have much effect. On the other side, if they are large ( > 150), the filter will be strong resulting in an image that is cartoonish and thus, edge detection will suffer. Recommended range of values is [25, 125]. NOTE: this values only applies to the “Line Detection” portion of the algorithm.

• LineBilatBlurSpace — Default: 75
  • This value filters sigma in the coordinate space. A larger value means that further pixels will influence each other as long as their colors are close enough (determined by LineBilatBlurColor).  
  • For simplicity, this value should be the same as LineBilatBlurColor. If both these values are small ( < 10), then the filter will not have much effect. On the other side, if they are large ( > 150), the filter will be strong resulting in an image that is cartoonish and thus, edge detection will suffer. Recommended range of values is [25, 125]. NOTE: this values only applies to the “Line Detection” portion of the algorithm.

• LineCannyEdgeLowerBound — Default: 100
  • The first threshold for the hysteresis procedure of the Canny algorithm to find edges. This is the lower threshold. 
  • If a pixel gradient that is detected is lower than this value, it is rejected. If the pixel gradient is in between LineCannyEdgeLowerBound and LineCannyEdgeThreshold, it is only accepted if it is connected to pixels above the upper threshold, LineCannyEdgeThreshold. If a pixel gradient is above the upper threshold, it is accepted as an edge.
  • The smallest value between LineCannyEdgeLowerBound and LineCannyEdgeThreshold is used for edge linking. The largest value is used to find initial segments of strong edges.
  • An upper:lower ratio between 2:1 and 3:1 is recommended.

• LineCannyEdgeThreshold — Default: 140
  • The second threshold for the hysteresis procedure of the Canny algorithm to find edges. This is the upper threshold.
  • If a pixel gradient that is detected is lower than this value, it is rejected. If the pixel gradient is in between LineCannyEdgeLowerBound and LineCannyEdgeThreshold, it is only accepted if it is connected to pixels above the upper threshold, LineCannyEdgeThreshold. If a pixel gradient is above the upper threshold, it is accepted as an edge.
  • The smallest value between LineCannyEdgeLowerBound and LineCannyEdgeThreshold is used for edge linking. The largest value is used to find initial segments of strong edges.
  • A upper:lower ratio between 2:1 and 3:1 is recommended.

• CornerGaussianIter — Default: 0
  • This is the same as LineGaussianIter but for the corner detection portion of the application.

• CornerErosionIter — Default: 1
  • Erosion strips the outermost layer of pixels in a structure, making corners more prominent. This variable determines the number of times that the erosion is applied to the image before processing. The higher the number, the more pronounced corners will be. This value should be an integer greater than 0. Also, the higher the number, the longer the application will take to process images. NOTE: this value only applies to the “Corner Detection” portion of the algorithm.

• CornerBilateralColor — Default: 200
  • This is the same as LineBilatBlurColor but for the corner detection portion of the application.

• CornerBilateralSpace — Default: 500
  • This is the same as LineBilatBlurSpace but for the corner detection portion of the application.

• CornerMaxDistance — Default: 75
  • This parameter determines how far the algorithm looks pixel-wise for other corners detected to connect to. 
  • The lower the number, the less corners will be connected because of their proximity to one another, leading to less features of interest being returned. A value too low will be useless, as corners with correlation will not be connected because they don’t meet the distance required.
  • The higher the number, the more corners will be connected because of their proximity to one another, leading to more features of interest being returned. A value too high will be useless, as corners that have no correlation will be connected due to a high pixel distance checked by the algorithm. 
  • A recommended value is between [25, 100].

• CornerNumPoints — Default: 3
  • This value determines the number of corners that a connected polygon needs to count as a feature of interest.
  • A polygon is formed from the connection of corners that are near each other distance-wise, as determined by the value of CornerMaxDistance.
  • Only polygons that have a minimum of CornerNumPoints connected will be returned as a feature. 
  • The lower the value, the more junk is returned because of a low threshold.
  • The higher the value, the less features of interest will be returned because of the high threshold.

 

Student(s) who implemented the algorithm in the program:

• Tony Huynh
• Seth Burchell