Некоторые вопросы кодирования изображений при одном методе сжатия информации тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

м -1 3,3,

КИЕВСКИЙ ИНЕЕРС5ГГЕТ имени Т. ШЕВЧЕНКО

Иа правах рукописи УЖ 519.7

ДШПШЯ НУГЗАР ШАЛВОВИЧ

НЕКОТОРЫЕ ВОПРОСЫ КОДИРОВАНИЯ ИЗОБРАЖЕНИИ ПРИ ОДНОМ МЕТОДЕ СЕАТИЯ ИНФОРМАЦИИ

О'.. 01. 09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертация на соискание ученой степени каьдидата физико-математических наук

Киев - 1932

Работа выполнена на кафедре кибернетики иилисского государственного университета имени И. Дхавахишвили

Научный руководитель - кандидат технически., наук,

доцент Нанобаивили Нодар Давидович Официальные опоненты - доктор физико-математических наук, професор Редко Владимир Никифорович -кандидат технически:- наук, доцент Гнакиь Лев Алексеевич

Ведущая организация - институт кибернетики АН Грузии

Запита диссертации состоится "1992г. в "_ "

часов на заседании специализированного совета Д068.18.16 по присуждению ученной степени кандидата физико-математических наук, в Киевском университете имони Т. Шевченко, по ачресу: Кнзв 127, проспект академика Глушкова 6, факультет кибернетики, аудитория 40.

С диссертацией мохно ознакомиться ь библиотеке университета.

Автореферат рачосл а У-/_ 1992г.

Ученый секретарь специализированного совета, кандидат . физико-математических наук

Кузмин А.В.

■ V Обвая'характериотзяа работы

Актуальность темы. Интенсивное развитие компьютеризации, средств программирования, автоматизации и управления привали к необходимости разработки эффективных способов кодирования и представления информации.

Одним из актуальных вопросов в кодировании данных является проблема кодирования изобразений с дальнейшим их распознованием.

Согласно исследовалиян по указанному вопросу, а течение последних десятил гий рост количества обрабатываемых и передаваемых данных происходит экспоненциально со временем и будет, пилимо, продолжаться. Следовательно, расходы ка переработку информации являются Еесьма значительными и, что особо интересно, около 90°/. этих расходсз идет на переработку повторяющейся, т.е. бес полезной информации.

В настоящее чрсмя кззестно значительное число работ по всл-рг ан кодирования изобраЕэнкЯ. Одним из ос:-;ов1ых преи:.1уцеств какого-либо метода следует считать его укязерсалыгость пр:г кодировании и распознавании изображений, а такте компактность при его записи в память ЭВМ.

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

Цпль работы. Зфф живность ко лир- 1ания и сжатия изобпагенка должна быть рассмотрена в ксктексте эффективности распознавания генного изображения.

Диссертационная работа представляет собой поьлку посредством совместног решения указанпих задач еоггтол::::ть опрсдоложп'Л

пробел, существующий в области разработки и создания путей построения новых математических схем по вопросам кодирования изображений.

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

Специфичность разложения и расположения кодовых векторов на . иг'юрмационной сетке позволяет:

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

б) распознавать фрагменты изображения без применения дополнительных технических средств сканирования и вычисления при распознавании изображения.

Практическая ценность. Рассмотренный в работе метол сжатия для кодирования изображении, с ' дальнейшим ее распознаванием, является простым,с точки зрения мавшшой реализации и веема эффективна - с точки зрения времени обработки и передачи

■ информации, а Также объему памяти для хранения информации.

\

Развиваемый в дисертации метод кодиропания и расспознавания изоэражении может быть применен для повышения достоверности передачи информации в системах связи и надежности хранения ее в памяти ЭВМ.

Апробация работы. Разделы этой работы, по мере их завершения, ;./блнковались в периодической печати т выли доложен-г на

нескольких научнчх конференциях.

Публикации. По натерялам дисертации опуСлшсовано 6 печатных работ Ш-С6]. ' .

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами основных результатов работы, спи ка литературы из 75 наименований и прил жепия . Работа содержит 128 страниц машинописного текста.

Краткое содержание работь.

Во введении показано актульность темы диссертации, формируется цель работы, приводятся основные реэултаты выносимые на защиту. Коротко излагается содержания диссертации по главам.

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

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

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

