shapefile - How to convert image of map into vector format?

What is the best way of converting a gif of a map into a vector format, such as a shapefile?

The only relevant parts that I am interested in are the outline of the island so I realize some manual work will be necessary where it is shaded orange; is there a way to handle the rest?

Regarding copyright, it's from the 1980s and it's being used for academic research.

Answer

GRASS GIS has a tool to convert raster lines to vector. The procedure is:

First open the map in an image editor (GIMP), select by colors with some tolerance and select the black color. Invert selection and delete non-black stuff. Save as Tiff WITH NO COMPRESSION.

Then in GRASS:

r.in.gdal - import raster
r.thin - Thins non-zero cells that denote linear features in a raster map.
r.to.vect - Converts a raster map into a vector map layer.

You will have problem with the texts and the grid. Some cleaning is essential for a good result.

As an example, here is a real screenshot of vector output of your image after the procedure in GRASS: