Methods to rectify distortion of digital camera document images of curved papers have become important for camera-based image recognition. In this paper we propose a novel distortion rectification method based on "shape from parallel geodesics.? This method considers the following features: parallel lines corresponding to character strings or ruled lines of tables on extended surface become parallel geodesics on a curved paper surface and a smoothly curved paper can be modeled by a ruled surface, that is, a sweep surface of rulings. The projected geodesics and the projected rulings exist in the input image derived from perspective transformation. The presented method extracts the projected geodesics, estimates the projected rulings in the input image, estimates the ruled surface that models the curved paper, and generates the corrected image, in this order. It can estimate the ruled surface model directly by numerical operations of differentiation, integration and matrix inversion without any iterative calculation. We also report on experiments that show the effectiveness of the proposed method.