Line of sight binary image Edge detection

Question

Consider this binary image:

The normal edge detection algorithm (e.g. Canny ) takes the binary image as input and the results into the outline shown in red. I need another algorithm that takes a “P” point as the second part of the input. "P" is the black dot in the previous image. This algorithm should lead to a blue outline. The blue outlines represent the “P” point of the lines of the visible edge of the binary image.

I searched for a lot of image processing algorithms that achieved this, but did not find. I also tried to think of a new one, but I still have a lot of difficulties.

Answer 1

Since you have a bitmap, you can use a bitmap algorithm.

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

pseudo code:

// 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 it sounds pretty awful ... But actually it is O(p) , where p is the number of pixels in your image.

The full code here works best on the 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 appreciate the contour of the straight line P 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) 

Answer 3

https://en.wikipedia.org/wiki/Hidden_surface_determination e.g. Z-buffer is relatively simple. Edge detection looks a lot more complicated and probably needs some tweaking. Why not take an existing border detection algorithm from a library that someone else hasn't configured, and then insert some Z-buffering code to calculate the blue outline from red?

Answer 4

First approach

main idea

• Run the edge detection algorithm (Canny should do it just fine).
• For each point in path C compute the triplet (slope, dir, dist) , where:
  • slope is the slope of a line passing through P and C
  • dir - a bit that is set if C is to the right of P (on the x axis) and reset if it is on the left; it was used to distinguish points that have the same slope, but from opposite sides of P
  • dist is the distance between P and C
• Classify a set of contour points in such a way that the class contains points with the same key (slope, dir) and stores one point from each such class with a minimum value of dist . Let S be the set of these nearest points.
• Sort S clockwise.
• Iterate through the sorted set again, and when two adjacent points are too far apart, draw a segment between them, otherwise just draw the points.

Notes

• You really don't need to calculate the real distance between P and C , since you only use dist to determine the closest point to P in step 3. Instead, you can save Cx - Px to dist . This information should also indicate which of the two points with the same slope is closest to P In addition, Cx - Px swallows the dir parameter (in the sign bit). So you really don't need dir .

• The classification in step 3 could ideally be accomplished by hashing (thus, in a linear number of steps), but since double / floating elements are rounded, you may need to resolve small errors by rounding slope values.

Second approach

main idea

You can execute some sort of BFS starting with P , for example, when trying to determine the country / zone in which P is located. For each pixel, look at the pixels around it that have already been visited by the BFS (called neighbors). Depending on the distribution of neighboring pixels that are on the line of sight, determine whether the current visited pixel in the line of sight is too much or not. You can probably apply a kind of convolution operator on neighboring pixels (for example, with any other filter). In addition, you do not need to immediately decide whether the pixel is correctly in line of sight. You could calculate some probability that this is true.

Notes

• Due to the fact that your graph is a two-dimensional image, BFS should be quite fast (since the number of edges is linear in the number of vertices).
• This second approach eliminates the need to run a boundary detection algorithm. In addition, if country / zone P is significantly smaller than the image, the overall performance should be better than performing the edge detection algorithm exclusively.