HaarWaveletTransform.java (3674B)
1 /* 2 * _______ _____ _____ _____ 3 * |__ __| | __ \ / ____| __ \ 4 * | | __ _ _ __ ___ ___ ___| | | | (___ | |__) | 5 * | |/ _` | '__/ __|/ _ \/ __| | | |\___ \| ___/ 6 * | | (_| | | \__ \ (_) \__ \ |__| |____) | | 7 * |_|\__,_|_| |___/\___/|___/_____/|_____/|_| 8 * 9 * ------------------------------------------------------------- 10 * 11 * TarsosDSP is developed by Joren Six at IPEM, University Ghent 12 * 13 * ------------------------------------------------------------- 14 * 15 * Info: http://0110.be/tag/TarsosDSP 16 * Github: https://github.com/JorenSix/TarsosDSP 17 * Releases: http://0110.be/releases/TarsosDSP/ 18 * 19 * TarsosDSP includes modified source code by various authors, 20 * for credits and info, see README. 21 * 22 */ 23 24 package be.tarsos.dsp.wavelet; 25 26 public class HaarWaveletTransform { 27 28 private final boolean preserveEnergy; 29 private final float sqrtTwo = (float) Math.sqrt(2.0); 30 31 public HaarWaveletTransform(boolean preserveEnergy){ 32 this.preserveEnergy = preserveEnergy; 33 } 34 35 public HaarWaveletTransform(){ 36 this(false); 37 } 38 39 /** 40 * Does an in-place HaarWavelet wavelet transform. The 41 * length of data needs to be a power of two. 42 * It is based on the algorithm found in "Wavelets Made Easy" by Yves Nivergelt, page 24. 43 * @param s The data to transform. 44 */ 45 public void transform(float[] s){ 46 int m = s.length; 47 assert isPowerOfTwo(m); 48 int n = log2(m); 49 int j = 2; 50 int i = 1; 51 for(int l = 0 ; l < n ; l++ ){ 52 m = m/2; 53 for(int k=0; k < m;k++){ 54 float a = (s[j*k]+s[j*k + i])/2.0f; 55 float c = (s[j*k]-s[j*k + i])/2.0f; 56 if(preserveEnergy){ 57 a = a/sqrtTwo; 58 c = c/sqrtTwo; 59 } 60 s[j*k] = a; 61 s[j*k+i] = c; 62 } 63 i = j; 64 j = j * 2; 65 } 66 } 67 68 /** 69 * Does an in-place inverse HaarWavelet Wavelet Transform. The data needs to be a power of two. 70 * It is based on the algorithm found in "Wavelets Made Easy" by Yves Nivergelt, page 29. 71 * @param data The data to transform. 72 */ 73 public void inverseTransform(float[] data){ 74 int m = data.length; 75 assert isPowerOfTwo(m); 76 int n = log2(m); 77 int i = pow2(n-1); 78 int j = 2 * i; 79 m = 1; 80 for(int l = n ; l >= 1; l--){ 81 for(int k = 0; k < m ; k++){ 82 float a = data[j*k]+data[j*k+i]; 83 float a1 = data[j*k]-data[j*k+i]; 84 if(preserveEnergy){ 85 a = a*sqrtTwo; 86 a1 = a1*sqrtTwo; 87 } 88 data[j*k] = a; 89 data[j*k+i] = a1; 90 } 91 j = i; 92 i = i /2; 93 m = 2*m; 94 } 95 } 96 97 98 99 /** 100 * Checks if the number is a power of two. For performance it uses bit shift 101 * operators. e.g. 4 in binary format is 102 * "0000 0000 0000 0000 0000 0000 0000 0100"; and -4 is 103 * "1111 1111 1111 1111 1111 1111 1111 1100"; and 4&-4 will be 104 * "0000 0000 0000 0000 0000 0000 0000 0100"; 105 * 106 * @param number 107 * The number to check. 108 * @return True if the number is a power of two, false otherwise. 109 */ 110 public static boolean isPowerOfTwo(int number) { 111 if (number <= 0) { 112 throw new IllegalArgumentException("number: " + number); 113 } 114 if ((number & -number) == number) { 115 return true; 116 } 117 return false; 118 } 119 120 /** 121 * A quick and simple way to calculate log2 of integers. 122 * 123 * @param bits 124 * the integer 125 * @return log2(bits) 126 */ 127 public static int log2(int bits) { 128 if (bits == 0) { 129 return 0; 130 } 131 return 31 - Integer.numberOfLeadingZeros(bits); 132 } 133 134 /** 135 * A quick way to calculate the power of two (2^power), by using bit shifts. 136 * @param power The power. 137 * @return 2^power 138 */ 139 public static int pow2(int power) { 140 return 1<<power; 141 } 142 143 }