Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics

Analysis and solution of complexity of basis function in ISAF reconstruction algorithm


ISAF reconstruction algorithm is used for reconstructing the three-dimensional structures of molecules. Its accuracy is better than that of traditional Fourier-Bessel reconstruction algorithm. But its basis function is so complex that lower its running speed particularly, which has affected the application of this method seriously. Therefore, it is very important to reduce the complexity of basis functions. By analyzing the complexity of the basis function, this paper proposed a solution. Firstly, the natural logarithm method is used for solving the large number computation problem in the course of generating combination coefficients. Secondly, a two-level index is built for all combination coefficients in memory to improve the addressing-speed. In addition, according to the locality principle during accessing memory, the combination coefficients that may be used in the near future are transferred into cache memory to reduce the number of accessing memory. Finally, the dynamic programming is used for improve the speed of computing spherical harmonic function, and the spherical harmonic function in all index and all times are computed at one pass. The fast computing model of ISAF basis function is built through an organic combination of the above methods. To validate this model, the simulated images of hepatitis E virus were used in three-dimensional reconstruction experiments. The referenced algorithm is the Fourier-Bessel reconstruction algorithm. The experiment results show that the running speed of ISAF reconstruction algorithm with this model is three times than that of Fourier-Bessel reconstruction algorithm. Furthermore, the speedup could grow up with the increase of the resolution requirement and the number of images.