Techniques are disclosed for removing haze from an image or video by constraining the medium transmission used in a haze image formation model. In particular, a de-hazed scene, which is a function of a medium transmission, is constrained to be greater than or equal to a fractionally scaled variant of the input image. The degree to which the input image is scaled can be selected manually or by using machine learning techniques on a pixel-by-pixel basis to achieve visually pleasing results. Next, the constrained medium transmission is filtered to be locally smooth with sharp discontinuities along image edge boundaries to preserve scene depth. This filtering results in a prior probability distribution that can be used for haze removal in an image or video frame. The input image is converted to gamma decoded sRGB linear space prior to haze removal, and gamma encoded into sRGB space after haze removal.