Due to the similarity of Brillouin optical time domain analyzer (BOTDA) signals, image denoising could be utilized to remove the noise. However, the performance can be much degraded due to inaccurate noise level estimation. By numerical and experimental study, we compare the noise level estimation of three different methods for BOTDA: calculating the standard deviation (STD) of the measurements, a filter-based estimation algorithm, and a patch-based estimation algorithm proposed in this paper, which selects weak textured patches of BOTDA signal and then estimates noise level using principal component analysis (W-PCA). The results show that W-PCA and the mean of STD can accurately estimate the noise level, while the filter-based method overestimates the noise level. Nevertheless, for BOTDA with distributed amplification, the STD has huge fluctuation along the length, while the W-PCA is relatively robust for its global consideration. Experimental results of an ultra-long-distance BOTDA prove that the non-local means denoising processing based on W-PCA effectively removes the noise of a sensing system without signal distortion.