Find The Length of a Coastline - Programming - Part 1

Fri, 12/15/2017 - 21:17

About a week ago I wrote an article where I hypothesized that I could find the length of a coast-line using an algorithm based on a map or satellite image.

check nearest pixel colors right

So, in good form, I decided to actually give it a try. I grabbed a screenshot of the British Isle's from Google Maps, taking note of the maps scale and compared it to the size of a single pixel of the resulting image when I zoomed in. The scale appears to be around 1 pixel for every 2 miles. 

The first step I am taking is to try to remove the text from the image. This is a little difficult to get just right because of aliasing*. It's actually working quite well. I was surprised.

It's not perfect just yet but, it might not have to be.

The algorithm loops all the pixels in the image and for dark pixels ,lines and text etc...it attempts to find the nearest alternate color to replace the text. It does this by looking to the surrounding pixels. It loops pixels within a distance of X (currently 5), above, below and on both sides of the pixel. The program counts each individual occurrence of a color and assigns the target pixel the color most common. It's not perfect, but it does seem to work..."pretty good".

I wrote the algorithm in Javascript and as usual I am using Wes Mantooth as a base to make things faster to build.

This is only the first step. Next I will need to:

  1. Reduce the overall color depth
  2. Account for lakes (probably using the same method as removing text or something similar)
  3. Write the algorithm to get the outline of the coast
  4. I think I might also write an algorithm get only Great Britain.
    1. Either a hack that removes pixel areas that are distance X from markers
    2. Determine the largest land mass by pixel count that is NOT water
  5. Count the pixels in the outline

For the island finding algorithm the second choice is the better choice I think, even though it would be the more difficult to implement. 

The first option would be a bit of a hack. I would set a number of pixels as markers on the map. The loop would check the distance of the current pixel to the marker and if its distance were close enough the pixel would be replaced with water. This would require an extra calculation to get the distance from point to point with each loop taking up resources. Also, it wouldn't be dynamic. In my opinion it's always better to write a program with broader usage than a specific task. 

The second option would simply count non-water pixels in a section. The largest section would be assumed to be the target. Everything else would be discarded.

The first option does have it's usefulness because it might make sense to target specific areas instead of allowing the program to decide for itself what to target...But, at least in this case I will be going with option two.

The current source for removing the labels is posted below and the resulting image before and after below that.

And here is a live demo.

 

 

const   W = 807,
                H = 807
        window.onload = function() {

            'use strict';
            
            var i = $w.add_object_single(
                1,
                Map,{
                    src:'1pixel2miles.bmp',
                    w:W,
                    h:H
                },
                document.getElementById('target'),
                W,H
            );
        }
        /**
         * Object
         * 
         * @param {Object}
         * @returns {Void}
         * */
        var Map = function(o){
            // SET WATER AS A CONSTANT
            this.water = [202,232,255,255];
            
            // set the width / height of the image
            this.w = o.w;
            this.h = o.h;
            // get the reference to the canvas
            this.i = o.i;
            // create an image object
            var img = new Image();
            img.src = o.src;
            // 
            var $this = this;
            // when the image has been loaded
            img.onload = function() {
                // get the canvas context
                var ctx = $w.canvas.get(o.i,'ctx');
                // draw the image
                ctx.drawImage(img, 0, 0);
                // get the image pixel colors as a two-dimensional array
                var p = $this.getData(ctx);
                // loop the pixels and act on them
                p = $this.loopPixels(p,ctx);
            }
            
        }
        /**
         * get the image data from the canvas
         * @param {Object}
         * @returns {Array}
         * */
        Map.prototype.getData = function(ctx){
            // Create an ImageData object.
            var imgd = ctx.getImageData(0,0,this.w,this.h);
            var pix = imgd.data;
            var x = 0, y = 0;
            var pixels = [[]];
            // Loop over each pixel and set a transparent red.
            for (var i = 0; n = pix.length, i < n; i += 4) {
                pixels[y][x] = [pix[i],pix[i+1],pix[i+2],pix[i+3]];
                x++;
                if (x == this.w) {
                    x = 0;
                    y++;
                    pixels[y] = [];
                }
            }   
            return pixels;
        }
        /**
         * loop all the pixels and run action as necessary
         * @param {Array}
         * @returns {Array}
         * */
        Map.prototype.loopPixels = function(p,ctx) {
            for (var y = 0; y<this.h;y++) {
                for (var x = 0; x<this.w;x++) {
                    // if color close to black
                    // change it to the nearest color
                    if(p[y][x][0] < 144 && p[y][x][1] < 144 && p[y][x][2] < 144) {
                        p[y][x] = this.nearestPixel(p,y,x,147,162,173);
                        ctx.fillStyle=$w.color.rgbToHex(p[y][x][0],p[y][x][1],p[y][x][2]);
                        ctx.fillRect(x,y,1,1);
                    }
                    // lets do a second pass
                    if(p[y][x][0] < 163 && p[y][x][1] < 163 && p[y][x][2] < 163) {
                        p[y][x] = this.nearestPixel(p,y,x,147,162,173,250);
                        ctx.fillStyle=$w.color.rgbToHex(p[y][x][0],p[y][x][1],p[y][x][2]);
                        ctx.fillRect(x,y,1,1);
                    }
                }   
            }
            return p;
        }
        /**
         * get the most common color within a range of nine pixels
         * @param {Array}
         * @param {Number}
         * @param {Number}
         * @param {Number} 0-255
         * @param {Number} 0-255
         * @param {Number} 0-255
         * @returns {Array}
         * */
        Map.prototype.nearestPixel = function(p,y,x,r,g,b){
                // @param {Object}
            var c = {},
                // @param {Number} how many surrounding pixels to look
                l = 5;
            /**
             * look at the adjoining pixels to get the most common pixel color
             *
             * #####
             * ##X##
             * #####
             *
             * */
            for(var yy=y-l;yy<y+l;yy++) {
                for(var xx=x-l;xx<x+l;xx++){
                    // if this is not black
                    if(p[yy][xx][0] > r && p[yy][xx][1] > g && p[yy][xx][2] > b) {
                        var q = p[yy][xx][0]+p[yy][xx][1]+p[yy][xx][2];
                        // increment a count of the color of this pixel
                        if (typeof c[q] === 'undefined') {
                            c[q] = {
                                c:p[yy][xx],
                                i:1
                            };
                        }else{
                            c[q].i++;
                        }
                    }
                }
            }
            // @param {Object}
            var max = {
                i:0,
                c:null
            }
            // loop the colors to see which is the most common
            for(var i in c) {
                if (c.hasOwnProperty(i)) {
                    // if this color was found more often than max then replace it
                    if(c[i].i > max.i) {
                        max.i = c[i].i
                        max.c = c[i].c;
                    }
                }
            }
            return max.c;
        }

* aliasing is blurring and or transparency added surrounding subjects of bitmap images generally to blend the image more seamlessly with the background however, in some cases aliasing is a result of compression as is often the case with JPEG

 

Tags
Image
remove text algorithm before and after