Debian Codegraph @

plugins/core/Standard/qCanupo/src/qCanupoTools.cpp

raw
1 //##########################################################################
2 //# #
3 //# CLOUDCOMPARE PLUGIN: qCANUPO #
4 //# #
5 //# This program is free software; you can redistribute it and/or modify #
6 //# it under the terms of the GNU General Public License as published by #
7 //# the Free Software Foundation; version 2 or later of the License. #
8 //# #
9 //# This program is distributed in the hope that it will be useful, #
10 //# but WITHOUT ANY WARRANTY; without even the implied warranty of #
11 //# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #
12 //# GNU General Public License for more details. #
13 //# #
14 //# COPYRIGHT: UEB (UNIVERSITE EUROPEENNE DE BRETAGNE) / CNRS #
15 //# #
16 //##########################################################################
17
18 #include "qCanupoTools.h"
19
20 //Local
21 #include "trainer.h"
22
23 //CCCoreLib
24 #include <DistanceComputationTools.h>
25 #include <Neighbourhood.h>
26 #include <ParallelSort.h>
27
28 //qCC_db
29 #include <ccPointCloud.h>
30 #include <ccProgressDialog.h>
31 #include <ccScalarField.h>
32
33 //qCC_plugins
34 #include <ccMainAppInterface.h>
35 #include <ccQtHelpers.h>
36
37 //Qt
38 #include <QApplication>
39 #include <QComboBox>
40 #include <QMainWindow>
41 #include <QtConcurrentMap>
42
43 //ComputeCorePointsDescriptors parameters
44 static struct
45 {
46 CCCoreLib::GenericIndexedCloud* corePoints;
47 ccGenericPointCloud* sourceCloud;
48 CCCoreLib::DgmOctree* octree;
49 unsigned char octreeLevel;
50 CorePointDescSet* descriptors;
51 bool invalidDescriptors;
52
53 CCCoreLib::NormalizedProgress* nProgress;
54 bool processCanceled;
55 bool errorOccurred;
56
57 ScaleParamsComputer* computer; //the per-scale parameters computer
58
59 std::vector<ccScalarField*>* roughnessSFs; //for test
60
61
62 } s_computeCorePointsDescParams;
63
64 //! Per-point descriptor computer (all the parameters are stored in s_computeCorePointsDescParams)
65 void ComputeCorePointDescriptor(unsigned index)
66 {
67 if (s_computeCorePointsDescParams.processCanceled)
68 return;
69
70 const CCVector3* P = s_computeCorePointsDescParams.corePoints->getPoint(index);
71 CCCoreLib::DgmOctree::NeighboursSet neighbours;
72
73 //extract the neighbors (maximum radius)
74 float maxRadius = s_computeCorePointsDescParams.descriptors->scales().front() / 2;
75 int n = s_computeCorePointsDescParams.octree->getPointsInSphericalNeighbourhood(*P,
76 maxRadius,
77 neighbours,
78 s_computeCorePointsDescParams.octreeLevel);
79
80 if (n != 0)
81 {
82 size_t scaleCount = s_computeCorePointsDescParams.descriptors->scales().size();
83
84 //get reference on corresponding descriptor
85 assert(s_computeCorePointsDescParams.descriptors->size() > index);
86 CorePointDesc& desc = s_computeCorePointsDescParams.descriptors->at(index);
87
88 unsigned dimPerScale = s_computeCorePointsDescParams.descriptors->dimPerScale();
89 assert(desc.params.size() == scaleCount * dimPerScale);
90
91 //init the whole neighborhood subset (we will prune it each time)
92 CCCoreLib::ReferenceCloud subset(s_computeCorePointsDescParams.sourceCloud);
93 {
94 if (!subset.reserve(n))
95 {
96 //not enough memory!
97 s_computeCorePointsDescParams.errorOccurred = true;
98 s_computeCorePointsDescParams.processCanceled = true; //to make the loop stop!
99 return;
100 }
101
102 //sort the neighbors by increasing distance
103 ParallelSort(neighbours.begin(), neighbours.end(), CCCoreLib::DgmOctree::PointDescriptor::distComp);
104
105 for (int j = 0; j < n; ++j)
106 {
107 subset.addPointIndex(neighbours[j].pointIndex);
108 }
109 }
110
111 s_computeCorePointsDescParams.computer->reset();
112
113 for (size_t i = 0; i < scaleCount; ++i)
114 {
115 const double radius = s_computeCorePointsDescParams.descriptors->scales()[i] / 2; //we start from the biggest
116
117 if (i != 0)
118 {
119 //trim the points that don't fall in the current neighborhood
120 double squareRadius = radius * radius;
121 CCCoreLib::DgmOctree::PointDescriptor fakeDesc(nullptr, 0, squareRadius);
122 CCCoreLib::DgmOctree::NeighboursSet::iterator up = std::upper_bound(neighbours.begin(), neighbours.end(), fakeDesc, CCCoreLib::DgmOctree::PointDescriptor::distComp);
123 if (up != neighbours.end())
124 {
125 size_t count = std::max<size_t>(1, up - neighbours.begin());
126
127 neighbours.resize(count);
128 subset.resize(static_cast<unsigned>(count));
129 }
130 }
131
132 //optional: compute per-level roughness
133 if (s_computeCorePointsDescParams.roughnessSFs)
134 {
135 ScalarType roughness = CCCoreLib::NAN_VALUE;
136
137 if (subset.size() >= 3)
138 {
139 //to compute we take the nearest point to the query point as 'central' point
140 //warning: it should work in most of the cases, apart if the core points have nothing to do
141 //with the global cloud!!!
142 unsigned lastIndex = subset.size() - 1;
143 subset.swap(0, lastIndex);
144
145 //temporarily remove the central point (now at the end)
146 unsigned globalIndex = subset.getPointGlobalIndex(lastIndex);
147 subset.resize(lastIndex);
148
149 CCCoreLib::Neighbourhood Z(&subset);
150 const PointCoordinateType* lsPlane = Z.getLSPlane();
151 if (lsPlane)
152 {
153 //distance to the LS plane fitted on the nearest neighbors
154 const CCVector3* centralPoint = s_computeCorePointsDescParams.sourceCloud->getPoint(globalIndex);
155 roughness = std::abs(CCCoreLib::DistanceComputationTools::computePoint2PlaneDistance(centralPoint, lsPlane));
156 }
157
158 //put back the point at its original place!
159 subset.addPointIndex(globalIndex);
160 subset.swap(0, lastIndex);
161 }
162
163 assert(s_computeCorePointsDescParams.roughnessSFs->size() == scaleCount);
164 ccScalarField* sf = s_computeCorePointsDescParams.roughnessSFs->at(i);
165 assert(sf && sf->currentSize() > index);
166 sf->setValue(index, roughness);
167 }
168
169 bool invalidScale = false;
170 s_computeCorePointsDescParams.computer->computeScaleParams(subset, radius, &(desc.params[i*dimPerScale]), invalidScale);
171
172 if (invalidScale)
173 {
174 s_computeCorePointsDescParams.invalidDescriptors = true;
175 //no need to compute the remaining scales!
176 for (size_t j = i + 1; j < scaleCount; ++j)
177 {
178 //copy the same parameters for all scales (see CANUPO paper)
179 memcpy(&(desc.params[j*dimPerScale]), &(desc.params[i*dimPerScale]), sizeof(float)*dimPerScale);
180 }
181 //neighbours.clear();
182 //subset.clear(true);
183 break;
184 }
185 }
186 }
187 else
188 {
189 //if the widest neighborhood has less than 3 points, we can't compute a valid descriptor!
190 s_computeCorePointsDescParams.invalidDescriptors = true;
191 }
192
193 //progress notification
194 if (s_computeCorePointsDescParams.nProgress && !s_computeCorePointsDescParams.nProgress->oneStep())
195 {
196 s_computeCorePointsDescParams.processCanceled = true;
197 }
198 }
199
200 bool qCanupoTools::ComputeCorePointsDescriptors(CCCoreLib::GenericIndexedCloud* corePoints,
201 CorePointDescSet& corePointsDescriptors,
202 ccGenericPointCloud* sourceCloud,
203 const std::vector<float>& sortedScales,
204 bool& invalidDescriptors,
205 QString& error, //if any
206 unsigned descriptorID/*=DESC_DIMENSIONALITY*/,
207 int maxThreadCount/*=0*/,
208 CCCoreLib::GenericProgressCallback* progressCb/*=nullptr*/,
209 CCCoreLib::DgmOctree* inputOctree/*=nullptr*/,
210 std::vector<ccScalarField*>* roughnessSFs/*=nullptr*/)
211 {
212 assert(corePoints && sourceCloud);
213 assert(!sortedScales.empty());
214
215 invalidDescriptors = true;
216 error = QString();
217
218 unsigned corePtsCount = corePoints->size();
219 if (corePtsCount == 0)
220 {
221 error = "No core points?!";
222 return false;
223 }
224 size_t scaleCount = sortedScales.size();
225 if (scaleCount == 0)
226 {
227 error = "No scales?!";
228 return false;
229 }
230
231 //descriptor (computer)
232 s_computeCorePointsDescParams.computer = ScaleParamsComputer::GetByID(descriptorID);
233 if (!s_computeCorePointsDescParams.computer)
234 {
235 error = QString("Unhandled descriptor ID (%1)!").arg(descriptorID);
236 return false;
237 }
238 if (s_computeCorePointsDescParams.computer->needSF() && !corePoints->enableScalarField())
239 {
240 error = "Couldn't allocate a scalar field for core points!";
241 return false;
242 }
243
244 corePointsDescriptors.setDescriptorID(descriptorID);
245 corePointsDescriptors.setDimPerScale(s_computeCorePointsDescParams.computer->dimPerScale());
246
247 CCCoreLib::DgmOctree* theOctree = inputOctree;
248 if (!theOctree)
249 {
250 theOctree = new CCCoreLib::DgmOctree(sourceCloud);
251 if (theOctree->build(progressCb) == 0)
252 {
253 error = "Failed to build the octree (not enough memory?)";
254 delete theOctree;
255 return false;
256 }
257 }
258
259 CCCoreLib::NormalizedProgress nProgress(progressCb, corePtsCount);
260 if (progressCb)
261 {
262 if (progressCb->textCanBeEdited())
263 {
264 progressCb->setInfo(qPrintable(QString("Core points: %1\nSource points: %2").arg(corePtsCount).arg(sourceCloud->size())));
265 progressCb->setMethodTitle("Computing descriptors");
266 }
267 progressCb->start();
268 QApplication::processEvents();
269 }
270
271 //reserve memory for descriptors storage
272 bool success = true;
273 try
274 {
275 corePointsDescriptors.resize(corePtsCount);
276 }
277 catch (const std::bad_alloc&)
278 {
279 success = false;
280 }
281
282 if (success)
283 success = corePointsDescriptors.setScales(sortedScales); //automatically resizes the 'params' structure for each core point
284 if (!success)
285 {
286 error = "Not enough memory to compute core points!";
287 if (!inputOctree)
288 delete theOctree;
289 return false;
290 }
291
292 PointCoordinateType biggestRadius = sortedScales.front() / 2; //we extract the biggest neighborhood
293 unsigned char octreeLevel = theOctree->findBestLevelForAGivenNeighbourhoodSizeExtraction(biggestRadius);
294
295 s_computeCorePointsDescParams.corePoints = corePoints;
296 s_computeCorePointsDescParams.descriptors = &corePointsDescriptors;
297 s_computeCorePointsDescParams.sourceCloud = sourceCloud;
298 s_computeCorePointsDescParams.octree = theOctree;
299 s_computeCorePointsDescParams.octreeLevel = octreeLevel;
300 s_computeCorePointsDescParams.nProgress = progressCb ? &nProgress : nullptr;
301 s_computeCorePointsDescParams.processCanceled = false;
302 s_computeCorePointsDescParams.errorOccurred = false;
303 s_computeCorePointsDescParams.invalidDescriptors = false;
304 s_computeCorePointsDescParams.roughnessSFs = roughnessSFs;
305
306 //we try the parallel way (if we have enough memory)
307 bool useParallelStrategy = true;
308 #ifdef _DEBUG
309 useParallelStrategy = false;
310 #endif
311
312 std::vector<unsigned> corePointsIndexes;
313 if (useParallelStrategy)
314 {
315 try
316 {
317 corePointsIndexes.resize(corePtsCount);
318 }
319 catch (const std::bad_alloc&)
320 {
321 //not enough memory
322 useParallelStrategy = false;
323 }
324 }
325
326 if (useParallelStrategy)
327 {
328 for (unsigned i = 0; i < corePtsCount; ++i)
329 {
330 corePointsIndexes[i] = i;
331 }
332
333 if (maxThreadCount == 0)
334 {
335 maxThreadCount = ccQtHelpers::GetMaxThreadCount();
336 }
337 assert(maxThreadCount <= QThread::idealThreadCount());
338 QThreadPool::globalInstance()->setMaxThreadCount(maxThreadCount);
339 QtConcurrent::blockingMap(corePointsIndexes, ComputeCorePointDescriptor);
340 }
341 else
342 {
343 //manually call the static per-point method!
344 for (unsigned i = 0; i < corePtsCount; ++i)
345 {
346 ComputeCorePointDescriptor(i);
347 }
348 }
349
350 //output flags
351 bool wasCanceled = s_computeCorePointsDescParams.processCanceled;
352 bool errorOccurred = s_computeCorePointsDescParams.errorOccurred;
353 if (errorOccurred)
354 error = "An error occurred during descriptors computation!";
355 else if (wasCanceled)
356 error = "Process has been cancelled by the user";
357 invalidDescriptors = s_computeCorePointsDescParams.invalidDescriptors;
358
359 //reset static parameters (just to be clean ;)
360 s_computeCorePointsDescParams.corePoints = nullptr;
361 s_computeCorePointsDescParams.descriptors = nullptr;
362 s_computeCorePointsDescParams.sourceCloud = nullptr;
363 s_computeCorePointsDescParams.octree = nullptr;
364 s_computeCorePointsDescParams.octreeLevel = 0;
365 s_computeCorePointsDescParams.nProgress = nullptr;
366 s_computeCorePointsDescParams.processCanceled = false;
367 s_computeCorePointsDescParams.errorOccurred = false;
368 s_computeCorePointsDescParams.invalidDescriptors = false;
369 s_computeCorePointsDescParams.computer = nullptr;
370
371 if (progressCb)
372 {
373 progressCb->stop();
374 }
375
376 if (!inputOctree)
377 delete theOctree;
378
379 return !errorOccurred && !wasCanceled;
380 }
381
382 bool qCanupoTools::CompareVectors(const std::vector<float>& first, const std::vector<float>& second)
383 {
384 //check scales
385 size_t firstCount = first.size();
386 if (firstCount != second.size())
387 return false;
388
389 for (size_t i = 0; i < firstCount; ++i)
390 if (!Fpeq<float>(first[i], second[i]))
391 return false;
392
393 return true;
394 }
395
396 size_t qCanupoTools::TestVectorsOverlap(const std::vector<float>& first, const std::vector<float>& second)
397 {
398 size_t size1 = first.size();
399 size_t size2 = second.size();
400 size_t minCount = std::min(size1, size2);
401
402 size_t i = 0;
403 for (i = 0; i < minCount; ++i)
404 if (!Fpeq<float>(first[size1 - 1 - i], second[size2 - 1 - i]))
405 break;
406
407 return i;
408 }
409
410 QString qCanupoTools::GetEntityName(ccHObject* obj)
411 {
412 if (!obj)
413 {
414 assert(false);
415 return QString();
416 }
417
418 QString name = obj->getName();
419 if (name.isEmpty())
420 name = "unnamed";
421 name += QString(" [ID %1]").arg(obj->getUniqueID());
422
423 return name;
424 }
425
426 ccPointCloud* qCanupoTools::GetCloudFromCombo(QComboBox* comboBox, ccHObject* dbRoot)
427 {
428 assert(comboBox && dbRoot);
429 if (!comboBox || !dbRoot)
430 {
431 assert(false);
432 return nullptr;
433 }
434
435 //return the cloud currently selected in the combox box
436 int index = comboBox->currentIndex();
437 if (index < 0)
438 {
439 assert(false);
440 return nullptr;
441 }
442 unsigned uniqueID = comboBox->itemData(index).toUInt();
443 ccHObject* item = dbRoot->find(uniqueID);
444 if (!item || !item->isA(CC_TYPES::POINT_CLOUD))
445 {
446 assert(false);
447 return nullptr;
448 }
449 return static_cast<ccPointCloud*>(item);
450 }
451
452 bool qCanupoTools::EvaluateClassifier(const Classifier& classifier,
453 const CorePointDescSet& descriptors1,
454 const CorePointDescSet& descriptors2,
455 const std::vector<float>& scales,
456 EvalParameters& params)
457 {
458 params = EvalParameters();
459
460 if (descriptors1.empty() || descriptors2.empty())
461 {
462 //empty descriptors?
463 return false;
464 }
465
466 //Evaluate on 1st class
467 {
468 size_t nsamples1 = descriptors1.size();
469 double sumd = 0;
470 double sumd2 = 0;
471 for (size_t i = 0; i < nsamples1; ++i)
472 {
473 float d = classifier.classify(descriptors1[i]);
474 if (d > 0)
475 params.false1++;
476 else
477 params.true1++;
478
479 sumd += d;
480 sumd2 += static_cast<double>(d)*d;
481 }
482 params.mu1 = sumd / nsamples1;
483 params.var1 = sumd2 / nsamples1 - params.mu1*params.mu1;
484 }
485
486 //Evaluate on 2nd class
487 {
488 size_t nsamples2 = descriptors2.size();
489 double sumd = 0;
490 double sumd2 = 0;
491 for (size_t i = 0; i < nsamples2; ++i)
492 {
493 float d = classifier.classify(descriptors2[i]);
494 if (d < 0)
495 params.false2++;
496 else
497 params.true2++;
498
499 sumd += d;
500 sumd2 += static_cast<double>(d)*d;
501 }
502 params.mu2 = sumd / nsamples2;
503 params.var2 = sumd2 / nsamples2 - params.mu2*params.mu2;
504 }
505
506 return true;
507 }
508
509 bool qCanupoTools::TrainClassifier( Classifier& classifier,
510 const CorePointDescSet& descriptors1,
511 const CorePointDescSet& descriptors2,
512 const std::vector<float>& scales,
513 ccPointCloud* mscCloud,
514 const CorePointDescSet* evaluationDescriptors/*=nullptr*/,
515 ccMainAppInterface* app/*=nullptr*/)
516 {
517 //fuse both descriptor sets in a single 'dlib' structure
518 size_t nsamples1 = descriptors1.size();
519 size_t nsamples2 = descriptors2.size();
520
521 if (nsamples1 == 0 || nsamples2 == 0)
522 {
523 if (app)
524 app->dispToConsole("Invalid descriptors!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
525 return false;
526 }
527
528 assert(descriptors1.descriptorID() == descriptors2.descriptorID());
529 classifier.descriptorID = descriptors1.descriptorID();
530
531 unsigned dimPerScale = descriptors1.dimPerScale();
532 assert(dimPerScale == descriptors2.dimPerScale());
533 classifier.dimPerScale = dimPerScale;
534
535 //we use the specified 'scales' (not necessarily all descriptors will be used!)
536 assert((descriptors1.front().params.size() % dimPerScale) == 0);
537 size_t paramsCount = descriptors1.front().params.size() / dimPerScale;
538 size_t scaleCount = scales.size();
539 assert(scaleCount <= paramsCount);
540 scaleCount = std::min(scaleCount, paramsCount);
541
542 classifier.scales = scales;
543 //already set outside!
544 //classifier.class1 = 1;
545 //classifier.class2 = 2;
546
547 size_t nsamples = nsamples1 + nsamples2;
548 size_t fdim = scaleCount * dimPerScale;
549
550 std::vector<LDATrainer::sample_type> samples;
551 std::vector<float> labels;
552 try
553 {
554 LDATrainer::sample_type nanSample;
555 nanSample.set_size(fdim, 1);
556 samples.resize(nsamples, nanSample);
557 labels.resize(nsamples, 1); //labels for class#1 will be changed to -1 (see below)
558 }
559 catch (const std::bad_alloc&)
560 {
561 if (app)
562 app->dispToConsole("Not enough memory to prepare the samples!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
563 return false;
564 }
565
566 //add class #1 data
567 {
568 for (size_t i = 0; i < nsamples1; ++i)
569 {
570 const CorePointDesc& desc = descriptors1[i];
571 LDATrainer::sample_type& sample = samples[i];
572 //assert(scaleCount <= paramsCount); //already tested above
573 size_t shift = (paramsCount - scaleCount)*dimPerScale; //if we use less scales than parameters
574 for (size_t j = 0; j < fdim; ++j)
575 {
576 sample(j) = desc.params[shift + j];
577 }
578 //class #1 is labelled with '-1'
579 labels[i] = -1;
580 }
581 }
582 //add class #2 data
583 {
584 for (size_t i = 0; i < nsamples2; ++i)
585 {
586 const CorePointDesc& desc = descriptors2[i];
587 LDATrainer::sample_type& sample = samples[nsamples1 + i];
588 //assert(scaleCount <= paramsCount); //already tested above
589 size_t shift = (paramsCount - scaleCount)*dimPerScale; //if we use less scales than parameters
590 for (size_t j = 0; j < fdim; ++j)
591 {
592 sample(j) = desc.params[shift + j];
593 }
594 //class #2 is labelled with '1' (already done above)
595 //labels[nsamples1+i] = 1;
596 }
597 }
598
599 //Computing the two best projection directions
600 QMainWindow* parentWindow = (app ? app->getMainWindow() : nullptr);
601 LDATrainer trainer;
602 {
603 QProgressDialog tempProgressDlg("LDA (step #1) in progress... please wait...", QString(), 0, 0, parentWindow);
604 tempProgressDlg.show();
605 QApplication::processEvents();
606
607 // shuffle before internal cross-validation to spread instances of each class
608 dlib::randomize_samples(samples, labels);
609 try
610 {
611 trainer.train(10, samples, labels);
612 }
613 catch (...)
614 {
615 if (app)
616 app->dispToConsole("Oops, it seems the LDA classifier just crashed!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
617 return false;
618 }
619 }
620
621 // get the projections of each sample on the first classifier direction
622 std::vector<float> proj1;
623 {
624 try
625 {
626 proj1.resize(nsamples);
627 }
628 catch (const std::bad_alloc&)
629 {
630 if (app)
631 app->dispToConsole("Not enough memory to project the samples!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
632 return false;
633 }
634
635 try
636 {
637 for (size_t i = 0; i < nsamples; ++i)
638 {
639 proj1[i] = static_cast<float>(trainer.predict(samples[i]));
640 }
641 }
642 catch (...)
643 {
644 if (app)
645 app->dispToConsole("Oops, it seems the LDA classifier just crashed!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
646 return false;
647 }
648
649 //std::pair<std::vector<float>::const_iterator, std::vector<float>::const_iterator> mm = std::minmax_element(proj1.begin(),proj1.end());
650 //m_app->dispToConsole(QString("Min/max(proj1) = (%1 , %2)").arg(*mm.first).arg(*mm.second));
651 }
652
653 dlib::matrix<LDATrainer::sample_type, 0, 1> basis;
654 {
655 basis.set_size(fdim);
656 for (size_t i = 0; i < fdim; ++i)
657 {
658 basis(i).set_size(fdim);
659 for (size_t j = 0; j < fdim; ++j)
660 basis(i)(j) = 0;
661 basis(i)(i) = 1;
662 }
663 }
664 LDATrainer::sample_type w_vect;
665 {
666 w_vect.set_size(fdim);
667 for (size_t i = 0; i < fdim; ++i)
668 w_vect(i) = static_cast<float>(trainer.m_weights[i]);
669 }
670
671 GramSchmidt(basis, w_vect);
672
673 //Determining orthogonal direction
674 std::vector<LDATrainer::sample_type> samples_reduced;
675 {
676 try
677 {
678 samples_reduced.resize(nsamples);
679 }
680 catch (const std::bad_alloc&)
681 {
682 if (app)
683 app->dispToConsole("Not enough memory to compute 'reduced' samples!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
684 return false;
685 }
686
687 for (size_t i = 0; i < nsamples; ++i)
688 samples_reduced[i].set_size(fdim - 1);
689 // project the data onto the hyperplane so as to get the second direction
690 for (size_t si = 0; si < nsamples; ++si)
691 for (size_t i = 1; i < fdim; ++i)
692 samples_reduced[si](i - 1) = dlib::dot(samples[si], basis(i));
693 }
694
695 LDATrainer orthoTrainer;
696 try
697 {
698 QProgressDialog tempProgressDlg("LDA (step #2) in progress... please wait...", QString(), 0, 0, parentWindow);
699 tempProgressDlg.show();
700 QApplication::processEvents();
701
702 orthoTrainer.train(10, samples_reduced, labels);
703 }
704 catch (...)
705 {
706 if (app)
707 app->dispToConsole("Oops, it seems the LDA classifier just crashed!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
708 return false;
709 }
710
711 // convert back the classifier weights into the original space
712 {
713 try
714 {
715 orthoTrainer.m_weights.resize(fdim + 1);
716 }
717 catch (const std::bad_alloc&)
718 {
719 if (app)
720 app->dispToConsole("Not enough memory to compute the classifier weights!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
721 return false;
722 }
723 orthoTrainer.m_weights[fdim] = orthoTrainer.m_weights[fdim - 1];
724
725 size_t i = 0;
726 for (i = 0; i < fdim; ++i)
727 w_vect(i) = 0;
728 for (i = 1; i < fdim; ++i)
729 w_vect += orthoTrainer.m_weights[i - 1] * basis(i);
730 for (i = 0; i < fdim; ++i)
731 orthoTrainer.m_weights[i] = w_vect(i);
732 }
733
734 std::vector<float> proj2;
735 {
736 try
737 {
738 proj2.resize(nsamples);
739 }
740 catch (const std::bad_alloc&)
741 {
742 if (app)
743 app->dispToConsole("Not enough memory to project samples!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
744 return false;
745 }
746
747 try
748 {
749 for (size_t i = 0; i < nsamples; ++i)
750 {
751 proj2[i] = static_cast<float>(orthoTrainer.predict(samples[i]));
752 }
753 }
754 catch (...)
755 {
756 if (app)
757 app->dispToConsole("Oops, it seems the LDA classifier just crashed!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
758 return false;
759 }
760
761 //std::pair<std::vector<float>::const_iterator, std::vector<float>::const_iterator> mm = std::minmax_element(proj2.begin(),proj2.end());
762 //m_app->dispToConsole(QString("Min/max(proj2) = (%1 , %2)").arg(*mm.first).arg(*mm.second));
763 }
764
765 // compute the reference points for orienting the classifier boundaries
766 // pathological cases are possible where an arbitrary point in the (>0,>0)
767 // quadrant is not in the +1 class for example
768 // here, just use the mean of the classes
769 ComputeReferencePoints( classifier.refPointPos,
770 classifier.refPointNeg,
771 proj1,
772 proj2,
773 labels);
774
775 classifier.weightsAxis1 = trainer.m_weights;
776 classifier.weightsAxis2 = orthoTrainer.m_weights;
777
778 if (true)
779 {
780 // Same as Brodu's code:
781 // Experimental: dilatation to highlight the internal data structure
782 if (!DilateClassifier( classifier,
783 proj1,
784 proj2,
785 labels,
786 samples,
787 trainer,
788 orthoTrainer))
789 {
790 if (app)
791 app->dispToConsole("Not enough memory to 'dilate' the classifier!",ccMainAppInterface::ERR_CONSOLE_MESSAGE);
792 return false;
793 }
794 }
795
796 //proceed to boundary evaluation
797 {
798 Classifier::Point2D boundaryCenter(0, 0);
799 Classifier::Point2D boundaryDir(0, 1);
800
801 assert(mscCloud);
802 if (!mscCloud)
803 {
804 if (app)
805 app->dispToConsole("[Internal error] Invalid output MSC cloud!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
806 return false;
807 }
808 //if we have no 'evaluation' cloud, we'll add it to the sum of the two input clouds
809 size_t cloudSize = nsamples;
810 if (evaluationDescriptors)
811 cloudSize += evaluationDescriptors->size();
812 mscCloud->clear();
813 if (!mscCloud->reserve(cloudSize))
814 {
815 if (app)
816 app->dispToConsole("Not enough memory to determine the classifier behavior!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
817 return false;
818 }
819
820 bool hasColors = true;
821 if (!mscCloud->reserveTheRGBTable())
822 {
823 if (app)
824 app->dispToConsole("Not enough memory to display colors!", ccMainAppInterface::ERR_CONSOLE_MESSAGE);
825 }
826 else
827 {
828 mscCloud->showColors(true);
829 }
830
831 //generate the cloud of (colored) MSC "points"
832 for (size_t i = 0; i < cloudSize; ++i)
833 {
834 LDATrainer::sample_type sample;
835 sample.set_size(fdim);
836
837 const CorePointDesc* desc = nullptr;
838 const ccColor::Rgb* col = &ccColor::lightGreyRGB;
839
840 if (i < nsamples1)
841 {
842 desc = &descriptors1[i];
843 col = &ccColor::blueRGB;
844 }
845 else if (i < nsamples)
846 {
847 desc = &descriptors2[i - nsamples1];
848 col = &ccColor::redRGB;
849 }
850 else if (evaluationDescriptors)
851 {
852 desc = &evaluationDescriptors->at(i - nsamples);
853 //col = &ccColor::lightGreyRGB;
854 }
855 else
856 {
857 assert(false);
858 continue;
859 }
860
861 assert(desc && col);
862 size_t shift = (paramsCount - scaleCount) * dimPerScale; //if we use less scales than parameters
863 for (size_t j = 0; j < fdim; ++j)
864 {
865 sample(j) = desc->params[shift + j];
866 }
867
868 double x = trainer.predict(sample);
869 double y = orthoTrainer.predict(sample);
870 mscCloud->addPoint( CCVector3( static_cast<float>(x),
871 static_cast<float>(y),
872 0) );
873 if (hasColors && col)
874 {
875 mscCloud->addColor(*col);
876 }
877 }
878
879 //DGM: we only use the evaluation cloud for representation now!
880 #if 0
881 if (evaluationDescriptors)
882 {
883 // radius from probabilistic SVM, diameter = 90% chance of correct classif
884 PointCoordinateType radius = static_cast<PointCoordinateType>(-log(1.0/0.9 - 1.0)/2.0);
885
886 //we'll need the octree
887 ccProgressDialog pDlg(true,parentWindow);
888 if (!mscCloud->computeOctree(&pDlg))
889 {
890 if (app)
891 app->dispToConsole("Not enough memory to determine the classifier boundary on evaluation cloud!",ccMainAppInterface::ERR_CONSOLE_MESSAGE);
892 return false;
893 }
894 ccOctree* octree = mscCloud->getOctree();
895 assert(octree);
896 unsigned char octreeLevel = octree->findBestLevelForAGivenNeighbourhoodSizeExtraction(radius);
897
898 int minNeighborCount = 0;
899 Classifier::Point2D bestDir(0,0);
900 Classifier::Point2D bestStartingPoint(0,0);
901
902 const int c_searchTransSteps = 13; // 2*13=26 steps between the reference points
903 const int c_searchDirCount = 90; // from 0 to 180 each 2 degree (unoriented lines)
904
905 CosSinTable<c_searchDirCount> tableCosSin;
906 float transStep = mscCloud->getOwnBB().getMaxBoxDim() / (c_searchTransSteps*2);
907
908 //progress notification
909 pDlg.reset();
910 pDlg.setCancelButton(0);
911 pDlg.setWindowTitle("Determining boundary line");
912 pDlg.setRange(0,c_searchTransSteps*2);
913 pDlg.setInfo(qPrintable(QString("Search steps: %1").arg(c_searchTransSteps*2)));
914
915 //we look for the line with the least number of neighbor points
916 for (int td=0; td<=c_searchTransSteps*2; ++td)
917 {
918 //strating point
919 Classifier::Point2D A = classifier.refPointNeg + (classifier.refPointPos - classifier.refPointNeg) * (static_cast<float>(td) / static_cast<float>(c_searchTransSteps*2));
920
921 // now we swipe a decision boundary in each direction around the point
922 // and look for the lowest overall density along the boundary
923 int sumds[c_searchDirCount];
924
925 // for each orientation
926 int minDirIndex = 0;
927 for (int sd=0; sd<c_searchDirCount; ++sd)
928 {
929 // unit vector in the direction of the line
930 Classifier::Point2D u( tableCosSin.cosines[sd],
931 tableCosSin.sines[sd] );
932 sumds[sd] = 0;
933 for (int sp = -c_searchTransSteps; sp <= c_searchTransSteps; ++sp)
934 {
935 float s = sp * transStep;
936
937 // use the parametric P2D = A + u*s formulation of a line
938 Classifier::Point2D P2D = A + u * s;
939
940 CCVector3 P(P2D.x,P2D.y,0);
941 CCCoreLib::DgmOctree::NeighboursSet Yk;
942 int count = octree->getPointsInSphericalNeighbourhood(P,radius,Yk,octreeLevel);
943
944 // count the number of neighbors
945 sumds[sd] += count;
946 }
947
948 // keep track of the best direction for this starting point
949 if (sumds[sd] < sumds[minDirIndex])
950 minDirIndex = sd;
951 }
952
953 if (td == 0 || sumds[minDirIndex] < minNeighborCount)
954 {
955 minNeighborCount = sumds[minDirIndex];
956 bestDir.x = tableCosSin.cosines[minDirIndex];
957 bestDir.y = tableCosSin.sines[minDirIndex];
958 bestStartingPoint = A;
959 }
960
961 //progress notification
962 pDlg.setValue(td);
963 }
964
965 pDlg.close();
966
967 // decision boundary in this 2D space
968 boundaryCenter = bestStartingPoint;
969 boundaryDir = bestDir;
970 }
971 else
972 #endif
973 {
974 //evaluate the boundary simply with the two input "class" clouds
975 Classifier::Point2D c1(0, 0);
976 Classifier::Point2D c2(0, 0);
977 unsigned n1 = 0;
978 unsigned n2 = 0;
979 ComputeReferencePoints(c2, c1, proj1, proj2, labels, &n2, &n1);
980
981 Classifier::Point2D w_vect = c2 - c1;
982 w_vect.normalize();
983 Classifier::Point2D w_orth(-w_vect.y, w_vect.x);
984
985 double cba2_max = 0;
986 const int c_searchSteps = 180;
987 CosSinTable<c_searchSteps> tableCosSin;
988
989 //progress notification
990 ccProgressDialog pDlg(false, parentWindow);
991 pDlg.setWindowTitle("Determining boundary line");
992 pDlg.setRange(0, c_searchSteps);
993 pDlg.setInfo(qPrintable(QString("Search steps: %1").arg(c_searchSteps)));
994
995 for (int sd = 1; sd < c_searchSteps; ++sd)
996 {
997 Classifier::Point2D v(tableCosSin.cosines[sd],
998 tableCosSin.sines[sd]);
999
1000 dlib::matrix<double, 2, 2> basis;
1001 Classifier::Point2D base_vec1 = w_vect;
1002 Classifier::Point2D base_vec2 = w_vect * v.x + w_orth * v.y;
1003 basis(0, 0) = base_vec1.x; basis(0, 1) = base_vec2.x;
1004 basis(1, 0) = base_vec1.y; basis(1, 1) = base_vec2.y;
1005 basis = inv(basis);
1006
1007 double m1 = 0;
1008 double m2 = 0;
1009 std::vector<double> p1;
1010 std::vector<double> p2;
1011 p1.reserve(n1);
1012 p2.reserve(n2);
1013 for (size_t i = 0; i < nsamples; ++i)
1014 {
1015 dlib::matrix<double, 2, 1> P;
1016 P(0) = proj1[i];
1017 P(1) = proj2[i];
1018 P = basis * P;
1019 const double& d = P(0); // projection on w_vect along the slanted direction
1020 if (labels[i] < 0)
1021 {
1022 p1.push_back(d);
1023 m1 += d;
1024 }
1025 else
1026 {
1027 p2.push_back(d);
1028 m2 += d;
1029 }
1030 }
1031 m1 /= n1;
1032 m2 /= n2;
1033
1034 // search for optimal separation
1035 bool reversed = false;
1036 if (m1 > m2)
1037 {
1038 reversed = true;
1039 std::swap(m1, m2);
1040 p1.swap(p2);
1041 }
1042 ParallelSort(p1.begin(), p1.end());
1043 ParallelSort(p2.begin(), p2.end());
1044
1045 for (int i = 0; i <= 100; ++i)
1046 {
1047 double pos = m1 + i * (m2 - m1) / 100.0;
1048
1049 size_t idx1 = std::lower_bound(p1.begin(), p1.end(), pos) - p1.begin();
1050 size_t idx2 = std::lower_bound(p2.begin(), p2.end(), pos) - p2.begin();
1051
1052 double pr1 = idx1 / static_cast<double>(n1);
1053 double pr2 = 1.0 - idx2 / static_cast<double>(n2);
1054 double cba2 = std::abs(pr1 + pr2);
1055 if (cba2 > cba2_max)
1056 {
1057 cba2_max = cba2;
1058 double r = (pos - m1) / (m2 - m1);
1059 if (reversed)
1060 r = 1.0 - r;
1061 Classifier::Point2D center = c1 + (c2 - c1) * static_cast<float>(r);
1062 boundaryCenter = center;
1063 boundaryDir = base_vec2;
1064 }
1065 }
1066
1067 pDlg.setValue(sd);
1068 }
1069
1070 pDlg.close();
1071 }
1072
1073 //update classifier info (boundary)
1074 {
1075 PointCoordinateType l = mscCloud->getOwnBB().getDiagVec().y / 2;
1076 classifier.path.resize(2);
1077 classifier.path[0] = boundaryCenter + boundaryDir * l;
1078 classifier.path[1] = boundaryCenter - boundaryDir * l;
1079 }
1080 }
1081
1082 return true;
1083 }