Haar Wavelets

wavelets.js

// http://bearcave.com/misl/misl_tech/wavelets/index.html

class WaveletBase {
  constructor() {
    this.forward = 1;
    this.inverse = 2;
  }
  split(vec, N) {
    var half = N >> 1;
    var vc = vec.slice();
    for (var i = 0, j = 0; i < N; i = i + 2, j++) {
      vec[j] = vc[i];
      vec[half + j] = vc[i + 1];
    }
  }
  merge(vec, N) {
    var half = N >> 1;
    var vc = vec.slice();
    for (var i = 0, j = 0; i < N; i = i + 2, j++) {
      vec[i] = vc[j];
      vec[i + 1] = vc[half + j];
    }
  }
  forwardTrans(vec) {
    const N = vec.length;
    for (var n = N; n > 1; n = n >> 1) {
      this.split(vec, n);
      this.predict(vec, n, this.forward);
    }
    return vec;
  }
  inverseTrans(vec) {
    const N = vec.length;
    for (var n = 2; n <= N; n = n << 1) {
      this.predict(vec, n, this.inverse);
      this.merge(vec, n);
    }
    return vec;
  }
  predict(vec, N, direction) {
    throw 'Abstract Class!';
  }
}

export class WaveletLinearTransform extends WaveletBase {
  newY(y1, y2) {
     return 2 * y2 - y1;
  }
  predict(vec, N, direction) {
    const half = N >> 1;
    var predictVal = 0;
    for (var i = 0; i < half; i++) {
      var j = i + half;
      if (i < half-1) {
        predictVal = (vec[i] + vec[i+1])/2;
      }
      else if (N == 2) {
        predictVal = vec[0];
      }
      else {
        predictVal = this.newY(vec[i-1], vec[i]);
      }
      if (direction == this.forward) {
        vec[j] = vec[j] - predictVal;
      }
      else if (direction == this.inverse) {
        vec[j] = vec[j] + predictVal;
      }
    }
  }
}

export class WaveletPolyTransform extends WaveletBase {
  constructor() {
    super();
    this.numPts = 4;
    this.fourPointTable = this.create2DArray(this.numPts, this.numPts);
    this.twoPointTable = this.create2DArray(2, 2);
    this.fillTable(this.numPts, this.fourPointTable);
    this.fillTable(2, this.twoPointTable);
  }
  create2DArray(rows, cols) {
    var arr = new Array(rows);
    for (var i = 0;i < rows; i++) {
       arr[i] = new Array(cols);
    }
    return arr;
  }
  legrange(x, N, c) {
    var num, denom;
    for (var i = 0; i < N; i++) {
      num = 1;
      denom = 1;
      for (var k = 0; k < N; k++) {
        if (i != k) {
          num = num * (x - k);
          denom = denom * (i - k);
        }
      }
      c[i] = num / denom;
    }
  }
  fillTable(N, table) {
    var x;
    var n = N;
    var i = 0;
    for (x = 0.5; x < n; x = x + 1.0) {
      this.legrange(x, N, table[i]);
      i++;
    }
  }
  getCoef(x, n, c) {
    var table = null;
    var j = ~~x; // Math.trunc
    if (j < 0 || j >= n) {
      throw 'getCoef: n = ' + n + ', bad x value';
    }
    if (n == this.numPts) {
      table = this.fourPointTable;
    }
    else if (n == 2) {
      table = this.twoPointTable;
      c[2] = 0.0;
      c[3] = 0.0;
    }
    else {
      throw 'getCoef: bad value for N';
    }
    if (table != null) {
      for (var i = 0; i < n; i++) {
        c[i] = table[j][i];
      }
    }
  }
  interpPoint(x, N, d) {
    var c = new Array(this.numPts);
    var point = 0;
    var n = this.numPts;
    if (N < this.numPts) {
      n = N;
    }
    this.getCoef(x, n, c);
    if (n == this.numPts) {
      point = c[0]*d[0] + c[1]*d[1] + c[2]*d[2] + c[3]*d[3];
    }
    else if (n == 2) {
      point = c[0]*d[0] + c[1]*d[1];
    }
    return point;
  }
  fill(vec, d, N, start) {
    var n = this.numPts;
    if (n > N) {
      n = N;
    }
    var end = start + n;
    var j = 0;
    for (var i = start; i < end; i++) {
      d[j] = vec[i];
      j++;
    }
  }
  predict(vec, N, direction) {
    var half = N >> 1;
    var d = new Array(this.numPts);
    for (var i = 0; i < half; i++) {
      var predictVal;
      if (i == 0) {
        if (half == 1) {
          predictVal = vec[0];
        }
        else {
          this.fill(vec, d, N, 0);
          predictVal = this.interpPoint(0.5, half, d);
        }
      }
      else if (i == 1) {
        predictVal = this.interpPoint(1.5, half, d);
      }
      else if (i == half - 2) {
        predictVal = this.interpPoint(2.5, half, d);
      }
      else if (i == half - 1) {
        predictVal = this.interpPoint(3.5, half, d);
      }
      else {
        this.fill(vec, d, N, i - 1);
        predictVal = this.interpPoint(1.5, half, d);
      }
      var j = i + half;
      if (direction == this.forward) {
        vec[j] = vec[j] - predictVal;
      }
      else if (direction == this.inverse) {
        vec[j] = vec[j] + predictVal;
      }
      else {
        throw 'bad direction value';
      }
    }
  }
}