javascript - 一种快速填充轮廓的方法，并且能够导出为类似多边形的格式

标签 javascript algorithm html5-canvas polygon flood-fill

我在 Canvas 上展示了许多医学图片，如下所示。

knee

我正在尝试制作一个工具，允许您使用该工具以可扩展圆圈的形式选择图像的任何区域，并仅填充不超出轮廓的部分原始点击像素所在的位置。在单独的 Canvas 层上绘制填充轮廓。

现在我使用最常见的具有可变容差(比较函数)的洪水填充迭代堆栈实现。 You can familiarize yourself with it here 。一切都不是很好，特别是在没有强烈对比度差异的图片和高分辨率图像中，其他一切都非常慢。

flood fill result

我有想法创建一个状态容器并查找那里是否存在所需的填充轮廓，如果存在，则只需替换 Canvas 像素数组(不过，我将不得不再次求助为了进行一些额外的处理， Canvas 像素数组包含 4 个 channel ，而在算法的输出中仅获得 1 个 channel ，仅替换内容是行不通的，您需要将每个像素替换为分为 4 个 channel 的像素)而不是每次都会缓慢地充满洪水。但这种方法有一个重大问题:内存消耗。正如您可能猜到的那样，填充的轮廓，尤其是仅具有不错的分辨率的轮廓，可能会占用相当多的空间，并且它们的设置成为内存消耗的真正问题。

决定以多边形的形式存储完成的轮廓，并从容器中提取它们，只需用更快的 context fill 填充它们即可。 。使用的算法允许我输出一组边界，但由于算法的特点，这个数组是无序的，并且按这个顺序连接顶点，我们只得到部分填充的轮廓(右图)。有没有一种方法可以对它们进行排序，使我只能连接它们并获得闭合路径(左图中填充轮廓中的孔不应该是先验的，所以我们不必担心关于他们)？

flood fill resulted path based on boundaries

总结一下，由于填充工作不太好，我想使用不同的算法/实现，但我不知道是哪一个。 以下是我的一些想法:

  1. 使用不同的实现方式，例如行扫描方法。据我所知，here is one of the fastest and most effective implementations of the algorithm among open sources 。 优点:可能的效率和速度。 缺点:我需要以某种方式将结果转换为多边形，将算法重写为javascript(可能是 emscripten ，可以做得很好，但无论如何我都必须重写相当一部分代码)。

  2. 使用完全不同的方法。

    a) 我不知道，但也许 Canny 检测器对于提取多边形很有用。但就程序在客户端的使用而言，提取所有边界是无利可图的，有必要弄清楚如何只处理必要的部分，而不是整个图片。

    b) 然后，了解边界后，使用任何足够快的填充算法，该算法根本不会超出找到的边界。

我很高兴了解其他一些方法，甚至更好地了解 JavaScript 中现成的实现

更新:

为了更好地理解，工具光标和算法的预期结果如下所示。

tool cursor expected result

最佳答案

这是一个使用 opencv 的示例

下面应该可以工作或最终使用代码片段内提供的 fiddle 链接

感兴趣:approxPolyDP，它可能足以满足您的需求(检查Ramer-Douglas-Peucker algorithm)

// USE FIDDLE
// https://jsfiddle.net/c7xrq1uy/

async function loadSomeImage() {
  const ctx = document.querySelector('#imageSrc').getContext('2d')
  ctx.fillStyle = 'black'
  const img = new Image()
  img.crossOrigin = ''
  img.src = 'https://cors-anywhere.herokuapp.com//image/aiZ7z.png'

  img.onload = () => {
    const imgwidth = img.offsetWidth
    const imgheight = img.offsetHeight
    ctx.drawImage(img, 0, 0, img.width, img.height, 0, 0, 400, 400) 
  }
}

