Binary Image "Lines-of-Sight" Edge Detection

Question

Consider this binary image:

A normal edge detection algorithm (Like Canny) takes the binary image as input and results into the contour shown in red. I need another algorithm that takes a point "P" as a second piece of input data. "P" is the black point in the previous image. This algorithm should result into the blue contour. The blue contours represents the point "P" lines-of-sight edge of the binary image.

I searched a lot of an image processing algorithm that achieve this, but didn't find any. I also tried to think about a new one, but I still have a lot of difficulties.

Answer 1

Since you've got a bitmap, you could use a bitmap algorithm.

Here's a working example (in JSFiddle or see below). (Firefox, Chrome, but not IE)

Pseudocode:

// part 1: occlusion
mark all pixels as 'outside'
for each pixel on the edge of the image
    draw a line from the source pixel to the edge pixel and
    for each pixel on the line starting from the source and ending with the edge
        if the pixel is gray mark it as 'inside'
        otherwise stop drawing this line

// part 2: edge finding
for each pixel in the image
    if pixel is not marked 'inside' skip this pixel
    if pixel has a neighbor that is outside mark this pixel 'edge'

// part 3: draw the edges
highlight all the edges

At first this sounds pretty terrible... But really, it's O(p) where p is the number of pixels in your image.

Full code here, works best full page:

var c = document.getElementById('c');
c.width = c.height = 500;
var x = c.getContext("2d");

//////////// Draw some "interesting" stuff ////////////
function DrawScene() {
    x.beginPath();
    x.rect(0, 0, c.width, c.height);
    x.fillStyle = '#fff';
    x.fill();

    x.beginPath();
    x.rect(c.width * 0.1, c.height * 0.1, c.width * 0.8, c.height * 0.8);
    x.fillStyle = '#000';
    x.fill();
    
    x.beginPath();
    x.rect(c.width * 0.25, c.height * 0.02 , c.width * 0.5, c.height * 0.05);
    x.fillStyle = '#000';
    x.fill();

    x.beginPath();
    x.rect(c.width * 0.3, c.height * 0.2, c.width * 0.03, c.height * 0.4);
    x.fillStyle = '#fff';
    x.fill();

    x.beginPath();
    var maxAng = 2.0;
    function sc(t) { return t * 0.3 + 0.5; }
    function sc2(t) { return t * 0.35 + 0.5; }
    for (var i = 0; i < maxAng; i += 0.1)
        x.lineTo(sc(Math.cos(i)) * c.width, sc(Math.sin(i)) * c.height);
    for (var i = maxAng; i >= 0; i -= 0.1)
        x.lineTo(sc2(Math.cos(i)) * c.width, sc2(Math.sin(i)) * c.height);
    x.closePath();
    x.fill();

    x.beginPath();
    x.moveTo(0.2 * c.width, 0.03 * c.height);
    x.lineTo(c.width * 0.9, c.height * 0.8);
    x.lineTo(c.width * 0.8, c.height * 0.8);
    x.lineTo(c.width * 0.1, 0.03 * c.height);
    x.closePath();
    x.fillStyle = '#000';
    x.fill();
}

//////////// Pick a point to start our operations: ////////////
var v_x = Math.round(c.width * 0.5);
var v_y = Math.round(c.height * 0.5);

function Update() {
    if (navigator.appName == 'Microsoft Internet Explorer'
        ||  !!(navigator.userAgent.match(/Trident/)
        || navigator.userAgent.match(/rv 11/))
        || $.browser.msie == 1)
    {
        document.getElementById("d").innerHTML = "Does not work in IE.";
        return;
    }
    
    DrawScene();

    //////////// Make our image binary (white and gray) ////////////
    var id = x.getImageData(0, 0, c.width, c.height);
    for (var i = 0; i < id.width * id.height * 4; i += 4) {
        id.data[i + 0] = id.data[i + 0] > 128 ? 255 : 64;
        id.data[i + 1] = id.data[i + 1] > 128 ? 255 : 64;
        id.data[i + 2] = id.data[i + 2] > 128 ? 255 : 64;
    }

    // Adapted from http://rosettacode.org/wiki/Bitmap/Bresenham's_line_algorithm#JavaScript
    function line(x1, y1) {
        var x0 = v_x;
        var y0 = v_y;
        var dx = Math.abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
        var dy = Math.abs(y1 - y0), sy = y0 < y1 ? 1 : -1; 
        var err = (dx>dy ? dx : -dy)/2;

        while (true) {
            var d = (y0 * c.height + x0) * 4;
            if (id.data[d] === 255) break;
            id.data[d] = 128;
            id.data[d + 1] = 128;
            id.data[d + 2] = 128;

            if (x0 === x1 && y0 === y1) break;
            var e2 = err;
            if (e2 > -dx) { err -= dy; x0 += sx; }
            if (e2 < dy) { err += dx; y0 += sy; }
        }
    }

    for (var i = 0; i < c.width; i++) line(i, 0);
    for (var i = 0; i < c.width; i++) line(i, c.height - 1);
    for (var i = 0; i < c.height; i++) line(0, i);
    for (var i = 0; i < c.height; i++) line(c.width - 1, i);
    
    // Outline-finding algorithm
    function gb(x, y) {
        var v = id.data[(y * id.height + x) * 4];
        return v !== 128 && v !== 0;
    }
    for (var y = 0; y < id.height; y++) {
        var py = Math.max(y - 1, 0);
        var ny = Math.min(y + 1, id.height - 1);
                    console.log(y);

        for (var z = 0; z < id.width; z++) {
            var d = (y * id.height + z) * 4;
            if (id.data[d] !== 128) continue;
            var pz = Math.max(z - 1, 0);
            var nz = Math.min(z + 1, id.width - 1);
            if (gb(pz, py) || gb(z, py) || gb(nz, py) ||
                gb(pz, y) || gb(z, y) || gb(nz, y) ||
                gb(pz, ny) || gb(z, ny) || gb(nz, ny)) {
                id.data[d + 0] = 0;
                id.data[d + 1] = 0;
                id.data[d + 2] = 255;
            }
        }
    }

    x.putImageData(id, 0, 0);

    // Draw the starting point
    x.beginPath();
    x.arc(v_x, v_y, c.width * 0.01, 0, 2 * Math.PI, false);
    x.fillStyle = '#800';
    x.fill();
}

Update();

c.addEventListener('click', function(evt) {
    var x = evt.pageX - c.offsetLeft,
        y = evt.pageY - c.offsetTop;
    v_x = x;
    v_y = y;
    Update();
}, false);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.2.3/jquery.min.js"></script>
<center><div id="d">Click on image to change point</div>
<canvas id="c"></canvas></center>

Answer 2

I would just estimate P's line of sight contour with ray collisions.

RESOLUTION = PI / 720;
For rad = 0 To PI * 2 Step RESOLUTION
  ray = CreateRay(P, rad)
  hits = Intersect(ray, contours)
  If Len(hits) > 0
    Add(hits[0], lineOfSightContour)