macOSでCMakeを使ってビルドする際にQt 5へのパスを渡す

Qt 5をライブラリとして用いるプログラムをCMakeを使ってビルドする際、例えばQt 5 Widgetsを使う場合はCMakeLists.txtに

find_package(Qt5Widgets REQUIRED)

または

find_package(Qt5 COMPONENTS Widgets REQUIRED)

などと記述することになります*1

しかしmacOSでは、これに対して単に

cmake [path for the project root]

と実行すると、

CMake Error at CMakeLists.txt:4 (find_package):
   By not providing "FindQt5Widgets.cmake" in CMAKE_MODULE_PATH this project
   has asked CMake to find a package configuration file provided by
   "Qt5Widgets", but CMake did not find one.

   Could not find a package configuration file provided by "Qt5Widgets" with
   any of the following names:

     Qt5WidgetsConfig.cmake
     qt5widgets-config.cmake

   Add the installation prefix of "Qt5Widgets" to CMAKE_PREFIX_PATH or set
   "Qt5Widgets_DIR" to a directory containing one of the above files.  If
   "Qt5Widgets" provides a separate development package or SDK, be sure it has
   been installed.

というエラーが表示されてしまいます。これの意味は、CMakeからはQt 5 (ここでは特にQt5Widgets) が発見できなかった、ということです。

これの解決策の一つは、エラー表記にも書いてある通り、CMAKE_PREFIX_PATHを指定することです*2

例えば公式サイトのパッケージからQt 5 (ver. 5.8) をインストールしてある場合、デフォルトの設定でインストールされていれば次のようにパスを指定することになります。

cmake [path for the project root] -DCMAKE_PREFIX_PATH=~/Qt/5.8/clang_64/

Homebrewを使ってQt 5 (ver. 5.10.0) インストールしてある場合は次のようになります。

cmake [path for the project root] -DCMAKE_PREFIX_PATH=/usr/local/Cellar/qt/5.10.0

Homebrewの場合は次のように指定することもできます。

cmake [path for the project root] -DCMAKE_PREFIX_PATH=$(brew --prefix qt5)

等式制約あり最適化問題と拡張ラグランジュ乗数法

拡張ラグランジュ乗数法

等式制約あり最適化問題

\displaystyle{
\min_{\mathbf{x}} \: f(\mathbf{x}) \:\: \text{s.t.} \:\: g(\mathbf{x}) = 0
} *1

を解くためのアルゴリズムとして、拡張ラグランジュ乗数法 (augmented Lagrangian algorithm) という手法があります。これは、同じく制約あり最適化問題を扱うための手法であるラグランジュの未定乗数法 (the method of Lagrange multipliers)ペナルティ法 (penalty method) とよく似ていますが、これらよりもより実用的な手法となっています。

ラグランジュの未定乗数法

ラグランジュの未定乗数法ではラグランジュ関数 (Lagrange function)

\displaystyle{
\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) - \lambda g(\mathbf{x})
}

を考え、これの \mathbf{x}\lambda に対する偏微分が全て 0 となる状態を探索する(例えばラグランジュ関数を目的関数とみなして制約なし最適化問題を解く*2)ことで等式制約あり最適化問題を解きます。

ペナルティ法

ペナルティ法では「等式制約がどれだけ満たされていないか」に対応する項(ペナルティ)を目的関数に足した制約なし最適化問題

\displaystyle{
\min_{\mathbf{x}} \: \left\{ \: f(\mathbf{x}) + \frac{1}{2} \mu \{ g(\mathbf{x}) \} ^2 \right\}
}

を考え、これを解くことで、元の等式制約あり最適化問題を解きます*3。一回ではなく、徐々に係数  \mu の値を大きくしていき (\mu \rightarrow \infty) ながら、繰り返しこの問題を解くことで、等式制約が(ほぼ)満たされた解を得られることになります。

この手法は、\mu の値が大きくなったときに数値的に不安定な問題となってしまうという問題があります。

拡張ラグランジュ乗数法

拡張ラグランジュ乗数法では、ラグランジュ関数を上述のペナルティ項によって拡張したようなもの (= 拡張ラグランジュ関数) を制約なし最適化問題の目的関数とみなし、これを繰り返し解くことで、元の等式制約あり最適化問題を解きます。具体的には、

\displaystyle{
\min_{\mathbf{x}} \: \left\{ \: f(\mathbf{x}) + \frac{1}{2} \mu \{ g(\mathbf{x}) \} ^2 - \lambda g(\mathbf{x}) \right\}
}

という問題を繰り返し解いていきます。その際、

