运用可变模板进行并行图像处理的一种快速算法

计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报CHINESEJOURNALOFCOMPUTERS

Vol.26No.3

Mar.2003

󰀁运用可变模板进行并行图像处理的一种快速算法

董育宁

(南京邮电学院信息工程系󰀁南京210003)

摘󰀁要󰀁提出了一种在并行机上有效地计算(空间)可变模板的方法.论证了利用一个在图像网格点处计算多项式的优化算法,可以大大减少可变模板的运算量.对于包含非多项式函数的可变模板,可以用函数的泰勒级数展开实现在像素点上的递推运算.详细分析了可变模板中若干常用函数的泰勒展开用于实现模板运算的合理性、准确性和有效性.关于硬件的影响以及该方法的适用范围,也做了讨论.关键词󰀁图像处理抽象;可变模板;快速算法中图法分类号TP391

AnEfficientAlgorithmforParallelImageProcessingwithVariantTemplates

DONGYu󰀁Ning

(DepartmentofInformationEngineering,NanjingUniversityofPostsandTelecommunications,Nanjing210003)

Abstract󰀁Afastalgorithmforparallelimageprocessingwithvarianttemplatesispresentedinthispaper.Thisalgorithmisbasedonakeyobservationthatwehaveaprioriknowledgeofthechangingpatternsofthear󰀁gumentsi,jandk,andcantakefulladvantageofthis.Itisshownthatthepoint󰀁wiseupdatingofthevarianttemplatescanbegreatlysimplifiedbyuseofanoptimizedalgorithmforevaluatingpolynomialsattheimagegridpoints.Whiletheefficientcomputationofpolynomialsplaysacentralroleinthisapproach,thetechniqueisextendedtoincludetranscendentalfunctionswiththehelpoftheTaylorexpansion.Examplesoftypicaltran󰀁scendentalfunctionsshowthatreasonablyhighprecision,forcommonlowlevelimageprocessingapplications,andefficiency,usingonlyveryfewinitialtermsoftheTaylorseries,canbeachieved,whentheseriesformofthefunctionisusedforexecutingthevarianttemplateoperations.Theinfluenceofhardwareandthelimitationsoftheproposedalgorithmarediscussedattheendofthepaper.

Keywords󰀁imageprocessingabstractions;varianttemplates;fastcomputation

的实时操作,并可通过监视器进行人机交互处理.这些处理功能的质量在很大程度上影响着研究工作的效率及研究的成果.

图像处理正在越来越多的领域中得到应用,包括工业流水线检测、目标追踪、自动汽车驾驶、数字

[1]

电视图像传输以及医疗成像等方面.在许多实际应用中,图像处理系统必须能够进行海量图像数据

低级图像处理包含图像的抽样、滤波、旋转及其它有关图像像素级和邻域级的运算.这些运算一般都很简单,但由于需要处理的数据量巨大,所以要求处理机具有强大的处理能力.典型的图像处理算法

[2]

1󰀁引󰀁言

收稿日期:2001󰀁10󰀁10;修改稿收到日期:2002󰀁12󰀁15.本课题得到江苏省教育厅󰀂医学图像三维重建与分析系统 项目资助.董育宁,男,1955年生,博士,教授,主要研究兴趣是图像处理与分析、三维重建、网络视频流传输和图像数据库技术.E󰀁mail:dongyn@njupt.edu.cn.

3期董育宁:运用可变模板进行并行图像处理的一种快速算法

333

要在图像的每一个像素上进行成百上千次的运算.为了实现这样巨大的计算能力,人们提出了并行处

[3,4]

理的方式.

高级图像处理抽象中最有力的工具是图像模板运算,尤其是可变模板管道或序列.可变模板管道能较好地表达许多图像操作,如自适应滤波和图像变[5~8]换.尽管近年来许多学者对有效地执行图像模板运算这个问题进行了研究,但很少有人提及如何有效地执行通用可变模板.因此,关于如何有效地计算通用可变模板或可变模板管道这个问题,尚无定论.

本文将探讨在中等或粗颗粒的MIMD分布式多处理器系统中,如何有效地计算(局部)平移可变模板管道这个问题.在这样的并行机中,每个处理器在本地内存中至少存有若干整行或整列的图像数据,并且独立地处理本地的子图像.在英国贝尔法斯特女皇大学和乌尔斯特大学研制的EPIC可扩展并行图像协处理器,便是这样一个系统

