GPU加速的基于增量式聚类的视频拷贝检测方法_图文

第 2 2卷 第 3期 
21 0 0年 3月 

计 算机 辅 助设计 与 图形学 学报 
J u n lo  mp trAie   sg & Co u e  a hc  o r a  fCo u e — d dDein mp trGr p is

V o .2   o.   1 2N 3
M ar 2O   . 1O

GP 加 速 的 基 于 增 量 式 聚 类 的 视 频 拷 贝 检 测 方 法  U
任化敏   张勇东” 林守勋”  。, ,  
( 国 科 学 院 计算 技 术 研 究 所 前 瞻 研 究 实 验 室  北 京  1 0 9 ) 中 0 1 0  ’ 中国 科 学 院 研 究 生 院 ( 北京 10 4 ) 0 0 9 

。( 京 中 医 药 大 学信 息 中心  北 京  10 2 )  北 0 0 9 
( e h a n ita . n) r n u mi@ c. c c  



要 :为有 效 地 保 护 版 权 , 高 大规 模 视 频 集 的拷 贝 检 测 速 度 , 出一 种 完 全 实 现 在 G U 上 的 基 于 增 量 式 聚 类 的  提 提 P

拷 贝 检 测 方 法 . 数 据 库 中 新 增 加 的 视 频 , 先调 用 G U 上 的 硬 件 解 码 单 元 对 视 频 流 解 码 , 实 时 的 速 度 提 取 高 维  对 首 P 以 SF 特 征 点 ; 后 对 特 征 点 进 行 增 量 K— a s 类 , 动态 地 反 映数 据 库 的 变 化 , 根 据 聚 类 结 果 更 新 视 觉 关 键 词  IT 然 men 聚 以 并 词典 ; 再将 每 帧 表 示 成 归 一 化 的 词 频 向量 ; 后 使 用 基 于 帧 级 别 词 频 向量 的 时 空 顺 序 匹 配 法 来 判 定 查 询 视 频 是 否 为  最 数 据 库 中视 频 的拷 贝 . 验 结 果 表 明 , 方 法 比原 有 的 C U 实 现 方 法 整体 提 速 最 高 达 6 实 该 P 3倍 .  
关 键 词 :拷 贝 检 测 ; 量 聚类 ; 觉 关 键 词 ; 增 视 图形 处 理 器 ; 算 统 一 设 备 架 构  计
中 图法 分 类 号 :TP 9  31

GPU- c l r t d Vi e   p   t c i n Ba e   n I r m e a   u t r n   Ac e e a e   d o Co y De e to   s d o   nc e nt lCl s e i g
R e   u m i   ’ , Zh ng Y o d g” , a d Li   ou n H a n ’    a   ng on n   n Sh xun  
”( a oa o yo   v n e   o u ig Ree rh,I si t o   o u i g Teh o o y, h n s Ac d my o   ce c s e ig 1 0 9 ) L b r tr   Ad a cd C mp t   sa c f n n t u e f C mp tn   c n lg C iee a e  f S in e ,B i n   0 1 0  t     j ( a u t U i est f C ieeAc d my o   ce cs e i g 1 0 4 ) Gr d a e n v ri o   h n s   y   a e  f S in e ,B i n   0 0 9  j ( n o ma inC n e ,B iig Unv ri     h n s  e iie e ig 1 0 2 ) If r t   e tr ejn   ie s y o C i ee d cn ,B i n   0 0 9   o t f M j

Absr c : Fo  e f c i e e s f rva y ta t r fe tv n s  o  p i c  pr t c i n n  e fce y f opy o e to  a d f iinc  o  c  de e to  o  l r e i o t c i n n a g  v de   da a e s,a f ly GPU— a e  nc e e a  o   t c i   c me i  r p e .W he    wl   dd d v de   ts t  ul  b s d i r m nt lc py de e ton s he  s p o os d n a ne y a e   i o a rv s i o t e d t ba e,GPU  — hi  e o ri  a ld f   i o s r a de o i r i e  nt  h   a a s on c p d c de  Sc le  orv de   t e m  c d ng.Att e s m e tm e    h   a  i , hi h d me s o I FT f a ur s r  e t a t d n he r m e n e ltm e, whih S o l we  b  a   g   i n i na SI e t e  a e x r c e  o  t  fa  i r a— i c  i f lo d y n i r me a  m e ns l t rn  me h  r s on i  t  t  d a c a a s  u e  t  u a e iua  nc e nt lK— a  cus e i g t od e p d ng o he yn mi d t ba e s d o pd t v s l wo ds c de ok The r   o bo . n,e c   r me i  e r s nt d wih   i u l a h f a   s r p e e e   t  a v s a wor s f e u nc   e t . Fi ly,a d   r q e y v c or nal   s a i e p r ls q nc   t hi g m e ho   s d o   iua  r s r p e e a i n a  r me lve  s us d p tot m o a  e ue e ma c n   t d ba e   n v s lwo d   e r s nt to   tf a   e li  e  

t   e e m i e wh t e   h   u r   s a c p . Ex e i e t lr s ls s o t a   u   o d tr n   eh rt e q e y i   o y   p r n a  e u t   h w  h t o r GPU  m p e n a i n m i l me t t   o
a hi v s u   o a 6   i e   p e up o e  he CPU  e son  c e e   p t     3 tm s s e d   v r t   vri .

K e   r : c py d t c i y wo ds o   e e ton; i c e e t lcus e i g;viu lw o ds GPU ;CU D A  n r m n a  l t rn s a  r ;

近 年来 , 网络 技 术 的 发展 和 带 宽 的提 高使 得 在 
线 视频观 看迅 速普及 , 网络 视频 呈爆 炸式 态势增 长 ,  

印 和拷 贝检测 技术 . 印技 术 可 以在 视 频 中添 加 某  水 些版 权信 息 , 但必须 在 视频发 布 前完成 ; 贝检测 技  拷
术 通 过提 取视 频特 征判 断给 定视 频段 是否 为拷 贝视 

版 权侵犯 现 象也 随之 加 剧 , 如何 有 效 地 保 护 版权 已 
成 为 了亟 待解 决 的 问题 , 目前 的主 要 解 决方 法 是 水 

频 , 视频 没有 附加 要求 , 用更 为灵 活. 对 使  

收稿 日期 :0 9 0 1 ; 回 日期 :0 9 2 1 . 金 项 目 : 2 0 — 5 5修 2 0 1 — 5 基 国家 “ 七 三 ” 点 基 础 研 究 发 展 计 划 项 目( 0 7 B 1 1 0 ; 家“ 六 三” 技  九 重 20C 310)国 八 高 术 研 究 发展 计 划 (0 7 2 0 AA0 Z 1 ) 国 家 自然 科 学 基 金 (0 7 1 5 6 82 2 ) 北 京 市科 技 新 星 计 划 项 目( o 7 O 1 ; 京 市 教 育 委 员 会 共 建  146 ; 6 8 3 6 ,0 0 0 8 ; 20B 7)北 项 目专项 . 化 敏 (9 0 ) 女 , 士 研 究 生 , 师 , 要 研 究 方 向 为 多媒 体 分 析 与 检 索 、 任 18 , 博 讲 主 多媒 体 的 高 性 能 计 算 ; 勇东 ( 93 ) 男 , 士 , 究  张 17 , 博 研