\displaystyle{
\lambda \leftarrow \lambda - \mu g(\mathbf{x}) \\
\mu \leftarrow \alpha \mu \:\: (\alpha > 1)
}

という更新をしていきます*4。ペナルティ法同様に \mu の値は増加していきますが、ラグランジュ乗数 \lambda が更新されていく分だけ制約 g(\mathbf{x}) = 0 が満たされた状態に近づくという性質があり*5、ペナルティ法に比べずっと小さい \mu でも有用な解に辿り着くことができます。

なお拡張ラグランジュ乗数法は "the original method of multipliers" と呼ばれることもあるようです*6*7

ライブラリを用いた利用例

NLopt というライブラリには拡張ラグランジュ乗数法が実装されており、これを呼び出すことで簡単に等式制約あり最適化問題を解くことができます。

以下の C++ による実装例では

\displaystyle{
\min_{x, y} \: x + y \:\: \text{s.t.} \:\: x^2 + y^2 = 1
}

という等式制約あり最適化問題を解いています。内部で繰り返し解く制約なし最適化問題に使用するアルゴリズムとして Nelder-Mead 法を指定しています。

#include <iostream>
#include <nlopt.hpp>

// f(x, y) = x + y
double objective_function(const std::vector<double> &x, std::vector<double>& /*grad*/, void* /*data*/)
{
    return x[0] + x[1];
}

// g(x, y) = x^2 + y^2 - 1
double equality_constraint(const std::vector<double> &x, std::vector<double>& /*grad*/, void* /*data*/)
{
    return x[0] * x[0] + x[1] * x[1] - 1.0;
}

int main()
{
    // Specify the augmented Lagrangian algorithm
    nlopt::opt optimizer(nlopt::LN_AUGLAG, 2);

    // Specify the objective function and the equality constraint
    optimizer.set_max_objective(objective_function, nullptr);
    optimizer.add_equality_constraint(equality_constraint, nullptr);

    // Specify the Nelder-Mead algorithm for solving each step
    nlopt::opt local_optimizer(nlopt::LN_NELDERMEAD, 2);
    optimizer.set_local_optimizer(local_optimizer);

    // Set initial solution
    std::vector<double> x = { 0.0, 0.0 };

    // Run optimization
    try
    {
        double value;
        optimizer.optimize(x, value);
    }
    catch (std::runtime_error e)
    {
        std::cerr << e.what() << std::endl;
    }

    // Print the result
    std::cout << "Solution: " << x[0] << ", " << x[1] << std::endl;

    return 0;
}

C++による実装例 (2018/2/13追記)

等式制約あり最適化問題を、ペナルティ法および拡張ラグランジュ乗数法で解くサンプルプログラムを公開しました。

github.com

C++11 で記述されており、制約なし最適化問題を解くために NLopt が使用されています。ソースコードは CMake で管理されています。

*1:ここでは簡単のため制約条件は1つとしていますが、任意の個数の制約条件がある場合でも基本的な考え方は変わりません。

*2:2018/02/12追記: 英語版 Wikipedia によると、\lambda に対する偏微分が 0 になる点はラグランジュ関数の極小値や極大値ではなく停留点 (saddle point) となるらしく、通常の数値最適化アルゴリズムラグランジュ関数を目的関数として計算しても解を発見できないようです。そこで、ラグランジュ関数そのものではなく、例えばラグランジュ関数の勾配の大きさを最小化するように数値最適化問題を解くことで、元々の等式制約あり最適化問題の解を得られるそうです。

*3:ペナルティ法では等式制約だけでなく不等式制約も扱うことができます。

*4:ただしパラメタ更新方法には様々な亜種があるようです。

*5:証明は教科書等を参照。

*6:http://www.mit.edu/~dimitrib/lagr_mult.html

*7:Interactive High-Quality Green-Screen Keying via Color Unmixing – Yağız Aksoy

Directional Field (方向場) の種類を整理する

Directional field (方向場)*1vector field (ベクトル場) についてのメモです。次の論文を参考にしています。

Directional Field Synthesis, Design, and Processing
Amir Vaxman, Marcel Campen, Olga Diamanti, Daniele Panozzo, David Bommes, Klaus Hildebrandt, Mirela Ben-Chen
Eurographics 2016 - State of the Art Reports
https://doi.org/10.1111/cgf.12864

この論文では三次元空間中の surface 上の directional fields (や vector fields) を主に想定して解説しています。

Directional field にはその他にも様々な種類があり、それぞれ様々な名前で呼ばれているようです。また、

Unfortunately, the available terminology in the literature suffers from many inconsistencies [...]

とあるように、時として一貫性のない言葉遣いもされているらしく、注意が必要です。

種類と特徴

