GPS Satellite navigation software!

[pyrohaz]

So I've decided to have a go at creating a CRUDE satnav system with my STM32F0 board an a little 128x128 LCD. So far I've managed to multiplex the SD SPI with the LCD SPI and display a 128x128 section of an extremely high resolution map (21kx25k pixels) of the UK that I downloaded using a BigMap perl script.

Now I say crude in the opening because the resolution required to pinpoint yourself on a path or road would be magnitudes larger than this map size. The map is stored in my own pixel format which is a linear stream of rows in RGB121 format (2 pixels/byte) meaning by just seeking through the file (with the header offset constant), I can grab rows and push them to the screen without needing to worry about decompression of byte padding (BMP) which cuts a bit of overhead and gets my images to the screen faster.

What I'm wanting to do now is to display my current GPS point on this map image then. I'll list my current methodology and then if there are any suggestions, I'd definitely appreciate it!

• Calculate the pixels/meter of the map using two known reference lat/long locations. I'm using two at either end of my map for less relative error. I'm acquiring my Lat/Longs from google maps, for example a notable bend in a road where I can get the exact pixel.
• From one of the reference points, I then calculate my distance and bearing from my current position to the reference point.
• I then convert my distance (still in meters) to a distance in pixels. The distance in pixels is then split into X and Y components using the bearing so I know that I am 'A' X pixels away and 'B' Y pixels away from the reference point
• This point is then plotted on my map.

So I'm sure you can pick out a couple of flaws already. As I previously mentioned, an extremely large resolution map would be required to pinpoint your location with any real accuracy. Having such a large file on my SD card also means that drawing the map to the screen takes a fair bit of time (up to about 2-3 seconds!) and leaves minimal space for much else!

What I'm wondering is: How do they do it on a real sat nav so efficiently?

[georges80]

'Real sat nav units' use Street level maps that are stored as vectors and then rendered when being displayed. They also have LOTS of storage for POI, lane hints/pictures etc.

Have fun playing with your GPS stuff.

cheers,
george.

[SaabFAN]

If vector-maps are not available, every pixel is assigned a longitude and lattitude-component essentially. I once had to do that with sea charts for a boat-computer running linux because the commercially available cards weren't available for the software I used (forgot the name, Something with Open CPM or similar...). After scanning the bitmaps, I had to use a special software to align the pixels with the navigation-grid.

So In essence, your approach is probably how to do it if only bitmaps are available and apart from using vector-maps, I don't see any big and obvious flaws.

What you could do to save space is using Photoshop and remove one color-channel which is then later reconstructed with software. When texturing 3D-Models I use that technique quite often to save some valuable RAM. You won't believe how valuable each MB of RAM becomes when doing game-graphics.

I'm using this method to remove the Blue Channel from the Normal-Map and use this formula inside the engine to reconstruct it: B=x*2-1 where "B" = The Greyscale-Value of the Pixel in the blue channel and "x" is the value of the Red and Green channel. I don't know at the moment how these two values are connected, but the only possibilities are difference and sum. In the Unreal Engine I only use nodes, which form this Network:
>> Texture with Normal-Map in the R & G-Channel -> R&G-Mask -> Multiply by 2 -> Invert -> Output" <<

Another method to save memory: Store one High Resolution Map and blend it with a low resolution color-map. Another technique often used in Games: The Normal-Map (giving the model depth and structure) is high resolution and the color-texture is half the resolution of the Normal-Map.

Of course both methods, as well as the vector-option, sacrifice available computing-time for memory. You can't have both

[Stupid Beard]

To give you a better understanding of this thing as a whole, with appropriate apologies if you already know this. You will want to fact-check this because most of it's from memory and I may be a bit inaccurate in places.

There's a couple of different things to consider before a co-ordinate has any meaning.

Firstly, you need to know the datum. This is the geographic model of the earth and gives meaning to latitude and longitude. GPS uses WGS-84, which is an ellipsoid. Google maps uses a big sphere because it makes some math easier. Since you're in the UK, it's also worth mentioning the national grid is based on OSGB36 which is based on the Airy ellipsoid.

A given lat / long will be valid on any ellipsoid, but will specify a different point in space. Depending on where you are, these can actually be close enough that you may not notice you're using the wrong one. From your point of view, the ellipsoid only really affects some parameters in the math.

The second thing to consider is the projection. This specifies how you map the 3D shape of the reference ellipsoid onto the 2D space that is the map. Both the OS and Google use transverse mercator. Vastly simplified, this will give you linear meters from a reference point and from those it's a piss easy conversion to pixels.

