Detecting right-angle corners of a rectangle in a complex image?

edit

I have some images of old scanned maps. The scans have "dead space" around them and also have a border around the map which is unnecessary and unhelpful for tiling the map. I'd like to automatically identify this border and crop it.

The border is of varying size, so this can't just be done with a standard imagemagick crop. I need to detect the corners of the scanned map.

This is the original image:

And this is what I'd like to end up with:

I've tried running canny edge detection on the original image, which simplifies nicely:

But I'm struggling with the next step - identifying the pixel positions of the four corners. It feels as though it should be easy - but maybe it's one of the things that is easy for humans but not for machines?

I've tried Hough line detection - this was very slow across the whole image, so I tried cropping the four relevant areas on the image and just running it on those.

The problem is that sometimes there are corners that are deceptive, e.g. here:

I also tried corner detection, but again, it finds all kinds of things that aren't right angle corners.

Any ideas for how I can find the four right angle corners that make up the image that I need? They're always in approximately the same areas of the image, if that helps.

Any ideas?

UPDATE: Thanks, I tried as per the suggestion. Unfortunately I'm having trouble with the Hough line detection. Here's my original:

Here are the canny edges:

And here are the Hough lines:

Unfortunately I can't start on the vertical/horizontal line detection because the line detection isn't good enough. It looks as though the line detection stops whenever it gets to a corner. Is there a way I can force it to continue through corners?

Also, I'm having problems setting the minimum line length: my parameter doesn't do anything.

This is my code:

gray = cv2.cvtColor(corner_img, cv2.COLOR_BGR2GRAY)
edges = cv2.Canny(gray, 100, 200)
cv2.imwrite('cropped_sw_corner-canny.png', edges)
minLineLength = 10 # Changing this to 100 does nothing.
maxLineGap = 1
threshold = 100
lines = cv2.HoughLinesP(edges,1,np.pi/180,threshold,minLineLength,maxLineGap)
for l in lines:
    for x1,y1,x2,y2 in l:
        cv2.line(corner_img,(x1,y1),(x2,y2),(0,0,255), 2)
cv2.imwrite('houghlines.jpg', corner_img)