Need 2D graphics guru

[lozina]

Hi fellas,

I really need a 2d GFX guru to advise me on how to accomplish something which I don't know even how to approach yet.

I want to develop a cool map based tool that needs to read a map image and separate distinct regions out of it so that I may easily do hit testing and filling on them. And this would be the key map to identify regions while another real map of the same location is what would be displayed. This is totally for personal hobby - not for work, not for profit.

My map image input would look something like this (basic example):

It contains a number of solid, unique colored continuous regions. This means all pixels for one region are connected to eachother and they are all exactly the same RGB value. There would be no other region with the same RGB value.

I want to scan this image in C# and be able to create I guess a Region object to represent each separate region of the map.

So perhaps after processing I'd end up with:

Which just illustrates that the program has detected 8 separate regions, labeled A-H. And the black lines represent the borders it detected between those regions.

Then once I have separate objects representing each region I can display a real looking map image on a GUI represented by the same area as the key map above but instead of simple, solid colored regions it is now a detailed map of greens of trees and such with no discernible regions. But since I have the region objects from the input image I can draw the borders on top of this map and even overlay the regions on top of this map by filling their area with some color.

So lets say the key map was for the counties of a state. Each county represented by a unique color. I scan this with some algorithm to detect the borders and create Region objects for each one.

Then the GUI displays a real satellite looking map of my state, and using the region data by reading the key map it can draw the borders between the counties on top of this map. Obviously both maps have exactly the same dimensions and match exactly in scale and everything. Then maybe when the user mouses over a county on the real map I will know which county they are on since I'd know it's Region and it's boundaries from the key map - and display pertinent info. And maybe they click a button which highlights all counties with population over 100,000 for example. Since I'd have Region objects I can easily Fill them with some overlay color.

Anyway - my problem is I have absolutely no idea how to do an algorithm to scan that key map and create the separate regions.

I would like something that is a little bit "loose", as in it does not build a giant path of points going pixel by pixel for the borders around the region, but sort of smooths it out like how I drew those lines in the second image above. This way each region is represented by much fewer points to save memory. And also I may need to do this for several thousand unique regions, so this algorithm's gotta be pretty quick so the user doesnt sit there for 5 minutes while this processes.

*ANY* advise on doing this would mean a lot to me... a link to an algorithm, a book, a tutorial - anything you may be familiar with or can suggest or whatever info I would greatly appreciate.Maybe even suggest another forum specific to gfx programming that may have more experts willing to lend some advice.

Thanks and happy new year!

 

[clamum]

I've been looking on MSDN's .NET Framework classes but I haven't found anything really relevant yet. I'm not writing any app like that, but I'd be interested in how the OP's issue could be solved.

 

[GodlessAstronomer]

I'm most definitely NOT a 2d graphics guru and I've never done anything like this, but for kicks I put together a little program that builds the border. It looks a bit funny because your input image has some .jpg compression which messes with the check for color equality. There are a ton of optimizations to be had in this code and there's probably a fundamentally better way of doing this, but this kind of works.

This method most certainly falls into the "naive approach" bucket.

Here's hwo it looks if you start with a clean image

using System;
using System.Drawing;

namespace MapThing
{
    class Program
    {
        private const string path = @"c:\Projects\a1.JPG";
        private static int tolerance = 30;

        // helper method, useful for testing if two colors match
        // within some tolerance.
        static bool colorsMatch(Color c1, Color c2)
        {
            if (Math.Abs(c1.A - c2.A) < tolerance &&
                Math.Abs(c1.B - c2.B) < tolerance &&
                Math.Abs(c1.G - c2.G) < tolerance)
                return true;
            return false;
        }

