When the horizon or long edges are skewed in photos, they may seem unstable unless they are artistic intentions, and hence we may wish to correct the skews. For the skew correction of faint as well as strong horizons, we propose a skew estimation method for natural images. We first apply a long-block-based edge detector that can construct edge maps even when the edge is faint and/or background is cluttered. We also propose a robust line-detection method that uses the generated edge map, based on progressive probabilistic Hough transform followed by refinement steps. For each of the detected lines, we define their weight and estimate the image skew based on the weighted votes from the lines. Since all the pixels in the long-blocks are used for the edge-map construction, the proposed method can find noisy or faint lines while rejecting curved or short lines. Experimental results show that the first salient angle corresponds with the image skew in most cases, and the skews are successfully corrected.