segmentation
•All Data Structures Namespaces Files Functions Variables Modules Pages
ms.h
1 /*******************************************************
2 
3  Mean Shift Analysis Library
4  =============================================
5 
6  The mean shift library is a collection of routines
7  that use the mean shift algorithm. Using this algorithm,
8  the necessary output will be generated needed
9  to analyze a given input set of data.
10 
11  MeanShift Base Class:
12  ====================
13 
14  The mean shift library of routines is realized
15  via the creation of a MeanShift base class. This class
16  provides a mechanism for calculating the mean shift vector
17  at a specified data point, using an arbitrary N-dimensional
18  data set, and a user-defined kernel.
19 
20  For image processing the mean shift base class also allows
21  for the definition of a data set that is on a two-dimensional
22  lattice. The amount of time needed to compute the mean shift
23  vector using such a data set is much less than that of an
24  arbitrary one. Because images usually contain many data points,
25  defining the image input data points as being on a lattice
26  greatly improves computation time and makes algorithms such
27  as image filtering practical.
28 
29  The MeanShift class prototype is provided below. Its
30  definition is provided in 'ms.cc'.
31 
32 The theory is described in the papers:
33 
34  D. Comaniciu, P. Meer: Mean Shift: A robust approach toward feature
35  space analysis.
36 
37  C. Christoudias, B. Georgescu, P. Meer: Synergism in low level vision.
38 
39 and they are is available at:
40  http://www.caip.rutgers.edu/riul/research/papers/
41 
42 Implemented by Chris M. Christoudias, Bogdan Georgescu
43 ********************************************************/
44 
45 #ifndef MS_H
46 #define MS_H
47 
48 //Included needed libraries
49 
50 //Include type definitions
51 #include "tdef.h"
52 
53 //include mean shift system used
54 //for function timing and system output
55 #include "msSys.h"
56 
57 //Include Debugging Constant
58 //#define DEBUG
59 
60 //Define Prompt - Prompts user on progress of Mean Shift algorithm
61 #define PROMPT
62 
63 //Define Show Progress - Prompts user on percent complete of a given
64 // mean shift algorithm
65 //#define SHOW_PROGRESS
66 
67 //Define Progress Rate - Indicates the number of convergences before
68 // checking progress
69 #define PROGRESS_RATE 100
70 
71 // Define Macros
72 #define SWAP(d_a, d_b) temp=(d_a);(d_a)=(d_b);(d_b)=temp;
73 
74 // Define Structures
75 
76  //k-Dimensional Binary Search Tree
77 struct tree {
78  float *x;
79  tree *right;
80  tree *left;
81  tree *parent;
82 };
83 
84  // User Defined Weight Function
85 struct userWeightFunct {
86 
87  double *w;
88  double halfWindow;
89  int sampleNumber;
90  int subspace;
91  userWeightFunct *next;
92 
93 };
94 
95 //Define class state structure
96 struct ClassStateStruct {
97  bool KERNEL_DEFINED;
98  bool INPUT_DEFINED;
99  bool LATTICE_DEFINED;
100  bool OUTPUT_DEFINED;
101 };
102 
103 // Define Constants
104 
105  // Threshold
106 const double EPSILON = 0.01; // define threshold (approx. Value of Mh at a peak or plateau)
107 const double MU = 0.05; // define threshold required that window is near convergence
108 const double TC_DIST_FACTOR = 0.5; // cluster search windows near convergence that are a distance
109  // h[i]*TC_DIST_FACTOR of one another (transitive closure)
110 const double SQ_TC_DFACTOR = 0.0625; // (TC_DIST_FACTOR)^2
111 const int LIMIT = 100; // define max. # of iterations to find mode
112 
113  // Gaussian Lookup Table
114 const int GAUSS_NUM_ELS = 16; // take 16 samples of exp(-u/2)
115 const double GAUSS_LIMIT = 2.9; // GAUSS_LIMIT = c
116 const double GAUSS_INCREMENT = GAUSS_LIMIT*GAUSS_LIMIT/GAUSS_NUM_ELS;
117  // GAUSS_INCREMENT = (c^2)/(# of samples)
118 
119  // Numerical Analysis
120 const double DELTA = 0.00001; // used for floating point to integer conversion
121 
122 //MeanShift Prototype
123 class MeanShift {
124 
125  public:
126 
127  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
128  /* Class Constructor and Destructor */
129  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
130 
131  MeanShift( void ); //Default Constructor
132  ~MeanShift( void ); //Class Destructor
133 
134  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
135  /* Creation/Initialization of Mean Shift Kernel */
136  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
137 
138  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
139  //<--------------------------------------------------->|//
140  //| |//
141  //| Method Name: |//
142  //| ============ |//
143  //| * Define Kernel * |//
144  //| |//
145  //<--------------------------------------------------->|//
146  //| |//
147  //| Description: |//
148  //| ============ |//
149  //| |//
150  //| Uploads a custom kernel into the private data |//
151  //| members of the mean shift class. This kernel is |//
152  //| used by the mean shift class to perform mean |//
153  //| shift. |//
154  //| |//
155  //| In order to create a valid kernel the following |//
156  //| argumens must be provided this method: |//
157  //| |//
158  //| <* kernel *> |//
159  //| A one dimensional array of type kernelType used |//
160  //| to specify the kernel type (Uniform, Gaussian, |//
161  //| or User Defined) of a given subspace of the input|//
162  //| set. Entry i of kernel correlates to the i-th |//
163  //| subspace of the input data set. |//
164  //| |//
165  //| <* h *> |//
166  //| A one dimensional array of floating point numb- |//
167  //| ers that are used to normalize the input data |//
168  //| set, each bandwidth specifying the relative imp- |//
169  //| ortance of a subspace of the input data set. |//
170  //| |//
171  //| <* kp *> |//
172  //| An integer that specifies the number of sub- |//
173  //| contained by the input data set. Both P and h |//
174  //| therefore consist of kp entries. |//
175  //| |//
176  //<--------------------------------------------------->|//
177  //| |//
178  //| Usage: |//
179  //| ====== |//
180  //| DefineKernel(kernel, h, P, kp) |//
181  //| |//
182  //<--------------------------------------------------->|//
183  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
184 
185  void DefineKernel(kernelType*, float*, int*, int);
186 
187  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
188  //<--------------------------------------------------->|//
189  //| |//
190  //| Method Name: |//
191  //| ============ |//
192  //| * Add Weight Function * |//
193  //| |//
194  //<--------------------------------------------------->|//
195  //| |//
196  //| Description: |//
197  //| ============ |//
198  //| |//
199  //| Each subspace specified as User Defined is un- |//
200  //| quely defined by a correlating weight function |//
201  //| which is user defined. |//
202  //| |//
203  //| A weight function w(u) exhibits the following |//
204  //| properties: |//
205  //| |//
206  //| (1) w(u) = w(-u) |//
207  //| (2) u = ((x_i-y_k)^2)/(h^2) (see docs) |//
208  //| (3) w(u) = 0, for |u| >= halfWindow |//
209  //| |//
210  //| To add a weight function to the mean shift class |//
211  //| the following must be specified: |//
212  //| |//
213  //| <* g() *> |//
214  //| A pointer the weight function w(u) exhibiting |//
215  //| the above properties. |//
216  //| |//
217  //| <* halfWindow *> |//
218  //| A floating point number specifying where w(u) |//
219  //| exists (is non zero). [See Property 3 Above] |//
220  //| |//
221  //| <* sampleNumber *> |//
222  //| An integer used to specify the number of samples |//
223  //| used to describe w(u). Linear interpolation is |//
224  //| used during the mean shift calculation using the |//
225  //| the samples of w(u) to determine the value of w |//
226  //| at a location |u| < halfWindow. |//
227  //| |//
228  //| <* subspace *> |//
229  //| An integer specifying which kernel w(u) defines. |//
230  //| |//
231  //| Weight functions are accounted for every time |//
232  //| a new kernel is created. |//
233  //| |//
234  //| If a weight function is added to non-existing |//
235  //| subspace of the input data set (example: the |//
236  //| input data set containes 3 subspaces and this |//
237  //| method is given subspace = 4) then the weight |//
238  //| defintion will simply be ignored by the mean |//
239  //| shift class. |//
240  //| |//
241  //| If a subspace is declared as kernel type User |//
242  //| Defined and a weight function is not defined |//
243  //| for that subspace a fatal error will occur. |//
244  //| |//
245  //<--------------------------------------------------->|//
246  //| |//
247  //| Usage: |//
248  //| ====== |//
249  //| AddWeightFunction(g(u) , halfWindow, |//
250  //| sampleNumber, subspace); |//
251  //| |//
252  //<--------------------------------------------------->|//
253  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
254 
255  void AddWeightFunction(double g(double), float, int, int);
256 
257  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
258  //<--------------------------------------------------->|//
259  //| |//
260  //| Method Name: |//
261  //| ============ |//
262  //| * Clear Weight Functions * |//
263  //| |//
264  //<--------------------------------------------------->|//
265  //| |//
266  //| Description: |//
267  //| ============ |//
268  //| |//
269  //| Removes all user defined weight functions added |//
270  //| using method AddWeightFunction() from the |//
271  //| private data members of the mean shift class. |//
272  //| |//
273  //<--------------------------------------------------->|//
274  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
275 
276  void ClearWeightFunctions( void );
277 
278  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
279  /* Input Data Set Declaration */
280  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
281 
282  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
283  //<--------------------------------------------------->|//
284  //| |//
285  //| Method Name: |//
286  //| ============ |//
287  //| * Define Input * |//
288  //| |//
289  //<--------------------------------------------------->|//
290  //| |//
291  //| Description: |//
292  //| ============ |//
293  //| |//
294  //| Uploads a one dimensional array containing L |//
295  //| N-dimensional data points into the mean shift |//
296  //| class. |//
297  //| |//
298  //| An input data set is specified by: |//
299  //| |//
300  //| <* x *> |//
301  //| A pointer to a floating point array. |//
302  //| |//
303  //| <* L *> |//
304  //| The number of data points stored by x. |//
305  //| |//
306  //| <* N *> |//
307  //| The dimension of the data points stored by x. |//
308  //| |//
309  //| The input x has the following format: |//
310  //| |//
311  //| x = <x11, x12,..., x1N,..., xL1, xL2,..., xLN> |//
312  //| |//
313  //<--------------------------------------------------->|//
314  //| |//
315  //| Usage: |//
316  //| ====== |//
317  //| DefineInput(x, L, N) |//
318  //| |//
319  //<--------------------------------------------------->|//
320  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
321 
322  void DefineInput(float*, int, int);
323 
324  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
325  //<--------------------------------------------------->|//
326  //| |//
327  //| Method Name: |//
328  //| ============ |//
329  //| * Define Lattice Input * |//
330  //| |//
331  //<--------------------------------------------------->|//
332  //| |//
333  //| Description: |//
334  //| ============ |//
335  //| |//
336  //| Use this method to specify define an input data |//
337  //| set defined on a lattice. |//
338  //| |//
339  //| The arguments of this method are: |//
340  //| |//
341  //| <* x *> |//
342  //| A pointer to a floating point array containing |//
343  //| height*width, N-dimensional data points. |//
344  //| |//
345  //| <* height *> |//
346  //| An integer specifying the height of the lattice. |//
347  //| |//
348  //| <* width *> |//
349  //| An integer specifying the width of the lattice. |//
350  //| |//
351  //| <* N *> |//
352  //| The dimension of the data points stored by x. |//
353  //| |//
354  //<--------------------------------------------------->|//
355  //| |//
356  //| Usage: |//
357  //| ====== |//
358  //| DefineLInput(x, height, width, N) |//
359  //| |//
360  //<--------------------------------------------------->|//
361  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
362 
363  void DefineLInput(float*, int, int, int);
364 
365  /*/\/\/\/\/\/\/\/\/\/\/\*/
366  /* Lattice Weight Map */
367  /*\/\/\/\/\/\/\/\/\/\/\/*/
368 
369  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
370  //<--------------------------------------------------->|//
371  //| |//
372  //| Method Name: |//
373  //| ============ |//
374  //| * Set Lattice Weight Map * |//
375  //| |//
376  //<--------------------------------------------------->|//
377  //| |//
378  //| Description: |//
379  //| ============ |//
380  //| |//
381  //| Uploads weight map specifying for each data |//
382  //| point a value used to weight the uniform kernel |//
383  //| when computing mean shift. |//
384  //| |//
385  //| The arguments to this method are: |//
386  //| |//
387  //| <* weightMap *> |//
388  //| A floating point array of size L specifying for |//
389  //| each data point a weight. |//
390  //| |//
391  //| Note: DefineLInput must be called prior to call- |//
392  //| ing this method. DefineLInput is used to |//
393  //| define the dimensions of the input data |//
394  //| set. |//
395  //| |//
396  //| |//
397  //| The weight map is used to weight the uniform |//
398  //| kernel used to computing meanshift on a data |//
399  //| point situated on a lattice. Alternatively, a |//
400  //| weight function may defined, however, if speed |//
401  //| is an issue, the lattice may be exploited to |//
402  //| result in a faster implementation of a weighted |//
403  //| kernel. |//
404  //| |//
405  //<--------------------------------------------------->|//
406  //| |//
407  //| Usage: |//
408  //| ====== |//
409  //| SetLatticeWeightMap(weightMap) |//
410  //| |//
411  //<--------------------------------------------------->|//
412  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
413 
414  void SetLatticeWeightMap(float*);
415 
416  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
417  //<--------------------------------------------------->|//
418  //| |//
419  //| Method Name: |//
420  //| ============ |//
421  //| * Remove Lattice Weight Map * |//
422  //| |//
423  //<--------------------------------------------------->|//
424  //| |//
425  //| Description: |//
426  //| ============ |//
427  //| |//
428  //| Removes lattice weight map. An error is NOT |//
429  //| flagged if a weight map was not defined prior |//
430  //| to calling this method. |//
431  //| |//
432  //<--------------------------------------------------->|//
433  //| |//
434  //| Usage: |//
435  //| ====== |//
436  //| RemoveLatticeWeightMap(weightMap) |//
437  //| |//
438  //<--------------------------------------------------->|//
439  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
440 
441  void RemoveLatticeWeightMap(void);
442 
443  /*/\/\/\/\/\/\/\/\/\/\/\/\*/
444  /* Mean Shift Operations */
445  /*\/\/\/\/\/\/\/\/\/\/\/\/*/
446 
447  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
448  //<--------------------------------------------------->|//
449  //| |//
450  //| Method Name: |//
451  //| ============ |//
452  //| * Mean Shift Vector * |//
453  //| |//
454  //<--------------------------------------------------->|//
455  //| |//
456  //| Description: |//
457  //| ============ |//
458  //| |//
459  //| If a kernel is created and input is uploaded, |//
460  //| this method calcualtes the mean shift vector, |//
461  //| Mh, at specific data point yk. |//
462  //| |//
463  //| The arguments of this method are: |//
464  //| |//
465  //| <* Mh *> |//
466  //| An array of N doubles storing the N dimensional |//
467  //| mean shift vector. |//
468  //| |//
469  //| <* yk *> |//
470  //| An array of N doubles storing the N dimensional |//
471  //| data point where the mean shift vector is to be |//
472  //| calculate. |//
473  //| |//
474  //<--------------------------------------------------->|//
475  //| |//
476  //| Usage: |//
477  //| ====== |//
478  //| msVector(Mh, yk) |//
479  //| |//
480  //<--------------------------------------------------->|//
481  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
482 
483  void msVector(double*, double*);
484 
485  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
486  //<--------------------------------------------------->|//
487  //| |//
488  //| Method Name: |//
489  //| ============ |//
490  //| * Lattice Mean Shift Vector * |//
491  //| |//
492  //<--------------------------------------------------->|//
493  //| |//
494  //| Description: |//
495  //| ============ |//
496  //| |//
497  //| If a kernel is created and input is uploaded, |//
498  //| this method calcualtes the mean shift vector, |//
499  //| Mh, at specific data point yk, assuming that the |//
500  //| data set exhists on a height x width two dim- |//
501  //| ensional lattice. |//
502  //| |//
503  //| The arguments of this method are: |//
504  //| |//
505  //| <* Mh *> |//
506  //| An array of N doubles storing the N dimensional |//
507  //| mean shift vector. |//
508  //| |//
509  //| <* yk *> |//
510  //| An array of N doubles storing the N dimensional |//
511  //| data point where the mean shift vector is to be |//
512  //| calculate. |//
513  //| |//
514  //| The height and width of the lattice must be |//
515  //| specified using DefineLattice() method. If this |//
516  //| is not performed prior to calling this method a |//
517  //| fatal error will be flagged. |//
518  //| |//
519  //<--------------------------------------------------->|//
520  //| |//
521  //| Usage: |//
522  //| ====== |//
523  //| latticeMSVector(Mh, yk) |//
524  //| |//
525  //<--------------------------------------------------->|//
526  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
527 
528  void latticeMSVector(double*, double*);
529 
530  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
531  //<--------------------------------------------------->|//
532  //| |//
533  //| Method Name: |//
534  //| ============ |//
535  //| * Find Mode * |//
536  //| |//
537  //<--------------------------------------------------->|//
538  //| |//
539  //| Description: |//
540  //| ============ |//
541  //| |//
542  //| If a kernel is created and input is uploaded, |//
543  //| this method calcualtes the mode of a specified |//
544  //| data point yk. |//
545  //| |//
546  //| The arguments of this method are: |//
547  //| |//
548  //| <* mode *> |//
549  //| An array of N doubles storing the N dimensional |//
550  //| mode of yk. |//
551  //| |//
552  //| <* yk *> |//
553  //| An array of N doubles storing the N dimensional |//
554  //| data point where the mean shift vector is to be |//
555  //| calculate. |//
556  //| |//
557  //<--------------------------------------------------->|//
558  //| |//
559  //| Usage: |//
560  //| ====== |//
561  //| FindMode(mode, yk) |//
562  //| |//
563  //<--------------------------------------------------->|//
564  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
565 
566  void FindMode(double*, double*);
567 
568  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
569  //<--------------------------------------------------->|//
570  //| |//
571  //| Method Name: |//
572  //| ============ |//
573  //| * Find Lattice Mode * |//
574  //| |//
575  //<--------------------------------------------------->|//
576  //| |//
577  //| Description: |//
578  //| ============ |//
579  //| |//
580  //| If a kernel is created and input is uploaded, |//
581  //| this method calcualtes the mode of a specified |//
582  //| data point yk, assuming that the data set |//
583  //| exhists on a height x width two dimensional |//
584  //| lattice. |//
585  //| |//
586  //| The arguments of this method are: |//
587  //| |//
588  //| <* mode *> |//
589  //| An array of N doubles storing the N dimensional |//
590  //| mode of yk. |//
591  //| |//
592  //| <* yk *> |//
593  //| An array of N doubles storing the N dimensional |//
594  //| data point where the mean shift vector is to be |//
595  //| calculate. |//
596  //| |//
597  //| The height and width of the lattice must be |//
598  //| specified using DefineLattice() method. If this |//
599  //| is not performed prior to calling this method a |//
600  //| fatal error will be flagged. |//
601  //| |//
602  //<--------------------------------------------------->|//
603  //| |//
604  //| Usage: |//
605  //| ====== |//
606  //| FindLMode(mode, yk) |//
607  //| |//
608  //<--------------------------------------------------->|//
609  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
610 
611  void FindLMode(double*, double*);
612 
613  /*/\/\/\/\/\/\/\/\/\/\/\/\/\*/
614  /* Error Handler Mechanism */
615  /*/\/\/\/\/\/\/\/\/\/\/\/\/\*/
616 
617  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
618  //<--------------------------------------------------->|//
619  //| |//
620  //| Description: |//
621  //| ============ |//
622  //| |//
623  //| ErrorMessage is an error message that is set by |//
624  //| a mean shift library class when an error occurs. |//
625  //| |//
626  //<--------------------------------------------------->|//
627  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
628 
629  char *ErrorMessage;
630 
631  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
632  //<--------------------------------------------------->|//
633  //| |//
634  //| Description: |//
635  //| ============ |//
636  //| |//
637  //| ErrorStatus indicates if an error has occured as |//
638  //| a result of improper use of a mean shift library |//
639  //| class method or because of insufficient resour- |//
640  //| ces. ErrorStatus is set to EL_ERROR (ErrorStatus |//
641  //| = 1) if an error has occured. If no error occur- |//
642  //| ed when calling a particular method ErrorStatus |//
643  //| is set to EL_OKAY (ErrorStatus = 0). |//
644  //| |//
645  //<--------------------------------------------------->|//
646  //--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//--\\||//
647 
648  ErrorLevel ErrorStatus;
649 
650  protected:
651 
652  //==========================
653  // *** Protected Methods ***
654  //==========================
655 
656  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
657  /* Mean Shift: Using kd-Tree */
658  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
659 
661  // <<*>> Usage: MSVector(Mh, yk) <<*>> //
663 
664  void MSVector (double*, double*); // Computes the mean shift vector at a specified
665  // window location yk in the data set x given
666  // the vector yk
667  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
668  /* Mean Shift: Using Lattice */
669  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
670 
672  // <<*>> Usage: LatticeMSVector(Mh, yk) <<*>> //
674 
675  void LatticeMSVector (double*, double*); // Uses the lattice defined by DefineLattice to compute the
676  // mean shift vector at a specified window location yk
677 
679  // <<*>> Usage: OptLatticeMSVector(Mh, yk) <<*>> //
681 
682  void OptLatticeMSVector (double*, double*); // Uses the lattice defined by DefineLattice to compute the
683  // mean shift vector at a specified window location yk using
684  // the basin of attraction optimization for better performace
685  // during mean shift filtering - used by a derived class
686 
687  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
688  /* Kernel-Input Data Consistency */
689  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
690 
692  // <<*>> Usage: classConsistencyCheck(N) <<*>> //
694 
695  void classConsistencyCheck(int, bool); // checks to see that a kernel is created and input defined, as
696  // well as the specified dimension of the data set matches that of
697  // the kernel, if not an error is flagged and the program is halted
698 
699  /*/\/\/\/\/\/\/\/\/\/\/\*/
700  /* Class Error Handler */
701  /*\/\/\/\/\/\/\/\/\/\/\/*/
702 
704  // <<*>> Usage: ErrorHandler( <<*>> //
705  // className, functName, errMessage) //
707 
708  void ErrorHandler(const char*, const char*, const char*); // flags an error and halts the system
709 
710 
711  //===============================
712  // *** Protected Data Members ***
713  //===============================
714 
715  //##########################################
716  //######### MEAN SHIFT SYSTEM ##########
717  //##########################################
718 
719  msSystem msSys; // used for function timing and system output
720 
721  //##########################################
722  //######### INPUT DATA PARAMETERS ##########
723  //##########################################
724 
725  int L, N, kp, *P; // length, dimension, subspace number, and subspace dimensions
726 
727 
728  //##########################################
729  //######### INPUT DATA STORAGE ##########
730  //##########################################
731 
733  float *data; // memory allocated for data points stored by tree nodes
734  // when used by the lattice data structure data does not store
735  // the lattice information; format of data:
736  // data = <x11, x12, ..., x1N,...,xL1, xL2, ..., xLN>
737  // in the case of the lattice the i in data(i,j) corresponds
738 
739  //##########################################
740  //######## LATTICE DATA STRUCTURE ##########
741  //##########################################
742 
744  int height, width; // Height and width of lattice
745 
746  //##########################################
747  //######### KERNEL DATA STRUCTURE ##########
748  //##########################################
749 
750  float *h; // bandwidth vector
751 
752  float *offset; // defines bandwidth offset caused by the use of a Gaussian kernel
753  // (for example)
754 
755  //##########################################
756  //######### BASIN OF ATTRACTION ##########
757  //##########################################
758 
759  unsigned char *modeTable; // Assigns a marking to each data point specifying whether
760  // or not it has been assigned a mode. These labels are:
761  // modeTable[i] = 0 - data point i is not associated with a mode
762  // modeTable[i] = 1 - data point i is associated with a mode
763  // modeTable[i] = 2 - data point i is associated with a mode
764  // however its mode is yet to be determined
765 
766  int *pointList; // a list of data points that due to basin of attraction will
767  // converge to the same mode as the mode that mean shift is
768  // currently being applied to
769 
770  int pointCount; // the number of points stored by the point list
771 
772 
773  //##########################################
774  //######### WEIGHT MAP USED ##########
775  //######### WHEN COMPUTING MEAN ##########
776  //######### SHIFT ON A LATTICE ##########
777  //##########################################
778 
779  float *weightMap; // weight map that may be used to weight the kernel
780  // upon performing mean shift on a lattice
781 
782  bool weightMapDefined; // used to indicate if a lattice weight map has been
783  // defined
784 
785  //##########################################
786  //####### CLASS STATE ########
787  //##########################################
788 
789  ClassStateStruct class_state; //specifies the state of the class(i.e if data has been loaded into
790  //the class, if a kernel has been defined, etc.)
791 
792  private:
793 
794  //========================
795  // *** Private Methods ***
796  //========================
797 
798  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
799  /* Kernel Creation/Manipulation */
800  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
801 
802  void generateLookupTable ( void ); // Generates Weight Function Lookup Table
803 
804  void DestroyKernel ( void ); // Destroys mean shift kernel, re-initializes kernel
805 
806 
807  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
808  /* Input Data Initialization/Destruction */
809  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
810 
811  void CreateBST ( void ); // Upload input into a kd-BST
812 
813  void InitializeInput (float*); // Allocates memory for and initializes the input data structure
814 
815  void ResetInput ( void ); // de-allocate memory for and re-initialize input data structure
816  // and mode structure
817 
818  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
819  /* k-dimensional Binary Search Tree */
820  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
821 
823  tree *BuildKDTree (tree*, int, int, tree* ); // Builds a kd tree given a subset of points initialized
824  // at depth 0 (dimension 0) (for Tree Structure)
825 
826  void QuickMedian (tree*, int, int, int ); // Finds the median tree in a forest of trees using
827  // dimension d, placing the median tree in the array of tree
828  // nodes at L/2, in which all trees to the left of the median tree
829  // have values less than that of the median tree in dimension d
830  // and all trees having values greater than that of the median tree
831  // in dimension d are placd to the right of this tree -
832  // This algorithm is used by BuildKDTree to construct a balanced tree
833 
834  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
835  /* Mean Shift: Using kd-Tree */
836  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
837 
838  void uniformSearch (tree*, int, double*, double*); // uses kdbst to perform range search on input data,
839  // computing the weighted sum of these points using
840  // a uniform kernel and storing the result into Mh
841  // (called by uniformMSVector)
842 
843  void generalSearch (tree*, int, double*, double*); // uses kdbst to perform range search on input data,
844  // computing the weighted sum of these points using
845  // a general kernel and storing the result into Mh
846  // (called by generalMSVector)
847 
848  /*/\/\/\/\/\/\/\/\/\/\/\/\/\/\*/
849  /* Mean Shift: Using Lattice */
850  /*\/\/\/\/\/\/\/\/\/\/\/\/\/\/*/
851 
852  void uniformLSearch (double *, double *); // given a center location and mean shift vector, a lattice
853  // search is performed to compute the mean shift vector
854  // using a uniform kernel
855 
856  void optUniformLSearch(double *, double *); // given a center location and mean shift vector, a lattice
857  // search is performed to compute the mean shift vector
858  // using a uniform kernel and the basin of attraction
859  // optimization for better performance
860 
861  void generalLSearch (double *, double *); // given a center location and mean shift vector, a lattice
862  // search is performed to compute the mean shift vector
863  // using a general kernel
864 
865  void optGeneralLSearch(double *, double *); // given a center location and mean shift vector, a lattice
866  // search is performed to compute the mean shift vector
867  // using a general kernel and the basin of attraction
868  // optimization for better performance
869 
870 
871  //=============================
872  // *** Private Data Members ***
873  //=============================
874 
875  //##########################################
876  //######### KERNEL DATA STRUCTURE ##########
877  //##########################################
878 
879  kernelType *kernel; // kernel types for each subspace S[i]
880 
881  double **w; // weight function lookup table
882 
883  double *increment; // increment used by weight hashing function
884 
885  bool uniformKernel; // flag used to indicate if the kernel is uniform or not
886 
887  userWeightFunct *head, *cur; // user defined weight function linked list
888 
889 
890  //##########################################
891  //######### INPUT DATA STORAGE ##########
892  //##########################################
893 
895  tree *root; // root of kdBST used to store input
896 
897  tree *forest; // memory allocated for tree nodes
898 
899  float *range; // range vector used to perform range search on kd tree, indexed
900  // by dimension of input - format:
901  // range = {Lower_Limit_1, Upper_Limit_1, ..., Lower_Limit_N, Upper_Limit_N}
902 
903  //##########################################
904  //######### MEAN SHIFT PROCESSING ##########
905  //######### DATA STRUCTURES ##########
906  //##########################################
907 
908  double *uv; // stores normalized distance vector between
909  // yk and xi
910 
911  double wsum; // sum of weights calculated at data points within the sphere
912 
913  //##########################################
914  //######### LATTICE DATA STRUCTURE #########
915  //##########################################
916 
918  int LowerBoundX, UpperBoundX; // Upper and lower bounds for lattice search window
919  // in the x dimension
920 
921  int LowerBoundY, UpperBoundY; // Upper and lower bounds for lattice search window
922  // in the y dimension
923 
924 };
925 
926 #endif
Generated by doxygen 1.9.1