b4d104db23
* Added algorithm for color contrast ratio.
* Added comment and example usage in main.
* Fixed calling method in main without creating object.
* Formatted with Google Java Formatter
* Add imports for ColorContrastRatio.java
* updating DIRECTORY.md
* Updated to follow repo conventions. Undid formatting of documents.
* Follow repository conventions.
* Formatted with Google Java Formatter
* Added test method with assetions.
* Formatted with Google Java Formatter
* Update Misc/ColorContrastRatio.java
Co-authored-by: Ayaan Khan <ayaankhan98@gmail.com>
* updating DIRECTORY.md
* Correct javadocs and parameter names.
* Formatted with Google Java Formatter
Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com>
Co-authored-by: Ayaan Khan <ayaankhan98@gmail.com>
61 lines
2.2 KiB
Java
61 lines
2.2 KiB
Java
package com.maths;
|
|
|
|
import java.util.ArrayList;
|
|
|
|
/**
|
|
* Class for linear convolution of two discrete signals using the convolution theorem.
|
|
*
|
|
* @author Ioannis Karavitsis
|
|
* @version 1.0
|
|
*/
|
|
public class ConvolutionFFT {
|
|
/**
|
|
* This method pads the signal with zeros until it reaches the new size.
|
|
*
|
|
* @param x The signal to be padded.
|
|
* @param newSize The new size of the signal.
|
|
*/
|
|
private static void padding(ArrayList<FFT.Complex> x, int newSize) {
|
|
if (x.size() < newSize) {
|
|
int diff = newSize - x.size();
|
|
for (int i = 0; i < diff; i++) x.add(new FFT.Complex());
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Discrete linear convolution function. It uses the convolution theorem for discrete signals
|
|
* convolved: = IDFT(DFT(a)*DFT(b)). This is true for circular convolution. In order to get the
|
|
* linear convolution of the two signals we first pad the two signals to have the same size equal
|
|
* to the convolved signal (a.size() + b.size() - 1). Then we use the FFT algorithm for faster
|
|
* calculations of the two DFTs and the final IDFT.
|
|
*
|
|
* <p>More info: https://en.wikipedia.org/wiki/Convolution_theorem
|
|
* https://ccrma.stanford.edu/~jos/ReviewFourier/FFT_Convolution.html
|
|
*
|
|
* @param a The first signal.
|
|
* @param b The other signal.
|
|
* @return The convolved signal.
|
|
*/
|
|
public static ArrayList<FFT.Complex> convolutionFFT(
|
|
ArrayList<FFT.Complex> a, ArrayList<FFT.Complex> b) {
|
|
int convolvedSize = a.size() + b.size() - 1; // The size of the convolved signal
|
|
padding(a, convolvedSize); // Zero padding both signals
|
|
padding(b, convolvedSize);
|
|
|
|
/* Find the FFTs of both signals (Note that the size of the FFTs will be bigger than the convolvedSize because of the extra zero padding in FFT algorithm) */
|
|
FFT.fft(a, false);
|
|
FFT.fft(b, false);
|
|
ArrayList<FFT.Complex> convolved = new ArrayList<>();
|
|
|
|
for (int i = 0; i < a.size(); i++) convolved.add(a.get(i).multiply(b.get(i))); // FFT(a)*FFT(b)
|
|
|
|
FFT.fft(convolved, true); // IFFT
|
|
convolved
|
|
.subList(convolvedSize, convolved.size())
|
|
.clear(); // Remove the remaining zeros after the convolvedSize. These extra zeros came from
|
|
// paddingPowerOfTwo() method inside the fft() method.
|
|
|
|
return convolved;
|
|
}
|
|
}
|