基于最小二乘的椭圆拟合及其FPGA实现  

Ellipse fitting algorithm of least square and FPGA implementation

作　　者：曾垣燊 吕勇[1] 刘力双[1] 夏润秋 ZENG Yuanshen;LYU Yong;LIU Lishuang;XIA Runqiu(School of Instrument Science and Opto-electronic Engineering,Beijing Information Science and Technology University,Beijing 100192,China)

机构地区：[1]北京信息科技大学仪器科学与光电工程学院,北京100192

出　　处：《激光杂志》2024年第2期85-90,共6页Laser Journal

基　　金：装备预研重点实验室基金(No.202105509)。

摘　　要：针对现有的基于FPGA平台实现的最小二乘椭圆拟合算法中线性方程求解输出时延较大的问题,采用Cholesky分解法解线性方程,并对Cholesky分解中的平方根求解,运用单向旋转、合并迭代、迭代次数可调等手段,提出了一种基于CORDIC算法的迭代自适应的平方根求解结构。实验结果表明,改进的平方根求解算法对缩短Cholesky分解输出时延有良好的效果,Cholesky分解在FPGA平台相较于现有的LDLT分解法实现63.26%的速度提升;椭圆拟合算法在保证输出绝对误差小于0.1 pixel的情况下,FPGA平台相对于计算机软件实现了1000倍以上的速度提升,适合实时性要求较高的应用场合。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 decomposition algorithm on FPGA platform.Under the condition that the absolute error of ellipse fitting algorithm is less than 0.1pixel,the computer speed can be improves by more than 1000 times based on FPGA,so it is suitable for applications with high real-time requirements.

关 键 词：最小二乘 椭圆拟合 CHOLESKY分解 CORDIC FPGA 

分 类 号：TN791[电子电信—电路与系统]