Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Сабельников, П.Ю.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2013
Назва видання:	Искусственный интеллект
Теми:	Анализ и синтез коммуникационной информации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/85083
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов / П.Ю. Сабельников // Искусственный интеллект. — 2013. — № 3. — С. 223–232. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-85083
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-850832025-02-09T14:29:21Z Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов Обчислення та використання моментів бінарних зображень при геометричному порівнянні об’єктів Calculation and using moments of binary images in geometric comparison of objects Сабельников, П.Ю. Анализ и синтез коммуникационной информации В статье рассматриваются вопросы вычисления и использования моментов бинарных изображений на различных этапах реализации алгоритма по методу геометрического сравнения объектов с частично искажённой формой. Предлагаемые автором решения позволяют значительно сократить время выполнения алгоритма при его программной реализации. У статті розглядаються питання обчислення і використання моментів бінарних зображень на різних етапах реалізації алгоритму за методом геометричного порівняння об’єктів з частково спотвореною формою. Пропоновані автором рішення дозволяють значно скоротити час виконання алгоритму при його програмній реалізації. The article deals with calculation and using moments of binary images on different stages of algorithm realization on method of geometric comparison of objects with partially distorted shape. The author’s solutions allow significant reduce the runtime of algorithm in its software implementation. 2013 Article Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов / П.Ю. Сабельников // Искусственный интеллект. — 2013. — № 3. — С. 223–232. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85083 004.932 ru Искусственный интеллект application/pdf Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Анализ и синтез коммуникационной информации Анализ и синтез коммуникационной информации
spellingShingle	Анализ и синтез коммуникационной информации Анализ и синтез коммуникационной информации Сабельников, П.Ю. Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов Искусственный интеллект
description	В статье рассматриваются вопросы вычисления и использования моментов бинарных изображений на различных этапах реализации алгоритма по методу геометрического сравнения объектов с частично искажённой формой. Предлагаемые автором решения позволяют значительно сократить время выполнения алгоритма при его программной реализации.
format	Article
author	Сабельников, П.Ю.
author_facet	Сабельников, П.Ю.
author_sort	Сабельников, П.Ю.
title	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
title_short	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
title_full	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
title_fullStr	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
title_full_unstemmed	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
title_sort	вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2013
topic_facet	Анализ и синтез коммуникационной информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/85083
citation_txt	Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов / П.Ю. Сабельников // Искусственный интеллект. — 2013. — № 3. — С. 223–232. — Бібліогр.: 8 назв. — рос.
series	Искусственный интеллект
work_keys_str_mv	AT sabelʹnikovpû vyčislenieiispolʹzovaniemomentovbinarnyhizobraženijprigeometričeskomsravneniiobʺektov AT sabelʹnikovpû občislennâtavikoristannâmomentívbínarnihzobraženʹprigeometričnomuporívnânníobêktív AT sabelʹnikovpû calculationandusingmomentsofbinaryimagesingeometriccomparisonofobjects
first_indexed	2025-11-26T21:09:02Z
last_indexed	2025-11-26T21:09:02Z
_version_	1849888705946320896
fulltext	ISSN 1561-5359 «Штучний інтелект» 2013 № 3 223 3С УДК 004.932 П.Ю. Сабельников Институт кибернетики имени В.М. Глушкова НАН Украины, г. Киев Украина, 03680, МСП, г. Киев-187, просп. Академика Глушкова, 40. Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов P.Y. Sabelnikov V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine, c. Kiev Ukraine, 03680, c. Kiev-187, Academik Glushkov st., 40 Calculation and Using Moments of Binary Images in Geometric Comparison of Objects П.Ю. Сабельніков Інститут кібернетики імені В.М. Глушкова НАН України, м. Київ Україна, 03680, МСП, м. Київ-187, просп. Академіка Глушкова, 40 Обчислення та використання моментів бінарних зображень при геометричному порівнянні об’єктів В статье рассматриваются вопросы вычисления и использования моментов бинарных изображений на различных этапах реализации алгоритма по методу геометрического сравнения объектов с частично искажённой формой. Предлагаемые автором решения позволяют значительно сократить время выполнения алгоритма при его программной реализации. Ключевые слова: сравнение изображений, контур, эталон, моменты. The article deals with calculation and using moments of binary images on different stages of algorithm realization on method of geometric comparison of objects with partially distorted shape. The author’s solutions allow significant reduce the runtime of algorithm in its software implementation. Key words: comparison of images, contour, standard, moments. У статті розглядаються питання обчислення і використання моментів бінарних зображень на різних етапах реалізації алгоритму за методом геометричного порівняння об’єктів з частково спотвореною формою. Пропоновані автором рішення дозволяють значно скоротити час виконання алгоритму при його програмній реалізації. Ключові слова: порівняння зображень, контур, еталон, моменти. Введение Известно, что форму объектов определяют их контуры, и многие объекты могут быть опознаны по контурам, без использования полутоновых изображений. В настоя- щее время известно достаточно много методов и алгоритмов распознавания объектов по их контурам [1-3]. В реальных условиях контуры исследуемых объектов могут иметь некоторые гео- метрические отличия по отношению к эталонам. При этом, в системах технического зре- ния возникает задача выявления этих отличий, их количественной и качественной оцен- ки, например, для контроля формы, размеров и количества продукции. Подобная задача решается методом геометрического сравнения, с поиском наи- лучшего совпадения контуров анализируемого объекта и эталона. Определение смещения и ориентации контура объекта, а также учёт его масштаба для совмещения с контуром Сабельников П.Ю. «Искусственный интеллект» 2013 № 3 224 3С эталона по характерным точкам (например, центр тяжести) и характеристикам, инва- риантным к сдвигу, повороту и масштабу, не дают желаемого результата, так как при гео- метрическом искажении меняется положение этих точек и значения характеристик. В работе [4] был предложен метод и алгоритм сравнения частично искажённых контуров объектов, основанный на предположении о существовании хотя бы одного неискажённого сегмента контура анализируемого объекта, тождественного соответству- ющему сегменту контура эталона. Данные сегменты контуров объекта и эталона берутся за основу для определения их взаимного расположения и ориентации. Приблизительное значение масштаба рассчитывается как отношение длин контуров или как корень из отношения площадей объекта и эталона. Уточнение масштаба производится методом подбора, путём прибавления и вычитания приращений к приблизительному масштабу. Точность подбора определяется величиной возможного геометрического искажения и ко- личеством заданных приращений. Автором предложен метод и алгоритм геометрического сравнения с новыми кри- териями поиска тождественных сегментов контуров объектов, с определением точного масштаба и ориентации по характеристикам неискажённых сегментов и более точной численной оценкой результатов сравнения [5]. Суть метода заключается в следующем. Имея обработанное и преобразованное в бинарный вид изображение, производит- ся процедура выделения контуров анализируемых объектов и сравнения их с эталонами, включающая следующие этапы: 1) Выделение и преобразование в векторную форму контуров анализируемых би- нарных объектов с вычислением их первичных параметров, таких как длины контуров, моменты, координаты центров тяжести. На данном этапе один или несколько выделенных контуров с первичными па- раметрами могут быть сохранены как эталоны в базу данных эталонов. При сохранении контур, вручную или автоматически, разбивается на несколько сегментов. Координаты граничных точек сегментов также сохраняются. 2) По характеристикам, вычисленным на основе первичных параметров, посред- ством сравнения с аналогичными характеристиками эталонов, производится отбор пар кандидатов (объект – эталон) для последующего геометрического сравнения. Следует иметь в виду, что для одного анализируемого объекта по характеристикам могут подой- ти несколько эталонов. Для каждой выбранной пары вычисляются приблизительное ма- сштабное соотношение и приблизительная взаимная ориентация. 3) Производится перебор всех отобранных пар. Для каждого из сегментов контура эталона выбранной пары, учитывая приблизительный масштаб и ориентацию, ищутся по заданным критериям тождественные ему сегменты на контуре анализируемого объекта. То есть, производится поиск начальной и конечной точек сегмента. В качестве критериев тождественности сегментов используется приблизительное равенство с за- данной погрешностью длин сегментов контуров объекта и эталона, а также отношений расстояния между крайними точками и длиною каждого из этих сегментов. При срав- нении длин учитывается приблизительный масштаб, а отношения являются величиной инвариантной к сдвигу, повороту и масштабу. По характеристикам тождественных сегментов контуров вычисляются вероятный масштаб, смещение и взаимная ориентация объектов. После чего производится наложе- ние контура эталона на шаблон контура объекта с вычислением оценки их соответствия. 4) За результат для принятия решения или выполнения последующей обработки берётся наложение с наилучшей оценкой. Предполагается, что оно было получено вследствие нахождения неискажённого сегмента контура объекта тождественного соот- Вычисление и использование моментов бинарных изображений… «Штучний інтелект» 2013 № 3 225 3С ветствующему сегменту контура эталона. Соответственно считаются точными и ис- пользуются для дальнейшего анализа параметры, полученные при данном наложении: масштаб, смещение и взаимная ориентация. Уменьшить количество производимых наложений и соответственно время не- обходимое для получения конечного результата можно, приблизительно определив взаимную ориентацию и масштабное соотношение объекта и эталона, тем самым сузив зону поиска тождественных сегментов их контуров, а также проводя промежуточные проверки, которые опровергнут или подтвердят целесообразность проведения процеду- ры наложения для текущего выбранного сегмента. Это возможно за счёт использования моментов бинарных изображений объектов, количество пикселей в которых практи- чески не зависит от ориентации в отличие от контуров. Дальнейшие рассуждения будем вести в рамках следующей модели. После предварительной обработки имеем бинарное изображение, где на белом фоне пред- ставлены чёрные объекты (или наоборот, это не принципиально), имеющие замкнутые контуры и обозначенные как объекты первого уровня. При этом в пределах объектов первого уровня могут быть расположены белые объекты второго уровня, в пределах объектов второго уровня могут быть расположены чёрные объекты третьего уровня и так далее. То есть, за изображение объекта принимаем совокупность пикселей с Одина- ковой яркостью, замкнутых контуром. Определим контур как замкнутую линию толщиной в один пиксель, соединяющую центры граничных пикселей объекта, примыкающих друг к другу по прямой или диаго- нали и принадлежащих этому объекту. Чтобы не возникало коллизий, связанных с пере- сечением контуров, установим, что точка между пикселями при переходах по диагонали принадлежит черным объектам и является препятствием для белых объектов. Такая модель позволяет в зависимости от природы полученного изображения анализировать объекты в отдельности, как независимые, или совместно, как связанные, то есть не меняющие своего положения и ориентации относительно друг друга в преде- лах объекта более высокого уровня. Моменты таких изображений достаточно стабильны, в значительной степени ха- рактеризуют геометрию объекта, легко вычисляются и позволяют образовывать Моме- нтные инварианты. При проведении промежуточных проверок их перерасчёт, для сравнения с аналогичными характеристиками эталона, требует значительно меньше времени, чем процедура наложения. Целью данной работы является рассмотрение практических вопросов: – вычисления моментов бинарных изображений объектов на первом этапе; – использования их при отборе кандидатов для сравнения и вычисления прибли- зительного значения масштаба и взаимной ориентации на втором этапе; – поиска граничных точек сегментов контура анализируемого объекта, тождествен- ных очередному сегменту контура эталона, на третьем этапе. Вычисление моментов бинарных изображений объектов Ниже, для дискретного случая, представлена общая формула вычисления мо- ментов [6] к-о порядка: ∑ = − − ⋅⋅= N i jk i j iijkj yxBM 1 , , j = (0, k), где Mj,k-j – моменты; Bi – значения яркостей пикселей объекта; xi, yi – коорди- наты пикселей; N – количество пикселей бинарного объекта. Сабельников П.Ю. «Искусственный интеллект» 2013 № 3 226 3С В соответствии с принятой моделью, изображения объектов имеют Одинаковую яркость всех пикселей, которую можно вынести за знак суммы и условно приравнять к единице. На изображении в пределах одной строки может находиться несколько сегментов объекта. То есть объект можно представлять как совокупность его сегментов в раз- личных строках, а момент некоторого порядка этого объекта – как сумму моментов такого же порядка всех его сегментов. Следовательно, зная начало и конец сегмента в конкретной строке можно определить его момент MSj,k-j как: ∑ = − − ⋅= n i j i jk jkj xyMS 1 , , где y – номер строки, а n – количество пикселей в сегменте. Рассмотрим два способа выделения и векторизации контуров. Первый способ [1] заключается в последовательном обходе границ каждого объекта с анализом по часовой стрелке (или против) обстановки в окрестности текущего граничного пикселя для опре- деления направления перехода к следующему граничному пикселю. Для восьмисвязной модели, представленной на рис. 1, зная направления переходов (откуда пришли и куда ушли), несложно определить, является ли текущий пиксель началом или концом сегмента объекта в строке. Поэтому моменты произвольного порядка можно вычислять непосредственно при обходе контура. 0 7 6 1 х 5 2 3 4 Рисунок 1 – Восьмисвязная модель переходов по контуру Если текущий граничный пиксель с координатами (xi , yi ) является началом сегмента в строке, то: ∑ − = − −− ⋅−= 1 1 ,, i x a jjk ijkjjkj ayMM , а если концом, тогда: ∑ = − −− ⋅+= i x a jjk ijkjjkj ayMM 1 ,, , где ∑ = i x a j a 1 – сумма членов арифметической прогрессии в степени j. Замкнутость контура является гарантией того, что при обходе контура будут пройдены начало и конец всех сегментов объекта. Аналогичным образом можно сделать выводы и для столбцов. При вычислении мо- ментов можно комбинировать, рассчитывая некоторые из них по строкам, а некоторые по столбцам. В табл. 1 приведены возможные варианты переходов через граничный пиксель (x) объекта при обходе контура против часовой стрелки и соответствующие обозначения этого пикселя: гн – начало сегмента объекта по горизонтали (в строке), гк – конец сегмента объекта по горизонтали (в строке), вн – начало сегмента объекта по вертикали (в столбце), вк – конец сегмента объекта по вертикали (в столбце). Вычисление и использование моментов бинарных изображений… «Штучний інтелект» 2013 № 3 227 3С Таблица 1 – Возможные варианты переходов через граничный пиксель (х) объекта и соответствующие значения этого пикселя Пере- ход Начало/конец сегмента по горизонтали, по вертикали Переход Начало/конец сегмента по горизонтали, по вертикали Переход Начало/конец сегмента по горизонтали, по вертикали Переход Начало/конец сегмента по горизонтали, по вертикали 0-x-2 гн 2-x-4 вк 4-x-6 гк 6-x-0 вн 0-x-3 гн 2-x-5 вк 4-x-7 гк 6-x-1 вн 0-x-4 гн, вк 2-x-6 гк, вк 4-x-0 гк, вн 6-x-2 гн, вн 0-x-5 гн, вк 2-x-7 гк, вк 4-x-1 гк, вн 6-x-3 гн, вн 0-x-6 гн, гк, вк 2-x-0 гк, вн, вк 4-x-2 гн, гк, вн 6-x-4 гн, вн, вк 0-x-7 гн, гк, вк 2-x-1 гк, вн, вк 4-x-3 гн, гк, вн 6-x-5 гн, вн, вк 0-x-0 гн, гк, вн, вк 2-x-2 гн, гк, вн, вк 4-x-4 гн, гк, вн, вк 6-x-6 гн, гк, вн, вк 1-x-4 вк 3-x-6 гк 5-x-0 вн 7-x-2 гн 1-x-5 вк 3-x-7 гк 5-x-1 вн 7-x-3 гн 1-x-6 гк, вк 3-x-0 гк, вн 5-x-2 гн, вн 7-x-4 гн, вк 1-x-7 гк, вк 3-x-1 гк, вн 5-x-3 гн, вн 7-x-5 гн, вк 1-x-0 гк, вн, вк 3-x-2 гн, гк, вн 5-x-4 гн, вн, вк 7-x-6 гн, гк, вк 1-x-1 гк, вн, вк 3-x-3 гн, гк, вн 5-x-5 гн, вн, вк 7-x-7 гн, гк, вк Второй способ выделения и векторизации контуров, в рамках рассматриваемой модели, основан на параллельном отслеживании контуров всех объектов в процессе построчного ввода изображения. Данный способ предложен и применялся автором при реализации алгоритмов обработки изображений в интеллектуальной видеокамере (ИВК), построенной на базе сигнального процессора. Он состоит в отслеживании зарождения ветвей всех контуров, их перехода из строки в строку и соединения в целостные зам- кнутые контуры параллельно с вводом строк изображения и преобразованием их в би- нарный вид. Согласно алгоритму, для анализа одновременно требуется не весь кадр изображения, а только считанная и предыдущая строки. За счёт этого повышается эф- фективность обработки, поскольку для хранения нескольких строк достаточно объёма внутренней памяти сигнального процессора, которая значительно быстрее внешней памяти, необходимой для хранения всего изображения. Данный способ предусматривает накопление по отдельности моментов всех сег- ментов (чёрных и белых), заключённых между одноимёнными ветвями контуров. Когда ветви соединяются в замкнутый контур, принимается решение о том, какие объекты на текущий момент присутствуют на изображении и какому уровню они принадлежат. В со- ответствии с этим производится расчёт моментов. На рис. 2 представлены примеры ситуаций, возникающих при параллельном выде- лении контуров после ввода и анализа нескольких строк изображения: Рисунок 2 – Примеры ситуаций, возникающих при параллельном выделении контуров Сабельников П.Ю. «Искусственный интеллект» 2013 № 3 228 3С а) образовались и переходят из строки в строку ветви контуров с номерами 1 и 2, предположительно объектов № 1 и № 2; б) замкнулись левые ветви контуров 1 и 2, следовательно, на изображении присут- ствует только один объект, замкнутый контуром 1. В этом случае из моментов объекта № 1 вычитаются моменты объекта № 2, ветвям с номером 2 присваивается номер 1, далее продолжается накопление моментов объекта № 1; в) замкнулись левая и правая ветви контура с номером 2, следовательно, можно счи- тать, что образовался белый объект № 2 с окончательно вычисленными для него моментами. Дополнительно для последующего анализа вычисляются координаты центров тя- жести бинарных объектов (xц, yц): 00 10 M M xц = , 00 01 M M y ц = . Использование моментов при выборе объектов для сравнения Выбор кандидатов (объект – эталон) для последующего сравнения осуществ- ляется с использованием соответствующих моментных функций, инвариантных к смещению, масштабу и повороту, образованных из центрированных и нормирован- ных по величине первичных моментов [3], [6-8]. Моменты смещённых объектов jkj −, µ в общем случае вычисляются следующим образом: ∑ = − − ∆−⋅∆−⋅= N i jk i j iijkj yyxxB 1 , )()(µ , где ∆ x и ∆ y – величина смещения по соответствующим координатам. После преобразований получаем следующие центрированные моменты (∆ x = xц ,∆ y = yц) нулевого, первого и второго порядков: 0000 M=µ , 0 000101 =⋅∆−= MyMµ , 0 001010 =⋅∆−= MxMµ , ц yMMyMyM −=⋅∆+⋅∆⋅−= 0200 2 010202 2µ , ц xMMxMxM −=⋅∆+⋅∆⋅−= 2000 2 102020 2µ , 00 0110 110001101111 M MM MMyxMxMyM ⋅ −=⋅∆⋅∆+⋅∆−⋅∆−=µ . Нормированные моменты jkj −, η соответственно равны: 12/ 00 , , + − − = k jkj jkj µ µ η . Для оценки приблизительного тождества исследуемых объектов и эталонов достаточно использовать нормированные длины контуров l и моментные инвариан- ты 1 f , 2 f , образованные на основе нормированных моментов второго порядка: 02201 ηη +=f , 2 11 2 02202 4)( ηηη +−=f , 00 µ L l = , где L – длина контура, l – нормированная длина контура. Вычисление и использование моментов бинарных изображений… «Штучний інтелект» 2013 № 3 229 3С В некоторых случаях, когда есть возможность определять координаты некоторых других характерных точек, которые при любом положении объекта не меняют своего расположения относительно этого объекта, можно также использовать моментный ин- вариант 0 f , образованный из моментов первого порядка: 2 01 2 100 ηη +=f . Подразумевается, что центр координат для объекта и эталона будет перемещён в эти точки, а не в центры тяжести. Следовательно, нормированные моменты первого по- рядка в данном случае не будут равны нулю. Пара объект – эталон считается выбранной для последующего геометрического сравнения, если относительные погрешности, при сравнении соответствующих мо- ментных инвариантов и нормированных длин контуров, не выйдут за пределы задан- ных, которые зависят от величины возможного геометрического искажения. Рассмотрение вопросов выбора предельных погрешностей не является предметом данной статьи. Вычисление приблизительного значения масштабного соотношения и взаимной ориентации объекта и эталона На этапе геометрического сравнения для каждого из сегментов контура эталона ищутся по заданным критериям тождественные ему сегменты на контуре анализируемого объекта. То есть, производится поиск граничных точек очередного сегмента контура объекта. Чтобы сузить зону их поиска, определяют приблизительное масштабное соотно- шение и взаимную ориентацию объекта и эталона. Это позволит искать граничные точки сегмента не по всему контуру объекта, а только на определённых его участках. Приблизительный линейный масштаб MT объекта по отношению к эталону опре- деляется соотношением: ∗ = 00 00 M M MT , где 00 M – момент объекта, ∗ 00 M – момент эталона. Для определения взаимной ориентации объекта и эталона используются норми- рованные моменты второго порядка. Будем обозначать моменты эталона звёздочкой. Тогда, предположив, что моменты повёрнутого на необходимый угол γ объекта равны моментам эталона, получаем систему из трёх уравнений: ( ) ( )     ⋅⋅−−−⋅= ⋅+⋅⋅−⋅= ⋅+⋅⋅+⋅= ∗ ∗ ∗ γγηηγγηη γηγγηγηη γηγγηγηη sincossincos sinsincos2cos sinsincos2cos 0220 22 1111 2 2011 2 0202 2 0211 2 2020 . Из третьего уравнения получаем выражение: ( ) 0220 1111 22 sincos sincos ηη ηηγγ γγ − −⋅− =⋅ ∗ . Подставив значение γγ sincos ⋅ в разницу первого и второго уравнений, получим: 2 11 2 0220 11110220022022 )(4)( 4)()( sincos ηηη ηηηηηη γγ ⋅+− ⋅+−⋅− =− ∗∗∗ . Обозначив выражение в правой части как c, получаем: 2 1 cos c+ ±=γ , 2 1 sin c− ±=γ , 0220 1111 sincos ηη ηη γγ − −⋅ =⋅ ∗ c . Сабельников П.Ю. «Искусственный интеллект» 2013 № 3 230 3С По последнему выражению определяются одинаковые или разные знаки γcos и γsin . В обоих случаях ориентация объекта по отношению к эталону может отличаться на угол γ или πγ + . Поиск граничных точек сегментов контура объекта, тождественных соответствующим сегментам контура эталона Полученные данные о взаимной ориентации позволяют определить участки контура объекта, на которых следует проводить поиск начальных и конечных точек сегментов контура объекта, тождественных соответствующим сегментам контура эталона. Так как объект и эталон могут отличаться, необходима проверка: абсолютная величина 22 sincos γγ − должна быть меньше 1. В противном случае поиск начальных точек сегментов контура объекта, соответ- ствующих начальным точкам сегментов контура эталона, необходимо проводить после- довательно по всему контуру объекта, сравнивая в пределах выбранной погрешности моментные инварианты объекта и эталона 0 f , 1 f , 2 f , пересчитанные с условием, что центр координат перемещается в эти точки. Пересчёт упрощается, так как при последо- вательном переходе от точки к точке 1,0 ±=∆x и 1,0 ±=∆y , следовательно, операции умножения на указанные величины заменяются операциями сложения и вычитания. Поиск конечных точек осуществляется по критериям тождественности сегментов. На рис. 3 представлены результаты наложения, полученные при моделировании алгоритма в соответствии с рассматриваемым методом: слева контура объекта № 1, взя- того в качестве эталона, на его шаблон, а справа этого же контура, масштабированного, повёрнутого и смещённого, на шаблон контура объекта № 2. Допуск в шаблонах (белая зона вокруг контуров) может задаваться. В данном конкретном случае контур № 1 состо- ит из 322, а контур № 2 из 558 пикселей. Контур № 1 как эталон был разбит на 4 сегмента, приблизительно равных по количеству пикселей. Номерами на рисунке обозначены по- рядковые номера интересующих нас пикселей, начиная с пикселя № 0. Отсчёт следует вести против часовой стрелки. Наилучшее по оценкам наложение контура № 1 на шаблон контура № 2 было получено по параметрам смещения, поворота и масштаба, вычислен- ными на основе третьего сегмента контура № 1 (начало – пиксель № 160, конец – пик- сель № 240) и тождественного ему по заданным критериям сегмента контура № 2 (нача- ло – пиксель № 294, конец – пиксель № 421). Рисунок 3 – Наложение контура № 1 на его шаблон и на шаблон контура № 2 При последовательном поиске первого пикселя сегмента контура № 2 пересчитыва- лись моментные инварианты 0 f , 1 f , 2 f бинарного изображения объекта № 2. За центр координат принимался каждый из пикселей этого контура. Затем они сравнивались с ана- логичными параметрами эталона (объект № 1), пересчитанными для пикселя № 160 его контура, также принятого за центр координат. Вычисление и использование моментов бинарных изображений… «Штучний інтелект» 2013 № 3 231 3С На рис. 4 представлен график, на котором показаны обозначенные инварианты по правому краю, соответственно сверху вниз, в порядке следования: – f2_obj, f1_obj, f0_obj – моментные инварианты бинарного изображения объек- та №2, с центром координат в каждом из пикселей его контура; – f1_et, f0_et, f2_et – моментные инварианты бинарного изображения эталона (объект №1), с центром координат в пикселе № 160, который соответствует началу третьего сегмента его контура. Горизонтальная ось – это порядковые номера пикселей контура объекта № 2, а вер- тикальная ось – это значения моментных инвариантов. При последовательном анализе контура № 2, в качестве начального пикселя сегме- нта, предположительно тождественного третьему сегменту контура эталона, берётся тот пиксель, для которого выполняются условия: etfobjf __ 00 ≈ , etfobjf __ 11 ≈ , etfobjf __ 22 ≈ . Из графика видно, что данные условия с заданной погрешностью выполняются в районе пикселей с номерами 67, 294, 466. Далее проводится поиск конечного пикселя сегмента по критерию, предусмотрен- ному методом. Возможна дополнительная проверка условий равенства моментных инва- риантов для конечных пикселей сегмента аналогично, так же как при поиске начальных пикселей. Рисунок 4 – График моментных инвариантов бинарных изображений объекта № 2 и эталона (объект № 1) Только в случае, когда все условия удовлетворены, производится наложение контура эталона на шаблон контура №2 с оценкой их совпадения. Выводы Вычисление и использование моментов бинарных изображений на различных этапах реализации алгоритма по представленному методу геометрического сравне- ния объектов позволяет, как показывают эксперименты моделирования, в среднем на порядок сократить время, необходимое для его выполнения. Эффект достигается за счёт значительного сокращения количества нерезультативных наложений контуров на шаб- лоны, так как в конечном итоге необходимо отыскать одно наложение, дающее лучшую оценку совпадения. Процедура наложения требует расчётов по каждой точке контура анализируемого объекта, количество которых может быть значительным. В то время как вычисление и перерасчёт нескольких моментов и инвариантов, а также процедуры про- межуточных проверок достаточно просты и не трудоёмки в вычислительном плане. Эксперименты по моделированию алгоритма показывают, что эффект в значи- тельной степени зависит от формы объектов. Предложенные решения не дают ощу- тимого эффекта при сравнении объектов симметричной округлой формы. Сабельников П.Ю. «Искусственный интеллект» 2013 № 3 232 3С Литература 1. Прэтт У. Цифровая обработка изображений / Прэтт У. – М. : Мир, 1982. – Кн. 2. – 480 с. 2. Ту Дж. Принципы распознавания образов /Дж. Ту, Р. Гонсалес. – М. : Мир, 1978. – 412 с. 3. Гонсалес Р. Цифровая обработка информации / Р. Гонсалес, Р. Вудс – М. : Техносфера, 2005. – 1072 с. 4. Боюн В.П. Порівняння двомірних зображень об’єктів за формою їх контурів / В.П. Боюн, Ю.А. Сабельніков // Комп’ютерні засоби, мережі та системи. – Київ : Ін-т кібернетики ім. В.М. Глушкова НАН України. – 2007. – № 6. – С. 155-161. 5. Сабельников П.Ю. Сравнение контуров объектов с частично искажённой формой / П.Ю. Сабельников // Journal of Qafqaz University. Mathematics and Computer Science. (Baku). – 2012. – № 34 – С. 47-58. 6. Глумов Н.И. Построение и применение моментных инвариантов для обработки изображений в скользящем окне / Н.И. Глумов // Компьютерная оптика – 1995. – № 14. – С. 46-54. 7. Яне Б. Цифровая обработка информации / Яне Б. – М. : Техносфера, 2007. – 584 с. 8. Методы компьютерной обработки изображений / [под ред. В.А. Сойфера]. – 2-е изд., испр. – М. : Физматлит, 2003. – 784 с. Literaturа 1. Pratt W. Digital image processing: Translation from English / W. Pratt. – M.: Mir, 1982. – B. 2. – 480 p. 2. Tou J., Gonsales R. Pattern Recognition Principles / J. Tou, R. Gonsales. – M.: Mir, 1978. – 412 p. 3. Gonsales R, Woods R. Digital processing of information / R. Gonsales, R. Woods. – M.: Technosphere, 2005. – 1072 p. 4. Boyun V.P., Sabelnikov Y.A. Comparison of two-dimensional images of objects in the form of contours / V.P. Boyun, Y.A. Sabelnikov // Computer equipment, networks and systems. – Kiev: The V.M. Glushkov Institute of Cybernetics of The National Academy of Sciences of Ukraine. – 2007. – № 6. –P. 155-161. 5. Sabelnikov P.Y. A comparison of objects contour with partially misresented shape / P.Y. Sabelnikov // Journal of Qafqaz University. Mathematics and Computer Science. (Baku). – 2012. – № 34 – P. 47-58. 6. Glumov N.I. Construction and using of moment invariants for image processing in sliding window / N.I. Glumov // Computer optics. – 1995. – № 14. –P. 46-54. 7. Yane B. Digital processing of information / B. Yane. – M.: Technosphere, 2007. – 584 p. 8. Computer image processing methods // edited by Soifer V.A. – 2nd edition, corrected. – M. : Phismatlit, 2003. – 784 p. RESUME P.Y. Sabelnikov Calculation and Using Moments of Binary Images in Geometric Comparison of Objects The article deals with calculation and using moments of binary images at different stages of the algorithm implementation using the method of geometric comparison of objects with partially distorted shape. The method is based on assumption of existence of undistorted contour segment of analyzed object. This contour should be identical to one of segments of standard contour. Using these segments it is possible to define the exact scale, mutual orientation and offset for combining of object and standard. This allows to detect and evaluate their differences in control systems of shape and sizes of products. Using the moments of the object and the standard allows you to: – implement preliminary selection of candidates (object – standard) for geometric com- parison; – calculate the approximate size and relative orientation of the object and standard, – to conduct an effective search of identical segments of the contours of the object and a standard. The proposed solutions significantly reduce the number of ineffective evaluation alignments contours of objects and standards and the total execution time of the algorithm. Статья поступила в редакцию 23.04.2013.

Вычисление и использование моментов бинарных изображений при геометрическом сравнении объектов

Репозитарії

Схожі ресурси