小贝子编程

如何在C++中找到两个向量之间的最小(优化)距离



我正在将Python版本的'page_dewarper'(https://mzucker.github.io/2016/08/15/page-dewarping.html)翻译成C++。我将使用 dlib，这是一个很棒的工具，之前帮助我解决了一些优化问题。在 Github 存储库 (https://github.com/mzucker/page_dewarp/blob/master/page_dewarp.py) 的第 748 行中，Matt 使用 Scipy 的优化函数来查找两个向量之间的最小距离。我认为，我的C++等价物应该是 solve_least_squares_lm() 或 solve_least_squares()。我将举一个具体的例子来分析。

我的数据：
a) dstpoints 是一个带有 OpenCV 点的向量 -std::vector<cv::Point2f>(在这个例子中我有 162 个点，它们没有变化)，
b) ppts 也是std::vector<cv::Point2f>的，并且与 dstpoints 的大小相同。

std::vector<cv::Point2f> ppts = project_keypoints(params, input);

它依赖于：
-dlib::column_vector'input' 是 2*162=324 长并且没有变化，-dlib::column_vector'params' 是 189 长，它的值应该改变以获得变量 'suma' 的最小值，
如下所示：

double suma = 0.0;
for (int i=0; i<dstpoints_size; i++)
{
suma += pow(dstpoints[i].x - ppts[i].x, 2);
suma += pow(dstpoints[i].y - ppts[i].y, 2);
}

我正在寻找"参数"向量，它将给我"suma"变量的最小值。最小二乘算法似乎是解决它的好选择：http://dlib.net/dlib/optimization/optimization_least_squares_abstract.h.html#solve_least_squares，但我不知道它是否对我的情况有好处。我认为，我的问题是，对于每个不同的"参数"向量，
我得到不同的"ppts"向量，而不仅仅是单个值，而且我不知道solve_least_squares函数是否可以与我的示例匹配。
我必须计算每个点的残差。我认为，我在上述链接中的"列表"应该是这样的：

(ppts[i].x - dstpoints[i].x, ppts[i].y - dstpoints[i].y, ppts[i+1].x - dstpoints[i+1].x, ppts[i+1].y - dstpoints[i+1].y, etc.)

，其中"ppts"向量依赖于"参数"向量，然后可以用最小二乘算法解决这个问题。我不知道如何使用这些假设创建data_samples，因为它需要每个样本dlib::input_vector，如示例所示：http://dlib.net/least_squares_ex.cpp.html。
我的想法对吗？

这天我也在做同样的事情。我的解决方案是自己写一个鲍威尔类。它有效，但真的很慢。该程序需要 2 分钟的去畸变linguistics_thesis.jpg。 我不知道是什么原因导致程序运行如此缓慢。也许是因为算法或代码有一些额外的循环。 我是一名中国学生，我的学校只有Java课程。因此，如果您在我的代码中找到一些额外的代码是正常的。 这是我的鲍威尔课。

using namespace std;
using namespace cv;
class MyPowell
{
public:
vector<vector<double>> xi;
vector<double> pcom;
vector<double> xicom;
vector<Point2d> dstpoints;
vector<double> myparams;
vector<double> params;
vector<Point> keypoint_index;
Point2d dst_br;
Point2d dims;
int N;
int itmax;
int ncom;
int iter;
double fret, ftol;
int usingAorB;
MyPowell(vector<Point2d> &dstpoints, vector<double> &params, vector<Point> &keypoint_index);
MyPowell(Point2d &dst_br, vector<double> &params, Point2d & dims);
MyPowell();
double obj(vector<double> &params);
void powell(vector<double> &p, vector<vector<double>> &xi, double ftol, double &fret);
double sign(double a);// , double b);
double sqr(double a);
void linmin(vector<double> &p, vector<double> &xit, int n, double &fret);
void mnbrak(double & ax, double & bx, double & cx,
double & fa, double & fb, double & fc);
double f1dim(double x);
double brent(double ax, double bx, double cx, double & xmin, double tol);
vector<double> usePowell();
void erase(vector<double>& pbar, vector<double> &prr, vector<double> &pr);
};

