HaarWavelet.java (4254B)
1 package be.tarsos.dsp.wavelet.lift; 2 3 /** 4 * <p> 5 * HaarWavelet (flat LineWavelet) wavelet. 6 * </p> 7 * 8 * <p> 9 * As with all Lifting scheme wavelet transform functions, the first stage of a 10 * transform step is the split stage. The split step moves the even element to 11 * the first half of an N element region and the odd elements to the second half 12 * of the N element region. 13 * </p> 14 * 15 * <p> 16 * The Lifting Scheme version of the HaarWavelet transform uses a wavelet 17 * function (predict stage) that "predicts" that an odd element will have the 18 * same value as it preceeding even element. Stated another way, the odd element 19 * is "predicted" to be on a flat (zero slope LineWavelet) shared with the even 20 * point. The difference between this "prediction" and the actual odd value 21 * replaces the odd element. 22 * </p> 23 * 24 * <p> 25 * The wavelet scaling function (a.k.a. smoothing function) used in the update 26 * stage calculates the average between an even and an odd element. 27 * </p> 28 * 29 * <p> 30 * The merge stage at the end of the inverse transform interleaves odd and even 31 * elements from the two halves of the array (e.g., ordering them 32 * even<sub>0</sub>, odd<sub>0</sub>, even<sub>1</sub>, odd<sub>1</sub>, ...) 33 * </p> 34 * 35 * <h4> 36 * Copyright and Use</h4> 37 * 38 * <p> 39 * You may use this source code without limitation and without fee as long as 40 * you include: 41 * </p> 42 * <blockquote> This software was written and is copyrighted by Ian Kaplan, Bear 43 * Products International, www.bearcave.com, 2001. </blockquote> 44 * <p> 45 * This software is provided "as is", without any warrenty or claim as to its 46 * usefulness. Anyone who uses this source code uses it at their own risk. Nor 47 * is any support provided by Ian Kaplan and Bear Products International. 48 * <p> 49 * Please send any bug fixes or suggested source changes to: 50 * 51 * <pre> 52 * iank@bearcave.com 53 * </pre> 54 * 55 * @author Ian Kaplan 56 */ 57 public class HaarWavelet extends LiftingSchemeBaseWavelet { 58 59 /** 60 * HaarWavelet predict step 61 */ 62 protected void predict(float[] vec, int N, int direction) { 63 int half = N >> 1; 64 65 for (int i = 0; i < half; i++) { 66 float predictVal = vec[i]; 67 int j = i + half; 68 69 if (direction == forward) { 70 vec[j] = vec[j] - predictVal; 71 } else if (direction == inverse) { 72 vec[j] = vec[j] + predictVal; 73 } else { 74 System.out.println("HaarWavelet::predict: bad direction value"); 75 } 76 } 77 } 78 79 public void forwardTransOne(float[] vec) { 80 final int N = vec.length; 81 82 split(vec, N); 83 predict(vec, N, forward); 84 update(vec, N, forward); 85 86 } // forwardTrans 87 88 /** 89 * <p> 90 * Update step of the HaarWavelet wavelet transform. 91 * </p> 92 * <p> 93 * The wavelet transform calculates a set of detail or difference 94 * coefficients in the predict step. These are stored in the upper half of 95 * the array. The update step calculates an average from the even-odd 96 * element pairs. The averages will replace the even elements in the lower 97 * half of the array. 98 * </p> 99 * <p> 100 * The HaarWavelet wavelet calculation used in the Lifting Scheme is 101 * </p> 102 * 103 * <pre> 104 * d<sub>j+1, i</sub> = odd<sub>j+1, i</sub> = odd<sub>j, i</sub> - even<sub>j, i</sub> 105 * a<sub>j+1, i</sub> = even<sub>j, i</sub> = (even<sub>j, i</sub> + odd<sub>j, i</sub>)/2 106 * </pre> 107 * <p> 108 * Note that the Lifting Scheme uses an in-place algorithm. The odd elements 109 * have been replaced by the detail coefficients in the predict step. With a 110 * little algebra we can substitute the coefficient calculation into the 111 * average calculation, which gives us 112 * </p> 113 * 114 * <pre> 115 * a<sub>j+1, i</sub> = even<sub>j, i</sub> = even<sub>j, i</sub> + (odd<sub>j, i</sub>/2) 116 * </pre> 117 */ 118 protected void update(float[] vec, int N, int direction) { 119 int half = N >> 1; 120 121 for (int i = 0; i < half; i++) { 122 int j = i + half; 123 float updateVal = vec[j] / 2.0f; 124 125 if (direction == forward) { 126 vec[i] = vec[i] + updateVal; 127 } else if (direction == inverse) { 128 vec[i] = vec[i] - updateVal; 129 } else { 130 System.out.println("update: bad direction value"); 131 } 132 } 133 } 134 135 } // HaarWavelet