[14,15]

[9~18]

规则像素网格点的性质,我们提出了一种解决更一般可变模板算子的方法,它可以大大简化这些模板的逐点更新过程.文章的最后讨论了硬件的影响及所提方法的适用范围.

2󰀁问题陈述

本节将指出可变模板管道的计算效率问题.一个模板T可用一个三元组集的通用表达式[8]

来定义:

T={!row-ofset1,col-ofset1,weight1∀,

!row-ofset2,col-ofset2,weight2∀,#

!row-ofsetN,col-ofsetN,weightN∀}

(1)

其中,每个三元组表示相对于中心像素的位置及该点的权值;N为模板中三元组的数目.每个可变模板的权值和󰀁或形状可随图像位置(i,j)和󰀁或管道阶数k而变化.实际上,模板的权值和形状可以是i,j,k及其它参数的任意函数,设为ft.图1列出了一些可变模板的例子.最直接的执行方法是通过调用函数ft在图像的每个像点上更新模板.不过,这种方法效率不会高.

.

本文第2节指出了可变模板的计算效率问题.根据我们最新的文献资料检索,该问题尚未很好地解决.为了对付这个问题,第3节中探讨了对某些特殊类型可变模板的解决方案.在第4节,根据图像中

其中,(a)为Hadamard行变换;(b)为类拉普拉斯算子,它的中心权值与它到图像中心(Cx,Cy)的距离成正比;(c)为可变形状的模板;(d)为通过反向地址映射的空间变换模板(如几何变形的校正;输入:IM0(p,q),输出:IM1(i,j)):

p=a0+a1i+a2j+a3i+a4ij+a5jq=b0+b1i+b2j+b3i+b4ij+b5j

2

2

2

2

两个变量,则可以先处理其它的变量(放在循环的最内层),在那里模板将保持不变.

(2)如果ft包含一些条件性测试,则可将图像分为几个子区域,每个子区域符合一个条件测试,并可用分段静态模板逐个地对每个子区域执行运算.例如:对于Hadamard行变换算子(图1(a)),按照even

k

(jdiv2)这个条件测试,每一行数据可分为两个子区域(真󰀁假),并将两个静态模板T1和T2分别用于这两个子区域.其中,

T1={!0,0,1∀,!0,2,1∀}󰀁󰀁󰀁真区域

k

.

3󰀁提高效率的提示

通过观察图1的例子,我们有若干种途径来改善直接法.

(1)如果ft最多只依赖于i,j,k三个变量中的T2={!0,0,-1∀,!0,-2,1∀}󰀁假区域󰀁具体地说,在第k阶,用于优化运算的C伪代码可写为k

334

for(m=0;mfor(j=0;j<2;j++){j1=m+j;

Image(i,j1)Conv.T1;󰀁󰀁真区域j2=m1+j;

Image(i,j2)Conv.T2;󰀁󰀁假区域}}

kk

计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2003年

(2)

运用Horner规则,得

