Median 필터는 임계치 분할, 스택킹 특성, 그리고 선형 분리성에 기반하여 이진 영역에서 구현이 가능하다. 본 논문에서는 VLSI 구현에 적합한 변형 가능한 메쉬(RMESH) 구조에서 median 필터링을 위한 1차원 및 2차운 병렬 알고리즘의 성능을 평가한다. 실제로 M 레벨의 1차원 시그널 길이가 N이고 윈도우 폭이 W일 때, 메쉬 구조에서는 $O(Mw^2)$의 시간 복잡도를 갖는 반면 RMESH 구조에서의 알고리즘은 O(Mw) 시간 복잡도를 갖는다. 또한 M 레벨의 2차원 영상의 크기가 $N{ imes}N$이고 원도우 크기가 $w{ imes}w$라고 가정하면, 본 논문에서 제안한 $N{ imes}N$ RMESH 상에서 median 필터링 알고리즘은 $N{ imes}N$ 메쉬의 $O(Mw^2)$ 시간 보다 더욱 향상된 O(Mw) 시간에 계산되어진다.
Median filter can be implemented in the binary domain based on threshold decomposition, stacking property, and linear separability. In this paper, we develop one-dimensional and two-dimensional parallel algorithms for the median filter on a reconfigurable mesh with buses(RMESH) which is suitable for VLSI implementation. And we evaluate their performance by comparing the time complexities of RMESH algorithms with those of algorithms on mesh-connected computer. When the length of M-valued 1-D signal is N and w is the window width, the RMESH algorithm is done in O(Mw) time and mesh algorithm is done in $O(Mw^2)$ time. Beside, when the size of M-valued 2-D image is $N{ imes}N$ and the window size is $w{ imes}w$, our algorithm on $N{ imes}N$ RMESH can be computed in O(Mw) time which is a significant improvement over the $O(Mw^2)$ complexity on $N{ imes}N$ mesh.
