1 // This is gel/vdgl/vdgl_digital_region.cxx
2 #include <iostream>
3 #include <cmath>
4 #include "vdgl_digital_region.h"
5 //:
6 // \file
7
8 #ifdef _MSC_VER
9 # include "vcl_msvc_warnings.h"
10 #endif
11 #include <cassert>
12 #include <vnl/algo/vnl_svd.h>
13 #include "vnl/vnl_float_3.h"
14
15 #ifndef MAX_ROUNDOFF
16 #define MAX_ROUNDOFF .000025
17 #endif
18
19 #define near_zero(a) (std::fabs (a) < MAX_ROUNDOFF)
20
clone() const21 vsol_spatial_object_2d* vdgl_digital_region::clone() const
22 {
23 return new vdgl_digital_region(*this);
24 }
25
26 //-------------------------------------------------------------------------
27 // Constructors
28 //
vdgl_digital_region(vdgl_digital_region const & r)29 vdgl_digital_region::vdgl_digital_region(vdgl_digital_region const& r)
30 : vsol_region_2d(r),
31 npts_given_(false), npts_(0), pixel_size_(1.f), xp_(nullptr), yp_(nullptr), pix_(nullptr),
32 max_(0), min_((unsigned short)(-1)), xo_(0.f), yo_(0.f),
33 io_(0.f), io_stdev_(0.0f), pix_index_(0),
34 fit_valid_(false), scatter_matrix_valid_(false),
35 X2_(0), Y2_(0), I2_(0), XY_(0), XI_(0), YI_(0), error_(0), sigma_sq_(0)
36 {
37 if(r.Npix() == 0)
38 return;
39 for (unsigned int i = 0; i<r.Npix(); ++i)
40 this->IncrementMeans(r.Xj()[i], r.Yj()[i], r.Ij()[i]);
41 this->InitPixelArrays();
42 for (unsigned int i = 0; i<r.Npix(); i++)
43 this->InsertInPixelArrays(r.Xj()[i], r.Yj()[i], r.Ij()[i]);
44 this->ComputeIntensityStdev();
45 }
46
vdgl_digital_region(int npts,const float * xp,const float * yp,const unsigned short * pix)47 vdgl_digital_region::vdgl_digital_region(int npts, const float* xp, const float* yp,
48 const unsigned short *pix)
49 : vsol_region_2d(),
50 npts_given_(false), npts_(0), pixel_size_(1.f), xp_(nullptr), yp_(nullptr), pix_(nullptr),
51 max_(0), min_((unsigned short)(-1)), xo_(0.f), yo_(0.f),
52 io_(0.f), io_stdev_(0.0f), pix_index_(0),
53 fit_valid_(false), scatter_matrix_valid_(false),
54 X2_(0), Y2_(0), I2_(0), XY_(0), XI_(0), YI_(0), error_(0), sigma_sq_(0)
55 {
56 assert(npts > 0);
57 for (int i = 0; i<npts; i++)
58 this->IncrementMeans(xp[i], yp[i], pix[i]);
59 this->InitPixelArrays();
60 for (unsigned int i = 0; i<npts_; i++)
61 this->InsertInPixelArrays(xp[i], yp[i], pix[i]);
62 this->ComputeIntensityStdev();
63 }
64
65 //-------------------------------------------------------------------------
66 //
67 // Destructor.
68 //
~vdgl_digital_region()69 vdgl_digital_region::~vdgl_digital_region()
70 {
71 delete[] xp_;
72 delete[] yp_;
73 delete[] pix_;
74 }
75
76 //-------------------------------------------------------
77 //: The X pixel coordinate
X() const78 float vdgl_digital_region::X() const
79 {
80 if (pix_index_<0 || pix_index_ >= (int)npts_)
81 return 0.0f;
82 else
83 return xp_[pix_index_];
84 }
85
86 //-------------------------------------------------------
87 //: The Y pixel coordinate
Y() const88 float vdgl_digital_region::Y() const
89 {
90 if (pix_index_<0 || pix_index_ >= (int)npts_)
91 return 0.0f;
92 else
93 return yp_[pix_index_];
94 }
95
96 //-------------------------------------------------------
97 //: The pixel Intensity
I() const98 unsigned short vdgl_digital_region::I() const
99 {
100 if (pix_index_<0 || pix_index_ >= (int)npts_)
101 return (unsigned short)0;
102 else
103 return pix_[pix_index_];
104 }
105
106 //-------------------------------------------------------
107 //: Modify the X pixel coordinate
set_X(float x)108 void vdgl_digital_region::set_X(float x)
109 {
110 if (pix_index_<0 || pix_index_ >= (int)npts_)
111 return;
112 xp_[pix_index_]=x;
113 }
114
115 //-------------------------------------------------------
116 //: Modify the Y pixel coordinate
set_Y(float y)117 void vdgl_digital_region::set_Y(float y)
118 {
119 if (pix_index_<0 || pix_index_ >= (int)npts_)
120 return;
121 yp_[pix_index_]=y;
122 }
123
124 //-------------------------------------------------------
125 //: Modify the pixel intensity
set_I(unsigned short I)126 void vdgl_digital_region::set_I(unsigned short I)
127 {
128 if (pix_index_<0 || pix_index_ >= (int)npts_)
129 return;
130 pix_[pix_index_]=I;
131 }
132
133 //--------------------------------------------------------
134 //:
135 // Initialize the region for accepting a stream of pixels
136 // through repeated calls to ::IncrementMeans(..)
ResetPixelData()137 void vdgl_digital_region::ResetPixelData()
138 {
139 npts_ = 0;
140 delete [] xp_; xp_ = nullptr;
141 delete [] yp_; yp_ = nullptr;
142 delete [] pix_; pix_ = nullptr;
143 xo_ = yo_ = io_ = io_stdev_=0.0f;
144 }
145
146 //-----------------------------------------------------------------
147 //:
148 // Used to scan through a set of pixels and acquire mean values
149 // for coordinates and intensity. This approach is necessary to
150 // accumulate scatter matrices which have zero mean. One scans
151 // the region pixels twice. First to get the means and number of
152 // region pixels and then to insert the pixel data into fixed arrays
IncrementMeans(float x,float y,unsigned short pix)153 void vdgl_digital_region::IncrementMeans(float x, float y,
154 unsigned short pix)
155 {
156 if(!npts_given_)
157 ++npts_;
158 xo_ += x;
159 yo_ += y;
160 io_ += pix;
161 }
162
163 //-----------------------------------------------------------------
164 //:
165 // Calculate the standard deviation of intensity for the region.
166 //
ComputeIntensityStdev()167 float vdgl_digital_region::ComputeIntensityStdev()
168 {
169 io_stdev_ = 0.0f; // start from scratch each time
170 float mean = this->Io(); // get the mean.
171 for (unsigned int i=0; i<npts_; i++) {
172 io_stdev_ += (pix_[i]-mean)*(pix_[i]-mean);
173 }
174 io_stdev_ = io_stdev_ * 1.0f/(npts_ - 1.0f);
175 io_stdev_ = std::sqrt(io_stdev_);
176 return io_stdev_;
177 }
178
179 //-----------------------------------------------------------------
180 //:
181 // Now we have the number of pixels so we can create the storage arrays.
InitPixelArrays()182 void vdgl_digital_region::InitPixelArrays()
183 {
184 assert(npts_ > 0);
185 delete [] xp_; xp_ = new float[npts_];
186 delete [] yp_; yp_ = new float[npts_];
187 delete [] pix_; pix_ = new unsigned short[npts_];
188 pix_index_ = 0;
189 min_ = (unsigned short)(-1);
190 max_ = 0;
191 }
SetNpts(int npts)192 void vdgl_digital_region::SetNpts(int npts){
193 npts_ = npts;
194 npts_given_ = true;
195 }
196 //------------------------------------------------------------------------
197 //: Insert pixel data into the face arrays.
InsertInPixelArrays(float x,float y,unsigned short pix)198 void vdgl_digital_region::InsertInPixelArrays(float x, float y,
199 unsigned short pix)
200 {
201 if (pix_index_<0||pix_index_>(int)npts_) return;
202 xp_[pix_index_] = x; yp_[pix_index_] = y;
203 pix_[pix_index_] = pix;
204 if (pix<min_) min_ = pix;
205 if (pix>max_) max_ = pix;
206 pix_index_++;
207 }
208
Xo() const209 float vdgl_digital_region::Xo() const
210 {
211 assert(npts_ > 0);
212 return xo_/npts_;
213 }
214
Yo() const215 float vdgl_digital_region::Yo() const
216 {
217 assert(npts_ > 0);
218 return yo_/npts_;
219 }
220
Io() const221 float vdgl_digital_region::Io() const
222 {
223 assert(npts_ > 0);
224 return io_/npts_;
225 }
226
Io_sd() const227 float vdgl_digital_region::Io_sd() const
228 {
229 assert(npts_ > 0);
230 return io_stdev_;
231 }
232
233 //: Individual scatter matrix elements
X2() const234 double vdgl_digital_region::X2() const
235 {
236 if (!scatter_matrix_valid_)
237 this->ComputeScatterMatrix();
238 return X2_;
239 }
240
Y2() const241 double vdgl_digital_region::Y2() const
242 {
243 if (!scatter_matrix_valid_)
244 this->ComputeScatterMatrix();
245 return Y2_;
246 }
247
XY() const248 double vdgl_digital_region::XY() const
249 {
250 if (!scatter_matrix_valid_)
251 this->ComputeScatterMatrix();
252 return XY_;
253 }
254
I2() const255 double vdgl_digital_region::I2() const
256 {
257 if (!scatter_matrix_valid_)
258 this->ComputeScatterMatrix();
259 return I2_;
260 }
261
XI() const262 double vdgl_digital_region::XI() const
263 {
264 if (!scatter_matrix_valid_)
265 this->ComputeScatterMatrix();
266 return XI_;
267 }
268
YI() const269 double vdgl_digital_region::YI() const
270 {
271 if (!scatter_matrix_valid_)
272 this->ComputeScatterMatrix();
273 return YI_;
274 }
275
276 //------------------------------------------------------------
277 //: Compute the diameter from the scatter matrix
Diameter() const278 float vdgl_digital_region::Diameter() const
279 {
280 // make sure the scatter matrix is valid
281 if (!scatter_matrix_valid_)
282 this->ComputeScatterMatrix();
283 if (this->Npix() < 4)
284 return 1.0f;
285 // construct the lower right 2x2 matrix of S, s.
286 vnl_matrix<double> s(2, 2, 0.0);
287 for (int r = 1; r<=2; r++)
288 for (int c = 1; c<=2; c++)
289 s(r-1,c-1) = Si_(r,c);
290 //Compute SVD of s to get diameter
291 vnl_svd<double> svd(s);
292 if (svd.rank()!=2)
293 return float(std::sqrt(this->area()));
294 //The factor of two is to estimate the extreme limit of the distribution
295 double radius = 2*std::sqrt(std::fabs(svd.W(0))+ std::fabs(svd.W(1)));
296 return float(2*radius);//diameter
297 }
298
299 //------------------------------------------------------------
300 //: Compute the aspect ratio from the scatter matrix
AspectRatio() const301 float vdgl_digital_region::AspectRatio() const
302 {
303 // make sure the scatter matrix is valid
304 if (!scatter_matrix_valid_)
305 this->ComputeScatterMatrix();
306 if (this->Npix() < 4)
307 return 1.0f;
308 // construct the lower right 2x2 matrix of S, s.
309 vnl_matrix<double> s(2, 2, 0.0);
310 for (int r = 1; r<=2; r++)
311 for (int c = 1; c<=2; c++)
312 s(r-1,c-1) = Si_(r,c);
313 //Compute SVD of s to get aspect ratio
314 vnl_svd<double> svd(s);
315 if (svd.rank()!=2)
316 return 1.0f;
317 return (float)std::sqrt(svd.W(0)/svd.W(1));
318 }
319
320 //------------------------------------------------------------
321 //: Compute the principal orientation of the region.
322 // major_axis is a 2-d vector representing the orientation.
PrincipalOrientation(vnl_float_2 & major_axis)323 bool vdgl_digital_region::PrincipalOrientation(vnl_float_2& major_axis)
324 {
325 // make sure the scatter matrix is valid
326 if (!scatter_matrix_valid_)
327 this->ComputeScatterMatrix();
328 if (this->Npix() < 4)
329 {
330 std::cout << "In vdgl_digital_region::PrincipalOrientation(..) Npts<4\n";
331 major_axis[0]=1.0; major_axis[1]=0.0;
332 return false;
333 }
334 // construct the lower right 2x2 matrix of S, s.
335 vnl_matrix<double> s(2, 2, 0.0);
336 for (int r = 1; r<=2; r++)
337 for (int c = 1; c<=2; c++)
338 s(r-1,c-1) = Si_(r,c);
339 //Compute SVD of s to get aspect ratio
340 vnl_svd<double> svd(s);
341 if (svd.rank()!=2)
342 {
343 std::cout << "In vdgl_digital_region::PrincipalOrientation(..) Insufficient rank\n";
344 major_axis[0]=1.0; major_axis[1]=0.0;
345 return false;
346 }
347 vnl_matrix<double> v = svd.V();
348 //2 sigma gives a good estimate of axis length (sigma = principal eigenvalue)
349 double radius = 2*std::sqrt(std::fabs(svd.W(0)));
350 major_axis[0]=float(v(0,0)*radius);
351 major_axis[1]=float(v(1,0)*radius);
352 return true;
353 }
354
Ix() const355 double vdgl_digital_region::Ix() const
356 {
357 if (!fit_valid_)
358 this->DoPlaneFit();
359 return Ix_;
360 }
361
Iy() const362 double vdgl_digital_region::Iy() const
363 {
364 if (!fit_valid_)
365 this->DoPlaneFit();
366 return Iy_;
367 }
368
369
370 //--------------------------------------------------------------
371 //: Update the scatter matrix elements.
372 // The means are subtracted from the input values before incrementing.
373 // Thus the scatter matrix is formed with a coordinate system at the origin.
IncrByXYI(double x,double y,int intens) const374 void vdgl_digital_region::IncrByXYI(double x, double y, int intens) const
375 {
376 fit_valid_=false;
377 scatter_matrix_valid_=false;
378 double dbx = x - this->Xo(), dby = y - this->Yo();
379 double dint = (double)intens- this->Io();
380 X2_ += dbx*dbx; Y2_ += dby*dby; I2_ += dint*dint;
381 XY_ += dbx*dby; XI_ += dbx*dint; YI_ += dby*dint;
382 }
383
384 //-------------------------------------------
385 //: The scatter matrix (upper 3x3) is transformed to the origin by subtracting off the means.
ComputeScatterMatrix() const386 void vdgl_digital_region::ComputeScatterMatrix() const
387 {
388 if (!npts_)
389 {
390 std::cout << "In vdgl_digital_region::ComputeScatterMatrix() - no pixels\n";
391 return;
392 }
393 X2_ = 0; Y2_ = 0; I2_ = 0;
394 XY_ = 0; XI_ = 0; YI_ = 0;
395
396 for (this->reset(); this->next();)
397 this->IncrByXYI(this->X(), this->Y(), this->I());
398
399
400 //The Scatter Matrix
401 //
402 // - -
403 // | I^2 XI YI |
404 // | |
405 // | XI X^2 XY |
406 // | |
407 // | YI XY Y^2 |
408 // - -
409 //
410 Si_(0,0) = I2_/npts_;
411 Si_(1,0) = Si_(0,1) = XI_/npts_;
412 Si_(2,0) = Si_(0,2) = YI_/npts_;
413 Si_(1,1) = X2_/npts_;
414 Si_(2,1) = Si_(1,2) = XY_/npts_;
415 Si_(2,2) = Y2_/npts_;
416 scatter_matrix_valid_ = true;
417 }
418
419 //---------------------------------------------------------------
420 //: Computes the squared deviation from the sample mean
421 //
ComputeSampleResidual() const422 double vdgl_digital_region::ComputeSampleResidual() const
423 {
424 if (!fit_valid_)
425 this->DoPlaneFit();
426 return Si_(0,0) + Si_(1,1) + Si_(2,2);
427 }
428
429 //: Solve for the fitted plane.
430 // Closed form solution in terms of the scatter matrix.
DoPlaneFit() const431 void vdgl_digital_region::DoPlaneFit() const
432 {
433 assert(npts_ >= 4);
434 fit_valid_ = true;
435
436 if (!scatter_matrix_valid_)
437 this->ComputeScatterMatrix();
438
439 double den = Si_(1,1)*Si_(2,2)
440 - Si_(1,2)*Si_(2,1);
441 if (near_zero(den))
442 {
443 std::cout << "In vdgl_digital_region::SolveForPlane(..) determinant near zero\n";
444 Ix_ = Iy_ = 0;
445 error_ = Si_(0,0);
446 sigma_sq_ = Si_(0,0) + Si_(1,1) + Si_(2,2);
447 return;
448 }
449 double adet = Si_(0,1)*Si_(2,2)
450 - Si_(0,2)*Si_(2,1);
451 double bdet = Si_(0,2)*Si_(1,1)
452 - Si_(0,1)*Si_(1,2);
453 Ix_ = adet/den;
454 Iy_ = bdet/den;
455 error_ = Si_(0,0) - 2*Ix_*Si_(0,1) - 2*Iy_*Si_(0,2)
456 + Ix_*Ix_*Si_(1,1) + 2*Ix_*Iy_*Si_(1,2) + Iy_*Iy_*Si_(2,2);
457 sigma_sq_ = this->ComputeSampleResidual();
458 }
459
460
PrintFit() const461 void vdgl_digital_region::PrintFit() const
462 {
463 if (!fit_valid_)
464 this->DoPlaneFit();
465 std::cout << "IntensityFit(In Plane Coordinates): "
466 << "Number of Points =" << npts_ << std::endl
467 << "Scatter Matrix:\n"
468 << "X2 Y2 I2 " << X2() << ' ' << Y2() << ' ' << I2() << std::endl
469 << "XY XI YI = " << XY() << ' ' << XI() << ' ' << YI() << std::endl
470 << "Xo Yo Io " << Xo() << ' ' << Yo() << ' ' << Io() << std::endl
471 << "fitted Plane:\n"
472 << "di/dx " << this->Ix() << std::endl
473 << "di/dy " << this->Iy() << std::endl
474 << "sample variance: " << this->Var()<< std::endl
475 << "squared cost: " << error_ << std::endl
476 << "average cost: " << std::sqrt(error_) << std::endl << std::endl;
477 }
478
479 #if 0
480 //-----------------------------------------------------------
481 //: Return a package of fitted coefficients
482 //
483 IntensityCoef_ref vdgl_digital_region::GetIntCoef() const
484 {
485 if (!fit_valid_)
486 this->DoPlaneFit();
487 return new IntensityCoef(this->Npix(), float(this->Var()),
488 float(this->Io()), float(this->Ix()),
489 float(this->Iy()));
490 }
491 #endif
492
493 //-------------------------------------------------------
494 //: The Residual Intensity
Ir() const495 float vdgl_digital_region::Ir() const
496 {
497 if (pix_index_<0 || pix_index_ >= (int)npts_)
498 return 0.0f;
499 if (npts_<4)
500 return 0.0f;
501
502 if (!fit_valid_)
503 {
504 int initial_pix_index = pix_index_;//Save the current pix_index_ state
505 this->DoPlaneFit();
506 pix_index_ = initial_pix_index;//Restore the pix_index_ state
507 }
508 auto val = float(this->I());
509 float io = this->Io(),
510 ix = float(this->Ix()), x = this->X(), xo = this->Xo(),
511 iy = float(this->Iy()), y = this->Y(), yo = this->Yo();
512 float plane_int = io + ix*(x - xo) + iy*(y-yo);
513
514 return val - plane_int;
515 }
516
transform(vnl_float_3x3 const & t)517 bool vdgl_digital_region::transform(vnl_float_3x3 const& t)
518 {
519 //Transform the Pixels
520 if (npts_ == 0)
521 return false;
522 for (unsigned int i=0; i<npts_; i++)
523 {
524 vnl_float_3 p = t * vnl_float_3(xp_[i], yp_[i], 1.0f);
525 xp_[i]=p[0]/p[2];
526 yp_[i]=p[1]/p[2];
527 }
528 //Transform the mean pixel position
529 vnl_float_3 m = t * vnl_float_3(this->Xo(), this->Yo(), 1.0f);
530 xo_ = m[0]/m[2]*npts_;
531 yo_ = m[1]/m[2]*npts_;
532 fit_valid_ = false;
533 scatter_matrix_valid_=false;
534 return true;
535 }
536
537 //--------------------------------------------------------
538 //: Compute the histogram
histogram(int nbins)539 std::vector<unsigned int> vdgl_digital_region::histogram(int nbins)
540 {
541 assert(nbins > 0);
542 if (nbins == 1) return std::vector<unsigned int>(1, npts_);
543 std::vector<unsigned int> hist(nbins, 0U);
544 if (npts_ == 0) return hist;
545 float res = max_-min_, step = res/nbins + 1e-6f;
546 for (unsigned int i =0; i<npts_; ++i)
547 ++hist[int((pix_[i]-min_)/step)];
548 return hist;
549 }
550
residual_histogram(int nbins,float * min,float * max) const551 std::vector<unsigned int> vdgl_digital_region::residual_histogram(int nbins,
552 float* min,
553 float* max) const
554 {
555 assert(nbins > 0);
556 if (nbins == 1) return std::vector<unsigned int>(1, npts_);
557 std::vector<unsigned int> hist(nbins, 0U);
558 if (npts_ == 0) return hist;
559 this->reset();
560 float mini = this->Ir(), maxi=mini;
561 while (this->next())
562 {
563 float ir = this->Ir();
564 if (ir<mini) mini = ir;
565 if (ir>maxi) maxi = ir;
566 }
567 if (min) *min = mini;
568 if (max) *max = maxi;
569 float res = maxi-mini, step = res/nbins + 1e-6f;
570 for (this->reset(); this->next(); )
571 ++hist[int((this->Ir()-mini)/step)];
572 return hist;
573 }
574 //: ==== public functions ===
575 //: merge two regions r12 must exist
merge(vdgl_digital_region * r1,vdgl_digital_region * r2,vdgl_digital_region * & r12)576 void merge(vdgl_digital_region* r1, vdgl_digital_region* r2, vdgl_digital_region*& r12 )
577 {
578 if(!r1 || !r2){
579 r12 = nullptr;
580 return;
581 }
582 unsigned int n1 = r1->Npix(), n2 = r2->Npix();
583 if(n1 == 0 && n2 == 0){
584 r12 = nullptr;
585 return;
586 }
587 if (n1==0)
588 r12 = r2;
589 if (n2==0)
590 r12 = r1;
591 int n = n1 + n2;
592 r12->SetNpts(n);
593 r12->InitPixelArrays();
594
595 float const* X1 = r1->Xj();
596 float const* Y1 = r1->Yj();
597 unsigned short const* I1 = r1->Ij();
598
599 float const* X2 = r2->Xj();
600 float const* Y2 = r2->Yj();
601 unsigned short const* I2 = r2->Ij();
602
603 for (unsigned i = 0; i<n2; i++)
604 {
605 r12->IncrementMeans(X2[i],Y2[i],I2[i]);
606 r12->InsertInPixelArrays(X2[i],Y2[i],I2[i]);
607 }
608 for (unsigned i = 0; i<n1; i++)
609 {
610 r12->IncrementMeans(X1[i],Y1[i],I1[i]);
611 r12->InsertInPixelArrays(X1[i],Y1[i],I1[i]);
612 }
613 }
614
merge(vdgl_digital_region_sptr const & r1,vdgl_digital_region_sptr const & r2)615 vdgl_digital_region_sptr merge(vdgl_digital_region_sptr const& r1, vdgl_digital_region_sptr const& r2){
616 auto* r12 = new vdgl_digital_region();
617 merge(r1.ptr(), r2.ptr(), r12);
618 return r12;
619 }
620