javascript - 获取具有白色背景的图像中复杂对象的边界(js)

Question

获取图像边界(不是图像本身，而是非白色像素)的好方法是什么？我正在使用 javascript，所以如果可以的话，请尽量将算法保持在该范围内。

例如，我如何获得所有 x 和 y 点的列表/两个列表，其中存在于此(一组)对象边界上的点:

请注意，应包括内部部分，但应排除完全位于内部的颜色缺失(如孔洞)。

因此，结果将是两个包含 x 和 y 点(对于像素)的列表，它们将构造一个类似于此的对象:

下面是我是如何“实现”它的。虽然它适用于所有凹面物体，但如果您尝试将它用于具有某些凸面的更复杂物体，它不可避免地会失败。

凹面物体成功

• jsfiddle:https://jsfiddle.net/bhc4qn87/

片段:

var _PI = Math.PI, _HALF_PI = Math.PI / 2, _TWO_PI = 2 * Math.PI;
var _radius = 10, _damp = 75, _center = new THREE.Vector3(0, 0, 0);
var _phi = _PI / 2, _theta = _theta = _PI / 7;
var _sceneScreenshot = null, _dirty = true;

var _tmpCan = document.createElement("canvas"),
	_tmpCtx = _tmpCan.getContext("2d");

var scene = document.getElementById("scene"),
	sw = scene.width, sh = scene.height;
var _scene = new THREE.Scene();
var _renderer = new THREE.WebGLRenderer({ canvas: scene, alpha: true, antialias: true });
_renderer.setPixelRatio(window.devicePixelRatio);
_renderer.setSize(sw, sh);
var _camera = new THREE.PerspectiveCamera(35, sw / sh, .1, 1000);

_tmpCan.width = sw; _tmpCan.height = sh;

_scene.add(new THREE.HemisphereLight(0x999999, 0x555555, 1));
_scene.add(new THREE.AmbientLight(0x404040));
var _camLight = new THREE.PointLight(0xdfdfdf, 1.8, 300, 2);
_scene.add(_camLight);

var geometry = new THREE.BoxBufferGeometry( 1, 1, 1 );
var material = new THREE.MeshPhysicalMaterial( { color: 0x2378d3, opacity: .7 } );
var cube = new THREE.Mesh( geometry, material );
_scene.add( cube );

function initialize() {
	document.body.appendChild(_tmpCan);
	_tmpCan.style.position = "absolute";
	_tmpCan.style.left = "8px";
	_tmpCan.style.top = "8px";
	_tmpCan.style.pointerEvents = "none";
	addListeners();
	updateCamera();
	animate();
}

function addListeners() {
	/* mouse events */

	var scene = document.getElementById("scene");

	scene.oncontextmenu = function(e) {
		e.preventDefault();
	}

	scene.onmousedown = function(e) {
		e.preventDefault();
		mouseTouchDown(e.pageX, e.pageY, e.button);
	}

	scene.ontouchstart = function(e) {
		if (e.touches.length !== 1) {
			return;
		}
		e.preventDefault();
		mouseTouchDown(e.touches[0].pageX, e.touches[0].pageY, e.touches.length, true);
	}

	function mouseTouchDown(pageX, pageY, button, touch) {
		_mouseX = pageX; _mouseY = pageY;
		_button = button;
		if (touch) {
			document.ontouchmove = function(e) {
				if (e.touches.length !== 1) {
					return;
				}
				mouseTouchMove(e.touches[0].pageX, e.touches[0].pageY, e.touches.length, true);
			}
			document.ontouchend = function() {
				document.ontouchmove = null;
				document.ontouchend = null;
			}
		} else {
			document.onmousemove = function(e) {
				mouseTouchMove(e.pageX, e.pageY, _button);
			}
			document.onmouseup = function() {
				document.onmousemove = null;
				document.onmouseup = null;
			}
		}
	}

	function mouseTouchMove(pageX, pageY, button, touch) {
		var dx = pageX - _mouseX,
			dy = pageY - _mouseY;

		_phi += dx / _damp;
		// _theta += dy / _damp;

		_phi %= _TWO_PI;
		if (_phi < 0) {
			_phi += _TWO_PI;
		}

		// var maxTheta = _HALF_PI - _HALF_PI * .8,
		// 	minTheta = -_HALF_PI + _HALF_PI * .8;

		// if (_theta > maxTheta) {
		// 	_theta = maxTheta;
		// } else if (_theta < minTheta) {
		// 	_theta = minTheta;
		// }

		updateCamera();
		_dirty = true;
		// updateLabels();
		_mouseX = pageX;
		_mouseY = pageY;
	}
}

