When restoring a scanned halftone image of a damaged document, parameters of the halftone structure (geometry) are estimated, as is an intended contone gray level for damaged portions of the image. Locations of halftone cell tiles in the scanned image are determined based on the halftone structure, and a halftone profile model is generated using the estimated halftone parameters and contone information. Image segments are aligned using global features for coarse alignment and halftone structure for fine alignment, such as in cases where the scanned halftone image contains unconnected fragments. Missing parts of the damaged document image are filled in using the halftone profile model and estimated contone values.