* green/mln/clustering/kmean1d.hh: Do minor modifications.
---
trunk/milena/sandbox/ChangeLog | 14 ++-
.../milena/sandbox/green/mln/clustering/kmean1d.hh | 172 +++++++++++---------
2 files changed, 102 insertions(+), 84 deletions(-)
diff --git a/trunk/milena/sandbox/ChangeLog b/trunk/milena/sandbox/ChangeLog
index 2057d9b..9ddceda 100644
--- a/trunk/milena/sandbox/ChangeLog
+++ b/trunk/milena/sandbox/ChangeLog
@@ -1,3 +1,9 @@
+2009-10-01 Yann Jacquelet <jacquelet(a)lrde.epita.fr>
+
+ Correct typo, update documentation and comment debugging outputs.
+
+ * green/mln/clustering/kmean1d.hh: Do minor modifications.
+
2009-09-30 Yann Jacquelet <jacquelet(a)lrde.epita.fr>
First draft for loading and saving example codes for the
@@ -9,18 +15,18 @@
2009-09-29 Yann Jacquelet <jacquelet(a)lrde.epita.fr>
- Fix behaviour when empty class appears. Fix methods order of the
+ Fix behaviour when empty class appears. Fix methods order of the
kmean1d loop.
* green/mln/clustering/kmean1d.hh
(update_kmean, launch_one_time, is_valid, is_descent_valid): Introduce
_is_number_valid which turns to false when empty class appears.
-
+
* green/mln/clustering/kmean1d.hh
(launch_one_time): Fix method call order in kmean's loop.
-
+
* green/mln/clustering/kmean1d.hh
- (launch_n_times): Introduce nb_tries that garanties to be infinite
+ (launch_n_times): Introduce nb_tries that garanties to be infinite
loop safe.
Update kmean.launch_n_times method call.
diff --git a/trunk/milena/sandbox/green/mln/clustering/kmean1d.hh b/trunk/milena/sandbox/green/mln/clustering/kmean1d.hh
index 9f467bd..670cb26 100644
--- a/trunk/milena/sandbox/green/mln/clustering/kmean1d.hh
+++ b/trunk/milena/sandbox/green/mln/clustering/kmean1d.hh
@@ -1,6 +1,4 @@
-// Copyright (C) 2007 EPITA Research and Development Laboratory (LRDE)
-// Copyright (C) 2008 EPITA Research and Development Laboratory (LRDE)
-// Copyright (C) 2009 EPITA Research and Development Laboratory (LRDE)
+// Copyright (C) 2008,2009 EPITA Research and Development Laboratory (LRDE)
//
// This file is part of Olena.
//
@@ -32,12 +30,12 @@
///
/// \brief Implements the optimized kmean algorithm.
///
-/// This algorithm is optimized in the way it proceeds directly with the
-/// greylevel attribute inspite of pixel attribute. The algorithm is
-/// independant from the image dimension. But, we have to use to compute
-/// one time the histogram. In fact, we move a recurrent cost to a fix cost
-/// in the complexity. This version is very adapted to image with small
-/// quantification.
+/// This algorithm is optimized in the way it proceeds directly with
+/// the greylevel attribute inspite of the pixel attribute. The
+/// algorithm is independant from the image dimension. But, we have to
+/// compute one time the histogram. In fact, we move a recurrent cost
+/// to a fix cost in the complexity. This version is very adapted to
+/// images with small quantification.
#include <limits.h>
#include <iostream>
@@ -127,7 +125,7 @@ namespace mln
/// \param[in] point : the image as the population of pixels.
/// \param[in] k_center : the number of centers.
/// \param[in] watch_dog : the limit to observe the convergence (10).
- /// \param[in] n_times : the number of times that we executed it (10).
+ /// \param[in] n_times : the number of times that we executed kmean(10).
kmean1d(const t_point_img& point,
const unsigned k_center,
@@ -165,7 +163,7 @@ namespace mln
// Testing outputs
t_color_dbg& get_color_dbg();
t_mean_dbg& get_mean_dbg();
- t_label_dbg& get_label_dbg();
+ t_label_dbg& get_label_dbg();
t_mean_cnv& get_mean_cnv();
t_variance_cnv& get_variance_cnv();
@@ -183,8 +181,8 @@ namespace mln
/// \{
/// \brief Two ways: Regular greylevel tick or random greylevel value or.
///
- /// There is two way to proceed the initialization. First of all, we
- /// divide the greyscale in regular tick and we assigne them to the mean
+ /// There is two way to proceed the initialization. First of all, we
+ /// divide the greyscale in regular tick and we assigne them to the mean
/// of the centers. Finaly, we can ask random initialization along the
/// greyscale axis. The second process is needed to launch_n_times the
/// kmean and converge to the best descent.
@@ -195,7 +193,7 @@ namespace mln
/// \}
-
+
//------------------------------------------------------------------------
// Computations of distance, group, center, within variance
//------------------------------------------------------------------------
@@ -206,7 +204,7 @@ namespace mln
///
/// The kmean process is a loop where distance from centers to pixels are
/// first compute. Then we assign the pixels to their nearest center.
- /// The new location of each center can then update. Finaly, hommogenity
+ /// The new location of each center can then update. Finaly, hommogeneity
/// in group is observed by the within variance.
void update_distance();
@@ -220,17 +218,37 @@ namespace mln
// Main loop
//------------------------------------------------------------------------
+ /// kmean main loop
+ /// \{
+ /// \brief User interface to launch the kmean process.
+ ///
+ /// There are two ways to launch the kmean process. The first one allow to
+ /// run it one time until convergence. As the process is a descent, it
+ /// depends on the initial center locations. The second call allow us to
+ /// rerun the process many times and to keep the best result (the one
+ /// with the smallest within variance).
+
void launch_one_time();
void launch_n_times();
+ /// \}
//------------------------------------------------------------------------
// Checking the validiy of the results
//------------------------------------------------------------------------
- bool is_valid();
- bool is_number_valid();
- bool is_descent_valid();
+ /// Checking the validity of the results.
+ /// \{
+ /// \brief These methods help us to determine the validity of the results.
+ ///
+ /// After each launching the kmean process one time, we need to know if
+ /// the descent was successfull or not. The method is_valid_descent do it
+ /// for us. The method looks for a bad center (a class with no greylevel
+ /// associate to it) and a failure in the convergence.
+
+ bool is_descent_valid();
+
+ /// \}
//------------------------------------------------------------------------
// Debugging tools
@@ -242,9 +260,11 @@ namespace mln
///
/// The methods build_label_dbg and build_all_dbg work in the input data
/// space. The first one build the 2d image of labels. The second call the
- /// first one and then builds the colorize label' image and the mean
- /// greylevel image.
-
+ /// first one and then builds the colorize label' image and the mean
+ /// greylevel image. The update_cnv and finalize_cnv methods are used to
+ /// trace the convergence. They fill two images with the mean info and
+ /// the within variance info along the convergence and the tries.
+
void build_label_dbg();
void build_all_dbg();
void update_cnv();
@@ -264,7 +284,7 @@ namespace mln
/// that the process will not converge at all. The second parameter
/// n_times is the number of times we launch again and again the simple
/// kmean loop. As the kmean process is a descent, restarting the process
- /// from different location will confort us in that we found a global
+ /// from different location will confort us in that we found a global
/// minima, not just a local one.
unsigned _k_center;
@@ -277,14 +297,19 @@ namespace mln
/// \{
/// \brief This information is used to follow the convergence.
///
- /// The within_variance is the homogenity indicator for the kmean process.
- /// The ideal situation is to find the center with the minimum variance
- /// around them. The within variance is just the sum of all variance
- /// around the centers. The current_step variable allows us to remember
- /// the current iteration in the kmean loop. This information is needed
- /// by is_descent_valid routine which decide if convergence occurs or not.
- /// The last information, current_launching, traces the progress while
- /// iterates kmean loop again and again.
+ /// The within_variance is the homogeniety indicator for the
+ /// kmean process. The ideal situation is to find the center
+ /// with the minimum variance around them. The within variance
+ /// is just the sum of all variance around the centers. The
+ /// current_step variable allows us to remember the current
+ /// iteration in the kmean loop. This information is needed by
+ /// is_descent_valid routine which decide if convergence occurs
+ /// or not. The current_step info explicit where we are in the
+ /// kmean iteration. The last information, current_launching,
+ /// traces the progress while iterates kmean loop again and
+ /// again. The flag is_number_valid is set when a empty class
+ /// appears. This flag inhibit the process and force to restart
+ /// a try.
t_result _within_variance;
unsigned _current_step;
@@ -298,9 +323,9 @@ namespace mln
/// Result of the kmean process.
/// \{
/// \brief The center location are the major results of the kmean process.
- ///
+ ///
/// The kmean process result is composed by three information. The best
- /// launching iteration, the best within variance obtained and the
+ /// launching iteration, the best within variance obtained and the
/// location of the centers associated.
unsigned _launching_min;
@@ -323,7 +348,7 @@ namespace mln
/// \{
/// \brief Centers are described by the first moment of their group.
///
- /// Centers are describe by their group attributes like the number of
+ /// Centers are describe by their group attributes like the number of
/// pixels wich are relying on, the mass center of the group and the
/// homogeneity of the group. The variance is used as indicator for the
/// convergence. The number of pixels is used as integrity indicator.
@@ -340,8 +365,8 @@ namespace mln
/// \{
/// \brief The information are concerned with the greylevel input image.
///
- /// The group image allow us to decide which greylevel (and of course
- /// which pixel) is assigned to a center. The distance image give us a
+ /// The group image allow us to decide which greylevel (and of course
+ /// which pixel) is assigned to a center. The distance image give us a
/// clue on how a greylevel could contribute to a center. The summation
/// over the greylevels of a center give us the within variance.
@@ -349,7 +374,7 @@ namespace mln
t_distance_img _distance; // label x graylevel
/// \}
-
+
/// Debugging, calibrating and testing results.
/// \{
/// \brief Some exports information to control the results.
@@ -652,7 +677,7 @@ namespace mln
//--------------------------------------------------------------------------
// Initialization of centers
//--------------------------------------------------------------------------
-
+
template <typename T, unsigned n>
inline
void kmean1d<T,n>::init_mean_regular()
@@ -660,7 +685,7 @@ namespace mln
trace::entering("mln::clustering::kmean1d::init_mean_regular");
T step = (mln_max(t_value) - mln_min(t_value)) / (_k_center-1);
mln_piter(image1d<t_value>) l(_mean.domain());
-
+
for_all(l)
{
_mean(l) = (l.ind()*step) + mln_min(t_value);
@@ -668,7 +693,7 @@ namespace mln
trace::exiting("mln::clustering::kmean1d<T,n,k>::init_mean_regular");
}
-
+
template <typename T, unsigned n>
inline
@@ -684,9 +709,9 @@ namespace mln
{
_mean(l) = (rand() % (max-min)) + min;
- std::cout << "mean" << l << " : " << _mean(l) << std::endl;
+ //std::cout << "mean" << l << " : " << _mean(l) << std::endl;
}
-
+
trace::exiting("mln::clustering::kmean1d::init_mean_random");
}
@@ -755,12 +780,12 @@ namespace mln
label = l.ind();
}
- //std::cout << "d" << l << " = " <<
+ //std::cout << "d" << l << " = " <<
// _distance(point2d(g.ind(), l.ind())) << std::endl;
}
//std::cout << "g = " << g << std::endl;
-
+
_group(g) = label;
//std::cout << "group = " << _group(g) << std::endl;
//std::cout << "-----------" << std::endl;
@@ -783,7 +808,7 @@ namespace mln
//
// Vg in [0..255]
// si w[g] = l
- // c[l] += g
+ // c[l] += h(g) * g
// n[l] += h(g)
//
// c[l] /= n
@@ -800,7 +825,7 @@ namespace mln
}
mln_piter(t_mean_img) l(_mean.domain());
-
+
/*
for_all(l)
{
@@ -810,7 +835,7 @@ namespace mln
*/
for_all(l)
{
- // State the stopping propagation Nan flag
+ // State the stopping propagation Nan flag
_is_number_valid = (0 != _number(l));
// Emergency exit
@@ -821,7 +846,7 @@ namespace mln
_mean(l) /= _number(l);
// Debugging
- std::cout << "c" << l << " = " << _mean(l) << std::endl;
+ //std::cout << "c" << l << " = " << _mean(l) << std::endl;
}
trace::exiting("mln::clustering::kmean1d::update_mean");
@@ -849,7 +874,7 @@ namespace mln
}
_within_variance += _variance(l);
- std::cout << "v(" << l << ") = " << _variance(l) << std::endl;
+ //std::cout << "v(" << l << ") = " << _variance(l) << std::endl;
}
//std::cout << "result" << result << std::endl;
@@ -869,12 +894,12 @@ namespace mln
mln_piter(t_point_img) pi(_point.domain());
mln_piter(t_label_dbg) po(_label_dbg.domain());
-
+
for_all_2(pi, po)
{
t_value val = _point(pi);
t_label grp = _group(point1d(val));
-
+
_label_dbg(po) = grp;
}
@@ -900,14 +925,14 @@ namespace mln
{
trace::entering("mln::clustering::kmean1d::update_cnv");
- _variance_cnv(point2d(_current_launching,
+ _variance_cnv(point2d(_current_launching,
_current_step)) = _within_variance;
mln_piter(t_mean_img) l(_mean.domain());
-
+
for_all(l)
{
- _mean_cnv(point3d(_current_launching,
+ _mean_cnv(point3d(_current_launching,
l.ind(),
_current_step)) = _mean(l);
}
@@ -924,7 +949,7 @@ namespace mln
// saturate the curv with the within variance
for (unsigned i = _current_step; i < _watch_dog; ++i)
_variance_cnv(point2d(_current_launching, i)) = _within_variance;
-
+
for (unsigned i = _current_step; i < _watch_dog; ++i)
{
mln_piter(t_mean_img) l(_mean.domain());
@@ -954,18 +979,7 @@ namespace mln
trace::exiting("mln::clustering::kmean1d::is_descent_valid");
return result;
}
-
- template <typename T, unsigned n>
- inline
- bool kmean1d<T,n>::is_number_valid()
- {
- trace::entering("mln::clustering::kmean1d::is_valid");
- bool result = _is_number_valid;
-
- trace::exiting("mln::clustering::kmean1d::is_valid");
- return result;
- }
//--------------------------------------------------------------------------
// Main loop
@@ -977,7 +991,7 @@ namespace mln
{
trace::entering("mln::clustering::kmean1d::launch_one_time");
- std::cout << "----------------------------------------" << std::endl;
+ //std::cout << "----------------------------------------" << std::endl;
// Initialization to start the descent
t_result old_variance = mln_max(t_result);
@@ -988,7 +1002,7 @@ namespace mln
init_mean();
update_distance();
- std::cout << "first_variance : " << old_variance << std::endl;
+ //std::cout << "first_variance : " << old_variance << std::endl;
// Execute the descent
do
@@ -1009,31 +1023,29 @@ namespace mln
// Debugging code
update_cnv();
- std::cout << "_current_step : " << _current_step << std::endl;
- std::cout << "_within_variance : " << _within_variance << std::endl;
+ //std::cout << "_current_step : " << _current_step << std::endl;
+ //std::cout << "_within_variance : " << _within_variance << std::endl;
++_current_step;
}
while (_current_step < _watch_dog && _within_variance < old_variance);
- std::cout << "----------------------------------------" << std::endl;
+ //std::cout << "----------------------------------------" << std::endl;
finalize_cnv();
trace::exiting("mln::clustering::kmean1d::launch_one_time");
}
- /// FIXME There is a risk of infinite loop if convergence is not observed
- /// FIXME What do we prefer, bad results or infinite loop ?
template <typename T, unsigned n>
inline
void kmean1d<T,n>::launch_n_times()
{
trace::entering("mln::clustering::kmean1d::launch_n_times");
-
- std::cout << "watch_dog : " << _watch_dog << std::endl;
- std::cout << "n_times : " << _n_times << std::endl;
+
+ //std::cout << "watch_dog : " << _watch_dog << std::endl;
+ //std::cout << "n_times : " << _n_times << std::endl;
// number of times we reexecute launch_one_time without any success
unsigned tries = 0;
@@ -1054,15 +1066,15 @@ namespace mln
_mean_min = _mean;
_launching_min = _current_launching;
}
-
+
// Reinitialize the number of echecs possible
tries = 0;
- std::cout << "_current_launching : " << _current_launching
- << std::endl;
+ //std::cout << "_current_launching : " << _current_launching
+ // << std::endl;
- std::cout << "within_variance[" << _current_launching << "] = "
- << _within_variance << std::endl;
+ //std::cout << "within_variance[" << _current_launching << "] = "
+ // << _within_variance << std::endl;
++_current_launching;
}
--
1.5.6.5