function updateCamera() {

	// var radius = _radius + (Math.sin(_theta % _PI)) * 10;
	var radius = _radius;
	var y = radius * Math.sin(_theta),
		phiR = radius * Math.cos(_theta);
	var z = phiR * Math.sin(_phi),
		x = phiR * Math.cos(_phi);

	_camera.position.set(x, y, z);
	_camLight.position.set(x, y, z);
	_camera.lookAt(_center);

}

function updateLabels() {
	if (_sceneScreenshot === null) {
		return;
	}

	var tmpImg = new Image();
	tmpImg.onload = function() {
		_tmpCtx.drawImage(tmpImg, 0, 0, sw, sh);

		var imgData = _tmpCtx.getImageData(0, 0, sw, sh);
		var data = imgData.data;

		var firstXs = [];
		var lastXs = [];
		for (var y = 0; y < sh; y++) {
			var firstX = -1;
			var lastX = -1;
			for (var x = 0; x < sw; x++) {
				var i = (x + y * sw) * 4;
				var sum = data[i] + data[i + 1] + data[i + 2];
				if (firstX === -1) {
					if (sum > 3) {
						firstX = x;
					}
				} else {
					if (sum > 3) {
						lastX = x;
					}
				}
			}
			if (lastX === -1 && firstX >= 0) {
				lastX = firstX;
			}
			firstXs.push(firstX);
			lastXs.push(lastX);
		}
		var firstYs = [];
		var lastYs = [];
		for (var x = 0; x < sw; x++) {
			var firstY = -1;
			var lastY = -1;
			for (var y = 0; y < sh; y++) {
				var i = (x + y * sw) * 4;
				var sum = data[i] + data[i + 1] + data[i + 2];
				if (firstY === -1) {
					if (sum < 759) {
						firstY = y;
					}
				} else {
					if (sum < 759) {
						lastY = y;
					}
				}
			}
			if (lastY === -1 && firstY >= 0) {
				lastY = firstY;
			}
			firstYs.push(firstY);
			lastYs.push(lastY);
		}
		postLoad(firstXs, lastXs, firstYs, lastYs);
	}
	tmpImg.src = _sceneScreenshot;


	function postLoad(firstXs, lastXs, firstYs, lastYs) {

		_tmpCtx.clearRect(0, 0, sw, sh);

		_tmpCtx.beginPath();
		for (var y = 0; y < sh; y++) {
			_tmpCtx.moveTo(firstXs[y], y);
			_tmpCtx.lineTo(lastXs[y], y);
		}
		/* TODO REMOVE BELOW TODO */
		_tmpCtx.strokeStyle = 'black';
		console.log(_tmpCtx.globalAlpha);
		_tmpCtx.stroke();
		/* TODO REMOVE ABOVE TODO */

		_tmpCtx.beginPath();
		for (var x = 0; x < sw; x++) {
			_tmpCtx.moveTo(x, firstYs[x]);
			_tmpCtx.lineTo(x, lastYs[x]);
		}
		/* TODO REMOVE BELOW TODO */
		_tmpCtx.strokeStyle = 'black';
		_tmpCtx.stroke();
		/* TODO REMOVE ABOVE TODO */

		var imgData = _tmpCtx.getImageData(0, 0, sw, sh);
		var data = imgData.data;

		for (var i = 0, iLen = data.length; i < iLen; i += 4) {
			if (data[i + 3] < 200) {
				data[i + 3] = 0;
			}
			/* TODO remove v TODO */
			else { data[i + 3] = 120; }
		}
		_tmpCtx.putImageData(imgData, 0, 0);
	}

}

function animate () {
	cube.rotation.x += 0.001;
	cube.rotation.y += 0.001;

	_renderer.render(_scene, _camera);
	if (_dirty) {
		_sceneScreenshot = _renderer.domElement.toDataURL();
		updateLabels();
		_dirty = false;
	}

	requestAnimationFrame( animate );
}

