1 /*=========================================================================
2
3 Program: Visualization Toolkit
4 Module: vtkPCAAnalysisFilter.cxx
5
6 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
7 All rights reserved.
8 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
9
10 This software is distributed WITHOUT ANY WARRANTY; without even
11 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
12 PURPOSE. See the above copyright notice for more information.
13
14 =========================================================================*/
15 #include "vtkPCAAnalysisFilter.h"
16 #include "vtkExecutive.h"
17 #include "vtkFloatArray.h"
18 #include "vtkInformation.h"
19 #include "vtkInformationVector.h"
20 #include "vtkMath.h"
21 #include "vtkMultiBlockDataSet.h"
22 #include "vtkObjectFactory.h"
23 #include "vtkPolyData.h"
24 #include "vtkTransformPolyDataFilter.h"
25
26 vtkStandardNewMacro(vtkPCAAnalysisFilter);
27
28 //------------------------------------------------------------------------------
29 // Matrix ops. Some taken from vtkThinPlateSplineTransform.cxx
NewMatrix(int rows,int cols)30 static inline double** NewMatrix(int rows, int cols)
31 {
32 double* matrix = new double[rows * cols];
33 double** m = new double*[rows];
34 for (int i = 0; i < rows; i++)
35 {
36 m[i] = &matrix[i * cols];
37 }
38 return m;
39 }
40
41 //------------------------------------------------------------------------------
DeleteMatrix(double ** m)42 static inline void DeleteMatrix(double** m)
43 {
44 delete[] * m;
45 delete[] m;
46 }
47
48 //------------------------------------------------------------------------------
MatrixMultiply(double ** a,double ** b,double ** c,int arows,int acols,int brows,int bcols)49 static inline void MatrixMultiply(
50 double** a, double** b, double** c, int arows, int acols, int brows, int bcols)
51 {
52 if (acols != brows)
53 {
54 return; // acols must equal br otherwise we can't proceed
55 }
56
57 // c must have size arows*bcols (we assume this)
58
59 for (int i = 0; i < arows; i++)
60 {
61 for (int j = 0; j < bcols; j++)
62 {
63 c[i][j] = 0.0;
64 for (int k = 0; k < acols; k++)
65 {
66 c[i][j] += a[i][k] * b[k][j];
67 }
68 }
69 }
70 }
71
72 //------------------------------------------------------------------------------
73 // Subtracting the mean column from the observation matrix is equal
74 // to subtracting the mean shape from all shapes.
75 // The mean column is equal to the Procrustes mean (it is also returned)
SubtractMeanColumn(double ** m,double * mean,int rows,int cols)76 static inline void SubtractMeanColumn(double** m, double* mean, int rows, int cols)
77 {
78 int r, c;
79 double csum;
80 for (r = 0; r < rows; r++)
81 {
82 csum = 0.0F;
83 for (c = 0; c < cols; c++)
84 {
85 csum += m[r][c];
86 }
87 // calculate average value of row
88 csum /= cols;
89
90 // Mean shape vector is updated
91 mean[r] = csum;
92
93 // average value is subtracted from all elements in the row
94 for (c = 0; c < cols; c++)
95 {
96 m[r][c] -= csum;
97 }
98 }
99 }
100
101 //------------------------------------------------------------------------------
102 // Normalise all columns to have length 1
103 // meaning that all eigenvectors are normalised
NormaliseColumns(double ** m,int rows,int cols)104 static inline void NormaliseColumns(double** m, int rows, int cols)
105 {
106 for (int c = 0; c < cols; c++)
107 {
108 double cl = 0;
109 for (int r = 0; r < rows; r++)
110 {
111 cl += m[r][c] * m[r][c];
112 }
113 cl = sqrt(cl);
114
115 // If cl == 0 something is rotten, don't do anything now
116 if (cl != 0)
117 {
118 for (int r = 0; r < rows; r++)
119 {
120 m[r][c] /= cl;
121 }
122 }
123 }
124 }
125
126 //------------------------------------------------------------------------------
127 // Here it is assumed that a rows >> a cols
128 // Output matrix is [a cols X a cols]
SmallCovarianceMatrix(double ** a,double ** c,int arows,int acols)129 static inline void SmallCovarianceMatrix(double** a, double** c, int arows, int acols)
130 {
131 const int s = acols;
132
133 // c must have size acols*acols (we assume this)
134 for (int i = 0; i < acols; i++)
135 {
136 for (int j = 0; j < acols; j++)
137 {
138 // Use symmetry
139 if (i <= j)
140 {
141 c[i][j] = 0.0;
142 for (int k = 0; k < arows; k++)
143 {
144 c[i][j] += a[k][i] * a[k][j];
145 }
146 c[i][j] /= (s - 1);
147 c[j][i] = c[i][j];
148 }
149 }
150 }
151 }
152
153 //------------------------------------------------------------------------------
NewVector(int length)154 static inline double* NewVector(int length)
155 {
156 double* vec = new double[length];
157 return vec;
158 }
159
160 //------------------------------------------------------------------------------
DeleteVector(double * v)161 static inline void DeleteVector(double* v)
162 {
163 delete[] v;
164 }
165
166 //------------------------------------------------------------------------------
167 // protected
vtkPCAAnalysisFilter()168 vtkPCAAnalysisFilter::vtkPCAAnalysisFilter()
169 {
170 this->Evals = vtkFloatArray::New();
171 this->evecMat2 = nullptr;
172 this->meanshape = nullptr;
173 }
174
175 //------------------------------------------------------------------------------
176 // protected
~vtkPCAAnalysisFilter()177 vtkPCAAnalysisFilter::~vtkPCAAnalysisFilter()
178 {
179 if (this->Evals)
180 {
181 this->Evals->Delete();
182 }
183 if (this->evecMat2)
184 {
185 DeleteMatrix(this->evecMat2);
186 this->evecMat2 = nullptr;
187 }
188 if (this->meanshape)
189 {
190 DeleteVector(this->meanshape);
191 this->meanshape = nullptr;
192 }
193 }
194
195 //------------------------------------------------------------------------------
196 // protected
RequestData(vtkInformation * vtkNotUsed (request),vtkInformationVector ** inputVector,vtkInformationVector * outputVector)197 int vtkPCAAnalysisFilter::RequestData(vtkInformation* vtkNotUsed(request),
198 vtkInformationVector** inputVector, vtkInformationVector* outputVector)
199 {
200 // get the info objects
201 vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);
202 vtkInformation* outInfo = outputVector->GetInformationObject(0);
203
204 // get the input and output
205 vtkMultiBlockDataSet* mbInput =
206 vtkMultiBlockDataSet::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
207
208 vtkDebugMacro(<< "Execute()");
209 int i;
210
211 // Clean up from previous computation
212 if (this->evecMat2)
213 {
214 DeleteMatrix(this->evecMat2);
215 this->evecMat2 = nullptr;
216 }
217 if (this->meanshape)
218 {
219 DeleteVector(this->meanshape);
220 this->meanshape = nullptr;
221 }
222
223 const int N_SETS = mbInput->GetNumberOfBlocks();
224
225 vtkPointSet* input = nullptr;
226 for (i = 0; i < N_SETS; i++)
227 {
228 input = vtkPointSet::SafeDownCast(mbInput->GetBlock(i));
229 if (input)
230 {
231 break;
232 }
233 }
234
235 if (!input)
236 {
237 return 1;
238 }
239
240 vtkMultiBlockDataSet* output =
241 vtkMultiBlockDataSet::SafeDownCast(outInfo->Get(vtkDataObject::DATA_OBJECT()));
242
243 vtkPointSet* tmpInput;
244 // copy the inputs across
245 for (i = 0; i < N_SETS; i++)
246 {
247 tmpInput = vtkPointSet::SafeDownCast(mbInput->GetBlock(i));
248 vtkPointSet* outputBlock = nullptr;
249 if (tmpInput)
250 {
251 outputBlock = tmpInput->NewInstance();
252 outputBlock->DeepCopy(tmpInput);
253 }
254 output->SetBlock(i, outputBlock);
255 if (outputBlock)
256 {
257 outputBlock->Delete();
258 }
259 }
260
261 // the number of points is determined by the first input (they must all be the same)
262 const int N_POINTS = input->GetNumberOfPoints();
263
264 vtkDebugMacro(<< "N_POINTS is " << N_POINTS);
265
266 if (N_POINTS == 0)
267 {
268 vtkErrorMacro(<< "No points!");
269 return 1;
270 }
271
272 // all the inputs must have the same number of points to consider executing
273 for (i = 1; i < N_SETS; i++)
274 {
275 tmpInput = vtkPointSet::SafeDownCast(mbInput->GetBlock(i));
276 if (!tmpInput)
277 {
278 continue;
279 }
280 if (tmpInput->GetNumberOfPoints() != N_POINTS)
281 {
282 vtkErrorMacro(<< "The inputs have different numbers of points!");
283 return 1;
284 }
285 }
286
287 // Number of shapes
288 const int s = N_SETS;
289
290 // Number of points in a shape
291 const int n = N_POINTS;
292
293 // Observation Matrix [number of points * 3 X number of shapes]
294 double** D = NewMatrix(3 * n, s);
295
296 for (i = 0; i < n; i++)
297 {
298 for (int j = 0; j < s; j++)
299 {
300 tmpInput = vtkPointSet::SafeDownCast(mbInput->GetBlock(j));
301 if (!tmpInput)
302 {
303 continue;
304 }
305 double p[3];
306 tmpInput->GetPoint(i, p);
307 D[i * 3][j] = p[0];
308 D[i * 3 + 1][j] = p[1];
309 D[i * 3 + 2][j] = p[2];
310 }
311 }
312
313 // The mean shape is also calculated
314 meanshape = NewVector(3 * n);
315
316 SubtractMeanColumn(D, meanshape, 3 * n, s);
317
318 // Covariance matrix of dim [s x s]
319 double** T = NewMatrix(s, s);
320 SmallCovarianceMatrix(D, T, 3 * n, s);
321
322 double* ev = NewVector(s);
323 double** evecMat = NewMatrix(s, s);
324
325 vtkMath::JacobiN(T, s, ev, evecMat);
326
327 // Compute eigenvecs of DD' instead of T which is D'D
328 // evecMat2 of dim [3*n x s]
329 evecMat2 = NewMatrix(3 * n, s);
330 MatrixMultiply(D, evecMat, evecMat2, 3 * n, s, s, s);
331
332 // Normalise eigenvectors
333 NormaliseColumns(evecMat2, 3 * n, s);
334
335 this->Evals->SetNumberOfValues(s);
336
337 // Copy data to output structures
338 for (int j = 0; j < s; j++)
339 {
340 this->Evals->SetValue(j, ev[j]);
341
342 vtkPointSet* block = vtkPointSet::SafeDownCast(output->GetBlock(j));
343
344 if (block)
345 {
346 for (i = 0; i < n; i++)
347 {
348 double x = evecMat2[i * 3][j];
349 double y = evecMat2[i * 3 + 1][j];
350 double z = evecMat2[i * 3 + 2][j];
351
352 block->GetPoints()->SetPoint(i, x, y, z);
353 }
354 }
355 }
356
357 DeleteMatrix(evecMat);
358 DeleteVector(ev);
359 DeleteMatrix(T);
360 DeleteMatrix(D);
361
362 return 1;
363 }
364
365 //------------------------------------------------------------------------------
366 // public
GetParameterisedShape(vtkFloatArray * b,vtkPointSet * shape)367 void vtkPCAAnalysisFilter::GetParameterisedShape(vtkFloatArray* b, vtkPointSet* shape)
368 {
369 vtkPointSet* output = nullptr;
370
371 vtkMultiBlockDataSet* mbOutput = this->GetOutput();
372
373 int numBlocks = mbOutput->GetNumberOfBlocks();
374
375 int i, j;
376
377 for (i = 0; i < numBlocks; i++)
378 {
379 output = vtkPointSet::SafeDownCast(mbOutput->GetBlock(i));
380 if (output)
381 {
382 break;
383 }
384 }
385
386 if (!output)
387 {
388 vtkErrorMacro(<< "No valid output block was found.");
389 return;
390 }
391
392 const int bsize = b->GetNumberOfTuples();
393
394 const int n = output->GetNumberOfPoints();
395
396 if (shape->GetNumberOfPoints() != n)
397 {
398 vtkErrorMacro(<< "Input shape does not have the correct number of points");
399 return;
400 }
401
402 double* shapevec = NewVector(n * 3);
403
404 // b is weighted by the eigenvals
405 // make weight vector for speed reasons
406 double* w = NewVector(bsize);
407 for (i = 0; i < bsize; i++)
408 {
409 w[i] = sqrt(this->Evals->GetValue(i)) * b->GetValue(i);
410 }
411 for (j = 0; j < n * 3; j++)
412 {
413 shapevec[j] = meanshape[j];
414
415 for (i = 0; i < bsize; i++)
416 {
417 shapevec[j] += w[i] * evecMat2[j][i];
418 }
419 }
420
421 // Copy shape
422 for (i = 0; i < n; i++)
423 {
424 shape->GetPoints()->SetPoint(i, shapevec[i * 3], shapevec[i * 3 + 1], shapevec[i * 3 + 2]);
425 }
426
427 DeleteVector(shapevec);
428 DeleteVector(w);
429 }
430
431 //------------------------------------------------------------------------------
432 // public
GetShapeParameters(vtkPointSet * shape,vtkFloatArray * b,int bsize)433 void vtkPCAAnalysisFilter::GetShapeParameters(vtkPointSet* shape, vtkFloatArray* b, int bsize)
434 {
435 vtkPointSet* output = nullptr;
436
437 vtkMultiBlockDataSet* mbOutput = this->GetOutput();
438
439 int numBlocks = mbOutput->GetNumberOfBlocks();
440
441 int i, j;
442
443 for (i = 0; i < numBlocks; i++)
444 {
445 output = vtkPointSet::SafeDownCast(mbOutput->GetBlock(i));
446 if (output)
447 {
448 break;
449 }
450 }
451
452 if (!output)
453 {
454 vtkErrorMacro(<< "No valid output block was found.");
455 return;
456 }
457
458 // Local variant of b for fast access.
459 double* bloc = NewVector(bsize);
460
461 const int n = output->GetNumberOfPoints();
462
463 if (shape->GetNumberOfPoints() != n)
464 {
465 vtkErrorMacro(<< "Input shape does not have the correct number of points");
466 DeleteVector(bloc);
467 return;
468 }
469
470 double* shapevec = NewVector(n * 3);
471
472 // Copy shape and subtract mean shape
473 for (i = 0; i < n; i++)
474 {
475 double p[3];
476 shape->GetPoint(i, p);
477 shapevec[i * 3] = p[0] - meanshape[i * 3];
478 shapevec[i * 3 + 1] = p[1] - meanshape[i * 3 + 1];
479 shapevec[i * 3 + 2] = p[2] - meanshape[i * 3 + 2];
480 }
481
482 for (i = 0; i < bsize; i++)
483 {
484 bloc[i] = 0;
485
486 // Project the shape onto eigenvector i
487 for (j = 0; j < n * 3; j++)
488 {
489 bloc[i] += shapevec[j] * evecMat2[j][i];
490 }
491 }
492
493 // Return b in number of standard deviations
494 b->SetNumberOfValues(bsize);
495 for (i = 0; i < bsize; i++)
496 {
497 if (this->Evals->GetValue(i))
498 b->SetValue(i, bloc[i] / sqrt(this->Evals->GetValue(i)));
499 else
500 b->SetValue(i, 0);
501 }
502
503 DeleteVector(shapevec);
504 DeleteVector(bloc);
505 }
506
507 //------------------------------------------------------------------------------
508 // public
PrintSelf(ostream & os,vtkIndent indent)509 void vtkPCAAnalysisFilter::PrintSelf(ostream& os, vtkIndent indent)
510 {
511 this->Superclass::PrintSelf(os, indent);
512 this->Evals->PrintSelf(os, indent.GetNextIndent());
513 }
514
515 //------------------------------------------------------------------------------
516 // public
GetModesRequiredFor(double proportion)517 int vtkPCAAnalysisFilter::GetModesRequiredFor(double proportion)
518 {
519 int i;
520
521 double eigen_total = 0.0F;
522 for (i = 0; i < this->Evals->GetNumberOfTuples(); i++)
523 {
524 eigen_total += this->Evals->GetValue(i);
525 }
526
527 double running_total = 0.0F;
528 for (i = 0; i < this->Evals->GetNumberOfTuples(); i++)
529 {
530 running_total += this->Evals->GetValue(i) / eigen_total;
531 if (running_total >= proportion)
532 {
533 return i + 1;
534 }
535 }
536
537 return Evals->GetNumberOfTuples();
538 }
539