We propose stochastic bilateral filter (SBF) and stochastic non-local means (SNLM), efficient randomized processes that agree with conventional bilateral filter (BF) and non-local means (NLM) on average, respectively. By Monte-Carlo, we repeat this process a few times with different random instantiations so that they can be averaged to attain the correct BF/NLM output. The computational bottleneck of the SBF and SNLM are constant with respect to the window size and the color dimension of the edge image, meaning the execution times for color and hyperspectral images are nearly the same as for the grayscale images. In addition, for SNLM, the complexity is constant with respect to the block size. The proposed stochastic filter implementations are considerably faster than the conventional and existing "fast" implementations for high dimensional image data.