So, the biggest question is where did you get the big map source data from? Is it from the Ordnance Survey? If so, then it's going to be using OSGB36 projected using transverse mercator to the national grid. If it's from google maps or open street map, then it will be using a different datum but similar projection.

So, to locate the correct pixel you first get your lat/long, re-project it from WGS-84 to either OSGB or Google maps then you project that lat/long to meters, then you convert meters to pixels based on the resolution of your map. There are libraries to do this; PROJ4 is one but there are others.

GPS receivers will by default specify the location on WGS-84, but you might be able to tell it to use a different ellipsoid (check the datasheet). If you can then that will save you re-projecting from WGS-84 to whatever is appropriate for your map which will save you a fair bit of math.

Because the math is pretty heavy you will want to do as much as possible in pixel space. Generally this means you'd convert an incoming location to a pixel location and then do the rest using pixels. By which I mean, determining how much of and which part of the map to display. This reduces the problem to dealing with a large image.

Anyway, that's how to handle the geography correctly. You may be able to take some shortcuts by not giving a shit about inaccuracies. It really depends on what you want out of it in the end.

This is pretty long and took long enough to write that I've lost track of my train of thought, so hopefully you found that helpful and I didn't miss anything

[SL4P]

Sorry if this is a repetition of the above...
In any case of map style, I 'know' the precise 'top-left' LAT-LON of the map, and the X-Y dimensions of the map in degrees, minutes.decimal. (Or any other two specific points on the map).

The screen window is referenced to a known LAT-LON coordinate of the top-left corner of the screen (you need to do some maths for rotating maps)...

Then based on the overall map, and your window 'viewport' on that map - you now add in scaling to allow for zoom factor, and you're half-way there.

To make it zoom nicely, you may like to move the viewport reference to the centre of the screen area... but make sure you don't fall off the edges of the stored map!

All these concepts apply for any kind of map, but the rendering methods will vary whether it's a bit-mapped or vector image.  Vector maps of course are scalable, and you can overlay the street names etc as you build up the displayed layers.

With a processor like the ARMs  rotation isn't a big deal - but only rotate as much as you need to render - and when possible - blit the images for pan & scroll - to eliminate CPU rendering time that could be used for something else!

[cdev]

I would get an RTKLib compatible receiver and the very capable and interesting RTKLib software by Tomoji Takasu, which can display and allow you to tweak every single step of the process including the solution  - Start here-  if you have any questions, feel free to PM me.

http://gpspp.sakura.ne.jp/indexe.html


That will give you an inside look at the entire process. There is really nothing else quite like it. Note you will need hardware thats supported. I have Skytraq hardware, there are a number of different inexpensive receiver/antenna options. if you get a good antenna and can set up a base station and resolve its exact location over time you end up with a system whose accuracy is really quite phenomenal.

[Stupid Beard]

Sorry if this is a repetition of the above...
In any case of map style, I 'know' the precise 'top-left' LAT-LON of the map, and the X-Y dimensions of the map in degrees, minutes.decimal. (Or any other two specific points on the map).

The screen window is referenced to a known LAT-LON coordinate of the top-left corner of the screen (you need to do some maths for rotating maps)...

Then based on the overall map, and your window 'viewport' on that map - you now add in scaling to allow for zoom factor, and you're half-way there.

You can do that, but remember that the lat/long co-ords are on the surface of an ellipsoid and the pixels are a 2 dimensional plane. It will work, but will suffer distortion unless the map data itself uses the same projection which it is unlikely to be doing.

If the source of the map data is vector based then you can re-project it all to form new map images where the above will work. If the original map is raster based then forget doing this, it will distort it too much.

How inaccurate this method would be with inappropriate map data depends on the size of the geographic area and where on the ellipsoid the location is. If the area is small enough and far enough away from the poles then it may work well enough that the error is acceptable.

[pyrohaz]

Wow! Thank you all for the brilliant response.

'Real sat nav units' use Street level maps that are stored as vectors and then rendered when being displayed. They also have LOTS of storage for POI, lane hints/pictures etc.

Have fun playing with your GPS stuff.

cheers,
george.

I'd actually be happy to look into vector rendering but I'm not really sure where to start! I understand the basics of vectors (from an engineering perspective) and assume that this knowledge can translate to map vectors?

If vector-maps are not available, every pixel is assigned a longitude and lattitude-component essentially. I once had to do that with sea charts for a boat-computer running linux because the commercially available cards weren't available for the software I used (forgot the name, Something with Open CPM or similar...). After scanning the bitmaps, I had to use a special software to align the pixels with the navigation-grid.

