With regards to the format, the Garmin maps have already been deciphered and there's a library giving access to them. It's linked from the Navit wiki.

With regards to routing, yes it's certainly conceivable that one might do image processing and then route using bitmaps, but there's no direction or speed data, so native vector formats are probably better if they exist (and they do).

OSM, Garmin and possibly these Wayfinder maps are all options.

For routing there are a number of options:
http://wiki.openstreetmap.org/index.php/Routing

I'd be more tempted to implement this as an add-on to maemo mapper (though I've not looked at the code) rather than trying to hack an add on into the Wayfinder software.