OpenCVの最適化モジュールについて

本記事はOpenCV Advent Calendar 19日目です。

OpenCVの中には沢山の機能が入っています。本日は、その中から最適化に関するモジュールの使い方について解説します。

最適化とは

ここでの最適化とは関数の最小化を指すものとします。例えば、

f(x) = x^2 + 2x + 1

の最小値は、$x=-1$の時にゼロになりますね。こういう簡単な問題は良いのですが、複雑な問題は、そう簡単に解けません。そのような時にどうするかというと、数値を色々試しに入れてみて、最適解を探索するという方策が取られます。ただし、愚直に全数値を入れていると当然ながら計算は終わらないので、これを効率化する様々な方法があります。OpenCVにはその中でも有名な、滑降シンプレックス法、共役勾配法、線形計画法、本日は紹介しませんがMarquardt法など様々なアルゴリズムが実装されています。研究開発をしていて、モデルとなる数式はできたので、これを最適化したい！という時にサクッと最適化できるので、便利なのではないでしょうか。

滑降シンプレックス法

詳しい説明は以下にあるので省略します。
https://ja.wikipedia.org/wiki/ネルダー–ミード法

ここでは、

f(x, y) = x^2 + y^2

という、簡単な数式を最小化してみましょう。以下にあるように、そのままですが、MinProblemSolver::Functionを継承して、関数を定義してやります。先ほどの数式における$x$がコードのx[0]に、$y$がコードのx[1]に対応します。また、変数の次元数をgetDims関数で定義します。

class DistanceToLines :public MinProblemSolver::Function {
  public:
  double calc(const double* x)const{
    return x[0] * x[0] + x[1] * x[1];
  }
  virtual int getDims() const { return 2; }
};

定義した関数を以下のように最小化します。ここまで書いたところで時間がなくなったので、また追記します。

void test_downhill()
{
  Mat P = (Mat_<double>(1, 2) << 1.0, 1.0);
  Mat step = (Mat_<double>(2, 1) << -0.5, 0.5);

  Ptr<MinProblemSolver::Function> ptr_F(new DistanceToLines());
  Ptr<DownhillSolver> solver1 = DownhillSolver::create();
  
  solver1->setFunction(ptr_F);
  solver1->setInitStep(step);
  
  double res = solver1->minimize(P);

  cout << "res " << res << endl;
}

共役勾配法

class DistanceToLines2 :public MinProblemSolver::Function {
  public:
  double calc(const double* x)const{
    return x[0] * x[0] + x[1] * x[1];
  }
  void getGradient(const double* x, double* grad) {
    grad[0] = 2 * x[0];
    grad[1] = 2 * x[1];
  }
  virtual int getDims() const { return 2; }
};

void test_conj()
{
  Mat P = (Mat_<double>(1, 2) << 1.0, 1.0);

  Ptr<MinProblemSolver::Function> ptr_F(new DistanceToLines2());
  Ptr<ConjGradSolver> solver2 = ConjGradSolver::create();
  
  solver2->setFunction(ptr_F);
  
  double res = solver2->minimize(P);

  cout << "res " << res << endl;
}

void test_lp()
{
  Mat A=(cv::Mat_<double>(3,1)<<3,1,2);
  Mat B=(cv::Mat_<double>(3,4)<<1,1,3,30,2,2,5,24,4,1,2,36);
  Mat z;
  cv::solveLP(A,B,z);
  cout << z << endl;
}