Symmetric Neighborhood Filter - Parallel Implementation

Most common enhancement filters will smooth the interior of regions at the cost of the edges, or find edges while introducing intrinsic error on previously homogeneous regions. However, the Symmetric Neighborhood Filter (SNF) is an edge-preserving smoothing filter, meaning that it performs well for both edge sharpening and region flattening. The SNF is a convergent filter which can be run for a predetermined number of iterations, or until a percentage of the image pixels are fixed in grey level. A variety of SNF operators have been studied, and we chose a single parameter version which has been shown to perform well. Previous parallel implementations of the SNF have been based around special purpose image processing platforms, including data parallel SIMD machines such as the TMC CM-2 and the MasPar MP-1 ([30]\ and [31]), video-rate VLSI implementations ([32]), pipelined computers ([19]), and systolic linear arrays such as the Warp ([2], [37], and [38]).

A useful data movement needed for this local SNF filter is the fetching of tile-based ghost cells ([15], [43]) which contain shadow copies of neighboring tiles' pixel borders. These ghost cells are used in the selection process when recalculating our tile's border. Suppose each tile of the image allocated to a processor is pixels. We have four ghost cell arrays, ghostN and ghostS which hold r pixels each, and ghostW and ghostE which hold q pixels each. In addition, four single pixel ghost cells for diagonal neighboring pixels are ghostNW, ghostNE, ghostSE, and ghostSW. An example of these ghost cells is pictured in Figure 3.

  
Figure 3: An example of Ghost Cells

The analysis for the prefetching of ghost cells is simple. We can divide the prefetching into eight separate data movements, one for each direction. Since each movement is a permutation, i.e. it has a unique source and destination, it can be routed with little or no contention. The prefetching of the north and south ghost cell arrays each take , the east and west ghost cell arrays each take , and the diagonal four ghost cells each take . Thus, the entire ghost cell prefetching takes

A second data movement needed for SNF is the reduction operation. Each processor i has a data value, , and we need the value of , where is any associative operator. Parallel computers can handle this efficiently [7], and SPLIT-C implements this as a primitive library function. A simple algorithm consists of p-1 rounds that can be pipelined [25]. Each processor initializes a local sum to . During round r, each processors then reads , for , and adds this value to the local sum. Since these rounds can be realized with p-1 pipelined prefetch read operations, the resulting complexity is

An SPMD algorithm for an iteration of SNF on Processor i:

For each iteration of the SNF operator on a p-processor machine, the theoretical analysis is as follows. The complexities for Step 1 and Step 4 are shown in (3) and (4), respectively. Steps 2 and 3 are completely local and take O. Thus, for , the SNF complexities are

Figure 10 in Appendix B shows the convergence of the SNF enhancement during the second phase of the smoothing filter. As can be seen, there is a fast convergence of the pixels asymptotically close to 100% fixed. Because fixed pixels are not recalculated, the time per iteration quickly ramps down from approximately 165 ms/iteration to 26 ms/iteration on a TM image.

The complexity of an iteration of the 1-Nearest Neighbor filter is simple, namely, a fetch of ghost cells and one pass through the image tile on each processor. The ghost cell analysis is given in (3), and the update of pixels takes O. Therefore, the 1-Nearest Neighbor \ algorithm has complexities