Sheared-beam imaging technique is considered to be a non-conventional speckle technique for remote imaging through turbulent medium. In this high resolution imaging technique, three beams are splitted from one laser source and illuminate a remote target simultaneously in shearing distribution. Each beam is modulated by a tiny frequency shift so that these beams can interfere and beat together. The returning speckle signals are received by an array of detectors. The primary algorithm for the signal processing and image reconstruction has been developed previously. However, the reconstructed image is deteriorated by the frequency drifting error and spectrum leakage. These frequency errors are always from the transmitter and scattered signals that are caused by spectrum-shift errors from acoustic-optic modulators, atmospheric turbulence, Doppler effects of moving targets, etc. To solve the problems mentioned above, in this paper we propose a new image reconstruction algorithm based on the all-phase spectrum analysis theory. The all-phase fast Fourier transform (FFT) spectrum analysis theory, which can effectively inhibit spectral leakage and correct speckle spectrum, is used to process the scattered signals. By searching for the accurate positions of the beat frequency components in the transformed frequency domain data, the speckle amplitude and phase difference frames can be extracted accurately. Based on the speckle phase-difference frames, the phase distribution of the wavefront is derived by least-square algorithm. The phase distribution in grid is highly coherent, in which each point is related to the phases of its four nearest neighbors. If an initial phase map is given or preset, the phase map of the wavefront can be estimated accurately by Gauss-Seidel method. Meanwhile, the amplitude of wavefront is obtained by the algebraic operation of speckle amplitude frames. The reconstructed wavefront is inverse Fourier transformed to yield a two dimensional image. A series of speckled images of the same object are averaged to reduce the speckle noise. The proposed method improves the ability of system imaging in the actual imaging environment. Simulation experiments validate the effectiveness of the proposed algorithm, and simulation results show that the proposed image reconstruction algorithm can inhibit the frequency errors from influencing imaging quality when there exist frequency errors in scattered signals. Thus, the imaging quality of the algorithm based on the all-phase FFT method is much better than that of the algorithm based on the traditional FFT method. The substantial usage of this technique is widely spread after the reconstruction algorithm has been optimized.