Most of the outdoor images suffer from contrast degradation caused by fog and haze. Two statistical frameworks have been proposed in recent years that exploit local (dark channel prior) and non-local (haze-lines) characteristics of hazy images for the estimation of scene configurations and the restoration of scene albedo. Both frameworks show intrinsic limitations due to the basic assumptions they rely on. In this paper we propose a novel dehazing method that combines the advantages of local and non-local dehazing methods. Exploiting their complementary statistical properties, we use the local features to regulate the estimation of non-local haze-lines for a better final restoration at challenging regions. Both quantitative and qualitative results validate the effectiveness of our proposed method over state-of-the-art frameworks.