员 , 士 生导 师 , C 博 C F高 级 会 员 , 要 研 究 方 向为 数 字 多 媒 体 技 术 , 括 视 频 内 容 分 析 和 表 征 以及 基 于 内容 的 视 频 编 码 与 传 输 (h d i . e 主 包 z y @ c a. t   e)林守勋(98 )男 , 士 , n; 14一 , 博 研究 员 , 士生 导 师 , C 博 C F高 级 会 员 , 要 研 究 方 向 为 多 媒 体 技术 及 应用 系统 (xi@ita. n . 主 sl n c.cc )  

40 5 

计 算 机 辅 助 设 计 与 图形 学学 报 

第 2 卷  2

基 于 内 容 的 拷 贝 检 测 ( o tn  a e  o y c ne t b sd cp  

些全局 信息 对于颜 色 的变 换 、 帧率 的改 变 、 辨率 的  分 改变具 有较 好 的鲁棒 性 , 计算 全 局 特 征所 需 的时  且
问短 、 匹配速度 快 ; 缺点是 对于视 频后期 制作 中频繁  出现 的变换类 型 , 如插 入 台标 、 切等效果 差. 剪  

d tcin B D) 一 种 常 用 的拷 贝检 测 方 法 , eet ,C C 是 o 在  具体 设计 时 必 须 考 虑 来 自于有 效 性 和 高效 性 的 挑  战. 有效性要 求 既能 应 对诸 如 增删 视 频 片段 、 照 、 光  

颜色 、 模糊 、 a G mma 全 局变 换 , 能 应 对剪 裁 、 等 也 平  移 、 中画 、 画 高光 等局 部 变换 ; 高效 性 则要 求 面 对庞 
大 的视频数 据库 时能够在 可容 忍的时 间范 围内得 到  精确 的检测结 果. 针对 we b视频 的 C C B D还需 要解  决 2 方面 的难题 :) 够应 对 随 时变化 的 we 个 1能 b数 

基 于局 部 特征 的方 法 分 为 2种 : 种是 通过 全  一
局 特征 整合局部 特征 , 改善局 部 的性能  ; 另一种 是  跟 踪视 频 序列 中局部 特 征点 的动态 变化  . 部 特  ]局 征 能更好 地关注 局部视 觉信 息的变 化 , 尺度 、 转  对 旋

等 变换表 现鲁棒 , 但是需 要更 大 的存 储空 间 , 匹配 更 
加耗 时.  

据. 互联 网上 每天都 有新上传 和新 删除 的视频 , 是动  态变化 的. 目前 Go ge o l 等对 于互联 网文本数 据处 理 
和检索 的主流方 法是 离线 生成 数 据 库 , 在一 定 时 问  间隔后重 新生成 数 据 库 以应对 数 据 的变化 , 此 方  但 法 对视频 数据 而言计算 量过 大 , 并不 适合. ) 2 能够 在 

我们 结合 使 用 了局 部特 征 和全 局 特征 的优 点 ,   将视 频本质 上存 在的时 序和空 间顺 序用于 匹配过程 
中 , 效地应 对 了全 局 和局 部 攻击 ; 时也 发现 , 有 同 作  为核 心 的特征 提取 和 聚类 方 法 相 当 费时 , 大地 影  极 响 了拷 贝检测 的整体 速度 r . 7 近年来 , ] 以超 越摩 尔定  律速度 发展 l 的 GP 是 十分 容 易获 得 的并 行计 算  8   U 硬件 , 已有 很 多研 究 者 为 了利 用 GP 的并 行 特 性  U 进 行通 用计 算 而设 计 了独 立 的 编 程 模 型 , GP   使 U 程 序 的 编写 变 得 简 单. Sa fr 如 tnod大学 B c uk等 设  计 的 B o k AMD 公 司 进 一 步 改 进 的 B o k , ro , ro +  
NVI I 公 司 的 C DA UDA 等 . U 用 于 通 用 计 算 的 GP  

有 效性和 高效性 之 间 寻求折 中. 使 C C 要 B D方 法 具  有 高 的有效 性 , 要 使 用大 量 的 高维 特 征描 述 视 频  需 的信息 , 据量增 大必然 导致计 算量 增大 , 降低 高  数 会
效性; 反之 , 如果选 择 低 维特 征 , 然 计算 量 得 以控  虽 制 , 会降 低 C C 的精 度. 但 B D  
本 文 提 出 的在 GP 上 实 现 的 基 于 增 量 式 聚 类  U

的拷 贝检测 方法能 够 较好 地 解 决 以上 2个 难题 . 对  于每 E大量新 增 的视 频数 据 , 文 首 次提 出 了基 于  l 本 增量 聚类 的拷 贝检 测 方法 , 以随 时将 新 的视频 特  可

发展 为我 们 的拷贝检测 方法 在性 能方面 获得提升 提  供 了机会 . 根据 我 们 的实践 经验 , 于 C A 在 易  由 UD
用性、 稳定 性和 性能上 优于其 他众 多编程 模型 , 以 所  

征描 述融人 特征数 据 库. 于有 效 性 和高 效 性难 以  对 兼得 的问题 , 我们 针 对 G U 的体 系 结 构 重新 设 计  P
了拷 贝检测方 法 的所 有 步骤 , 本 文方 法 可 以完 全  使 运 行在 G U 上 , 仅 计 算 效 率 获 得 提 升 , 具 有  P 不 还 C U 仅负责 GP 核 函数调 用 的优 势 , 免 了低 效  P U 避

我们 采用 它作 为本文方 法 的实现 手段.  

2 基 于视 觉 关键 词 的 w b视频 拷 贝检 测方 法    e
2 1 方 法 描 述  .

的 C U 与 GP 间的数据 传输. P U  

1 相 关 工 作   
C C 方 法 可 分 为 基 于 全 局 特 征 和 局 部 特 征 的  B D

文献 [ ] 用 了 S F g作 为 局 部特 征 描 述 子 , 7采 I T_     视觉 关键词 作 为帧级 别 的描 述信 息 , 随后将 每 帧 表  示为 各个视 觉关 键词 的词 频 向量 , 待 查询 的视 频  将

两 大类口 . 局特 征 的方 法 基 于对 2段 视 频 的颜 色  J全 直 方 图、 度在时序和空 间上 的分 布等 全局信息 的比  灰

与数 据库 中视频 的 比较 转换为 对应 帧序列 的时空顺  序 匹配. I T是 公认 的在尺度 、 转 、 照等变换 中 SF 旋 光   性能 鲁棒 的特征 ; 觉关 键 词 的使 用 很 好地 弥 补 了  视
SF I T特征 维数 高 、 算 量 大 的缺 点 ; 空顺 序 匹 配  计 时

较, 关键在 于全 局信息的选取 . a ce 等  提取 关键  S nhz 帧 的颜色 直方 图的 主成 分作 为 全局 信 息 ; a au  H mpp r 等 l 提取边 缘 特 征 作 为全 局信 息 ; mp p r等  3   Ha a u 将 帧分为 N  ×N 个 区块 , 算 各个 区块 的灰 度 均  计
值并 排序 , 最终将 帧 表示 为 一 个分 量 为各 区块 灰 度 

方法 有效地利 用 了视 频 本 身存 在 的 时空 关 系 , 文  本
中的实验结 果也 验证 了该 方 法 的有 效性 . 了满 足  为

