CODEWITHSUNDEEP
c#imagevectorpolygons
Giulio Zausa
Giulio Zausa

Reputation: 231

Converting Pixels to Polygons

I have an satellite image and I want to get all greens area. In pratice i need to load the image from a bmp, select one color and tollerance and get many polygons that are the green areas in the photo. How i can do this in C#? (i need this for Flight Simulations)

Upvotes: 1

Views: 5091

Answers (3)

Wolf5370
Wolf5370

Reputation: 1374

Use LockBits and iterate through each byte (depending on pixel format - indexed images use palette so you would need to interrogate that first to get the palette indexes that are within your tolerance range - for non indexed (and non 1bpp/16ppgreyscale) you can access the colour channels directly - see GDI+ FAQ for help here). Each coloured pixel in your range can either be written out directly to another image (i.e. only pixels you want - rest are filled with invisible pixels - Alpha 0) - or into a collection. Personally I would do the former first. This is very quick (if you use LockBits). Then its a matter of using edge detection of pixel walking alogorithms to calculate "shards" (irregular polygons if you like). AForge library may well help you here.

Upvotes: 1

KeithS
KeithS

Reputation: 71573

Hmm. Sounds like a "magic wand" algorithm (from the control in PhotoShop/PSP with that name, allowing you to click one pixel to select all adjacent pixels within a certain color threshold).

So, the first step would be to select a pixel on the bitmap identified as "green" that should be part of your polygon. Then, you can recursively move left, right, up and down from that point, and test to see if the pixel at that point is within the threshold limits you set from the original pixel's color. Add the point to a collection if it's within the threshold and NOT already in the collection, and keep traversing; if the point is not "green enough", or has already been mapped, return. There are ways to limit "backtracking", by limiting the directions that subsequent recursive calls can traverse. For instance, say we made four calls, to travel up, down, left and right. The call that travels left from the "origin" can from that point only make further calls that travel left or up.

Now you have a set of pixels, roughly corresponding to a set of geometric points. You must then identify the subset of these points that define the borders of your polygon. This is known as computing the "convex hull" of these points, and Wikipedia has many algorithms that can be implemented in C#: http://en.wikipedia.org/wiki/Convex_hull_algorithms.

The easiest to understand is probably the Graham Scan: With all the points arranged in a list, start at the first point (A), draw a line to the second (B), and then determine whether a line from B to the third point (C) would constitute a "left turn" or "right turn" from the direction from A to B. If it would be a "left turn", make the turn by drawing the line from B to C, and then compare that line to a line from C to D as before. If it would be a "right turn", then forget B as a possible vertex of the convex hull, draw from A to C, then check to see if the line C to D is a left turn. Whenever you see a "right turn", disregard the current "middle point" of the three points defining the lines and instead trace a line between the other two. Continue, wrapping around the list from the last point back to A, until the points define a series of lines that all make "left turns" from the direction of the last line. This is the "convex hull" of the set of points, and it can be done on any list of points in NlogN time.

Understand that a "convex hull" will be exactly that; you can never get a concave shape (like a star) from it. If this is important, you'll need a tweak of the algorithm to allow some "right turns" but to not allow any line segments to cross.

Upvotes: 1

Kendall Frey
Kendall Frey

Reputation: 44366

Well, the first step is to figure out if a given pixel is within the region or not. That I think is quite straightforward. You can then create regions of pixels that are 'on' or 'off'.

Then you need to convert pixels to polygons. How to do that depends on the granularity you need. If you want high accuracy, you can use Marching Squares to get polygons from your regions. If you need simple polygons, you will need a more advanced method to trace the borders.

Upvotes: 2

Related Questions