并联中值滤波器 [英] Parallel Median Filter
问题描述
因此，我一直在研究中值滤波器*(由于正在学习如何并行编码，因此比较了并行与并行)，但是对于较大的输入(大约100k，并行版本可以无限期地运行；对于更少的输入，它可以很好地运行) ).
So I've been working on a median filter* (comparing sequential to parallel, since I'm learning how to code concurrently), but the parallel version runs indefinitely for a large input (about 100k; it runs fine for less).
从本质上讲，代码将接收文件，在给定窗口大小的情况下对其进行过滤，然后将其写入新文件.并行编程的新手，所以在这里可能出现问题时我迷失了.
In essence, the code takes in a file, filters it given a certain window size, then writes it to a new file. New to parallel programming, so I'm kind of lost when it comes to what might be wrong here.
//import everything
public class SecondMedianFilter extends RecursiveAction {
float[] numbers;
static int filter;
int window;
int length;
int lo;
int hi;
static final int SEQUENTIAL_CUTOFF = 500;
float[] outArray;
public SecondMedianFilter(float[] numbers, int filter, int lo, int hi) {
this.numbers = numbers;
this.filter = filter;
this.lo = lo;
this.hi = hi;
length = numbers.length;
window = (filter - 1) / 2;
}
public float[] getRes() {
return result;
}
protected void compute() {
result = new float[length];
if ((hi - lo) < SEQUENTIAL_CUTOFF) {
for (int a = lo; a < hi; a++) {
for (int i = 0; i < length; i++) {
if (i < window || i >= length - window) {
result[i] = numbers[i];
} else {
float[] subArray = Arrays.copyOfRange(numbers, i - window, i + window + 1);
Arrays.sort(subArray);
float median = subArray[(subArray.length / 2)];
result[i] = median;
}
}
}
} else {
SecondMedianFilter left = new SecondMedianFilter(filtered, filter, lo, (hi + lo) / 2);
SecondMedianFilter right = new SecondMedianFilter(filtered, filter, (hi + lo) / 2, hi);
left.fork();
right.compute();
left.join();
}
}
public static void main(String[] args) {
//reads in a file, processes each line into an array of floats that
// I call inArray, which gets filtered into outIntArray
float[] outIntArray = new float[inArray.length];
if (window < 3 || window > 21 || window % 2 == 0) {
System.out.println("Window size error.");
} else {
SecondMedianFilter smf = new SecondMedianFilter(inArray, window, 0, inArray.length);
smf.compute();
outIntArray = smf.getRes();
// loops through outIntArray and writes to file.
}//end main
}
}
按顺序执行似乎很有效(在一秒钟之内可以处理大约1 000 000个元素)，但是我的并发版本只需要4个就可以处理10 000个元素.就像我说的那样，并行编程是全新的，所以我很迷茫.有没有一种方法可以并行执行我所缺少的中值滤波器?
Doing it sequentially appears to work (under a second for about 1 000 000 elements), and yet my concurrent version takes almost 4 just to do 10 000 elements. As I said, brand new to parallel programming, so I'm quite lost. Is there an approach to doing a median filter in parallel that I'm missing?
(*中值过滤器=选取数组的某个窗口，对它们进行排序，然后将该索引处的原始元素替换为排序后的子数组的中值；例如:2、80、6、3、1的结果为2，6，6，3，1.)
(* Median filter = take a certain window of the array, sort them and replace the original element at that index with the median of the sorted sub-array; for example: 2, 80, 6, 3, 1 results in 2, 6, 6, 3, 1.)
*例如:
Taking in this file:
5.0
13.2
-2.6
22.3
12.4
-0.21
23.1
-0.2454
它将读入数组[5.0，13.2，-2.6，22.3，12.4，-0.21，23.1，-0.2454] 窗口大小为3.为了适用于过滤，一个元素必须在它之前有n个元素，在它之后有n个元素，其中n =(window-1)/2;因此，在window = 3的情况下，元素的任一侧都必须具有1个元素.如果不满足该条件，则该元素保持原样.
It'll read that into an array [5.0, 13.2, -2.6, 22.3, 12.4, -0.21, 23.1, -0.2454] With a window size of, say, 3. In order to be applicable for filtering, an element must have n elements before it and n elements after it, where n = (window - 1)/2; hence, an element, in the case of window = 3, must have 1 element on either side of it. If it doesn't satisfy that condition, that element is taken as-is.
因此5.0将会保留，因为它之前没有任何元素.但是13.2满足条件-因此，采用了一个子数组[5.0，13.2，-2.6].然后对该数组排序(使用.sort():[-2.6，5.0，13.2])，然后取中位数为5.0.随后在最终数组中将13.2替换为5.0，现在看起来像[5.0，5.0，...].
So 5.0 will remain, given that it doesn't have an element before it. But 13.2 satisfies the condition - hence, a sub-array is taken [5.0, 13.2, -2.6]. This array is then sorted (using .sort(): [-2.6, 5.0, 13.2]), then the median is taken to be 5.0. 13.2 is subsequently replaced with 5.0 in the final array, which now looks like [5.0, 5.0,...].
接下来，它前进到-2.6-它在元素之前和之后都有一个元素，因此对子数组[-2.6，22.3，12.4]进行了排序，并将中值12.4添加到了最终数组中: [5.0，5.0，12.4，...].重复此过程，直到访问了原始数组中的所有元素.然后将最终数组写入文件，但这并不是特别相关(除非可以通过某种方式并行完成-我对此表示怀疑，但正如我所说:在此处完成noob).
Next it moves on to -2.6 - it has an element before and one after, so the sub-array [-2.6, 22.3, 12.4] is taken, sorted, and the median of 12.4 is added to the final array: [5.0, 5.0, 12.4,...]. It repeats this process until all elements in the original array have been visited. It then writes the final array to a file, but this isn't particularly relevant (unless this can be done in parallel somehow - which I doubt, but as I said: complete noob here).
推荐答案
您正在处理的是完全可并行化的.确实，您可以为元素的每个子集计算中值过滤器(因为您不必在计算中更改原始数组的内容).因此，是的，您可以并行进行.
You're processing is totally parallizable. Indeed you can compute the median filter for every single subset of elements (because you don't change the content of the original array in your calculations). So, yes, you can do it in parallel.
这样说，即使我不知道 RecursiveAction 的所有细节，我也会说您错过了整个 threads 部分.我检查了一下，任何递归操作都应由 ForkJoinPool 类调用.然后，该线程处理线程并派生/加入它们.
Said this, even if I don't know all the details of the RecursiveAction, I would say that you miss the whole threads part. I've checked a bit and any recursive action should be invoked by an ForkJoinPool class. This one then handles the threads and fork/join them.
此外，要左右拆分操作(使用两个不同的调用)，则需要稍后分别叉和加入.
Furthmore, splitting the operations on right and left (with two different calls) requires that you fork and join both them later.
我希望这样的东西可以正常工作:
I expect something like this to have a working configuration:
public class SecondMedianFilter extends RecursiveAction {
...
protected void compute() {
result = new float[length];
if ((hi - lo) < SEQUENTIAL_CUTOFF) {
for (int a = lo; a < hi; a++) {
for (int i = 0; i < length; i++) {
if (i < window || i >= length - window) {
result[i] = numbers[i];
} else {
float[] subArray = Arrays.copyOfRange(numbers, i - window, i + window + 1);
Arrays.sort(subArray);
float median = subArray[(subArray.length / 2)];
result[i] = median;
}
}
}
} else {
SecondMedianFilter left = new SecondMedianFilter(filtered, filter, lo, (hi + lo) / 2);
SecondMedianFilter right = new SecondMedianFilter(filtered, filter, (hi + lo) / 2, hi);
left.fork();
//CODE CHANGES FROM HERE
right.fork();
//right.compute(); <- IS IMPLICIT IN THE FORK
left.join();
right.join();
//TO HERE
}
}
public static void main(String[] args) {
//reads in a file, processes each line into an array of floats that
// I call inArray, which gets filtered into outIntArray
float[] outIntArray = new float[inArray.length];
if (window < 3 || window > 21 || window % 2 == 0) {
System.out.println("Window size error.");
} else {
// CODE CHANGES FROM HERE
ForkJoinPool pool = new ForkJoinPool(); // WHO HANDLES THE THREADS
SecondMedianFilter smf = new SecondMedianFilter(inArray, window, 0, inArray.length);
//smf.compute(); <- DUTY OF THREAD POOL
pool.invoke(smf); // START OF PROCESSING
outIntArray = smf.getRes();
// loops through outIntArray and writes to file.
}//end main
}
}
我将为您提供两个链接，它们将详细解释整个过程的工作方式(其中一个显示了并行方法和顺序方法).
I'll provide you two links, they'll explain enough in detail how the whole process works (where one shows both the parallel and sequential approachs).
http://www.concretepage.com/java /jdk7/example-of-recursiveaction-in-java
http://www.logicbig. com/how-to/java/fork-and-join-recursive-action/
编辑 我还没有检查算法的工作原理(我希望它将数组分成两个整数，直到遇到绑定情况时)，所以我只是根据您编写的内容添加了几段代码.
EDIT I've not checked how you're algorithm works (I expect that it splits the array in two up to when it comes to to a bound case), so I've just added pieces of code according to what you've written.
这篇关于并联中值滤波器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
