Reputation: 153
I have a number of medical pictures presented on canvas, as an example below.
I’m trying to make a tool that allows you to select any area of the image with the tool in the form of an expandable circle, and fill in only that part of it that doesn't go beyond the outline in which the original click pixel was located. A filled outline is drawn on a separate canvas layer.
Now I use the most common iterative stack implementation of flood fill with variable tolerance (comparison function). You can familiarize yourself with it here. Everything doesn't work very well, especially in pictures where there are no strong contrast differences and in high-resolution images, everything else is pretty slow.
I had the idea to create a state container and look for whether the desired filled outline exists there and if so, then just replace the canvas pixel array (though, again, I will have to resort to some additional processing, the canvas pixel array contains 4 channel, while at the output of the algorithm only 1 is obtained and just replacing the content doesn't work, you need to replace each pixel with a pixel divided into 4 channels) instead of a slow flood fill each time. But this approach has one significant problem: memory consumption. As you might guess, a filled outline, especially of a decent resolution alone, can take up quite a lot of space, and their set becomes a real problem of memory consumption.
It was decided to store the finished contours in the form of polygons and extracting them from the container simply fill them with faster context fill. The algorithm used allows me to output a set of boundaries, but due to the features of the algorithm, this array is unordered and connecting the vertices in this order, we get only a partially filled outline (right picture). Is there a way to sort them in such a way that I could only connect them and get a closed path (the holes that are in the filled outline in the left picture shouldn't be a priori, so we don’t have to worry about them)?
Summing up, due to the not-so-best fill job, I think to use a different algorithm / implementation, but I don’t know which one. Here are some of my ideas:
Use a different implementation, for example, a line scanning method. As far as I know, here is one of the fastest and most effective implementations of the algorithm among open sources. Pros: possible efficiency and speed. Cons: I need to somehow convert the result to a polygon, rewrite the algorithm to javascript (probably emscripten, can do it well, but in any case I will have to rewrite a considerable part of the code).
Use a completely different approach.
a) I don’t know, but maybe the Canny detector can be useful for extracting the polygon. But as far as the use of the program is meant on the client side, it will be unprofitable to extract all the boundaries, it is necessary to figure out how to process only the necessary section, and not the entire picture.
b) Then, knowing the border, use any sufficiently fast fill algorithm that simply won't go beyond the boundaries found.
I'll be glad to know about some other ways, and even better to see ready-made implementations in javascript
UPD:
For a better understanding, the tool cursor and the expected result of the algorithm are presented below.
Upvotes: 2
Views: 1331
Reputation: 5703
Here is an example with opencv
Below should work or eventually use the fiddle link provided inside the code snippet
Of interest: approxPolyDP which may be sufficient for your needs (check 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/https://i.sstatic.net/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: polygon is output in the console
edit: in below snippet I had more fun and implemented the mask. We may make the snippet [full page] then hover over the first 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/https://i.sstatic.net/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>
Upvotes: 2