initialize();

<script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/92/three.js"></script>

<canvas id="scene" width="400" height="300"></canvas>

复杂对象失败

• jsfiddle:https://jsfiddle.net/xdr9bt0w/

var _PI = Math.PI, _HALF_PI = Math.PI / 2, _TWO_PI = 2 * Math.PI;
var _radius = 10, _damp = 75, _center = new THREE.Vector3(0, 0, 0);
var _phi = _PI / 2, _theta = _theta = 0;
var _sceneScreenshot = null, _dirty = true;

var _tmpCan = document.createElement("canvas"),
	_tmpCtx = _tmpCan.getContext("2d");

var scene = document.getElementById("scene"),
	sw = scene.width, sh = scene.height;
var _scene = new THREE.Scene();
var _renderer = new THREE.WebGLRenderer({ canvas: scene, alpha: true, antialias: true });
_renderer.setPixelRatio(window.devicePixelRatio);
_renderer.setSize(sw, sh);
var _camera = new THREE.PerspectiveCamera(35, sw / sh, .1, 1000);

_tmpCan.width = sw; _tmpCan.height = sh;

_scene.add(new THREE.HemisphereLight(0x999999, 0x555555, 1));
_scene.add(new THREE.AmbientLight(0x404040));
var _camLight = new THREE.PointLight(0xdfdfdf, 1.8, 300, 2);
_scene.add(_camLight);

var geometry = new THREE.BoxBufferGeometry( 1, 1, 1 );
var material = new THREE.MeshPhysicalMaterial( { color: 0x2378d3, opacity: .7 } );
var cube = new THREE.Mesh( geometry, material );
_scene.add( cube );

var geometry = new THREE.BoxBufferGeometry( 1, 1, 1 );
var material = new THREE.MeshPhysicalMaterial( { color: 0xc36843, opacity: .7 } );
var cube2 = new THREE.Mesh( geometry, material );
cube2.position.x = -.75;
cube2.position.y = .75
_scene.add( cube2 );

var geometry = new THREE.BoxBufferGeometry( 1, 1, 1 );
var material = new THREE.MeshPhysicalMaterial( { color: 0x43f873, opacity: .7 } );
var cube3 = new THREE.Mesh( geometry, material );
cube3.position.x = -.25;
cube3.position.y = 1.5;
_scene.add( cube3 );


var geometry = new THREE.BoxBufferGeometry( 1, 1, 1 );
var material = new THREE.MeshPhysicalMaterial( { color: 0x253621, opacity: .7 } );
var cube4 = new THREE.Mesh( geometry, material );
cube4.position.x = 1;
cube4.position.y = .35;
_scene.add( cube4 );

function initialize() {
	document.body.appendChild(_tmpCan);
	_tmpCan.style.position = "absolute";
	_tmpCan.style.left = "200px";
	_tmpCan.style.top = "0px";
	_tmpCan.style.pointerEvents = "none";
	addListeners();
	updateCamera();
	animate();
}

function addListeners() {
	/* mouse events */

	var scene = document.getElementById("scene");

	scene.oncontextmenu = function(e) {
		e.preventDefault();
	}

	scene.onmousedown = function(e) {
		e.preventDefault();
		mouseTouchDown(e.pageX, e.pageY, e.button);
	}

	scene.ontouchstart = function(e) {
		if (e.touches.length !== 1) {
			return;
		}
		e.preventDefault();
		mouseTouchDown(e.touches[0].pageX, e.touches[0].pageY, e.touches.length, true);
	}

	function mouseTouchDown(pageX, pageY, button, touch) {
		_mouseX = pageX; _mouseY = pageY;
		_button = button;
		if (touch) {
			document.ontouchmove = function(e) {
				if (e.touches.length !== 1) {
					return;
				}
				mouseTouchMove(e.touches[0].pageX, e.touches[0].pageY, e.touches.length, true);
			}
			document.ontouchend = function() {
				document.ontouchmove = null;
				document.ontouchend = null;
			}
		} else {
			document.onmousemove = function(e) {
				mouseTouchMove(e.pageX, e.pageY, _button);
			}
			document.onmouseup = function() {
				document.onmousemove = null;
				document.onmouseup = null;
			}
		}
	}

	function mouseTouchMove(pageX, pageY, button, touch) {
		var dx = pageX - _mouseX,
			dy = pageY - _mouseY;

		_phi += dx / _damp;
		// _theta += dy / _damp;

		_phi %= _TWO_PI;
		if (_phi < 0) {
			_phi += _TWO_PI;
		}

		// var maxTheta = _HALF_PI - _HALF_PI * .8,
		// 	minTheta = -_HALF_PI + _HALF_PI * .8;

		// if (_theta > maxTheta) {
		// 	_theta = maxTheta;
		// } else if (_theta < minTheta) {
		// 	_theta = minTheta;
		// }

		updateCamera();
		_dirty = true;
		// updateLabels();
		_mouseX = pageX;
		_mouseY = pageY;
	}
}

