Gallery of Level Set Method in 2D

in English

先に実装したエンジンをネットで拾った画像に適用してみました。現時点での限界が分かります。

gallery

Compilation of OpenCV by clang with C++11

Let's start by downloading source code from this site. Then, my procedure is as follows: Here, the error claiming that the function iota is not defined occurred. The place is in the 809-th line of OpenCV-2.4.3/modules/contrib/src/spinimages.cpp. At the top of the file, I added #include <numeric>. Again make. That's all.

Level Set Method in 3D

in Japanese

Introduction

In the previous page, I showed the implementation of the Level Set Method in the 2D space. As I have recently extended it to the 3D space, I would like to provide you with a brief explanation on the new implementation.

Demos

I start with showing two demo movies.
demo-1:

There are two blue spheres. The initial front colored in red is a cube that encloses those spheres. The term "front" means the zero level set. Once the Level Set Method begins, the front gradually splits into two spherical surfaces, each of which wraps the blue sphere. If the screen capture is off and there is no operation to change the viewpoint, the calculation is done in about 70 second.
demo-2:

Also in this demo there are two spheres. The initial front is placed, however, outside those spheres. As the Level Set Method goes on, the front is growing up with enclosing the two spheres. The front finally translates into a large spherical surface that has the two spherical surfaces inside it. To stop the evolution of the front, I put a spherical wall that is drawn using the blue wire frame in the demo. If the screen capture is off and there is no operation to change the viewpoint, the calculation is done in about 120 second.

In both demos, the size of the space is 200x200x200 pixels. I used the OpenGL library to draw the sequences.

Development Environment

1. Mac OS X 10.8.2
2. Processor：3.06 GHz Intel Core 2 Duo
3. Memory：4GB
4. Xcode4.5.2 with Apple LLVM 4.1（C++ Language Dialect → C++11, C++ Standard Library → libc++）
5. boost-1.51.0 built by the above compiler. See here.
6. opencv-2.4.3 built by the above compiler. See here.

The C++11 new features, such as lambda expression and thread library, are used to implement the application.

My Source Code

Here is my source code. I have tested the application on the above machine.

Usage

An execution file name is LevelSetMethod2. Running it without any arguments, it prints the following usage statements on the standard output: The detail descriptions for those arguments are as follows:

1. dim : This is the space dimension. Set either 2 or 3.
2. input : In the case of the 3D space, set either "pattern0" or "pattern1." When the former(latter) string is given, the application begins the demo-1(demo-2). I have a plan to support arbitrary 3D objects users create.(See here)
3. wband : I applied the Narrow Band Level Set Method to the current application. The parameter wband indicates the width of region in which the front is calculated. It is discussed below.
4. wreset : To increase accuracy of the calculation, the front is re-initialized every time it comes in a region. The parameter wreset indicates the width of the region. It is discussed below.
5. time_step : The Level Set Method results in the time evolution equation. The parameter time_step represents the time step used to solve the equation.
6. gain : The speed of the front consists of a constant term and a curvature-dependent term. The weight of the latter term is given by the parameter gain. It is discussed below.
7. constant_speed : the constant term of the speed
8. speed_threshold : When the speed gets less than speed_threshold, it is replaced by zero.
9. left, right, top, bottom, front, back : In these parameters, the term "front" does not mean the zero level set. These specifies the size and position of the initial zero level set. It is always a cube. The parameters front and back are used in the 3D space.

The parameters wband and wreset are illustrated in the following figure.

The green part of wband corresponds to wreset. Every time the front comes in the region, it is re-initialized to increase accuracy of the calculation.

The speed function is defined as,

where, is the curvature of the front. The parameter constant_speed indicates . If you want to shrink(expand) the front, you have to set it to negative(positive) value. The parameter gain corresponds to .
has the smoothing effect on the front.

① In the 3D space:
The following command begins the demo-1: In this case, the following operations from the keyboard are available:

1. ESC: quit the application
2. p: pause the application
3. f: enable/disable to draw the front in the viewer
4. o: enable/disable to draw the objects in the viewer
5. <: make the viewpoint close to the objects
6. >: make the viewpoint far from the objects
7. u: rotate around x axis with positive(right-hand) direction
8. n: rotate around x axis with negative direction
9. h: rotate around y axis with positive(right-hand) direction
10. j: rotate around y axis with negative direction

