Алгоритм распознавания двухмерных фигур - поиск руководства
Мне нужна возможность убедиться, что пользователь правильно нарисовал фигуру, начиная с простых фигур, таких как круг, треугольник, и более сложных фигур, таких как буква А.
Мне нужно уметь вычислять правильность в реальном времени, например, если пользователь должен нарисовать круг, но рисует прямоугольник, я надеюсь, что смогу обнаружить это во время рисования.
Есть несколько разных подходов к распознаванию формы, к сожалению, у меня нет опыта или времени, чтобы попробовать их все и посмотреть, что работает.
Какой подход вы бы порекомендовали для этой конкретной задачи?
Ваша помощь ценится.
3 ответа
Мы можем определить "распознавание" как способность обнаруживать особенности / характеристики в элементах и сравнивать их с характеристиками известных элементов, обнаруженных в нашем опыте. Объекты со схожими функциями, вероятно, являются похожими объектами. Чем выше количество и сложность функций, тем больше наша способность различать подобные объекты.
В случае фигур мы можем использовать их геометрические свойства, такие как количество углов, значения углов, количество сторон, размеры сторон и так далее. Поэтому, чтобы выполнить вашу задачу, вы должны использовать алгоритмы обработки изображений для извлечения таких признаков из чертежей.
Ниже я представлю очень простой подход, который показывает эту концепцию на практике. Мы узнаем разные формы, используя количество углов. Как я сказал: "Чем выше количество и сложность функций, тем больше наша способность различать подобные объекты". Так как мы используем только одну особенность - количество углов, мы можем различать несколько разных видов фигур. Фигуры с одинаковым количеством углов не будут различаться. Поэтому, чтобы улучшить подход, вы можете добавить новые функции.
ОБНОВИТЬ:
Для выполнения этой задачи в режиме реального времени вы можете извлечь функции в режиме реального времени. Если объект для рисования представляет собой треугольник и пользователь рисует четвертую сторону любой другой фигуры, вы знаете, что он или она не рисует треугольник. Что касается уровня корректности, вы можете рассчитать расстояние между вектором объекта нужного объекта и нарисованным.
Входные данные :
Алгоритм
- Уменьшите входное изображение, так как требуемые функции могут быть обнаружены в более низком разрешении.
- Сегментируйте каждый объект для обработки независимо.
- Для каждого объекта извлеките его особенности, в данном случае просто количество углов.
- Используя особенности, классифицируйте форму объекта.
Программное обеспечение:
Представленное ниже программное обеспечение было разработано на Java и с использованием Marvin Image Processing Framework. Однако вы можете использовать любой язык программирования и инструменты.
import static marvin.MarvinPluginCollection.floodfillSegmentation;
import static marvin.MarvinPluginCollection.moravec;
import static marvin.MarvinPluginCollection.scale;
public class ShapesExample {
public ShapesExample(){
// Scale down the image since the desired features can be extracted
// in a lower resolution.
MarvinImage image = MarvinImageIO.loadImage("./res/shapes.png");
scale(image.clone(), image, 269);
// segment each object
MarvinSegment[] objs = floodfillSegmentation(image);
MarvinSegment seg;
// For each object...
// Skip position 0 which is just the background
for(int i=1; i<objs.length; i++){
seg = objs[i];
MarvinImage imgSeg = image.subimage(seg.x1-5, seg.y1-5, seg.width+10, seg.height+10);
MarvinAttributes output = new MarvinAttributes();
output = moravec(imgSeg, null, 18, 1000000);
System.out.println("figure "+(i-1)+":" + getShapeName(getNumberOfCorners(output)));
}
}
public String getShapeName(int corners){
switch(corners){
case 3: return "Triangle";
case 4: return "Rectangle";
case 5: return "Pentagon";
}
return null;
}
private static int getNumberOfCorners(MarvinAttributes attr){
int[][] cornernessMap = (int[][]) attr.get("cornernessMap");
int corners=0;
List<Point> points = new ArrayList<Point>();
for(int x=0; x<cornernessMap.length; x++){
for(int y=0; y<cornernessMap[0].length; y++){
// Is it a corner?
if(cornernessMap[x][y] > 0){
// This part of the algorithm avoid inexistent corners
// detected almost in the same position due to noise.
Point newPoint = new Point(x,y);
if(points.size() == 0){
points.add(newPoint); corners++;
}else {
boolean valid=true;
for(Point p:points){
if(newPoint.distance(p) < 10){
valid=false;
}
}
if(valid){
points.add(newPoint); corners++;
}
}
}
}
}
return corners;
}
public static void main(String[] args) {
new ShapesExample();
}
}
Выход программного обеспечения:
figure 0:Rectangle
figure 1:Triangle
figure 2:Pentagon
Другой способ заключается в том, что вы можете использовать математику в этой задаче, используя среднее значение каждой точки, наименьшее расстояние от той, с которой вы сравниваете ее, сначала вы должны изменить размеры фигуры с помощью тех, которые находятся в вашей библиотеке форм, а затем:
function shortestDistanceSum( subject, test_subject ) {
var sum = 0;
operate( subject, function( shape ){
var smallest_distance = 9999;
operate( test_subject, function( test_shape ){
var distance = dist( shape.x, shape.y, test_shape.x, test_shape.y );
smallest_distance = Math.min( smallest_distance, distance );
});
sum += smallest_distance;
});
var average = sum/subject.length;
return average;
}
function operate( array, callback ) {
$.each(array, function(){
callback( this );
});
}
function dist( x, y, x1, y1 ) {
return Math.sqrt( Math.pow( x1 - x, 2) + Math.pow( y1 - y, 2) );
}
var square_shape = Array; // collection of vertices in a square shape
var triangle_shape = Array; // collection of vertices in a triangle
var unknown_shape = Array; // collection of vertices in the shape your'e comparing from
square_sum = shortestDistanceSum( square_shape, unknown_shape );
triangle_sum = shortestDistanceSum( triangle_shape, unknown_shape );
Где самая низкая сумма - самая близкая форма.
У вас есть два входа - исходное изображение и пользовательский ввод - и вы ищете логический результат.
В идеале вы должны конвертировать все ваши входные данные в сопоставимый формат. Вместо этого вы также можете параметризовать оба типа ввода и использовать контролируемый алгоритм машинного обучения (ближайший сосед приходит на ум для замкнутых фигур).
Хитрость в том, чтобы найти правильные параметры. Если ваш ввод представляет собой плоский файл изображения, это может быть двоичное преобразование. Если пользовательский ввод является движением смахивания или пером, я уверен, что есть способы записать и отобразить это как двоичный файл, но алгоритм, вероятно, был бы более надежным, если бы он использовал данные, наиболее близкие к исходному вводу.