function updateCamera() {

	// var radius = _radius + (Math.sin(_theta % _PI)) * 10;
	var radius = _radius;
	var y = radius * Math.sin(_theta),
		phiR = radius * Math.cos(_theta);
	var z = phiR * Math.sin(_phi),
		x = phiR * Math.cos(_phi);

	_camera.position.set(x, y, z);
	_camLight.position.set(x, y, z);
	_camera.lookAt(_center);

}

function updateLabels() {
	if (_sceneScreenshot === null) {
		return;
	}

	var tmpImg = new Image();
	tmpImg.onload = function() {
		_tmpCtx.drawImage(tmpImg, 0, 0, sw, sh);

		var imgData = _tmpCtx.getImageData(0, 0, sw, sh);
		var data = imgData.data;

		var firstXs = [];
		var lastXs = [];
		for (var y = 0; y < sh; y++) {
			var firstX = -1;
			var lastX = -1;
			for (var x = 0; x < sw; x++) {
				var i = (x + y * sw) * 4;
				var sum = data[i] + data[i + 1] + data[i + 2];
				if (firstX === -1) {
					if (sum > 3) {
						firstX = x;
					}
				} else {
					if (sum > 3) {
						lastX = x;
					}
				}
			}
			if (lastX === -1 && firstX >= 0) {
				lastX = firstX;
			}
			firstXs.push(firstX);
			lastXs.push(lastX);
		}
		var firstYs = [];
		var lastYs = [];
		for (var x = 0; x < sw; x++) {
			var firstY = -1;
			var lastY = -1;
			for (var y = 0; y < sh; y++) {
				var i = (x + y * sw) * 4;
				var sum = data[i] + data[i + 1] + data[i + 2];
				if (firstY === -1) {
					if (sum > 3) {
						firstY = y;
					}
				} else {
					if (sum > 3) {
						lastY = y;
					}
				}
			}
			if (lastY === -1 && firstY >= 0) {
				lastY = firstY;
			}
			firstYs.push(firstY);
			lastYs.push(lastY);
		}
		postLoad(firstXs, lastXs, firstYs, lastYs);
	}
	tmpImg.src = _sceneScreenshot;


	function postLoad(firstXs, lastXs, firstYs, lastYs) {

		_tmpCtx.clearRect(0, 0, sw, sh);

		_tmpCtx.beginPath();
		for (var y = 0; y < sh; y++) {
			_tmpCtx.moveTo(firstXs[y], y);
			_tmpCtx.lineTo(lastXs[y], y);
		}
		/* TODO REMOVE BELOW TODO */
		_tmpCtx.strokeStyle = 'black';
		console.log(_tmpCtx.globalAlpha);
		_tmpCtx.stroke();
		/* TODO REMOVE ABOVE TODO */

		_tmpCtx.beginPath();
		for (var x = 0; x < sw; x++) {
			_tmpCtx.moveTo(x, firstYs[x]);
			_tmpCtx.lineTo(x, lastYs[x]);
		}
		/* TODO REMOVE BELOW TODO */
		_tmpCtx.strokeStyle = 'black';
		_tmpCtx.stroke();
		/* TODO REMOVE ABOVE TODO */

		var imgData = _tmpCtx.getImageData(0, 0, sw, sh);
		var data = imgData.data;

		for (var i = 0, iLen = data.length; i < iLen; i += 4) {
			if (data[i + 3] < 200) {
				data[i + 3] = 0;
			}
			/* TODO remove v TODO */
			else { data[i + 3] = 120; }
		}
		_tmpCtx.putImageData(imgData, 0, 0);
	}

}

