algorithm - 二值图像 "Lines-of-Sight"边缘检测

Question

考虑这个二进制图像:

正常的边缘检测算法(如 Canny )将二值图像作为输入并生成以红色显示的轮廓。我需要另一种算法，将点“P”作为第二条输入数据。 “P”是上图中的黑点。该算法应生成蓝色轮廓。蓝色轮廓表示二值图像的“P”点视线边缘。

我搜索了很多实现此目的的图像处理算法，但没有找到。我也试着想过一个新的，但还是有很多困难。

Answer 1

既然你有位图，你可以使用位图算法。

Here's a working example (在 JSFiddle 中或见下文)。 (Firefox、Chrome，但不是 IE)

伪代码:

// 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

起初这听起来很糟糕......但实际上，它是 O(p)，其中 p 是图像中的像素数。

完整代码在这里，最适合整页:

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>