Пусть задано п - мерное лилейное пространств. Ьп над поле_ 0Р(2). Сопостаым каждому вектору пространства Мп отдельную вер-

пину п-мерного гиперкуба Г.

Пусть G - отображение гиперкуба Г на плоскость я с точность» до изоморфизма. Расположи» векторы с одинаковыми весами, являющиеся элементами соответствующих множеств М, .М,,....М,.....Мп

на так называемых весовых линиях L0 ,L,.....L,,...,Ln гиперкуба G

со следующими условиями:

а) Любой вектор V, » [а,], п> с весом, равным i, W(Vt) = l, где V «И , 0,6(0,1) и С<Кп, кромэ векторов, расположенных на весовых линиях L0 и Ц^, с помощью п ребер связан с п числом векторов с весами, равиыми 1-1 и 1+1;

б) Вектор V с каждым из связанных велторов в сумме по модулю 2 (mod 2), образует вектор с весом, равным единице.

Назовем векюр - la, п> где Osksn и al€{0,l). вектором основания матрицы A^-IV,1, где

V1

Если относительно строк матрицы Ав удовлетворяет условия

а) и б) , тогда :звс лекторов V,, Уг....., из матрицы Ащ, равен

к-1, а вес остальных п-к количество векторов Ук+1.....V, равен

к+1, где к - вьс лектора В И((1к)»к. При этом элементы матрицы Ав характеризуются следующими особенностями:

1) Линейная комбинация лтбых двух строк-векторов V, и матрицы Аг по модулю 2 дает суммарный вектор с весом, равным двум:

в V,) - 2. и - 1,2.....п:

2) Линейная комбинация любой строки вектора Vl матрицы Ап с вектором основания Uk, поро*даюдим матрицу Ап, дает суммарный вектор с весом, равным единице:

W(Vt 1 Uk)>l, где 1-1,2.....n, к-0,1.....п.

Обозначим через S - р р ......ре , где р,6(0,1) суммарный

П П ~ 1 .21 1

вектор, явллющийся произвольной линейной комбинация строк векторов матрицы Ап. Назовем вектором восстановления вектор S'=p'p' ,...р'р', где pí€{0,1), каждая компонента р' которого

П П — 1 3 1 1 »

сопоставлена некоторой строке-вектору V.. Точнее, - если р' -

I В

- • 1. где ».п, и » » » 0, то катрица Ап с размерностью пхп преобразуется в «атрпцу А>п, с размерностью шхп. Тогда, согласно определению S' и свойствам а) и 3), произвольная | совокупность сзхтораэ 0k,S' будет отображать соответствующую матрицу А>п о .точностью до эквивалентности. Это означает, что матрацу rasn можно

заменить парой "чкторов Uk,S'. ;

Доказаны следующие теоремы:

Теорема 2.1.1. _слн n-керяый есх. op Us есть вектор основания, пороадаюзий соотЕетствусаую матрицу Ав, тогда:

1) Если вес вектора-основавяя кзчэтеыЗ. W(Uk)-2d-l, d« 1.2..... то для любого Уие. справедливо следуюаее

соотношение; ..«.'.

V- 2 V, j*m. (nod 2). (2.1)

j-i '

т.е.строки-векторы матрицы Ав образуют систему ляпвйно-зависимых векторов; .

2) Если вес вектора-основания является четным, т.е

W(Uk) - 2d, d«i,2..... то строки - векторы соответствуюзей мат

рицы А образуют базис заданного линейного вект .шого пространства М .

Теорема 2.1.2. Есл" вес вектора основания И(ик) является четным, то тогда:

1)четному значению К соответствует четное значение веса К(Б) вектора Б:

2)нечетному значению К соответствует нечетное значение веса У(Б) вектора Б.

Теорема 2.1.3. Если 1)к фиксированный вектор основания, с произвольным весомАяп- матрица размера тхп (т*п), соответствующая паре И^Б', то вектор восстановления 5' с суммарным вектором Б связан следующим соотношением:

где d-l",2.....а Н количество .строк-вектопов матрицы Авп-

Во второй параграфе главы II приводятся некоторые конструктивные допущения для определения возможностей эффективного кодирования изображений на заданной плоскости. Введено понятие информационной сетки и указаны особенносты расположен. .! матриц на информационной сетке ( теорема 2.2.1).

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

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

