Skew correction of scanned documents is a crucial step for document recognition systems. Due to the problem of high computational costs of the state-of-the-art methods, we present herein a variation of a parallelograms covering algorithm. This variation strongly reduces the computational time and works over noisy documents and documents containing non-textual elements, like: stamps, handwritten components and vertical bars. Experimental studies with different databases show that this variation overcomes well-known techniques, achieving better results over synthetic rotated documents and real scanned documents.