#include"Powell.h"
MyPowell::MyPowell(vector<Point2d> &dstpoints, vector<double>& params, vector<Point> &keypoint_index)
{
this->dstpoints = dstpoints;
this->myparams = params;
this->keypoint_index = keypoint_index;
N = params.size();
itmax = N * N;
usingAorB = 1;
}
MyPowell::MyPowell(Point2d & dst_br, vector<double>& params, Point2d & dims)
{
this->dst_br = dst_br;
this->myparams.push_back(dims.x);
this->myparams.push_back(dims.y);
this->params = params;
this->dims = dims;
N = 2;
itmax = N * 1000;
usingAorB = 2;
}
MyPowell::MyPowell()
{
usingAorB = 3;
}
double MyPowell::obj(vector<double> &myparams)
{
if (1 == usingAorB)
{
vector<Point2d> ppts = Dewarp::projectKeypoints(keypoint_index, myparams);
double total = 0;
for (int i = 0; i < ppts.size(); i++)
{
double x = dstpoints[i].x - ppts[i].x;
double y = dstpoints[i].y - ppts[i].y;
total += (x * x + y * y);
}
return total;
}
else if(2 == usingAorB)
{
dims.x = myparams[0];
dims.y = myparams[1];
//cout << "dims.x " << dims.x << "  dims.y " << dims.y << endl;
vector<Point2d> vdims = { dims };
vector<Point2d> proj_br = Dewarp::projectXY(vdims, params);
double total = 0;
double x = dst_br.x - proj_br[0].x;
double y = dst_br.y - proj_br[0].y;
total += (x * x + y * y);
return total;
}
return 0;
}
void MyPowell::powell(vector<double> &x, vector<vector<double>> &direc, double ftol, double &fval)
{
vector<double> x1;
vector<double> x2;
vector<double> direc1;
int myitmax = 20;
if(N>500)
myitmax = 10;
else if (N > 300)
{
myitmax = 15;
}
double fx2, t, fx, dum, delta;
fval = obj(x);
int bigind;
for (int j = 0; j < N; j++)
{
x1.push_back(x[j]);
}
int iter = 0;
while (true)
{
do
{
do
{
iter += 1;
fx = fval;
bigind = 0;
delta = 0.0;
for (int i = 0; i < N; i++)
{
direc1 = direc[i];
fx2 = fval;
linmin(x, direc1, N, fval);
if (fabs(fx2 - fval) > delta)
{
delta = fabs(fx2 - fval);
bigind = i;
}
}
if (2.0 * fabs(fx - fval) <= ftol * (fabs(fx) + fabs(fval)) + 1e-7)
{
erase(direc1, x2, x1);
return;
}
if (iter >= itmax)
{
cout << "powell exceeding maximum iterations" << endl;
return;
}
if (!x2.empty())
{
x2.clear();
}
for (int j = 0; j < N; j++)
{
x2.push_back(2.0*x[j] - x1[j]);
direc1[j] = x[j] - x1[j];
x1[j] = x[j];
}
myitmax--;
cout << fx2 << endl;
fx2 = obj(x2);
if (myitmax < 0)
return;
} while (fx2 >= fx);
dum = fx - 2 * fval + fx2;
t = 2.0*dum*pow((fx - fval - delta), 2) - delta * pow((fx - fx2), 2);
} while (t >= 0.0);
linmin(x, direc1, N, fval);
direc[bigind] = direc1;
} 
}
double MyPowell::sign(double a)//, double b)
{
if (a > 0.0)
{
return 1;
}
else
{
if (a < 0.0)
{
return -1;
}
}
return 0;
}
double MyPowell::sqr(double a)
{
return a * a;
}
void MyPowell::linmin(vector<double>& p, vector<double>& xit, int n, double &fret)
{
double tol = 1e-2;
ncom = n;
pcom = p;
xicom = xit;
double ax = 0.0;
double xx = 1.0;
double bx = 0.0;
double fa, fb, fx, xmin;
mnbrak(ax, xx, bx, fa, fx, fb);
fret = brent(ax, xx, bx, xmin, tol);
for (int i = 0; i < n; i++)
{
xit[i] = (xmin * xit[i]);
p[i] += xit[i];
}
}
void MyPowell::mnbrak(double & ax, double & bx, double & cx, 
double & fa, double & fb, double & fc)
{
const double GOLD = 1.618034, GLIMIT = 110.0, TINY = 1e-20;
double val, fw, tmp2, tmp1, w, wlim;
double denom;
fa = f1dim(ax);
fb = f1dim(bx);
if (fb > fa)
{
val = ax;
ax = bx;
bx = val;
val = fb;
fb = fa;
fa = val;
}
cx = bx + GOLD * (bx - ax);
fc = f1dim(cx);
int iter = 0;
while (fb >= fc)
{
tmp1 = (bx - ax) * (fb - fc);
tmp2 = (bx - cx) * (fb - fa);
val = tmp2 - tmp1;
if (fabs(val) < TINY)
{
denom = 2.0*TINY;
}
else
{
denom = 2.0*val;
}
w = bx - ((bx - cx)*tmp2 - (bx - ax)*tmp1) / (denom);
wlim = bx + GLIMIT * (cx - bx);
if ((bx - w) * (w - cx) > 0.0)
{
fw = f1dim(w);
if (fw < fc)
{
ax = bx;
fa = fb;
bx = w;
fb = fw;
return;
}
else if (fw > fb)
{
cx = w;
fc = fw;
return;
}
w = cx + GOLD * (cx - bx);
fw = f1dim(w);
}
else 
{
if ((cx - w)*(w - wlim) >= 0.0)
{
fw = f1dim(w);
if (fw < fc)
{
bx = cx;
cx = w;
w = cx + GOLD * (cx - bx);
fb = fc;
fc = fw;
fw = f1dim(w);
}
}
else if ((w - wlim)*(wlim - cx) >= 0.0)
{
w = wlim;
fw = f1dim(w);
}
else
{
w = cx + GOLD * (cx - bx);
fw = f1dim(w);
}
}
ax = bx;
bx = cx;
cx = w;
fa = fb;
fb = fc;
fc = fw;
}
}
double MyPowell::f1dim(double x)
{
vector<double> xt;
for (int j = 0; j < ncom; j++)
{
xt.push_back(pcom[j] + x * xicom[j]);
}
return obj(xt);
}
double MyPowell::brent(double ax, double bx, double cx, double & xmin, double tol = 1.48e-8)
{
const double CGOLD = 0.3819660, ZEPS = 1.0e-4;
int itmax = 500;
double a = MIN(ax, cx);
double b = MAX(ax, cx);
double v = bx;
double w = v, x = v;
double deltax = 0.0;
double fx = f1dim(x);
double fv = fx;
double fw = fx;
double rat = 0, u = 0, fu;
int iter;
int done;
double dx_temp, xmid, tol1, tol2, tmp1, tmp2, p;
for (iter = 0; iter < 500; iter++)
{
xmid = 0.5 * (a + b);
tol1 = tol * fabs(x) + ZEPS;
tol2 = 2.0*tol1;
if (fabs(x - xmid) <= (tol2 - 0.5*(b - a)))
break;
done = -1;
if (fabs(deltax) > tol1)
{
tmp1 = (x - w) * (fx - fv);
tmp2 = (x - v) * (fx - fw);
p = (x - v) * tmp2 - (x - w) * tmp1;
tmp2 = 2.0 * (tmp2 - tmp1);
if (tmp2 > 0.0)
p = -p;
tmp2 = fabs(tmp2);
dx_temp = deltax;
deltax = rat;
if ((p > tmp2 * (a - x)) && (p < tmp2 * (b - x)) &&
fabs(p) < fabs(0.5 * tmp2 * dx_temp))
{
rat = p / tmp2;
u = x + rat;
if ((u - a) < tol2 || (b - u) < tol2)
{
rat = fabs(tol1) * sign(xmid - x);
}
done = 0;
}
}
if(done)
{
if (x >= xmid)
{
deltax = a - x;
}
else
{
deltax = b - x;
}
rat = CGOLD * deltax;
}
if (fabs(rat) >= tol1)
{
u = x + rat;
}
else
{
u = x + fabs(tol1) * sign(rat);
}
fu = f1dim(u);
if (fu > fx)
{
if (u < x)
{
a = u;
}
else
{
b = u;
}
if (fu <= fw || w == x)
{
v = w;
w = u;
fv = fw;
fw = fu;
}
else if (fu <= fv || v == x || v == w)
{
v = u;
fv = fu;
}
}
else
{
if (u >= x)
a = x;
else
b = x;
v = w;
w = x;
x = u;
fv = fw;
fw = fx;
fx = fu;
}
}
if(iter > itmax)
cout << "n Brent exceed maximum iterations.nn";
xmin = x;
return fx;
}
vector<double> MyPowell::usePowell()
{
ftol = 1e-4;
vector<vector<double>> xi;
for (int i = 0; i < N; i++)
{
vector<double> xii;
for (int j = 0; j < N; j++)
{
xii.push_back(0);
}
xii[i]=(1.0);
xi.push_back(xii);
}
double fret = 0;
powell(myparams, xi, ftol, fret);
//for (int i = 0; i < xi.size(); i++)
//{
//  double a = obj(xi[i]);
//  if (fret > a)
//  {
//      fret = a;
//      myparams = xi[i];
//  }
//}
cout << "final result" << fret << endl;
return myparams;
}
void MyPowell::erase(vector<double>& pbar, vector<double>& prr, vector<double>& pr)
{
for (int i = 0; i < pbar.size(); i++)
{
pbar[i] = 0;
}
for (int i = 0; i < prr.size(); i++)
{
prr[i] = 0;
}
for (int i = 0; i < pr.size(); i++)
{
pr[i] = 0;
}
}

我使用了PRAXIS库，因为它不需要导数信息并且速度很快。 我根据自己的需要稍微修改了代码，现在它比用 Python 编写的原始版本更快。

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium