2d:null 2e:["$","title",null,{"children":"Image Processing Algorithms | Neil Turley | Observable"}] 33:T401,md`# Image Processing Algorithms High level reasoning about the world (even simulated worlds) is a difficult problem. The physical world is a messy place and while human perception is very capable of simplifying messy samples of physical stimulus and turning that into abstract higher level models, this is more complicated to teach to a computer. This notebook explores a few algorithms that are useful in turning a grid of boolean values into higher level models of what that grid of data represents. This is useful in robotics, game AI, vision processing, etc. ## Boundary Tracing [Boundary Tracing](https://en.wikipedia.org/wiki/Boundary_tracing) or Contour tracing is searching around the image data to identify the outline of the shape. We use Dr. Kovalevsky algorithm here, which basically is to sweep across the image looking for any black pixels. Then follow the outer edge of the black boxes until we arrive back at the start point. This is similar to what potrace does. Click on the boxes to change the shape `34:T7f5,{ const margin = -22; const posScale = 30; const boxSize = 20; const boxGap = posScale - boxSize; const pathOffset = boxSize + boxGap/2 + margin; let boxes = testShape.map((row, y) => row.map((cell, x) => { let rect = svg``; rect.onclick = () => { mutable testShape[y][x] = testShape[y][x]?0:1; mutable testShape = mutable testShape; }; return rect; }) ).flat(); return html``; }35:T530,md`## Voronoi Tessalation Sometimes for processing the shape of a polygon it's useful to build a skeleton of paths along the interior of the shape. This can be helpful for further analyisis. For example, if you are trying to recognize letters in an optical character recognition type of application. This also reduces the polygon to a simpler model that can efficiently leverage theory and algorithms from graph theory. For instance if this shape represents on overhead map of walkable areas, this can leverage path finding algorithms like A* to find a path that avoids walls and barriers. Voronoi Diagrams take a set of points (called generators) and subdivide the plane into cells that represent the region of the plane where all points in the region are closest to the same generator. The cell edges represent lines that are equidistant to two generators. The point where two cell edges intersect is a point that is equidistant from three points. That point is called a circumcenter. Each circumcenter has a radius which is the distance from it to the nearest three generators. If we filter out circumcenters and edges that go outside of our polygon we are left with a set of points and lines between them and the lines tend to follow the middle of the paths through our shape and lead into each corner that it can find. `36:T5d8,{ let canvas = document.createElement('canvas'); canvas.width = image.width; canvas.height = image.height; let context = canvas.getContext('2d') //context.drawImage(image, 0, 0, image.width, image.height); //let distMap = _.cloneDeep(passMap) let distMap = [] for (let y in passMap) { let row = [] for (let x in passMap[0]) { row.push( passMap[y][x] * 255) } distMap.push(row) } let flood = (x, y) => { let ret = [] let dps = [[{dx:1,dy:0},{dx:0,dy:1},{dx:-1,dy:0}, {dx:0,dy:-1}], [{dx:1,dy:1},{dx:1,dy:-1},{dx:-1,dy:1},{dx:-1,dy:-1}]] let dist = [1,1.7] for (let i=0; i<2;i++) { for (let dp of dps[i]) { if (passMap[y+dp.dy][x+dp.dx] && distMap[y+dp.dy][x+dp.dx] > distMap[y][x]+dist[i]*18) { distMap[y+dp.dy][x+dp.dx] = distMap[y][x]+dist[i]*18 ret.push({x:x+dp.dx,y:y+dp.dy}) } } } return ret } for (let trace of scTraces) { for (let point of trace) { distMap[point.y][point.x] = 1 let q = [{x:point.x, y:point.y}] while(q.length > 0) { let n = q.pop() q = q.concat(flood(n.x, n.y)) } } } for (let y in passMap) { for (let x in passMap[0]) { if (distMap[y][x]) { context.fillStyle = `rgb(255,${ distMap[y][x] }, 0)`; context.fillRect(x, y, 1, 1) } } } canvas.style.width ='500px'; canvas.style.imageRendering= 'pixelated'; return canvas }37:T443,{ let width = 600 let height = 200 let x = d3.scaleBand() .domain(d3.range(histogram.length)) .range([0, width]) let y = d3.scaleLinear() .domain([0, d3.max(histogram)]) .range([0, 300]) const svg = d3.create("svg") .attr("width", width) .attr("height", height+30) const bar = svg.selectAll("g") .data(histogram) .join("g") .attr("transform", (d, i) => `translate(${x(i)}, ${height-y(d)})`); bar.append("rect") .attr("fill", (d, i) => { return (cluster_ranges2.find(c => i*5 <= c.max && i*5 >= c.min) || {'color':'black'}).color }) .attr("width", x.bandwidth()) .attr("height", y) svg.append('text') .attr('y', height + 20) .attr('x', x(2)) .text((2-1)*5) svg.append('text') .attr('y', height + 20) .attr('x', x(20)) .text((20-1)*5) svg.append('text') .attr('y', height + 20) .attr('x', x(34)) .text((34-1)*5) svg.append('text') .attr('y', height + 20) .attr('x', x(49)) .text((49-1)*5) return svg.node(); }38:T592,{ let posScale=1 let pathOffset=0 let lastPoint = nextSteps2.length-1; let point2 = _.maxBy(simpleChest[0], p => p.x+p.y); let point = _.maxBy(simpleChest[1], p => -p.x+p.y); let mid = Math.floor((_.maxBy(simpleChest[0], p => p.x).x+_.minBy(simpleChest[1], p => p.x).x)/2); let midRow = _.findIndex(chestGrayScale.map(row => row[mid]), v => v>167) let near = _.minBy(simpleChest[0], p => (p.x-mid)*(p.x-mid) + (p.y -midRow)*(p.y-midRow)) let near2 = _.minBy(simpleChest[1], p => (p.x-mid)*(p.x-mid) + (p.y -midRow)*(p.y-midRow)) return html` ` }39:T54c,getNextPos = function(last, shape) { if (last.dir == 'right') { let next = {x:last.x+1, y:last.y} let topVal = shape[next.y][next.x]; if (shape[next.y][next.x+1] != topVal) return {x:next.x, y:next.y, dir:'up'}; if (shape[next.y+1][next.x+1] != topVal) return {x:next.x, y:next.y, dir:'right'}; return {x:next.x, y:next.y, dir:'down'}; } if (last.dir == 'down') { let next = {x:last.x, y:last.y+1} let topVal = shape[next.y][next.x]; if (shape[next.y+1][next.x+1] == topVal) return {x:next.x, y:next.y, dir:'right'}; if (shape[next.y+1][next.x] != topVal) return {x:next.x, y:next.y, dir:'left'}; return {x:next.x, y:next.y, dir:'down'}; } if (last.dir == 'left') { let next = {x:last.x-1, y:last.y} let topVal = shape[next.y][next.x+1]; if (shape[next.y+1][next.x] == topVal) return {x:next.x, y:next.y, dir:'down'}; if (shape[next.y][next.x] != topVal) return {x:next.x, y:next.y, dir:'up'}; return {x:next.x, y:next.y, dir:'left'}; } if (last.dir == 'up') { let next = {x:last.x, y:last.y-1} let bottomRightVal = shape[next.y+1][next.x+1]; if (shape[next.y][next.x] == bottomRightVal) return {x:next.x, y:next.y, dir:'left'}; if (shape[next.y][next.x+1] != bottomRightVal) return {x:next.x, y:next.y, dir:'right'}; return {x:next.x, y:next.y, dir:'up'}; } }3a:[{"id":"46996788aca3bd7a304175101f4ff794b4bb174013107600e950b11e251e970efd22c9b917b4f0cc3f4270965ed0fd218a140dbeb7f402c3cae28698043999af","href":"https://static.observableusercontent.com/files/46996788aca3bd7a304175101f4ff794b4bb174013107600e950b11e251e970efd22c9b917b4f0cc3f4270965ed0fd218a140dbeb7f402c3cae28698043999af","name":"path.png","type":"image/png","lastModified":1583612896775.708,"size":2169},{"id":"05addab2f9cc7feddb1c67c91dd5b94bfb6d4873d231f8d6daa72b58b4f2589d7b9c725b0472f0e29701ee7b32d2a0b1ef84b7b532c7f153f9789ab70747358f","href":"https://static.observableusercontent.com/files/05addab2f9cc7feddb1c67c91dd5b94bfb6d4873d231f8d6daa72b58b4f2589d7b9c725b0472f0e29701ee7b32d2a0b1ef84b7b532c7f153f9789ab70747358f","name":"00000001_000.png","type":"image/png","lastModified":1584832004839.408,"size":457171}] 31:{"id":"4de349b468851bfe","slug":"bitmap-vectorization-algorithm","title":"Image Processing Algorithms","thumbnail":"98c22a8e58add805ae03018029c350bf82032508ff9c09e0d9d2e47042b702b5","access_level":"public","create_time":"$D2020-02-23T19:38:04.529Z","update_time":"$D2021-01-11T04:21:25.191Z","view_time":null,"first_public_time":"$D2020-02-24T14:13:04.264Z","has_unpublished_edits":null,"fork":false,"stars":11,"starred":false,"owner":{"type":"team","id":"d3a5c7e199005588","login":"nturley","name":"Neil Turley","avatar_url":"https://avatars-next.observableusercontent.com/1144dcde8da195bed152315b9c34a7cd1cc33f52ca513a9b8582d9a077aff812","tier":"starter_2024"},"version":2061,"publish_version":2061,"role":null,"authored":false,"authors":[{"type":"individual","id":"08c0e1b672bab3d7","login":"nturley","name":"Neil Turley","avatar_url":"https://avatars-next.observableusercontent.com/1144dcde8da195bed152315b9c34a7cd1cc33f52ca513a9b8582d9a077aff812","tier":null}],"members":[{"type":"individual","id":"08c0e1b672bab3d7","login":"nturley","name":"Neil Turley","avatar_url":"https://avatars-next.observableusercontent.com/1144dcde8da195bed152315b9c34a7cd1cc33f52ca513a9b8582d9a077aff812","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":null,"type":"notebook","body":{"title":"Image Processing Algorithms","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":546,"value":"md`## Traced Polygon`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":488,"value":"{\n const margin = -22;\n const posScale = 30;\n const boxSize = 20;\n const boxGap = posScale - boxSize;\n const pathOffset = boxSize + boxGap/2 + margin;\n return html``\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":485,"value":"md`\n## Line Simplification\n\nFor many applications polygons with this much resolution can be a lot of data and this can slow down performance for subsequent algorithms, so often we would like to reduce the representation to something simpler. [Line simplification](https://bost.ocks.org/mike/simplify/) is the process of removing points from a polyline or polygon without changing the overall shape too much. We'll use an algorithm called [Ramer-Douglas-Peucker](https://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm) or split and merge.\n\nIf the error threshold is zero then we only remove points that are colinear with both of it's neighbors, if we set the threshold very high then we distort the image beyond recognition.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":585,"value":"viewof errorThreshold = slider({max: 3, value:0, description:\"Error Threshold\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":563,"value":"{\n const margin = -22;\n const posScale = 30;\n const boxSize = 20;\n const boxGap = posScale - boxSize;\n const pathOffset = boxSize + boxGap/2 + margin;\n return html``\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":668,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":622,"value":"{\n const margin = -22;\n const posScale = 30;\n const boxSize = 20;\n const boxGap = posScale - boxSize;\n const pathOffset = boxSize + boxGap/2 + margin;\n return html`\n `\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":794,"value":"md`To further simplify the model, we can filter out some of these points with only one neighbor whose radius is less than some amount. We can also filter out points whose neighbors are colinear.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":853,"value":"md`# More Complex Example\nOften we are working with much higher resolution than 5x9 pixels. So let's try the above algorithms on a little bit bigger image size. This is a passability map from the game Starcraft 2. It is ${image.width}px by ${image.height}px\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":851,"value":"image = FileAttachment(\"path.png\").image()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":916,"value":"md`## Trace Outlines`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":890,"value":"{\n let canvas = document.createElement('canvas');\n canvas.width = image.width;\n canvas.height = image.height;\n let context = canvas.getContext('2d')\n context.drawImage(image, 0, 0, image.width, image.height);\n let colors = ['red','orange','yellow', 'green', 'purple']\n let tnum = 0\n for (let t of scTraces) {\n context.fillStyle = colors[tnum % colors.length];\n for (let p of t) {\n context.fillRect(p.x, p.y, 1, 1)\n }\n tnum+=1;\n }\n \n canvas.style.width ='400px';\n canvas.style.imageRendering= 'pixelated';\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1098,"value":"md`## Vectorize`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":923,"value":"viewof errorThreshold2 = slider({max: 3, value:0.5, description:\"Error Threshold\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1092,"value":"{\n let posScale=3\n let pathOffset=0\n let lastPoint = nextSteps2.length-1;\n return html`\n\n`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1119,"value":"md`# Voronoi\nAs you can see below, Voronoi produces okayish results in many cases but there are some parts where the voronoi diagram has produced unacceptably bad errors. Some of them are due to points of the polygon that are too far apart and so the voronoi edges no longer form a path that stays in the boundaries of the polygon. Also removing voronoi edges that are not completely in the passable area is computationally expensive and my implementation still has errors because there are still places where the bluelines cross over black lines.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":985,"value":"{\n let posScale=3\n let pathOffset=0\n return html`\n\n`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1155,"value":"md` ## Altitude Map\nAn alternative to voronoi is to use a variant of flood fill to create an altitude map. The \"altitude\" of each pixel represents the distance to the nearest edge. This is similar to a discrete voronoi where each local maxima is equivalent to the voronoi circumcenter. Floodfill algorithms are quite cheap and the discrete voronoi doesn't suffer from the errors that we saw in the previous example. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1161,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1292,"value":"md`# Medical Imagery\nSmall grids and game passability maps are still artificial. Also, the real world doesn't tend to be binary, it tends to be varying quantities of some physical measurement. Let's take an image recorded from reality. A chest X-ray. Traditional chest X-ray images are light where the X-rays are absorbed and dark where they pass through. Bone and fluid tend to absorb X-rays and will appear white, whereas soft tissue and air will appear dark.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1298,"value":"chestImage = {\n let im = await FileAttachment('00000001_000.png').image()\n im.style.height = '200px'\n return im\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1959,"value":"md` I'm not doctor, but from what I understand, chest X-rays can show that there is some type of fluid in the lungs which could be indicative of pneumonia. They can also show that the heart is too large (cardiomegaly) which can be caused by high blood pressure, or heart valve disease.\n\nIn order to reason about this chest X-ray, we need to find the features of interest. Namely the lungs and heart. Breaking up an image into it's constituent features is called [segmentation](https://en.wikipedia.org/wiki/Image_segmentation).\n\n## Clustering\n\nOne of the ways we can pick out features is by grouping pixels that are a similar color. Let's take a look at the distribution of color on this image to see if there are any clusters of colors.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2053,"value":"{\n let width = 600\n let height = 200\n let x = d3.scaleBand()\n .domain(d3.range(histogram.length))\n .range([0, width])\n let y = d3.scaleLinear()\n .domain([0, d3.max(histogram)])\n .range([0, 300])\n const svg = d3.create(\"svg\")\n .attr(\"width\", width)\n .attr(\"height\", height+30)\n \n const bar = svg.selectAll(\"g\")\n .data(histogram)\n .join(\"g\")\n .attr(\"transform\", (d, i) => `translate(${x(i)}, ${height-y(d)})`);\n\n bar.append(\"rect\")\n .attr(\"fill\", \"steelblue\")\n .attr(\"width\", x.bandwidth())\n .attr(\"height\", y)\n \n svg.append('text')\n .attr('y', height + 20)\n .attr('x', x(2))\n .text((2-1)*5)\n svg.append('text')\n .attr('y', height + 20)\n .attr('x', x(20))\n .text((20-1)*5)\n svg.append('text')\n .attr('y', height + 20)\n .attr('x', x(34))\n .text((34-1)*5)\n svg.append('text')\n .attr('y', height + 20)\n .attr('x', x(49))\n .text((49-1)*5)\n \n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1963,"value":"md`Looks like there's three or four bumps in this data. We could use [k-means clustering](https://en.wikipedia.org/wiki/K-means_clustering) to break these up, but I found it didn't produce satisfactory results, so instead let's just break it up ourselves.\n\nIf you move around the sliders to the various minima in the histogram, you can see what edges it differentiates between.\n`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2026,"value":"viewof minMask = slider({max: 255, min:1, step:1, value:5, description:\"Minimum\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2029,"value":"viewof maxMask = slider({max: 255, min:1, step:1, value:95, description:\"Maximum\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1938,"value":"{\n let width = 600\n let height = 100\n let x = d3.scaleBand()\n .domain(d3.range(histogram.length))\n .range([0, width])\n let y = d3.scaleLinear()\n .domain([0, d3.max(histogram)])\n .range([0, 100])\n const svg = d3.create(\"svg\")\n .attr(\"width\", width)\n .attr(\"height\", height+30)\n \n const bar = svg.selectAll(\"g\")\n .data(histogram)\n .join(\"g\")\n .attr(\"transform\", (d, i) => `translate(${x(i)}, ${height-y(d)})`);\n\n bar.append(\"rect\")\n .attr(\"fill\", (d,i) => i*5 maxMask?\"black\":\"gray\")\n .attr(\"width\", x.bandwidth())\n .attr(\"height\", y)\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2033,"value":"{\n let canvas = document.createElement('canvas');\n canvas.width = chestGrayScale.length;\n canvas.height = chestGrayScale.length;\n let context = canvas.getContext('2d')\n context.drawImage(chestImage, 0, 0, chestImage.width, chestImage.height);\n for (let y=0;ymaxMask) context.fillRect(x, y, 1, 1)\n }\n }\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2022,"value":"md`The high part at the left edge is where it is pitch black. That is clearly the edge of the patient. Mostly we are interested in the large lump next to that, because that is the lungs. The lungs should represent a significant chunk of the image and should be the next darkest part, so let's put all of the lower bump red. Then there's a section at the right which represents the brightest parts of the image, the heart and diaphragm. Which leaves this middle gray part which seems to represent the shoulders and neck.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1355,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1439,"value":"{\n let canvas = document.createElement('canvas');\n canvas.width = chestGrayScale.length;\n canvas.height = chestGrayScale.length;\n let context = canvas.getContext('2d')\n context.drawImage(chestImage, 0, 0, chestImage.width, chestImage.height);\n context.fillStyle = `yellow`\n for (let y=0;y i <= c.max && i >= c.min) || {'color':'black'}).color\n \n context.fillRect(x, y, 1, 1)\n }\n }\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1482,"value":"md`The ranges we picked did a pretty good job. Some of these edges are a little narrow, for instance, we need the lungs to be distinct from the upper shoulders and we need the heart to be distinct from the spinal column.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1518,"value":"{\n let canvas = document.createElement('canvas');\n canvas.width = chestImage.width;\n canvas.height = chestImage.height;\n let context = canvas.getContext('2d')\n context.drawImage(chestImage, 0, 0, canvas.width, canvas.height);\n let colors = ['red','orange','yellow', 'green', 'purple']\n let tnum = 0\n for (let t of longest_traces) {\n context.fillStyle = colors[tnum % colors.length];\n for (let p of t) {\n context.fillRect(p.x, p.y, 1, 1)\n }\n tnum+=1;\n }\n return canvas\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1975,"value":"md` # Line Simplification\nOnce again we will use line simplification, but this time, instead of minimizing error diverging from the original line (RDP), I'll minimize the error of the total area of the lungs which is called the [Visvalingam](https://www.aplitop.com/subidas/ayuda/en/MDT/index.html#!visvalingamAlgorithm) algorithm. I think it produces less weird distortions on the simplified polygon.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1526,"value":"viewof errorThreshold3 = slider({max: 73, min:7, step:1, value:70, description:\"Error Threshold\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1529,"value":"{\n let posScale=1\n let pathOffset=0\n let lastPoint = nextSteps2.length-1;\n return html`\n\n`\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1583,"value":"md`# Inferring Heart Position\nThere is very little difference in color from the bottom of the heart to the beginning of the diaphragm. Especially on top of the spinal column, so we are just going to have to infer that edge from the position of the lungs.\n\nThe diaphragm is pretty much flat and the heart and lungs seem to be sitting right on top of it. So let's try drawing a line between the bottom of the two lungs and call that the boundary of the heart and diagragm.\n\nThe top of the heart has a small amount of shading difference to help us find the edge. We only need to find one point and then join it to the inner edges of the lungs and now we have a reasonably accurate outline of the heart.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1817,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2000,"value":"md`\nNow that we have a segmented image, we can start to provide data that can help answer questions we might have about the image.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2004,"value":"md`# Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1562,"value":"v = require('https://bundle.run/visvalingam-simplifier@0.1.5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1508,"value":"longest_traces = {\n let sorted = chestTraces.sort()\n return [sorted[chestTraces.length-1],\n sorted[chestTraces.length-3]\n ]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1492,"value":"chestTraces = get_traces(binChest)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1487,"value":"binChest = {\n let ret = []\n for (let y=0;y5 && chestGrayScale[y][x] < 95 && x>0 && y>0 &&x<199 &&y<199) {\n row.push(1)\n } else {\n row.push(0)\n }\n }\n ret.push(row)\n }\n return ret\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1345,"value":"histogram = {\n let hist = []\n for (let i=0;i<52;i++) {\n hist[i] =0\n }\n \n for (let y=0;y x1 && x3 > x2 && x4 > x2 && x3 > x1) return false;\n if (x4 < x1 && x3 < x2 && x4 < x2 && x3 < x1) return false;\n if (y4 > y1 && y3 > y2 && y4 > y2 && y3 > y1) return false;\n if (y4 < y1 && y3 < y2 && y4 < y2 && y3 > y1) return false;\n if (det === 0) {\n return false;\n } else {\n lambda = ((y4 - y3) * (x4 - x1) + (x3 - x4) * (y4 - y1)) / det;\n gamma = ((y1 - y2) * (x4 - x1) + (x2 - x1) * (y4 - y1)) / det;\n return (0 < lambda && lambda < 1) && (0 < gamma && gamma < 1);\n }\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":859,"value":"passMap = {\n let canvas = document.createElement('canvas');\n canvas.width = image.width;\n canvas.height = image.height;\n let context = canvas.getContext('2d')\n context.drawImage(image, 0, 0, image.width, image.height);\n let data = context.getImageData(0, 0, image.width, image.height).data;\n let ret = []\n for (let y=0;y dp.polygonContains(nextSteps.map(p=>translate(p)),c))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":996,"value":"circumcenters2= {\n let ret = []\n for (let i=0;i dp.polygonContains(simplified2.map(p=>translate(p)),c))\n return ret.filter(c => dp.polygonContains(simplified2.map(p => translate2(p)), c))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":753,"value":"voronoi.vectors","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":676,"value":"delaunay = {\n const margin = -22;\n const posScale = 30;\n const boxSize = 20;\n const boxGap = posScale - boxSize;\n const pathOffset = boxSize + boxGap/2 + margin;\n return de.Delaunay.from(nextSteps, p=> p.x*posScale+pathOffset, p=> p.y*posScale+pathOffset);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":978,"value":"delaunay2 = {\n let flat = scSimple.flat()\n return de.Delaunay.from(flat, p=> p.x*3, p=> p.y*3);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":982,"value":"voronoi2 = delaunay2.voronoi([0, 0, 180*3, 180*3])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":702,"value":"voronoi = {\n const voronoi = delaunay.voronoi([0, 0, 275, 175])\n return voronoi\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1786,"value":"cluster_ranges2 = [\n {min: 0, max: 7, color: \"blue\"},\n {min: 8, max: 100, color: \"red\"},\n {min: 100, max: 169, color: \"gray\"},\n {min: 169, max: 255, color: \"yellow\"},\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"function translate(p) {\n const margin = -22;\n const posScale = 30;\n const boxSize = 20;\n const boxGap = posScale - boxSize;\n const pathOffset = boxSize + boxGap/2 + margin;\n return [p.x*posScale+pathOffset, p.y*posScale+pathOffset]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1001,"value":"function translate2(p) {\n return [p.x*3, p.y*3]\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":715,"value":"dp = require('d3-polygon')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":627,"value":"de = require(\"d3-delaunay\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":682,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":559,"value":"simplified = rdp(nextSteps,errorThreshold)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":928,"value":"simplified2 = rdp(nextSteps2,errorThreshold2)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1544,"value":"simpleChest = longest_traces.map(t => v.simplify_line(t, errorThreshold3))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1088,"value":"scSimple = scTraces.map(trace => rdp(trace,errorThreshold2))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":555,"value":"rdp = require('https://bundle.run/line-simplify-rdp@0.4.0')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"pairwise = function(arr){\n let ret = []\n for(var i=0; i < arr.length - 1; i++){\n ret.push([arr[i], arr[i + 1]])\n }\n return ret;\n}\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1071,"value":"function trace(start, grid, visited) {\n const width = grid[0].length;\n const height = grid.length;\n const ret = [start]\n let currPos = start;\n for (let i=0;i<2000;i++) {\n currPos = getNextPos(currPos, grid)\n ret.push(currPos);\n visited[currPos.y*width+currPos.x] = true\n if (currPos.x == start.x && currPos.y == start.y) return ret\n }\n return null\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1027,"value":"function get_traces(grid) {\n const width = grid[0].length;\n const height = grid.length;\n let visited = []\n let traces = []\n //skip the last row\n for (let y=0; y < height - 1; y++) {\n for (let x=0;x < width - 1; x++) {\n if (y * width + x in visited){\n continue\n }\n let firstVal = grid[y][x];\n let firstPoint = null\n if (grid[y][x+1] != firstVal) firstPoint = {x:x, y:y, dir:'up'}\n else if (grid[y+1][x+1] != firstVal) firstPoint = {x:x, y:y, dir:'right'}\n else if (grid[y+1][x] != firstVal) firstPoint = {x:x, y:y, dir:'down'}\n if (firstPoint) {\n let t = trace(firstPoint, grid, visited)\n if (t) traces.push(t)\n }\n }\n }\n return traces\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1029,"value":"scTraces = get_traces(passMap)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1078,"value":"{\n let v = []\n trace(start_pos2, passMap, v)\n return v\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":882,"value":"start_pos2 = {\n let shape = passMap;\n for (let y=0;y