So In essence, your approach is probably how to do it if only bitmaps are available and apart from using vector-maps, I don't see any big and obvious flaws.

What you could do to save space is using Photoshop and remove one color-channel which is then later reconstructed with software. When texturing 3D-Models I use that technique quite often to save some valuable RAM. You won't believe how valuable each MB of RAM becomes when doing game-graphics.

I'm using this method to remove the Blue Channel from the Normal-Map and use this formula inside the engine to reconstruct it: B=x*2-1 where "B" = The Greyscale-Value of the Pixel in the blue channel and "x" is the value of the Red and Green channel. I don't know at the moment how these two values are connected, but the only possibilities are difference and sum. In the Unreal Engine I only use nodes, which form this Network:
>> Texture with Normal-Map in the R & G-Channel -> R&G-Mask -> Multiply by 2 -> Invert -> Output" <<

Another method to save memory: Store one High Resolution Map and blend it with a low resolution color-map. Another technique often used in Games: The Normal-Map (giving the model depth and structure) is high resolution and the color-texture is half the resolution of the Normal-Map.

Of course both methods, as well as the vector-option, sacrifice available computing-time for memory. You can't have both

I'm quite sure that openstreetmap offers vectorised maps though as I said, I'm not too sure on where to start with creating a vector renderer. Your pixel storage method seems pretty interesting though! Is it related at all to YCbCr storage method just with integer operations to encode and decode?

To give you a better understanding of this thing as a whole, with appropriate apologies if you already know this. You will want to fact-check this because most of it's from memory and I may be a bit inaccurate in places.

There's a couple of different things to consider before a co-ordinate has any meaning.

Firstly, you need to know the datum. This is the geographic model of the earth and gives meaning to latitude and longitude. GPS uses WGS-84, which is an ellipsoid. Google maps uses a big sphere because it makes some math easier. Since you're in the UK, it's also worth mentioning the national grid is based on OSGB36 which is based on the Airy ellipsoid.

A given lat / long will be valid on any ellipsoid, but will specify a different point in space. Depending on where you are, these can actually be close enough that you may not notice you're using the wrong one. From your point of view, the ellipsoid only really affects some parameters in the math.

The second thing to consider is the projection. This specifies how you map the 3D shape of the reference ellipsoid onto the 2D space that is the map. Both the OS and Google use transverse mercator. Vastly simplified, this will give you linear meters from a reference point and from those it's a piss easy conversion to pixels.

So, the biggest question is where did you get the big map source data from? Is it from the Ordnance Survey? If so, then it's going to be using OSGB36 projected using transverse mercator to the national grid. If it's from google maps or open street map, then it will be using a different datum but similar projection.

So, to locate the correct pixel you first get your lat/long, re-project it from WGS-84 to either OSGB or Google maps then you project that lat/long to meters, then you convert meters to pixels based on the resolution of your map. There are libraries to do this; PROJ4 is one but there are others.

GPS receivers will by default specify the location on WGS-84, but you might be able to tell it to use a different ellipsoid (check the datasheet). If you can then that will save you re-projecting from WGS-84 to whatever is appropriate for your map which will save you a fair bit of math.

Because the math is pretty heavy you will want to do as much as possible in pixel space. Generally this means you'd convert an incoming location to a pixel location and then do the rest using pixels. By which I mean, determining how much of and which part of the map to display. This reduces the problem to dealing with a large image.

Anyway, that's how to handle the geography correctly. You may be able to take some shortcuts by not giving a shit about inaccuracies. It really depends on what you want out of it in the end.

This is pretty long and took long enough to write that I've lost track of my train of thought, so hopefully you found that helpful and I didn't miss anything

No need to apologise! I appreciate every part of information. I've been reading up on the map projection techniques and I think thats where I'm finding my associated errors from. I'm using the haversine method to find distances though I find that using linear interpolation of GPS points gives about the same level of accuracy (down to about 1 pixel). I like the look of the PROJ4 library. Do you know of any sources that I can find high resolution maps with predefined datapoints? Realistically, I'm looking for about 1 pixel of accuracy which translates to about 1 mile/pixel with a map of 21kx25k. I think the next best option after this will be to use tiled maps and just reference the correct map dependent on my current location.

Sorry if this is a repetition of the above...
In any case of map style, I 'know' the precise 'top-left' LAT-LON of the map, and the X-Y dimensions of the map in degrees, minutes.decimal. (Or any other two specific points on the map).