we 频拷 贝检测 的需求 , b视 本文 在文献 E ] 7 的基础 上 
将生 成词典 的过程 改 为 动 态过 程 , 当数 据库 中新增 
视频 时 , 据新增 的特 征动态调 整 已有 的视 觉词 典 , 根  

序号 的 向量( 称为 顺 序灰 度 签 名 ) 并 将待 查 询 视 频  ,

与 库视频 的匹配转 换为 给定 时间窗 口内对应 灰度 签 
名 的差异 , 该方法 利 用 了灰 度 在 时 间和 空 间上 的分  布 , 对数 字化或 解码 中产生 的全局 变换不 敏感. 但 这 

而不 是重新计 算 库 中 的所 有数 据. 文 方法 的流 程  本
图如 图 1 示 . 所  

第 3期 

任 化 敏 , : U 加 速 的基 于增 量式 聚类 的 视 频 拷 贝 检 测 方 法  等 GP

41 5 

新增视频  I 提取特征 

 ̄) rg a  k abg

+l 觉关 词词} 提取   成视 键   特征
厂 —  

I - en聚类生 l 厂—一 K m as

 

典 !   IL   ! I !  !   T   l ,   ^ J  
I 确定特征点的 I  
所属词
Y 

l 广——一

l  

数据 库视频 

 

查视 H 提特 H 询频 取征

确  

的 H

生望  时顺匹  需频 空序配

帧级 别 

I  

词频向量  l  
— —

(o   J B W)     /
  — — — —

离线 

图 1 本 文 方 法 流程 图 

当新视 频增 加到 数据 库 时需 要 使用增 量 聚类方  法 . 文本不 同 , 与 由于视 频 含有 丰富 的信 息和 大量 的  数据 , 因此增 量 聚类实 现难 度很 大 , 我们 目前 尚未见 

2 SF ) I T特征 提取 . 提取 S F 特征 的主要 步骤  IT 包括 构建 图像 的 尺度空 间 、 检测特 征 点 、 定特 征点  确 的尺 度 和主 方 向 、 成 特 征 描 述 4个 步骤 . 体 来  生 总

到有 关 有 效 的 视 频 数 据 增量 聚类 方 法 的报 道.   C I M 是 文 本 中 的 增 量 聚 类 方 法  , 每 次 将 无  2C 其
法 属于 任何种 子 类 的点 丢 人 rg a , 下 次 增量 时  abg 作 先 找到 与该 rg a a b g最 近的类 , 合并 属 于 2个 类 的所  有 特征 之后再 作 聚类 ; 但该 方法 不 适 合 特 征 多 的视  频数 据 . 本文采 用 的增量 式 聚类方 法 步骤 如下 :  
Se 1 tp .建 立视 觉 关 键 词 词 典 . 义 数 据 库 的 特 征 集 合  定 为 F, 觉关 键 词 词 典 的容 量 为 K, 典 对 应 的 特 征 向 量 集  视 词 合 用 w 表 示 . 新 增 视 频 的 特 征 集 合 为 ,, 每 一 个 属 于集  设 对

讲 ,I T方法 属 于易 并 行 方 法 , 任 何 一个 像 素 点  SF 对 或特 征点 的计 算对 不依 赖其 他点 , 以 同时 进行 . 可 基  于这 种并 行性 , o等口 Ha  在 1 6核 的对 称 多 处 理 器  计算机和 6 4核 的片 上 多处 理 器 模 拟 器 上实 现 了并  行 SF I T方 法 , y n He ma n等  使 用 传 统 GP 和 图 U  
形 AP 实 现 了 SF 方 法 , h r t _  GP 上  I IT C ai 等 l 在 o 。 U

进 行 了 图片匹 配及 可扩 展性 分析 .   3 )K— a s聚 类 . men men K— a s聚 类 方 法_ 1  将 7 2   个 d维 特征 的数 据点 构成 的 1 数据 簇聚 类为 k 组 个 

合 ,的特 征 向量 v 寻 找 与 v欧 氏距 离 最 小 的 视 觉 关 键 词 w, ,  
如 果 该 距 离 小 于 指 定 的 阂 值 , 将  归 属 到 这 个 词 , 将 词  则 并 的 特 征 描 述 更 新 为 
N ·w + 1 ·v  
’ : ‘   ’ —   一 ;  

子数 据簇 , 一个 子数 据簇 代表 一类 , 并用 均值 来表示  其 聚类 中心 . 体 实 现 中 , 具 初值 聚类 中心 随 机 给定 ,  
每 步迭 代时 计算 每 个 数据 点 与 聚类 中心 点 的距 离 ,  

将该 点 关联 到 与其 最 近 的 中 心点 所 代 表 的类 后 , 再 
其 中 N 为更 新 前视 觉关 键 词  包 含 的 特 征 点 个 数 .   S e2 tp .如 果 存 在 无 法 归 属 到 任 意 一 个 视 觉 关 键 词 的 特 
征 , 将 其 放 入 rg a. 则 abg   S e3 tp .当 rg a a b g中数 目超 过 一 定 值 时 , K me n 聚  用 - as 类 rg a a b g中的 特 征 点 , 更 新 已 有 的 词 典 . 并  

由该 类 所有数 据 点取 均值 生 成 新 的 中心 点 , 到所  直 有数 据 点归类 后 迭代 完 成. 论 是 传统 K— a s聚  无 me n
类还 是本 文 的增 量 聚类 方 法 , 耗 时 的部 分 都是 特  最 征点 间的距离 计算 . 由于 K~ a s men 聚类 方法 的 每个  数据 点各 自独 立 , 寻 找 其 最 近 中心 点 时 不产 生 数  在 据相 关性 , 计算 每 个 子数 据簇 的 中心 点 也 不产 生 数  据相 关 , 以 K- a s聚类 可 以并 行 地 完 成. 所 men 已经  有一 些 在 GP 上 实 现 的 K— a s聚 类 方 法 , U me n 如 

可 以 证 明 , 觉 关 键 词 词 典 的 形 成 不 依 赖 于 增  视

量 视频 的顺序 , 论用 户 以怎样 的顺 序上 传视 频 , 无 只 
要数 据是 确定 的 , 最 终形 成 的视 觉 关 键 词 词典 就  则 是确 定 的.  
22 可 并行 性分析  .

C o等口 a  利用 传统 GP 的流 式 体 系结 构 实现 了流  U
式 K— a s 法 ; h me n 方 C e等n  使 用 C A 实 现 了简  UD

1 )视频 帧提 取. 提取视 频 帧是 提 取 特征 和特 征 

匹配 的基 础 , 目前 多数 GP 都 具 备 对 于 多 种 主 流  U
视频 编码 格式 硬件 解 码 的能 力 , 种 硬 件解 码 单 元  这 在 NVI I   U 上 被 称 为 视 频 处 理 器 , AMD D A GP 在  