As the argument --verbose is set, some quantities on the pixels constituting the front(zero level set) are printed on the standard output. The meanings of those are as follows:

1. zero speed rate: the rate of the number of the pixels with zero speed. When it reaches 1, the evolution of the front completely finishes.
2. front size: the total number of pixels
3. total speed: the sum of the absolute values of the speeds

The application finishes when the total speed takes the same value three successive times.

②In the 2D space:
The following command begins the Level Set Method in the 2D space: As the above command does not have the argument --verbose, the quantities on the front are not written on the standard output. In the 2D space, the input has to be the one-channel gray image. The demo video is shown below. If the screen capture is off, the calculation is done in about 0.8 second. The size of the image is 256x256pixels. (See also here.)

In this case, the following operations from the keyboard are available:

1. ESC: quit the application
2. p: pause the application
3. f: enable/disable to draw the front in the viewer
4. o: enable/disable to draw the objects in the viewer

Brief Overview Of Source Code

The main function is as follows:
//main.cpp In the class CommandLineInterface, the following static functions are defined,

1. execute_level_set_method_in_2d
2. execute_level_set_method_in_3d

For example, the function execute_level_set_method_in_3d constructs the object of the class LevelSetMethodViewer3d.
//CommandLineInterface.cpp In the 9-th line, the object of the class LevelSetMethodViewer3d is created. Then the viewer is initialized in the 19-th line(initialize_viewer) and the Level Set Method is also initialized in the 20-th line(initialize_level_set_method). The latter function has the following body:
// LevelSetMethodViewer.h The object of the class LevelSetMethod<Dimension> in the 13-th line executes the Level Set Method. It is the template class as,
// LevelSetMethod.h The template argument D accepts the class that represents the dimension as,
// DimensionTypes.h

References

1. コンピュータビジョン 最先端ガイド1, 第1章(in Japanese)
2. Fast Level Set Methodの提案とビデオ画像の移動物体のリアルタイム追跡, 情報処理学会論文誌, Vol.44, No.8, Aug, 2003(in Japanese)
3. Fast Level Set Methodを用いた複数移動物体の三次元追跡, 日本ロボット学会誌, Vol.23, No.7, pp.813-820, 2005(in Japanese)
4. Level Set Methods and Fast Marching Methods, J.A.Sethian, Cambridge University Press, ISBN 0-521-64557-3

Level Set 法 3次元への適用

in English

はじめに

以前こちらでLevel Set法を紹介しました。今回これを3次元に拡張したのであらためて紹介します。
（プログラムにバグがありましたので以下の文章を書き直しました。この修正により、計算速度が大幅に改善されました。2013年1月20日）

デモ

こんな感じです。
デモ1:

2つの球体をその内部に持つように立方体（初期波面）を配置します。Level Set法を実行すると、立方体が徐々に縮まり、2つの球面に分裂する様子を見ることが出来ます（画面キャプチャなし視点変更なしなら、70秒ほどで計算を終えます）。
デモ2:

立方体（初期波面）を2つの球体の外に置いた場合です。立方体は球体を呑み込みながら成長していき、ワイヤフレームで示した大きな球面に衝突して止まります。言い換えると、小さな立方体は2つの球面を内部に含む大きな球面に成長します（画面キャプチャなし視点変更なしなら、120秒ほどで計算を終えます）。

どちらのデモも空間の大きさは200x200x200pixlesです。描画にはOpenGLを使いました。

開発環境

1. Mac OS X 10.8.2
2. プロセッサ：3.06 GHz Intel Core 2 Duo
3. メモリ：4GB
4. Xcode4.5.2 with Apple LLVM 4.1（C++ Language Dialect → C++11, C++ Standard Library → libc++）
5. boost-1.51.0（上記コンパイラでコンパイルしたもの。こちら）
6. opencv-2.4.3（上記コンパイラでコンパイルしたもの。こちら）

注意：lambda式やthreadなど、C++11の新しい機能を使用しています。

ソース

こちらです。上記の開発環境で動作確認しました。

実行方法

実行ファイ名は、LevelSetMethod2です。引数なしで実行すると以下を出力します。 各引数の意味は以下の通りです。

