由浅入深用js造一个形状识别-逐梦个人博客

提到图像识别，可能更多人选择会用一些现有的库和对于识别方面比较的语言比如Python来实现，忽略了对于底层知识的学习和了解，本文我们将不借助任何图像库，使用最基础的js一步一步实现形状识别。

在开始之前，我们先准备好我们需要的html节点：

<div class="content">
    <input type="text" placeholder="特征名" id="feature">
    <input type="button" value="添加">
    识别结果：<span id="result"></span>
</div>
<canvas id="canvas"></canvas>

并设置好对应的样式：

.content {
    position: relative;
    z-index: 99;
}
#canvas {
    position: fixed;
    top: 0;
    left: 0;
    width: 100%;
    height: 100%;
}
#result {
    color: #f00;
}

我们添加了一个全屏的canvas用于接收用户的形状输入，content用于添加新特征并显示识别的结果。

在开始绘图之前，我们先做一些准备，设置canvas，并获取全局绘图环境，并初始化point类。

canvas.width = window.innerWidth;
canvas.height = window.innerHeight;

// 获得绘图上下文
const ctx = canvas.getContext('2d');

function Point(x, y) {
    this.x = x;
    this.y = y;
}

要识别用户画的形状，首先我们需要在canvas中画出用户需要的形状，在canvas中画内容主要是mousedown，mousemove，mouseup，mouseout这几个事件的应用。

canvas.addEventListener('mousedown', e => {
    if (!canvas.points) {
        canvas.points = [];
    }
    canvas.points.length = 0;
    canvas.isDragging = true;

    // 清空画布
    ctx.clearRect(0, 0, canvas.width, canvas.height);

    const point = new Point(e.layerX, e.layerY);
    canvas.points.push(point);
    
    // 这步很重要
    ctx.beginPath();
    ctx.strokeStyle = '#f00';
    ctx.moveTo(point.x, point.y);
});

canvas.addEventListener('mousemove', e => {
    if (!canvas.isDragging) {
        return;
    }
    const point = new Point(e.layerX, e.layerY);
    canvas.points.push(point);
    ctx.lineTo(point.x, point.y);
    ctx.stroke();
});

canvas.addEventListener('mouseup', e => {
    canvas.isDragging = false;
});

canvas.addEventListener('mouseout', e => {
    canvas.isDragging = false;
});

我们知道形状都是由一条条线组成的，线又是由一个个点组成的，而要组成一条线，需要很多个点，比如上图平均100多个点，图形越大点越多，但在我们识别时不可能去对比这么多的点，也不需要去对比这么多点，所以我们重新处理这些点，这个过程就是重新采样：

function calcDistance(p1, p2) {
    const dx = p2.x - p1.x;
    const dy = p2.y - p1.y;
    return +Math.sqrt(dx * dx + dy * dy).toFixed(2);
}

function calcLength(points) {
    let sum = 0;
    for (let i=1; i<points.length; i++) {
        sum += calcDistance(points[i-1], points[i]);
    }
    return Math.round(sum);
}

function reSample(points, sampleLength = 64) {
    const averageDistance = calcLength(points) / sampleLength;
    const sampledPointes = [ points[0] ];
    let tmpDistance = 0;
    for (let i=1; i<points.length; i++) {
        const prevPoint = points[i-1];
        const point = points[i];
        const distance = calcDistance(prevPoint, point);
        if (tmpDistance + distance >= averageDistance) {
            const ratio = (averageDistance - tmpDistance) / distance;
            const x = prevPoint.x + (point.x - prevPoint.x) * ratio;
            const y = prevPoint.y + (point.y - prevPoint.y) * ratio;
            const newPoint = new Point(x, y);
            sampledPointes.push(newPoint);
            points.splice(i, 0, newPoint);
            tmpDistance = 0;
        } else {
            tmpDistance += distance;
        }
    }
    return sampledPointes;
}

我们默认采样64个点，但实际采样出来并不一定是64个点，也有可能是63，65，猜测是四舍五入的问题。算法的执行过程是先计算出所有每2个点的距离的总和，然后除以我们要采样点的个数得到采样后每两个点距离的平均间距averageDistance，接着从1开始遍历点，算出2个相邻点之间的间距distance的累加值tmpDistance并和平均间距averageDistance作比较，如果小于averageDistance，则累加distance，如果大于等于averageDistance则重计算并采样该点，同时重置tmpDistance累加值为0,如此反复，最终得到采样结果sampledPointes。

其中距离计算用的欧式距离，公式如下：

