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

Question

考虑这个二值图像：

正常的边缘检测算法（如Canny）将二值图像作为输入，结果为红色所示的轮廓。我需要另一种算法，将点 "P" 作为第二条输入数据。 "P"是上一张图中的黑点。该算法应生成蓝色轮廓。蓝色轮廓代表点 "P" 二值图像的视线边缘。

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

Answer 1

https://en.wikipedia.org/wiki/Hidden_surface_determination 例如Z 缓冲区相对容易。边缘检测看起来要复杂得多，可能需要一些调整。为什么不从其他人调整过的库中获取现有的边缘检测算法，然后插入一些 Z 缓冲代码来根据红色计算蓝色轮廓？

Answer 2

我只想用光线碰撞来估计 P 的视线轮廓。

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)

Answer 3

第一种方法

主要思想

运行一种边缘检测算法（Canny 应该做得很好）。
对于每个轮廓点 C 计算三元组 (slope, dir, dist)，其中：
- slope是通过P和C的直线的斜率
- dir 是一个位，如果 C 在 P 的右侧（在 x 轴上），如果在左侧则重置;它用于区分具有相同斜率但在 P
- dist 是 P 和 C 之间的距离。
对轮廓点集进行分类，使得 class 包含具有相同键值 (slope, dir) 的点，并保留每个 class 具有最小值 [=20] 的点=].设 S 为这些最近点的集合。
按顺时针顺序对 S 进行排序。
再次遍历排序集，每当两个连续的点相距太远时，在它们之间画一条线段，否则只画点。

备注

你真的不需要计算 P 和 C 之间的实际距离，因为你只使用 dist 来确定离 [= 最近的点13=] 在第 3 步。您可以将 C.x - P.x 保留在 dist 中。这条信息还应该告诉你斜率相同的两个点中哪一个最接近 P。此外，C.x - P.x 吞没了 dir 参数（在符号位中）。所以你也不需要dir。
第 3 步中的 class 化可以理想地通过散列来完成（因此，以线性步数），但是由于 doubles/floats 会四舍五入，您可能需要通过四舍五入斜率的值来允许出现小错误。

第二种方法

主要思想

您可以从 P 开始执行某种 BFS，例如在尝试确定 P 所在的 country/zone 时。对于每个像素，查看它周围的像素BFS 已经访问过的（称为邻居）。根据视线内相邻像素的分布情况，判断当前访问的像素是否也在视线内。您可能可以在相邻像素上应用一种卷积运算符（与任何其他过滤器一样）。此外，您真的不需要立即决定某个像素是否确实在视线内。您可以改为计算它为真的概率。

备注

由于您的图形是二维图像，BFS 应该非常快（因为边数与顶点数成线性关系）。
第二种方法消除了运行边缘检测算法的需要。此外，如果 country/zone P 所在的区域比图像小得多，则整体性能应该优于运行单独使用边缘检测算法。

Answer 4

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

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>

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

Binary Image "Lines-of-Sight" Edge Detection

algorithm

image-processing

edge-detection