论文研究-一种KNN算法的可重构硬件加速器设计.pdf

所需积分/C币:10 2019-07-22 23:14:53 1.19MB .PDF
14
收藏 收藏
举报

设计并实现了一种可快速运算基于哈尔小波变换的KNN(K nearest neighbors)算法且具备可重构能力的硬件结构。该硬件结构通过增减哈尔小波变换组件即可适应不同维度样本的哈尔小波变换;对同样维度样本的计算则可以通过调整并行度满足对逻辑资源和处理时间的不同需求,克服了现有软件KNN计算速度慢、硬件实现的KNN不够灵活的缺陷。通过在Xilinx VC707 FPGA开发板上实现该硬件结构,实验结果展示了不同维度及并行度下算法实现在逻辑资源耗费及运算时间方面的变化。此外,将该硬件结构作为一种高质量轮廓提取算法硬件加速器的纹理分类模块时,在保持计算准确度的情况下获得了远高于软件运行的速度。
3630· 计算机应用研究 第31卷 组成。对于n维向量,所需 Hwt level模块数量为2--<N≤2″人系统。样本首先经过小波变换,进入待分类样本缓冲池,然 个。例如,1024维的样木需要10个 Hwt level模块来完成哈尔后KICK_OUT和PDS模块同时启动对待分类样木进行K近邻 小波的完全分解ε该哽件结枃通过增减和组合Iw_leve模块搜索,满足当前待分类样本K近邻条件的将会进入SORT模 可方便地处理不同维度的向量。第一层的输入是原始样本,此块。每次剔除最远的一个近邻,并重新排序。最后统计未知样 后卜一层的近似系数作为下一层的输入,细节系数直接输出存本所属类,并算出当前D,将SORT模块初始化成K个最大距 储。控制信号采用流水模式,由上一层负责驱动下一层,如D_离值。当整个训练样本空间搜索完毕,输出待分类样本所属类 en_in为数据冇效信号、LD_in为样木结尾信号,控制不满2的别,开始下一个待分类样本搜索。 CONTROL模块是整个系统 n次幂长度的样本做补零操作。最后一层Iwt_ level的LD_0的控制模块。其中, ADDRESS_GEN模块是 lable ram和 train 信号即是整个样本完全哈尔小波分解后的输出。 ing_ sample RaM地址控制模块,根据并行度、样本维度和系数 Hwt level 判定信息计算地址。它还有一个寄存器组,包含样本维度、当 [Lwt level 前最大近邻距离、系统重置等系统控制信息。每一个待分类样 -PA 木搜索结束时控制系统将重置 Hwt level CONTROL 一Di---量后数据入 Hwl evel KICK OUT 节系散输日 最后据抢日 最后五似系 system bua 图2哈尔小波变换硬件结构 BUFFER H PDS SORT 2)部分距离搜索的硬件实现本文设计了如图3所示的 图4基于哈尔小波变换的KNN硬件框图 硬件结构来满足不同并行庋的重构需求,距离计算模块由多个 维度计算模块构成。例如,当并行度为P时,K、Y到x+p、3实验结果 Y;组模块会同时进行计算。需要扩展并行度时只需增加相 应的计算模块,増加样木输出位宽,让并行计算的数据同时从 本章实验所采用的FPGA开发板为Xinx公司提供的 训练样本RM输出;同时更新图4中 CONTROL模块的并行VC707,含有一块XC7VX4852Hl76C作为HGA主芯 度值,模块会计算出地址增量值、适应位宽改变时RAM地址片,系统工作频率设定为10Hz 的定位。每个待分类样本进行K近邻搜索时,训练样本数据3.1KN硬件的可重构结果 将不断地被输入PDS模块进行数据切分与待分类样本的部分 表1列出了不同的本文设计的基于哈尔小波的KNN硬件 距离计算。当与每个已训练样木的距离计算结束时,距离累加结构的重构结果。其屮13维64个样本的数据是Pb纹理分类 崙会被清空,为下一个训练样本距离的累加做好准备。如果细的数据,k=1,未知样木数为15440164维的556个样木数据 节系数和近似系数判定生效,或者部分距离超出时,相应的训是Sur算法的特征向量匹配数据,未知样本是550个,k=2。 练样本RAM地址也会跳到下一个样本处。 Clear信号会一直从表1可看出,本文设计的结构通过硬件的重构可以满足不同 保持,直到下一个正确有效的数据到达时才开始累加。当已训应用对处理时间和资源消耗的特定需求。 练样木距高值没有被中断而完成全部距离值累加时,sort信号 表1不同维度/并行度的KNN硬件实现结果 控制当前训练样本的亞离值输入图4中SRT模块进行K近 数量/维度 block /并行度 寄存器杳找表 邻排序,同时统计训练样本类别。地址计算、 clear信号、sort信 RAM 来法器时间/s 号都在 CONTROL模块中产牛。通过该方法可以实现计算并 0.00283 行度的伸缩,以适应不同的应用需求。 64/13/2 876 254( 0.00512 556/64/16 743 3749 160.00552 X Y 可用资源60720030360010 2800 3.2KNN硬件在Pb算法中的应用 为了验证本文所设计硬件的可用性,本节将KNN硬件作 为P轮廓提取算法中的图像纹理分类模块,并在计算速度和 准确度方面与软件方式进行∫对比。实验所用CPU是tel CPL上740@2.8GHz,HGA工作频率为10UMHz。所处理图 sort 像选自伯克利计算机视觉标准图片测试集5,大小为321× compare next sample→ 481。样本维度13维,训练样本空间是64个,PDS模块是每次 图3部分距离搜索硬件结构 计算8个维度。 如图5所示,在处理相同计算时,硬件方式的图像纹理分类 2.3系统整体硬件结构 模块处理时间是每帧0.00154s,相对软件方式的0.943s,计算 图4是基于哈尔小波变换的KNN算法的整体硬件框图。速度提高了612倍,可以更好地满足应用的实时处理需求。 如图4所示,训练样本和对应的类别标签通常会提前离线处理 图6、7分别展小了Pb算法中哈尔小波变换模块的仿真结 并存储到相应位置。待分类样本则从接口 system bus实吋输果和纹理分类的仿真结果。 Element输入的是纹珥特征向量, 第12期 柴志管,等:一种KNN算法的可重构硬件加速器设计 3631 即待分类样本, Detail coe输出的是细节系数, Approx_coe输出硬件设计屮子模块的接口兼容性、重构的易操作性等方面继续 的是近似系数, classfication是纹理分类结果输出。通过仿真验深入矸究,为KNN算法在不同实际系统中的应用提供技术 证了本文所设计的硬件结构在逻辑上是正确的。 支持。 参考文献 0.8 [1 XIE Qiao-bing, LASZLO C A, WARD R K. Vector quantization 0.6 technique for nonparametric classifier design[J]. IEEE Trans an Pattern Analysis and Machine Intelligence, 1993, 15(12): 1326 0.2 1330 CPU FPGAx100 [2 LI Juan. TKNN: an improved KNn algorithm based on tree structure 时间/0.9430.154 L C//Proc of the 7th International Conference on Computational In- 图5软、硬件计算时问比较 telligence and Security. Washington DC: IEEE Computer Society 2011:1390-1394 [3]刘艳,郝忠孝.基于Δ-me的自底向上的深度递归KNN查询算法 P Elene s) B石 [J.计算机应用研究,2011,28(8):2889-289 Un renard [4 MCNAMES J. A fast nearest-neighbor algorithm based on a pI axis search tree[J. IEEE Trans on Pattern Analysis and Ma hine Intelli [5 PAN JS, LU ZM, SUN SH. Fast codeword search algorithm for im- rain15倒 age coding based on mean-variance pyramids of codewords[ J]. Elec 图6纹理特征向量的小波变换仿真 tronics Letters 2000 36(3): 210-211 6〗乔玉龙,浴正祥,孙圣和一种改进的快速K-近邻分类算法[J tart vector2 电子学报,2005,336):1146-1149 [7 HWANG W J, CHEN B Y, JENG S S, A fast vector quantization en- 多 classticatiDl 0c00 coding method using wavelet transform[J. Pattern Recognition Te classfication_e Letters,1997,18(1):73-76. [8 SCHUMACHER T, MEICHE R, KAUFMAN\ P, et aL. A hardware 图7Pb轮廓提取时的纹理分类仿真结果 accelerator for hth nearest neighbor thinning[ C]//Proc of Intern 图8是Pb中纹理分类的结果。原图计算出的纹理特征向 tional Conferenee on Engincering of Reconfigurable Systems and Algo 量作为输入进入KNN分类运算,经过搜索计算,将所有的像素 rithms.2008:245-251 点分成64类。图8(b)是软件计算结果,(c)是硬件计算结果。「9 YEH YJ,LHY, HWANG WJ,ctal. PCA implementation of 根据结果对比,说明分类结果没有差别,证明了本文所设计硬 knn classifier baset on wavelet transform and partial dislance search 件结构的可用性。 [Cl//Proe of the 15 th Scandinavian Conference on Image Analysis. 1O LI Hui-ya, YEH Y, HWANG WJ. Fast KNn classification based on snfieore CPU and reconfigurable harrlware J]. Intelligent Auto mation Soft Computing, 2011, 17(4): 431-446 L 11 MARTIN D R, FOWLKES CC, MALIK J. Leaning to detect natural image boundaries using local brightness, color, and texture cues[ J I IEEE Trans on Pattern Analysis and Machine Intelligence 2004,26(5):530-549 [12 QIAO Yu-long, LU Zhe-ming, PAN J S, et al. Fast K-nearest neigh- bor search al gorithm based on pyramid strueture of wavelet transform [J. Digital Signal Pro cessing,2010,20(3):837-845. (a)原图 (b软件计算结果(c)硬件计算结果 [13 PAN S, QIAO Yu-long, SUN Sheng-he. A fast K-nearest neighbors 图8软、硬件分类结果比较 gorithm[ J. IEICE Trans on Fundamentals of E- 4结束语 lectronics, Communications and Computer Sciences, 2004, 87 (4):961-963 本文针对日前KN算法存在的软件方式计算速度慢、硬14itx7 FPGA VC707 evaluation kitE0L.2012-06-08.l 件方式不够灵活的不足,设计并实现了一种可快速运算基于哈 tp: //china. xilinx. com/publications/prod_ mktg/VC707-Kit-Produ I-B 尔小波变换的KNN算法且具备可重构能力的硬件结构。从实 15 Berkeley segmentation and boundary detection benchmark and dataset 验结果可知,该哽件结构可以满足不同维度及不同并行度的计 [eb/Ol-.(2003).http://www.cs.berkeleyedu/projects/vision/ 算需求,支持用户在资源消耗和计算时间之间更方便地进行平 grouping/segbench 衡。同吋,该结构相对(P可获得较好的计算加速比并能保[16]吕成戍,王维国,丁永健基于KNVM的混合协同过滤推荐算 持计算结果的准确度。由丁KNN应用厂泛,下一步将在KNN 法[冂.计算杌应用研究,2012,29(5):1707-1709

...展开详情
试读 4P 论文研究-一种KNN算法的可重构硬件加速器设计.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-一种KNN算法的可重构硬件加速器设计.pdf 10积分/C币 立即下载
1/4
论文研究-一种KNN算法的可重构硬件加速器设计.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载 >