单 的 K  a s men 方法 , 还 需 要 C U 参 与 一 部 分 计  但 P 算 , 能完 全 利 用 GP 的计 算 能 力 ; a g等[ 没 U Fn 1  也  使用 C UDA 实 现 了 基 于 访 存 联 合 的 K— a s聚  me n 类, 但其 与二 维数 据 紧密耦 合 , 聚类 高维 数据 时性 能  明显 降低.  
本文方 法的设计 目标是完全执行 于 GP 的针对  U

GP U上 被称 为统 一视 频解 码 器 , 们 可 以直接 调 用  我
相 应硬 件提 供 的软件 接 口获得 相对 于 软件解 码更 高 
的速度 .  

42 5 

计 算 机 辅 助设 计 与 图形 学 学 报 

第 2 卷  2

高维 数 据 的 性 能优 化 , 因此 必 须基 于 G U 体 系结  P
构重 新设计 整个 方法.  

储 器上 , 由于采 用访 存 联 合 大量 减 少 了全 局 内存 读  取 次数 , 读取 速度得 以提高 .  
4 2 原 子 加 操 作 的 优 化  .

3 G U 的优 化 策 略    P
1 )指 令 吞 吐 量 的优 化 . U 与 C U 的 最 重 要  GP P

特 征点 提 取 中 的方 向定 位 、 聚类 中的类 数据 点  总 和计算 以及 特征 点所 属 词 的词 频 计算 , 涉及 大 量 
独 立 的线 程 对 同 一 地 址 数 据 进 行 写 操 作 , 时 会 造  此

不 同就是 其 计 算 单 元 是 C U 上 计 算 单 元 的 数 十  P

成 写后读 或读后 写 的 数据 不 一致 , 解决 此类 问题 的  方 法是加 锁 , 称为原 子操作 . 也 本文 在共享 存储器 内 

倍 , 效分 配和利 用众 多 的计 算 单元 是 拷 贝 检测 方  有 法获得 计算 能力 的保 证. 实现 拷 贝检 测 的要 求 是  对
能够分 配足够 多 的线 程 , 线程 数 目、 存 次数 、 算  访 计
量要 根据各 自的时间进行 调整 , 达 到更好 的效果 . 以  

进行 原子加 , 有数据 执行读 或写操 作后 , 将各个  所 再
线程 块 内的结果 数据 累加 , 成计算 . 完  
4 3 求 特 征 点 间 距 离 的 优 化  .

2 )存储 器带 宽 的优 化. 储器 带 宽 的优化 效率  存 主要来 自于 2个方 面 : 访存 联 合 和 共享 存 储 器 的使  用. 访存 联合 指如果 连续 的 1 条 线程访 问连续 的地  6 址空 间 , 其 首 地 址 是 6 i 整 数 倍 , 取 跨 度  且 4bt的 读

在初 始 聚类 、 量聚类 、 增 确定 特征点所 属词 等很  多 步骤 中都需要 计算 n个 1 8维特 征点 与 正个 1 8 2 2  维 中心点 的欧 氏距离 , 即 

3 i 则此 1 条 线程 读取 的 1 个 操 作 数 只需 要 1 2 t b, 6 6  
次访存 而非 1 6次. 利用 GP 片 内的共 享存 储器 是  U 另一个 有效手段 , C c e 与 ah 的原理 类似 , 享存 储器  共

√F—一   一 ; 厂——   ——  ——
其中, d为待求 欧 氏距 离 ,  c分 别 为特 征 点和 中  z和   心 点 的第 i 数据 . 维   由于本 文 中 每 点 特 征 维 数 高 达 1 8维 , 时  2 此 Fn a g等0  基 于 Sr cu eo  ry的优 化 方 法 变  tut r fAra  

可 以让 多次使 用 的数 据保存 在离计 算单元 最近 的地 
方 , 访 问 GP 设 备 内存 至 少 2 0个 时钟 周 期 的  与 U 0 延迟 相 比 , 共 享存 储 器 中取 操 作 数 一般 只 需要 1 从   个时钟 周期.  
3 )基 于 缩 减 的 优 化 . P 的 线 程 执 行 方 式 决  G U

得 完全不适 用. 方法 是将原 始数据 进行转 置存储 , 该  
每 次传进 每维度 的一 部 分 数据 进 入 共享 存 储 器 , 这  种优 化方法 仅能处 理低 维数据 , 高维 时 会 由于 G U P   多处 理器 上共享存 储 器 容 量 的 限制 导致 性 能 极低 .   本 文按照原 始点 的 自然顺 序将 维度 数据读 入共享 存 

定 了线 程之 间的通 信 只能 通 过共 享 存 储 器完 成 , 线 

程块 问线程 的通 信 只 能通 过 全 局存 储 器 完成 , 效  有 利用这 种通信结 构 可 以带 来 性 能 的提 升. 缩减 方 式 
是 这类 优化 的典 型 代 表 , 过 共 享存 储 器 或全 局 存  通 储器 , 大量线程 以缩减 的方 式实现 数据 累加 、 极值  求 等方法 , 执行 时间可 以从 0( ) n 降低 到 0(o ( ) . 1g n )  

储器 , 时优化 的重 点 是距 离 计 算方 法 和线 程 块 内  此 线程 数量 的分配 . 于两点 的距离计 算 , 对 首先 必须保 
证 每个维度 差值 的平 方 在 同一 时 刻 被计 算 , 不是  而 使 用 内循环 方式 ; 次 必须 保 证 维度 数 目的 中 间结  其 果 的 累加 方 式 高 效 , 也 正 是 C o等  基 于传 统  这 a
G U 和 图 形 AP 方 式 所 做 不 到 的 . P I  

4 拷 贝检 测 方 法 优 化 
4 1 天 然 并 行 方 法 访 存 的 优 化  . 

为保 证 高效 距 离计 算 的这 两 点要 求 , 为使线  也
程块 满 载 运行 , 可让 线 程 块在 同一 时 刻最 多计 算 4   个 数据 点 ( 因为 每 线 程 块 同 时 最 多 包 含 5 2个 线  1

使 用 高斯 核对 各 尺度 视 频 帧作卷 积 时 , 为生 成  高斯差分 金字塔 ( i ee c  f u s n o , df rn eo  si ,D G) 需  f Ga a 要 对连续 视频 帧 的不 同尺 度 卷积 变 换 后 , 进 行 帧  再

程 ) 使线程 块 内第 i , 条线 程计 算 ( 一 c) 结 果存     。
人共 享存储 器 , 由线 程块 内所 有线 程 对共 享 存储  再
器 内 的 最 多 4组 1 8维 数 据 进 行 流 式 缩 减 的 累 加  2

间减法 . o 中具 有本 地最 大 或最 小 亮度 的像 素点  DG 被认为 是候选特 征 点. 候选 特 征 点 的选 定 需要 在 当  
前 图像 和 邻近 尺 度 的 2幅图像 的 3 ×3区域 , 2  即 6

操 作.   图 2所 示 为本 文优 化 策 略 的线程 块示 意 图 , 图  中假 设 每个 点是 8维数 据 , 程块 内有  和 q2个  线  

邻 域上进 行最大/ 最小 值 比较 计 算. 于 这种 易并 行  对
的计算 , 注的主 要 问题 是 , 免无 法 访 存 联合 的 、 关 避  
不整 齐的 内存 读取 . 为解决 此 问题 , 文利用共 享存  本

点 , 是 中心 点 , 。  是每 个维度 差值 的平 方结 果  c z ~z
值. 进行 流式 缩减 累加操作 之后 , 2组 流式 缩 减 序列  的第 1 数 为累加 结 果 , 个 对其 求 平 方根 后 分 别得 到 
P 和 q与 c的 距 离 .  

