Обнаружение линии прямой видимости на двоичном изображении

Рассмотрим это двоичное изображение: введите описание изображения здесь

Обычный алгоритм обнаружения краев (например, Canny) принимает двоичное изображение в качестве входных данных и приводит к показанному контуру в красном. Мне нужен другой алгоритм, который принимает точку «P» в качестве второй части входных данных. «P» - это черная точка на предыдущем изображении. Этот алгоритм должен привести к синему контуру. Синие контуры представляют точку "P" на линии прямой видимости двоичного изображения.

Я много искал алгоритмы обработки изображений, которые позволяли бы достичь этого, но не нашел. Я тоже пробовал думать о новом, но у меня все еще много трудностей.


person Hesham Eraqi    schedule 14.06.2015    source источник
comment
Как представлены ваши контуры? Это полигоны или растровые изображения?   -  person Kaganar    schedule 06.08.2015
comment
@Kaganar Это растровые изображения.   -  person Hesham Eraqi    schedule 09.08.2015


Ответы (4)


Поскольку у вас есть растровое изображение, вы можете использовать алгоритм растрового изображения.

Вот рабочий пример (в 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>

person Kaganar    schedule 10.08.2015
comment
Если вы хотите получить векторное представление контура, вы можете просто соединить совпадения строк - вы получите что-то очень похожее на то, что предлагает @LouisRicci, но оно будет лучше, чем константа- угол радиальной стреловидности. - person Kaganar; 10.08.2015

Я бы просто оценил контур прямой видимости 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)
person Louis Ricci    schedule 06.08.2015

https://en.wikipedia.org/wiki/Hidden_surface_determination, например, Z-буфер относительно просто. Обнаружение краев выглядит намного сложнее и, вероятно, требует небольшой настройки. Почему бы не взять существующий алгоритм обнаружения краев из библиотеки, которую кто-то настроил, а затем вставить некоторый код Z-буферизации, чтобы вычислить синий контур из красного?

person mcdowella    schedule 14.06.2015

Первый подход

Основная идея

  1. Запустите алгоритм обнаружения краев (Canny должен с этим справиться).
  2. For each contour point C compute the triplet (slope, dir, dist), where:
    • slope is the slope of the line that passes through P and C
    • dir - это бит, который устанавливается, если C находится справа от P (на оси x), и сбрасывается, если он находится слева; он используется для того, чтобы различать точки с одинаковым наклоном, но на противоположных сторонах P
    • dist - это расстояние между P и C.
  3. Классифицируйте набор точек контура так, чтобы класс содержал точки с одним и тем же ключом (slope, dir), и оставьте одну точку из каждого такого класса, имеющую минимум dist. Пусть S будет набором этих ближайших точек.
  4. Отсортируйте S по часовой стрелке.
  5. Пройдите еще раз по отсортированному набору и, если две последовательные точки находятся слишком далеко друг от друга, нарисуйте между ними сегмент, в противном случае просто нарисуйте точки.

Примечания

  • На самом деле вам не нужно вычислять реальное расстояние между P и C, поскольку вы используете dist только для определения ближайшей точки к P на шаге 3. Вместо этого вы можете оставить C.x - P.x в dist. Эта информация также должна сообщить вам, какая из двух точек с одинаковым наклоном ближе всего к P. Кроме того, C.x - P.x проглатывает параметр dir (в знаковом бите). Так что вам dir тоже не особо нужно.

  • Классификация на шаге 3 в идеале может быть выполнена с помощью хеширования (таким образом, с линейным числом шагов), но поскольку числа типа double / float подлежат округлению, вам может потребоваться допустить возникновение небольших ошибок путем округления значений наклонов.

Второй подход

Основная идея

Вы можете выполнить своего рода BFS, начиная с P, например, при попытке определить страну / зону, в которой находится P. Для каждого пикселя посмотрите на пиксели вокруг него, которые уже были посещены BFS (называемые соседями). В зависимости от распределения соседних пикселей, которые находятся в зоне прямой видимости, определите, находится ли текущий посещаемый пиксель в зоне прямой видимости или нет. Вероятно, вы можете применить своего рода оператор свертки к соседним пикселям (как и с любым другим фильтром). Кроме того, вам не обязательно сразу решать, точно ли пиксель находится на линии прямой видимости. Вместо этого вы можете вычислить некоторую вероятность того, что это правда.

Примечания

  • Из-за того, что ваш график представляет собой 2D-изображение, BFS должен быть довольно быстрым (поскольку количество ребер линейно зависит от количества вершин).
  • Этот второй подход устраняет необходимость запускать алгоритм обнаружения края. Кроме того, если страна / зона, в которой находится P, значительно меньше, чем изображение, общая производительность должна быть лучше, чем запуск только алгоритма обнаружения границ.
person cobarzan    schedule 06.08.2015