Алгоритмы распознавания фигур

Автор: | 05.02.2018

Моделирование задачи распознавания прямоугольников
Распознавание фигур на основе «выборки для обучения»
Распознавание фигур «через самообучение»
Сортировка плоских деталей
Алгоритм задачи “Разбор завала”

Программные реализации:

Формирование контуров
Распознавание прямоугольников (по признаку равенства сторон и диагоналей)
Распознавание прямоугольников (по признаку прямого угла)

Моделирование задачи распознавания прямоугольников

Постановка задачи определяется целью и возможностями ее реализации.

Цель. Разработать программу классификации деталей прямоугольной формы на качественные и бракованные.

Возможности для реализации задачи определяются возможностями компьютера. Компьютер способен обрабатывать числовую информацию в алгоритмической последовательности. Чтобы реализовать возможности компьютера необходимо смоделировать решаемую задачу.

Моделирование с применением компьютера подразумевает переход от реального объекта (мира) к кодированному описанию его свойств при помощи данных и операций над ними. Такой переход, как правило, выполняется в несколько этапов:

Абстракция – выбор наиболее существенных признаков объекта с точки зрения поставленной задачи.

Необходимо провести исследования, которые позволяют от объекта моделирования перейти к субъекту моделирования отбросив все лишнее в соответствии с целью в поставленной задаче

Чем отличается прямоугольник от других четырёхугольников?

  • Равенство противоположных сторон.
  • Параллельность противоположных сторон.
  • Равенство диагоналей.
  • Все углы прямые.

Какой минимум признаков нужен для однозначного решения задачи?

  • Равенство 2-х противоположных сторон + равенство диагоналей.
  • Параллельность 2-х противоположных сторон + равенство диагоналей.
  • Три угла прямые.

Итак, благодаря абстракции мы получили словесную информационную модель. Но, она еще пока непонятна для компьютера. Он понимает математическую модель, представленную в виде алгоритма и  реализованную программно.

Методика реализации задачи.

Чертёж качественной детали (прямоугольника) или бракованной детали (четырехугольника) выполняется из отрезков (команда LINE) в графической системе AutoCAD и экспортируется в DXF-файл. Программа kntrs.lsp (см. описание программы) считывает из DXF-файла данные об отрезках (координаты вершин) и записывает их в текстовый файл vrtks.txt в круговом порядке обхода вершин.

 

 

Текстовый файл vrtks.txt можно создать вручную, снимая координаты вершин непосредственно с чертежа.

Разработанная программа rct.lsp должна считывать данные из файла vrtks.txt, анализировать их и выводить в файл result.txt запись о соответствии детали требованиям (прямоугольник или нет).

Формализация признаков

Равенство длин отрезков (сторон или диагоналей): Длина каждого отрезка определяется как гипотенуза прямоугольного прямоугольника (по теореме Пифагора) через разницу координат отрезков:

(setq DX12 (abs (- X1 X2)))
(setq DY12 (abs (- Y1 Y2)))
(setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))

Параллельность прямых: K2= K1, где К – угловой коэффициент прямой К=(Y2-Y1)/(X2-X1)

Как формализовать понятие «Прямой угол»? В рамках поставленной задачи наличие «Прямого угла» можно определить по признаку перпендикулярности отрезков: K2= -1/K1, где К – угловой коэффициент прямой. К=(Y-Y0)/(X-X0).

Отображение модели  в компьютере

Любая информация в конечном итоге отображается в компьютере с помощью двоичных чисел (кодов) во внутримашинную модель. Ранее кодирование осуществлялось программистом. Сейчас основная часть программ создаётся на алгоритмических языках. Преобразование во внутримашинную модель осуществляется автоматически с помощью программ-трансляторов.

Программная реализация 1: Распознавание прямоугольника по признакам «равенство диагоналей» и «равенство противоположных сторон».

