AfastmedianfilterusingAltiVec资源-CSDN文库

5星 · 超过95%的资源需积分: 10 177 浏览量 2012-08-12 21:08:27 上传评论收藏 223KB PDF 举报

### 快速中值滤波器使用AltiVec技术 #### 概述本文介绍了一种基于Motorola AltiVec架构设计与实现的快速中值滤波器算法。该算法利用16路单指令多数据（SIMD）并行处理能力来对图形图像进行高效的滤波操作。对于3×3的窗口，滤波速率可达到每像素1.15个周期；对于5×5的窗口，则为每像素6.6个周期。这一快速滤波算法的关键在于采用了新颖的排序网络来处理N×N矩阵中的元素，并且通过有效地利用排序结果以及现代CPU架构提供的并行性来提高性能。 #### 技术背景二维图形图像是由像素组成的矩形区域，每个像素具有离散的数值。中值滤波器计算图像中每个像素的输出值为其邻域内的像素值中位数。例如，一个3×3窗口中心的像素，其输出值将取自该窗口内9个像素的中位数。这种非线性滤波方法能有效去除图像中的随机噪声，同时避免了线性低通滤波器常见的模糊效应，因此被广泛应用于图像处理软件中。然而，对于包含大量像素的图像来说，中值滤波是一项非常耗费CPU资源的任务，因此提高执行效率成为迫切需求。 #### 核心技术点解析 **排序网络** 为了找到N×N矩阵中的中位数，本文提出了一种新的排序网络，该网络通过对矩阵中的所有列、行以及对角线进行排序来实现对整个矩阵的排序。这种方法相比于传统的排序算法，在处理大量数据时更加高效。具体来说，对于N×N矩阵，通过先对每一列进行排序，再对每一行进行排序，最后对两条主要对角线进行排序，可以得到完全有序的矩阵，从而方便地找到中位数。 **比较操作优化** 中值滤波算法中最耗时的操作是像素值之间的比较。为了减少比较操作的时间，本文提出了三种优化方法： 1. **减少比较次数**：通过对原始数据进行预处理或采用更高效的排序算法，可以减少需要进行的比较次数。 2. **比较结果复用**：在处理相邻或重叠的窗口时，可以利用上一个窗口比较的结果来加速当前窗口的处理速度。例如，在3×3到5×5窗口的转换过程中，可以复用部分已有的排序结果。 3. **利用SIMD并行性**：AltiVec架构支持16路SIMD并行处理，这意味着可以在单个指令周期内对多个像素值进行比较。充分利用这一特性能够显著提高处理速度。 #### 测试方案为了验证提出的排序网络的有效性，本文还设计了一套测试方案。这套方案包括了一系列测试用例，用以确保排序网络能够在各种情况下正确工作。通过这种方式，不仅验证了算法的正确性，也为实际应用提供了可靠的基础。 #### 结论本研究提出的基于AltiVec架构的快速中值滤波器算法，通过优化比较操作、复用排序结果以及利用SIMD并行性，实现了高效的图像滤波处理。该算法特别适用于需要实时处理大量图像数据的应用场景，如视频监控、图像识别等。此外，通过引入创新的排序网络和有效的测试方法，进一步提高了算法的实用性和可靠性。

资源详情

资源评论

资源推荐

A Fast Median Filter using AltiVec

Priyadarshan Kolte Roger Smith Wen Su

Motorola, Inc., Austin, Texas

pkolte,rogers,wens@ncct.sps.mot.com

Abstract

This paper describes the design and implementation of

a median lter for graphics images on the Motorola

AltiVec architecture. The lter utilizes 16-way SIMD

parallelism to lter images at rates of 1.15 cycles/pixel

for



squares and 6.6 cycles/pixel for



squares.

The median lter is based on a new sorting network

which sorts

numbers (arrangedinan



square)

by sorting al l columns, rows, and diagonal lines in the

square. This paper also describes a scheme for eÆcient

testing of the sorting network.

1. Intro duction

Two dimensional graphics images are rectangles of pix-

els, where each pixel has a discrete value. A

median

lter

computes the output value of each pixel in an im-

age as the median value of pixels in a small neighbor-

hoo d such as the 9 pixels in the 3



3 square centered

around the pixel [8]. This type of non-linear ltering is

eective in removing random noise from images with-