p(x)=(#((amx+am-1)x+am-2)x+#+a1)+a0

(3)

这样计算p(x)需要m次乘法和加法.如果不能完全省去沿x的函数逐点更新,是否有可能进一步简化计算呢?通常这很困难,但在这里的特殊情况下,通过一个在算术序列点处计算多项式的算法,可以大大减少计算量.

给定如式(2)的m阶多项式p(x),我们希望计算在N个算术序列点x=d,d+h,#,d+(N-1)h(点距为h)处的多项式值.如果N󰀂m,则存在一种快速算法,可以大大减少代价较高的乘法运算

快速算法如下.

1.运用如式(3)的方法,计算前m+1个函数值,

p0,p1,#pm,其中pk=p(d+kh)

2.形成一个差分表格:󰀁Forq=1tom{

Fork=mdowntoqpk%=pk-pk-1;}

3.按如下方法算出所有N个函数值.󰀁SetP0%=p0thenloop:

Forq=1toN-1{Pq%=Pq-1+p1;Fork=1tom-1pk%=pk+pk+1;}

(4)

[19]

(3)大多数情况下,管道长度k远小于图像行或列的长度,并且总是可以先沿着i或j的方向运算,把k留在循环的最外层.所以,就计算效率而言,

在大多数应用中,依赖于k的ft变化并不重要.

如果ft依赖于i,j,k三个变量,并且没有类似于(2)的条件性测试(它可将T(ft)简化为一系列的分段静态模板),则我们必须寻找其它的方法来优化计算.显而易见,这种情况是最一般的,也是最难处理的.

.

4󰀁一般情况下的解决方案

本节提出一个一般情况下的解决方案,这个方案中有如下三个假设:

(1)每个处理器的本地内存中至少包含若干整行或整列的图像数据.

(2)可变模板的权值或形状将随函数ft的自变量i,j,k及其它参数变化,但是其它参数在整个处理过程中是固定不变的.

(3)在用户程序第一次运行之前或之后,优化器可获知ft的具体表达式信息(例如EPIC).

在阐述一般问题之前,先看一下另一个提示:对每一个处理器,由于运算是从一个方向到另一个方向逐步进行的(通常是从i或j方向开始的).所以为方便起见,在第一个方向上可暂时将ft看成是一元函数.如果沿这个方向(放在循环的最内层)可简化计算,则算法的复杂度将至少减少N倍(N为图像在那个方向的长度).

鉴于此,我们下面将把ft看成是一元函数f(x),而将另两个自变量当作参数.4.1󰀁多项式函数

首先考虑一个特例:f(x)是一个m阶多项式函数p(x),其中p(x)=amx+am-1x

m

m-1

由上可见,在p(x)的前(m+1)个值算出之后(第1,2步),p(x)在后续点的值只需m次加法便可算出(第3步),完全不需要乘法.4.2󰀁超越或无理函数

本节讨论常见的超越󰀁无理函数,它们有可能出现在可变模板的表达式中(以下为简便起见,就用超越函数来代表超越󰀁无理函数).

由上节可见,对于递推运算,多项式表达式是一个很有效的形式.因此我们希望,对于递推更新过程,能用多项式作为统一的表达方式.这一点可以由超越函数的泰勒级数实现.

设f是一个连续超越函数,f的泰勒展开可写成hf(x+h)=f(x)+hf&(x)+f∋(x)+#+

2!h(n-1)

f(x)+Rn,󰀁a x b

(n-1)!其中f

(k)n-1

2

+#+a1x+a0=

i=0

∃ax

i

m

(5a)

i

(x)是f(x)的k阶导数(假设这些导数存3期董育宁:运用可变模板进行并行图像处理的一种快速算法

335

n-1

2i+1

在);a,b是泰勒级数的收敛域.

Rn=

∃

(

i=n

hf(i)(x)i!

i

(5b)

2hlog(x+h)=log(x)+∃i=02i+12x+h其中,

2hRn=∃i=n2i+12x+h

(

2i+1

+Rn

(8a)(8b)

是余项.这样,一个无限项泰勒级数可表示为一个有限项级数加上余项.

现在的问题是:是否每一个超越函数的泰勒级数都存在一个适当的收敛域a,b.换句话说,我们是否能在n充分大时,使近似误差或余项任意小.这时,就可只取前n项,即

n-1i

h(i-1)

f(x+h))∃f(x),󰀁a x b(6)

i=0i!误差也能控制在预先设定的范围内.下面我们将分析一些典型的函数.

对数函数

f(x)=log(x)

(1)泰勒展开

[20]

更一般的,我们用y和󰀁y分别代替式(8)中的x和h,得

2󰀁ylog(y+󰀁y)=log(y)+∃i=02i+12y+󰀁y

y>0,-y<󰀁y<+(2󰀁y

其中,Rn=∃i=n2i+12y+󰀁yy可以是x的任意函数.

m

(

2i+1

n-1

2i+1

+Rn,(9a)(9b)

现在考虑一种较简单的情况:y是m阶多项式,

y(x)=P(m)(x)=

n=0

∃ax

n

n

(10)

hlog(x+h)=log(x)+2+

2x+h

1h32x+h

(3

假设式(9)的无限项级数在x的一个子域内收敛,并且f在一定的精度范围内,可用级数的前n

5

h+152x+h

+#

2n+1

项近似,则

n-1

log(y+󰀁y))log(y)+

=log(x)+

n=0

∃

2h2n+12x+h

∃

i=0

2󰀁y2i+12y+󰀁y

2i+1

,(7)

展开和式,得

3

(11)

x>0,󰀁-x或者

󰀁y1󰀁y

log(y+󰀁y))log(y)+2+

2y+󰀁y32y+󰀁y

󰀁y(2n-1)!!(2y+󰀁y)

=log(y)+

1󰀁y

+#+

2n-12y+󰀁y

2n-132(n-2)

+1(󰀁y)(2n-1)!!(2y+󰀁y)+#3+2n-1(2n-1)!!(2y+󰀁y)2(n-1)

1(󰀁y)5(2n-1)!!(2y+󰀁y)2(n-3)+#+(2n-3)!!(󰀁y)2n-152n-1(2n-1)!!(2y+󰀁y)S(m*

=log(y)+P*

(mQ(m*(2n-1))(x)=

P(m*(2n-1))(x)

其中,Q(m*Q(m*(x)

(12c)

注意,由于log(y)的值在上一次运算中已得出,所以在这里可看作一个常数,这样就不会增加上式中多项式Q(x)的次数.

f现在可用有理分式的形式计算更新值,它的分子和分母都是多项式,多项式的阶数由所需的精(2n-1))

(x)(2n-1))(x)

2(n-1))

(12a)(12b)

度和泰勒级数的收敛速度决定.

(2)收敛域

为了使式(11)或(12)中log(y+󰀁y)的近似值有效,必须确定式(9)的收敛域.下面这个简单例子讲述了确定收敛域的基本过程,假设x∗

例1.

设式(10)中的m=1,即

y=a1x+a0,󰀁a1+0󰀁y=a1h

y(x+1)=y(x)+a1(当h=1)(13)(14)0,N.

(x)与P(m*

(2n-1))

(x)均为m*(2n-(x)+S(m*

1)阶多项式;

(2n-1))

(x)=log(y)P(m*

(2n-1))2(n-1))

336

计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2003年

情况1.󰀁a1>0

由图2(a)可见收敛条件为(式(9),y>0)

a0>0,󰀁a1>0

如果式(15)成立,则另一个条件自动满足.情况2.󰀁a1<0由图2(b),可得

(15)

且

a1N+a0>0,󰀁对y>0

a1>-a1x-a0,󰀁对-y<󰀁y<+(

,

a1+a0

>x=Na1

(16a)

(16b)(17)

,a1(1+N)+a0>0,󰀁a1<0

因此,式(15)和(17)指出了该例中的收敛条件.对同一函数,泰勒展开有不同的形式,也就对应不同的收敛域.例如,对数函数也可展开为

2

󰀁y(󰀁y)log(y+󰀁y)=logy+-+2y2y

(󰀁y)

-#-y<󰀁y y33y

3

(

f(t)=

2-a(2t+1)

e2t+1

[21](

(22)

根据柯西󰀁麦克劳林积分公式

f(t)dt<−

n

,

(23)

i=n

∃f(i)

(

<

f(t)dt+f(n)−

n

(18)

将u=a(2t+1),du=2adt代入上式,积分式变为

如仍用式(13)和(14)的条件,收敛域可以是

a1阶数较高,则确定收敛域就较复杂些.

(3)误差控制

为使式(11)的泰勒级数在实际工作中可用,则近似误差应是可控制的.即对于给定的精度标准,我们应能确定要取开头多少项级数.通常,这可通过设定余项Rn的上下界来实现.

用一个最简单的例子来说明这个方法:令y=x且󰀁y=h=1.则式(9)变为

(2i+1

21

Rn=∃,󰀁x>0(20)

i=n2i+12x+1可见Rn依赖于x的值.当x增加时,Rn减小.设x!1,则Rn

i=n

−

z

(

uedu=E1(z)

-1-u

(24)

其中,z=a(2n+1);E1(z)为非完全Gamma函数的指数积分

[21]

.根据式(21)~(24),Rn2-z

e2n+1

(25)

由数学表查得因此,

[22]

(a=loge3)1∀10),

(26)

E1(5∀5)n=2=0∀00064

-5.5

R25

=0∀00064+0∀4.0∀004087=1∀64.10

-3

(27)

-3

在本例中,如果我们希望近似误差小于1∀64.10,只需取泰勒级数的前两项即可.

(4)收敛速度

如果所用函数的泰勒级数收敛速度很慢,为了达到指定的精度,就需要保留相当多的项(n很大).但是因为项数越多,计算量也越大,所以这就可能影响本方法的效率.在这种情况下,就需要提高级数的∃

(

2-(2i+1)

3=2i+1

i=n

∃

(

2-a(2i+1)

e,x>02i+1

(21)

其中,a=loge3,若令3期董育宁:运用可变模板进行并行图像处理的一种快速算法

337

收敛速度.

有一种可行的方法是:在式(7)的两边同时乘上一个多项式,通过改变多项式的系数以消除级数中收敛较慢的部分.考虑一个简单的例子:式(7)

2

h

中,log(x+h)乘上1+a1,得

2x+h1+a1

(

[21]

另外,也可写成

n-1

(x+h)

m

=

∃

i=0

m!m-ii

xh+Rn

i!(m-i)!

(33a)

其中,Rn=

i=n

∃

(

mm-ii

xhi

(33b)

h2x+h

2

log(x+h)=

2n+1

2h∃n=02n+12x+h

2a1h+∃n=02n+12x+h

(

2n+3

(28)

逐项合并右边的两个级数,得1+a1

h2x+h

(

2

log(x+h)

h2x+h

2n+1

2ha11=+2∃+2x+h2n-1n=12n+1

(

2n-1+a1(2n+1)2hh=+2∃2x+h(2n+1)(2n-1)2x+hn=12n(1+a1)+a1-12hh=+2∃2x+h(2n+1)(2n-1)2x+hn=1

(

2n+1

2n+1

(29)

显而易见,若令a1=-1,则合并后的序列为2h-2h+2∃2x+h2x+hn=1(2n+1)(2n-1)它随n

-2

(

2n+1

(30)收敛,比原来级数的收敛速度提高了一个

(2)收敛域

如果仍用y和󰀁y分别代替式(32)中的x和h,设y为x的一次函数,就像式(13)一样,则也将得到如式(19)的收敛域.

(3)误差控制

[21]

对式(33)的余项运用拉格朗日公式,得

(

mm-iimm-nn

Rn=∃xh=(x+󰀂)h(34)

i=nin

其中,0 󰀂 h.

m-n

设h=1,如n>m,则当󰀂=0时,(x+󰀂)最大.所以

mm-n

Rn x,x>1(35)

n

设m=1󰀁2,当x!2时,有

1-21-11-4.5-22R2 ...2=2=4.42.10222

(36a)

3.5-3

R4 =3.45.10(36b)3

16.24.22同样,当x增加时,Rn减小.若x!5,则R2 2-3.52=1.12.10-2(37a)

-43.5R4 =1.40.10(37b)3

16.24.55

(4)收敛速度

我们可以用前面所讲的方法来提高式(32)的收

mh敛速度.将式(32)中的(x+h)乘上1+a1,得

x

hm

1+a1(x+h)

x((n+1mhnmmh=x∃+a1∃xn=0nn=0nx=x=x=x

m

1-2

数量级.

事实上,可以乘上更高阶的多项式,使合并后的级数以n

log(x+h)

2h-2h

log(x)++2

2x+h(2n+1)(2n-1)2x+hn=1

=2h

1-2x+h

-3

,n

-4

等速率收敛.结果,我们将式(7)这

样一个简单的级数展开变为一个新的有理分式:

∃

(

2n+1

,(31)

这个分式表达式既简洁,又有效,它缩短了级数,提高了计算效率.

二项式函数

m

f(x)=(x+h)󰀁(m不是整数)(1)泰勒展开

[20]

二项式函数可展开成如下的泰勒级数:(x+h)mm1+1+1+

n=1

m

∃∃∃

((

(

mn

hx

n

+a1hxhx

n

n=1

∃

(

mn-1hx

n

󰀁󰀁

n=1

m

mn-1mn-1m-n+1+a1nnm+1+(a1-1)n

n

(38a)

n

n=1

=n=0∃(mnxm-nhn(32)若令a1=1,则上式变为x+mm!其中,=叫作二项式系数.n!(m-n)!n∃(n=1mm-nnm+1xh

nn-1(38b)

338

计󰀁󰀁算󰀁󰀁机󰀁󰀁学󰀁󰀁报2003年

原先分子中的m-n+1被m+1代替,而m+1是一个常数(与n无关).这样将收敛速度提高了-1

n级.

硬件有关.如果计算机配置了算术协处理器,则内置函数(如log,sqt,exp等)就执行得相对快,所以也许不必对这些函数进行泰勒展开,直接法可能更有效.不过,要是能对任一种计算机都提供一个优化方案,而不需借助于特殊的硬件,不是更好吗?

5.3󰀁算法的局限

这里没有考虑嵌套超越函数的情况.尽管本文讲的基本理论也许适用于这种复杂的情况,但诸如收敛性、误差分析和级数展开的有效性等问题还有待验证.不过所幸的是,在低级图像处理中,很少见到这种复杂的表达式.

5󰀁讨󰀁论

5.1󰀁误差分析的进一步讨论

(1)另一种途径

前面已通过例子论述了如何控制近似误差,这种方法也可用来处理更复杂的情况,只是要用到更多的数学计算.由于在非实时情况下,真实值通常总是可得的,所以可考虑另一种替代方法.让z和z^分别表示真实值和估计值,则误差E可表示为

(39)

因此,可用另一种方法来估算精度.这种误差控制方法可与前面提及的解析方法结合使用,并且,如果解析公式不够精确或很难得到,这种方法也许就更好.

(2)误差累积

前文的误差分析方法,只考虑了当前位置产生的近似误差.但是,由于递归计算包含了前一位置的馈入,所以上一步产生的误差可能会累积到下一步.比如,从位置0前进到位置1,

^E=z-z

6󰀁结󰀁论

本文提出的快速计算可变模板管道的方法,是基于这样一种观察,即我们知道自变量i,j,k的变

化模式,并能充分利用这些条件.文中证明了,可以利用在图像网格点处计算多项式的优化算法,来有效地减少计算可变模板算子的运算量.

尽管在这种方法中,多项式的高效计算起了重要作用,借助于泰勒展开,这种方法已可扩展到超越函数.在几乎任何系统配置中,这种方法对多项式而言,在计算上的优势是显而易见的.而对超越函数而言,则依赖于其它一些因素,包括硬件的配置.但是,通过前述典型的超越函数的例子可知,当用函数的级数形式来执行可变模板算子时,能够得到较高的精度(对一般的低级图像处理而言)和较高的效率(仅使用泰勒级数的前几项).

^1=z^0+󰀁z^󰀁󰀁(由式(39))z

=z0+E0+󰀁z+E1=z0+󰀁z+E0+E1=z1+E1c

其中

E1c=E0+E1

位置t,

Etc=

i=0

(40a)(40b)

是包括从位置0扩散到位置1的累计误差.通常,在

致谢󰀁感谢英国贝尔法斯特女皇大学的D.Crookes教授对本文工作的宝贵建议.

∃E

t

i

(41)

12

参考文献

可能我们已注意到,在许多情况下,近似误差或泰勒级数的余项Rn与x的位置有关.当x增大时,它就减小,就如式(20),(35)和(40)所示的那样.这就给了我们一个提示,即沿着x轴倒序循环,就可

能减小总体误差.这样,由前面迭代产生的很小的误差,在后面的迭代中可忽略不计.因此,总体误差就可由在x的最后一点(最小值)处产生的误差粗略地估算得到.

5.2󰀁性能的硬件相关性

就多项式的计算而言,本文所讲的方法在绝大多数机器上都能高效地运行.而对于超越函数,则与645

PrattWK.DigitalImageProcessing,2ndEd.NY:JohnWiley&Sons,1991

ChoudharyAN,PatelJH.ParallelArchitecturesandParallelAlgo󰀁rithmsforIntegratedVisionSystems.KluwerAcademicPublishers,19903

HullMEC,CrookesD,SweeneyPJeds.ParallelProcessing:TheTransputerandItsApplications.Addison󰀁Wesley,1994

ZomayaAYed.ParallelComputing:ParadigmsandApplications.In󰀁ternationalThomsonComputerPress,1996

RitterGX,etal.Imagealgebra:Anoverview.CVGIP,1990,49:297~331

BrownTJ,CrookesD.Ahighlevellanguageforimageprocessing.3期董育宁:运用可变模板进行并行图像处理的一种快速算法

339

ImageandVisionComputing,1994,12(2):67~797

CrookesD,MorrowPJ,McParlandPJ.IAL:Aparallelimagepro󰀁cessingprogramminglanguage.IEEProceedings,PartI,1990,137(3):176~1828

CrookesD,SpenceITA,BrownTJ.Efficientparallelimagetrans󰀁forms:Averyhighlevelapproach.In:Proceedingsofthe1995WorldTransputerCongress,1995.135~1439

WilsonJN,FischerGR,RitterGX.Implementationanduseofanimageprocessingalgebraforprogrammingmassivelyparallelcomputers.In:Proceedingsofthe2ndSymposiumontheFrontiersofMassivelyParallelComputation,Fairfax,VA,1988.587~5941011

CoffieldPC,ScudiereMB.Aprototypecoprocessorforimagealgebraoperations.In:ProceedingsoftheSPIE,1993,2030:327~333ShiH,RitterGX,WilsonJN.Anefficientalgorithmforimage󰀁tem󰀁plateproductonSIMDmeshconnectedcomputers.In:Proceedingsofthe1993InternationalConferenceonApplication󰀁SpecificArrayProces󰀁sors,Venice,Italy,19931213

ShiH,RitterGX.Aspecialclassofnonlocalimage󰀁templateopera󰀁tions.In:ProceedingsoftheSPIE,1994,2300:204~212

ShiHong󰀁Chi.Twoimage󰀁templateoperationsforbinaryimageprocess󰀁ing.JournalofMathematicalImagingandVision,1997,7(3):269~27414

CrookesD,BrownTJ,DongY,McAleeseG,MorrowPJ,Roantree

2221201918171615

DK,SpenceITA.Aself󰀁optimisingcoprocessormodelforportableparallelimageprocessing.In:LNCS1124,Berlin:SpringerVerlag,1996.213~216

MorrowP,CrookesD,BrownJ,DongY,McAleeseG,RoantreeD,SpenceI.Achievingscalability,portabilityandefficiencyinahigh󰀁levelprogrammingmodelforparallelarchitectures.In:ProceedingsofUKPAR&96,1996.29~39

WilsonJN,ForsmanRH.Usingtemplatesandneighborhoods:Practi󰀁calconsiderationsandformalobservations.In:ProceedingsoftheSPIE,1994,2300:192~203

LiD.Recursiveoperationsinimagealgebra.󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁󰀁

SussnerP,RitterGX.Rank󰀁baseddecompositionsofmorphologicaltemplates.IEEETransactionsonImageProcessing,2000,9(8):1420~1430

CrandallRE.TopicsinAdvancedScientificComputation.SpringerTe󰀁los,1996

BeyerWH.CRCHandbookofMathematicalSciences,5thed.FL:CRCPress,Inc.,1975

ArfkenG.MathematicalMethodsforPhysicists,3rded.Orlando:Ac󰀁ademicPress,Inc.,1985

BeyerWH.CRCStandardMathematicalTables,26thed.FL:CRCPress,1981

DONGYu󰀁Ning,male,borninyearof1992󰀁1993,hestayedatImperialCollegeLondonasvisitingscholar,supportedbyaBritishCouncilpostdoctoralfellowship.From1993to1995,hejoinedUniversityofTexasMedicalBranchaspostdoctoralfellow,workingonmedicalimaging.AfterthathespentthreeyearsasresearchfellowatQUBandUniversityofBir󰀁mingham.HeiscurrentlyprofessoroftheDept.ofInformationEnggofNUPT.Hisresearchinterestsincludeimageprocessing󰀁analysis,3Dreconstruction,Internetvideostreamingandimagedatabases.

1955,receivedhisB.E.degreein1982,M.E.degreein1984fromNanjingUniversityofPosts&Telecommunications(NUPT),Ph.D.degreefromSoutheastUniversityin1988,allinElectricalEngineering,andM.PhildegreeinComputerSciencefromThe

Queen/sUniversityofBelfast(QUB)in1998.Duringtheacademic