In this paper, we propose an efficient coupled approach for uncertainty quantification of permeability for randomly reconstructed three-dimensional (3D) pore images, where the porosity and two-point correlations of a realistic sandstone sample are honored. The Joshi-Quiblier-Adler approach and Karhunen-Loève expansion are utilized for quick reconstruction of 3D pore images with reduced random dimensionality. The eigenvalue problem for the covariance matrix of 3D intermediate Gaussian random fields is solved equivalently by a kernel method. Then, the lattice Boltzmann method is adopted to simulate fluid flow in reconstructed pore space and evaluate permeability. Lastly, the sparse polynomial chaos expansion (sparse PCE) integrated with a feature selection method is employed to predict permeability distributions incurred by the randomness in microscopic pore structures. The feature selection process, which is intended to discard redundant basis functions, is carried out by the least absolute shrinkage and selection operator-modified least angle regression along with cross validation. The competence of our proposed approach is validated by the results from Monte Carlo simulation. It reveals that a small number of samples is sufficient for sparse PCE with feature selection to produce convincing results. Then, we utilize our method to quantify the uncertainty of permeability under different porosities and correlation parameters. It is found that the predicted permeability distributions for reconstructed 3D pore images are close to experimental measurements of Berea sandstones in the literature. In addition, the results show that porosity and correlation length are the critical influence factors for the uncertainty of permeability.