# Dense Robust 3D Reconstruction and Measurement for 3D Printing Process Based on Vision
## 3 The Matching Method Based on the FFT-SIFT-AKAKAE
### Improved SIFT Algorithm Based on Fast Fourier Transform (FFT-SIFT)  
The traditional SIFT algorithm has four steps, which are constructing scale space to detect extreme points, the accurate positioning of the key points, determining direction parameters of key points, and generating descriptor of feature points. The process of constructing scale space occupies 72.85% of the time. Therefore, accelerating the construction of the Gaussian pyramid is the key to solving the above-mentioned problems.  
The literature [22] theoretically proposed that the fast Fourier transform algorithm should be applied to the construction of the Gaussian pyramid to accelerate the process of convolution between the image and the Gaussian filter template, realize the rapid construction of the scale space, and then improve the feature extraction speed of the whole SIFT algorithm. The improved Gaussian pyramid creation process using FFT is shown in Figure 2.  
The DoG (Difference of Gaussians) pyramid creation has three operations: image amplification, image smoothing using Gaussian convolution, and image down sampling [22]. A set of images with different scales can be obtained by convolution the image in the original SIFT algorithm. In practice, the last second images of a set of images is down sampling to become be the first image of the next set of images, and then produce the image of the O (Octave) group S (Level) layer by analogy. In the image Pyramid, images of two adjacent scale space are subtracted to form the DoG pyramid.  
In the improved Gaussian pyramid, the input image \(f(x,y)\) is firstly transformed into the frequency domain \(f\) [\(u\),\(v\)] by two-dimensional FFT transform, and then the Gaussian filter template is used to make its size consistent with the image by zero-filling operation,  
Figure 2: The construction process of the improved Gauss pyramid.  
and the FFT transform is also carried out. \(M\) and \(N\) in the formula represent the two-dimensional sequence length, respectively.  
\[F[u,v]=\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f[x,y]e^{-j2\pi\frac{u}{M}x}e^{-j2\pi \frac{v}{M}y} \tag{4}\]  
\[f[x,y]=\frac{1}{MN}\sum_{u=0}^{M-1}\sum_{v=0}^{N-1}F[u,v]e^{j2\pi\frac{u}{M}x}e^ {j2\pi\frac{v}{M}y} \tag{5}\]  
According to the convolution theorem, the scale space is constructed by multiplying the initial image in the frequency domain with the Gaussian template after FFT transformation. After convolution with Gaussian template, it is necessary to downsampling the image to create different groups of Gaussian pyramid. The third layer from the bottom of each group is downsampling as the first picture of the next group. Similarly, desampling can be achieved in the frequency domain by superposition of spectral signals according to the convolution theorem. The superimposed down-sampling signal is:  
\[V(k)=\frac{1}{2}\bigg{[}X\bigg{(}\frac{k}{2}\bigg{)}+X\bigg{(}\frac{k+N}{2} \bigg{)}\bigg{]} \tag{6}\]  
where \(X(k)\) is the spectrum of the original image, and \(V(k)\) is the spectrum of the sampled signal of length \(N\). Finally, the processed image is transformed into Gaussian pyramid by inverse FFT, and the subsequent operation is similar to the traditional SIFT. In theory, the reconstruction of the Gaussian pyramid based on FFT can significantly speed up the construction speed of the pyramid, and then the speed of the whole feature point extraction can be improved.