        static void Main(string[] args)
        {
            Bitmap bmp = new Bitmap(path);
            Bitmap outline = new Bitmap(bmp.Width, bmp.Height);
            
            // This loop just sets the new BMP pixels to white
            for (int i = 0; i < outline.Width; i++)
            {
                for (int j = 0; j < outline.Height; j++)
                {
                    outline.SetPixel(i, j, Color.FromArgb(0xffffff));
                }
            }

            // loop through each pixel in the imput bmp and see if it's color
            // matches that of it's neighbour. If the colors don't match then mark the border.
            for (int x = 0; x < bmp.Width; x++)
            {
                for (int y = 0; y < bmp.Height; y++)
                {
                    Color c = bmp.GetPixel(x,y);
                    if (x > 0 && !colorsMatch(c, bmp.GetPixel(x - 1, y)))
                        outline.SetPixel(x - 1, y, Color.FromArgb(0,0,0));
                    if (x < bmp.Width-1 && !colorsMatch(c, bmp.GetPixel(x + 1, y)))
                        outline.SetPixel(x + 1, y, Color.FromArgb(0, 0, 0));
                    if (y > 0 && !colorsMatch(c, bmp.GetPixel(x, y - 1)))
                        outline.SetPixel(x, y - 1, Color.FromArgb(0, 0, 0));
                    if (y < bmp.Height-1 && !colorsMatch(c, bmp.GetPixel(x, y + 1)))
                        outline.SetPixel(x, y + 1, Color.FromArgb(0, 0, 0));


                }
            }
            Console.WriteLine("saving...");
            outline.Save(@"c:\Projects\output.bmp", System.Drawing.Imaging.ImageFormat.Bmp);
            Console.WriteLine("done");
            Console.ReadLine();
        }
    }
}

Quick question before I proceed, will each region in the map have a distinct color? Or will colors be reused?

 

[Markbnj]

The classic text covering some of these areas is Foley, van Dam, et al, "Computer Graphics Principles and Practice." I happen to have a copy, and chapter 19 deals with advanced 2D algorithms such as filling and edge detection. I'm sure much of this information is out on the web as well.

You need to break the problem up and address specific pieces of it. You'll need the primitives that allow you to define "regions" and in order to define those it will help to have a strong sense of what a region itself is. The .NET framework defines some useful primitives in the System.Drawing and System.Drawing.Drawing2D namespaces, and you should have a look at those. Specifically I would think Region, RegionData, and GraphicsPath would be interesting to you.

Basically a "region" is an enclosed, bounded area. Using some combination of your own or .NET's primitives you will need to define the data that represents a "region" in your application. Having done that you will need an algorithm to scan the input image, detect the regions of homogenous color in it, and produce "region" definitions that describe what was found. For example you can turn a region containing 2500 "green" pixels into a series of connected line segments describing the border, and a single variable to describe the color.

Detecting where that border is will be the fun part. It's essentially an edge detection problem, although I presume you can greatly optimize/simplify it because of your color constraints. This is an area I knew a lot more about 20 years ago that I do now, and I assume there are some new algorithms and ideas out there for this task. Hopefuly some of the other members here will have some ideas.

 

[lozina]

I'm most definitely NOT a 2d graphics guru and I've never done anything like this, but for kicks I put together a little program that builds the border. It looks a bit funny because your input image has some .jpg compression which messes with the check for color equality. There are a ton of optimizations to be had in this code and there's probably a fundamentally better way of doing this, but this kind of works.


Quick question before I proceed, will each region in the map have a distinct color? Or will colors be reused?

Hey, that's pretty awesome man !

And you're doing it more difficult because the image I posted above was compressed just for forum's sake. The real images would be bmp so there would be no need for a tolerance setting since the RGB values for one region will be exactly the same pixel to pixel.

And each region will have it's own unique color.

Nice job!

 

[Cerebus451]

One question I would ask is if the boundary files you are trying to generate don't already exist. Not that creating an edge detection algorithm is a useless exercise, as that kind of algorithm has plenty of practical applications, and is fun to develop.

However, if you wanted to jump in to your main application, you might find the boundary files you are trying to create already exist (going off your one example of county boundaries). For the U.S., you can find boundaries down to the census block group for free in shape file format from the Census bureau (http://www.census.gov/geo/www/cob/bdy_files.html), and there are free libraries available for working with shape files.
http://www.census.gov/geo/www/cob/bdy_files.html

 

[Cogman]

If this was some sort of photo. (IE, not a distinct Image) Then I would recommend using a different color space and optimizing based on the changes in that color (IE, use YUV instead of RGB. It matches better what colors we perceive as different rather then what an RGB color code would say is different).

Given that this uses specific colors, the easiest way to build the board would be to go from left to right, store the last color value seen, and then when a new color value is encountered, store it in a linked list somewhere and call that the boarder. Then change that pixel that was different black. That should nicely and quickly build the boarder up for you.

Things get much more tricky after that. I'm not entirely sure of the best approach to take.

 

[EagleKeeper]

Most political entities within the US have maps in AutoCad or MicroGrafix format.