Explainable AI (XAI) is essential for fostering trust in the predictions of deep neural networks (DNNs), especially within the domain of image classification. SHAP (SHapley Additive exPlanations), a theoretically sound method rooted in game theory, stands as a prominent XAI technique for attributing feature importance. However, SHAP’s inherent computational complexity, which grows exponentially with the number of features, restricts its practical application. Although numerous approximation methods have been proposed, they often deviate from the original SHAP formulation, potentially sacrificing accuracy and theoretical fidelity. In this paper, we introduce CorrSHAP, a novel approach that leverages image superpixel correlations to significantly accelerate SHAP value estimation while preserving the rigor of the original formulation. CorrSHAP efficiently quantifies the interdependence of superpixels within an image, enabling the SHAP calculation to consider only interdependent superpixel combinations. This targeted approach significantly reduces the computational burden without compromising the faithfulness of the explanation. Evaluation results demonstrate that CorrSHAP outperforms the comparable Monte Carlo SHAP method in explanation faithfulness, achieving this in a fraction of a second, with a 55-fold speed improvement. The source code is available on the link ( https://github.com/vhasic/CorrSHAP ).