To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computat...To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computation, a fast algorithm is proposed. The proposed algorithm includes three techniques. First, a linear array A[N] is introduced to store the sum of every row of the distance matrix （the same as SK）, which can eliminate many repeated computations. Secondly, the value of A [i] is computed only once at the beginning of the algorithm, and is updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of operational taxonomic units （OTUs） i and j is designed, and the correctness of the formula is proved. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases, constructing a tree with 2 000 OTUs in 3 min on a current desktop computer. To earn the time with the cost of the space and reduce the computations in the innermost loop are the basic solutions for algorithms with many loops.展开更多
3D traveltime calculation is widely used in seismic exploration technologies such as seismic migration and tomography. The fast marching method （FMM） is useful for calculating 3D traveltime and has proven to be effi...3D traveltime calculation is widely used in seismic exploration technologies such as seismic migration and tomography. The fast marching method （FMM） is useful for calculating 3D traveltime and has proven to be efficient and stable. However, it has low calculation accuracy near the source, which thus gives it low overall accuracy. This paper proposes a joint traveltime calculation method to solve this problem. The method firstly employs the wavefront construction method （WFC）, which has a higher calculation accuracy than FMM in calculating traveltime in the small area near the source, and secondly adopts FMM to calculate traveltime for the remaining grid nodes. Due to the increase in calculation precision of grid nodes near the source, this new algorithm is shown to have good calculation precision while maintaining the high calculation efficiency of FMM, which is employed in most of the computational area. Results are verified using various numerical models.展开更多
A method of restoring scratches on old paintings is proposed,and the corresponding high-accuracy output workflow is also developed.Firstly the scanner is selected as an input device to get the RGB(red,green,blue)image...A method of restoring scratches on old paintings is proposed,and the corresponding high-accuracy output workflow is also developed.Firstly the scanner is selected as an input device to get the RGB(red,green,blue)image of the painting,and for the purpose of capturing high-quality image,scanner characterization is done by using neural network.And then the scratches on the RGB image are restored with the technology of digital inpainting,while the inpainting algorithm is mainly based on gradient vector and fast marching method.Finally the restored image is output with a printer,which is calibrated by using the high order polynomial regression method.In experiment the new replicated painting is well restored in the scratched areas,as well as keeps high resemblance with the original painting.展开更多
文摘To improve the performance of Saitou and Nei＇s algorithm （SN） and Studier and Keppler＇s improved algorithm （SK） for constructing neighbor-joining phylogenetic trees and reduce the time complexity of the computation, a fast algorithm is proposed. The proposed algorithm includes three techniques. First, a linear array A[N] is introduced to store the sum of every row of the distance matrix （the same as SK）, which can eliminate many repeated computations. Secondly, the value of A [i] is computed only once at the beginning of the algorithm, and is updated by three elements in the iteration. Thirdly, a very compact formula for the sum of all the branch lengths of operational taxonomic units （OTUs） i and j is designed, and the correctness of the formula is proved. The experimental results show that the proposed algorithm is from tens to hundreds times faster than SN and roughly two times faster than SK when N increases, constructing a tree with 2 000 OTUs in 3 min on a current desktop computer. To earn the time with the cost of the space and reduce the computations in the innermost loop are the basic solutions for algorithms with many loops.
基金supported by NSFC(Nos.41274120,41404085,and 41504084)
文摘3D traveltime calculation is widely used in seismic exploration technologies such as seismic migration and tomography. The fast marching method （FMM） is useful for calculating 3D traveltime and has proven to be efficient and stable. However, it has low calculation accuracy near the source, which thus gives it low overall accuracy. This paper proposes a joint traveltime calculation method to solve this problem. The method firstly employs the wavefront construction method （WFC）, which has a higher calculation accuracy than FMM in calculating traveltime in the small area near the source, and secondly adopts FMM to calculate traveltime for the remaining grid nodes. Due to the increase in calculation precision of grid nodes near the source, this new algorithm is shown to have good calculation precision while maintaining the high calculation efficiency of FMM, which is employed in most of the computational area. Results are verified using various numerical models.
基金"13115"Sci-Tech Innovation Programof Shaanxi Province,China(No.2008ZDKG39)Youth Foundation of Xi'an University of Technology,China(No.104210807)
文摘A method of restoring scratches on old paintings is proposed,and the corresponding high-accuracy output workflow is also developed.Firstly the scanner is selected as an input device to get the RGB(red,green,blue)image of the painting,and for the purpose of capturing high-quality image,scanner characterization is done by using neural network.And then the scratches on the RGB image are restored with the technology of digital inpainting,while the inpainting algorithm is mainly based on gradient vector and fast marching method.Finally the restored image is output with a printer,which is calibrated by using the high order polynomial regression method.In experiment the new replicated painting is well restored in the scratched areas,as well as keeps high resemblance with the original painting.
