So I've been confronted with a rather simple problem in the Java chat on Stack Overflow. It's about doing a median filter with a sliding reference window.
For the purpose of the task we can assume the window used for filtering is always an odd integer between 3 and 21. The sliding window does not wrap around the array borders and accordingly array elements that cannot be processed with a full window are simply copied over to the target array.
For an array
$$[N_0, N_1, N_2, N_3, \dots, N_{n-1}]$$
the window moves over the whole array once and writes the result of the median calculation to the current index of a result array.
Small reminder: The median of a Set is calculated by ordering the set and choosing the middle element. For sets with an even number of elements, the median is the arithmetic mean of the two middle elements.
$$ [1, 5, 2, 7, 3] \mapsto [1, 2, 3, 5, 7] \mapsto 3$$ $$[1, 9, 7, 2, 7, 4] \mapsto [1, 2, 4, 7, 7, 9] \mapsto \frac{4+7}{2} = 5.5$$
To make this a little clearer, here's how it works for a sample array with a window size of 3. In the beginning, the target array contains no elements. Since we cannot run a median filtering in places where the window doesn't fit we copy over the outermost \$\frac{w - 1}{2}\$ elements. For window size 3 that's 1 element.
$$A_{source} = [1, 5, 2, 7, 6, 3] $$ $$ A_{target} = [1, 0, 0, 0, 0, 3]$$
Now we can run the first median filter. Placing the window at the first position possible, we can examine the indices 0, 1 and 2. These elements are responsible for the target value at index 1.
$$A_{window} = [1, 5, 2] \mapsto A_{sorted} = [1, 2, 5]$$
accordingly the median value for index 1 is \$2\$. writing that result to \$A_{target}\$ gets us:
$$A_{target} = [1, 2, 0, 0, 0, 3]$$
Now the reference window moves by one index. We examine indices 1, 2 and 3:
$$A_{window} = [5, 2, 7] \mapsto A_{sorted} = [2, 5, 7]$$
Take result 5, write it into the target array, rinse and repeat unti we finally arrive at the median-filtered array:
$$A_{result} = [1, 2, 5, 6, 6, 3] $$
The following code is a generic approach at providing code that can be trivially multithreaded to run these calculations on a Comparable[]
import java.util.Arrays;
import java.util.concurrent.CountDownLatch;
public class MedianFilter {
private final CountDownLatch completionLatch = new CountDownLatch(1);
private final Comparable[] sourceArray;
private final Comparable[] targetArray;
private final int slidingWindowSize;
public MedianFilter(final Comparable[] data, final int windowSize) {
// we can assume that windowSize is an odd integer (3, 21)
assert (windowSize % 2 == 1);
if (windowSize > data.length) {
throw new IllegalArgumentException(
"sliding window size cannot exceed array length");
}
sourceArray = data;
targetArray = new Comparable[data.length];
slidingWindowSize = windowSize;
}
public Comparable[] getResults() {
// check that we really completed :)
try {
completionLatch.await();
} catch (InterruptedException e) {
// interruption while waiting, should never happen here, so we
// ignore that
}
return targetArray;
}
public void doFilter() {
final int shoulderSize = (slidingWindowSize - 1) / 2;
final int startIndex = shoulderSize;
final int endIndex = sourceArray.length - shoulderSize;
// copy over shoulders
System.arraycopy(sourceArray, 0, targetArray, 0, shoulderSize);
System.arraycopy(sourceArray, endIndex, targetArray, endIndex,
shoulderSize);
for (int index = startIndex; index < endIndex; index++) {
runMedian(index, shoulderSize);
}
completionLatch.countDown();
}
private void runMedian(final int index, final int shoulderSize) {
Comparable[] window = new Comparable[slidingWindowSize];
System.arraycopy(sourceArray, index - shoulderSize, window, 0,
slidingWindowSize);
Arrays.sort(window, null); // use natural ordering of Comparable
targetArray[index] = window[shoulderSize];
}
}
As mentioned this is intended to be trivially multithreadable. Current usage contex (e.g. with Integers) can be found in this gist.
The code is working as intended and producing correct results for manual Tests.
I am looking for feedback on the clarity of approach, variable names and general feedback.