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