function animate () {
	cube.rotation.x += 0.001;
	cube.rotation.y += 0.001;
    
    cube2.rotation.x -= 0.001;
	cube2.rotation.y += 0.001;
    
    cube3.rotation.x += 0.001;
	cube3.rotation.y -= 0.001;
    
    cube4.rotation.x -= 0.001;
	cube4.rotation.y -= 0.001;

	_renderer.render(_scene, _camera);
	if (_dirty) {
		_sceneScreenshot = _renderer.domElement.toDataURL();
		updateLabels();
		_dirty = false;
	}

	requestAnimationFrame( animate );
}

initialize();

<script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/92/three.js"></script>
<canvas id="scene" width="400" height="300"></canvas>

您可以通过上面的 jsfiddle 看到这个复杂的凸图像的内部在内部失败。

问题

因此，问题仍然存在:如果您愿意，什么是创建图像(忽略孔洞) mask 的好方法，该 mask 将覆盖背景为白色的任何复杂/凸物体的所有外部图像的组成部分不是白色的？谢谢

Answer 1

这是一个使用 flood-fill 的解决方案算法用白色覆盖外部区域，用黑色覆盖其余区域。
请记住，这是一个非常幼稚的实现，有很多优化可以完成(例如，通过计算边界矩形并仅在其中填充，另一种方法是使用 32-bit arrays 进行实际的像素分配填充时)。
另一件需要注意的事情是，填充总是从左上角开始，如果对象当前覆盖该像素，它将不起作用(但是您可以选择另一个像素开始)。

我删除了触摸处理程序和一些其他项目以保持示例简短。updateMask 函数是创建掩码的地方。

function createCube(color, x, y){
    const geo = new THREE.BoxBufferGeometry( 1, 1, 1 );
    const mat = new THREE.MeshPhysicalMaterial( { color: color, opacity: 1 } );
    const mesh = new THREE.Mesh(geo, mat);
    mesh.position.x = x;
    mesh.position.y = y;
    return mesh;
}

const c_main = document.getElementById("main");
const c_mask = document.getElementById("mask");
const ctx_mask = c_mask.getContext("2d");
ctx_mask.fillStyle = "#000";
const cw = c_main.width, ch = c_main.height;

const TWO_PI = Math.PI * 2;
const damp = 75, radius = 10, animspeed = 0.001;
const center = new THREE.Vector3(0, 0, 0);
let x1 = 0;
let phi = Math.PI / 2;

const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(35, cw / ch, 0.1, 1000);
const renderer = new THREE.WebGLRenderer({ canvas: c_main, alpha: true, antialias: false });
renderer.setPixelRatio(window.devicePixelRatio);
renderer.setSize(cw, ch);
const camLight = new THREE.PointLight(0xdfdfdf, 1.8, 300, 2);
scene.add(new THREE.HemisphereLight(0x999999, 0x555555, 1));
scene.add(new THREE.AmbientLight(0x404040));
scene.add(camLight);
const cubes = [];
cubes.push(createCube(0x2378d3, 0, 0));
cubes.push(createCube(0xc36843, -0.75, 0.75));
cubes.push(createCube(0x43f873, -0.25, 1.5));
cubes.push(createCube(0x253621, 1, 0.35));
scene.add(...cubes);

function initialize() {
    c_main.addEventListener("mousedown", mouseDown, false);
    updateCamera();
    animate();
}

function updateMask(){
    //First, fill the canvas with black
    ctx_mask.globalCompositeOperation = "source-over";
    ctx_mask.fillRect(0,0, cw, ch);
    //Then using the composite operation "destination-in" the canvas is made transparent EXCEPT where the new image is drawn.
    ctx_mask.globalCompositeOperation = "destination-in";
    ctx_mask.drawImage(c_main, 0, 0);

    //Now, use a flood fill algorithm of your choice to fill the outer transparent field with white.
    const idata = ctx_mask.getImageData(0,0, cw, ch);
    const array = idata.data;
    floodFill(array, 0, 0, cw, ch);
    ctx_mask.putImageData(idata, 0, 0);

    //The only transparency left are in the "holes", we make these black by using the composite operation "destination-over" to paint black behind everything.
    ctx_mask.globalCompositeOperation = "destination-over";
    ctx_mask.fillRect(0,0, cw, ch);
}