代表的なもので次図のようなものが存在します。

f:id:yuki-koyama:20171102150439p:plain

円は対象の空間中のある点、矢印や線分はその点が持つ情報を表しています。

なお "direction" は方向のみを持つ情報、"vector" は方向と大きさを持つ情報として言葉を使い分けています。また rotationally-symmetric directional field を縮めて RoSy field と呼ぶそうです。前図のうち line field と cross field はそれぞれ RoSy field の一種です。

Vector Field (ベクトル場)

Vector field では空間中の各点が持つ情報は 1 つの vector によって定義されます。例えば scalar field (スカラー場) の勾配を計算することで得られるのも vector field です。

Line Field (線場)

Line field では空間中の各点が持つ情報は 180 度の回転対称性のある 2 つの directions によって定義されます。2-RoSy field とも呼ばれます。Vector field に比べて、magnitude がないだけでなく、前と後ろのどちらを向いているかの区別がありません。各点で定義される値が対称な階数 2 の tensor で表されることから symmetric tensor fields (対称テンソル場) と呼ばれることもあるようです*2

Cross Field (交差場)

Cross field では空間中の各点が持つ情報は 90 度の回転対称性の関係にある 4 つの directions によって定義されます。4-RoSy field とも呼ばれます。Non-photorealistic rendering (NPR) でも使われます*3

Frame Field

Frame field では空間中の各点が持つ情報は、必ずしも直交しない 2 つのベクトルと、その 180 度の回転対称性の関係にあるもう 2 つのベクトルによって定義されます。Panozzo et al.*4 によって導入されて以来よく使われているようです。

*1:この訳が一般的かどうかは不明。

*2:Kai Xu, Lintao Zheng, Zihao Yan, Guohang Yan, Eugene Zhang, Matthias Niessner, Oliver Deussen, Daniel Cohen-Or, and Hui Huang. 2017. Autonomous reconstruction of unknown indoor scenes guided by time-varying tensor fields. ACM Trans. Graph. 36, 6, pp.202:1--202:15. URL: http://vcc.szu.edu.cn/research/2017/tfnav/