; Проверка выполнения признаков в пределах погрешности E 
(setq E 1.0) ; погрешность Е=1.0
(setq DDIG (abs (- DIG1 DIG2)))
(setq DDA (abs (- DA1 DA2))) 
(if (and (<= DDIG E) (<= DDA E))…

Программная реализация 2: Распознавание прямоугольника по признакам наличия «прямых углов».

;Проверка признаков D1=-1/D2 для смежных отрезков в пределах погрешности E
(setq D12 (abs (- D1 (/ 1 D2))))
(setq D23 (abs (- D2 (/ 1 D3))))
(setq D34 (abs (- D3 (/ 1 D4))))
(setq D41 (abs (- D4 (/ 1 D1))))
(setq E 0.05) ; погрешность E=0.05
(if (and (<= D12 E) (<= D23 E) (<= D34 E) (<= D41 E))…

Контрольные задания. Разработать следующие программные приложения:

  1. Распознавание равностороннего треугольника на основе программной реализация 1
  2. Распознавание равнобедренного треугольника на основе программной реализация 1
  3. Распознавание прямоугольного треугольника на основе программной реализация 2
  4. Распознавание равнобедренного прямоугольного треугольника на основе программной реализация 1 и программной реализация 2

Задания 1-3 моделируются по аналогии с рассмотренной выше задачи  “Распознавание прямоугольника” на основе одной из 2-х программных реализаций.

Распознавание фигур на основе «выборки для обучения»

Введение в проблему

Ранее была рассмотрена задача распознавания изображения «по инструкции». В ней условия для определения типа фигуры вносятся в программу в готовом виде.

В отличие от предыдущей в этой задаче условия для определения типа фигуры задаются не явно, а формируются программно – на основе выборки фигур для обучения.

Практическое значение такой задачи может иметь место, например, на производстве – при сортировке деталей с возможностью перенастройки устройства под определенный тип детали. Если, при использовании первой программы для перенастройки требуется модифицировать программу, то при использовании второй программы достаточно показать сортирующему устройству, какие детали относятся к определенной группе.

Рекомендуемый алгоритм обработки данных

Для каждой из 3-х комбинаций сторон (a-b, b-c, a-c) установим по два признака (равенство и перпендикулярность сторон). Наличие (1) или отсутствие (0) признака определяется из элементарных геометрических соотношений по координатам вершин (см. формализация признаков). Тип треугольника определяется из условий (см.табл.)

Условия для определения типа треугольника формируются программно из элементарных признаков с помощью булевых операций:

Тип треугольника можно определить с помощью булевой функции

где значение аргументов – значения признаков треугольников (см. табл.).

Аргументы, при которых значение функции равно 1, определяются по данным о выборке треугольников для обучения. Например, пусть функция Y = F(X) принимает значение 1 при

а в других случаях – значение 0. Формула запишется:

Знак отрицания ставится над аргументами, значение которых равно 0. Эту формулу можно записать на языке LISP следующим образом:

При подстановке в формулу значений признаков треугольника, который тестируется, например, (0 0 0 1 0 0), функция Y = F(X) принимает значение 1, если тип этого треугольника соответствует типу хотя бы одного из треугольников для обучения.

Распознавание фигур «через самообучение»

С помощью компьютера можно решить задачу классификации, если явно указать признак (или через обучение), по которому производится классификация. А если этот признак не указывать? Можно ли на компьютере реализовать такую задачу? Ниже приводится постановка задачи, в которой в определенной степени демонстрируется такая возможность.

Создать программу, обеспечивающую классификацию треугольников на основе самостоятельно выбираемого существенного признака. Программа должна считывать из DXF-файла данные о примитивах чертежа (отрезках) и по координатам вершин определить типы треугольников (сформировать совокупность признаков-характеристик образа), затем выбрать существенные признаки для представленной выборки треугольников и, наконец – классифицировать треугольники по этим признакам. Существенными признаками могут быть элементарные признаки (например, размер фигуры), либо совокупность признаков-характеристик образа (тип треугольника). Примеры:

Пример 1 – существенный признак “равнобедренный треугольник”

Пример 2 – существенные признаки “размер фигуры” и “прямоугольный треугольник”

Пример 3 – существенные признаки “прямоугольный треугольник” и “равнобедренный треугольник”


Существенным для классификации является признак (условие), который повторяется для нескольких треугольников из выборки, причем разделяет элементы выборки приблизительно пополам.

Сортировка плоских деталей

 Разработать программное приложение, обеспечивающее  сортировку деталей на качественные (проходные) и бракованные. Информация о тестируемых деталях поступает в виде отсканированного изображения в формате BMP- файла. В начале обрабатывается файл отсканированных годных (проходных) деталей. Характерные параметры  и свойства этих деталей определяются с помощью операции векторизации отсканированных профилей. Эти параметры заносятся в базу данных (файл). В дальнейшем аналогичным образом определяются характеристики тестируемых деталей, сравниваются с характеристиками проходных деталей из базы данных и выносится решение о годности детали. Бракованные детали выделяются.

Типы распознаваемых деталей (четырехугольник и треугольник, или один из них). Качественные детали могут отличаться от бракованных по признакам равенства углов и сторон.

Рисунок для обучения:

Рисунок для тестирования:

Программа после обучения должна определить, что правильные фигуры – прямоугольник и прямоугольный треугольник. Неправильные фигуры выделяются красным цветом.

Алгоритм задачи “Разбор завала”

Введение в проблему.

При визуальном восприятии окружающего мира человеку приходится решать множество задач. Одна из них – синтез образов из более простых элементов. Может существовать множество вариантов объединения элементов в образы. Человек выбирает наиболее правильные варианты. При этом он способен определить недостающие (перекрываемые или плохо видимые) элементы образов.

Возможности имитации задачи синтеза образов обычно исследуются на решении конкретных узкоспециализированных задач. В литературе по проблемам искусственного интеллекта упоминается задача «разбор завала». Суть задачи заключается в создании роботизированной системы, обеспечивающей последовательную разборку беспорядочно сваленных в кучу деталей. Для выбора и захвата механизмом детали необходимо определить контуры деталей, и выяснить, какая деталь находится сверху. Другое возможное приложение подобной задачи – синтез объектов чертежа при его чтении.

Постановка задачи.

Разработать программу, которая по чертежу, имитирующему цилиндрические детали, восстанавливает (если это может и человек) контуры перекрывающихся фигур и определяет, какие детали находятся сверху.

Детали имитируются прямоугольниками . Чертёж из прямоугольников выполняется из отрезков в графической системе (например, в системе AutoCAD) и экспортируется в DXF-файл. Этот файл наряду с другой информацией содержит данные о примитивах чертежа (отрезках) и их параметрах (координатах вершин). Разработанная программа должна считывать и анализировать данные из DXF файла.

Формализация задачи

По каким признакам человек выделяет цилиндрическую деталь, контуры которой (прямоугольник) частично перекрыты другими деталями?

  • Принадлежность отрезков одной прямой (уравнение Y=K*X+B): равенство угловых коэффициентов K отрезков, где K=(Y1-Y2)/(X1-X2); равенство коэффициентов отрезков B, где B=Y1-K*X1.
  • Наличие прямых углов между отрезками.
  • Взаимное расположение углов – параллельность (K2= K1) или перпендикулярность сторон углов (K2= — 1/ K1).

Какой минимум необходим для определения контура прямоугольника?

  • Достаточно знать положение двух диагональных углов прямоугольника.

Какие параметры определяют прямые углы?

  • Координаты вершины (X Y) и угловой коэффициент К1 одной из сторон. Угловой коэффициент другой стороны определяется соотношением (K2= — 1/ K1)

Какие признаки необходимы для формирования прямого угла?

  • Наличие парного отрезка, выходящего из вершины под прямым углом.
  • Какие признаки для отбора углов, принадлежащих одному прямоугольнику?
  • Параллельность или перпендикулярность сторон углов.

Как определить, что углы диагональные?

  • Нужно сравнить угловой коэффициент отрезка, который соединяет вершины и угловой коэффициент стороны угла.

Каким образом определяются прямоугольники, которые не перекрываются?

  • Сравнивается периметр прямоугольника (определяется по диагональным углам) с суммой длин отрезков вдоль сторон прямоугольника.

Программные реализации

Формирование контуров

;***************************************************************************
; kntrs.lsp
; ФОРМИРОВАНИЕ КОНТУРОВ МНОГОУГОЛЬНИКОВ
; Программа считывает из DXF-файла данные об отрезках (коорд. вершин),
; затем отбирает из них те, которые образуют замкнутые контуры. Данные о
; контурах (координаты вершин и их количество) записываются в файл.
;***************************************************************************
; НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ
(defun C:kntrs()
; Чтение DXF-файла и формирование списка из отрезков
(setq fr (open "a.dxf" "r"))
(setq str (read-line fr)) ; читаем первую строку
(while (/= str "EOF") ; EOF-последняя строка DXF-файла
(if (= str "LINE") (lst_ln)) ; формирование списка отрезков
(setq str (read-line fr)) ; читаем следующую строку
)
(close fr)
; Считывание списка, отбор отрезков и формирование файла контура ломаной
(setq fw (open "vrtks.txt" "w"))
(setq N 0)
(setq NS 0) ; NS - текущий номер элемента списка
(setq NK (length FL)) ; NK - число элементов списка
(setq NK (1- NK)) ; NK - номер последнего элемента списка
(while (<= NS NK)
(setq TPL (car (nth NS FL)))
(if (= TPL "LINE")
(progn
(par_ln) ; считывание списка параметров точек отрезка
(rules) ; отбор отрезков и формирование файла контуров
)
)
(setq NS (+ NS 1))
)
(write-line "END" fw) ; END записываем в файл
(close fw)
)
; КОНЕЦ ОСНОВНОЙ ПРОГРАММЫ
; **********************************************************************

; Формирование списка из отрезков по данным из файла fr (*.dxf)
(defun lst_ln()
(repeat 11 (read-line fr)) ; переход к следующей строке
(setq X1 (atof (read-line fr))) ; чтение значения X1 из файла fr
(read-line fr)
(setq Y1 (atof (read-line fr))) ; чтение значения Y1 из файла fr
(read-line fr)
(setq Z1 (atof (read-line fr))) ; чтение значения Z1 из файла fr
(read-line fr)
(setq X2 (atof (read-line fr))) ; чтение значения X2 из файла fr
(read-line fr)
(setq Y2 (atof (read-line fr))) ; чтение значения Y2 из файла fr
(read-line fr)
(setq Z1 (atof (read-line fr))) ; чтение значения Z1 из файла fr
(setq P1 (list X1 Y1)) ; P1 и P2 - списки координат
(setq P2 (list X2 Y2)) ; точек отрезка
(setq LN (list "LINE" P1 P2)) ; LN-список точек отрезка
(setq FL (cons LN FL)) ; FL- список из подсписков LN
)
; **********

; Извлечение из списка FL коорд. вершин и формирование списков точек отрезка
(defun par_ln()
(setq X1 (car (cadr (nth NS FL))))
(setq Y1 (cadr (cadr (nth NS FL))))
(setq X2 (car (caddr (nth NS FL))))
(setq Y2 (cadr (caddr (nth NS FL))))
(setq P1 (list X1 Y1))
(setq P2 (list X2 Y2))
)
; ********
; Правила обеспечивают выбор из списка непрерывных отрезков и проверяют
; ломаную на замкнутость. Данные о контуре записываются в файл.
(defun rules()
; Правило_1
; Если первый отрезок из списка, то данные о нём записываются в файл
(if (= N 0)
(progn
(write-line "KONTUR\n" fw)
(princ X1 fw) ; значение X1 записываем в файл
(write-line "" fw) ; пустую строку записываем в файл
(princ Y1 fw) ; значение Y1 записываем в файл
(write-line "\n" fw) ; перевод строки в файле
(princ X2 fw) ; значение X2 записываем в файл
(write-line "" fw) ; пустую строку записываем в файл
(princ Y2 fw) ; значение Y2 записываем в файл
(write-line "\n" fw) ; перевод строки в файле
(setq PN P1) ; т.P1 объявл. начальной т. ломаной
(setq PK1 P2) ; т.P2 объявл. конечной т. ломаной
(setq N1 1) ; колич. вершин ломаной = 1
(setq METKA 1) ; не вносить отрезок в новый список
)
)
; Правило_2
; Если точка P1 текущeго отрезка в списке совпадает с точкой PK ломаной,
; но отрезок не замыкает контур
(if (and (>= N 1) (equal P1 PK) (not (equal P2 PN)))
(progn
(princ X2 fw) ; значение X2 записываем в файл
(write-line "" fw) ; пустую строку записываем в файл
(princ Y2 fw) ; значение Y2 записываем в файл
(write-line "\n" fw) ; перевод строки в файле
(setq PK1 P2) ; т.P2 объявл. конечной т. ломаной
(setq N1 (1+ N)) ; колич. вершин увелич. на 1
(setq METKA 1) ; не вносить отрезок в новый список
)
)
; Правило_3
; Если точка P2 текущeго отрезка в списке совпадает с точкой PK ломаной,
; но отрезок не замыкает контур
(if (and (>= N 1) (equal P2 PK) (not (equal P1 PN)))
(progn
(princ X1 fw) ; значение X1 записываем в файл
(write-line "" fw) ; пустую строку записываем в файл
(princ Y1 fw) ; значение Y1 записываем в файл
(write-line "\n" fw) ; перевод строки в файле
(setq PK1 P1) ; т.P1 объявл. конечной т. ломаной
(setq N1 (1+ N)) ; колич. вершин увелич. на 1
(setq METKA 1) ; не вносить отрезок в новый список
)
)
; Правило_4
; Если текущий отрезок в списке замыкает контур,
(if (or (and (>= N 1) (equal P1 PK) (equal P2 PN))
(and (>= N 1) (equal P2 PK) (equal P1 PN))
)
(progn
(setq N1 (1+ N)) ; колич. вершин увелич. на 1
(princ N1 fw) ; число вершин контура запис. в файл
(write-line "\n" fw) ; перевод строки в файле
(setq N1 0) ; задаем условие первого отрезка контура
(setq METKA 1) ; не вносить отрезок в новый список
)
)
; Правило_5
; Если текущий отрезок не примыкает к контуру, внести его в новый список
(if (= METKA nil)
(progn
(setq LN1 (list "LINE" P1 P2)) ; LN1-список точек отрезка
(setq FL1 (cons LN1 FL1)) ; FL1- список из подсписков LN1
)
)
; Правило_6
; Если последний отрезок в списке не замыкает контур,
(if (or (and (= NS NK) (not (equal P2 PN)))
(and (= NS NK) (not (equal P1 PN)))
)
(progn
(setq NS -1) ; повторить чтение списка c 0-го элемента
(setq FL FL1) ; список из отрезков которые не вошли в контур
(setq NK (length FL)) ; NK - число элементов нового списка
(setq NK (1- NK)) ; NK - номер последнего элемента списка
(setq FL1 nil) ; обнулить FL1- список из подсписков LN1
)
)
; Подготовка к следующему циклу
(setq N N1)
(setq PK PK1)
(setq METKA nil)
)
; ******

 

Распознавание прямоугольников (по признаку равенства противоположных сторон и диагоналей)

;**************************************************************************
; РАСПОЗНАВАНИЕ ПРЯМОУГОЛЬНИКА
; Программа считывает из файла данные о контуре детали (коорд.вершин)
; и определяет, прямоугольная деталь или нет по признакам
; "равенство диагоналей" и "равенство противоположных сторон"
;**************************************************************************

(defun C:rct()
(setq f (open "vrtks.txt" "r")) ; чтение файла
(read-line f) ; КОНТУР
(read-line f)
(setq X1 (atof (read-line f))) ; 277.331
(setq Y1 (atof (read-line f))) ; 229.567
(read-line f)
(setq X2 (atof (read-line f))) ; 129.751
(setq Y2 (atof (read-line f))) ; 155.777
(read-line f)
(setq X3 (atof (read-line f))) ; 161.056
(setq Y3 (atof (read-line f))) ; 93.1672
(read-line f)
(setq X4 (atof (read-line f))) ; 308.636
(setq Y4 (atof (read-line f))) ; 166.957
(close f)
; Определяем размеры сторон DA,DB и диагоналей DIG
(setq DX12 (abs (- X1 X2)))
(setq DY12 (abs (- Y1 Y2)))
(setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))
(setq DX43 (abs (- X4 X3)))
(setq DY43 (abs (- Y4 Y3)))
(setq DA2 (sqrt (+ (* DX43 DX43) (* DY43 DY43))))
(setq DX14 (abs (- X1 X4)))
(setq DY14 (abs (- Y1 Y4)))
(setq DB1 (sqrt (+ (* DX14 DX14) (* DY14 DY14))))
(setq DX23 (abs (- X2 X3)))
(setq DY23 (abs (- Y2 Y3)))
(setq DB2 (sqrt (+ (* DX23 DX23) (* DY23 DY23))))
(setq DIG1 (sqrt (+ (* DA1 DA1) (* DB1 DB1))))
(setq DIG2 (sqrt (+ (* DA2 DA2) (* DB2 DB2))))
; Проверка выполнения признаков в пределах погрешности E
(setq E 0.05) ; погрешность Е=0.05
(setq DDIG (abs (- DIG1 DIG2)))
(setq DDA (abs (- DA1 DA2)))
(if (and (<= DDIG E) (<= DDA E))
(progn ; действия при выполнении признаков
(setq f1 (open "res.txt" "w")) ; запись в файл
(write-line "RECTANGLE" f1) ; RECTANGLE
(write-line "" f1)
(princ "A=" f1) ; A=164.999
(princ DA1 f1)
(write-line "\n" f1) ; B=70.001
(write-line "" f1)
(princ "B=" f1)
(princ DB1 f1)
(close f1)
)
(progn ; действия при невыполнении признаков
(setq f1 (open "res.txt" "w")) ; запись в файл
(write-line "BRAK" f1) ; BRAK
(close f1)
)
)
)

Распознавание прямоугольников (по признаку прямого угла)

;**************************************************************************
; РАСПОЗНАВАНИЕ ПРЯМОУГОЛЬНИКА
; Программа считывает из файла данные о контуре детали (коорд.вершин)
; и определяет, прямоугольная деталь или нет по признакам "прямого угла"
;**************************************************************************

(defun C:rct1()
(setq f (open ("vrtks.txt" "r")) ; чтение файла
(read-line f) ; КОНТУР
(read-line f)
(setq X1 (atof (read-line f))) ; 277.331
(setq Y1 (atof (read-line f))) ; 229.567
(read-line f)
(setq X2 (atof (read-line f))) ; 129.751
(setq Y2 (atof (read-line f))) ; 155.777
(read-line f)
(setq X3 (atof (read-line f))) ; 161.056
(setq Y3 (atof (read-line f))) ; 93.1672
(read-line f)
(setq X4 (atof (read-line f))) ; 308.636
(setq Y4 (atof (read-line f))) ; 166.957
(close f)
; Определение разности координат DX и DY смежных отрезков и отношения DY/DX
(setq DX12 (abs (- X1 X2)))
(setq DY12 (abs (- Y1 Y2)))
(setq D1 (/ DY12 DX12))
(setq DX23 (abs (- X2 X3)))
(setq DY23 (abs (- Y2 Y3)))
(setq D2 (/ DY23 DX23))
(setq DX34 (abs (- X3 X4)))
(setq DY34 (abs (- Y3 Y4)))
(setq D3 (/ DY34 DX34))
(setq DX41 (abs (- X4 X1)))
(setq DY41 (abs (- Y4 Y1)))
(setq D4 (/ DY41 DX41))
; Проверка признаков D1=-1/D2 для смежных отрезков в пределах погрешности E
(setq D12 (abs (- D1 (/ 1 D2))))
(setq D23 (abs (- D2 (/ 1 D3))))
(setq D34 (abs (- D3 (/ 1 D4))))
(setq D41 (abs (- D4 (/ 1 D1))))
(setq E 0.05) ; погрешность E=0.05
(if (and (<= D12 E) (<= D23 E) (<= D34 E) (<= D41 E))
(progn ; действия при выполнении признаков
(setq DA (sqrt (+ (* DX12 DX12) (* DY12 DY12)))) ; размеры
(setq DB (sqrt (+ (* DX23 DX23) (* DY23 DY23)))) ; сторон
(setq f1 (open "res.txt" "w")) ; запись в файл
(write-line "RECTANGLE" f1) ; RECTANGLE
(write-line "" f1)
(princ "A=" f1) ; A=164.999
(princ DA f1)
(write-line "\n" f1) ; B=70.001
(write-line "" f1)
(princ "B=" f1)
(princ DB f1)
(close f1)
)
(progn ; действия при невыполнении признаков
(setq f1 (open "res.txt" "w")) ; запись в файл
(write-line "BRAK" f1) ; BRAK
(close f1)
)
)
)

Автор: Николай Свирневский

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *