基于最小二乘的椭圆拟合及其FPGA实现
Ellipse fitting algorithm of least square and FPGA implementation
曾垣燊 1吕勇 1刘力双 1夏润秋1
作者信息
- 1. 北京信息科技大学仪器科学与光电工程学院,北京 100192
- 折叠
摘要
针对现有的基于FPGA平台实现的最小二乘椭圆拟合算法中线性方程求解输出时延较大的问题,采用Cholesky分解法解线性方程,并对Cholesky分解中的平方根求解,运用单向旋转、合并迭代、迭代次数可调等手段,提出了一种基于CORDIC算法的迭代自适应的平方根求解结构.实验结果表明,改进的平方根求解算法对缩短Cholesky分解输出时延有良好的效果,Cholesky分解在FPGA平台相较于现有的LDLT分解法实现63.26％的速度提升;椭圆拟合算法在保证输出绝对误差小于0.1 pixel的情况下,FPGA平台相对于计算机软件实现了 1 000倍以上的速度提升,适合实时性要求较高的应用场合.
Abstract
In view of the unsatisfactory time-consuming performance of linear equation solution in the existing least squares ellipse fitting algorithm implemented on field programmable gate array(FPGA)platform,the Cholesky decomposition algorithm was used to solve the linear equation,and an iterative adaptive square root solution structure based on Coordinate Rotation Digital Computer(CORDIC)algorithm was proposed by using unidirectional rotation,merging iteration,and adaptive adjustable iteration times to solve the square root operation in Cholesky decomposition.The experimental results show that the improved square root algorithm has a good effect on shortening the output latency of Cholesky decomposition,and Cholesky decomposition achieves 63.26％improvement over the existing LDLT decom-position algorithm on FPGA platform.Under the condition that the absolute error of ellipse fitting algorithm is less than 0.1 pixel,the computer speed can be improves by more than 1 000 times based on FPGA,so it is suitable for applica-tions with high real-time requirements.
关键词
最小二乘/椭圆拟合/Cholesky分解/CORDIC/FPGAKey words
least square method/ellipse fitting/Cholesky decomposition/CORDIC/FPGA引用本文复制引用
基金项目
装备预研重点实验室基金(202105509)
出版年
2024
NETL
NSTL
万方数据