libcrn  3.9.5
A document image processing library
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CRN2Means.h
Go to the documentation of this file.
1 /* Copyright 2013-2016 INSA-Lyon, ENS-Lyon
2  *
3  * This file is part of libcrn.
4  *
5  * libcrn is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU Lesser General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  *
10  * libcrn is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public License
16  * along with libcrn. If not, see <http://www.gnu.org/licenses/>.
17  *
18  * file: CRN2Means.h
19  * \author Yann LEYDIER
20  */
21 
22 #ifndef CRN2MEANS_HEADER
23 #define CRN2MEANS_HEADER
24 
25 #include <CRNType.h>
26 #include <CRNMath/CRNMath.h>
27 #include <type_traits>
28 
29 namespace crn
30 {
31  /****************************************************************************/
46  template<
47  typename ITER,
48  typename std::enable_if<
49  // can copy
50  std::is_copy_assignable<typename std::iterator_traits<ITER>::value_type>::value &&
51  // can assign 0
52  std::is_assignable<typename std::add_lvalue_reference<typename std::decay<typename std::iterator_traits<ITER>::value_type>::type>::type, int>::value &&
53  // operator<
55  // operators +, -, *(double)
57  int>::type = 0
58  >
59  std::pair<typename std::iterator_traits<ITER>::value_type, typename std::iterator_traits<ITER>::value_type>
60  TwoMeans(ITER beg, ITER en, double stop_crit = 0.00001)
61  {
62  using datatype = typename std::iterator_traits<ITER>::value_type;
63  using dectype = DecimalType<datatype>;
64  if (beg == en)
65  throw ExceptionDomain("Empty range");
66  // set prototypes as min & max
67  datatype p1 = *beg;
68  datatype p2 = *beg;
69  for (ITER it = beg; it != en; ++it)
70  {
71  if (*it < p1) p1 = *it;
72  if (!(*it < p2)) p2 = *it;
73  }
74  // run 2 means
75  bool cont = true;
76  while (cont)
77  {
78  dectype s1 = 0, s2 = 0;
79  size_t n1 = 0, n2 = 0;
80  for (ITER it = beg; it != en; ++it)
81  {
82  if (Abs(*it - p1) < Abs(*it - p2))
83  {
84  s1 += *it;
85  n1 += 1;
86  }
87  else
88  {
89  s2 += *it;
90  n2 += 1;
91  }
92  }
93  if (n1)
94  s1 = datatype(s1 * (1.0 / double(n1)));
95  if (n2)
96  s2 = datatype(s2 * (1.0 / double(n2)));
97  cont = double(Abs(dectype(p1) - s1) + Abs(dectype(p2) - s2)) > stop_crit;
98  p1 = datatype(s1);
99  p2 = datatype(s2);
100  }
101  return std::make_pair(p1, p2);
102  }
103 
104  /****************************************************************************/
121  template<typename ITER>
122  std::pair<typename std::iterator_traits<ITER>::value_type, typename std::iterator_traits<ITER>::value_type>
123  TwoMeans(ITER beg, ITER en, typename std::iterator_traits<ITER>::value_type p1, typename std::iterator_traits<ITER>::value_type p2, double stop_crit = 0.00001)
124  noexcept(std::is_nothrow_constructible<typename std::iterator_traits<ITER>::value_type>::value
125  && std::is_nothrow_copy_assignable<typename std::iterator_traits<ITER>::value_type>::value)
126  {
127  using datatype = typename std::iterator_traits<ITER>::value_type;
128  using dectype = DecimalType<datatype>;
129  if (beg == en)
130  throw ExceptionDomain("Empty range");
131  // run 2 means
132  bool cont = true;
133  while (cont)
134  {
135  dectype s1 = 0, s2 = 0;
136  size_t n1 = 0, n2 = 0;
137  for (ITER it = beg; it != en; ++it)
138  {
139  if (Abs(*it - p1) < Abs(*it - p2))
140  {
141  s1 += *it;
142  n1 += 1;
143  }
144  else
145  {
146  s2 += *it;
147  n2 += 1;
148  }
149  }
150  if (n1)
151  s1 = datatype(s1 / double(n1));
152  if (n2)
153  s2 = datatype(s2 / double(n2));
154  cont = double(Abs(dectype(p1) - s1) + Abs(dectype(p2) - s2)) > stop_crit;
155  p1 = datatype(s1);
156  p2 = datatype(s2);
157  }
158  return std::make_pair(p1, p2);
159  }
160 }
161 
162 #endif
163 
std::pair< typename std::iterator_traits< ITER >::value_type, typename std::iterator_traits< ITER >::value_type > TwoMeans(ITER beg, ITER en, double stop_crit=0.00001)
2-means clustering algorithm for scalar data
Definition: CRN2Means.h:60
A generic domain error.
Definition: CRNException.h:83
typename TypeInfo< T >::DecimalType DecimalType
Definition: CRNType.h:187
void Abs(Image< T > &img, typename std::enable_if< std::is_arithmetic< T >::value >::type *dummy=nullptr) noexcept
Replaces each pixel by its absolute value.
Definition: CRNImageGray.h:47