储器一 次把需 要 的全 局存储 器数 据读 到片 内共 享存 

第 3期 

任 化 敏 , : P 加 速 的基 于增 量 式 聚类 的 视 频 拷 贝 检 测 方 法  等 G U

43 5 

图 2 特 征点 P和 q与 中心 点 c距 离 计 算 示 意 图    

4 4 增 量 聚 类 中 生 成 索 引 的 优 化  .

换后 的视频命 名 为 1 ~1  将 本 文方 法 在 C U 和    c 0. C P G U上 分别 运 行 , 一 在 C U 方 法 的有 效 性 、 P 逐 P   GP 与 C U 结果 的一 致性 、 法 核心 模块 在 GP   U P 方 U 上 的性 能 、 方法 可伸缩 性及 功耗 等 方面进 行实 验.   为 保 证实 验 的全 面性 , 文 采 用 2套 硬 件 平 台  本 进 行 实 验 : ) 有 2 6个 流 处 理 器 的 NVI I   1 具 1 DA Geo e  X 2 0+ GP 配 合 I tlC r2 D O fre GT   6 U n e oe  U    
E 2 0C U ( 频 2 6  8 0  P 主 .6 GHz ; ) 有 3 )2具 2个 流 处 理  

对 于增 量聚类 中不 属 于 已有 中心 点范 围 的特定  点, 需要 对其 进行 区分 和另 外存储 , 以在后期 对 这些  点重 新 聚类 , 涉 及 快 速 的索 引计 算. 验 证 明 , 这 实 实  际上仅有 极少 数 的点 需 要 另 外存 储 , 时需 要 一 个  此 索 引标记 位置 , 串行 的生 成 方式是 循环 比对 , 这种 方 

法 几乎 无 法 在 G U 上 有 效 实 现 , 以本 文 使 用 基  P 所
于前缀 和 的并 行检 索实 现 索引生 成.  

使 用第 43节 介绍 的距离 方 法判 断每 个 特征 点  .
是 否可归 为 已有类 , 并生 成 01序 列 , 于可 以归 类  - 对 的标 记 为 0 无 法 归 类 的 标 记 为 1 对 该 序 列 执 行  ; . Hii 等口 ls  提 出 的前缀 和 方法 , 到 前缀 和序 列. l 得 该  序 列 中每个元 素 的值 即是对 应位 置 的原始 序列 在 目  

器 的 NVI I   eo c  5 0 T GP 配合 P nim  D A G fre9 0 G   U et u Du l 2 4  P 主 频 16 a E 1 0C U(   .  GHz. 2个 平 台均为  )这 2   DR   D 2内存 . 文方 法 在 W id wsVi a操作  GB 本 no   s t 系统 、 sa S u i 2 0 Vi l t do 0 5和 2 1 本 的 C A 上进  u    .版 UD 行 代码 实 现.  
5 2 有 效 性 实 验  .

标序 列 中 的位 置 , 照 该位 置 索 引 可 直接 将 数 据 拷  按
贝至输 出序列 , 该方法 的时 间复杂度 由串行 时的O     () 降 为优 化 后 的 0(o (z) 本 文 直 接 调 用 C A  1g , . ) UD D t  aall r t e 函数 库实 现这部 分 的优化 . aaP rl   i i s e P mi v  

文 献 E ] 证 了 时序 和 空 间关 系具 有 同等 重要  7验
的作用 , 因此本 文 的 匹配 过 程 也将 时序 差 异 与 空 间  差 异赋 予相 同 的权 重. 阈值 设 为 o 3 , 将 . 0 如果 待 查 

询 的视 频 与数据 库 中的视 频 距 离 小 于 该 阈值 , 认  则

5 实验 结 果   
5 1 实 验 数 据 和 环 境  .

为匹配 , 即待查 询视 频为 拷 贝视频 . 当视 觉关 键词词  典 的容 量 K 一6 5时 , 于 普 通 K— a s聚 类 的拷  基 me n 贝检测 方法 能够 检测 出 2 , , , C 9 , 示该方    3 6 8 ,  表 e e c   C 法 能够 应 对 如 分 辨 率 变 换 和 轻 度 的 模 糊 等 全 局 攻  击 , 能应 对剪 切和 高光 等局部 攻击 . 也 但对 于严 重 的  模糊 的情况 , 其检 测效 果不 好 , 因为 严重 的模糊 大大 

本 文 从 MUS L — C   0 7 据 库 中 随 机 选  C EV D 20数 取了 1 0个 视频 ( 辨 率 3 2 8 , E 1编码 )  分 5 ×2 8 MP G一 ,

每个 截取 2  0 S片段作 为 基础数 据 , 名 为 1 ~l , 命   s O   S
之后 把 每个视 频用 P e ee 件 分别 施 加模 糊 、 rmir 软 分 

地 减少 了视 频 帧 中特 征 点 的数 目, 减 少 了许 多有  也 区分力 的信 息. 基于增 量 式 K— a s men 聚类 的拷 贝检  测 结果 比普 通 K— a s men 多检 出 了 4 , ,0c应 对    7 1 , c e

辨率 、 a ma 噪声 、 Gm 、 画中画 、 糊 & 高光 、 模 高光 & 翻 
录、 剪切 & 模糊 、 高光 & 剪 切 、 糊 & 噪 声变 换 , 模 变 

44 5 

计 算 机 辅 助设 计 与 图形 学 学 报 

第2 2卷 

攻 击 的能力也 更 好 . 普通 K— a s聚 类方 法 中 , me n 每 

本 文方 法 中采 用 的流式缩减 计算 的累加 次序也 与 串  

新 增一个 点 , 都将 聚 类 中心 修 改为 该 类包 含 的所 有 
点 的均值 , 换言 之 , 中每 个点 的作用 都 是 一样 的 ; 类  

行 方式 不 同 , 浮点数存 在舍 人误差 , 很难保 证 串行浮 
点 加法 和并行 浮点加 法 的结 果一致 性.  

在增 量式 K— a s me n 聚类 中, 增点 的作 用取 决 于该  新
类原 来包含 的特 征点 的个 数 , 原 来 包括 很 多点 的  对

虽然 在微 观 层 面 上 G U 与 C U 的 数 值 结果  P P
往 往不一 致 , 这种 不 一致 从 误差 评 估 的 角度 来看  但

类 , 增加 的点对 聚类 中心 的修 改是微小 的 , 如果  新 但
该类 已有 的点很少 , 增 加 的点 就 对新 的聚类 中心  新 起 了关 键 的作 用. 量 式 的 聚类 方 法有 利 于 突 出一  增

可 接受. 而 , 个 方法 每 步误 差 都 会产 生 累积 , 然 整 对 
最终 检测 结果是 否有影 响还需 在宏 观层面考 察.  
5 3 2 宏 观 层 面 结 果 一 致 性  ..

些具有 显著特 征但 是 数量 较 少 的点 的 作用 , 而这 种  特征点 在拷 贝检测 中发挥着 重要 的作用.  
5 3 G U 与 C U 结 果 一 致 性 实 验  .  P P

为检 测 方法 的数 值 误 差 是 否 会 对 检 测结 果 产 

