In order to solve the problems that existing image dehazing methods cannot effectively remove non-homogeneous haze and their iterative dehazing results takes on overall darkening effects, a brightness compensation based iterative non-homogeneous image dehazing algorithm framework is proposed with the image dehazing module and the brightness compensation module. In each iteration, the image dehazing module is first employed to enhance the contrast of the image and reduce the haze density. Subsequently, the brightness compensation module is utilized to make up for the brightness loss caused by the image dehazing module, ensuring that the results of brightness compensation not only maintain the previous image dehazing effect but also achieve the original brightness level before the dehazing procedure. This process creates favorable conditions for further improving the dehazing effect of the image in the next iteration. In the brightness compensation module, a brightness compensation operator is designed according to the brightness changes before and after the image dehazing module, and a brightness compensation coefficients based adaptive brightness compensation mechanism is established, which can not only restore the original brightness of the image, but also improve the contrast of the image which can further boost the image dehazing effects. Extensive experimental results on the FiveK-HAZE, SOTS test set, and Real-Haze dataset demonstrate outstanding performance of the proposed algorithm in handling non-homogeneous haze images. The dehazed results exhibit excellent brightness, contrast, and color saturation. Our algorithm outperforms comparison methods in commonly used evaluation metrics such as peak signal-to-noise ratio, structural similarity, haze density, image naturalness, and learned perceptual image patch similarity.