function plotPoints(canvas, points, color = 'green', hold = false){
  const ctx = canvas.getContext('2d')
  !hold && ctx.clearRect(0, 0, 400, 400)
  ctx.strokeStyle = color

  Object.values(points).forEach(ps => {
    ctx.beginPath()
    ctx.moveTo(ps[0].x, ps[0].y)
    ps.slice(1).forEach(({ x, y }) => ctx.lineTo(x,y))
    ctx.closePath()
    ctx.stroke()
  })
}
const binarize = (src, threshold) => {
  cv.cvtColor(src, src, cv.COLOR_RGB2GRAY, 0)
  const dst = new cv.Mat()
  src.convertTo(dst, cv.CV_8U)
  cv.threshold(src, dst, threshold, 255, cv.THRESH_BINARY_INV)
  cv.imshow('binary', dst)
  return dst
}
const flip = src => {
  const dst = new cv.Mat()
  cv.threshold(src, dst, 128, 255, cv.THRESH_BINARY_INV)
  cv.imshow('flip', dst)
  return dst
}
const dilate = (src) => {
  const dst = new cv.Mat()
  let M = cv.Mat.ones(3, 3, cv.CV_8U)
  let anchor = new cv.Point(-1, -1)
  cv.dilate(src, dst, M, anchor, 1, cv.BORDER_CONSTANT, cv.morphologyDefaultBorderValue())
  M.delete()
  cv.imshow('dilate', dst)
  return dst
}
const PARAMS = {
  threshold: 102,
  anchor: { x: 180, y: 180 },
  eps: 1e-2
}
const dumpParams = ({ threshold, anchor, eps }) => {
  document.querySelector('#params').innerHTML = `thres=${threshold} (x,y)=(${anchor.x}, ${anchor.y}) eps:${eps}`
}
document.querySelector('input[type=range]').onmouseup = e => {
  PARAMS.threshold = Math.round(parseInt(e.target.value, 10) / 100 * 255)
  dumpParams(PARAMS)
  runCv(PARAMS)
}
document.querySelector('input[type=value]').onchange = e => {
  PARAMS.eps = parseFloat(e.target.value)
  dumpParams(PARAMS)
  runCv(PARAMS)
}
document.querySelector('#imageSrc').onclick = e => {
  const rect = e.target.getBoundingClientRect()
  PARAMS.anchor = {
    x: e.clientX - rect.left,
    y: e.clientY - rect.top
  }
  dumpParams(PARAMS)
  runCv(PARAMS)
}
const contourToPoints = cnt => {
  const arr = []
  for (let j = 0; j < cnt.data32S.length; j += 2){
    let p = {}
    p.x = cnt.data32S[j]
    p.y = cnt.data32S[j+1]
    arr.push(p)
  }
  return arr
}
loadSomeImage()
dumpParams(PARAMS)
let CVREADY
const cvReady = new Promise((resolve, reject) => CVREADY = resolve)

const runCv = async ({ threshold, anchor, eps }) => {
  await cvReady
  const canvasFinal = document.querySelector('#final')
  const mat = cv.imread(document.querySelector('#imageSrc'))
  const binaryImg = binarize(mat, threshold, 'binary')
  const blurredImg = dilate(binaryImg)
  const flipImg = flip(blurredImg)
  var contours = new cv.MatVector()
  const hierarchy = new cv.Mat
  cv.findContours(flipImg, contours, hierarchy, cv.RETR_EXTERNAL, cv.CHAIN_APPROX_SIMPLE)

  const points = {}
  let matchingPoints = null
  let matchingContour = null
  for (let i = 0; i < contours.size(); ++i) {
  let minArea = 1e40
    const ci = contours.get(i)
    points[i] = contourToPoints(ci)
    if (anchor) {
      const point = new cv.Point(anchor.x, anchor.y)
      const inside = cv.pointPolygonTest(ci, point, false) >= 1
      const area = cv.contourArea(ci)
      if (inside && area < minArea) {
        matchingPoints = points[i]
        matchingContour = ci
        minArea = area
      }
    }
  }
  plotPoints(canvasFinal, points)

  if (anchor) {
    if (matchingPoints) {
      plotPoints(canvasFinal, [matchingPoints], 'red', true)
      if (eps) {
        const epsilon = eps * cv.arcLength(matchingContour, true)
        const approx = new cv.Mat()
        cv.approxPolyDP(matchingContour, approx, epsilon, true)
        const arr = contourToPoints(approx)
        console.log('polygon', arr)
        plotPoints(canvasFinal, [arr], 'blue', true)
      }
    }
  }
  mat.delete()
  contours.delete()
  hierarchy.delete()
  binaryImg.delete()
  blurredImg.delete()
  flipImg.delete()
}
function onOpenCvReady() {
  cv['onRuntimeInitialized'] = () => {console.log('cvready'); CVREADY(); runCv(PARAMS)}
}
// just so we can load async script
var script = document.createElement('script');
script.onload = onOpenCvReady
script.src = 'https://docs.opencv.org/master/opencv.js';
document.head.appendChild(script)
canvas{border: 1px solid black;}
  .debug{width: 200px; height: 200px;}
binarization threeshold<input type="range" min="0" max="100"/><br/>
eps(approxPolyDp) <input type="value" placeholder="0.01"/><br/>
params: <span id="params"></span><br/>
<br/>
<canvas id="imageSrc" height="400" width="400"/></canvas>
<canvas id="final" height="400" width="400"></canvas>
<br/>
<canvas class="debug" id="binary" height="400" width="400" title="binary"></canvas>
<canvas class="debug" id="dilate" height="400" width="400" title="dilate"></canvas>
<canvas class="debug" id="flip" height="400" width="400" title="flip"></canvas>

