Joe Verbout / Mbed 2 deprecated main

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependencies:   mbed

opencv2/flann/simplex_downhill.h@0:ea44dc9ed014, 2016-03-31 (annotated)

Committer:
joeverbout
Date:
Thu Mar 31 21:16:38 2016 +0000
Revision:
0:ea44dc9ed014
OpenCV on mbed attempt

Who changed what in which revision?

UserRevisionLine numberNew contents of line
joeverbout 0:ea44dc9ed014 1 /***********************************************************************
joeverbout 0:ea44dc9ed014 2 * Software License Agreement (BSD License)
joeverbout 0:ea44dc9ed014 3 *
joeverbout 0:ea44dc9ed014 4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
joeverbout 0:ea44dc9ed014 6 *
joeverbout 0:ea44dc9ed014 7 * THE BSD LICENSE
joeverbout 0:ea44dc9ed014 8 *
joeverbout 0:ea44dc9ed014 9 * Redistribution and use in source and binary forms, with or without
joeverbout 0:ea44dc9ed014 10 * modification, are permitted provided that the following conditions
joeverbout 0:ea44dc9ed014 11 * are met:
joeverbout 0:ea44dc9ed014 12 *
joeverbout 0:ea44dc9ed014 13 * 1. Redistributions of source code must retain the above copyright
joeverbout 0:ea44dc9ed014 14 * notice, this list of conditions and the following disclaimer.
joeverbout 0:ea44dc9ed014 15 * 2. Redistributions in binary form must reproduce the above copyright
joeverbout 0:ea44dc9ed014 16 * notice, this list of conditions and the following disclaimer in the
joeverbout 0:ea44dc9ed014 17 * documentation and/or other materials provided with the distribution.
joeverbout 0:ea44dc9ed014 18 *
joeverbout 0:ea44dc9ed014 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
joeverbout 0:ea44dc9ed014 20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
joeverbout 0:ea44dc9ed014 21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
joeverbout 0:ea44dc9ed014 22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
joeverbout 0:ea44dc9ed014 23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
joeverbout 0:ea44dc9ed014 24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
joeverbout 0:ea44dc9ed014 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
joeverbout 0:ea44dc9ed014 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
joeverbout 0:ea44dc9ed014 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
joeverbout 0:ea44dc9ed014 28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
joeverbout 0:ea44dc9ed014 29 *************************************************************************/
joeverbout 0:ea44dc9ed014 30
joeverbout 0:ea44dc9ed014 31 #ifndef OPENCV_FLANN_SIMPLEX_DOWNHILL_H_
joeverbout 0:ea44dc9ed014 32 #define OPENCV_FLANN_SIMPLEX_DOWNHILL_H_
joeverbout 0:ea44dc9ed014 33
joeverbout 0:ea44dc9ed014 34 namespace cvflann
joeverbout 0:ea44dc9ed014 35 {
joeverbout 0:ea44dc9ed014 36
joeverbout 0:ea44dc9ed014 37 /**
joeverbout 0:ea44dc9ed014 38 Adds val to array vals (and point to array points) and keeping the arrays sorted by vals.
joeverbout 0:ea44dc9ed014 39 */
joeverbout 0:ea44dc9ed014 40 template <typename T>
joeverbout 0:ea44dc9ed014 41 void addValue(int pos, float val, float* vals, T* point, T* points, int n)
joeverbout 0:ea44dc9ed014 42 {
joeverbout 0:ea44dc9ed014 43 vals[pos] = val;
joeverbout 0:ea44dc9ed014 44 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 45 points[pos*n+i] = point[i];
joeverbout 0:ea44dc9ed014 46 }
joeverbout 0:ea44dc9ed014 47
joeverbout 0:ea44dc9ed014 48 // bubble down
joeverbout 0:ea44dc9ed014 49 int j=pos;
joeverbout 0:ea44dc9ed014 50 while (j>0 && vals[j]<vals[j-1]) {
joeverbout 0:ea44dc9ed014 51 swap(vals[j],vals[j-1]);
joeverbout 0:ea44dc9ed014 52 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 53 swap(points[j*n+i],points[(j-1)*n+i]);
joeverbout 0:ea44dc9ed014 54 }
joeverbout 0:ea44dc9ed014 55 --j;
joeverbout 0:ea44dc9ed014 56 }
joeverbout 0:ea44dc9ed014 57 }
joeverbout 0:ea44dc9ed014 58
joeverbout 0:ea44dc9ed014 59
joeverbout 0:ea44dc9ed014 60 /**
joeverbout 0:ea44dc9ed014 61 Simplex downhill optimization function.
joeverbout 0:ea44dc9ed014 62 Preconditions: points is a 2D mattrix of size (n+1) x n
joeverbout 0:ea44dc9ed014 63 func is the cost function taking n an array of n params and returning float
joeverbout 0:ea44dc9ed014 64 vals is the cost function in the n+1 simplex points, if NULL it will be computed
joeverbout 0:ea44dc9ed014 65
joeverbout 0:ea44dc9ed014 66 Postcondition: returns optimum value and points[0..n] are the optimum parameters
joeverbout 0:ea44dc9ed014 67 */
joeverbout 0:ea44dc9ed014 68 template <typename T, typename F>
joeverbout 0:ea44dc9ed014 69 float optimizeSimplexDownhill(T* points, int n, F func, float* vals = NULL )
joeverbout 0:ea44dc9ed014 70 {
joeverbout 0:ea44dc9ed014 71 const int MAX_ITERATIONS = 10;
joeverbout 0:ea44dc9ed014 72
joeverbout 0:ea44dc9ed014 73 assert(n>0);
joeverbout 0:ea44dc9ed014 74
joeverbout 0:ea44dc9ed014 75 T* p_o = new T[n];
joeverbout 0:ea44dc9ed014 76 T* p_r = new T[n];
joeverbout 0:ea44dc9ed014 77 T* p_e = new T[n];
joeverbout 0:ea44dc9ed014 78
joeverbout 0:ea44dc9ed014 79 int alpha = 1;
joeverbout 0:ea44dc9ed014 80
joeverbout 0:ea44dc9ed014 81 int iterations = 0;
joeverbout 0:ea44dc9ed014 82
joeverbout 0:ea44dc9ed014 83 bool ownVals = false;
joeverbout 0:ea44dc9ed014 84 if (vals == NULL) {
joeverbout 0:ea44dc9ed014 85 ownVals = true;
joeverbout 0:ea44dc9ed014 86 vals = new float[n+1];
joeverbout 0:ea44dc9ed014 87 for (int i=0; i<n+1; ++i) {
joeverbout 0:ea44dc9ed014 88 float val = func(points+i*n);
joeverbout 0:ea44dc9ed014 89 addValue(i, val, vals, points+i*n, points, n);
joeverbout 0:ea44dc9ed014 90 }
joeverbout 0:ea44dc9ed014 91 }
joeverbout 0:ea44dc9ed014 92 int nn = n*n;
joeverbout 0:ea44dc9ed014 93
joeverbout 0:ea44dc9ed014 94 while (true) {
joeverbout 0:ea44dc9ed014 95
joeverbout 0:ea44dc9ed014 96 if (iterations++ > MAX_ITERATIONS) break;
joeverbout 0:ea44dc9ed014 97
joeverbout 0:ea44dc9ed014 98 // compute average of simplex points (except the highest point)
joeverbout 0:ea44dc9ed014 99 for (int j=0; j<n; ++j) {
joeverbout 0:ea44dc9ed014 100 p_o[j] = 0;
joeverbout 0:ea44dc9ed014 101 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 102 p_o[i] += points[j*n+i];
joeverbout 0:ea44dc9ed014 103 }
joeverbout 0:ea44dc9ed014 104 }
joeverbout 0:ea44dc9ed014 105 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 106 p_o[i] /= n;
joeverbout 0:ea44dc9ed014 107 }
joeverbout 0:ea44dc9ed014 108
joeverbout 0:ea44dc9ed014 109 bool converged = true;
joeverbout 0:ea44dc9ed014 110 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 111 if (p_o[i] != points[nn+i]) {
joeverbout 0:ea44dc9ed014 112 converged = false;
joeverbout 0:ea44dc9ed014 113 }
joeverbout 0:ea44dc9ed014 114 }
joeverbout 0:ea44dc9ed014 115 if (converged) break;
joeverbout 0:ea44dc9ed014 116
joeverbout 0:ea44dc9ed014 117 // trying a reflection
joeverbout 0:ea44dc9ed014 118 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 119 p_r[i] = p_o[i] + alpha*(p_o[i]-points[nn+i]);
joeverbout 0:ea44dc9ed014 120 }
joeverbout 0:ea44dc9ed014 121 float val_r = func(p_r);
joeverbout 0:ea44dc9ed014 122
joeverbout 0:ea44dc9ed014 123 if ((val_r>=vals[0])&&(val_r<vals[n])) {
joeverbout 0:ea44dc9ed014 124 // reflection between second highest and lowest
joeverbout 0:ea44dc9ed014 125 // add it to the simplex
joeverbout 0:ea44dc9ed014 126 Logger::info("Choosing reflection\n");
joeverbout 0:ea44dc9ed014 127 addValue(n, val_r,vals, p_r, points, n);
joeverbout 0:ea44dc9ed014 128 continue;
joeverbout 0:ea44dc9ed014 129 }
joeverbout 0:ea44dc9ed014 130
joeverbout 0:ea44dc9ed014 131 if (val_r<vals[0]) {
joeverbout 0:ea44dc9ed014 132 // value is smaller than smalest in simplex
joeverbout 0:ea44dc9ed014 133
joeverbout 0:ea44dc9ed014 134 // expand some more to see if it drops further
joeverbout 0:ea44dc9ed014 135 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 136 p_e[i] = 2*p_r[i]-p_o[i];
joeverbout 0:ea44dc9ed014 137 }
joeverbout 0:ea44dc9ed014 138 float val_e = func(p_e);
joeverbout 0:ea44dc9ed014 139
joeverbout 0:ea44dc9ed014 140 if (val_e<val_r) {
joeverbout 0:ea44dc9ed014 141 Logger::info("Choosing reflection and expansion\n");
joeverbout 0:ea44dc9ed014 142 addValue(n, val_e,vals,p_e,points,n);
joeverbout 0:ea44dc9ed014 143 }
joeverbout 0:ea44dc9ed014 144 else {
joeverbout 0:ea44dc9ed014 145 Logger::info("Choosing reflection\n");
joeverbout 0:ea44dc9ed014 146 addValue(n, val_r,vals,p_r,points,n);
joeverbout 0:ea44dc9ed014 147 }
joeverbout 0:ea44dc9ed014 148 continue;
joeverbout 0:ea44dc9ed014 149 }
joeverbout 0:ea44dc9ed014 150 if (val_r>=vals[n]) {
joeverbout 0:ea44dc9ed014 151 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 152 p_e[i] = (p_o[i]+points[nn+i])/2;
joeverbout 0:ea44dc9ed014 153 }
joeverbout 0:ea44dc9ed014 154 float val_e = func(p_e);
joeverbout 0:ea44dc9ed014 155
joeverbout 0:ea44dc9ed014 156 if (val_e<vals[n]) {
joeverbout 0:ea44dc9ed014 157 Logger::info("Choosing contraction\n");
joeverbout 0:ea44dc9ed014 158 addValue(n,val_e,vals,p_e,points,n);
joeverbout 0:ea44dc9ed014 159 continue;
joeverbout 0:ea44dc9ed014 160 }
joeverbout 0:ea44dc9ed014 161 }
joeverbout 0:ea44dc9ed014 162 {
joeverbout 0:ea44dc9ed014 163 Logger::info("Full contraction\n");
joeverbout 0:ea44dc9ed014 164 for (int j=1; j<=n; ++j) {
joeverbout 0:ea44dc9ed014 165 for (int i=0; i<n; ++i) {
joeverbout 0:ea44dc9ed014 166 points[j*n+i] = (points[j*n+i]+points[i])/2;
joeverbout 0:ea44dc9ed014 167 }
joeverbout 0:ea44dc9ed014 168 float val = func(points+j*n);
joeverbout 0:ea44dc9ed014 169 addValue(j,val,vals,points+j*n,points,n);
joeverbout 0:ea44dc9ed014 170 }
joeverbout 0:ea44dc9ed014 171 }
joeverbout 0:ea44dc9ed014 172 }
joeverbout 0:ea44dc9ed014 173
joeverbout 0:ea44dc9ed014 174 float bestVal = vals[0];
joeverbout 0:ea44dc9ed014 175
joeverbout 0:ea44dc9ed014 176 delete[] p_r;
joeverbout 0:ea44dc9ed014 177 delete[] p_o;
joeverbout 0:ea44dc9ed014 178 delete[] p_e;
joeverbout 0:ea44dc9ed014 179 if (ownVals) delete[] vals;
joeverbout 0:ea44dc9ed014 180
joeverbout 0:ea44dc9ed014 181 return bestVal;
joeverbout 0:ea44dc9ed014 182 }
joeverbout 0:ea44dc9ed014 183
joeverbout 0:ea44dc9ed014 184 }
joeverbout 0:ea44dc9ed014 185
joeverbout 0:ea44dc9ed014 186 #endif //OPENCV_FLANN_SIMPLEX_DOWNHILL_H_
joeverbout 0:ea44dc9ed014 187