Intrinsic image decomposition is a longstanding problem in computer vision. In this paper, we present a novel approach for efficiently decomposing an RGBD image into its reflectance and shading components. A robust super-pixel segmentation method is employed to select piece-wise constant reflectance regions and reduce the total number of unknowns. With the use of depth information, low frequency environment light can be represented by spherical harmonics and solved with super-pixels. After that, pixels that do not belong to any super-pixel are solved based on the super-pixels’ shading. Compared to existing works, which often depend on the color Retinex assumption, our algorithm does not require any chromaticity-based constraints and enables us to solve many challenging cases such as color lighting environments and gray-scale textures. We also design an efficient solver for our system, and with our GPU implementation, it achieves 10-23 fps and boosts the decomposition process to real-time performance, enabling a wide range of applications such as dynamic object recoloring, re-texturing and virtual object composition.