ps:控制台输出多边形

使用掩码实现

编辑:在下面的代码片段中，我获得了更多乐趣并实现了蒙版。我们可以将片段制作为[整页]，然后将鼠标悬停在第一个 Canvas 上。

// USE FIDDLE
// https://jsfiddle.net/c7xrq1uy/

async function loadSomeImage() {
  const ctx = document.querySelector('#imageSrc').getContext('2d')
  ctx.fillStyle = 'black'
  const img = new Image()
  img.crossOrigin = ''
  img.src = 'https://cors-anywhere.herokuapp.com//image/aiZ7z.png'

  img.onload = () => {
    const imgwidth = img.offsetWidth
    const imgheight = img.offsetHeight
    ctx.drawImage(img, 0, 0, img.width, img.height, 0, 0, 400, 400) 
  }
}

function plotPoints(canvas, points, color = 'green', hold = false){
  const ctx = canvas.getContext('2d')
  !hold && ctx.clearRect(0, 0, 400, 400)
  ctx.strokeStyle = color

  Object.values(points).forEach(ps => {
    ctx.beginPath()
    ctx.moveTo(ps[0].x, ps[0].y)
    ps.slice(1).forEach(({ x, y }) => ctx.lineTo(x,y))
    ctx.closePath()
    ctx.stroke()
  })
}
const binarize = (src, threshold) => {
  cv.cvtColor(src, src, cv.COLOR_RGB2GRAY, 0)
  const dst = new cv.Mat()
  src.convertTo(dst, cv.CV_8U)
  cv.threshold(src, dst, threshold, 255, cv.THRESH_BINARY_INV)
  cv.imshow('binary', dst)
  return dst
}
const flip = src => {
  const dst = new cv.Mat()
  cv.threshold(src, dst, 128, 255, cv.THRESH_BINARY_INV)
  cv.imshow('flip', dst)
  return dst
}
const dilate = (src) => {
  const dst = new cv.Mat()
  let M = cv.Mat.ones(3, 3, cv.CV_8U)
  let anchor = new cv.Point(-1, -1)
  cv.dilate(src, dst, M, anchor, 1, cv.BORDER_CONSTANT, cv.morphologyDefaultBorderValue())
  M.delete()
  cv.imshow('dilate', dst)
  return dst
}
const PARAMS = {
  threshold: 102,
  anchor: { x: 180, y: 180 },
  eps: 1e-2,
  radius: 50
}
const dumpParams = ({ threshold, anchor, eps }) => {
  document.querySelector('#params').innerHTML = `thres=${threshold} (x,y)=(${anchor.x}, ${anchor.y}) eps:${eps}`
}
document.querySelector('input[type=range]').onmouseup = e => {
  PARAMS.threshold = Math.round(parseInt(e.target.value, 10) / 100 * 255)
  dumpParams(PARAMS)
  runCv(PARAMS)
}
document.querySelector('input[type=value]').onchange = e => {
  PARAMS.eps = parseFloat(e.target.value)
  dumpParams(PARAMS)
  runCv(PARAMS)
}
document.querySelector('#imageSrc').onclick = e => {
  const rect = e.target.getBoundingClientRect()
  PARAMS.anchor = {
    x: e.clientX - rect.left,
    y: e.clientY - rect.top
  }
  dumpParams(PARAMS)
  runCv(PARAMS)
}
// sorry for the globals, keep code simple
let DST = null
let MATCHING_CONTOUR = null
let DEBOUNCE = 0
document.querySelector('#imageSrc').onmousemove = e => {
  if (Date.now() - DEBOUNCE < 100) return
  if (!MATCHING_CONTOUR || !DST) { return }
  const rect = e.target.getBoundingClientRect()
  DEBOUNCE = Date.now()
  const x = e.clientX - rect.left
  const y = e.clientY - rect.top
  const dst = DST.clone()
  plotIntersectingMask(dst, MATCHING_CONTOUR, { anchor: { x, y }, radius: PARAMS.radius })
  dst.delete()
}
const contourToPoints = cnt => {
  const arr = []
  for (let j = 0; j < cnt.data32S.length; j += 2){
    let p = {}
    p.x = cnt.data32S[j]
    p.y = cnt.data32S[j+1]
    arr.push(p)
  }
  return arr
}
const plotIntersectingMask = (dst, cnt, { anchor, radius }) => {
  const { width, height } = dst.size()
  
  const contourMask = new cv.Mat.zeros(height, width, dst.type())
  const matVec = new cv.MatVector()
  matVec.push_back(cnt)
  cv.fillPoly(contourMask, matVec, [255, 255, 255, 255])

  const userCircle = new cv.Mat.zeros(height, width, dst.type())
  cv.circle(userCircle, new cv.Point(anchor.x, anchor.y), radius, [255, 128, 68, 255], -2)

  const commonMask = new cv.Mat.zeros(height, width, dst.type())
  cv.bitwise_and(contourMask, userCircle, commonMask)
  
  userCircle.copyTo(dst, commonMask)
  cv.imshow('final', dst)

  commonMask.delete()
  matVec.delete()
  contourMask.delete()
  userCircle.delete()
}
loadSomeImage()
dumpParams(PARAMS)
let CVREADY
const cvReady = new Promise((resolve, reject) => CVREADY = resolve)