在绘制图形时，用户可能随意画，所以绘制的图形的角度是不定的，比如写一个7，我可以横着写，也可以竖着写，也可以侧着写，我们需要识别这类变化，所以我们需要将其旋转回去，在这之前我们需要获取图形旋转的角度。

function getCenterPoint(points) {
    let sumX = 0, sumY = 0;
    const length = points.length;
    for (let i=0; i<points.length; i++) {
        sumX += points[i].x;
        sumY += points[i].y;
    }
    return {
        x: sumX / length,
        y: sumY / length,
    };
}

function getRadian(points) {
    const center = getCenterPoint(points);
    return Math.atan2(center.y - points[0].y, center.x - points[0].x);
}

这里定义的旋转角度（弧度制）是图形中心点和起点之间的夹角，也可以用其他的算法，这些算法在某些情况下不太准确，关于atan2的使用你可以参考：https://blog.csdn.net/weixin_42142612/article/details/80972768https://blog.csdn.net/weixin_42142612/article/details/80972768。

得到了旋转角度，我们就可以将所有的点都旋转回去了

function rotatePoints(points, radian) {
    const center = getCenterPoint(points);
    const cos = Math.cos(radian);
    const sin = Math.sin(radian);
    return points.map(point => {
        const dx = point.x - center.x;
        const dy = point.y - center.y;
        const nx = dx * cos - dy * sin + center.x;
        const ny = dx * sin + dy * cos + center.y;
        return {
            x: nx,
            y: ny,
        }
    });
}

这里使用了极坐标旋转公式，定义如下：

在绘制的过程中，用户绘制的图片的大小也不一样，我们需要将其缩放至固定的大小，便于后期的识别工作：

function getBoundingBox(points) {
    let minX = +Infinity, minY = +Infinity, maxX = -Infinity, maxY = -Infinity;
    points.forEach(point => {
        const { x, y } = point;
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, x);
        maxY = Math.max(maxY, y);
    });
    return {
        x: minX,
        y: minY,
        width: maxX - minX,
        height: maxY - minY,
    }
}

function scalePoints(points, size = 200) {
    const box = getBoundingBox(points);
    return points.map(point => {
        const { x, y } = point;
        const nx = x * (size / box.width);
        const ny = y * (size / box.height);
        return {
            x: nx,
            y: ny,
        }
    });
}

我们先获取了图形的包络线的大小，然后根据我们定义的固定大小size和包络线宽高之前的比例换算出每个点坐标。

在绘制的过程中，用户绘制图形的位置是随机的，不固定，对我们后期的识别增加了难度，为了降低后期的复杂度，我们将其中心点平移至(0, 0)点：

function translatePoints(points, { x = 0, y = 0 } = {}) {
    const center = getCenterPoint(points);
    return points.map(point => {
        return {
            x: point.x + x - center.x,
            y: point.y + y - center.y,
        }
    });
}

到这里，我们对于点的处理就结束了，总结整个过程，就是将点按照统一的规范去做归一化处理，统一形状的标准，大小，位置，角度等等，后期可以按照统一的标准来做识别。

在这些点处理完成之后，我们需要根据这些点生成特征向量：

function getVector(points) {
    let newPoints = reSample(points);
    const radian = getRadian(newPoints);
    newPoints = rotatePoints(newPoints, -radian);
    newPoints = scalePoints(newPoints);
    newPoints = translatePoints(newPoints);
    const vectors = [];
    let sum = 0;
    newPoints.forEach(({ x, y }) => {
        vectors.push(x);
        vectors.push(y);
        sum += x * x + y * y;
    });
    const magnitude = Math.sqrt(sum);
    const vector = vectors.map((item) => {
        return item / magnitude;
    });
    return vector;
}

得到的特征向量是这样的：

最后我们只需要将已定义的特征向量和当前形状的特征向量作比较就可以了：

function recognize(storedFeatures, v) {
    let similarity = -Infinity, feature = '';
    const threshold = 0.5;
    Object.keys(storedFeatures).forEach(name => {
        const vectors = storedFeatures[name];
        vectors.map(vector => {
            const distance = getDiatance(v, vector);
            if (distance >= similarity) {
                similarity = distance;
                feature = name;
            }
        });
    });
    if (similarity > threshold) {
        return feature;
    }
    return '没有匹配结果';
}

上面相似度的计算用了余弦相似度算法，关于余弦相似度相关的知识，可以参考：https://blog.csdn.net/green_lily/article/details/91872625 https://blog.csdn.net/green_lily/article/details/91872625

文章写到这里，整个图形识别就基本结束了，你可以猛戳这里查看在线demo，记得在开始识别前多加几个特征，同一特征名可以对应多个特征向量。

猛戳这里下载本文案例源码包