Нэоораж&.ше, получе: юе на информационно сетке, формально

(2.3)

можно описать с помощью некоторой многопаранетрическоП функции . к

Р-2 ft (а,Э.А.8.С....).

где ^ (а,р,л,д,£,...) Формальное описание той части изобрахения которая гсследуется в определенный момент времени, а.&.л.д.с,.. можно считать разными специфическими характеристиками изображения.

Функция Р удовлетворяет следующим условиям: -является конечной:

-является быективыш отображением заданного изобрахения в пространстве векгоров Йп. заданных над полем С?(2); '

-каждый элемент функции ^ер является сгатьм вектором размерности п, над которым натянута кодовая матрица размерности пхга. где И5П и в-ТТп.

Введет определения и обознаеппя, применилеыие в вопросах формализации взаимо расположении геометрических точек при кодирования и с*.- "ия изображении.

Доказаны теоремы в выведены сяедствя . позволяющие определить:

-расположение элементов информационной сетки на опой непрерывной прямой, разных траектории (теорема 3.1.1); -длину отрезков прямой (следствие );

-расположение отрезков прямых' на одноименных траекториях (теорема 3.1.2);

-пагалольность отрезков прямых (следствие); -пересекаемое.л отезков прямых (теорема 3.1.3); -перпендикулярность отрезков прямых (следствие). Рассмотрены вопросы распознавания при сжатия. Доказаны соответствующие теоремы (теорема 3.2.1 - 3.2.6).

Введно пон .тив яаблона, соввря^чной сиг'втрии и совераенной

?

симметрии I и II степены. Показано (теорема 3.2.7), что можно ■ ровести распознавания при сжатии с точностью до совершенной симметшш I или II степены.

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

1. Занимаемый объем пам). и в процессе распознавания:

2. Сложность алгоритма и скорость распознавания;

. 3. Точность распозна лкия. - •

Так как рассмотренный выше метод распознавания образов с применение:.: метода сжатия в определенной смысле удовлетворяет перечисленным критериям, то его вполне кожно считать рабочим.

В четвертой главе сведаны некоторые выводы относительно эффективности описанного метода. Рассмотрены вопросы эффективности скатяя и распозноьания, даны числовые оценки экономии объема памяти, сделано зг -лючение о целесообразности применения данного метода на практике.

Оскоп::аа роз'/льтатц диссертации опубликованы в следующих работах: ,

1. Дгикил Н.Ш. Кодирование изображении с применением 'специальной схемы сжатия информации. Труды XI конференции проподавател.л ВУЗ-ов Грузии. Кутаиси. 1986.

2. Деикия Н.Ш., Нанобашвили Н.Д. Кодирование изображения с использованием одного метода сжатия информации. Труды II республиканской конференции по проблемно ориентированным Г"э погов1Л1 системам (П0"~). т 2. Батум 1987.

?. Дгг.ккя Р.И., НаноОаивилн Н.Д. Способ обнаружения > .чества Суг'кциошфова. .¡я дискретных сис-ои при исполЬзопании

матричного метода сжатия информации. Сообиения АН Грузии, т. 130. N 2. 19Э8.

4. Джикия Н.И. Об одной применении матричного метола схаатия информации. Труды научной конференции факультета кибернетики и прикладной математики Т~У. Тбилиси. 198?.

5. Дхикия Н.Ш. Об одном подходе .. пргяэнеяию матричного метода сжатия информации (на грузинском языка). Труды ТГУ. т. 294.-1989.

6. Дхикия Н.Ш. Об одном способе кодирования изображении. Труды IV республиканской конференции по ПОДС. Батуми. 1990.

¡rnjoj fopjot)

ujdnbob3coönb jnpofjOfíl! firyo^œo l\>joot;-,o6®n¡.dj(jnnlj d.XlJddjnb 5*1110 djainpob ¿¿дпуэб^йпа (•fîjbjc1 оЬоед) тйорпЫ) 1992

Бесплатно ¡

Заказ & 'J я pay !€«:• '

oOj n.sojjoo l>úb:¿¿Srigjöjöoao do®30j(çojo0

зеоо<*э, ,000с :$оо ¿P№

Ротапринт института прикладной математики им. и. beкуа ТГУ 360043, Тбилисг., у-.Университетская 2.