Wiki
Version 6 (Annamaria Kiss, 03/02/2017 10:52) → Version 7/62 (Annamaria Kiss, 03/02/2017 11:40)
h1. The "lsm3d" tool
h2. The Level Set Method (LSM) Download
<pre>
svn --username $USER checkout http://forge.cbp.ens-lyon.fr/svn/levelsetmethod/lsm3D
</pre>
h2. Compile
<pre>
cd lsm3D
./lsm3D_compile.sh
</pre>
The main idea of binaries will be in the level set method in segmentation is lsm3D/bin folder. Add this folder to evolve a contour until it fits a desired object your PATH by adding in the image. A level set function (LSF) is defined on the image (one value per pixel), and the contour is defined as it's zero crossing points. The function is positive inside the contour and negative outside of it. At each time step, the values of the LSF are updated in each pixel, and thus the zero crossing points change and the contour evolves. The LSF's evolution is such that an energy is minimized, which in turn is usually based on the image properties (gradient, intensity...) and the geometrical aspects of the contour (curvature, size...). your .bashrc file
export PATH=$PATH:Path_to_your_directory/lsm3D/bin
h2. Test and Howto
Go into the data directory
<pre>
cd data
</pre>
If you lounch the binaries without any arguments, they will print the syntax and example values of all parameters.
h3. lsm_detect_contour
In order to check the syntax,
<pre>
lsm_detect_contour
</pre>
gives as output
<pre>
Usage : lsm_detect_contour img t_up t_down a b smooth perUp perDown
Examples for parameter values:
------------------------------
img : grayscale image of cells, (.inr or .inr.gz)
Upper threshold : t_up = 20
Down threshold : t_down = 5
Area term : a = 0 (0.5, 1)
Curvature term : b = 0 (1)
Gaussian filter : smooth = 1 (0, if image already filtered)
Stop criteria : the contour evolution is in [perDown,perUp] for 10 consecutive iterations
perUp = 0.002, perDown = -0.002
</pre>
In order to test it on an image file "t3_cut.inr.gz", lounch the binary with parameters :
<pre>
lsm_detect_contour t3_cut.inr.gz 20 10 0 0 1 0.002 -0.002
</pre>
The detected contour is in the directory "t3_cut_LSMcont20-10a0b0s1".
h3. lsm_cells
The syntax is
<pre>
Usage : lsm_cells img img_wat img_contour erosion [a b smooth lsm_type]
-----------------
img : grayscale image of cells, (.inr or .inr.gz)
img_wat : image of seeds, (.inr or .inr.gz)
img_contour : mask, where cells do not evolve, (.inr or .inr.gz)
if 'None', then cells can evolve on the whole image
erosion : amount of erosion of seeds for initialisation (uint8) --> -2, 0, 2
if 0, then no erosion or dilation
if negative, then a dilation is performed
a : area term (float) --> 0 or 0.5 or 1 (the default is 0.5)
if negative, the object retracts
if positive, the object inflates
b : curvature term (float) --> 0 or 1 (the default is 0)
gamma : scale parameter (float>0) --> 0.5 or 1 (the default is 1)
smooth : gaussian blur to apply to the image (int) --> 0 or 1 (the default is 0)
lsm_type : image, gradient or hessien based evolution --> 'i', 'g' or 'h' (the default is g)
</pre>
Applying it to the image "t3_cut.inr.gz" as the level sets are initialised by the watershed segmentation of the same image
<pre>
lsm_cells t3_cut.inr.gz t3_cut_wat.inr.gz t3_cut_LSMcont20-10a0b0s1/t3_cut_LSMcont20-10a0b0s1.inr.gz 2 0.3 0 0.2 1 'h'
</pre>
you will get the new segmentation in the "t3_cut_wat_cellLSM-d2-a0.3-b0-g0.2-s1-h" folder.
h2. Level Set Method
The main idea of the level set method in segmentation is to evolve a contour until it fits a desired shape.
A function is defined on the image (one value per pixel), and the contour is defined as it's zero crossing points. The function is positive inside the contour and negative outside it. At each time step, the values of the function are updated in each pixel, and thus the zero crossing points change and the contour evolve. The function can be seen as an energy to minimize. It is usually based on the image properties (gradient, intensity...) and the geometrical aspect of the contour (curvature, size...).
h3. LSM to detect exterior shape (LSM detect contour)
The LSM is initialized with a linear threshold, which roughly separates the background from the cells. The threshold is linear to adjust for the image intensity variation along the z-axis. The function takes +c0 values inside the initial contour and -c0 outside, the area in the contour being the background.
The contour evolves attracted mainly by the maximum gradient, corresponding to the edge of the cell walls. There are also a curvature term, to obtain a smoother contour, and an inflate term to push the contour towards the boundaries.
Each time step, the background growth is measured. The algorithm stops when the growth stays in a small interval near zero for ten consecutive iterations. The background is then fixed and will not move during the watershed segmentation and the LSM cell detection.
*How to use*
<pre>
./lsm_contour.exe image t_up t_down beta smooth
image : grayscale 8bit image in .inr or .inr.gz
t_up, t_down : extreme value for linear threshold
beta : coefficient of the curvature term (0 - 1)
smooth : amount of Gaussian blur to apply on the image
</pre>
h3. LSM to detect cells (LSM cells)
The detection of the cells shapes is done in 3 step :
* Eroding the watershed segmentation and initialize a function for each cell
* Evolve independently each cell's contour, attract by the maximal gradient (the inside edge of the cell walls)
* Evolve simultaneously every cell's contour, attract by the maximal intensity (center of the cell walls)
In the last step, every cell evolve for one iteration and then possible overlap are checked. An overlap region is consider not segmented. A cell can't evolve in an other cell area : overlap can only happen in a same iteration. At each iteration, the growth of the segmented areas is measured, and the algorithm stop when this growth become null.
Theoretically, the algorithm should stop when all the image is segmented. In practice, the segmentation growth is more and more slow and some area between cells are never segmented, or too slowly. It's more efficient to stop the LSM and to use another algorithm to fill the remaining holes.
From left to right : watershed, eroded watershed (step 1), evolve towards edge (step 2), final segmentation (step 3)
!watershed.jpg! !t3-cut_eroded.png! !t3-cut_evoEdge.png! !t3-cut_final.png!
*How to use*
<pre>
./lsm_cells.exe image wat contour erosion
image : grayscale 8bit image .inr or .inr.gz
wat : 16bit image in .inr or .inr.gz
contour : binary image in .inr or .inr.gz with background=1
erosion : amount of erosion for each cell
</pre>
h2. Program optimization
h3. Translation and shortcuts
The codes were first translate from Python to C++, without major modifications. The python codes use the OpenAlea library whereas the C++ translation use the CImg library.
The computation time was divided by 4.5 from Python to C++ in the LSM detect contour. The amount of memory used was also slightly diminish.
Some part of the code were then optimize by changing the way to loop over images and by removing unnecessary computation. Those modifications divided the computation time by 2.5. We try to implement a narrow-band method but it wasn't conclusive.
For the LSM detect contour, the final C++ code is approximately 11 time faster than the original Python code. It also use thrice as less memory.
h3. Parallelization
h2. The Level Set Method (LSM) Download
<pre>
svn --username $USER checkout http://forge.cbp.ens-lyon.fr/svn/levelsetmethod/lsm3D
</pre>
h2. Compile
<pre>
cd lsm3D
./lsm3D_compile.sh
</pre>
The main idea of binaries will be in the level set method in segmentation is lsm3D/bin folder. Add this folder to evolve a contour until it fits a desired object your PATH by adding in the image. A level set function (LSF) is defined on the image (one value per pixel), and the contour is defined as it's zero crossing points. The function is positive inside the contour and negative outside of it. At each time step, the values of the LSF are updated in each pixel, and thus the zero crossing points change and the contour evolves. The LSF's evolution is such that an energy is minimized, which in turn is usually based on the image properties (gradient, intensity...) and the geometrical aspects of the contour (curvature, size...). your .bashrc file
export PATH=$PATH:Path_to_your_directory/lsm3D/bin
h2. Test and Howto
Go into the data directory
<pre>
cd data
</pre>
If you lounch the binaries without any arguments, they will print the syntax and example values of all parameters.
h3. lsm_detect_contour
In order to check the syntax,
<pre>
lsm_detect_contour
</pre>
gives as output
<pre>
Usage : lsm_detect_contour img t_up t_down a b smooth perUp perDown
Examples for parameter values:
------------------------------
img : grayscale image of cells, (.inr or .inr.gz)
Upper threshold : t_up = 20
Down threshold : t_down = 5
Area term : a = 0 (0.5, 1)
Curvature term : b = 0 (1)
Gaussian filter : smooth = 1 (0, if image already filtered)
Stop criteria : the contour evolution is in [perDown,perUp] for 10 consecutive iterations
perUp = 0.002, perDown = -0.002
</pre>
In order to test it on an image file "t3_cut.inr.gz", lounch the binary with parameters :
<pre>
lsm_detect_contour t3_cut.inr.gz 20 10 0 0 1 0.002 -0.002
</pre>
The detected contour is in the directory "t3_cut_LSMcont20-10a0b0s1".
h3. lsm_cells
The syntax is
<pre>
Usage : lsm_cells img img_wat img_contour erosion [a b smooth lsm_type]
-----------------
img : grayscale image of cells, (.inr or .inr.gz)
img_wat : image of seeds, (.inr or .inr.gz)
img_contour : mask, where cells do not evolve, (.inr or .inr.gz)
if 'None', then cells can evolve on the whole image
erosion : amount of erosion of seeds for initialisation (uint8) --> -2, 0, 2
if 0, then no erosion or dilation
if negative, then a dilation is performed
a : area term (float) --> 0 or 0.5 or 1 (the default is 0.5)
if negative, the object retracts
if positive, the object inflates
b : curvature term (float) --> 0 or 1 (the default is 0)
gamma : scale parameter (float>0) --> 0.5 or 1 (the default is 1)
smooth : gaussian blur to apply to the image (int) --> 0 or 1 (the default is 0)
lsm_type : image, gradient or hessien based evolution --> 'i', 'g' or 'h' (the default is g)
</pre>
Applying it to the image "t3_cut.inr.gz" as the level sets are initialised by the watershed segmentation of the same image
<pre>
lsm_cells t3_cut.inr.gz t3_cut_wat.inr.gz t3_cut_LSMcont20-10a0b0s1/t3_cut_LSMcont20-10a0b0s1.inr.gz 2 0.3 0 0.2 1 'h'
</pre>
you will get the new segmentation in the "t3_cut_wat_cellLSM-d2-a0.3-b0-g0.2-s1-h" folder.
h2. Level Set Method
The main idea of the level set method in segmentation is to evolve a contour until it fits a desired shape.
A function is defined on the image (one value per pixel), and the contour is defined as it's zero crossing points. The function is positive inside the contour and negative outside it. At each time step, the values of the function are updated in each pixel, and thus the zero crossing points change and the contour evolve. The function can be seen as an energy to minimize. It is usually based on the image properties (gradient, intensity...) and the geometrical aspect of the contour (curvature, size...).
h3. LSM to detect exterior shape (LSM detect contour)
The LSM is initialized with a linear threshold, which roughly separates the background from the cells. The threshold is linear to adjust for the image intensity variation along the z-axis. The function takes +c0 values inside the initial contour and -c0 outside, the area in the contour being the background.
The contour evolves attracted mainly by the maximum gradient, corresponding to the edge of the cell walls. There are also a curvature term, to obtain a smoother contour, and an inflate term to push the contour towards the boundaries.
Each time step, the background growth is measured. The algorithm stops when the growth stays in a small interval near zero for ten consecutive iterations. The background is then fixed and will not move during the watershed segmentation and the LSM cell detection.
*How to use*
<pre>
./lsm_contour.exe image t_up t_down beta smooth
image : grayscale 8bit image in .inr or .inr.gz
t_up, t_down : extreme value for linear threshold
beta : coefficient of the curvature term (0 - 1)
smooth : amount of Gaussian blur to apply on the image
</pre>
h3. LSM to detect cells (LSM cells)
The detection of the cells shapes is done in 3 step :
* Eroding the watershed segmentation and initialize a function for each cell
* Evolve independently each cell's contour, attract by the maximal gradient (the inside edge of the cell walls)
* Evolve simultaneously every cell's contour, attract by the maximal intensity (center of the cell walls)
In the last step, every cell evolve for one iteration and then possible overlap are checked. An overlap region is consider not segmented. A cell can't evolve in an other cell area : overlap can only happen in a same iteration. At each iteration, the growth of the segmented areas is measured, and the algorithm stop when this growth become null.
Theoretically, the algorithm should stop when all the image is segmented. In practice, the segmentation growth is more and more slow and some area between cells are never segmented, or too slowly. It's more efficient to stop the LSM and to use another algorithm to fill the remaining holes.
From left to right : watershed, eroded watershed (step 1), evolve towards edge (step 2), final segmentation (step 3)
!watershed.jpg! !t3-cut_eroded.png! !t3-cut_evoEdge.png! !t3-cut_final.png!
*How to use*
<pre>
./lsm_cells.exe image wat contour erosion
image : grayscale 8bit image .inr or .inr.gz
wat : 16bit image in .inr or .inr.gz
contour : binary image in .inr or .inr.gz with background=1
erosion : amount of erosion for each cell
</pre>
h2. Program optimization
h3. Translation and shortcuts
The codes were first translate from Python to C++, without major modifications. The python codes use the OpenAlea library whereas the C++ translation use the CImg library.
The computation time was divided by 4.5 from Python to C++ in the LSM detect contour. The amount of memory used was also slightly diminish.
Some part of the code were then optimize by changing the way to loop over images and by removing unnecessary computation. Those modifications divided the computation time by 2.5. We try to implement a narrow-band method but it wasn't conclusive.
For the LSM detect contour, the final C++ code is approximately 11 time faster than the original Python code. It also use thrice as less memory.
h3. Parallelization