8 December 2017 in IEEE Transactions on Image Processing
Median filtering is a smoothing technique for noise removal in images. While there are various implementations of median filtering for a single-core CPU, there are few implementations for accelerators and multi-core systems. Many parallel implementations of median filtering use a sorting algorithm for rearranging the values within a filtering window and taking the median of the sorted value. While using sorting algorithms allows for simple parallel implementations, the cost of the sorting becomes prohibitive as the filtering windows grows. This makes such algorithms, sequential and parallel alike, inefficient. In this work we introduce the first software parallel median filtering that is non-sorting based. The new algorithm uses efficient histogram based operations. These reduce the computational requirements of the new algorithm while also accessing the image fewer times. We show an implementation of our algorithm for both the CPU and NVIDIA’s CUDA supported GPU. The new algorithm is compared with several other leading CPU and GPU implementations. The CPU implementation has near perfect linear scaling with a 3.7X speedup on a quad-core system. Our GPU implementation is several orders of magnitude faster than the other GPU implementations for mid-size median filters. For small kernels, 3 × 3 and 5 × 5, comparison based approaches are preferable as fewer operations are required. Lastly, the new algorithm is open-source and can be found in the OpenCV library.
7 July 2022 in ACM Journal of Experimental Algorithmics
Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this article, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. Previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings; however, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between \( 1.5\times \) and \( 3.5\times \) , depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10,000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of edges in fractions of seconds.