The screen window is referenced to a known LAT-LON coordinate of the top-left corner of the screen (you need to do some maths for rotating maps)...

Then based on the overall map, and your window 'viewport' on that map - you now add in scaling to allow for zoom factor, and you're half-way there.

To make it zoom nicely, you may like to move the viewport reference to the centre of the screen area... but make sure you don't fall off the edges of the stored map!

All these concepts apply for any kind of map, but the rendering methods will vary whether it's a bit-mapped or vector image.  Vector maps of course are scalable, and you can overlay the street names etc as you build up the displayed layers.

With a processor like the ARMs  rotation isn't a big deal - but only rotate as much as you need to render - and when possible - blit the images for pan & scroll - to eliminate CPU rendering time that could be used for something else!

I've been doing this kind of method though since the edges of my map are in the middle of the sea, I've been using notable landmarks at the edges of the British Isles! If you would know of any source of high resolution maps with defined data points and their lat/long with pixel locations, I'd be extremely appreciative!

I would get an RTKLib compatible receiver and the very capable and interesting RTKLib software by Tomoji Takasu, which can display and allow you to tweak every single step of the process including the solution  - Start here-  if you have any questions, feel free to PM me.

http://gpspp.sakura.ne.jp/indexe.html


That will give you an inside look at the entire process. There is really nothing else quite like it. Note you will need hardware thats supported. I have Skytraq hardware, there are a number of different inexpensive receiver/antenna options. if you get a good antenna and can set up a base station and resolve its exact location over time you end up with a system whose accuracy is really quite phenomenal.

Sadly, I'll be using a cheapo Ublox7 GPS module though that library looks extremely useful!

Sorry if this is a repetition of the above...
In any case of map style, I 'know' the precise 'top-left' LAT-LON of the map, and the X-Y dimensions of the map in degrees, minutes.decimal. (Or any other two specific points on the map).

The screen window is referenced to a known LAT-LON coordinate of the top-left corner of the screen (you need to do some maths for rotating maps)...

Then based on the overall map, and your window 'viewport' on that map - you now add in scaling to allow for zoom factor, and you're half-way there.

You can do that, but remember that the lat/long co-ords are on the surface of an ellipsoid and the pixels are a 2 dimensional plane. It will work, but will suffer distortion unless the map data itself uses the same projection which it is unlikely to be doing.

If the source of the map data is vector based then you can re-project it all to form new map images where the above will work. If the original map is raster based then forget doing this, it will distort it too much.

How inaccurate this method would be with inappropriate map data depends on the size of the geographic area and where on the ellipsoid the location is. If the area is small enough and far enough away from the poles then it may work well enough that the error is acceptable.

I think with the map I have, this distortion is giving me the majority of my error, the error predominantly seems to occur on the Y axis of the map though, whether that is because of the projection being a squished sphere thing, I don't know!

I think my main questions now are if anyone knows of any predefined maps with data points OR a method that I can accurately acquire these?

[Stupid Beard]

For map data, your best bet is to go with OpenStreetMap at least initially. If memory serves, they have a bunch of tools that will re-project and render the maps.

Stop thinking in miles. Cartography is done in meters. I know that's hard to do in this country because we all love to hold on to our imperial measurements in spite of metric. But all map data you acquire will be specified in meters and resolution is specified in meters per pixel. Don't worry, you can still hang on to pints of milk

Don't bother with vector maps yet, at least not at the device level. Rendering vector maps involves first rasterizing them either on the fly or offline in advance. Once you get down to a low enough level it's all just displaying a really large bitmap.

[pyrohaz]

For map data, your best bet is to go with OpenStreetMap at least initially. If memory serves, they have a bunch of tools that will re-project and render the maps.

Stop thinking in miles. Cartography is done in meters. I know that's hard to do in this country because we all love to hold on to our imperial measurements in spite of metric. But all map data you acquire will be specified in meters and resolution is specified in meters per pixel. Don't worry, you can still hang on to pints of milk

Don't bother with vector maps yet, at least not at the device level. Rendering vector maps involves first rasterizing them either on the fly or offline in advance. Once you get down to a low enough level it's all just displaying a really large bitmap.