out causing the blurring that is typical of linear low{

pass lters, and it is oered by popular image pro cess-

ing programs. However, median ltering for images

containing many pixels is a CPU intensive task, and

there is a need to improve execution time.

A dominant factor in the execution time of the lter

is p erforming compares of pixel values to nd the me-

dian value. There are three ways of improving the time

required by these compare operations. The rst is to

reduce the number of compares needed. The second is

to reuse the results of compares p erformed within one

square for nding the medians of adjacentoverlapping

squares. The third way is to use the parallelism of-

fered by mo dern CPU architectures to compare multi-

ple pixel values simultaneously. Wehave developed a

median lter which uses all three ways to improve the

execution time.

Our implementation of the median lter targets the

Motorola AltiVec architecture [1, 4]. This architecture

extends the PowerPC architecture with vector instruc-

tions that can process 16 8-bit data values simultane-

ously. We have measured image pro cessing rates of

1.15 cycles/pixel for 3



3 squares and 6.6 cycles/pixel

for 5



5 squares using our median lter implemen-

tation. A comparable implementation of the median

nding algorithm byPaeth [8] would require at least

2 cycles/pixel for 3



3 squares and 10.9 cycles/pixel

for 5



5 squares. Thus, our implementation improves

processing rates by at least 65% over prior work.

Our median lter is based on a new sorting network

for numbers arranged in squares. This sorting network

for squares operates by successively sorting columns,

rows, and diagonal line segments of varying slop es.

Section 2 describes the scalar median algorithm and

sorting network. Section 3 describ es our technique for

testing the correctness of the median algorithm and

sorting network. Section 4 provides the details of the

AltiVec implementation and explains how we paral-

lelized the scalar median algorithm. Section 5 presents

related work and Section 6 concludes.

2. Scalar median algorithm

We rst discuss a scalar algorithm for nding the me-

dian of a 3



3 square and then generalize the median

algorithm for an



square, where

is o dd. We

also describe sorting networks for completely sorting



square, rst for the case where

is odd,

and then for the case where

is even.

2.1. Background on sorting networks

compare-swap

of two elements

(a,b)

compares

and exchanges

and

so that we have

a <= b

af-

ter the op eration. A

sorting network

is a sequence

compare-swap

operations that depends only on the

numb er of elements to b e sorted, not on the values of

the elements [5]. Bubblesort is an example of a sorting

network whereas quicksort is not a sorting network.

Although a sorting network for a xed numb er of el-

ements usually requires a greater numb er of compare

operations than a sorting method such as quicksort,

the advantage of the sorting network is that the se-

quence of comparisons is xed, so that the compare

operations to b e p erformed so not dep end on the out-

come of previously p erformed compare operations [6].

This absence of control{dependences in the sorting

network makes it well suited to utilizing the data{

parallelism oered by Single Instruction Multiple Data

(SIMD) pro cessors, since multiple indep endent arrays

can b e sorted in parallel using a xed sequence of data{

parallel

compare-swap

operations.

Example sorting network.

The following gure

shows an example of a sorting network for 3 elements

(in0, in1, in2)

such that the output

(out0, out1,

out2)

is in non-decreasing order. The boxes imple-

ment

compare-swap

operations such that the lesser in-

put value app ears on the upper output and the greater

input value app ears on the lower output. For example,

box

implements

compare-swap(in0,in1)

so that

tmin = min(in0,in1)

and

tmax = max(in0,in1)

- -- -

out0

out1

out2in2

in1

in0

tmin

tmax tmed

Notation.

We shall use the term

extremum

to mean

min

or a

max

operation so that we can say that com-

pletely sorting 3 elements requires 6 extrema.

Best sorting networks.

The table b elow (derived

from the table on page 227 of Knuth's b ook [5]) shows

values of

(

), where

(

) represents the number

of extrema required by the best sorting networks (i.e.,

those which require the least number of extrema for

sorting

elements). We use these best sorting net-

works as sub components of our sorting networks.

= 1 2 3 4 5 6 7 8

(

)= 0 2 6 10 18 24 32 38

= 9 10 11 12 13 14 15 16

(

)= 50 58 70 78 92 102 112 120

Dead co de elimination.

In the sorting network for

3 elements shown ab ove, if we need just the median of

3 elements, we omit the 2 extremum instructions for

the non-median elements (

out0

and

out2

), and the

numb er of extrema needed reduces from 6 to 4.

This optimization of omitting extremum instruc-

tions for results that are not needed is similar to the

\dead code elimination" transformation p erformed by

optimizing compilers. We use it to reduce the num-

ber of extrema in cases where a complete sort of all

elements is not needed and a partial sort is suÆcient.

2.2.



median algorithm

Algorithm

median

shown below nds the median of

the 9 values in array

[3][3] by rst sorting each 3

element column, then nding the maximum element

of the rst row, the median of the second row, and

the minimum of the third row, and nally nding the

median of the three intermediate results.

Algorithm: median_3

Input: A is an unsorted 3x3 array

Output: median of the 9 values

for c = 0 to 2

sort column c so that A[r-1,c] <= A[r,c]

let max0 = max (A[0,0], A[0,1], A[0,2])

let med1 = med (A[1,0], A[1,1], A[1,2])

let min2 = min (A[2,0], A[2,1], A[2,2])

let med3 = med (max0, med1, min2)

The following gure shows an example to illustrate the

operation of the

median

algorithm.

9 7

523

8 7



7

cols

sort

med3 = 5

min2 = 7

max0 = 5

med1 = 4

Using a sorting network to sort 3 columns of array

requires 3



6 = 18 extremum operations, comput-

ing

max0

requires 2 extrema,

med1

requires 4 extrema,

min2

requires 2 extrema, and

med3

requires 4 extrema.

Thus,

median

requires a total of 30 extrema.

2.3.



median algorithm (odd N)

We generalize

median 3

to work for all odd values of

as shown b elow in algorithm

median odd N

Algorithm: median_odd_N

Input: A is an unsorted NxN array

Output: median of the NxN values

let M = (N-1)/2

/* Sort columns. */

for c = 0 to N-1

sort column c so that A[r-1,c] <= A[r,c]

/* Partially sort rows. */

for r = 0 to N-1

sort row r so that A[r,c-1] <= A[r,c]

for k = 1 to M

/* Partially sort diagonals of slope k */

for s = k*(M+1) to k*(M-1)+(N-1)

sort line (k*r + c = s) so that

A[r-1, s-k*(r-1)] <= A[r, s-k*r]

let median = A[M,M]

剩余7页未读，继续阅读

xiaoyin9395

2013-12-05

很有用的文章。很有针对性。谢谢了。

评论收藏

内容反馈

chenmoumou

粉丝: 9
资源: 13

A fast median filter using AltiVec

评论3

最新资源

A fast median filter using AltiVec

评论3

分治算法思想解决median问题

A_fast_approximation_of_the_bilateral_filter_using_a_signal_processing_approach

Fast Median Filter-开源

Fast Multi-exposure Image Fusion with Median Filter and Recursive Filter

a new directional weighted median filter

directional weighted median filter(DWMF)图像的方向加权中值滤波图像去噪matlab仿真

median-filter.rar_filter lena_lena_noisy median filter

Median-filtering.rar_median filter

MedianFilter.rar_ARP filter sourse_median filter matlab_pressb6r

论文研究-A Robust Median Filtering Detector Based On Filter Residual.pdf

Median filter

GUI.rar_GUI MSE_mean_mean filter_median filter

Adaptive-Median-Filter-master.zip

DBUTM-trimmed-median-filter.rar_filter_median

median_pgm.rar_.pgm_C++ PGM_median filter_pgm_purpose

median filter.rar_Salt Pepper noise_image processing_low_pass_fi

tuxiangchuli.rar_median filter_图像分割java_图形 分割

中值滤波median_filter

median filter.rar

Ani.pdf.zip_PSNR_de-noising_ief_impulse noise_median filter

xilinx中值滤波程序vhdl源码 median filter

median_filter_中值滤波_

residual demosaicking with efficient median filter

median_filter.zip_NOISE

medfilt3.rar_2D滤波_3d median filter _medfilt_中值滤波_滤波 二维

raly.rar_NOISE_geometric median_max min filter_max-median_trimme

median_filter_test

center_weighted_median_filter.rar_Center_difference image _matla

最新资源

tuxiangchuli.rar_median filter_图像分割java_图形分割

medfilt3.rar_2D滤波_3d median filter _medfilt_中值滤波_滤波二维