GPU-Efficient Recursive Filtering and Summed-Area Tables

晃晃

GPU-Efficient Recursive Filtering and Summed-Area Tables

Diego Nehab1 André Maximo1 Rodolfo S. Lima2 Hugues Hoppe3

1IMPA 2Digitok 3Microsoft Research



Abstract

Image processing operations like blurring, inverse convolution, and

summed-area tables are often computed efficiently as a sequence of

1D recursive filters. While much research has explored parallel recur-

sive filtering, prior techniques do not optimize across the entire filter

sequence. Typically, a separate filter (or often a causal-anticausal

filter pair) is required in each dimension. Computing these filter

passes independently results in significant traffic to global memory,

creating a bottleneck in GPU systems. We present a new algorithmic

framework for parallel evaluation. It partitions the image into 2D

blocks, with a small band of additional data buffered along each

block perimeter. We show that these perimeter bands are sufficient to

accumulate the effects of the successive filters. A remarkable result

is that the image data is read only twice and written just once, inde-

pendent of image size, and thus total memory bandwidth is reduced

even compared to the traditional serial algorithm. We demonstrate

significant speedups in GPU computation.

1 Introduction

Linear filtering (i.e. convolution) is commonly used to blur, sharpen,

or downsample images. A direct implementation evaluating a filter

of support d on an hw-image has cost O(hwd). For filters with a

wide impulse response, the Fast Fourier Transform reduces the cost

to O(hw log hw), regardless of filter support. Often, similar results

can be obtained with a recursive filter, in which the computation

reuses prior outputs, e.g. yi = xi   1

2 yi 1. Such feedback allows

for an infinite impulse response (IIR), i.e. an effectively large filter

support, at reduced cost O(hwr), where the number r of recursive

feedbacks (a.k.a. the filter order) is small relative to d. Recursive

filters are a key computational tool in several applications:

 Low-pass filtering. Filters like Gaussian kernels are well

approximated by a pair of low-order causal and anticausal

recursive filters [e.g. Deriche 1992; van Vliet et al. 1998].

 Inverse convolution. If an image X is the result of convolving

an image V with a compactly supported filter F, i.e. X = V F,

the original image can be recovered as V = X F 1

. Although

the inverse filter F 1

generally has infinite support, it can be

expressed exactly as a sequence of low-order recursive filters.

 Summed-area tables. Such tables store the sum of all pixel

values above and to the left of each pixel [Crow 1984]. They

have many uses in graphics and vision. On a GPU, summed-area

tables are typically computed with prefix sums over all columns

then all rows of the image [Hensley et al. 2005]. ***cially, a

prefix sum is a special case of a 1D first-order recursive filter.

These applications all have in common the fact that they invoke a

sequence of recursive filters. First, a 2D operation is decomposed

into separate 1D filters. Second, except for the case of summed-

area tables, one usually desires a centered and well-shaped impulse

response function, and this requires the combination of a causal and

anticausal filter pair in each dimension.



全文请下载附件：

晃晃

每年短信都很卡，今年提前一点发，就算网络再怎么忙，保准我是第一个，祝福提前到：运气顺顺顺，一切旺旺旺，一年更比一年强！收到有福啦！

菜刀吻电线

我无语！

tc

楼主收集的可真全哦

晃晃

好`我顶``顶顶

tc

谢谢楼主，真是太实用了

晃晃

呵呵,真得不错哦!!

菜刀吻电线

跑着去顶朋友滴铁

铁锹 3D打印店铺

便利购物新体验_鸿星尔克推出3D试衣镜



3D成像技术可制作胎儿模型




HTML将增添新图形能力_万维网或将支持交互式3D图形




这些新技术让伦敦奥运会与众不同




网页游戏与客户端游戏将走向融合




什么是AR




“活报纸” 颠覆传统媒体观念




建设智慧城市技术路线图的关键技术分析




3D乐视TV遭抢购_新品工程机成“彩蛋”




美国工程师3D打印步枪

tc

佩服，好多阿 ，哈哈