Haha! I completely agree with dropping miles, It would be much better if we all adopted metric measurements. I'm quite a fan of OSM, I find it so impressive that you can get such high quality maps through generally good people of the world (I contribute to OpenCellID to aid the open source mapping stuff too!). Yeh, I'm currently running the system on an STM32F0 so I don't have anywhere near enough RAM to even render a full graphics buffer! I do all my testing through Matlab and C++ on my computer before testing on my platform though. I'm not actually very knowledgeable when it comes to the many offers of OSM. Do you think I could use their projecting package to get the useful reference points?

[Stupid Beard]

For map data, your best bet is to go with OpenStreetMap at least initially. If memory serves, they have a bunch of tools that will re-project and render the maps.

Stop thinking in miles. Cartography is done in meters. I know that's hard to do in this country because we all love to hold on to our imperial measurements in spite of metric. But all map data you acquire will be specified in meters and resolution is specified in meters per pixel. Don't worry, you can still hang on to pints of milk

Don't bother with vector maps yet, at least not at the device level. Rendering vector maps involves first rasterizing them either on the fly or offline in advance. Once you get down to a low enough level it's all just displaying a really large bitmap.

Haha! I completely agree with dropping miles, It would be much better if we all adopted metric measurements. I'm quite a fan of OSM, I find it so impressive that you can get such high quality maps through generally good people of the world (I contribute to OpenCellID to aid the open source mapping stuff too!). Yeh, I'm currently running the system on an STM32F0 so I don't have anywhere near enough RAM to even render a full graphics buffer! I do all my testing through Matlab and C++ on my computer before testing on my platform though. I'm not actually very knowledgeable when it comes to the many offers of OSM. Do you think I could use their projecting package to get the useful reference points?

It's been a really long time since I looked at OSM, but https://wiki.openstreetmap.org/wiki/Main_Page should have everything you need to know about using their data. I am pretty sure that all the OSM tools use either PROJ4 or one of the similar things (who's name is currently escaping me) under the hood.

The Ordnance Survey have a bunch of freely available data also at https://www.ordnancesurvey.co.uk/opendatadownload/products.html

To hopefully make this a bit simpler for you to understand/have things to look up, here's a quick high level overview of how you'd do it with PROJ4. Whether you use PROJ4 or not the general idea is the same.

PROJ4 has init strings that define the datum and projection. Other libs may specify this differently, or they may support PROJ4 init strings directly. The ones you are likely to care about are as follows:

WGS84 (GPS):

Code: [Select]

+proj=longlat +ellps=WGS84 +datum=WGS84 +no_defs
Ordnance Survey:

Code: [Select]

+proj=tmerc +lat_0=49 +lon_0=-2 +k=0.9996012717 +x_0=400000 +y_0=-100000 +ellps=airy +datum=OSGB36 +units=m +no_defs
Google / OpenStreetMap (should double check that OSM actually uses this, but I'm pretty sure it does):

Code: [Select]

+proj=merc +a=6378137 +b=6378137 +lat_ts=0.0 +lon_0=0.0 +x_0=0.0 +y_0=0 +k=1.0 +units=m +nadgrids=@null +no_defs
You pass these to pj_init_plus() to get an appropriate projPJ pointer to pass to other functions.

Lets say you're using stock open street map tiles. When you get a lat/long point from your GPS, you call pj_transform() with wgs84 as the source projection and the google one as the destination projection.

That will give you a point in meters. To get from there to pixels you just need to know the offset (in meters) of pixel 0,0 and the pixel resolution of the tiles you're using.

You can also do all this in reverse if you want to go from a pixel location to a lat/long.

What is happening is this:

• The lat/long point gets transformed from the source ellipsoid to the destination ellipsoid
• It does a transverse mercator projection (for Ordnance Survey) or mercator (Google) to get from lat/long on the dest ellipsoid to meters

Mercator and Transverse Mercator are basically the same thing. The transverse part just means there's a constant offset, which for ordnance survey means that all co-ordinates on the national grid will be positive.

I would suggest playing around with this in C++ on your computer first to get a really solid understanding of it from a high level view. I don't think you'd want to use PROJ4 on the device itself because it's pretty bloated and slow. Instead you'd want to figure out the exact math it would be doing and do that yourself. Sorry, I've been skirting around the issue of the exact math because it's been 3 years since I looked at this and I'm really rusty on it so I don't want to send you down the garden path.

Some things to remember:

• Use double and not float. Float does not have enough precision for the size of the numbers required.
• When you are dealing with lat/long in PROJ4, it wants them in radians. You are likely thinking of them in degrees, so watch out for that. Also don't try and convert meters to radians 
• OSM tiles and zoom levels are all pow2 based, so you can do use bitshifts for some of the math.

Hope that helps