Difference between revisions of "Validation:Algorithms"

From BoofCV
Jump to navigationJump to search
m
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
= External Validation =
= Validation and Regression =


Correctly implementing algorithms and producing the expected performance is difficult. Academic papers more of then than not leave out important implementation details which are needed to reproduce their results.  Just like with the halting problem in CS, its nearly impossible to formally prove that an algorithm is correctly implemented.
Correctly implementing algorithms and producing the expected performance is difficult. BoofCV contains thousands internal tests to help ensure correctness of its algorithms, but it is nearly impossible to be 100% sure that the implementation is correct.  This is especially true since often academic papers leave out important implementations needed to reproduce their work!.  In the best case scenario an implementation will be compared against the author's original implementation.  This page contains a list of important algorithms inside of BoofCV and if they have been validated against external libraries or not.


BoofCV contains over a thousand internal tests to help ensure correctness of its algorithms, but testing against external sources provides a hard number to compare against.  This page contains a list of important algorithms inside of BoofCV and if they have been validated against external libraries or not.  Just because some code has not been validated does not mean it is incorrect.
Source code used to validate BoofCV can be found at the [https://github.com/lessthanoptimal/ValidationBoof| ValidationBoof project on GitHub].  ValidationBoof also contains regression tests designed to check for changes in stability/performance of different algorithms.  It is entirely possible for all the unit tests to pass and have a 20% drop in performance due to a minor change.  Regression tests are designed to catch those problems.  


{| class="wikitable" border="1"
{| class="wikitable" border="1"
Line 25: Line 25:
|-
|-
| SURF || Validated || Original authors reference binary and others.  http://boofcv.org/index.php?title=Performance:SURF
| SURF || Validated || Original authors reference binary and others.  http://boofcv.org/index.php?title=Performance:SURF
|-
| SIFT || Validated || Scale-space is computed significantly different from original.  Out performs reference binary, possibly due to more tuning options.
|-
|-
| KLT || ||  
| KLT || ||  
|-
|-
| BRIEF || ||
| BRIEF || ||
|-
| Oriented Gaussian || NA || Not validated and known to not replicate the original paper
|}
|}


Line 62: Line 62:
| EPnP || || Pending verification against author's code
| EPnP || || Pending verification against author's code
|-
|-
| Linear F || ||
| 8+ pt Fundamental || ||
|-
| 8+ pt Essential || ||
|-
| 7 pt Fundamental || ||
|-
| 7 pt Essential || ||
|-
| 5 pt Essential Nister || || Pending validation against author's Matlab code
|-
|-
| Linear H || ||
| Linear H || ||
|-
| Linear Trifocal 7 || Validated || [http://www.csse.uwa.edu.au/~wongt/matlab.html Compared to matlab code found online that was based off the same source.] [https://github.com/lessthanoptimal/ValidationBoof/tree/master/fast Validation Code]
|}
== Object Tracking ==
{| class="wikitable" border="1"
! scope="col" width="75"  | Algorithm
! scope="col" width="50"  | Status
! scope="col" width="600" | Comments
|-
| TLD || Validated || Comparable to slightly less stable than original. TLD is less stable than it at first appears, making scoring difficult. 
|-
| Circulant || Validated || Improved over original.  Much faster and slightly more stable.
|-
| MeanShiftComaniciu2003 || ||
|}
== Dense Optical Flow ==
{| class="wikitable" border="1"
! scope="col" width="75"  | Algorithm
! scope="col" width="50"  | Status
! scope="col" width="600" | Comments
|-
| Brox Warping ||  ||
|-
| HornSchunck ||  ||
|-
| HornSchunck Pyramid ||  ||
|-
| KLT ||  || Common technique.
|-
| Block ||  || Nothing to validate against.  Not based off any specific paper.
|}
|}
== Image Segmentation ==
{| class="wikitable" border="1"
! scope="col" width="75"  | Algorithm
! scope="col" width="50"  | Status
! scope="col" width="600" | Comments
|-
| FelzenHutten04 ||  ||
|-
| Mean-Shift ||  ||
|-
| SLIC ||  ||
|-
| Watershed ||  ||
|}


== Image Processing ==
== Image Processing ==

Latest revision as of 11:07, 11 June 2014

Validation and Regression

Correctly implementing algorithms and producing the expected performance is difficult. BoofCV contains thousands internal tests to help ensure correctness of its algorithms, but it is nearly impossible to be 100% sure that the implementation is correct. This is especially true since often academic papers leave out important implementations needed to reproduce their work!. In the best case scenario an implementation will be compared against the author's original implementation. This page contains a list of important algorithms inside of BoofCV and if they have been validated against external libraries or not.

Source code used to validate BoofCV can be found at the ValidationBoof project on GitHub. ValidationBoof also contains regression tests designed to check for changes in stability/performance of different algorithms. It is entirely possible for all the unit tests to pass and have a 20% drop in performance due to a minor change. Regression tests are designed to catch those problems.

Status Meaning
Validated As good or better than original code or test data
Needs Work Producing results which are not as good as expected
NA Significantly different from original. See comments in code
Blank means that it has not been externally validated

Region Descriptors

Algorithm Status Comments
SURF Validated Original authors reference binary and others. http://boofcv.org/index.php?title=Performance:SURF
SIFT Validated Scale-space is computed significantly different from original. Out performs reference binary, possibly due to more tuning options.
KLT
BRIEF

Feature Detectors

Algorithm Status Comments
Fast Hessian Validated Original authors reference binary and others. http://boofcv.org/index.php?title=Performance:SURF
FAST Validated Original author's source code. Validation Code
Harris Corner
KLT Corner
Hough Line

3D Vision

Algorithm Status Comments
Zhang99 Validated More accurate than parameters found in paper. Given same points it produces same results as OpenCV. More accurate calibration point detector then OpenCV.
EPnP Pending verification against author's code
8+ pt Fundamental
8+ pt Essential
7 pt Fundamental
7 pt Essential
5 pt Essential Nister Pending validation against author's Matlab code
Linear H
Linear Trifocal 7 Validated Compared to matlab code found online that was based off the same source. Validation Code

Object Tracking

Algorithm Status Comments
TLD Validated Comparable to slightly less stable than original. TLD is less stable than it at first appears, making scoring difficult.
Circulant Validated Improved over original. Much faster and slightly more stable.
MeanShiftComaniciu2003

Dense Optical Flow

Algorithm Status Comments
Brox Warping
HornSchunck
HornSchunck Pyramid
KLT Common technique.
Block Nothing to validate against. Not based off any specific paper.

Image Segmentation

Algorithm Status Comments
FelzenHutten04
Mean-Shift
SLIC
Watershed


Image Processing

Algorithm Status Comments
Convolution

Interpolation

Algorithm Status Comments
Nearest Neighbour
Bilinear

Image Transformation

Algorithm Status Comments
Wavelet
Retrieved from "http://boofcv.org/index.php?title=Validation:Algorithms&oldid=1366"