const runCv = async ({ threshold, anchor, eps, radius }) => {
  await cvReady
  const canvasFinal = document.querySelector('#final')
  const mat = cv.imread(document.querySelector('#imageSrc'))
  const binaryImg = binarize(mat, threshold, 'binary')
  const blurredImg = dilate(binaryImg)
  const flipImg = flip(blurredImg)
  var contours = new cv.MatVector()
  const hierarchy = new cv.Mat
  cv.findContours(flipImg, contours, hierarchy, cv.RETR_EXTERNAL, cv.CHAIN_APPROX_SIMPLE)

  const points = {}
  let matchingPoints = null
  let matchingContour = null
  for (let i = 0; i < contours.size(); ++i) {
  let minArea = 1e40
    const ci = contours.get(i)
    points[i] = contourToPoints(ci)
    if (anchor) {
      const point = new cv.Point(anchor.x, anchor.y)
      const inside = cv.pointPolygonTest(ci, point, false) >= 1
      const area = cv.contourArea(ci)
      if (inside && area < minArea) {
        matchingPoints = points[i]
        matchingContour = ci
        minArea = area
      }
    }
  }
  plotPoints(canvasFinal, points)

  if (anchor) {
    if (matchingPoints) {
      MATCHING_CONTOUR = matchingContour
      plotPoints(canvasFinal, [matchingPoints], 'red', true)
      if (eps) {
        const epsilon = eps * cv.arcLength(matchingContour, true)
        const approx = new cv.Mat()
        cv.approxPolyDP(matchingContour, approx, epsilon, true)
        const arr = contourToPoints(approx)
        //console.log('polygon', arr)
        plotPoints(canvasFinal, [arr], 'blue', true)

        if (DST) DST.delete()
        DST = cv.imread(document.querySelector('#final'))
      }
    }
  }
  mat.delete()
  contours.delete()
  hierarchy.delete()
  binaryImg.delete()
  blurredImg.delete()
  flipImg.delete()
}
function onOpenCvReady() {
  cv['onRuntimeInitialized'] = () => {console.log('cvready'); CVREADY(); runCv(PARAMS)}
}
// just so we can load async script
var script = document.createElement('script');
script.onload = onOpenCvReady
script.src = 'https://docs.opencv.org/master/opencv.js';
document.head.appendChild(script)
  canvas{border: 1px solid black;}
  .debug{width: 200px; height: 200px;}
  #imageSrc{cursor: pointer;}
binarization threeshold<input type="range" min="0" max="100"/><br/>
eps(approxPolyDp) <input type="value" placeholder="0.01"/><br/>
params: <span id="params"></span><br/>
<br/>
<canvas id="imageSrc" height="400" width="400"/></canvas>
<canvas id="final" height="400" width="400"></canvas>
<br/>
<canvas class="debug" id="binary" height="400" width="400" title="binary"></canvas>
<canvas class="debug" id="dilate" height="400" width="400" title="dilate"></canvas>
<canvas class="debug" id="flip" height="400" width="400" title="flip"></canvas>

关于javascript - 一种快速填充轮廓的方法，并且能够导出为类似多边形的格式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/61685407/

上一篇：c - 为什么生成此代码以取消引用浮点指针？

下一篇：python - 使用经过训练的 TensorFlow 模型预测单个 PNG 图像

相关文章：

HTML5 canvas drawImage() 不会在 Firefox 上绘制大图像

javascript - 单击任何按钮都会触发我的 UserService.getUsers 函数，但这不应该发生

javascript - HTML5 Canvas 创建振荡运动

performance - 为什么这些例程在 Mathematica 中的相对效率高？

css - 将 svg 转换为 png 时如何包含 CSS 样式

javascript - html svg 中的动画脚步

javascript - Jquery Mobile 复制自动分隔符

javascript - 从 url(adwords 着陆页)触发嵌入式 Javascript

algorithm - 具有 4 个已知邻居的细化/骨架化算法

algorithm - Kotlin - 按类别和子类别排序的列表

©2024 IT工具网  联系我们