生影 响 , 我们 对全 部 1 段 视频 和不 同的攻击类 型进  0
行 了考察 , 结果显 示 , U 与 C U 上 的拷 贝检 测 匹  GP P 配结 果完全 一致 , 测准 确 率 以及 检 测 召 回率 也完  检 全一致 . 表明在 本文 的实验 中 , P 与 C U 结果  这 G U P 数据数 值上 的误差 没 有 对最 终 匹 配结 果 产 生影 响.  

同一数值 算法 的串行 和并 行 实现计算 结果往 往  略有误 差 , 再考 虑 G U 与 C U 浮 点 计算 单元 硬 件  P P 实现机 制不 同 , 以本文 关 心 2个 层 面 的结 果 一 致  所

性: 第一 是 微 观层 面 , G U 与 C U 每 个 方 法 结  即 P P
果 是否 一致 ; 二 是 宏 观 层 面 , 面对 多种 攻 击类  第 即 型 , P 与 C U最 终结果 是否一 致. G U P  
5 3 1 微 观 层 面 结 果 一 致 性  ..

更进一 步 的结 论还 有赖 于更大数 据量 的实验 和理论 
推导.  
5 4 G U 性 能 实 验 结 果  .  P

为 了对 本 文方 法 进行 更具 一 般性 的性 能评 价 ,   我们选择 整 个 方 法 中具 典 型 意 义 的 方 法 步 进 行 实  验. 对数 据集 中数据点 数进行 了截 取 , 以整 数个点进 

本文 方法 中大量特 征点欧 氏距离计 算和 卷积计 
算属 于浮 点数计算 , 可能 发生 G U 与 C U 的 浮  有 P P

点 结果不 一致 的现象 . 对 实 验结 果 的分 析 和 统计  经
发 现 , 3个模块 中发 现 了数据 结果不 一致 现象 : 在   1 )帧解码 结果不 一致. 视频 的解码 结果 是若  对 干视 频 帧图片 , 然不存 在 肉眼可察觉 的差异 , 虽 但逐 

行 实验 , 并对 每个测试 项做 1 0 循环取平 均值 . 0次  
1 )视频 解码 . 由于本 文 使 用 GP 上 的硬 件 单  U 元 进行视 频解码 , 以速度 比软件 解码快得 多. 验  所 实

显 示 , U 的解 码每 帧平 均仅 耗 费 06 , C U GP .  而 P   ms
的 软 件 解 码 平 均 速 度 是 2 .  , 慢 于 G U 的 硬  15 ms远 P

像 素数值进 行 比对 会 发 现二 者 有很 小 的差值 . 这种  不一 致 现象 可能是 由于 G U 上 的硬件 视频 解 码单  P 元在 追求解码 速度 的 同时舍 弃 了部 分 精度 , 有 可  也 能来 源 于我们 的 软件解 码 方法 与 G U 的硬 件 方法  P
存在 实现方式 上 的差 异.  

件 解码方 式.  

2 )原子加 . 验 显 示 , 于 1 24 0个 数 据 的  实 对 0 0 原 子加法 , 本文使 用共 享 存 储器 配 合原 子 加 的方法  与直 接使 用 GP 的硬 件原 子加 的方 法 的执行 速度  U
分别 是 0 2  .6 ms和 12  , 者 比后 者 的加 速 约  .8 ms 前
5倍 .  

2 I T特 征点 个数 不一致 、 )S F 点数 据 总体一 致.  
用完 全一致 的视 频 帧作 为 输 入 , 验 显示 , 全 部  实 从
1 0段 视 频 提 取 的 SF 特 征 点 , P 与 G U 的 结  IT C U P

3 I T特 征 提 取. 3所 示 为对 1帧 视 频提  )SF 图 取 6 6 SF 9 个 I T特征 速度 比较 , 以看 出 GP 方法  可 U 对 于 S F 的 4个 主 要 步 骤 为 D G 生 成 、 征 点  IT o 特 定位 、 定 主方 向和 特 征 向量 生成 , 取 速度 分 别  选 提
口 CP U  口 GP U 

果在 数量上 的差值 约 百分 之 一 , 同一特 征 点 的部 分  特征 向量数 值 存 在 约 0 5 o 的误 差 . 们 推 测  . ×1  我
误差 的主要来 源是单 精度浮 点数 的计算最 高精 确度  有限 和舍人方 式 的不 同.  

3 )K— a s men 聚类 的 中心 点数据 总体 一致 . 完  用 全一致 的视频 帧作 为输 入 , 验显 示 , 全 部 1 实 对 0段 
视 频 , U 与 C U 的聚类 结 果 中 心点 的每 维 度 数  GP P
-’ _’ 1 

值均 有 约 0 5 0 的数 值误 差 , 中心 点 位 置 总  . ×1  但
体 一致 . 这些误 差一 方 面可 能 来 自于聚类 求 取 和 比   较 欧 氏距 离 的浮点乘 加 计 算 , 另一 方 面 可能 来 自于 
D G生成  特 征点定位 选定主 方 向 特征 向量生成  o

图 3 S F 特 征 提 取 速度 比较 ( 坐 标 为对 数 刻 度 )   IT 纵  

第 3 期 

任 化 敏 , : U 加 速 的 基 于 增 量 式 聚 类 的 视 频 拷 贝 检 测 方 法  等 GP

45 5 

提 高约 8倍 、 l 、 6倍 和 2 3倍 1 6倍 , 体 性能 提 高 约  整
2 2倍.   虽 然速 度 得 到 了提 升 , 这个 提 升 倍 数远 没 有  但 达 到我们 预期 的加 速 比 , 原 因是 我 们 的视 频 分 辨  其

流 处 理 器 数 目比值 基 本 一 致 . 6所 示 为 G fre 图 eo c 
G  6 +在不 同运行频率 下 的执行 时 间 , 中模 式  TX 2 0 图 l ~4的流 处 理器 和 显示 内存频 率 分 别 为 1 9    6 2 MHz  
和 8 0 Hz 1 9   Hz和 11 7M Hz 1 0   Hz和  3  M ,  6 2 M  0   ,  3 4 M

率 较低 , 帧 产 生 的 SF 特 征 较 少 , 能 让 GP 每 IT 没 U 
满 负荷 运行 , 以加速 比较低 . 所   4 )K~ a s me n 聚类 . 4所 示 为 GP 方 法 相 对  图 U

1 0  Hz 1 0  Hz和 11 7M Hz 可 以 看 出 ,   7 1 M ,  4M 5  0  . 随 

着流 处理 器频 率 的提升 , 执行 时 间相应 减少 , 二者 几  乎 成 正 比关 系 , 但显 示 内存 频 率 改 变对 执 行 速 度 几 
乎 无影 响.  

于 C U 的速度 提高 比较. 验 显示 , 文 基 于流 式  P 实 本 缩 减 的 G U 实 现 方 法 在 聚类 5 0 P 1 0个 数 据 点 时 , 2  
相 比 C U方法 达到 7 P 3倍 的 加 速 比 , GP 的原  比 U 始 实现也 有 近 6倍 的加 速 比. 验 中也 发 现 , 实 在数 据 

量 达到 1 2 0 0  0之后 , 速 比有 轻 微 的下 降 , 4 加 这可 能 
是 由于 线程 块 内的线程 数 目增加 带来 了每 线程 可分  配 资源 的减少 , 而影 响 了 GP 方 法性 能 的提高 . 从 U  
1 0  0   0 00 0
l  0   00 0 10 0  0  10 0 
—  一  

