`package be.tarsos.dsp.wavelet.lift;`

/**

* <p>

* class LiftingSchemeBaseWavelet: base class for simple Lifting Scheme wavelets

* using split, predict, update or update, predict, merge steps.

* </p>

*

* <p>

* Simple lifting scheme wavelets consist of three steps, a split/merge step,

* predict step and an update step:

* </p>

* <ul>

* <li>

* <p>

* The split step divides the elements in an array so that the even elements are

* in the first half and the odd elements are in the second half.

* </p>

* </li>

* <li>

* <p>

* The merge step is the inverse of the split step. It takes two regions of an

* array, an odd region and an even region and merges them into a new region

* where an even element alternates with an odd element.

* </p>

* </li>

* <li>

* <p>

* The predict step calculates the difference between an odd element and its

* predicted value based on the even elements. The difference between the

* predicted value and the actual value replaces the odd element.

* </p>

* </li>

* <li>

* <p>

* The predict step operates on the odd elements. The update step operates on

* the even element, replacing them with a difference between the predict value

* and the actual odd element. The update step replaces each even element with

* an average. The result of the update step becomes the input to the next

* recursive step in the wavelet calculation.

* </p>

* </li>

*

* </ul>

*

* <p>

* The split and merge methods are shared by all Lifting Scheme wavelet

* algorithms. This base class provides the transform and inverse transform

* methods (forwardTrans and inverseTrans). The predict and update methods are

* abstract and are defined for a particular Lifting Scheme wavelet sub-class.

* </p>

*

* <p>

* <b>References:</b>

* </p>

*

* <ul>

* <li>

* <a href=" http://www.bearcave.com/misl/misl_tech/wavelets/lifting/index.html">

* <i>The Wavelet Lifting Scheme</i></a> by Ian Kaplan, www.bearcave.com. This

* is the parent web page for this Java source code.</li>

* <li>

* <i>Ripples in Mathematics: the Discrete Wavelet Transform</i> by Arne Jense

* and Anders la Cour-Harbo, Springer, 2001</li>

* <li>

* <i>Building Your Own Wavelets at Home</i> in <a

* href=" http://www.multires.caltech.edu/teaching/courses/waveletcourse/">

* Wavelets in Computer Graphics</a></li>

* </ul>

*

* <h4>

* Copyright and Use</h4>

*

* <p>

* You may use this source code without limitation and without fee as long as

* you include:

* </p>

* <blockquote> This software was written and is copyrighted by Ian Kaplan, Bear

* Products International, www.bearcave.com, 2001. </blockquote>

* <p>

* This software is provided "as is", without any warrenty or claim as to its

* usefulness. Anyone who uses this source code uses it at their own risk. Nor

* is any support provided by Ian Kaplan and Bear Products International.

* <p>

* Please send any bug fixes or suggested source changes to:

*

* <pre>

*

iank@bearcave.com

* </pre>

*

* @author Ian Kaplan

*/

public abstract class LiftingSchemeBaseWavelet {

/** "enumeration" for forward wavelet transform */

protected final int forward = 1;

/** "enumeration" for inverse wavelet transform */

protected final int inverse = 2;

/**

* Split the <i>vec</i> into even and odd elements, where the even elements

* are in the first half of the vector and the odd elements are in the

* second half.

*/

protected void split(float[] vec, int N) {

int start = 1;

int end = N - 1;

while (start < end) {

for (int i = start; i < end; i = i + 2) {

float tmp = vec[i];

vec[i] = vec[i + 1];

vec[i + 1] = tmp;

}

start = start + 1;

end = end - 1;

}

}

/**

* Merge the odd elements from the second half of the N element region in

* the array with the even elements in the first half of the N element

* region. The result will be the combination of the odd and even elements

* in a region of length N.

*/

protected void merge(float[] vec, int N) {

int half = N >> 1;

int start = half - 1;

int end = half;

while (start > 0) {

for (int i = start; i < end; i = i + 2) {

float tmp = vec[i];

vec[i] = vec[i + 1];

vec[i + 1] = tmp;

}

start = start - 1;

end = end + 1;

}

}

/**

* Predict step, to be defined by the subclass

*

* @param vec

*

input array

* @param N

*

size of region to act on (from 0..N-1)

* @param direction

*

forward or inverse transform

*/

protected abstract void predict(float[] vec, int N, int direction);

/**

* Update step, to be defined by the subclass

*

* @param vec

*

input array

* @param N

*

size of region to act on (from 0..N-1)

* @param direction

*

forward or inverse transform

*/

protected abstract void update(float[] vec, int N, int direction);

/**

* <p>

* Simple wavelet Lifting Scheme forward transform

* </p>

*

* <p>

* forwardTrans is passed an array of doubles. The array size must be a

* power of two. Lifting Scheme wavelet transforms are calculated in-place

* and the result is returned in the argument array.

* </p>

*

* <p>

* The result of forwardTrans is a set of wavelet coefficients ordered by

* increasing frequency and an approximate average of the input data set in

* vec[0]. The coefficient bands follow this element in powers of two (e.g.,

* 1, 2, 4, 8...).

* </p>

*

* @param vec

*

the vector

*/

public void forwardTrans(float[] vec) {

final int N = vec.length;

for (int n = N; n > 1; n = n >> 1) {

split(vec, n);

predict(vec, n, forward);

update(vec, n, forward);

}

} // forwardTrans

/**

* <p>

* Default two step Lifting Scheme inverse wavelet transform

* </p>

*

* <p>

* inverseTrans is passed the result of an ordered wavelet transform,

* consisting of an average and a set of wavelet coefficients. The inverse

* transform is calculated in-place and the result is returned in the

* argument array.

* </p>

*

* @param vec

*

the vector

*/

public void inverseTrans(float[] vec) {

final int N = vec.length;

for (int n = 2; n <= N; n = n << 1) {

update(vec, n, inverse);

predict(vec, n, inverse);

merge(vec, n);

}

} // inverseTrans

} // LiftingSchemeBaseWavelet