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