function mouseDown(e){
    e.preventDefault();
    x1 = e.pageX;
    const button = e.button;

    document.addEventListener("mousemove", mouseMove, false);
    document.addEventListener("mouseup", mouseUp, false);
}
function mouseUp(){
    document.removeEventListener("mousemove", mouseMove, false);
    document.removeEventListener("mouseup", mouseUp, false);
}
function mouseMove(e){
    const x2 = e.pageX;
    const dx = x2 - x1;

    phi += dx/damp;
    phi %= TWO_PI;
    if( phi < 0 ){
      phi += TWO_PI;
    }

    x1 = x2;
    updateCamera();
}


function updateCamera() {
    const x = radius * Math.cos(phi);
    const y = 0;
    const z = radius * Math.sin(phi);

    camera.position.set(x, y, z);
    camera.lookAt(center);
    camLight.position.set(x, y, z);
}
function animate(){
    cubes[0].rotation.x += animspeed;
    cubes[0].rotation.y += animspeed;
    cubes[1].rotation.x -= animspeed;
    cubes[1].rotation.y += animspeed;
    cubes[2].rotation.x += animspeed;
    cubes[2].rotation.y -= animspeed;
    cubes[3].rotation.x -= animspeed;
    cubes[3].rotation.y -= animspeed;

    renderer.render(scene, camera);
    updateMask();

    requestAnimationFrame(animate);
}

const FILL_THRESHOLD = 254;
//Quickly adapted flood fill from http://www.adammil.net/blog/v126_A_More_Efficient_Flood_Fill.html

function floodStart(array, x, y, width, height){
    const M = width * 4;
    while(true){
    let ox = x, oy = y;
    while(y !== 0 && array[(y-1)*M + x*4 + 3] < FILL_THRESHOLD){ y--; }
    while(x !== 0 && array[y*M + (x-1)*4 + 3] < FILL_THRESHOLD){ x--; }
    if(x === ox && y === oy){ break; }
  }

  floodFill(array, x, y, width, height);
}

function floodFill(array, x, y, width, height){
    const M = width * 4;

    let lastRowLength = 0;
  do{
    let rowLength = 0, sx = x;
    let idx = y*M + x*4 + 3;
    if(lastRowLength !== 0 && array[idx] >= FILL_THRESHOLD){
      do{
        if(--lastRowLength === 0){ return; }
      }
      while(array[ y*M + (++x)*4 + 3]);
      sx = x;
    }
    else{
      for(; x !== 0 && array[y*M + (x-1)*4 + 3] < FILL_THRESHOLD; rowLength++, lastRowLength++){
        const idx = y*M + (--x)*4;
        array[idx] = 255;
        array[idx + 1] = 255;
        array[idx + 2] = 255;
        array[idx + 3] = 255;
        if( y !== 0 && array[(y-1)*M + x*4 + 3] < FILL_THRESHOLD ){
          floodStart(array, x, y-1, width, height);
        }
        }
    }

    for(; sx < width && array[y*M + sx*4 + 3] < FILL_THRESHOLD; rowLength++, sx++){
        const idx = y*M + sx*4;
      array[idx] = 255;
      array[idx + 1] = 255;
      array[idx + 2] = 255;
      array[idx + 3] = 255;
    }
    if(rowLength < lastRowLength){
      for(let end=x+lastRowLength; ++sx < end; ){
        if(array[y*M + sx*4 + 3] < FILL_THRESHOLD){
            floodFill(array, sx, y, width, height);
        }
      }
    }
    else if(rowLength > lastRowLength && y !== 0){
      for(let ux=x+lastRowLength; ++ux<sx; ){
        if(array[(y-1)*M + ux*4 + 3] < FILL_THRESHOLD){
            floodStart(array, ux, y-1, width, height);
        }
      }
    }
    lastRowLength = rowLength;
  }
  while(lastRowLength !== 0 && ++y < height);
}

initialize();

<script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/92/three.js"></script>
<canvas id="main" width="300" height="200"></canvas>
<canvas id="mask" width="300" height="200"></canvas>