1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646
|
/************************************************************************/
/* */
/* vspline - a set of generic tools for creation and evaluation */
/* of uniform b-splines */
/* */
/* Copyright 2015 - 2018 by Kay F. Jahnke */
/* */
/* The git repository for this software is at */
/* */
/* https://bitbucket.org/kfj/vspline */
/* */
/* Please direct questions, bug reports, and contributions to */
/* */
/* kfjahnke+vspline@gmail.com */
/* */
/* Permission is hereby granted, free of charge, to any person */
/* obtaining a copy of this software and associated documentation */
/* files (the "Software"), to deal in the Software without */
/* restriction, including without limitation the rights to use, */
/* copy, modify, merge, publish, distribute, sublicense, and/or */
/* sell copies of the Software, and to permit persons to whom the */
/* Software is furnished to do so, subject to the following */
/* conditions: */
/* */
/* The above copyright notice and this permission notice shall be */
/* included in all copies or substantial portions of the */
/* Software. */
/* */
/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
/* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
/* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
/* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
/* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
/* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
/* OTHER DEALINGS IN THE SOFTWARE. */
/* */
/************************************************************************/
/// \file bootstrap.cc
///
/// \brief Code to calculate b-spline basis function values at half
/// unit steps, and prefilter poles.
///
/// These calculations are done using GNU GSL, BLAS and GNU GMP
/// which are not used in other parts of vspline. this file also has
/// code to verify that the precomputed data in <vspline/poles.h>
/// are valid. TODO make that a separate program
///
/// In contrast to my previous implementation of generating the
/// precomputed values (prefilter_poles.cc, now gone), I don't
/// compute the values one-by-one using recursive functions, but
/// instead build them layer by layer, each layer using it's
/// predecessor. This makes the process very fast, even for
/// large spline degrees.
///
/// In my tests, I found that with the very precise basis function
/// values obtained with GMP, I could get GSL to provide raw values
/// for the prefilter poles up to degree 45, above which it would
/// miss roots. So this is where I set the limit, and I think it's
/// unlikely anyone would ever want more than degree 45. If they
/// do, they'll have to find other polynomial root code.
///
/// compile: g++ -O3 -std=gnu++11 bootstrap.cc -obootstrap \
/// -lgmpxx -lgmp -lgsl -lblas -pthread
///
/// run by simply issuing './bootstrap' on the command line. you may
/// want to redirect output to a file. The output should be equal
/// to the values in vspline/poles.h
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <limits>
#include <numeric>
#include <assert.h>
#include <gsl/gsl_poly.h>
#include <gmpxx.h>
// #include <eigen3/unsupported/Eigen/Polynomials>
#include <vspline/vspline.h>
// In my trials, I could take the spline degree up to 45 when calculating
// the prefilter poles. The basis function value can be found for arbitrary
// degrees.
#define degree_limit 46
// when using mpf_class from GMP, we use 512 bits of precision.
#define mpf_bits 512
// we want to build a table of basis function values at multiples
// of 1/2 mimicking the Cox-de Boor recursion. We only need one half
// of the table since the basis function is symmetric (b(x) == b(-x))
// - except for degree 0, which needs special treatment.
// Note that we 'invert' the Cox-de Boor recursion and generate
// the result iteratively, starting with degree 0. This results in
// every single difference relation being executed excactly once,
// which makes the iterative solution very fast.
// Note the use of x2 throughout, this is the doubled argument,
// so that we can operate in integral maths throughout the basis
// function calculations (we use mpq_class for arbitrary-sized
// fractions, so there is no error at all)
// We make the table one column wider than strictly necessary to
// allow access to x2 outside the range, in which case we want to
// access a location containing 0.
mpq_class basis_table [ degree_limit ] [ degree_limit + 1 ] ;
// we want to access the table both for reading and writing, mapping
// negative x2 to positive ones and treating access to the first row
// (for degree 0) specially. Once the table is filled, we can access
// the table at arbitrary x2.
mpq_class & access_table ( int degree , int x2 )
{
if ( degree >= degree_limit || degree < 0 )
throw std::invalid_argument ( "access with degree out of bounds" ) ;
int column ;
// at degree 0, we have no symmetry: the basis function is
// 1 for x2 == -1 and x2 == 0.
if ( degree == 0 )
{
if ( x2 == -1 || x2 == 0 )
column = 0 ;
else
column = 1 ;
}
// for all other degrees the basis function is symmetric
else
column = x2 >= 0 ? x2 : -x2 ;
// for out-of-range x2, land in the last column, which is 0.
column = std::min ( column , degree_limit ) ;
return basis_table [ degree ] [ column ] ;
}
// subroutine filling the table at a specific x2 and degree.
// we rely on the table being filled correctly up to degree - 1
void _fill_basis_table ( int x2 , int degree )
{
// look up the neighbours one degree down and one to the
// left/right
mpq_class & f1 ( access_table ( degree - 1 , x2 + 1 ) ) ;
mpq_class & f2 ( access_table ( degree - 1 , x2 - 1 ) ) ;
// use the recursion to calculate the current value and store
// that value at the appropriate location in the table
access_table ( degree , x2 )
= ( f1 * ( degree + 1 + x2 )
+ f2 * ( degree + 1 - x2 ) )
/ ( 2 * degree ) ;
}
// to fill the whole table, we initialize the single value
// in the first row, then fill the remainder by calling the
// single-value subroutine for all non-zero locations
void fill_basis_table()
{
access_table ( 0 , 0 ) = 1 ;
for ( int degree = 1 ; degree < degree_limit ; degree++ )
{
for ( int x2 = 0 ; x2 <= degree ; x2++ )
_fill_basis_table ( x2 , degree ) ;
}
}
// routine for one iteration of Newton's method applied to
// a polynomial with ncoeff coefficients stored at pcoeff.
// the polynomial and it's first derivative are computed
// at x, then the quotient of function value and derivative
// is subtracted from x, yielding the result, which is
// closer to the zero we're looking for.
template < typename dtype >
void newton ( dtype & result , dtype x , int ncoeff , dtype * pcoeff )
{
dtype * pk = pcoeff + ncoeff - 1 ; // point to last pcoefficient
dtype power = 1 ; // powers of x
int xd = 1 ; // ex derivative, n in (x^n)' = n(x^(n-1))
dtype fx = 0 ; // f(x)
dtype dfx = 0 ; // f'(x)
// we work our way back to front, starting with x^0 and raising
// the power with each iteration
fx += power * *pk ;
for ( ; ; )
{
--pk ;
if ( pk == pcoeff )
break ;
dfx += power * xd * *pk ;
xd++ ;
power *= x ;
fx += power * *pk ;
}
power *= x ;
fx += power * *pk ;
result = x - fx / dfx ;
}
// calculate_prefilter_poles relies on the table with basis function
// values having been filled with fill_basis_table(). It extracts
// the basis function values at even x2 (corresponding to whole x)
// as double precision values, takes these to be coefficients of
// a polynomial, and uses gsl and blas to obtain the roots of this
// polynomial. The real parts of those roots which are less than one
// are the raw values of the filter poles we're after.
// Currently I don't have an arbitrary-precision root finder, so I
// use the double precision one from GSL and submit the 'raw' result
// to polishing code in high precision arithmetic. This only works
// as far as the root finder can go, I found from degree 46 onwards
// it fails to find some roots, so that's how far I take it for now.
// The poles are stored in a std::vector of mpf_class and returned.
// These values are precise to mpf_bits, since after using gsl's
// root finder in double precision, they are polished as mpf_class
// values with the newton method, so the very many postcomma digits
// we print out below are all proper significant digits.
void calculate_prefilter_poles ( std::vector<mpf_class> &res ,
int degree )
{
const int r = degree / 2 ;
// we need storage for the coefficients of the polynomial
// first in double precision to feed gsl's root finder,
// then in mpf_class, to do the polishing
double coeffs [ 2 * r + 1 ] ;
mpf_class mpf_coeffs [ 2 * r + 1 ] ;
// here is space for the roots we want to compute
double roots [ 4 * r + 2 ] ;
// we fetch the coefficients from the table of b-spline basis
// function values at even x2, corresponding to whole x
double * pcoeffs = coeffs ;
mpf_class * pmpf_coeffs = mpf_coeffs ;
for ( int x2 = -r * 2 ;
x2 <= r * 2 ;
x2 += 2 , pcoeffs++ , pmpf_coeffs++ )
{
*pmpf_coeffs = access_table ( degree , x2 ) ;
*pcoeffs = access_table ( degree , x2 ) . get_d() ;
}
// we set up the environment gsl needs to find the roots
gsl_poly_complex_workspace * w
= gsl_poly_complex_workspace_alloc ( 2 * r + 1 ) ;
// now we call gsl's root finder
gsl_poly_complex_solve ( coeffs , 2 * r + 1 , w , roots ) ;
// and release it's workspace
gsl_poly_complex_workspace_free ( w ) ;
// we only look at the real parts of the roots, which are stored
// interleaved real/imag. And we take them back to front, even though
// it doesn't matter which end we start with - but conventionally
// Pole[0] is the root with the largest absolute, so I stick with that.
// I tried using eigen alternatively, but it found less roots
// than gsl/blas, so I stick with the GNU code, but for the reference,
// here is the code to use with eigen3 - for degrees up to 23 it was okay
// when I last tested. TODO: maybe the problem is that I did not get
// long double values to start with, which is tricky from GMP
// {
// using namespace Eigen ;
//
// Eigen::PolynomialSolver<long double, Eigen::Dynamic> solver;
// Eigen::Matrix<long double,Dynamic, 1 > coeff(2*r+1);
//
// for ( int i = 0 ; i < 2*r+1 ; i++ )
// {
// // this is stupid: can't get a long double for an mpq_type
// // TODO take the long route via a string (sigh...)
// coeff[i] = mpf_coeffs[i].get_d() ;
// }
//
// solver.compute(coeff);
//
// const Eigen::PolynomialSolver<long double, Eigen::Dynamic>::RootsType & r
// = solver.roots();
//
// for ( int i = r.rows() - 1 ; i >= 0 ; i-- )
// {
// if ( std::fabs ( r[i].real() ) < 1 )
// {
// std::cout << "eigen gets " << r[i].real() << std::endl ;
// }
// }
// }
for ( int i = 2 * r - 2 ; i >= 0 ; i -= 2 )
{
if ( std::abs ( roots[i] ) < 1.0 )
{
// fetch a double precision root from gsl's output
// converting to high-precision
mpf_class root ( roots[i] ) ;
// for the polishing process, we need a few more
// high-precision values
mpf_class pa , // current value of the iteration
pb , // previous value
pdelta ; // delta we want to go below
pa = root , pb = 0 ;
pdelta = "1e-300" ;
// while we're not yet below delta
while ( ( pa - pb ) * ( pa - pb ) >= pdelta )
{
// assign current to previous
pb = pa ;
// polish current value
newton ( pa , pa , 2*r+1 , mpf_coeffs ) ;
}
// polishing iteration terminated, we're content and store the value
root = pa ;
res.push_back ( root ) ;
}
}
}
// forward recursive filter, used for testing
void forward ( mpf_class * x , int size , mpf_class pole )
{
mpf_class X = 0 ;
for ( int n = 1 ; n < size ; n++ )
{
x[n] = X = x[n] + pole * X ;
}
}
// backward recursive filter, used for testing
void backward ( mpf_class * x , int size , mpf_class pole )
{
mpf_class X = 0 ;
for ( int n = size - 2 ; n >= 0 ; n-- )
{
x[n] = X = pole * ( X - x[n] );
}
}
// to test the poles, we place the reconstruction kernel - a unit-spaced
// sampling of the basis function at integral x - into the center of a large
// buffer which is otherwise filled with zeroes. Then we apply all poles
// in sequence with a forward and a backward run of the prefilter.
// Afterwards, we expect to find a unit pulse in the center of the buffer.
// Since we use very high precision (see mpf_bits) we can set a conservative
// limit for the maximum error, here I use 1e-150. If this test throws up
// warnings, there might be something wrong with the code.
void test ( int size ,
const std::vector<mpf_class> & poles ,
int degree )
{
mpf_class buffer [ size ] ;
for ( int k = 0 ; k < size ; k++ )
{
buffer[k] = 0 ;
}
// calculate overall gain of the filter
mpf_class lambda = 1 ;
for ( int k = 0 ; k < poles.size() ; k++ )
lambda = lambda * ( 1 - poles[k] ) * ( 1 - 1 / poles[k] ) ;
int center = size / 2 ;
// put basis function samples into the buffer, applying gain
for ( int x2 = 0 ; x2 <= degree ; x2 += 2 )
buffer [ center - x2/2 ]
= buffer [ center + x2/2 ]
= lambda * access_table ( degree , x2 ) ;
// filter
for ( int k = 0 ; k < poles.size() ; k++ )
{
forward ( buffer , size , poles[k] ) ;
backward ( buffer , size , poles[k] ) ;
}
// test
mpf_class error = 0 ;
mpf_class max_error = 0 ;
for ( int x2 = 0 ; x2 <= degree ; x2 += 2 )
{
error = abs ( buffer [ center - x2/2 ] - ( x2 == 0 ? 1 : 0 ) ) ;
if ( error > max_error )
max_error = error ;
error = abs ( buffer [ center + x2/2 ] - ( x2 == 0 ? 1 : 0 ) ) ;
if ( error > max_error )
max_error = error ;
}
mpf_class limit = 1e-150 ;
if ( max_error > limit )
std::cerr << "WARNING: degree " << degree
<< " error exceeds limit 1e-150: "
<< max_error << std::endl ;
}
// we want to do the test in long double as well, to see how much
// downcasting the data to long double affects precision:
vspline::xlf_type get_xlf ( const mpf_class & _x )
{
long exp ;
std::string sign ( "+" ) ;
mpf_class x ( _x ) ;
if ( x < 0 )
{
x = -x ;
sign = std::string ( "-" ) ;
}
auto str = x.get_str ( exp , 10 , 64 ) ;
std::string res = sign + std::string ( "." ) + str
+ std::string ( "e" ) + std::to_string ( exp )
+ std::string ( "l" ) ;
vspline::xlf_type ld = std::stold ( res ) ;
return ld ;
} ;
// forward recursive filter, used for testing
void ldforward ( vspline::xlf_type * x , int size , vspline::xlf_type pole )
{
vspline::xlf_type X = 0 ;
for ( int n = 1 ; n < size ; n++ )
{
x[n] = X = x[n] + pole * X ;
}
}
// backward recursive filter, used for testing
void ldbackward ( vspline::xlf_type * x , int size , vspline::xlf_type pole )
{
vspline::xlf_type X = 0 ;
for ( int n = size - 2 ; n >= 0 ; n-- )
{
x[n] = X = pole * ( X - x[n] );
}
}
// test with values cast down to long double
void ldtest ( int size ,
const std::vector<mpf_class> & poles ,
int degree )
{
int nbpoles = degree / 2 ;
vspline::xlf_type buffer [ size ] ;
for ( int k = 0 ; k < size ; k++ )
{
buffer[k] = 0 ;
}
// calculate overall gain of the filter
vspline::xlf_type lambda = 1 ;
for ( int k = 0 ; k < nbpoles ; k++ )
{
auto ldp = get_xlf ( poles[k] ) ;
lambda = lambda * ( 1 - ldp ) * ( 1 - 1 / ldp ) ;
}
int center = size / 2 ;
// put basis function samples into the buffer, applying gain
for ( int x2 = 0 ; x2 <= degree ; x2 += 2 )
{
vspline::xlf_type bf = get_xlf ( access_table ( degree , x2 ) ) ;
buffer [ center - x2/2 ]
= buffer [ center + x2/2 ]
= lambda * bf ;
}
// filter
for ( int k = 0 ; k < nbpoles ; k++ )
{
auto ldp = get_xlf ( poles[k] ) ;
ldforward ( buffer , size , ldp ) ;
ldbackward ( buffer , size , ldp ) ;
}
// test
vspline::xlf_type error = 0 ;
vspline::xlf_type max_error = 0 ;
for ( int x2 = 0 ; x2 <= degree ; x2 += 2 )
{
error = std::abs ( buffer [ center - x2/2 ] - ( x2 == 0 ? 1 : 0 ) ) ;
if ( error > max_error )
max_error = error ;
error = std::abs ( buffer [ center + x2/2 ] - ( x2 == 0 ? 1 : 0 ) ) ;
if ( error > max_error )
max_error = error ;
}
vspline::xlf_type limit = 1e-12 ;
if ( max_error > limit )
std::cerr << "WARNING: degree " << degree
<< " ld error exceeds limit 1e-12: "
<< max_error << std::endl ;
}
#include <random>
int main ( int argc , char * argv[] )
{
mpf_set_default_prec ( mpf_bits ) ;
bool print_basis_function = true ;
bool print_prefilter_poles = true ;
bool print_umbrella_structures = true ;
std::cout << std::setprecision ( 64 ) ;
fill_basis_table() ;
mpf_class value ;
if ( print_basis_function )
{
for ( int degree = 0 ; degree < degree_limit ; degree++ )
{
std::cout << "const vspline::xlf_type K"
<< degree
<< "[] = {"
<< std::endl ;
for ( int x2 = 0 ; x2 <= degree ; x2++ )
{
value = access_table ( degree , x2 ) ;
std::cout << " XLF("
<< value
<< ") ,"
<< std::endl ;
get_xlf ( value ) ;
}
std::cout << "} ;"
<< std::endl ;
}
}
for ( int degree = 2 ; degree < degree_limit ; degree++ )
{
std::vector<mpf_class> res ;
calculate_prefilter_poles ( res , degree ) ;
if ( res.size() != degree / 2 )
{
std::cerr << "not enough poles for degree " << degree << std::endl ;
continue ;
}
if ( print_prefilter_poles )
{
std::cout << "const vspline::xlf_type Poles_"
<< degree
<< "[] = {"
<< std::endl ;
for ( int p = 0 ; p < degree / 2 ; p++ )
{
value = res[p] ;
std::cout << " XLF("
<< value
<< ") ,"
<< std::endl ;
}
std::cout << "} ;"
<< std::endl ;
}
// test if the roots are good
test ( 10000 , res , degree ) ;
// optional, to see what happens when data are cast down to long double
ldtest ( 10000 , res , degree ) ;
}
if ( print_umbrella_structures )
{
std::cout << std::noshowpos ;
std::cout << "const vspline::xlf_type* const precomputed_poles[] = {"
<< std::endl ;
std::cout << " 0, " << std::endl ;
std::cout << " 0, " << std::endl ;
for ( int i = 2 ; i < degree_limit ; i++ )
std::cout << " Poles_" << i << ", " << std::endl ;
std::cout << "} ;" << std::endl ;
std::cout << "const vspline::xlf_type* const precomputed_basis_function_values[] = {"
<< std::endl ;
for ( int i = 0 ; i < degree_limit ; i++ )
std::cout << " K" << i << ", " << std::endl ;
std::cout << "} ;" << std::endl ;
}
}
|