hayasaka
2024.02.02
210
手書きで描かれた三角形を認識するロジック解説します
図の黒い線は手書きの線です、紫色の線が認識された三角形になります
今回のロジックを思いついた経緯としてはタブレットでタッチ操作のみでフローチャート描きたい、画面のメニューボタン等を極力少なくしたいと考えた所が始まりです
Excel等にある図形パレット操作を指で描いた四角形や円からその図形が出てくるという操作にしてメニュー等のボタンを少なくできるし、描画操作でオブジェクトが湧いてくるのは楽しいかも?と思ったので作ってみました
末尾にソースコードを全て掲載します、HTML1ファイル単体で動作するように作っています
マウスゼスチャに代表されるポインティングデバイスの軌道でなんらかのアクションをするというのが基本的な使い方になると思います
Z の軌道を描いたらメニュー起動とか、VRゲームで手をトラッキングして星型を描いていたら魔法が発動するとかでしょうか?
部屋にトラッキング装置を設置して部屋の証明や暖房の調整ができてもいいかもしれません
処理1.描き始めから描き終わりまでのXY座標(マウスの軌道)を全て記録
処理2.三角形判定
「処理1」で記録した座標配列を解析し三角形であるかの判定をします
条件1.折返し(角)が3つ以上ある(任意に設定した最小角度以上であり、最大角度以下である事)
条件2.3つの角全てが同一方向への回転である(全部右回り又は全部左回り)
処理3.「処理2」の条件を全て満たしていたら三角形と断定し、3つの折返し部分を頂点とした三角形を描画する
おおまかにこのような流れで三角形の判定を行っています
マウスクリックで記録開始(描く間はずっと押しっぱなし)
クリック時のX座標、Y座標を保存
マウス移動が検出されたらX座標、Y座標を追加で保存していきます
マウスボタンが離されたら記録終了とし図形判定処理を行います
canvas.addEventListener("mousedown", function(event) {
prt("mousedown");
me.operationReset();
me.mouseTrackingX.push(event.offsetX);
me.mouseTrackingY.push(event.offsetY);
me.operationMousePress = true;
me.operationMouseRelease = false;
});
canvas.addEventListener("mouseup", function(event) {
prt("mouseup");
me.operationMousePress = false;
me.operationMouseRelease = true;
me.drawEnd();
});
canvas.addEventListener("mousemove", function(event) {
if(me.operationMousePress === true) {
me.mouseTrackingX.push(event.offsetX);
me.mouseTrackingY.push(event.offsetY);
var x = me.mouseTrackingX;
var y = me.mouseTrackingY;
var idxA = x.length - 2;
var idxB = x.length - 1;
var canvas = document.getElementById(me.constCanvasId);
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.strokeStyle = "rgb(0, 0, 0)";
ctx.moveTo(x[idxA], y[idxA]);
ctx.lineTo(x[idxB], y[idxB]);
ctx.stroke();
}
});
例えば記録されたXY座標データが100個だとしてその中から20フレームだけを処理対象とする方法を取ります
手ブレの酷い箇所を雑に取り除くためです、丁寧に手ブレ検出する方法もあるのかもしれませんが良いロジックを思いつかなかったので解析粒度を粗くすることで細かなブレを無視するというロジックにしました
4個スキップして5個目だけ採用するという処理で配列を作り直し、中間データのブレ(があると決めつけた区間)を無視します
記録したデータをそのまま解析すると瞬間的な手ブレ箇所を三角形だと誤認識してしまいます
その際にスキップする個数は動的で、大きな三角形であれば粗く解析する(スキップ数多い)、小さな三角形であれば細かく解析する(スキップ数少ない)、として解析します
var skipRate = parseInt(me.mouseTrackingX.length / self.constSensitivity);
var x = n1d.skipSampling(me.mouseTrackingX, skipRate);
var y = n1d.skipSampling(me.mouseTrackingY, skipRate);
閉じない三角形を描かれた場合を考慮しXY座標記録の先頭のいくつかをXY座標の末尾に追加して図形を閉じた状態にします
本処理を実施することで3個の角を描かれた場合でも2個の角だけの閉じていない三角形でも3個角を必要とする同じロジックで三角形判定が行なえます
x = x.concat(x.slice(0, me.constRingBufferSize));
y = y.concat(y.slice(0, me.constRingBufferSize));
前処理でデータを整えたら三角形判定処理を実行します
プログラム中の trackingIsTriangle という関数になります
XY座標配列から3点の座標を取得
処理1.「折返し」と認識できる箇所を3箇所以上検出する
処理1-1.3点の成す角度を取得
処理1-2.「処理1-1」の角度が任意の角度範囲であれば「折返し」として保存、そうでなければ保存しない
処理1-2-1.回転方向を取得し保存
処理2.以下の条件を全て満たしていたら「三角形成立」と、3点座標の構造体を返却、そうでない場合は「三角形不成立」取れただけの「折返し」座標の構造体を返却
条件1.「処理1」の結果、3箇所以上の「折返し」が発見されている
条件2.全ての「折返し」で回転方向が同一である
以下の資料を参考にした
■3点の座標から角度と回転方向を求める方法を解説!プログラムで自動化!
https://youta-blog.com/angle-and-rotation-direction/
■3点の座標から簡単に角度と回転方向を求める.
https://www5d.biglobe.ne.jp/~noocyte/Programming/Geometry/RotationDirection.html#GetAngleOnly
点A → 点B → 点C の順番で描画された場合に3点の成す角度(Bの角度)を求めます
2つのベクトル →BA、→BC とし内積を取り、公式に当てはめて cosθ を求めます
求めた cosθ を arccos 関数で ラジアンに変換します
詳細は参考資料としたサイトを御覧ください(手抜き)
function angleOf3Points(a, b, c) {
var vBA = [a.x - b.x, a.y - b.y];
var vBC = [c.x - b.x, c.y - b.y];
var dot = n2d.dot(vBA, vBC);
var normBA = Math.sqrt(Math.pow(vBA[0], 2) + Math.pow(vBA[1], 2));
var normBC = Math.sqrt(Math.pow(vBC[0], 2) + Math.pow(vBC[1], 2));
var cosTheta = dot / (normBA * normBC);
return Math.acos(cosTheta);
}
以下の資料を参考にした
■3点の回転方向を調べる
https://qiita.com/tydesign/items/d41ac74b5effd87141b8
点A → 点B → 点C の順番で描画された場合に描画方向を特定し、その描画順が三角形を右回りで描こうとしているのか、左回りで描こうとしているのかを特定します
点A → 点B → 点C の描画を「点A を中心に 点B から 点C へと回転変形した」と考えます
→AB と →AC の傾きを比較して →AC のほうが大きく傾いているのであれば左回り、そうでなければ右回りとします
詳細は参考資料としたサイトを御覧ください(手抜き)
// 折返しと認識する「最小角度」「最大角度」を設定する
// 折返しが3個以上ある場合は検査処理を実行
// 発見した折返しの最初の3個について検査処理を実行
// 3箇所全てが同じ方向への回転だった場合は三角形だとする
var dataRotate = [];
var dataRad = [];
var dataX = []
var dataY = [];
var count = 0;
for(var i = 0; i < size - 2; i += 1) {
var A = {x: x[i + 0], y: y[i + 0]};
var B = {x: x[i + 1], y: y[i + 1]};
var C = {x: x[i + 2], y: y[i + 2]};
var rad = angleOf3Points(A, B, C);
if(rad > minRad && rad < maxRad) {
var rotate = rotateDirectionOf3Points(A, B, C);
dataRotate.push(rotate);
dataRad.push(rad);
dataX.push(B.x);
dataY.push(B.y);
count += 1;
if(count >= 3) {
break;
}
}
}
//prt("dataRotate", dataRotate);
//prt("dataRad", dataRad);
//prt("dataX", dataX);
//prt("dataY", dataY);
// 折返しとみなせる物が3箇所あり、3箇所の回転方向が同一であるなら三角形の描画とする
if(count >= 3 && n1d.allEqual(dataRotate, dataRotate[0])) {
return {
ok: true,
size: dataX.length,
x: dataX,
y: dataY,
}
} else {
return {
ok: false,
size: dataX.length,
x: dataX,
y: dataY,
}
}
三角形の検出が終わったら特に特殊なロジックはありません
返却された三角形のパラメータに従い三角形を描画します
処理解説は以上です
サンプリングの粒度変更ロジックはまだ改善の余地があります、現状は「描いた長さに比例して粒度調整」ですが点と点の間の距離を見て区間別に粒度調整するのが望ましいと思います、点ABCの→ABは高速に描き、→BCはゆっくり描かれていたとしますその際に→ABは細かい粒度で判定して問題なく、→BCは荒い粒度でブレを軽減させる処置が必要になります
これは実際にある問題で三角形を描く際にそれぞれの辺を描く時の自分の手の動きを注意して観察すると分かります、素早くなめらかに描ける辺とブレやすく描くのが遅い辺があるはずです、人間の手の動きではXY軸全てに精密動作はできないはずです、人それぞれ癖があります
今回のロジックは書き順に完全に依存しています、そもそもがゼスチャーの延長なので大きな問題ではないのですが。
ただし図形を認識させるという点で考えた場合に書き順を無視して輪郭や線の検出に特化したほうが効率が良い、精度が高い場合も考えられます
目的によっては根本的なロジック変更を考えたほうが良さそうです
三角形は1つの角度と2辺が決まれば三角形を決定することが可能です、長方形は直角部分と2辺が決まれば四角形全体を決定可能です、このように理論的に可能な条件と人間に「三角形を描いてください」と指示した場合には大きな差があります、エンジニア寄りの人間は「1つの角度と2辺が決まれば三角形を決定できるのだからそれだけ描けば認識するんでしょ?」と思う可能性が高いです
人種や用途によって個人の認識差がありロジックが大幅に異なる事もありますので、自動認識ソフトを作成する時は誰向けになにを目的とした物を作るのかを考える必要があります、具体的には試験する際にエンジニアだけで終わらせずに非エンジニアにも触らせたりすればそれで良い話だとは思います
<html lang="ja">
<head>
<meta charset="utf-8">
</head>
<body>
<div id="draw_area">
<canvas id="draw_area_canvas" width="800" height="600" style="background-color: #bbbbbb;"></canvas>
</div>
<div id="config_area">
<input type="text" id="config_area_ring_buffer_size"> データの最初と最後を繋げる配列の数<br>
<input type="text" id="config_area_minimum_radian"> 最小角度係数(π/n) の n に使用されます<br>
<input type="text" id="config_area_maximum_radian"> 最大角度係数(π/n) の n に使用されます<br>
<input type="text" id="config_area_sensitivity"> 座標サンプリング係数、大きいと荒く、小さいと細かく座標を検査するようになります<br>
<button type="button" id="config_area_reset_button">
Reset
</button>
<br>
</div>
<div id="log_area">
<textarea id="log_arrea_view" style="width: 200px; height: 600px; background-color: #DDDDDD;">
</textarea>
</div>
<script type="text/javascript">
function prt() {
console.log.apply(null, arguments);
}
function Number1D() {
var self = this;
self.allEqual = function(x, n) {
for(var i = 0; i < x.length; i += 1) {
if(x[i] != n) {
return false;
}
}
return true;
}
self.skipSampling = function(x, n) {
var y = [];
for(var i = 0; i < x.length; i += 1) {
if(i % n == 0) {
y.push(x[i]);
}
}
return y;
}
}
var n1d = new Number1D();
function Number2D() {
var self = this;
self.dot = function(a, b) {
var dot = 0;
for(var i = 0; i < 2; i += 1) {
dot += a[i] * b[i];
}
return dot;
}
}
var n2d = new Number2D();
////////////////////////////////////////
// 点A→B→Cの順番に描画した場合にその描画が右回りか左回りかの判定
// 右回り = 0
// 左回り = 1
////////////////////////////////////////
function rotateDirectionOf3Points(a, b, c) {
var dy1 = b.y - a.y;
var dx1 = b.x - a.x;
var dy2 = c.y - a.y;
var dx2 = c.x - a.x;
//var leftN = dy1 / dx1;
//var rightN = dy2 / dx2;
var leftN = dx2 * dy1;
var rightN = dx1 * dy2;
if(leftN < rightN) {
return 0;
} else {
return 1;
}
}
function angleOf3Points(a, b, c) {
var vBA = [a.x - b.x, a.y - b.y];
var vBC = [c.x - b.x, c.y - b.y];
var dot = n2d.dot(vBA, vBC);
var normBA = Math.sqrt(Math.pow(vBA[0], 2) + Math.pow(vBA[1], 2));
var normBC = Math.sqrt(Math.pow(vBC[0], 2) + Math.pow(vBC[1], 2));
var cosTheta = dot / (normBA * normBC);
return Math.acos(cosTheta);
}
function trackingIsTriangle(size, minRad, maxRad, x, y) {
// 折返しと認識する「最小角度」「最大角度」を設定する
// 折返しが3個以上ある場合は検査処理を実行
// 発見した折返しの最初の3個について検査処理を実行
// 3箇所全てが同じ方向への回転だった場合は三角形だとする
var dataRotate = [];
var dataRad = [];
var dataX = []
var dataY = [];
var count = 0;
for(var i = 0; i < size - 2; i += 1) {
var A = {x: x[i + 0], y: y[i + 0]};
var B = {x: x[i + 1], y: y[i + 1]};
var C = {x: x[i + 2], y: y[i + 2]};
var rad = angleOf3Points(A, B, C);
if(rad > minRad && rad < maxRad) {
var rotate = rotateDirectionOf3Points(A, B, C);
dataRotate.push(rotate);
dataRad.push(rad);
dataX.push(B.x);
dataY.push(B.y);
count += 1;
if(count >= 3) {
break;
}
}
}
//prt("dataRotate", dataRotate);
//prt("dataRad", dataRad);
//prt("dataX", dataX);
//prt("dataY", dataY);
// 折返しとみなせる物が3箇所あり、3箇所の回転方向が同一であるなら三角形の描画とする
if(count >= 3 && n1d.allEqual(dataRotate, dataRotate[0])) {
return {
ok: true,
size: dataX.length,
x: dataX,
y: dataY,
}
} else {
return {
ok: false,
size: dataX.length,
x: dataX,
y: dataY,
}
}
}
////////////////////////////////////////
// 手書き図形補正機能クラス
////////////////////////////////////////
function HandWriteFigureCorrection() {
var self = this;
////////////////////////////////////////
// 定数
////////////////////////////////////////
self.constCanvasId = "draw_area_canvas";
self.constViewLogId = "log_arrea_view";
self.constConfigRingBufferSizeId = "config_area_ring_buffer_size";
self.constConfigMinimumRadianCoeffId = "config_area_minimum_radian";
self.constConfigMaximumRadianCoeffId = "config_area_maximum_radian";
self.constConfigSensitivityId = "config_area_sensitivity";
self.constConfigResetButtonId = "config_area_reset_button";
self.constRingBufferSize = 5;
self.constMinimumRadianCoeff = 9.0;
self.constMaximumRadianCoeff = 1.5;
self.constSensitivity = 22;
self.configRingBufferSize = self.constRingBufferSize;
self.configMinimumRadianCoeff = self.constMinimumRadianCoeff;
self.configMaximumRadianCoeff = self.constMaximumRadianCoeff;
self.configSensitivity = self.constSensitivity;
////////////////////////////////////////
// フラグ
////////////////////////////////////////
self.operationMousePress = false;
self.operationMouseRelease = false;
////////////////////////////////////////
// その他変数
////////////////////////////////////////
self.mouseTrackingX = [];
self.mouseTrackingY = [];
////////////////////////////////////////
// イベント設定
////////////////////////////////////////
self.setupEvents = function() {
var me = this;
var canvas = document.getElementById(me.constCanvasId);
canvas.addEventListener("mousedown", function(event) {
prt("mousedown");
me.operationReset();
me.mouseTrackingX.push(event.offsetX);
me.mouseTrackingY.push(event.offsetY);
me.operationMousePress = true;
me.operationMouseRelease = false;
});
canvas.addEventListener("mouseup", function(event) {
prt("mouseup");
me.operationMousePress = false;
me.operationMouseRelease = true;
me.drawEnd();
});
canvas.addEventListener("mousemove", function(event) {
if(me.operationMousePress === true) {
me.mouseTrackingX.push(event.offsetX);
me.mouseTrackingY.push(event.offsetY);
var x = me.mouseTrackingX;
var y = me.mouseTrackingY;
var idxA = x.length - 2;
var idxB = x.length - 1;
var canvas = document.getElementById(me.constCanvasId);
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.strokeStyle = "rgb(0, 0, 0)";
ctx.moveTo(x[idxA], y[idxA]);
ctx.lineTo(x[idxB], y[idxB]);
ctx.stroke();
}
});
document.getElementById(me.constConfigResetButtonId).addEventListener("click", function(event) {
me.initConfigInputs();
});
}
self.operationReset = function() {
var me = this;
var canvas = document.getElementById(me.constCanvasId);
var ctx = canvas.getContext('2d');
ctx.fillStyle = "rgb(187, 187, 187)";
ctx.fillRect(0, 0, canvas.width, canvas.height);
me.operationMousePress = false;
me.operationMouseRelease = false;
me.mouseTrackingX = [];
me.mouseTrackingY = [];
}
self.updateConfigItem = function(id, configName, configType) {
var me = this;
var elm = document.getElementById(id);
if(configType == "int") {
me[configName] = parseInt(elm.value);
} else if(configType == "float") {
me[configName] = parseFloat(elm.value);
}
}
self.updateConfig = function() {
var me = this;
var canvas = document.getElementById(me.constConfigRingBufferSizeId);
me.updateConfigItem(me.constConfigRingBufferSizeId, "configRingBufferSize", "int");
me.updateConfigItem(me.constConfigMinimumRadianCoeffId, "configMinimumRadianCoeff", "float");
me.updateConfigItem(me.constConfigMaximumRadianCoeffId, "configMaximumRadianCoeff", "float");
me.updateConfigItem(me.constConfigSensitivityId, "configSensitivity", "int");
}
self.initConfigInputs = function() {
var me = this;
document.getElementById(me.constConfigRingBufferSizeId).value = String(me.constRingBufferSize);
document.getElementById(me.constConfigMinimumRadianCoeffId).value = String(me.constMinimumRadianCoeff);
document.getElementById(me.constConfigMaximumRadianCoeffId).value = String(me.constMaximumRadianCoeff);
document.getElementById(me.constConfigSensitivityId).value = String(me.constSensitivity);
}
self.test1 = function() {
var me = this;
var x = me.mouseTrackingX;
var y = me.mouseTrackingY;
var size = x.length;
var idxA = 0;
var idxB = parseInt(size / 2);
var idxC = size - 1;
var canvas = document.getElementById(me.constCanvasId);
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.strokeStyle = "rgb(255, 0, 0)";
ctx.moveTo(x[idxA], y[idxA]);
ctx.lineTo(x[idxB], y[idxB]);
ctx.lineTo(x[idxC], y[idxC]);
ctx.stroke();
var plotX = [x[idxA], x[idxB], x[idxC]];
var plotY = [y[idxA], y[idxB], y[idxC]];
ctx.font = "16px serif";
ctx.fillStyle = "rgb(0, 0, 0)";
ctx.fillText("A(" + String(plotX[0]) + ", " + String(plotY[0]) + ")", plotX[0], plotY[0]);
ctx.fillText("B(" + String(plotX[1]) + ", " + String(plotY[1]) + ")", plotX[1], plotY[1]);
ctx.fillText("C(" + String(plotX[2]) + ", " + String(plotY[2]) + ")", plotX[2], plotY[2]);
var rotate = rotateDirectionOf3Points({x: plotX[0], y: plotY[0]}, {x: plotX[1], y: plotY[1]}, {x: plotX[2], y: plotY[2]});
var rad = angleOf3Points({x: plotX[0], y: plotY[0]}, {x: plotX[1], y: plotY[1]}, {x: plotX[2], y: plotY[2]});
var degree = rad * (180 / Math.PI);
var lines = ["rad: " + String(rad), "degree: " + String(degree), "rotate: " + String(rotate)];
for(var i = 0; i < plotX.length; i += 1) {
var txt = "X=" + String(plotX[i]) + ", Y=" + String(plotY[i]);
lines.push(txt);
}
var logView = document.getElementById(me.constViewLogId);
var logText = lines.join("\n");
logView.value = lines.join("\n");
}
////////////////////////////////////////
// 描画終了処理
////////////////////////////////////////
self.drawEnd = function() {
var me = this;
me.updateConfig();
prt("configRingBufferSize", me.configRingBufferSize);
prt("configMinimumRadianCoeff", me.configMinimumRadianCoeff);
prt("configMaximumRadianCoeff", me.configMaximumRadianCoeff);
prt("configSensitivity", me.configSensitivity);
prt(me.mouseTrackingX);
prt(me.mouseTrackingY);
var skipRate = parseInt(me.mouseTrackingX.length / self.constSensitivity);
prt("skipRate", skipRate);
var x = n1d.skipSampling(me.mouseTrackingX, skipRate);
var y = n1d.skipSampling(me.mouseTrackingY, skipRate);
x = x.concat(x.slice(0, me.constRingBufferSize));
y = y.concat(y.slice(0, me.constRingBufferSize));
var res = trackingIsTriangle(
x.length,
Math.PI / me.constMinimumRadianCoeff,
Math.PI / me.constMaximumRadianCoeff,
x,
y);
if(0) {
me.test1();
} else {
var logView = document.getElementById(me.constViewLogId);
var lines = ["三角形: " + String(res.ok ? "true": "false")];
for(var i = 0; i < res.size; i += 1) {
lines.push("座標 " + String(i + 1) + ": " + String(res.x[i]) + ", " + String(res.y[i]));
}
var logText = lines.join("\n");
logView.value = lines.join("\n");
if(res.ok === true) {
var canvas = document.getElementById(me.constCanvasId);
var ctx = canvas.getContext('2d');
ctx.beginPath();
ctx.strokeStyle = "rgb(255, 0, 255)";
ctx.moveTo(res.x[0], res.y[0]);
ctx.lineTo(res.x[1], res.y[1]);
ctx.lineTo(res.x[2], res.y[2]);
ctx.lineTo(res.x[0], res.y[0]);
ctx.stroke();
}
}
}
self.start = function() {
var me = this;
me.initConfigInputs();
me.setupEvents();
}
}
window.addEventListener('load', function(){
var x = new HandWriteFigureCorrection();
x.start();
});
</script>
</body>
</html>
293
hayasaka
2024.02.20
183
金子
2024.01.04
101
金子
2024.01.04