。 P Gu 始实 Gu   现一 CU。 P原 现a P缩蟹  
—— 一 —   一 一  
|   一

1 X 据点  0 数
l  
一  

图 6 GP 在 不 同 运行 频 率 下 执 行 时 间    U

一  

通 过 以上 2个 项 实验 可 以认 为 , 文方 法 在 流  本

1  0 1   8   1  6 3  2

f L      —
6   1 8 2 6 5 2 0 42 4   6   4 2   5   1  1 2   0 8 25 0

处 理器 数 目和运 行 频 率 方 面具 备 稳 定 的 可扩 展 性 ,   易于 扩展 到未来 更 高规格 的 GP 上 . U  
5 6 实 验 结 果 对 比 分 析  .

1 一×数据 点  0。

图 4 K— a s 度 比较 ( 坐标 为对 数 刻 度 )   me n 速 纵  

系统各 部 分 方 法 在 C U 和 GP 上 的执 行 时  P U 间分别 如 图 7   a和 7   b所 示 , 以 看 出 , 量 聚类 与  可 增 生 成视 觉关 键词 词 频 向量 占用 的时 间 比重 比较 大.  

5 )前缀 和 法生 成 索 引. 验 显示 , 于 12 0  实 对 0  0 4

个数据点 , 使用前缀和法生成 特征点索 引需 要 28 , .    ms 而 GP 的原始循 环方 式 需要 1 .  , 者 比后 者  U 23 ms 前 快 4倍 以上.  
5 5 可 扩 展 性 实 验  .

以5   S为例 , C U 上 分别 为 2 2 .  在 P 288 S和 1 5 . , 995   S 在 GP 上 执行 时 间分别 为 3 .  和 2 . . 们在  U 05S 68 我 S
GP 上 的基 I 增量式 聚类 的视频 拷 贝检测 方法整 体  U 于
5  O
— —  

除 比较 了本 文 方 法 的 基 础 性 能 , 们 也 以 K— 我  
∞  

me n 聚 类为 例进 行 了可 扩 展性 实 验. 验 中使 用  as 实 Geoe  X 2 0 fre GT  6 十和 Geo c 5 0 fre9 0 GT分别 执行 相 

壶4 0  

量3 0  
簧2 0  
1  0 O  

二— 一一  —     

同 的计 算 , 比较执 行 时 间 ; 使 用 GP 频率 修 改 工  再 U
具 改 变 Geo c  freGTX 2 0   6 +的流 处理 器 频 率和 显示  设 备 内存执 行频 率 , 并进行 比较.   图 5所 示 为 G freGT   6 十 与 Geo c  eo e  X 2 O fre 9 0 G 的执行 时 间 比值 . 以看 出 , 比值在 4   50 T 可 该 ~7 之 间随数 据量 增 大而 不 断 增 加 , 与 2块 G U 的  且 P

廿  
毫  

渗 _    荫

1   2S 3S 4s 5S 6 S 7S 8s 9S 1      S                           0S

视频序 号 
a C U上的 时间分配    P

 ̄   /1

8  
7   6  
. 



 

厘 

/ 
/  

留 

5   4   3  
2  



 
视频 序号 

8  

1  6

3  2

6  4

18 2 

26 5 

5 2 10 4 1   2  

b P  G U上 的时 间分配 

1一x 0  数据 点 

注: -解帧 ; 。增量 聚类 ; SF 特 征 点 ; 。 IT 。视觉关 键词词 频 向量 

图 5 G 2 0 5 0 T 的 执 行 时 间 比值    TX 6 +9 0 G

图 7 系 统 各 部 分 方 法 在 C U 和 GP 上 的 时 间分 配    P U

46 5 

计 算 机 辅 助设 计 与 图形 学 学 报 

第 2 卷  2

所需 要 的时间 比 C U 提 高 了约 5 P 4倍 至 6 倍 . 3  

a g rt m  a e   n l b l  fbe a i r f r v d o c p   e e t n l o ih b s d o  a e so   h vo  o   i e   o y d t c i   o

[ ] / rceig  fte 4h An ulAC Itr ainl c / oedn s o  h 1 t  n a P   M  nen t a o  

6 结   

论 

Co f r n e o   u tme i n e e c   n M li d a,Sa t   r a a,2 0 n a Ba b r 0 6:8 5 8 4 3- 4 

[] Re   M 7  n H 

,Li    ,Z a g D  ,e  1 nSX h n  M ta .Vi u lwo d   a e   s a  r s b s d

saitmp rl eu nemac igi v e oydtci c] pt e oa sq e c  thn    i oc p eet n[   o   n d o

本 文在 文 献 [ ] 作 的基 础 上 提 出 了 完 全 在  7工
GP 上 执 行 的 基 于 增 量 式 聚 类 的 视 频 拷 贝 检 测 方  U

/ rceig f E EItrai aC neec nMut da / oedn so  E  nen t n l o frn e   lme i P I o   o i  
a d Ex o n   p ,Ne Yo k,2 0 w  r 0 9:1 8 - 3 5 3 2 1 8 

法, 该方法 不仅 在有 效性 上 高 于基 于 普通 聚类 的拷 
贝 检 测 方 法 , 且 可 以 有 效 地 弥 补 现 有 聚 类 方 法 无  而

[] W 8 

u Enh a S a e o   h   r  n   u u e c a lng   n g n r l   u . t t  f t e a t a d f t r   h l e eo   e e a  

p ro e o uaino  U [] J un l f ot r , 04  up s  mp tt  nGP J . o ra o  f e 20 , c o   S wa
1 ( 0 5 1 ):1 9 -  0 ( n Ch n s ) 4 3 l 4 i  i e e  5

法 实时更 新数 据 库 的 问题 . 外 , 文 方 法 完 全 在  另 本 GP 上执行 , U 无需 与 C U 数据交 互 , 化 了高 维数  P 优

( 恩 华 .图形 处 理 器 用 于 通 用 计 算 的 技 术 、 状 及 其 挑 战  吴 现

[] J.软件 学 报 ,2 0 ,1 ( 0 :1 9 —  4  0 4 5 1 ) 4 3 10 ) 5 [ ] L we  G. Obe t eo nt n r m o a c l iv r n  9  o  D jc  rc g i o  fo  lc l ae n a i t i  s   a

据 的增量 聚类性 能 以及 其他 组 成部 分 , 拷 贝 检测  将 的速度整体提 高最 多 6 倍 , 3 且具 备 良好的可扩展性.  
在实现 过程 中我们也 发现 , P 在浮 点精 度上  G U 存在 与 C U 结 果 不 一 致 的 问 题 , 进 一 步 的实 验  P 但
结 果 表 明 , 种 层 面 的 精 度 问 题 对 本 文 最 终 结 果  这 无 影 响 ; 时 , 图 形 AP 同 与 I相 比 , 于 C 的 C A  基 UD

faue c /rceig fteItrai a C nee c n etrs[ ]/ oedn so h nen t n l o frneo  P o  
Co p t r V ii n, K e k r m u e   so r y a, 1 9 9 9, 2:1 5   1 0

b  [ O Be k rB,Ce e M I ] r e 

,I me      s tZ Y. Ve y—a g   c l n r me t l r l r e s a e i c e n a 

c seigJ ] i e t i e t ies y 2 0  l tr  R .Bl n:Bl n  v ri , 0 7 u n k k Un t
o [ I Ha   1] F, L   E, Ch n Y , e  a . P r l I a i n a d i   e    t    a a l i t0   n   ez