*3:Aaron Hertzmann and Denis Zorin. 2000. Illustrating smooth surfaces. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques (SIGGRAPH '00). ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 517-526. DOI=http://dx.doi.org/10.1145/344779.345074

*4:Daniele Panozzo, Enrico Puppo, Marco Tarini, and Olga Sorkine-Hornung. 2014. Frame fields: anisotropic and non-orthogonal cross fields. ACM Trans. Graph. 33, 4, Article 134 (July 2014), 11 pages. DOI: https://doi.org/10.1145/2601097.2601179

論文読み: Differential Coordinates for Interactive Mesh Editing (SMI 2004)

以下の論文に関するメモです。

Differential Coordinates for Interactive Mesh Editing
Yaron Lipman, Olga Sorkine, Daniel Cohen-Or, David Levin, Christian Roessl, Hans-Peter Seidel
International Conference on Shape Modeling and Applications (SMI) 2004

論文について

SMI 2004 という IEEE 系の国際会議で発表された論文です。この会議は現在では消滅してしまったか改名してしまったかで、そのままは残っていなさそう*1です。

Google Scholar によると 2017 年 3 月 21 日時点で 278 件の文書に引用されている*2ようです。これは Computer Graphics 分野では非常に多い*3引用件数です。

後続研究がたくさんありそうです。例えば同年の SGP や翌年の SIGGRAPH で発表された以下の論文は同じ研究グループからの論文で、いずれも 300 件以上の引用がある*4*5有名研究です。

Linear Rotation-invariant Coordinates for Meshes
Yaron Lipman, Olga Sorkine, David Levin, Daniel Cohen-Or
SIGGRAPH 2005

Laplacian Surface Editing
Olga Sorkine, Daniel Cohen-Or, Yaron Lipman, Marc Alexa, Christian Roessl, Hans-Peter Seidel
SGP 2004

他にも多くの解説論文やサーベイ論文が出ていそうですが、ここでは省略します。

論文の主旨

Differential coordinates という考え方を利用して、三角形メッシュで表現された三次元形状を編集する手法を提案しています。Differential coordinates は、

In this paper we advocate the use of linear differential coordinates as means to preserve the high-frequency detail of the surface.

とあるように、サーフェスの高周波な詳細を保存するために導入されます。

さらにこの論文では編集による局所的な回転をうまく扱うための工夫をしていて、そこがこの論文の重要なところなのですが、ここでは省略します。

Differential Coordinates の概要

Differential coordinates とは座標の表現の一種で、ここではメッシュの各頂点の座標を表すために世界座標系による表現の代わりに用いることを想定しています。

日本語訳は不明です。もしかしたらまだないのかもしれません。

後述するように、Laplacian coordinates は differential coordinates の一種です。

世界座標系による表現が与えられたとき、それに対応する differential coordinates は、ある線形変換 D によって得ることができます。逆に differential coordinates が与えられたとき、それに対応する世界座標系による表現は、線形変換 D の逆変換 D^{-1} によって得ることができます。実際には線形変換 D は行列として表現されるので、逆変換を行うには線形方程式を解くことになります。

Differential Coordinates の導入

ここでは論文の Section 3: Fundamentals に当たる部分を簡単に紹介します。

まず G=(V, E) を三角形メッシュとします。ここで V は頂点の座標の集合、 E は辺の集合です。また j 番目の頂点の位置を \mathbf{p}_j と表すことにします。

続いて、S\mathbf{p}_j \in V を受け取りその近似的な位置を返す写像 S:

\mathbf{p}_j \approx S(\mathbf{p}_j)

を考えます。特にここでは、近似的な位置がその他の頂点位置の線形和で表されるものを考えます。つまり、
\displaystyle{S(\mathbf{p}_j) = \sum_{i \in \text{supp}(j), i \neq j} \alpha_{ji} \mathbf{p}_i}

と表される場合を考えます。ここで \text{supp}(j)j 番目の頂点を近似するために使われる頂点の集合、\alpha_{ji}j 番目の頂点を近似する際に i 番目の頂点位置に対して乗じられる重みを表します。\text{supp}(\cdot)\alpha を定めることで写像 S は定まります。

次に、頂点位置を変換するための線形変換演算子 D

D(\mathbf{p}_j) = \mathbf{p}_j - S(\mathbf{p}_j)

と定義します。ベクトル D(\mathbf{p}_j)j 番目の頂点の differential coordinates であると呼びます。

演算子 D は線形であるため、行列形式で書くことが可能です。n = \left| V \right| とし、\mathbf{M}n \times n の行列として、


M_{ij} = \begin{cases}
    1 & (i = j) \\
    - \alpha_{ij} & (j \in \text{supp}(i)) \\
    0 & (\text{otherwise})
\end{cases}

と定義します。すると、
\begin{bmatrix} \delta^{(x)} & \delta^{(y)} & \delta^{(z)} \end{bmatrix} = \mathbf{M} \begin{bmatrix} \mathbf{p}^{(x)} & \mathbf{p}^{(y)} & \mathbf{p}^{(z)} \end{bmatrix}

という関係式が成立します。ただし \delta^{(x)} \in \mathbb{R}^{n}i 番目の要素に i 番目の頂点の differential coordinates の x 座標を持つベクトルです。\delta^{(y)}, \delta^{(z)} も同様です。また、\mathbf{p}^{(x)} \in \mathbb{R}^{n}i 番目の要素に i 番目の頂点の元の x 座標を持つベクトルです。\mathbf{p}^{(y)}, \mathbf{p}^{(z)} も同様です。

なお、\left| \text{supp}(\cdot) \right| が小さければ \mathbf{M} は疎行列になるため、元の座標から differential coordinates への変換は比較的高速です。

逆に differential coordinates の情報から元の座標情報を再構築するには、上述の線形連立方程式を解けば良い*6ことになります。その際にユーザによる形状編集の意図*7を soft constraints としてこの線形連立方程式に組み込み、それを最小二乗法で解くというのが、この手法の流れとなります。

Laplacian Coordinates との関係

Laplacian coordinates は differential coordinates の特殊形です。特に

\displaystyle{\text{supp}(j) = \{ i \mid (j, i) \in E \}, \alpha_{ji} = \frac{1}{d_{ij}}}

としたときの differential coordinates のことを Laplacian coordinates と呼びます。ここで d_{ij} は頂点間の距離に応じた値などが使われますが、幾つかバリエーションがあります。

*1:http://dblp2.uni-trier.de/db/conf/smi/

*2:https://scholar.google.com/scholar?q=differential+coordinates+for+interactive+mesh+editing

*3:参考までに、本ブログでも散々言及している Muller らによる Position Based Dynamics という論文は現時点で 362 件でした。

*4:https://scholar.google.com/scholar?q=linear+rotation-invariant+coordinates+for+meshes

*5:https://scholar.google.com/scholar?q=laplacian+surface+editing

*6:ただし \mathbf{M} が特異行列の場合は soft constraints を足さないと解が定まりません。

*7:例えば「i 番目の頂点をある位置に固定したい」などの線形な制約であれば、上述の連立方程式を拡張することで組み込むことができます。