1. dim:次元です。2か3を指定します。
2. verbose:途中経過を出力したいときに指定します。
3. input: 2次元のとき入力ファイルへのパスを、3次元のとき"pattern0"か"pattern1"を渡します。3次元の場合はプログラム内で既定の立体を作成します。任意の立体を与えられるようにする予定です（こちらへ）。
4. wband: Narrow Band Level Set法を採用しています。波面（境界面）の計算領域の幅を設定します（後述）。
5. wreset: Level Set法の精度を高めるため、ある計算ステップごとに波面の初期化を行います。その引き金となる領域の幅を設定します（後述）。
6. time_step: Level Set法では波面を時間発展させます。その時間幅を設定します。
7. gain: 波面の速度は定数項と波面の曲率に依存する項から成ります。後者の割合です（後述）。
8. constant_speed: 波面速度の定数項です（後述）。
9. speed_threshold: この速度以下の場合、波面速度を0とみなします。
10. left, right, top, bottom, front, back: 最初に与える立方体のサイズを指定します。frontとbackは３次元の場合に使います。

以下の図はwbandとwresetを示したものです。

wbandのうち緑で示した領域の幅がwresetです。波面が緑の領域に到達すると、波面の再初期化が実行されます。 本アプリで使用している速度関数 は以下で定義されます。

ここで、 は曲率です。constant_speedは に相当します。閉曲面を内側に向かって収縮させるなら負の値を、その逆なら正の値を設定します。また、gainは に相当します。この項は曲面を滑らかにする効果を持ちます。

①３次元の場合:
以下のコマンドを実行します。最初に示したデモ1が始まります。 ここでキーボードから以下の操作が可能です。

1. ESC: 終了します。
2. p: 一時停止します。
3. f: 波面(front)の描画を有効・無効にします。
4. o: 物体(object)の描画を有効・無効にします。
5. <: 視点を物体に近づけます。
6. >: 視点を物体から遠ざけます。
7. u: x軸周りに回転します（右ねじ）。
8. n: x軸周りに逆回転します。
9. h: y軸周りに回転します（右ねじ）。
10. j: y軸周りに逆回転します。

引数に--verboseを指定したので、コマンドライン上に波面（front）を構成するピクセルに関する量が表示されます。 その意味は以下の通りです。

1. zero speed rate: 成長速度が0となったピクセルの割合。1のとき波面の成長は完全に停止します。
2. front size: 全ピクセル数。
3. total speed: ピクセルの成長速度の絶対値の和。

本アプリは、total speedが３回連続して同じ値になると終了します。

②２次元の場合:
以下のコマンドを実行します。 引数に--verboseを指定しない場合、波面に関する上記3つの量は表示されません。 なお、入力画像は１チャンネルのグレー画像でなければなりません。こんな感じになります( 画面キャプチャなしなら0.8秒程で計算を終えます)。画像サイズは256x256pixelsです。（追記：こちらに２次元のデモを追加しました。）

ここで、キーボードから以下の操作が可能です。

1. ESC: 終了します。
2. p: 一時停止します。
3. f: 波面(front)の描画を有効・無効にします。
4. o: 物体(object)の描画を有効・無効にします。

ソース概説

main関数は以下の通りです。
//main.cpp クラスCommandLineInterfaceには以下2つのstatic関数が定義されています。

1. execute_level_set_method_in_2d
2. execute_level_set_method_in_3d

例えばexecute_level_set_method_in_3dではクラスLevelSetMethodViewer3dを呼び出しています。
//CommandLineInterface.cpp 9行目でクラスLevelSetMethodViewer3dのインスタンスを作成し、そのあと、viewerの初期化（19行目のinitialize_viewer）とLevel Set法の初期化（20行目のinitialize_level_set_method）を行っています。後者の関数の中身は以下の通りです。
// LevelSetMethodViewer.h 13行目にあるクラスLevelSetMethod<Dimension>がLevel Set法を実行します。これはテンプレートクラスです。
// LevelSetMethod.h テンプレート引数Dには次元を表現するクラスを与えます。
// DimensionTypes.h

参考文献

1. コンピュータビジョン 最先端ガイド1, 第1章
2. Fast Level Set Methodの提案とビデオ画像の移動物体のリアルタイム追跡, 情報処理学会論文誌, Vol.44, No.8, Aug, 2003
3. Fast Level Set Methodを用いた複数移動物体の三次元追跡, 日本ロボット学会誌, Vol.23, No.7, pp.813-820, 2005
4. Level Set Methods and Fast Marching Methods, J.A.Sethian, Cambridge University Press, ISBN 0-521-64557-3

追記

こちらにも2Dへの適用例を掲載しました。