编程 模型难度 降低 了很 多 , 但方 法调优 十分费 时 , 且 
需要 小心 谨 慎 , U 代 码 自动 优 化 编译 器 还 有 待  GP
提高 .  

caatr ain f IT n mut cr sse h rcei t  o SF  o  z o l  oe ytms [ ] / i c /  
Pr c e i gs o   EEE  n e na i n l Sy o i m  n o edn   fI I t r to a  mp su o  W o k o d r la  
Ch r c e ia i n,S a te a a t rz t o e t l ,2 08 0 :1 — 3 42 

[ 2  y nn 1 3 He ma  

S, M a l r K , S   l   e   mo i  A, e  n . l c   t £  

SF I T 

i l me t t  a d mp e n a i on n  op i z to  f  ge e a — u p s  GPU  t mi a i n or n rlp r o e

参 考文献 ( eee cs : R frn e)  
n   oy A ta1 d o c p   ee to   [ ] Ia ToJ 1   w    ,Che I,J l  ,e  . Vie   o y d tcin:a

[ ] / rce ig o  h  5h nen t n l o frn e i c / oedn s fte 1 t Itrai a P o  C nee c n  
Ce t a Eu op  o  Co nrl r e n mp t r u e  Gr p i s Viu l a i n n   a hc , s a i t  a d z o
Co p t r V ii n, P z n, 2 0 m u e   so le 0 7:3 7 3 2 1 -2 

cmprt e td [ ] /Po edn s f te 6h A o aai  su y c v /rceig o  h  t  CM 
I e n to a Co f r n e n ma e a d Vi e   Re re a , nt r a i n 1 n e e c  o  I g   n   do t iv l 
Am s e d m ,2 0 tr a 0 7: 3 1 3 8 7— 7 

ot rv n R. GPU — o s e   n i e i ge ma c i g b o t d o l   ma   n thn   [ 3  a i   .Ke i e   1 ] Ch r A

E ] / rceig  fte 9h Itrain lC nee c  n C / oedn s o h 1t nen t a o frne o  P o  
Pa t r   c g ii n,T a p t e n Re o n to m a,2 0 0 8: 1 4 - 

n f  ti  Z o a  oora ay i  E ] S nc e   ,BieaX ,ViraJ,酣 & . L c lc l   n lss 2  a h zJM
f r s e ebr a   e e to   p le   o t   o o   c n   e k d t c i n a p i d t   v c mme ca sr c g iin r i l e o n to    

c en JB. meme h d  o  lsiiai   n   n lss o   [ 4 M a Qu e    So   t o sfr ca sfc t n a d a ay i 1]

o  lvr t  bevt n [ ] / rce ig o  h 5h fmut ai e o srai s c / o edn s ft e t  i a o P
Be k ly r e e   S mp su y o i m  o   M a h ma ia  St ts is a d n t e tc l a itc   n   Pr ba i t o b l y,B r e e i e k ly,1 6 9 7:2 1 2   8 — 97

[ ] /P oedn s fte r Itrain l o frne n C / rceig o  h 3d nen t a o  C nee c o 
Vi u l n o ma in n  I f r to  S s e s a I f r t  a d n o ma i n y t ms, Am s e d m , o tr a  
19   9: 2 7 2 4 9 3— 4 

n o  Ao ig. Fat  ̄use ig f a a te ms yn s l trn  o d t sra   [  Ca Fe g, Zh u 1] o 5
Fe t r  b s d n x n  f r a u e a e  i de i g o  me i  da

le [ ] Ha a u   , Bo l R . 3  mp p r A

uigga hc rcsos J .J un l fS f r,20 ,1  s  rp i poesr [] o ra o ot e 0 7 8 n s   wa
( ):2 1 0 ( n Ch n s ) 2 9 -3 2 i   i e e 

t cig[ ]/Po edn so E E Itrain l o frne r kn c / rce i   fI E  nent a C nee c  a g o  
o  ut n M li d a a d Ex o, w  r   t me i  n   p Ne Yo k Ciy,2 0 0 0:1 0 — 7 2 79 1 1  u  o l  mp rs n o   e u n e [ ] Ha a u   ,Hy n K H ,B le R.Co a io   f s q e c   4  mp p r A

( 曹

锋, 周傲 英 .基 于 图 形 处理 器 的数 据 流快 速 聚类 [] J.软 

件 学 报 ,2 0 ,1 ( ) 2 卜3 2  07 82 : 9 0) [ 6 Ch   B y r ,M e g , e  1 A p ro ma c su y o  1] eS, o e M n  J ta . e fr n e t d   f
g n r l p r o e a p ia i n   o   g a h c  p o e s r  u i g e e a— u p s  p l t s n c o r p i s r c s o s sn  

macig eh iu s fr v e  cp   dtcin [ ] / thn  tcnq e  o  i o o y eet d o c /  
P o e d n s o   n e e c   n S o a e a d Re re a  o   e i  r c e i g   fCo f r n e o   t r g   n   t iv lf r M d a

Daa a e ,S nJ s ,2 0 tb ss a   o e 0 2:l 4 2   9 — O1 eio  is n O a u e sa i ia  e re a  s I ]J l  ,Frlc tC, Buso   . Fe t r  t t tc1r tiv l s  oy A

C UDA [] o r a o  aallad Dsr ue  o uig  J .Ju nl fP rl   n  itb tdC mp t ,   e i n
20 0 8,6 ( O 8 1 ):1 7 - 3 0 3 0 1 8 
u K    [7  n     I] Fa g W B,La   K, Lu M ,e  1 P r l l d t   n n   n ta . a a l   a a mi i g o   e

apidt o tn  ae o yie ti t n[ ]/Po edn s p l  ocn etbsdcp dnic i c /rce ig  e fao
o   t e I t r a i n l Co f r n e o   I g   Pr c s i g, f h   n e n t a  o n e e c  n ma e o esn  
S n a o e,2 0 ig p r 0 4: 6 — 8   81 6 4

ga hc rcsos R] eig rp i poesr [ .B in :Mi oot hn ,20  s j c sf C ia 08 r  
[8  ls 1 ] Hii l W D, Sel  L. Daa aall loi ms [] te  G e t p rl  ag r h e t J.  
Co mmu i a i n   f t e ACM ,1 8 n c to s o   h     6,29 1 ):l 7 - 1 3 9 (2 10 1 8 

[ ] L w ToJ uso  Go e Bu e V, t 1 6 a    ,B i nO, ut rnt ea .Ro ut oig s       bsvt     n


相关文档

基于GPU的快速图像拷贝检测
一种快速聚类算法的GPU加速
基于GPU加速的多物体碰撞检测方法
基于视频指纹的快速视频拷贝检测方法
基于内容的视频拷贝检测方法研究
一种快速有效的网络视频拷贝检测方法
GPU加速的自适应仿射传播聚类方法
基于GPU加速视频抠像技术
主设备与GPU的快速数据拷贝
基于通用可编程GPU的视频编解码器——架构、算法与实现
电脑版