tesseract  3.05.02
cluster.cpp
Go to the documentation of this file.
1 /******************************************************************************
2  ** Filename: cluster.c
3  ** Purpose: Routines for clustering points in N-D space
4  ** Author: Dan Johnson
5  ** History: 5/29/89, DSJ, Created.
6  **
7  ** (c) Copyright Hewlett-Packard Company, 1988.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  ******************************************************************************/
18 #include "const.h"
19 #include "cluster.h"
20 #include "emalloc.h"
21 #include "genericheap.h"
22 #include "helpers.h"
23 #include "kdpair.h"
24 #include "matrix.h"
25 #include "tprintf.h"
26 #include "danerror.h"
27 #include "freelist.h"
28 #include <math.h>
29 
30 #define HOTELLING 1 // If true use Hotelling's test to decide where to split.
31 #define FTABLE_X 10 // Size of FTable.
32 #define FTABLE_Y 100 // Size of FTable.
33 
34 // Table of values approximating the cumulative F-distribution for a confidence of 1%.
35 const double FTable[FTABLE_Y][FTABLE_X] = {
36  {4052.19, 4999.52, 5403.34, 5624.62, 5763.65, 5858.97, 5928.33, 5981.10, 6022.50, 6055.85,},
37  {98.502, 99.000, 99.166, 99.249, 99.300, 99.333, 99.356, 99.374, 99.388, 99.399,},
38  {34.116, 30.816, 29.457, 28.710, 28.237, 27.911, 27.672, 27.489, 27.345, 27.229,},
39  {21.198, 18.000, 16.694, 15.977, 15.522, 15.207, 14.976, 14.799, 14.659, 14.546,},
40  {16.258, 13.274, 12.060, 11.392, 10.967, 10.672, 10.456, 10.289, 10.158, 10.051,},
41  {13.745, 10.925, 9.780, 9.148, 8.746, 8.466, 8.260, 8.102, 7.976, 7.874,},
42  {12.246, 9.547, 8.451, 7.847, 7.460, 7.191, 6.993, 6.840, 6.719, 6.620,},
43  {11.259, 8.649, 7.591, 7.006, 6.632, 6.371, 6.178, 6.029, 5.911, 5.814,},
44  {10.561, 8.022, 6.992, 6.422, 6.057, 5.802, 5.613, 5.467, 5.351, 5.257,},
45  {10.044, 7.559, 6.552, 5.994, 5.636, 5.386, 5.200, 5.057, 4.942, 4.849,},
46  { 9.646, 7.206, 6.217, 5.668, 5.316, 5.069, 4.886, 4.744, 4.632, 4.539,},
47  { 9.330, 6.927, 5.953, 5.412, 5.064, 4.821, 4.640, 4.499, 4.388, 4.296,},
48  { 9.074, 6.701, 5.739, 5.205, 4.862, 4.620, 4.441, 4.302, 4.191, 4.100,},
49  { 8.862, 6.515, 5.564, 5.035, 4.695, 4.456, 4.278, 4.140, 4.030, 3.939,},
50  { 8.683, 6.359, 5.417, 4.893, 4.556, 4.318, 4.142, 4.004, 3.895, 3.805,},
51  { 8.531, 6.226, 5.292, 4.773, 4.437, 4.202, 4.026, 3.890, 3.780, 3.691,},
52  { 8.400, 6.112, 5.185, 4.669, 4.336, 4.102, 3.927, 3.791, 3.682, 3.593,},
53  { 8.285, 6.013, 5.092, 4.579, 4.248, 4.015, 3.841, 3.705, 3.597, 3.508,},
54  { 8.185, 5.926, 5.010, 4.500, 4.171, 3.939, 3.765, 3.631, 3.523, 3.434,},
55  { 8.096, 5.849, 4.938, 4.431, 4.103, 3.871, 3.699, 3.564, 3.457, 3.368,},
56  { 8.017, 5.780, 4.874, 4.369, 4.042, 3.812, 3.640, 3.506, 3.398, 3.310,},
57  { 7.945, 5.719, 4.817, 4.313, 3.988, 3.758, 3.587, 3.453, 3.346, 3.258,},
58  { 7.881, 5.664, 4.765, 4.264, 3.939, 3.710, 3.539, 3.406, 3.299, 3.211,},
59  { 7.823, 5.614, 4.718, 4.218, 3.895, 3.667, 3.496, 3.363, 3.256, 3.168,},
60  { 7.770, 5.568, 4.675, 4.177, 3.855, 3.627, 3.457, 3.324, 3.217, 3.129,},
61  { 7.721, 5.526, 4.637, 4.140, 3.818, 3.591, 3.421, 3.288, 3.182, 3.094,},
62  { 7.677, 5.488, 4.601, 4.106, 3.785, 3.558, 3.388, 3.256, 3.149, 3.062,},
63  { 7.636, 5.453, 4.568, 4.074, 3.754, 3.528, 3.358, 3.226, 3.120, 3.032,},
64  { 7.598, 5.420, 4.538, 4.045, 3.725, 3.499, 3.330, 3.198, 3.092, 3.005,},
65  { 7.562, 5.390, 4.510, 4.018, 3.699, 3.473, 3.305, 3.173, 3.067, 2.979,},
66  { 7.530, 5.362, 4.484, 3.993, 3.675, 3.449, 3.281, 3.149, 3.043, 2.955,},
67  { 7.499, 5.336, 4.459, 3.969, 3.652, 3.427, 3.258, 3.127, 3.021, 2.934,},
68  { 7.471, 5.312, 4.437, 3.948, 3.630, 3.406, 3.238, 3.106, 3.000, 2.913,},
69  { 7.444, 5.289, 4.416, 3.927, 3.611, 3.386, 3.218, 3.087, 2.981, 2.894,},
70  { 7.419, 5.268, 4.396, 3.908, 3.592, 3.368, 3.200, 3.069, 2.963, 2.876,},
71  { 7.396, 5.248, 4.377, 3.890, 3.574, 3.351, 3.183, 3.052, 2.946, 2.859,},
72  { 7.373, 5.229, 4.360, 3.873, 3.558, 3.334, 3.167, 3.036, 2.930, 2.843,},
73  { 7.353, 5.211, 4.343, 3.858, 3.542, 3.319, 3.152, 3.021, 2.915, 2.828,},
74  { 7.333, 5.194, 4.327, 3.843, 3.528, 3.305, 3.137, 3.006, 2.901, 2.814,},
75  { 7.314, 5.179, 4.313, 3.828, 3.514, 3.291, 3.124, 2.993, 2.888, 2.801,},
76  { 7.296, 5.163, 4.299, 3.815, 3.501, 3.278, 3.111, 2.980, 2.875, 2.788,},
77  { 7.280, 5.149, 4.285, 3.802, 3.488, 3.266, 3.099, 2.968, 2.863, 2.776,},
78  { 7.264, 5.136, 4.273, 3.790, 3.476, 3.254, 3.087, 2.957, 2.851, 2.764,},
79  { 7.248, 5.123, 4.261, 3.778, 3.465, 3.243, 3.076, 2.946, 2.840, 2.754,},
80  { 7.234, 5.110, 4.249, 3.767, 3.454, 3.232, 3.066, 2.935, 2.830, 2.743,},
81  { 7.220, 5.099, 4.238, 3.757, 3.444, 3.222, 3.056, 2.925, 2.820, 2.733,},
82  { 7.207, 5.087, 4.228, 3.747, 3.434, 3.213, 3.046, 2.916, 2.811, 2.724,},
83  { 7.194, 5.077, 4.218, 3.737, 3.425, 3.204, 3.037, 2.907, 2.802, 2.715,},
84  { 7.182, 5.066, 4.208, 3.728, 3.416, 3.195, 3.028, 2.898, 2.793, 2.706,},
85  { 7.171, 5.057, 4.199, 3.720, 3.408, 3.186, 3.020, 2.890, 2.785, 2.698,},
86  { 7.159, 5.047, 4.191, 3.711, 3.400, 3.178, 3.012, 2.882, 2.777, 2.690,},
87  { 7.149, 5.038, 4.182, 3.703, 3.392, 3.171, 3.005, 2.874, 2.769, 2.683,},
88  { 7.139, 5.030, 4.174, 3.695, 3.384, 3.163, 2.997, 2.867, 2.762, 2.675,},
89  { 7.129, 5.021, 4.167, 3.688, 3.377, 3.156, 2.990, 2.860, 2.755, 2.668,},
90  { 7.119, 5.013, 4.159, 3.681, 3.370, 3.149, 2.983, 2.853, 2.748, 2.662,},
91  { 7.110, 5.006, 4.152, 3.674, 3.363, 3.143, 2.977, 2.847, 2.742, 2.655,},
92  { 7.102, 4.998, 4.145, 3.667, 3.357, 3.136, 2.971, 2.841, 2.736, 2.649,},
93  { 7.093, 4.991, 4.138, 3.661, 3.351, 3.130, 2.965, 2.835, 2.730, 2.643,},
94  { 7.085, 4.984, 4.132, 3.655, 3.345, 3.124, 2.959, 2.829, 2.724, 2.637,},
95  { 7.077, 4.977, 4.126, 3.649, 3.339, 3.119, 2.953, 2.823, 2.718, 2.632,},
96  { 7.070, 4.971, 4.120, 3.643, 3.333, 3.113, 2.948, 2.818, 2.713, 2.626,},
97  { 7.062, 4.965, 4.114, 3.638, 3.328, 3.108, 2.942, 2.813, 2.708, 2.621,},
98  { 7.055, 4.959, 4.109, 3.632, 3.323, 3.103, 2.937, 2.808, 2.703, 2.616,},
99  { 7.048, 4.953, 4.103, 3.627, 3.318, 3.098, 2.932, 2.803, 2.698, 2.611,},
100  { 7.042, 4.947, 4.098, 3.622, 3.313, 3.093, 2.928, 2.798, 2.693, 2.607,},
101  { 7.035, 4.942, 4.093, 3.618, 3.308, 3.088, 2.923, 2.793, 2.689, 2.602,},
102  { 7.029, 4.937, 4.088, 3.613, 3.304, 3.084, 2.919, 2.789, 2.684, 2.598,},
103  { 7.023, 4.932, 4.083, 3.608, 3.299, 3.080, 2.914, 2.785, 2.680, 2.593,},
104  { 7.017, 4.927, 4.079, 3.604, 3.295, 3.075, 2.910, 2.781, 2.676, 2.589,},
105  { 7.011, 4.922, 4.074, 3.600, 3.291, 3.071, 2.906, 2.777, 2.672, 2.585,},
106  { 7.006, 4.917, 4.070, 3.596, 3.287, 3.067, 2.902, 2.773, 2.668, 2.581,},
107  { 7.001, 4.913, 4.066, 3.591, 3.283, 3.063, 2.898, 2.769, 2.664, 2.578,},
108  { 6.995, 4.908, 4.062, 3.588, 3.279, 3.060, 2.895, 2.765, 2.660, 2.574,},
109  { 6.990, 4.904, 4.058, 3.584, 3.275, 3.056, 2.891, 2.762, 2.657, 2.570,},
110  { 6.985, 4.900, 4.054, 3.580, 3.272, 3.052, 2.887, 2.758, 2.653, 2.567,},
111  { 6.981, 4.896, 4.050, 3.577, 3.268, 3.049, 2.884, 2.755, 2.650, 2.563,},
112  { 6.976, 4.892, 4.047, 3.573, 3.265, 3.046, 2.881, 2.751, 2.647, 2.560,},
113  { 6.971, 4.888, 4.043, 3.570, 3.261, 3.042, 2.877, 2.748, 2.644, 2.557,},
114  { 6.967, 4.884, 4.040, 3.566, 3.258, 3.039, 2.874, 2.745, 2.640, 2.554,},
115  { 6.963, 4.881, 4.036, 3.563, 3.255, 3.036, 2.871, 2.742, 2.637, 2.551,},
116  { 6.958, 4.877, 4.033, 3.560, 3.252, 3.033, 2.868, 2.739, 2.634, 2.548,},
117  { 6.954, 4.874, 4.030, 3.557, 3.249, 3.030, 2.865, 2.736, 2.632, 2.545,},
118  { 6.950, 4.870, 4.027, 3.554, 3.246, 3.027, 2.863, 2.733, 2.629, 2.542,},
119  { 6.947, 4.867, 4.024, 3.551, 3.243, 3.025, 2.860, 2.731, 2.626, 2.539,},
120  { 6.943, 4.864, 4.021, 3.548, 3.240, 3.022, 2.857, 2.728, 2.623, 2.537,},
121  { 6.939, 4.861, 4.018, 3.545, 3.238, 3.019, 2.854, 2.725, 2.621, 2.534,},
122  { 6.935, 4.858, 4.015, 3.543, 3.235, 3.017, 2.852, 2.723, 2.618, 2.532,},
123  { 6.932, 4.855, 4.012, 3.540, 3.233, 3.014, 2.849, 2.720, 2.616, 2.529,},
124  { 6.928, 4.852, 4.010, 3.538, 3.230, 3.012, 2.847, 2.718, 2.613, 2.527,},
125  { 6.925, 4.849, 4.007, 3.535, 3.228, 3.009, 2.845, 2.715, 2.611, 2.524,},
126  { 6.922, 4.846, 4.004, 3.533, 3.225, 3.007, 2.842, 2.713, 2.609, 2.522,},
127  { 6.919, 4.844, 4.002, 3.530, 3.223, 3.004, 2.840, 2.711, 2.606, 2.520,},
128  { 6.915, 4.841, 3.999, 3.528, 3.221, 3.002, 2.838, 2.709, 2.604, 2.518,},
129  { 6.912, 4.838, 3.997, 3.525, 3.218, 3.000, 2.835, 2.706, 2.602, 2.515,},
130  { 6.909, 4.836, 3.995, 3.523, 3.216, 2.998, 2.833, 2.704, 2.600, 2.513,},
131  { 6.906, 4.833, 3.992, 3.521, 3.214, 2.996, 2.831, 2.702, 2.598, 2.511,},
132  { 6.904, 4.831, 3.990, 3.519, 3.212, 2.994, 2.829, 2.700, 2.596, 2.509,},
133  { 6.901, 4.829, 3.988, 3.517, 3.210, 2.992, 2.827, 2.698, 2.594, 2.507,},
134  { 6.898, 4.826, 3.986, 3.515, 3.208, 2.990, 2.825, 2.696, 2.592, 2.505,},
135  { 6.895, 4.824, 3.984, 3.513, 3.206, 2.988, 2.823, 2.694, 2.590, 2.503}
136 };
137 
142 #define MINVARIANCE 0.0004
143 
150 #define MINSAMPLESPERBUCKET 5
151 #define MINSAMPLES (MINBUCKETS * MINSAMPLESPERBUCKET)
152 #define MINSAMPLESNEEDED 1
153 
160 #define BUCKETTABLESIZE 1024
161 #define NORMALEXTENT 3.0
162 
163 struct TEMPCLUSTER {
164  CLUSTER *Cluster;
165  CLUSTER *Neighbor;
166 };
167 
168 typedef tesseract::KDPairInc<float, TEMPCLUSTER*> ClusterPair;
169 typedef tesseract::GenericHeap<ClusterPair> ClusterHeap;
170 
171 struct STATISTICS {
172  FLOAT32 AvgVariance;
173  FLOAT32 *CoVariance;
174  FLOAT32 *Min; // largest negative distance from the mean
175  FLOAT32 *Max; // largest positive distance from the mean
176 };
177 
178 struct BUCKETS {
179  DISTRIBUTION Distribution; // distribution being tested for
180  uinT32 SampleCount; // # of samples in histogram
181  FLOAT64 Confidence; // confidence level of test
182  FLOAT64 ChiSquared; // test threshold
183  uinT16 NumberOfBuckets; // number of cells in histogram
184  uinT16 Bucket[BUCKETTABLESIZE];// mapping to histogram buckets
185  uinT32 *Count; // frequency of occurrence histogram
186  FLOAT32 *ExpectedCount; // expected histogram
187 };
188 
189 struct CHISTRUCT{
190  uinT16 DegreesOfFreedom;
191  FLOAT64 Alpha;
192  FLOAT64 ChiSquared;
193 };
194 
195 // For use with KDWalk / MakePotentialClusters
196 struct ClusteringContext {
197  ClusterHeap *heap; // heap used to hold temp clusters, "best" on top
198  TEMPCLUSTER *candidates; // array of potential clusters
199  KDTREE *tree; // kd-tree to be searched for neighbors
200  inT32 next; // next candidate to be used
201 };
202 
203 typedef FLOAT64 (*DENSITYFUNC) (inT32);
204 typedef FLOAT64 (*SOLVEFUNC) (CHISTRUCT *, double);
205 
206 #define Odd(N) ((N)%2)
207 #define Mirror(N,R) ((R) - (N) - 1)
208 #define Abs(N) ( ( (N) < 0 ) ? ( -(N) ) : (N) )
209 
210 //--------------Global Data Definitions and Declarations----------------------
218 #define SqrtOf2Pi 2.506628275
219 static const FLOAT64 kNormalStdDev = BUCKETTABLESIZE / (2.0 * NORMALEXTENT);
220 static const FLOAT64 kNormalVariance =
221  (BUCKETTABLESIZE * BUCKETTABLESIZE) / (4.0 * NORMALEXTENT * NORMALEXTENT);
222 static const FLOAT64 kNormalMagnitude =
223  (2.0 * NORMALEXTENT) / (SqrtOf2Pi * BUCKETTABLESIZE);
224 static const FLOAT64 kNormalMean = BUCKETTABLESIZE / 2;
225 
228 #define LOOKUPTABLESIZE 8
229 #define MAXDEGREESOFFREEDOM MAXBUCKETS
230 
231 static const uinT32 kCountTable[LOOKUPTABLESIZE] = {
232  MINSAMPLES, 200, 400, 600, 800, 1000, 1500, 2000
233 }; // number of samples
234 
235 static const uinT16 kBucketsTable[LOOKUPTABLESIZE] = {
236  MINBUCKETS, 16, 20, 24, 27, 30, 35, MAXBUCKETS
237 }; // number of buckets
238 
239 /*-------------------------------------------------------------------------
240  Private Function Prototypes
241 --------------------------------------------------------------------------*/
242 void CreateClusterTree(CLUSTERER *Clusterer);
243 
244 void MakePotentialClusters(ClusteringContext *context, CLUSTER *Cluster,
245  inT32 Level);
246 
247 CLUSTER *FindNearestNeighbor(KDTREE *Tree,
248  CLUSTER *Cluster,
249  FLOAT32 *Distance);
250 
251 CLUSTER *MakeNewCluster(CLUSTERER *Clusterer, TEMPCLUSTER *TempCluster);
252 
253 inT32 MergeClusters (inT16 N,
254 register PARAM_DESC ParamDesc[],
255 register inT32 n1,
256 register inT32 n2,
257 register FLOAT32 m[],
258 register FLOAT32 m1[], register FLOAT32 m2[]);
259 
260 void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config);
261 
262 PROTOTYPE *MakePrototype(CLUSTERER *Clusterer,
263  CLUSTERCONFIG *Config,
264  CLUSTER *Cluster);
265 
266 PROTOTYPE *MakeDegenerateProto(uinT16 N,
267  CLUSTER *Cluster,
268  STATISTICS *Statistics,
269  PROTOSTYLE Style,
270  inT32 MinSamples);
271 
272 PROTOTYPE *TestEllipticalProto(CLUSTERER *Clusterer,
273  CLUSTERCONFIG *Config,
274  CLUSTER *Cluster,
275  STATISTICS *Statistics);
276 
277 PROTOTYPE *MakeSphericalProto(CLUSTERER *Clusterer,
278  CLUSTER *Cluster,
279  STATISTICS *Statistics,
280  BUCKETS *Buckets);
281 
282 PROTOTYPE *MakeEllipticalProto(CLUSTERER *Clusterer,
283  CLUSTER *Cluster,
284  STATISTICS *Statistics,
285  BUCKETS *Buckets);
286 
287 PROTOTYPE *MakeMixedProto(CLUSTERER *Clusterer,
288  CLUSTER *Cluster,
289  STATISTICS *Statistics,
290  BUCKETS *NormalBuckets,
291  FLOAT64 Confidence);
292 
293 void MakeDimRandom(uinT16 i, PROTOTYPE *Proto, PARAM_DESC *ParamDesc);
294 
295 void MakeDimUniform(uinT16 i, PROTOTYPE *Proto, STATISTICS *Statistics);
296 
297 STATISTICS *ComputeStatistics (inT16 N,
298 PARAM_DESC ParamDesc[], CLUSTER * Cluster);
299 
300 PROTOTYPE *NewSphericalProto(uinT16 N,
301  CLUSTER *Cluster,
302  STATISTICS *Statistics);
303 
304 PROTOTYPE *NewEllipticalProto(inT16 N,
305  CLUSTER *Cluster,
306  STATISTICS *Statistics);
307 
308 PROTOTYPE *NewMixedProto(inT16 N, CLUSTER *Cluster, STATISTICS *Statistics);
309 
310 PROTOTYPE *NewSimpleProto(inT16 N, CLUSTER *Cluster);
311 
312 BOOL8 Independent (PARAM_DESC ParamDesc[],
313 inT16 N, FLOAT32 * CoVariance, FLOAT32 Independence);
314 
315 BUCKETS *GetBuckets(CLUSTERER* clusterer,
316  DISTRIBUTION Distribution,
317  uinT32 SampleCount,
318  FLOAT64 Confidence);
319 
320 BUCKETS *MakeBuckets(DISTRIBUTION Distribution,
321  uinT32 SampleCount,
322  FLOAT64 Confidence);
323 
324 uinT16 OptimumNumberOfBuckets(uinT32 SampleCount);
325 
326 FLOAT64 ComputeChiSquared(uinT16 DegreesOfFreedom, FLOAT64 Alpha);
327 
328 FLOAT64 NormalDensity(inT32 x);
329 
330 FLOAT64 UniformDensity(inT32 x);
331 
332 FLOAT64 Integral(FLOAT64 f1, FLOAT64 f2, FLOAT64 Dx);
333 
334 void FillBuckets(BUCKETS *Buckets,
335  CLUSTER *Cluster,
336  uinT16 Dim,
337  PARAM_DESC *ParamDesc,
338  FLOAT32 Mean,
339  FLOAT32 StdDev);
340 
341 uinT16 NormalBucket(PARAM_DESC *ParamDesc,
342  FLOAT32 x,
343  FLOAT32 Mean,
344  FLOAT32 StdDev);
345 
346 uinT16 UniformBucket(PARAM_DESC *ParamDesc,
347  FLOAT32 x,
348  FLOAT32 Mean,
349  FLOAT32 StdDev);
350 
351 BOOL8 DistributionOK(BUCKETS *Buckets);
352 
353 void FreeStatistics(STATISTICS *Statistics);
354 
355 void FreeBuckets(BUCKETS *Buckets);
356 
357 void FreeCluster(CLUSTER *Cluster);
358 
359 uinT16 DegreesOfFreedom(DISTRIBUTION Distribution, uinT16 HistogramBuckets);
360 
361 int NumBucketsMatch(void *arg1, // BUCKETS *Histogram,
362  void *arg2); // uinT16 *DesiredNumberOfBuckets);
363 
364 int ListEntryMatch(void *arg1, void *arg2);
365 
366 void AdjustBuckets(BUCKETS *Buckets, uinT32 NewSampleCount);
367 
368 void InitBuckets(BUCKETS *Buckets);
369 
370 int AlphaMatch(void *arg1, // CHISTRUCT *ChiStruct,
371  void *arg2); // CHISTRUCT *SearchKey);
372 
373 CHISTRUCT *NewChiStruct(uinT16 DegreesOfFreedom, FLOAT64 Alpha);
374 
375 FLOAT64 Solve(SOLVEFUNC Function,
376  void *FunctionParams,
377  FLOAT64 InitialGuess,
378  FLOAT64 Accuracy);
379 
380 FLOAT64 ChiArea(CHISTRUCT *ChiParams, FLOAT64 x);
381 
382 BOOL8 MultipleCharSamples(CLUSTERER *Clusterer,
383  CLUSTER *Cluster,
384  FLOAT32 MaxIllegal);
385 
386 double InvertMatrix(const float* input, int size, float* inv);
387 
388 //--------------------------Public Code--------------------------------------
399 CLUSTERER *
400 MakeClusterer (inT16 SampleSize, const PARAM_DESC ParamDesc[]) {
401  CLUSTERER *Clusterer;
402  int i;
403 
404  // allocate main clusterer data structure and init simple fields
405  Clusterer = (CLUSTERER *) Emalloc (sizeof (CLUSTERER));
406  Clusterer->SampleSize = SampleSize;
407  Clusterer->NumberOfSamples = 0;
408  Clusterer->NumChar = 0;
409 
410  // init fields which will not be used initially
411  Clusterer->Root = NULL;
412  Clusterer->ProtoList = NIL_LIST;
413 
414  // maintain a copy of param descriptors in the clusterer data structure
415  Clusterer->ParamDesc =
416  (PARAM_DESC *) Emalloc (SampleSize * sizeof (PARAM_DESC));
417  for (i = 0; i < SampleSize; i++) {
418  Clusterer->ParamDesc[i].Circular = ParamDesc[i].Circular;
419  Clusterer->ParamDesc[i].NonEssential = ParamDesc[i].NonEssential;
420  Clusterer->ParamDesc[i].Min = ParamDesc[i].Min;
421  Clusterer->ParamDesc[i].Max = ParamDesc[i].Max;
422  Clusterer->ParamDesc[i].Range = ParamDesc[i].Max - ParamDesc[i].Min;
423  Clusterer->ParamDesc[i].HalfRange = Clusterer->ParamDesc[i].Range / 2;
424  Clusterer->ParamDesc[i].MidRange =
425  (ParamDesc[i].Max + ParamDesc[i].Min) / 2;
426  }
427 
428  // allocate a kd tree to hold the samples
429  Clusterer->KDTree = MakeKDTree (SampleSize, ParamDesc);
430 
431  // Initialize cache of histogram buckets to minimize recomputing them.
432  for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
433  for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
434  Clusterer->bucket_cache[d][c] = NULL;
435  }
436 
437  return Clusterer;
438 } // MakeClusterer
439 
456 SAMPLE* MakeSample(CLUSTERER * Clusterer, const FLOAT32* Feature,
457  inT32 CharID) {
458  SAMPLE *Sample;
459  int i;
460 
461  // see if the samples have already been clustered - if so trap an error
462  if (Clusterer->Root != NULL)
463  DoError (ALREADYCLUSTERED,
464  "Can't add samples after they have been clustered");
465 
466  // allocate the new sample and initialize it
467  Sample = (SAMPLE *) Emalloc (sizeof (SAMPLE) +
468  (Clusterer->SampleSize -
469  1) * sizeof (FLOAT32));
470  Sample->Clustered = FALSE;
471  Sample->Prototype = FALSE;
472  Sample->SampleCount = 1;
473  Sample->Left = NULL;
474  Sample->Right = NULL;
475  Sample->CharID = CharID;
476 
477  for (i = 0; i < Clusterer->SampleSize; i++)
478  Sample->Mean[i] = Feature[i];
479 
480  // add the sample to the KD tree - keep track of the total # of samples
481  Clusterer->NumberOfSamples++;
482  KDStore (Clusterer->KDTree, Sample->Mean, (char *) Sample);
483  if (CharID >= Clusterer->NumChar)
484  Clusterer->NumChar = CharID + 1;
485 
486  // execute hook for monitoring clustering operation
487  // (*SampleCreationHook)( Sample );
488 
489  return (Sample);
490 } // MakeSample
491 
513 LIST ClusterSamples(CLUSTERER *Clusterer, CLUSTERCONFIG *Config) {
514  //only create cluster tree if samples have never been clustered before
515  if (Clusterer->Root == NULL)
516  CreateClusterTree(Clusterer);
517 
518  //deallocate the old prototype list if one exists
519  FreeProtoList (&Clusterer->ProtoList);
520  Clusterer->ProtoList = NIL_LIST;
521 
522  //compute prototypes starting at the root node in the tree
523  ComputePrototypes(Clusterer, Config);
524  // We don't need the cluster pointers in the protos any more, so null them
525  // out, which makes it safe to delete the clusterer.
526  LIST proto_list = Clusterer->ProtoList;
527  iterate(proto_list) {
528  PROTOTYPE *proto = reinterpret_cast<PROTOTYPE *>(first_node(proto_list));
529  proto->Cluster = NULL;
530  }
531  return Clusterer->ProtoList;
532 } // ClusterSamples
533 
547 void FreeClusterer(CLUSTERER *Clusterer) {
548  if (Clusterer != NULL) {
549  memfree (Clusterer->ParamDesc);
550  if (Clusterer->KDTree != NULL)
551  FreeKDTree (Clusterer->KDTree);
552  if (Clusterer->Root != NULL)
553  FreeCluster (Clusterer->Root);
554  // Free up all used buckets structures.
555  for (int d = 0; d < DISTRIBUTION_COUNT; ++d) {
556  for (int c = 0; c < MAXBUCKETS + 1 - MINBUCKETS; ++c)
557  if (Clusterer->bucket_cache[d][c] != NULL)
558  FreeBuckets(Clusterer->bucket_cache[d][c]);
559  }
560 
561  memfree(Clusterer);
562  }
563 } // FreeClusterer
564 
574 void FreeProtoList(LIST *ProtoList) {
575  destroy_nodes(*ProtoList, FreePrototype);
576 } // FreeProtoList
577 
588 void FreePrototype(void *arg) { //PROTOTYPE *Prototype)
589  PROTOTYPE *Prototype = (PROTOTYPE *) arg;
590 
591  // unmark the corresponding cluster (if there is one
592  if (Prototype->Cluster != NULL)
593  Prototype->Cluster->Prototype = FALSE;
594 
595  // deallocate the prototype statistics and then the prototype itself
596  if (Prototype->Distrib != NULL)
597  memfree (Prototype->Distrib);
598  if (Prototype->Mean != NULL)
599  memfree (Prototype->Mean);
600  if (Prototype->Style != spherical) {
601  if (Prototype->Variance.Elliptical != NULL)
602  memfree (Prototype->Variance.Elliptical);
603  if (Prototype->Magnitude.Elliptical != NULL)
604  memfree (Prototype->Magnitude.Elliptical);
605  if (Prototype->Weight.Elliptical != NULL)
606  memfree (Prototype->Weight.Elliptical);
607  }
608  memfree(Prototype);
609 } // FreePrototype
610 
626 CLUSTER *NextSample(LIST *SearchState) {
627  CLUSTER *Cluster;
628 
629  if (*SearchState == NIL_LIST)
630  return (NULL);
631  Cluster = (CLUSTER *) first_node (*SearchState);
632  *SearchState = pop (*SearchState);
633  while (TRUE) {
634  if (Cluster->Left == NULL)
635  return (Cluster);
636  *SearchState = push (*SearchState, Cluster->Right);
637  Cluster = Cluster->Left;
638  }
639 } // NextSample
640 
650 FLOAT32 Mean(PROTOTYPE *Proto, uinT16 Dimension) {
651  return (Proto->Mean[Dimension]);
652 } // Mean
653 
663 FLOAT32 StandardDeviation(PROTOTYPE *Proto, uinT16 Dimension) {
664  switch (Proto->Style) {
665  case spherical:
666  return ((FLOAT32) sqrt ((double) Proto->Variance.Spherical));
667  case elliptical:
668  return ((FLOAT32)
669  sqrt ((double) Proto->Variance.Elliptical[Dimension]));
670  case mixed:
671  switch (Proto->Distrib[Dimension]) {
672  case normal:
673  return ((FLOAT32)
674  sqrt ((double) Proto->Variance.Elliptical[Dimension]));
675  case uniform:
676  case D_random:
677  return (Proto->Variance.Elliptical[Dimension]);
678  case DISTRIBUTION_COUNT:
679  ASSERT_HOST(!"Distribution count not allowed!");
680  }
681  }
682  return 0.0f;
683 } // StandardDeviation
684 
685 
686 /*---------------------------------------------------------------------------
687  Private Code
688 ----------------------------------------------------------------------------*/
704 void CreateClusterTree(CLUSTERER *Clusterer) {
705  ClusteringContext context;
706  ClusterPair HeapEntry;
707  TEMPCLUSTER *PotentialCluster;
708 
709  // each sample and its nearest neighbor form a "potential" cluster
710  // save these in a heap with the "best" potential clusters on top
711  context.tree = Clusterer->KDTree;
712  context.candidates = (TEMPCLUSTER *)
713  Emalloc(Clusterer->NumberOfSamples * sizeof(TEMPCLUSTER));
714  context.next = 0;
715  context.heap = new ClusterHeap(Clusterer->NumberOfSamples);
716  KDWalk(context.tree, (void_proc)MakePotentialClusters, &context);
717 
718  // form potential clusters into actual clusters - always do "best" first
719  while (context.heap->Pop(&HeapEntry)) {
720  PotentialCluster = HeapEntry.data;
721 
722  // if main cluster of potential cluster is already in another cluster
723  // then we don't need to worry about it
724  if (PotentialCluster->Cluster->Clustered) {
725  continue;
726  }
727 
728  // if main cluster is not yet clustered, but its nearest neighbor is
729  // then we must find a new nearest neighbor
730  else if (PotentialCluster->Neighbor->Clustered) {
731  PotentialCluster->Neighbor =
732  FindNearestNeighbor(context.tree, PotentialCluster->Cluster,
733  &HeapEntry.key);
734  if (PotentialCluster->Neighbor != NULL) {
735  context.heap->Push(&HeapEntry);
736  }
737  }
738 
739  // if neither cluster is already clustered, form permanent cluster
740  else {
741  PotentialCluster->Cluster =
742  MakeNewCluster(Clusterer, PotentialCluster);
743  PotentialCluster->Neighbor =
744  FindNearestNeighbor(context.tree, PotentialCluster->Cluster,
745  &HeapEntry.key);
746  if (PotentialCluster->Neighbor != NULL) {
747  context.heap->Push(&HeapEntry);
748  }
749  }
750  }
751 
752  // the root node in the cluster tree is now the only node in the kd-tree
753  Clusterer->Root = (CLUSTER *) RootOf(Clusterer->KDTree);
754 
755  // free up the memory used by the K-D tree, heap, and temp clusters
756  FreeKDTree(context.tree);
757  Clusterer->KDTree = NULL;
758  delete context.heap;
759  memfree(context.candidates);
760 } // CreateClusterTree
761 
771 void MakePotentialClusters(ClusteringContext *context,
772  CLUSTER *Cluster, inT32 Level) {
773  ClusterPair HeapEntry;
774  int next = context->next;
775  context->candidates[next].Cluster = Cluster;
776  HeapEntry.data = &(context->candidates[next]);
777  context->candidates[next].Neighbor =
778  FindNearestNeighbor(context->tree,
779  context->candidates[next].Cluster,
780  &HeapEntry.key);
781  if (context->candidates[next].Neighbor != NULL) {
782  context->heap->Push(&HeapEntry);
783  context->next++;
784  }
785 } // MakePotentialClusters
786 
803 CLUSTER *
804 FindNearestNeighbor(KDTREE * Tree, CLUSTER * Cluster, FLOAT32 * Distance)
805 #define MAXNEIGHBORS 2
806 #define MAXDISTANCE MAX_FLOAT32
807 {
808  CLUSTER *Neighbor[MAXNEIGHBORS];
809  FLOAT32 Dist[MAXNEIGHBORS];
810  int NumberOfNeighbors;
811  inT32 i;
812  CLUSTER *BestNeighbor;
813 
814  // find the 2 nearest neighbors of the cluster
815  KDNearestNeighborSearch(Tree, Cluster->Mean, MAXNEIGHBORS, MAXDISTANCE,
816  &NumberOfNeighbors, (void **)Neighbor, Dist);
817 
818  // search for the nearest neighbor that is not the cluster itself
819  *Distance = MAXDISTANCE;
820  BestNeighbor = NULL;
821  for (i = 0; i < NumberOfNeighbors; i++) {
822  if ((Dist[i] < *Distance) && (Neighbor[i] != Cluster)) {
823  *Distance = Dist[i];
824  BestNeighbor = Neighbor[i];
825  }
826  }
827  return BestNeighbor;
828 } // FindNearestNeighbor
829 
842 CLUSTER *MakeNewCluster(CLUSTERER *Clusterer, TEMPCLUSTER *TempCluster) {
843  CLUSTER *Cluster;
844 
845  // allocate the new cluster and initialize it
846  Cluster = (CLUSTER *) Emalloc(
847  sizeof(CLUSTER) + (Clusterer->SampleSize - 1) * sizeof(FLOAT32));
848  Cluster->Clustered = FALSE;
849  Cluster->Prototype = FALSE;
850  Cluster->Left = TempCluster->Cluster;
851  Cluster->Right = TempCluster->Neighbor;
852  Cluster->CharID = -1;
853 
854  // mark the old clusters as "clustered" and delete them from the kd-tree
855  Cluster->Left->Clustered = TRUE;
856  Cluster->Right->Clustered = TRUE;
857  KDDelete(Clusterer->KDTree, Cluster->Left->Mean, Cluster->Left);
858  KDDelete(Clusterer->KDTree, Cluster->Right->Mean, Cluster->Right);
859 
860  // compute the mean and sample count for the new cluster
861  Cluster->SampleCount =
862  MergeClusters(Clusterer->SampleSize, Clusterer->ParamDesc,
863  Cluster->Left->SampleCount, Cluster->Right->SampleCount,
864  Cluster->Mean, Cluster->Left->Mean, Cluster->Right->Mean);
865 
866  // add the new cluster to the KD tree
867  KDStore(Clusterer->KDTree, Cluster->Mean, Cluster);
868  return Cluster;
869 } // MakeNewCluster
870 
886 inT32 MergeClusters(inT16 N,
887  PARAM_DESC ParamDesc[],
888  inT32 n1,
889  inT32 n2,
890  FLOAT32 m[],
891  FLOAT32 m1[], FLOAT32 m2[]) {
892  inT32 i, n;
893 
894  n = n1 + n2;
895  for (i = N; i > 0; i--, ParamDesc++, m++, m1++, m2++) {
896  if (ParamDesc->Circular) {
897  // if distance between means is greater than allowed
898  // reduce upper point by one "rotation" to compute mean
899  // then normalize the mean back into the accepted range
900  if ((*m2 - *m1) > ParamDesc->HalfRange) {
901  *m = (n1 * *m1 + n2 * (*m2 - ParamDesc->Range)) / n;
902  if (*m < ParamDesc->Min)
903  *m += ParamDesc->Range;
904  }
905  else if ((*m1 - *m2) > ParamDesc->HalfRange) {
906  *m = (n1 * (*m1 - ParamDesc->Range) + n2 * *m2) / n;
907  if (*m < ParamDesc->Min)
908  *m += ParamDesc->Range;
909  }
910  else
911  *m = (n1 * *m1 + n2 * *m2) / n;
912  }
913  else
914  *m = (n1 * *m1 + n2 * *m2) / n;
915  }
916  return n;
917 } // MergeClusters
918 
930 void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config) {
931  LIST ClusterStack = NIL_LIST;
932  CLUSTER *Cluster;
933  PROTOTYPE *Prototype;
934 
935  // use a stack to keep track of clusters waiting to be processed
936  // initially the only cluster on the stack is the root cluster
937  if (Clusterer->Root != NULL)
938  ClusterStack = push (NIL_LIST, Clusterer->Root);
939 
940  // loop until we have analyzed all clusters which are potential prototypes
941  while (ClusterStack != NIL_LIST) {
942  // remove the next cluster to be analyzed from the stack
943  // try to make a prototype from the cluster
944  // if successful, put it on the proto list, else split the cluster
945  Cluster = (CLUSTER *) first_node (ClusterStack);
946  ClusterStack = pop (ClusterStack);
947  Prototype = MakePrototype(Clusterer, Config, Cluster);
948  if (Prototype != NULL) {
949  Clusterer->ProtoList = push (Clusterer->ProtoList, Prototype);
950  }
951  else {
952  ClusterStack = push (ClusterStack, Cluster->Right);
953  ClusterStack = push (ClusterStack, Cluster->Left);
954  }
955  }
956 } // ComputePrototypes
957 
975 PROTOTYPE *MakePrototype(CLUSTERER *Clusterer,
976  CLUSTERCONFIG *Config,
977  CLUSTER *Cluster) {
978  STATISTICS *Statistics;
979  PROTOTYPE *Proto;
980  BUCKETS *Buckets;
981 
982  // filter out clusters which contain samples from the same character
983  if (MultipleCharSamples (Clusterer, Cluster, Config->MaxIllegal))
984  return NULL;
985 
986  // compute the covariance matrix and ranges for the cluster
987  Statistics =
988  ComputeStatistics(Clusterer->SampleSize, Clusterer->ParamDesc, Cluster);
989 
990  // check for degenerate clusters which need not be analyzed further
991  // note that the MinSamples test assumes that all clusters with multiple
992  // character samples have been removed (as above)
993  Proto = MakeDegenerateProto(
994  Clusterer->SampleSize, Cluster, Statistics, Config->ProtoStyle,
995  (inT32) (Config->MinSamples * Clusterer->NumChar));
996  if (Proto != NULL) {
997  FreeStatistics(Statistics);
998  return Proto;
999  }
1000  // check to ensure that all dimensions are independent
1001  if (!Independent(Clusterer->ParamDesc, Clusterer->SampleSize,
1002  Statistics->CoVariance, Config->Independence)) {
1003  FreeStatistics(Statistics);
1004  return NULL;
1005  }
1006 
1007  if (HOTELLING && Config->ProtoStyle == elliptical) {
1008  Proto = TestEllipticalProto(Clusterer, Config, Cluster, Statistics);
1009  if (Proto != NULL) {
1010  FreeStatistics(Statistics);
1011  return Proto;
1012  }
1013  }
1014 
1015  // create a histogram data structure used to evaluate distributions
1016  Buckets = GetBuckets(Clusterer, normal, Cluster->SampleCount,
1017  Config->Confidence);
1018 
1019  // create a prototype based on the statistics and test it
1020  switch (Config->ProtoStyle) {
1021  case spherical:
1022  Proto = MakeSphericalProto(Clusterer, Cluster, Statistics, Buckets);
1023  break;
1024  case elliptical:
1025  Proto = MakeEllipticalProto(Clusterer, Cluster, Statistics, Buckets);
1026  break;
1027  case mixed:
1028  Proto = MakeMixedProto(Clusterer, Cluster, Statistics, Buckets,
1029  Config->Confidence);
1030  break;
1031  case automatic:
1032  Proto = MakeSphericalProto(Clusterer, Cluster, Statistics, Buckets);
1033  if (Proto != NULL)
1034  break;
1035  Proto = MakeEllipticalProto(Clusterer, Cluster, Statistics, Buckets);
1036  if (Proto != NULL)
1037  break;
1038  Proto = MakeMixedProto(Clusterer, Cluster, Statistics, Buckets,
1039  Config->Confidence);
1040  break;
1041  }
1042  FreeStatistics(Statistics);
1043  return Proto;
1044 } // MakePrototype
1045 
1069 PROTOTYPE *MakeDegenerateProto( //this was MinSample
1070  uinT16 N,
1071  CLUSTER *Cluster,
1072  STATISTICS *Statistics,
1073  PROTOSTYLE Style,
1074  inT32 MinSamples) {
1075  PROTOTYPE *Proto = NULL;
1076 
1077  if (MinSamples < MINSAMPLESNEEDED)
1078  MinSamples = MINSAMPLESNEEDED;
1079 
1080  if (Cluster->SampleCount < MinSamples) {
1081  switch (Style) {
1082  case spherical:
1083  Proto = NewSphericalProto (N, Cluster, Statistics);
1084  break;
1085  case elliptical:
1086  case automatic:
1087  Proto = NewEllipticalProto (N, Cluster, Statistics);
1088  break;
1089  case mixed:
1090  Proto = NewMixedProto (N, Cluster, Statistics);
1091  break;
1092  }
1093  Proto->Significant = FALSE;
1094  }
1095  return (Proto);
1096 } // MakeDegenerateProto
1097 
1111 PROTOTYPE *TestEllipticalProto(CLUSTERER *Clusterer,
1112  CLUSTERCONFIG *Config,
1113  CLUSTER *Cluster,
1114  STATISTICS *Statistics) {
1115  // Fraction of the number of samples used as a range around 1 within
1116  // which a cluster has the magic size that allows a boost to the
1117  // FTable by kFTableBoostMargin, thus allowing clusters near the
1118  // magic size (equal to the number of sample characters) to be more
1119  // likely to stay together.
1120  const double kMagicSampleMargin = 0.0625;
1121  const double kFTableBoostMargin = 2.0;
1122 
1123  int N = Clusterer->SampleSize;
1124  CLUSTER* Left = Cluster->Left;
1125  CLUSTER* Right = Cluster->Right;
1126  if (Left == NULL || Right == NULL)
1127  return NULL;
1128  int TotalDims = Left->SampleCount + Right->SampleCount;
1129  if (TotalDims < N + 1 || TotalDims < 2)
1130  return NULL;
1131  const int kMatrixSize = N * N * sizeof(FLOAT32);
1132  FLOAT32* Covariance = reinterpret_cast<FLOAT32 *>(Emalloc(kMatrixSize));
1133  FLOAT32* Inverse = reinterpret_cast<FLOAT32 *>(Emalloc(kMatrixSize));
1134  FLOAT32* Delta = reinterpret_cast<FLOAT32*>(Emalloc(N * sizeof(FLOAT32)));
1135  // Compute a new covariance matrix that only uses essential features.
1136  for (int i = 0; i < N; ++i) {
1137  int row_offset = i * N;
1138  if (!Clusterer->ParamDesc[i].NonEssential) {
1139  for (int j = 0; j < N; ++j) {
1140  if (!Clusterer->ParamDesc[j].NonEssential)
1141  Covariance[j + row_offset] = Statistics->CoVariance[j + row_offset];
1142  else
1143  Covariance[j + row_offset] = 0.0f;
1144  }
1145  } else {
1146  for (int j = 0; j < N; ++j) {
1147  if (i == j)
1148  Covariance[j + row_offset] = 1.0f;
1149  else
1150  Covariance[j + row_offset] = 0.0f;
1151  }
1152  }
1153  }
1154  double err = InvertMatrix(Covariance, N, Inverse);
1155  if (err > 1) {
1156  tprintf("Clustering error: Matrix inverse failed with error %g\n", err);
1157  }
1158  int EssentialN = 0;
1159  for (int dim = 0; dim < N; ++dim) {
1160  if (!Clusterer->ParamDesc[dim].NonEssential) {
1161  Delta[dim] = Left->Mean[dim] - Right->Mean[dim];
1162  ++EssentialN;
1163  } else {
1164  Delta[dim] = 0.0f;
1165  }
1166  }
1167  // Compute Hotelling's T-squared.
1168  double Tsq = 0.0;
1169  for (int x = 0; x < N; ++x) {
1170  double temp = 0.0;
1171  for (int y = 0; y < N; ++y) {
1172  temp += Inverse[y + N*x] * Delta[y];
1173  }
1174  Tsq += Delta[x] * temp;
1175  }
1176  memfree(Covariance);
1177  memfree(Inverse);
1178  memfree(Delta);
1179  // Changed this function to match the formula in
1180  // Statistical Methods in Medical Research p 473
1181  // By Peter Armitage, Geoffrey Berry, J. N. S. Matthews.
1182  // Tsq *= Left->SampleCount * Right->SampleCount / TotalDims;
1183  double F = Tsq * (TotalDims - EssentialN - 1) / ((TotalDims - 2)*EssentialN);
1184  int Fx = EssentialN;
1185  if (Fx > FTABLE_X)
1186  Fx = FTABLE_X;
1187  --Fx;
1188  int Fy = TotalDims - EssentialN - 1;
1189  if (Fy > FTABLE_Y)
1190  Fy = FTABLE_Y;
1191  --Fy;
1192  double FTarget = FTable[Fy][Fx];
1193  if (Config->MagicSamples > 0 &&
1194  TotalDims >= Config->MagicSamples * (1.0 - kMagicSampleMargin) &&
1195  TotalDims <= Config->MagicSamples * (1.0 + kMagicSampleMargin)) {
1196  // Give magic-sized clusters a magic FTable boost.
1197  FTarget += kFTableBoostMargin;
1198  }
1199  if (F < FTarget) {
1200  return NewEllipticalProto (Clusterer->SampleSize, Cluster, Statistics);
1201  }
1202  return NULL;
1203 }
1204 
1218 PROTOTYPE *MakeSphericalProto(CLUSTERER *Clusterer,
1219  CLUSTER *Cluster,
1220  STATISTICS *Statistics,
1221  BUCKETS *Buckets) {
1222  PROTOTYPE *Proto = NULL;
1223  int i;
1224 
1225  // check that each dimension is a normal distribution
1226  for (i = 0; i < Clusterer->SampleSize; i++) {
1227  if (Clusterer->ParamDesc[i].NonEssential)
1228  continue;
1229 
1230  FillBuckets (Buckets, Cluster, i, &(Clusterer->ParamDesc[i]),
1231  Cluster->Mean[i],
1232  sqrt ((FLOAT64) (Statistics->AvgVariance)));
1233  if (!DistributionOK (Buckets))
1234  break;
1235  }
1236  // if all dimensions matched a normal distribution, make a proto
1237  if (i >= Clusterer->SampleSize)
1238  Proto = NewSphericalProto (Clusterer->SampleSize, Cluster, Statistics);
1239  return (Proto);
1240 } // MakeSphericalProto
1241 
1255 PROTOTYPE *MakeEllipticalProto(CLUSTERER *Clusterer,
1256  CLUSTER *Cluster,
1257  STATISTICS *Statistics,
1258  BUCKETS *Buckets) {
1259  PROTOTYPE *Proto = NULL;
1260  int i;
1261 
1262  // check that each dimension is a normal distribution
1263  for (i = 0; i < Clusterer->SampleSize; i++) {
1264  if (Clusterer->ParamDesc[i].NonEssential)
1265  continue;
1266 
1267  FillBuckets (Buckets, Cluster, i, &(Clusterer->ParamDesc[i]),
1268  Cluster->Mean[i],
1269  sqrt ((FLOAT64) Statistics->
1270  CoVariance[i * (Clusterer->SampleSize + 1)]));
1271  if (!DistributionOK (Buckets))
1272  break;
1273  }
1274  // if all dimensions matched a normal distribution, make a proto
1275  if (i >= Clusterer->SampleSize)
1276  Proto = NewEllipticalProto (Clusterer->SampleSize, Cluster, Statistics);
1277  return (Proto);
1278 } // MakeEllipticalProto
1279 
1297 PROTOTYPE *MakeMixedProto(CLUSTERER *Clusterer,
1298  CLUSTER *Cluster,
1299  STATISTICS *Statistics,
1300  BUCKETS *NormalBuckets,
1301  FLOAT64 Confidence) {
1302  PROTOTYPE *Proto;
1303  int i;
1304  BUCKETS *UniformBuckets = NULL;
1305  BUCKETS *RandomBuckets = NULL;
1306 
1307  // create a mixed proto to work on - initially assume all dimensions normal*/
1308  Proto = NewMixedProto (Clusterer->SampleSize, Cluster, Statistics);
1309 
1310  // find the proper distribution for each dimension
1311  for (i = 0; i < Clusterer->SampleSize; i++) {
1312  if (Clusterer->ParamDesc[i].NonEssential)
1313  continue;
1314 
1315  FillBuckets (NormalBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
1316  Proto->Mean[i],
1317  sqrt ((FLOAT64) Proto->Variance.Elliptical[i]));
1318  if (DistributionOK (NormalBuckets))
1319  continue;
1320 
1321  if (RandomBuckets == NULL)
1322  RandomBuckets =
1323  GetBuckets(Clusterer, D_random, Cluster->SampleCount, Confidence);
1324  MakeDimRandom (i, Proto, &(Clusterer->ParamDesc[i]));
1325  FillBuckets (RandomBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
1326  Proto->Mean[i], Proto->Variance.Elliptical[i]);
1327  if (DistributionOK (RandomBuckets))
1328  continue;
1329 
1330  if (UniformBuckets == NULL)
1331  UniformBuckets =
1332  GetBuckets(Clusterer, uniform, Cluster->SampleCount, Confidence);
1333  MakeDimUniform(i, Proto, Statistics);
1334  FillBuckets (UniformBuckets, Cluster, i, &(Clusterer->ParamDesc[i]),
1335  Proto->Mean[i], Proto->Variance.Elliptical[i]);
1336  if (DistributionOK (UniformBuckets))
1337  continue;
1338  break;
1339  }
1340  // if any dimension failed to match a distribution, discard the proto
1341  if (i < Clusterer->SampleSize) {
1342  FreePrototype(Proto);
1343  Proto = NULL;
1344  }
1345  return (Proto);
1346 } // MakeMixedProto
1347 
1358 void MakeDimRandom(uinT16 i, PROTOTYPE *Proto, PARAM_DESC *ParamDesc) {
1359  Proto->Distrib[i] = D_random;
1360  Proto->Mean[i] = ParamDesc->MidRange;
1361  Proto->Variance.Elliptical[i] = ParamDesc->HalfRange;
1362 
1363  // subtract out the previous magnitude of this dimension from the total
1364  Proto->TotalMagnitude /= Proto->Magnitude.Elliptical[i];
1365  Proto->Magnitude.Elliptical[i] = 1.0 / ParamDesc->Range;
1366  Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
1367  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);
1368 
1369  // note that the proto Weight is irrelevant for D_random protos
1370 } // MakeDimRandom
1371 
1382 void MakeDimUniform(uinT16 i, PROTOTYPE *Proto, STATISTICS *Statistics) {
1383  Proto->Distrib[i] = uniform;
1384  Proto->Mean[i] = Proto->Cluster->Mean[i] +
1385  (Statistics->Min[i] + Statistics->Max[i]) / 2;
1386  Proto->Variance.Elliptical[i] =
1387  (Statistics->Max[i] - Statistics->Min[i]) / 2;
1388  if (Proto->Variance.Elliptical[i] < MINVARIANCE)
1389  Proto->Variance.Elliptical[i] = MINVARIANCE;
1390 
1391  // subtract out the previous magnitude of this dimension from the total
1392  Proto->TotalMagnitude /= Proto->Magnitude.Elliptical[i];
1393  Proto->Magnitude.Elliptical[i] =
1394  1.0 / (2.0 * Proto->Variance.Elliptical[i]);
1395  Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
1396  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);
1397 
1398  // note that the proto Weight is irrelevant for uniform protos
1399 } // MakeDimUniform
1400 
1417 STATISTICS *
1418 ComputeStatistics (inT16 N, PARAM_DESC ParamDesc[], CLUSTER * Cluster) {
1419  STATISTICS *Statistics;
1420  int i, j;
1421  FLOAT32 *CoVariance;
1422  FLOAT32 *Distance;
1423  LIST SearchState;
1424  SAMPLE *Sample;
1425  uinT32 SampleCountAdjustedForBias;
1426 
1427  // allocate memory to hold the statistics results
1428  Statistics = (STATISTICS *) Emalloc (sizeof (STATISTICS));
1429  Statistics->CoVariance = (FLOAT32 *) Emalloc (N * N * sizeof (FLOAT32));
1430  Statistics->Min = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1431  Statistics->Max = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1432 
1433  // allocate temporary memory to hold the sample to mean distances
1434  Distance = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1435 
1436  // initialize the statistics
1437  Statistics->AvgVariance = 1.0;
1438  CoVariance = Statistics->CoVariance;
1439  for (i = 0; i < N; i++) {
1440  Statistics->Min[i] = 0.0;
1441  Statistics->Max[i] = 0.0;
1442  for (j = 0; j < N; j++, CoVariance++)
1443  *CoVariance = 0;
1444  }
1445  // find each sample in the cluster and merge it into the statistics
1446  InitSampleSearch(SearchState, Cluster);
1447  while ((Sample = NextSample (&SearchState)) != NULL) {
1448  for (i = 0; i < N; i++) {
1449  Distance[i] = Sample->Mean[i] - Cluster->Mean[i];
1450  if (ParamDesc[i].Circular) {
1451  if (Distance[i] > ParamDesc[i].HalfRange)
1452  Distance[i] -= ParamDesc[i].Range;
1453  if (Distance[i] < -ParamDesc[i].HalfRange)
1454  Distance[i] += ParamDesc[i].Range;
1455  }
1456  if (Distance[i] < Statistics->Min[i])
1457  Statistics->Min[i] = Distance[i];
1458  if (Distance[i] > Statistics->Max[i])
1459  Statistics->Max[i] = Distance[i];
1460  }
1461  CoVariance = Statistics->CoVariance;
1462  for (i = 0; i < N; i++)
1463  for (j = 0; j < N; j++, CoVariance++)
1464  *CoVariance += Distance[i] * Distance[j];
1465  }
1466  // normalize the variances by the total number of samples
1467  // use SampleCount-1 instead of SampleCount to get an unbiased estimate
1468  // also compute the geometic mean of the diagonal variances
1469  // ensure that clusters with only 1 sample are handled correctly
1470  if (Cluster->SampleCount > 1)
1471  SampleCountAdjustedForBias = Cluster->SampleCount - 1;
1472  else
1473  SampleCountAdjustedForBias = 1;
1474  CoVariance = Statistics->CoVariance;
1475  for (i = 0; i < N; i++)
1476  for (j = 0; j < N; j++, CoVariance++) {
1477  *CoVariance /= SampleCountAdjustedForBias;
1478  if (j == i) {
1479  if (*CoVariance < MINVARIANCE)
1480  *CoVariance = MINVARIANCE;
1481  Statistics->AvgVariance *= *CoVariance;
1482  }
1483  }
1484  Statistics->AvgVariance = (float)pow((double)Statistics->AvgVariance,
1485  1.0 / N);
1486 
1487  // release temporary memory and return
1488  memfree(Distance);
1489  return (Statistics);
1490 } // ComputeStatistics
1491 
1505 PROTOTYPE *NewSphericalProto(uinT16 N,
1506  CLUSTER *Cluster,
1507  STATISTICS *Statistics) {
1508  PROTOTYPE *Proto;
1509 
1510  Proto = NewSimpleProto (N, Cluster);
1511 
1512  Proto->Variance.Spherical = Statistics->AvgVariance;
1513  if (Proto->Variance.Spherical < MINVARIANCE)
1514  Proto->Variance.Spherical = MINVARIANCE;
1515 
1516  Proto->Magnitude.Spherical =
1517  1.0 / sqrt ((double) (2.0 * PI * Proto->Variance.Spherical));
1518  Proto->TotalMagnitude = (float)pow((double)Proto->Magnitude.Spherical,
1519  (double) N);
1520  Proto->Weight.Spherical = 1.0 / Proto->Variance.Spherical;
1521  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);
1522 
1523  return (Proto);
1524 } // NewSphericalProto
1525 
1538 PROTOTYPE *NewEllipticalProto(inT16 N,
1539  CLUSTER *Cluster,
1540  STATISTICS *Statistics) {
1541  PROTOTYPE *Proto;
1542  FLOAT32 *CoVariance;
1543  int i;
1544 
1545  Proto = NewSimpleProto (N, Cluster);
1546  Proto->Variance.Elliptical = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1547  Proto->Magnitude.Elliptical = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1548  Proto->Weight.Elliptical = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1549 
1550  CoVariance = Statistics->CoVariance;
1551  Proto->TotalMagnitude = 1.0;
1552  for (i = 0; i < N; i++, CoVariance += N + 1) {
1553  Proto->Variance.Elliptical[i] = *CoVariance;
1554  if (Proto->Variance.Elliptical[i] < MINVARIANCE)
1555  Proto->Variance.Elliptical[i] = MINVARIANCE;
1556 
1557  Proto->Magnitude.Elliptical[i] =
1558  1.0 / sqrt ((double) (2.0 * PI * Proto->Variance.Elliptical[i]));
1559  Proto->Weight.Elliptical[i] = 1.0 / Proto->Variance.Elliptical[i];
1560  Proto->TotalMagnitude *= Proto->Magnitude.Elliptical[i];
1561  }
1562  Proto->LogMagnitude = log ((double) Proto->TotalMagnitude);
1563  Proto->Style = elliptical;
1564  return (Proto);
1565 } // NewEllipticalProto
1566 
1582 PROTOTYPE *NewMixedProto(inT16 N, CLUSTER *Cluster, STATISTICS *Statistics) {
1583  PROTOTYPE *Proto;
1584  int i;
1585 
1586  Proto = NewEllipticalProto (N, Cluster, Statistics);
1587  Proto->Distrib = (DISTRIBUTION *) Emalloc (N * sizeof (DISTRIBUTION));
1588 
1589  for (i = 0; i < N; i++) {
1590  Proto->Distrib[i] = normal;
1591  }
1592  Proto->Style = mixed;
1593  return (Proto);
1594 } // NewMixedProto
1595 
1606 PROTOTYPE *NewSimpleProto(inT16 N, CLUSTER *Cluster) {
1607  PROTOTYPE *Proto;
1608  int i;
1609 
1610  Proto = (PROTOTYPE *) Emalloc (sizeof (PROTOTYPE));
1611  Proto->Mean = (FLOAT32 *) Emalloc (N * sizeof (FLOAT32));
1612 
1613  for (i = 0; i < N; i++)
1614  Proto->Mean[i] = Cluster->Mean[i];
1615  Proto->Distrib = NULL;
1616 
1617  Proto->Significant = TRUE;
1618  Proto->Merged = FALSE;
1619  Proto->Style = spherical;
1620  Proto->NumSamples = Cluster->SampleCount;
1621  Proto->Cluster = Cluster;
1622  Proto->Cluster->Prototype = TRUE;
1623  return (Proto);
1624 } // NewSimpleProto
1625 
1646 BOOL8
1647 Independent (PARAM_DESC ParamDesc[],
1648 inT16 N, FLOAT32 * CoVariance, FLOAT32 Independence) {
1649  int i, j;
1650  FLOAT32 *VARii; // points to ith on-diagonal element
1651  FLOAT32 *VARjj; // points to jth on-diagonal element
1652  FLOAT32 CorrelationCoeff;
1653 
1654  VARii = CoVariance;
1655  for (i = 0; i < N; i++, VARii += N + 1) {
1656  if (ParamDesc[i].NonEssential)
1657  continue;
1658 
1659  VARjj = VARii + N + 1;
1660  CoVariance = VARii + 1;
1661  for (j = i + 1; j < N; j++, CoVariance++, VARjj += N + 1) {
1662  if (ParamDesc[j].NonEssential)
1663  continue;
1664 
1665  if ((*VARii == 0.0) || (*VARjj == 0.0))
1666  CorrelationCoeff = 0.0;
1667  else
1668  CorrelationCoeff =
1669  sqrt (sqrt (*CoVariance * *CoVariance / (*VARii * *VARjj)));
1670  if (CorrelationCoeff > Independence)
1671  return (FALSE);
1672  }
1673  }
1674  return (TRUE);
1675 } // Independent
1676 
1694 BUCKETS *GetBuckets(CLUSTERER* clusterer,
1695  DISTRIBUTION Distribution,
1696  uinT32 SampleCount,
1697  FLOAT64 Confidence) {
1698  // Get an old bucket structure with the same number of buckets.
1699  uinT16 NumberOfBuckets = OptimumNumberOfBuckets(SampleCount);
1700  BUCKETS *Buckets =
1701  clusterer->bucket_cache[Distribution][NumberOfBuckets - MINBUCKETS];
1702 
1703  // If a matching bucket structure is not found, make one and save it.
1704  if (Buckets == NULL) {
1705  Buckets = MakeBuckets(Distribution, SampleCount, Confidence);
1706  clusterer->bucket_cache[Distribution][NumberOfBuckets - MINBUCKETS] =
1707  Buckets;
1708  } else {
1709  // Just adjust the existing buckets.
1710  if (SampleCount != Buckets->SampleCount)
1711  AdjustBuckets(Buckets, SampleCount);
1712  if (Confidence != Buckets->Confidence) {
1713  Buckets->Confidence = Confidence;
1714  Buckets->ChiSquared = ComputeChiSquared(
1715  DegreesOfFreedom(Distribution, Buckets->NumberOfBuckets),
1716  Confidence);
1717  }
1718  InitBuckets(Buckets);
1719  }
1720  return Buckets;
1721 } // GetBuckets
1722 
1741 BUCKETS *MakeBuckets(DISTRIBUTION Distribution,
1742  uinT32 SampleCount,
1743  FLOAT64 Confidence) {
1744  const DENSITYFUNC DensityFunction[] =
1745  { NormalDensity, UniformDensity, UniformDensity };
1746  int i, j;
1747  BUCKETS *Buckets;
1748  FLOAT64 BucketProbability;
1749  FLOAT64 NextBucketBoundary;
1750  FLOAT64 Probability;
1751  FLOAT64 ProbabilityDelta;
1752  FLOAT64 LastProbDensity;
1753  FLOAT64 ProbDensity;
1754  uinT16 CurrentBucket;
1755  BOOL8 Symmetrical;
1756 
1757  // allocate memory needed for data structure
1758  Buckets = reinterpret_cast<BUCKETS*>(Emalloc(sizeof(BUCKETS)));
1759  Buckets->NumberOfBuckets = OptimumNumberOfBuckets(SampleCount);
1760  Buckets->SampleCount = SampleCount;
1761  Buckets->Confidence = Confidence;
1762  Buckets->Count = reinterpret_cast<uinT32*>(
1763  Emalloc(Buckets->NumberOfBuckets * sizeof(uinT32)));
1764  Buckets->ExpectedCount = reinterpret_cast<FLOAT32*>(
1765  Emalloc(Buckets->NumberOfBuckets * sizeof(FLOAT32)));
1766 
1767  // initialize simple fields
1768  Buckets->Distribution = Distribution;
1769  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
1770  Buckets->Count[i] = 0;
1771  Buckets->ExpectedCount[i] = 0.0;
1772  }
1773 
1774  // all currently defined distributions are symmetrical
1775  Symmetrical = TRUE;
1776  Buckets->ChiSquared = ComputeChiSquared(
1777  DegreesOfFreedom(Distribution, Buckets->NumberOfBuckets), Confidence);
1778 
1779  if (Symmetrical) {
1780  // allocate buckets so that all have approx. equal probability
1781  BucketProbability = 1.0 / (FLOAT64) (Buckets->NumberOfBuckets);
1782 
1783  // distribution is symmetric so fill in upper half then copy
1784  CurrentBucket = Buckets->NumberOfBuckets / 2;
1785  if (Odd (Buckets->NumberOfBuckets))
1786  NextBucketBoundary = BucketProbability / 2;
1787  else
1788  NextBucketBoundary = BucketProbability;
1789 
1790  Probability = 0.0;
1791  LastProbDensity =
1792  (*DensityFunction[(int) Distribution]) (BUCKETTABLESIZE / 2);
1793  for (i = BUCKETTABLESIZE / 2; i < BUCKETTABLESIZE; i++) {
1794  ProbDensity = (*DensityFunction[(int) Distribution]) (i + 1);
1795  ProbabilityDelta = Integral (LastProbDensity, ProbDensity, 1.0);
1796  Probability += ProbabilityDelta;
1797  if (Probability > NextBucketBoundary) {
1798  if (CurrentBucket < Buckets->NumberOfBuckets - 1)
1799  CurrentBucket++;
1800  NextBucketBoundary += BucketProbability;
1801  }
1802  Buckets->Bucket[i] = CurrentBucket;
1803  Buckets->ExpectedCount[CurrentBucket] +=
1804  (FLOAT32) (ProbabilityDelta * SampleCount);
1805  LastProbDensity = ProbDensity;
1806  }
1807  // place any leftover probability into the last bucket
1808  Buckets->ExpectedCount[CurrentBucket] +=
1809  (FLOAT32) ((0.5 - Probability) * SampleCount);
1810 
1811  // copy upper half of distribution to lower half
1812  for (i = 0, j = BUCKETTABLESIZE - 1; i < j; i++, j--)
1813  Buckets->Bucket[i] =
1814  Mirror(Buckets->Bucket[j], Buckets->NumberOfBuckets);
1815 
1816  // copy upper half of expected counts to lower half
1817  for (i = 0, j = Buckets->NumberOfBuckets - 1; i <= j; i++, j--)
1818  Buckets->ExpectedCount[i] += Buckets->ExpectedCount[j];
1819  }
1820  return Buckets;
1821 } // MakeBuckets
1822 
1838 uinT16 OptimumNumberOfBuckets(uinT32 SampleCount) {
1839  uinT8 Last, Next;
1840  FLOAT32 Slope;
1841 
1842  if (SampleCount < kCountTable[0])
1843  return kBucketsTable[0];
1844 
1845  for (Last = 0, Next = 1; Next < LOOKUPTABLESIZE; Last++, Next++) {
1846  if (SampleCount <= kCountTable[Next]) {
1847  Slope = (FLOAT32) (kBucketsTable[Next] - kBucketsTable[Last]) /
1848  (FLOAT32) (kCountTable[Next] - kCountTable[Last]);
1849  return ((uinT16) (kBucketsTable[Last] +
1850  Slope * (SampleCount - kCountTable[Last])));
1851  }
1852  }
1853  return kBucketsTable[Last];
1854 } // OptimumNumberOfBuckets
1855 
1874 FLOAT64
1875 ComputeChiSquared (uinT16 DegreesOfFreedom, FLOAT64 Alpha)
1876 #define CHIACCURACY 0.01
1877 #define MINALPHA (1e-200)
1878 {
1879  static LIST ChiWith[MAXDEGREESOFFREEDOM + 1];
1880 
1881  CHISTRUCT *OldChiSquared;
1882  CHISTRUCT SearchKey;
1883 
1884  // limit the minimum alpha that can be used - if alpha is too small
1885  // it may not be possible to compute chi-squared.
1886  Alpha = ClipToRange(Alpha, MINALPHA, 1.0);
1887  if (Odd (DegreesOfFreedom))
1888  DegreesOfFreedom++;
1889 
1890  /* find the list of chi-squared values which have already been computed
1891  for the specified number of degrees of freedom. Search the list for
1892  the desired chi-squared. */
1893  SearchKey.Alpha = Alpha;
1894  OldChiSquared = (CHISTRUCT *) first_node (search (ChiWith[DegreesOfFreedom],
1895  &SearchKey, AlphaMatch));
1896 
1897  if (OldChiSquared == NULL) {
1898  OldChiSquared = NewChiStruct (DegreesOfFreedom, Alpha);
1899  OldChiSquared->ChiSquared = Solve (ChiArea, OldChiSquared,
1900  (FLOAT64) DegreesOfFreedom,
1901  (FLOAT64) CHIACCURACY);
1902  ChiWith[DegreesOfFreedom] = push (ChiWith[DegreesOfFreedom],
1903  OldChiSquared);
1904  }
1905  else {
1906  // further optimization might move OldChiSquared to front of list
1907  }
1908 
1909  return (OldChiSquared->ChiSquared);
1910 
1911 } // ComputeChiSquared
1912 
1929 FLOAT64 NormalDensity(inT32 x) {
1930  FLOAT64 Distance;
1931 
1932  Distance = x - kNormalMean;
1933  return kNormalMagnitude * exp(-0.5 * Distance * Distance / kNormalVariance);
1934 } // NormalDensity
1935 
1945 FLOAT64 UniformDensity(inT32 x) {
1946  static FLOAT64 UniformDistributionDensity = (FLOAT64) 1.0 / BUCKETTABLESIZE;
1947 
1948  if ((x >= 0.0) && (x <= BUCKETTABLESIZE))
1949  return UniformDistributionDensity;
1950  else
1951  return (FLOAT64) 0.0;
1952 } // UniformDensity
1953 
1964 FLOAT64 Integral(FLOAT64 f1, FLOAT64 f2, FLOAT64 Dx) {
1965  return (f1 + f2) * Dx / 2.0;
1966 } // Integral
1967 
1990 void FillBuckets(BUCKETS *Buckets,
1991  CLUSTER *Cluster,
1992  uinT16 Dim,
1993  PARAM_DESC *ParamDesc,
1994  FLOAT32 Mean,
1995  FLOAT32 StdDev) {
1996  uinT16 BucketID;
1997  int i;
1998  LIST SearchState;
1999  SAMPLE *Sample;
2000 
2001  // initialize the histogram bucket counts to 0
2002  for (i = 0; i < Buckets->NumberOfBuckets; i++)
2003  Buckets->Count[i] = 0;
2004 
2005  if (StdDev == 0.0) {
2006  /* if the standard deviation is zero, then we can't statistically
2007  analyze the cluster. Use a pseudo-analysis: samples exactly on
2008  the mean are distributed evenly across all buckets. Samples greater
2009  than the mean are placed in the last bucket; samples less than the
2010  mean are placed in the first bucket. */
2011 
2012  InitSampleSearch(SearchState, Cluster);
2013  i = 0;
2014  while ((Sample = NextSample (&SearchState)) != NULL) {
2015  if (Sample->Mean[Dim] > Mean)
2016  BucketID = Buckets->NumberOfBuckets - 1;
2017  else if (Sample->Mean[Dim] < Mean)
2018  BucketID = 0;
2019  else
2020  BucketID = i;
2021  Buckets->Count[BucketID] += 1;
2022  i++;
2023  if (i >= Buckets->NumberOfBuckets)
2024  i = 0;
2025  }
2026  }
2027  else {
2028  // search for all samples in the cluster and add to histogram buckets
2029  InitSampleSearch(SearchState, Cluster);
2030  while ((Sample = NextSample (&SearchState)) != NULL) {
2031  switch (Buckets->Distribution) {
2032  case normal:
2033  BucketID = NormalBucket (ParamDesc, Sample->Mean[Dim],
2034  Mean, StdDev);
2035  break;
2036  case D_random:
2037  case uniform:
2038  BucketID = UniformBucket (ParamDesc, Sample->Mean[Dim],
2039  Mean, StdDev);
2040  break;
2041  default:
2042  BucketID = 0;
2043  }
2044  Buckets->Count[Buckets->Bucket[BucketID]] += 1;
2045  }
2046  }
2047 } // FillBuckets
2048 
2062 uinT16 NormalBucket(PARAM_DESC *ParamDesc,
2063  FLOAT32 x,
2064  FLOAT32 Mean,
2065  FLOAT32 StdDev) {
2066  FLOAT32 X;
2067 
2068  // wraparound circular parameters if necessary
2069  if (ParamDesc->Circular) {
2070  if (x - Mean > ParamDesc->HalfRange)
2071  x -= ParamDesc->Range;
2072  else if (x - Mean < -ParamDesc->HalfRange)
2073  x += ParamDesc->Range;
2074  }
2075 
2076  X = ((x - Mean) / StdDev) * kNormalStdDev + kNormalMean;
2077  if (X < 0)
2078  return 0;
2079  if (X > BUCKETTABLESIZE - 1)
2080  return ((uinT16) (BUCKETTABLESIZE - 1));
2081  return (uinT16) floor((FLOAT64) X);
2082 } // NormalBucket
2083 
2097 uinT16 UniformBucket(PARAM_DESC *ParamDesc,
2098  FLOAT32 x,
2099  FLOAT32 Mean,
2100  FLOAT32 StdDev) {
2101  FLOAT32 X;
2102 
2103  // wraparound circular parameters if necessary
2104  if (ParamDesc->Circular) {
2105  if (x - Mean > ParamDesc->HalfRange)
2106  x -= ParamDesc->Range;
2107  else if (x - Mean < -ParamDesc->HalfRange)
2108  x += ParamDesc->Range;
2109  }
2110 
2111  X = ((x - Mean) / (2 * StdDev) * BUCKETTABLESIZE + BUCKETTABLESIZE / 2.0);
2112  if (X < 0)
2113  return 0;
2114  if (X > BUCKETTABLESIZE - 1)
2115  return (uinT16) (BUCKETTABLESIZE - 1);
2116  return (uinT16) floor((FLOAT64) X);
2117 } // UniformBucket
2118 
2131 BOOL8 DistributionOK(BUCKETS *Buckets) {
2132  FLOAT32 FrequencyDifference;
2133  FLOAT32 TotalDifference;
2134  int i;
2135 
2136  // compute how well the histogram matches the expected histogram
2137  TotalDifference = 0.0;
2138  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
2139  FrequencyDifference = Buckets->Count[i] - Buckets->ExpectedCount[i];
2140  TotalDifference += (FrequencyDifference * FrequencyDifference) /
2141  Buckets->ExpectedCount[i];
2142  }
2143 
2144  // test to see if the difference is more than expected
2145  if (TotalDifference > Buckets->ChiSquared)
2146  return FALSE;
2147  else
2148  return TRUE;
2149 } // DistributionOK
2150 
2159 void FreeStatistics(STATISTICS *Statistics) {
2160  memfree (Statistics->CoVariance);
2161  memfree (Statistics->Min);
2162  memfree (Statistics->Max);
2163  memfree(Statistics);
2164 } // FreeStatistics
2165 
2171 void FreeBuckets(BUCKETS *buckets) {
2172  Efree(buckets->Count);
2173  Efree(buckets->ExpectedCount);
2174  Efree(buckets);
2175 } // FreeBuckets
2176 
2189 void FreeCluster(CLUSTER *Cluster) {
2190  if (Cluster != NULL) {
2191  FreeCluster (Cluster->Left);
2192  FreeCluster (Cluster->Right);
2193  memfree(Cluster);
2194  }
2195 } // FreeCluster
2196 
2211 uinT16 DegreesOfFreedom(DISTRIBUTION Distribution, uinT16 HistogramBuckets) {
2212  static uinT8 DegreeOffsets[] = { 3, 3, 1 };
2213 
2214  uinT16 AdjustedNumBuckets;
2215 
2216  AdjustedNumBuckets = HistogramBuckets - DegreeOffsets[(int) Distribution];
2217  if (Odd (AdjustedNumBuckets))
2218  AdjustedNumBuckets++;
2219  return (AdjustedNumBuckets);
2220 
2221 } // DegreesOfFreedom
2222 
2233 int NumBucketsMatch(void *arg1, // BUCKETS *Histogram,
2234  void *arg2) { // uinT16 *DesiredNumberOfBuckets)
2235  BUCKETS *Histogram = (BUCKETS *) arg1;
2236  uinT16 *DesiredNumberOfBuckets = (uinT16 *) arg2;
2237 
2238  return (*DesiredNumberOfBuckets == Histogram->NumberOfBuckets);
2239 
2240 } // NumBucketsMatch
2241 
2250 int ListEntryMatch(void *arg1, //ListNode
2251  void *arg2) { //Key
2252  return (arg1 == arg2);
2253 
2254 } // ListEntryMatch
2255 
2266 void AdjustBuckets(BUCKETS *Buckets, uinT32 NewSampleCount) {
2267  int i;
2268  FLOAT64 AdjustFactor;
2269 
2270  AdjustFactor = (((FLOAT64) NewSampleCount) /
2271  ((FLOAT64) Buckets->SampleCount));
2272 
2273  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
2274  Buckets->ExpectedCount[i] *= AdjustFactor;
2275  }
2276 
2277  Buckets->SampleCount = NewSampleCount;
2278 
2279 } // AdjustBuckets
2280 
2289 void InitBuckets(BUCKETS *Buckets) {
2290  int i;
2291 
2292  for (i = 0; i < Buckets->NumberOfBuckets; i++) {
2293  Buckets->Count[i] = 0;
2294  }
2295 
2296 } // InitBuckets
2297 
2312 int AlphaMatch(void *arg1, //CHISTRUCT *ChiStruct,
2313  void *arg2) { //CHISTRUCT *SearchKey)
2314  CHISTRUCT *ChiStruct = (CHISTRUCT *) arg1;
2315  CHISTRUCT *SearchKey = (CHISTRUCT *) arg2;
2316 
2317  return (ChiStruct->Alpha == SearchKey->Alpha);
2318 
2319 } // AlphaMatch
2320 
2332 CHISTRUCT *NewChiStruct(uinT16 DegreesOfFreedom, FLOAT64 Alpha) {
2333  CHISTRUCT *NewChiStruct;
2334 
2335  NewChiStruct = (CHISTRUCT *) Emalloc (sizeof (CHISTRUCT));
2336  NewChiStruct->DegreesOfFreedom = DegreesOfFreedom;
2337  NewChiStruct->Alpha = Alpha;
2338  return (NewChiStruct);
2339 
2340 } // NewChiStruct
2341 
2357 FLOAT64
2358 Solve (SOLVEFUNC Function,
2359 void *FunctionParams, FLOAT64 InitialGuess, FLOAT64 Accuracy)
2360 #define INITIALDELTA 0.1
2361 #define DELTARATIO 0.1
2362 {
2363  FLOAT64 x;
2364  FLOAT64 f;
2365  FLOAT64 Slope;
2366  FLOAT64 Delta;
2367  FLOAT64 NewDelta;
2368  FLOAT64 xDelta;
2369  FLOAT64 LastPosX, LastNegX;
2370 
2371  x = InitialGuess;
2372  Delta = INITIALDELTA;
2373  LastPosX = MAX_FLOAT32;
2374  LastNegX = -MAX_FLOAT32;
2375  f = (*Function) ((CHISTRUCT *) FunctionParams, x);
2376  while (Abs (LastPosX - LastNegX) > Accuracy) {
2377  // keep track of outer bounds of current estimate
2378  if (f < 0)
2379  LastNegX = x;
2380  else
2381  LastPosX = x;
2382 
2383  // compute the approx. slope of f(x) at the current point
2384  Slope =
2385  ((*Function) ((CHISTRUCT *) FunctionParams, x + Delta) - f) / Delta;
2386 
2387  // compute the next solution guess */
2388  xDelta = f / Slope;
2389  x -= xDelta;
2390 
2391  // reduce the delta used for computing slope to be a fraction of
2392  //the amount moved to get to the new guess
2393  NewDelta = Abs (xDelta) * DELTARATIO;
2394  if (NewDelta < Delta)
2395  Delta = NewDelta;
2396 
2397  // compute the value of the function at the new guess
2398  f = (*Function) ((CHISTRUCT *) FunctionParams, x);
2399  }
2400  return (x);
2401 
2402 } // Solve
2403 
2424 FLOAT64 ChiArea(CHISTRUCT *ChiParams, FLOAT64 x) {
2425  int i, N;
2426  FLOAT64 SeriesTotal;
2427  FLOAT64 Denominator;
2428  FLOAT64 PowerOfx;
2429 
2430  N = ChiParams->DegreesOfFreedom / 2 - 1;
2431  SeriesTotal = 1;
2432  Denominator = 1;
2433  PowerOfx = 1;
2434  for (i = 1; i <= N; i++) {
2435  Denominator *= 2 * i;
2436  PowerOfx *= x;
2437  SeriesTotal += PowerOfx / Denominator;
2438  }
2439  return ((SeriesTotal * exp (-0.5 * x)) - ChiParams->Alpha);
2440 
2441 } // ChiArea
2442 
2470 BOOL8
2471 MultipleCharSamples (CLUSTERER * Clusterer,
2472 CLUSTER * Cluster, FLOAT32 MaxIllegal)
2473 #define ILLEGAL_CHAR 2
2474 {
2475  static BOOL8 *CharFlags = NULL;
2476  static inT32 NumFlags = 0;
2477  int i;
2478  LIST SearchState;
2479  SAMPLE *Sample;
2480  inT32 CharID;
2481  inT32 NumCharInCluster;
2482  inT32 NumIllegalInCluster;
2483  FLOAT32 PercentIllegal;
2484 
2485  // initial estimate assumes that no illegal chars exist in the cluster
2486  NumCharInCluster = Cluster->SampleCount;
2487  NumIllegalInCluster = 0;
2488 
2489  if (Clusterer->NumChar > NumFlags) {
2490  if (CharFlags != NULL)
2491  memfree(CharFlags);
2492  NumFlags = Clusterer->NumChar;
2493  CharFlags = (BOOL8 *) Emalloc (NumFlags * sizeof (BOOL8));
2494  }
2495 
2496  for (i = 0; i < NumFlags; i++)
2497  CharFlags[i] = FALSE;
2498 
2499  // find each sample in the cluster and check if we have seen it before
2500  InitSampleSearch(SearchState, Cluster);
2501  while ((Sample = NextSample (&SearchState)) != NULL) {
2502  CharID = Sample->CharID;
2503  if (CharFlags[CharID] == FALSE) {
2504  CharFlags[CharID] = TRUE;
2505  }
2506  else {
2507  if (CharFlags[CharID] == TRUE) {
2508  NumIllegalInCluster++;
2509  CharFlags[CharID] = ILLEGAL_CHAR;
2510  }
2511  NumCharInCluster--;
2512  PercentIllegal = (FLOAT32) NumIllegalInCluster / NumCharInCluster;
2513  if (PercentIllegal > MaxIllegal) {
2514  destroy(SearchState);
2515  return (TRUE);
2516  }
2517  }
2518  }
2519  return (FALSE);
2520 
2521 } // MultipleCharSamples
2522 
2528 double InvertMatrix(const float* input, int size, float* inv) {
2529  // Allocate memory for the 2D arrays.
2530  GENERIC_2D_ARRAY<double> U(size, size, 0.0);
2531  GENERIC_2D_ARRAY<double> U_inv(size, size, 0.0);
2532  GENERIC_2D_ARRAY<double> L(size, size, 0.0);
2533 
2534  // Initialize the working matrices. U starts as input, L as I and U_inv as O.
2535  int row;
2536  int col;
2537  for (row = 0; row < size; row++) {
2538  for (col = 0; col < size; col++) {
2539  U[row][col] = input[row*size + col];
2540  L[row][col] = row == col ? 1.0 : 0.0;
2541  U_inv[row][col] = 0.0;
2542  }
2543  }
2544 
2545  // Compute forward matrix by inversion by LU decomposition of input.
2546  for (col = 0; col < size; ++col) {
2547  // Find best pivot
2548  int best_row = 0;
2549  double best_pivot = -1.0;
2550  for (row = col; row < size; ++row) {
2551  if (Abs(U[row][col]) > best_pivot) {
2552  best_pivot = Abs(U[row][col]);
2553  best_row = row;
2554  }
2555  }
2556  // Exchange pivot rows.
2557  if (best_row != col) {
2558  for (int k = 0; k < size; ++k) {
2559  double tmp = U[best_row][k];
2560  U[best_row][k] = U[col][k];
2561  U[col][k] = tmp;
2562  tmp = L[best_row][k];
2563  L[best_row][k] = L[col][k];
2564  L[col][k] = tmp;
2565  }
2566  }
2567  // Now do the pivot itself.
2568  for (row = col + 1; row < size; ++row) {
2569  double ratio = -U[row][col] / U[col][col];
2570  for (int j = col; j < size; ++j) {
2571  U[row][j] += U[col][j] * ratio;
2572  }
2573  for (int k = 0; k < size; ++k) {
2574  L[row][k] += L[col][k] * ratio;
2575  }
2576  }
2577  }
2578  // Next invert U.
2579  for (col = 0; col < size; ++col) {
2580  U_inv[col][col] = 1.0 / U[col][col];
2581  for (row = col - 1; row >= 0; --row) {
2582  double total = 0.0;
2583  for (int k = col; k > row; --k) {
2584  total += U[row][k] * U_inv[k][col];
2585  }
2586  U_inv[row][col] = -total / U[row][row];
2587  }
2588  }
2589  // Now the answer is U_inv.L.
2590  for (row = 0; row < size; row++) {
2591  for (col = 0; col < size; col++) {
2592  double sum = 0.0;
2593  for (int k = row; k < size; ++k) {
2594  sum += U_inv[row][k] * L[k][col];
2595  }
2596  inv[row*size + col] = sum;
2597  }
2598  }
2599  // Check matrix product.
2600  double error_sum = 0.0;
2601  for (row = 0; row < size; row++) {
2602  for (col = 0; col < size; col++) {
2603  double sum = 0.0;
2604  for (int k = 0; k < size; ++k) {
2605  sum += input[row*size + k] * inv[k *size + col];
2606  }
2607  if (row != col) {
2608  error_sum += Abs(sum);
2609  }
2610  }
2611  }
2612  return error_sum;
2613 }
TEMPCLUSTER::Cluster
CLUSTER * Cluster
Definition: cluster.cpp:164
FTable
const double FTable[FTABLE_Y][FTABLE_X]
Definition: cluster.cpp:35
ListEntryMatch
int ListEntryMatch(void *arg1, void *arg2)
Definition: cluster.cpp:2250
CLUSTERCONFIG::Confidence
FLOAT64 Confidence
Definition: cluster.h:54
SOLVEFUNC
FLOAT64(* SOLVEFUNC)(CHISTRUCT *, double)
Definition: cluster.cpp:204
PROTOTYPE::Cluster
CLUSTER * Cluster
Definition: cluster.h:76
MakeSample
SAMPLE * MakeSample(CLUSTERER *Clusterer, const FLOAT32 *Feature, inT32 CharID)
Definition: cluster.cpp:456
ClusterPair
tesseract::KDPairInc< float, TEMPCLUSTER * > ClusterPair
Definition: cluster.cpp:168
DELTARATIO
#define DELTARATIO
first_node
#define first_node(l)
Definition: oldlist.h:139
BUCKETS::Count
uinT32 * Count
Definition: cluster.cpp:185
NewEllipticalProto
PROTOTYPE * NewEllipticalProto(inT16 N, CLUSTER *Cluster, STATISTICS *Statistics)
Definition: cluster.cpp:1538
MultipleCharSamples
BOOL8 MultipleCharSamples(CLUSTERER *Clusterer, CLUSTER *Cluster, FLOAT32 MaxIllegal)
Definition: cluster.cpp:2471
GetBuckets
BUCKETS * GetBuckets(CLUSTERER *clusterer, DISTRIBUTION Distribution, uinT32 SampleCount, FLOAT64 Confidence)
Definition: cluster.cpp:1694
MakeClusterer
CLUSTERER * MakeClusterer(inT16 SampleSize, const PARAM_DESC ParamDesc[])
Definition: cluster.cpp:400
Mean
FLOAT32 Mean(PROTOTYPE *Proto, uinT16 Dimension)
Definition: cluster.cpp:650
TRUE
#define TRUE
Definition: capi.h:45
inT16
short inT16
Definition: host.h:33
ComputeStatistics
STATISTICS * ComputeStatistics(inT16 N, PARAM_DESC ParamDesc[], CLUSTER *Cluster)
Definition: cluster.cpp:1418
BUCKETS::NumberOfBuckets
uinT16 NumberOfBuckets
Definition: cluster.cpp:183
STATISTICS::Min
FLOAT32 * Min
Definition: cluster.cpp:174
UniformDensity
FLOAT64 UniformDensity(inT32 x)
Definition: cluster.cpp:1945
DISTRIBUTION
DISTRIBUTION
Definition: cluster.h:58
BUCKETS::Distribution
DISTRIBUTION Distribution
Definition: cluster.cpp:179
MAXDEGREESOFFREEDOM
#define MAXDEGREESOFFREEDOM
Definition: cluster.cpp:229
PROTOTYPE::TotalMagnitude
FLOAT32 TotalMagnitude
Definition: cluster.h:79
CLUSTERER::Root
CLUSTER * Root
Definition: cluster.h:91
ALREADYCLUSTERED
#define ALREADYCLUSTERED
Definition: cluster.h:133
KDDelete
void KDDelete(KDTREE *Tree, FLOAT32 Key[], void *Data)
Definition: kdtree.cpp:265
PARAM_DESC::Range
FLOAT32 Range
Definition: ocrfeatures.h:51
KDStore
void KDStore(KDTREE *Tree, FLOAT32 *Key, void *Data)
Definition: kdtree.cpp:219
CLUSTERER::KDTree
KDTREE * KDTree
Definition: cluster.h:90
CLUSTERER::ParamDesc
PARAM_DESC * ParamDesc
Definition: cluster.h:88
normal
Definition: cluster.h:59
PI
#define PI
Definition: const.h:19
InitBuckets
void InitBuckets(BUCKETS *Buckets)
Definition: cluster.cpp:2289
NewChiStruct
CHISTRUCT * NewChiStruct(uinT16 DegreesOfFreedom, FLOAT64 Alpha)
Definition: cluster.cpp:2332
MINSAMPLESNEEDED
#define MINSAMPLESNEEDED
Definition: cluster.cpp:152
MakeMixedProto
PROTOTYPE * MakeMixedProto(CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *NormalBuckets, FLOAT64 Confidence)
Definition: cluster.cpp:1297
DegreesOfFreedom
uinT16 DegreesOfFreedom(DISTRIBUTION Distribution, uinT16 HistogramBuckets)
Definition: cluster.cpp:2211
PROTOTYPE::Merged
unsigned Merged
Definition: cluster.h:69
NIL_LIST
#define NIL_LIST
Definition: oldlist.h:126
MINBUCKETS
#define MINBUCKETS
Definition: cluster.h:26
FreeCluster
void FreeCluster(CLUSTER *Cluster)
Definition: cluster.cpp:2189
Config
CLUSTERCONFIG Config
Definition: commontraining.cpp:50
InitSampleSearch
#define InitSampleSearch(S, C)
Definition: cluster.h:105
sample::CharID
inT32 CharID
Definition: cluster.h:38
PROTOTYPE::LogMagnitude
FLOAT32 LogMagnitude
Definition: cluster.h:80
MINVARIANCE
#define MINVARIANCE
Definition: cluster.cpp:142
CLUSTERCONFIG::Independence
FLOAT32 Independence
Definition: cluster.h:53
CHISTRUCT::DegreesOfFreedom
uinT16 DegreesOfFreedom
Definition: cluster.cpp:190
ClusteringContext::candidates
TEMPCLUSTER * candidates
Definition: cluster.cpp:198
FTABLE_Y
#define FTABLE_Y
Definition: cluster.cpp:32
MakeKDTree
KDTREE * MakeKDTree(inT16 KeySize, const PARAM_DESC KeyDesc[])
Definition: kdtree.cpp:183
NormalBucket
uinT16 NormalBucket(PARAM_DESC *ParamDesc, FLOAT32 x, FLOAT32 Mean, FLOAT32 StdDev)
Definition: cluster.cpp:2062
Efree
void Efree(void *ptr)
Definition: emalloc.cpp:79
sample::Prototype
unsigned Prototype
Definition: cluster.h:34
ClipToRange
T ClipToRange(const T &x, const T &lower_bound, const T &upper_bound)
Definition: helpers.h:115
FreeBuckets
void FreeBuckets(BUCKETS *Buckets)
Definition: cluster.cpp:2171
memfree
void memfree(void *element)
Definition: freelist.cpp:30
ComputeChiSquared
FLOAT64 ComputeChiSquared(uinT16 DegreesOfFreedom, FLOAT64 Alpha)
Definition: cluster.cpp:1875
uinT8
unsigned char uinT8
Definition: host.h:32
MakePotentialClusters
void MakePotentialClusters(ClusteringContext *context, CLUSTER *Cluster, inT32 Level)
Definition: cluster.cpp:771
PROTOTYPE::Variance
FLOATUNION Variance
Definition: cluster.h:81
ILLEGAL_CHAR
#define ILLEGAL_CHAR
TEMPCLUSTER::Neighbor
CLUSTER * Neighbor
Definition: cluster.cpp:165
NewSimpleProto
PROTOTYPE * NewSimpleProto(inT16 N, CLUSTER *Cluster)
Definition: cluster.cpp:1606
STATISTICS::AvgVariance
FLOAT32 AvgVariance
Definition: cluster.cpp:172
CHISTRUCT::ChiSquared
FLOAT64 ChiSquared
Definition: cluster.cpp:192
tesseract::GenericHeap::Push
void Push(Pair *entry)
Definition: genericheap.h:95
BOOL8
unsigned char BOOL8
Definition: host.h:46
SqrtOf2Pi
#define SqrtOf2Pi
Definition: cluster.cpp:218
MakeDimRandom
void MakeDimRandom(uinT16 i, PROTOTYPE *Proto, PARAM_DESC *ParamDesc)
Definition: cluster.cpp:1358
BUCKETS::SampleCount
uinT32 SampleCount
Definition: cluster.cpp:180
STATISTICS::CoVariance
FLOAT32 * CoVariance
Definition: cluster.cpp:173
pop
LIST pop(LIST list)
Definition: oldlist.cpp:299
CHISTRUCT::Alpha
FLOAT64 Alpha
Definition: cluster.cpp:191
NewMixedProto
PROTOTYPE * NewMixedProto(inT16 N, CLUSTER *Cluster, STATISTICS *Statistics)
Definition: cluster.cpp:1582
TestEllipticalProto
PROTOTYPE * TestEllipticalProto(CLUSTERER *Clusterer, CLUSTERCONFIG *Config, CLUSTER *Cluster, STATISTICS *Statistics)
Definition: cluster.cpp:1111
Mirror
#define Mirror(N, R)
Definition: cluster.cpp:207
PROTOTYPE::Significant
unsigned Significant
Definition: cluster.h:68
search
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:406
FTABLE_X
#define FTABLE_X
Definition: cluster.cpp:31
MAX_FLOAT32
#define MAX_FLOAT32
Definition: host.h:57
MINSAMPLES
#define MINSAMPLES
Definition: cluster.cpp:151
DENSITYFUNC
FLOAT64(* DENSITYFUNC)(inT32)
Definition: cluster.cpp:203
KDTREE
Definition: kdtree.h:49
CLUSTERER::ProtoList
LIST ProtoList
Definition: cluster.h:92
AlphaMatch
int AlphaMatch(void *arg1, void *arg2)
Definition: cluster.cpp:2312
uinT16
unsigned short uinT16
Definition: host.h:34
KDNearestNeighborSearch
void KDNearestNeighborSearch(KDTREE *Tree, FLOAT32 Query[], int QuerySize, FLOAT32 MaxDistance, int *NumberOfResults, void **NBuffer, FLOAT32 DBuffer[])
Definition: kdtree.cpp:321
FreeStatistics
void FreeStatistics(STATISTICS *Statistics)
Definition: cluster.cpp:2159
Odd
#define Odd(N)
Definition: cluster.cpp:206
PROTOTYPE::NumSamples
unsigned NumSamples
Definition: cluster.h:75
StandardDeviation
FLOAT32 StandardDeviation(PROTOTYPE *Proto, uinT16 Dimension)
Definition: cluster.cpp:663
CHIACCURACY
#define CHIACCURACY
FreeClusterer
void FreeClusterer(CLUSTERER *Clusterer)
Definition: cluster.cpp:547
FALSE
#define FALSE
Definition: capi.h:46
PARAM_DESC::HalfRange
FLOAT32 HalfRange
Definition: ocrfeatures.h:52
CLUSTERCONFIG::MinSamples
FLOAT32 MinSamples
Definition: cluster.h:50
mixed
Definition: cluster.h:45
FreePrototype
void FreePrototype(void *arg)
Definition: cluster.cpp:588
destroy
LIST destroy(LIST list)
Definition: oldlist.cpp:182
NewSphericalProto
PROTOTYPE * NewSphericalProto(uinT16 N, CLUSTER *Cluster, STATISTICS *Statistics)
Definition: cluster.cpp:1505
STATISTICS::Max
FLOAT32 * Max
Definition: cluster.cpp:175
FLOAT32
float FLOAT32
Definition: host.h:44
PROTOTYPE::Distrib
DISTRIBUTION * Distrib
Definition: cluster.h:77
FLOAT64
double FLOAT64
Definition: host.h:45
sample::SampleCount
unsigned SampleCount
Definition: cluster.h:35
void_proc
void(* void_proc)(...)
Definition: cutil.h:66
FindNearestNeighbor
CLUSTER * FindNearestNeighbor(KDTREE *Tree, CLUSTER *Cluster, FLOAT32 *Distance)
Definition: cluster.cpp:804
ClusterSamples
LIST ClusterSamples(CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
Definition: cluster.cpp:513
FLOATUNION::Spherical
FLOAT32 Spherical
Definition: cluster.h:63
PROTOTYPE::Mean
FLOAT32 * Mean
Definition: cluster.h:78
OptimumNumberOfBuckets
uinT16 OptimumNumberOfBuckets(uinT32 SampleCount)
Definition: cluster.cpp:1838
DoError
void DoError(int Error, const char *Message)
Definition: danerror.cpp:42
destroy_nodes
void destroy_nodes(LIST list, void_dest destructor)
Definition: oldlist.cpp:199
PROTOTYPE::Magnitude
FLOATUNION Magnitude
Definition: cluster.h:82
push
LIST push(LIST list, void *element)
Definition: oldlist.cpp:317
CreateClusterTree
void CreateClusterTree(CLUSTERER *Clusterer)
Definition: cluster.cpp:704
inT32
int inT32
Definition: host.h:35
CLUSTERCONFIG::MagicSamples
int MagicSamples
Definition: cluster.h:55
FreeKDTree
void FreeKDTree(KDTREE *Tree)
Definition: kdtree.cpp:350
DistributionOK
BOOL8 DistributionOK(BUCKETS *Buckets)
Definition: cluster.cpp:2131
HOTELLING
#define HOTELLING
Definition: cluster.cpp:30
ComputePrototypes
void ComputePrototypes(CLUSTERER *Clusterer, CLUSTERCONFIG *Config)
Definition: cluster.cpp:930
BUCKETS::Bucket
uinT16 Bucket[BUCKETTABLESIZE]
Definition: cluster.cpp:184
tprintf
#define tprintf(...)
Definition: tprintf.h:31
PARAM_DESC::MidRange
FLOAT32 MidRange
Definition: ocrfeatures.h:53
INITIALDELTA
#define INITIALDELTA
PARAM_DESC::Circular
inT8 Circular
Definition: ocrfeatures.h:47
NORMALEXTENT
#define NORMALEXTENT
Definition: cluster.cpp:161
PARAM_DESC::NonEssential
inT8 NonEssential
Definition: ocrfeatures.h:48
sample::Clustered
unsigned Clustered
Definition: cluster.h:33
CLUSTERER::bucket_cache
BUCKETS * bucket_cache[DISTRIBUTION_COUNT][MAXBUCKETS+1 - MINBUCKETS]
Definition: cluster.h:95
BUCKETTABLESIZE
#define BUCKETTABLESIZE
Definition: cluster.cpp:160
NextSample
CLUSTER * NextSample(LIST *SearchState)
Definition: cluster.cpp:626
MakeBuckets
BUCKETS * MakeBuckets(DISTRIBUTION Distribution, uinT32 SampleCount, FLOAT64 Confidence)
Definition: cluster.cpp:1741
LOOKUPTABLESIZE
#define LOOKUPTABLESIZE
Definition: cluster.cpp:228
tesseract::GenericHeap::Pop
bool Pop(Pair *entry)
Definition: genericheap.h:118
MakeEllipticalProto
PROTOTYPE * MakeEllipticalProto(CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *Buckets)
Definition: cluster.cpp:1255
CLUSTERCONFIG::ProtoStyle
PROTOSTYLE ProtoStyle
Definition: cluster.h:49
InvertMatrix
double InvertMatrix(const float *input, int size, float *inv)
Definition: cluster.cpp:2528
iterate
#define iterate(l)
Definition: oldlist.h:159
MakeDegenerateProto
PROTOTYPE * MakeDegenerateProto(uinT16 N, CLUSTER *Cluster, STATISTICS *Statistics, PROTOSTYLE Style, inT32 MinSamples)
Definition: cluster.cpp:1069
ChiArea
FLOAT64 ChiArea(CHISTRUCT *ChiParams, FLOAT64 x)
Definition: cluster.cpp:2424
PROTOTYPE::Style
unsigned Style
Definition: cluster.h:74
MAXNEIGHBORS
#define MAXNEIGHBORS
MINALPHA
#define MINALPHA
CLUSTERER::NumChar
inT32 NumChar
Definition: cluster.h:93
sample
Definition: cluster.h:32
Integral
FLOAT64 Integral(FLOAT64 f1, FLOAT64 f2, FLOAT64 Dx)
Definition: cluster.cpp:1964
uinT32
unsigned int uinT32
Definition: host.h:36
MakeSphericalProto
PROTOTYPE * MakeSphericalProto(CLUSTERER *Clusterer, CLUSTER *Cluster, STATISTICS *Statistics, BUCKETS *Buckets)
Definition: cluster.cpp:1218
PARAM_DESC::Min
FLOAT32 Min
Definition: ocrfeatures.h:49
BUCKETS::ExpectedCount
FLOAT32 * ExpectedCount
Definition: cluster.cpp:186
NumBucketsMatch
int NumBucketsMatch(void *arg1, void *arg2)
Definition: cluster.cpp:2233
sample::Right
struct sample * Right
Definition: cluster.h:37
Emalloc
void * Emalloc(int Size)
Definition: emalloc.cpp:47
BUCKETS::Confidence
FLOAT64 Confidence
Definition: cluster.cpp:181
sample::Left
struct sample * Left
Definition: cluster.h:36
MakeNewCluster
CLUSTER * MakeNewCluster(CLUSTERER *Clusterer, TEMPCLUSTER *TempCluster)
Definition: cluster.cpp:842
MAXDISTANCE
#define MAXDISTANCE
Independent
BOOL8 Independent(PARAM_DESC ParamDesc[], inT16 N, FLOAT32 *CoVariance, FLOAT32 Independence)
Definition: cluster.cpp:1647
AdjustBuckets
void AdjustBuckets(BUCKETS *Buckets, uinT32 NewSampleCount)
Definition: cluster.cpp:2266
RootOf
#define RootOf(T)
Definition: kdtree.h:58
MAXBUCKETS
#define MAXBUCKETS
Definition: cluster.h:27
PARAM_DESC::Max
FLOAT32 Max
Definition: ocrfeatures.h:50
ClusterHeap
tesseract::GenericHeap< ClusterPair > ClusterHeap
Definition: cluster.cpp:169
BUCKETS::ChiSquared
FLOAT64 ChiSquared
Definition: cluster.cpp:182
FillBuckets
void FillBuckets(BUCKETS *Buckets, CLUSTER *Cluster, uinT16 Dim, PARAM_DESC *ParamDesc, FLOAT32 Mean, FLOAT32 StdDev)
Definition: cluster.cpp:1990
ClusteringContext::heap
ClusterHeap * heap
Definition: cluster.cpp:197
sample::Mean
FLOAT32 Mean[1]
Definition: cluster.h:39
CLUSTERER::NumberOfSamples
inT32 NumberOfSamples
Definition: cluster.h:89
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:84
MakeDimUniform
void MakeDimUniform(uinT16 i, PROTOTYPE *Proto, STATISTICS *Statistics)
Definition: cluster.cpp:1382
Solve
FLOAT64 Solve(SOLVEFUNC Function, void *FunctionParams, FLOAT64 InitialGuess, FLOAT64 Accuracy)
Definition: cluster.cpp:2358
CLUSTERER::SampleSize
inT16 SampleSize
Definition: cluster.h:87
UniformBucket
uinT16 UniformBucket(PARAM_DESC *ParamDesc, FLOAT32 x, FLOAT32 Mean, FLOAT32 StdDev)
Definition: cluster.cpp:2097
CLUSTERCONFIG::MaxIllegal
FLOAT32 MaxIllegal
Definition: cluster.h:51
MergeClusters
inT32 MergeClusters(inT16 N, register PARAM_DESC ParamDesc[], register inT32 n1, register inT32 n2, register FLOAT32 m[], register FLOAT32 m1[], register FLOAT32 m2[])
PROTOTYPE::Weight
FLOATUNION Weight
Definition: cluster.h:83
NormalDensity
FLOAT64 NormalDensity(inT32 x)
Definition: cluster.cpp:1929
FreeProtoList
void FreeProtoList(LIST *ProtoList)
Definition: cluster.cpp:574
PROTOSTYLE
PROTOSTYLE
Definition: cluster.h:44
Abs
#define Abs(N)
Definition: cluster.cpp:208
MakePrototype
PROTOTYPE * MakePrototype(CLUSTERER *Clusterer, CLUSTERCONFIG *Config, CLUSTER *Cluster)
Definition: cluster.cpp:975
FLOATUNION::Elliptical
FLOAT32 * Elliptical
Definition: cluster.h:64
KDWalk
void KDWalk(KDTREE *Tree, void_proc action, void *context)
Definition: kdtree.cpp:331