How can I perform non-uniform rectification/straightening of a scanned image?

Question

I have a scanned image (let's assume 300 DPI and grayscale). It's a scanned page, on which the printing was perhaps not perfectly straight to being with, plus the scanning itself may have introduced some non-uniform stretching in different areas. On the other hand, the original content does have a lot of guidelines for straightness - literal lines: Underlined text and some tables covering a lot of the page.

So, the different lines are not pairwise-parallel (or pairwise-perpendicular when it's a vertical vs horizontal line); thus whenever I use one of these lines to "straighten" the image out by rotation - other lines become not-parallel with their relevant axis.

I'm sure that academic literature has methods for straightening out such lines; but - are there tools I could use today (on a Linux or Windows PC) to specify which lines need to become straight, and have the image "straightened" non-uniformly based on the proximity of each pixel to different guidelines?

Even more complicated version: Same question, but the guidelines themselves are not merely rotated, but slightly curved, i.e. when we think of the guidelines as paths, which one specifies using points along them.

Answer 1

In Photoshop, there is a tool called "Transform Warp" (or "Warp Transform").

For GIMP, I think an equivalent is the "n-point deformation tool."

These sound like they might fulfill your requirement.

Any automated tool would probably lean on something like that after some form of registration/recognition pass to determine how to deform the image.