Об определении точек разрыва непрерывности на искаженных помехами графиках функций
Исходя из предположения, что феномен переменной разрешающей способности используется в зрительном восприятии человека для сегментации изображений, в частности, графиков, предложен новый метод определения разрывов непрерывности на графике. График обрабатывается при нескольких разрешающих способностях...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2018 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/144948 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об определении точек разрыва непрерывности на искаженных помехами графиках функций / А.В. Шарыпанов // Математичні машини і системи. — 2018. — № 2. — С. 157-168. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144948 |
|---|---|
| record_format |
dspace |
| spelling |
Шарыпанов, А.В. 2019-01-10T17:32:53Z 2019-01-10T17:32:53Z 2018 Об определении точек разрыва непрерывности на искаженных помехами графиках функций / А.В. Шарыпанов // Математичні машини і системи. — 2018. — № 2. — С. 157-168. — Бібліогр.: 13 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/144948 004.02 Исходя из предположения, что феномен переменной разрешающей способности используется в зрительном восприятии человека для сегментации изображений, в частности, графиков, предложен новый метод определения разрывов непрерывности на графике. График обрабатывается при нескольких разрешающих способностях. Определяют интервалы, содержащие разрывы непрерывности первого рода. Окончательное решение о сегментации принимается на основании совместного рассмотрения всех частных ответов при всех разрешениях. Представлены результаты проверки работоспособности нового алгоритма на примере сегментации кардиосигнала. Виходячи з припущення, що феномен змінної роздільної здатності використовується у зоровому сприйнятті людини для сегментації зображень, зокрема, графіків, запропоновано новий метод визначення розривів неперервності на графіку. Графік обробляється при декількох роздільних здатностях. Визначають інтервали, що містять розриви неперервності першого роду. Остаточне рішення стосовно сегментації приймається на підставі сумісного розгляду всіх окремих відповідей при всіх роздільних здатностях. Представлені результати перевірки працездатності нового алгоритму на прикладі сегментації кардіосигналу. Based on the assumption that the phenomenon of variable resolution is used in human visual perception for image segmentation, in particular graphs, a new method for finding discontinuities in the graph is proposed. The graph is processed under several resolutions. Intervals containing jump discontinuities are located. The final decision on segmentation is made on the basis of joint consideration of all partial answers at all resolutions. The results of testing the efficiency of the new algorithm on the example of cardiac signal segmentation are presented. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління Об определении точек разрыва непрерывности на искаженных помехами графиках функций Щодо визначення точок розриву безперервності на спотворених перешкодами графіках функцій On the determination of discontinuity points on distorted graphs of functions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| spellingShingle |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций Шарыпанов, А.В. Моделювання і управління |
| title_short |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| title_full |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| title_fullStr |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| title_full_unstemmed |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| title_sort |
об определении точек разрыва непрерывности на искаженных помехами графиках функций |
| author |
Шарыпанов, А.В. |
| author_facet |
Шарыпанов, А.В. |
| topic |
Моделювання і управління |
| topic_facet |
Моделювання і управління |
| publishDate |
2018 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Щодо визначення точок розриву безперервності на спотворених перешкодами графіках функцій On the determination of discontinuity points on distorted graphs of functions |
| description |
Исходя из предположения, что феномен переменной разрешающей способности используется в зрительном восприятии человека для сегментации изображений, в частности, графиков, предложен новый метод определения разрывов непрерывности на графике. График обрабатывается при нескольких разрешающих способностях. Определяют интервалы, содержащие разрывы непрерывности первого рода. Окончательное решение о сегментации принимается на основании совместного рассмотрения всех частных ответов при всех разрешениях. Представлены результаты проверки работоспособности нового алгоритма на примере сегментации кардиосигнала.
Виходячи з припущення, що феномен змінної роздільної здатності використовується у зоровому сприйнятті людини для сегментації зображень, зокрема, графіків, запропоновано новий метод визначення розривів неперервності на графіку. Графік обробляється при декількох роздільних здатностях. Визначають інтервали, що містять розриви неперервності першого роду. Остаточне рішення стосовно сегментації приймається на підставі сумісного розгляду всіх окремих відповідей при всіх роздільних здатностях. Представлені результати перевірки працездатності нового алгоритму на прикладі сегментації кардіосигналу.
Based on the assumption that the phenomenon of variable resolution is used in human visual perception for image segmentation, in particular graphs, a new method for finding discontinuities in the graph is proposed. The graph is processed under several resolutions. Intervals containing jump discontinuities are located. The final decision on segmentation is made on the basis of joint consideration of all partial answers at all resolutions. The results of testing the efficiency of the new algorithm on the example of cardiac signal segmentation are presented.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144948 |
| citation_txt |
Об определении точек разрыва непрерывности на искаженных помехами графиках функций / А.В. Шарыпанов // Математичні машини і системи. — 2018. — № 2. — С. 157-168. — Бібліогр.: 13 назв. — рос. |
| work_keys_str_mv |
AT šarypanovav obopredeleniitočekrazryvanepreryvnostinaiskažennyhpomehamigrafikahfunkcii AT šarypanovav ŝodoviznačennâtočokrozrivubezperervnostínaspotvorenihpereškodamigrafíkahfunkcíi AT šarypanovav onthedeterminationofdiscontinuitypointsondistortedgraphsoffunctions |
| first_indexed |
2025-11-24T06:29:51Z |
| last_indexed |
2025-11-24T06:29:51Z |
| _version_ |
1850843043779837952 |
| fulltext |
© Шарыпанов А.В., 2018 157
ISSN 1028-9763. Математичні машини і системи, 2018, № 2
УДК 004.02
А.В. ШАРЫПАНОВ
*
ОБ ОПРЕДЕЛЕНИИ ТОЧЕК РАЗРЫВА НЕПРЕРЫВНОСТИ НА ИСКАЖЕННЫХ
ПОМЕХАМИ ГРАФИКАХ ФУНКЦИЙ
*
Институт проблем математических машин и систем НАН Украины, г. Киев, Украина
Анотація. Виходячи з припущення, що феномен змінної роздільної здатності використовується у
зоровому сприйнятті людини для сегментації зображень, зокрема, графіків, запропоновано новий
метод визначення розривів неперервності на графіку. Графік обробляється при декількох розділь-
них здатностях. Визначають інтервали, що містять розриви неперервності першого роду. Оста-
точне рішення стосовно сегментації приймається на підставі сумісного розгляду всіх окремих
відповідей при всіх роздільних здатностях. Представлені результати перевірки працездатності
нового алгоритму на прикладі сегментації кардіосигналу.
Ключові слова: розрив неперервності, змінна роздільна здатність, кутові коефіцієнти відрізків
прямих.
Аннотация. Исходя из предположения, что феномен переменной разрешающей способности ис-
пользуется в зрительном восприятии человека для сегментации изображений, в частности, гра-
фиков, предложен новый метод определения разрывов непрерывности на графике. График обра-
батывается при нескольких разрешающих способностях. Определяют интервалы, содержащие
разрывы непрерывности первого рода. Окончательное решение о сегментации принимается на
основании совместного рассмотрения всех частных ответов при всех разрешениях. Представле-
ны результаты проверки работоспособности нового алгоритма на примере сегментации кардио-
сигнала.
Ключевые слова: разрыв непрерывности, переменная разрешающая способность, угловые коэф-
фициенты отрезков прямых.
Abstract. Based on the assumption that the phenomenon of variable resolution is used in human visual
perception for image segmentation, in particular graphs, a new method for finding discontinuities in the
graph is proposed. The graph is processed under several resolutions. Intervals containing jump disconti-
nuities are located. The final decision on segmentation is made on the basis of joint consideration of all
partial answers at all resolutions. The results of testing the efficiency of the new algorithm on the example
of cardiac signal segmentation are presented.
Keywords: discontinuity, variable resolution, angular coefficients of straight lines segments.
1. Введение
Работа многих информационных систем связана с накоплением информации в виде изоб-
ражений, различных графиков, по которым должно быть получено мнение эксперта: при-
нято то или иное решение. Большой и постоянно возрастающий объем данных требует
разработки инструментария, позволяющего снизить нагрузку на лиц, принимающих реше-
ния, путем частичной или полной автоматизации обработки исходных данных.
Обработка данных предполагает выделение характерных элементов функции, реа-
лизацией которой является график. Прежде всего, это разрывы непрерывности самой
функции и ее производных, максимумы, минимумы, отрезки прямых как отдельные эле-
менты кусочно-гладкой функции, прочее.
Как правило, графики, подлежащие обработке, искажены помехами, что затрудняет
решение этих задач не только в автоматическом, но даже в полуавтоматическом режиме.
Благодаря свойствам зрительного восприятия, человек способен выделять на гра-
фике определенные элементы, несмотря на значительные помехи, то есть сегментировать
график.
158 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
Рис. 1. Изменение размеров зоны возбуждения
рецептивного поля нейрона во время
зрительного акта
Задача данной работы заключается в том, чтобы проанализировать новейшие ис-
следования механизмов зрительного восприятия, составить формальное описание их рабо-
ты в части выделения указанных элементов и реализовать их в разрабатываемых сред-
ствах обработки визуальной информации.
Исследования зрительного восприятия человека показали, что каждый из нейронов
зрительной системы получает информацию от множества рецепторов, составляющих ре-
цептивное поле нейрона. В простейшем случае рецептивное поле нейрона имеет форму
круга. Рецептивные поля соседних нейронов перекрываются [1]. Центральная часть рецеп-
тивных полей называется зоной возбуждения, периферийная часть (кольцо вокруг цен-
тральной части) – зоной торможения. При подаче светового стимула на зону возбуждения
рецептивного поля нейрона генерируется определенное количество импульсов. Чем боль-
ше стимул, тем большее количество импульсов будет сгенерировано. Если размер светово-
го стимула превысит диаметр зоны возбуждения, занимая часть зоны торможения, количе-
ство импульсов будет уменьшаться. Зрительное восприятие человека работает в режиме
следующих друг за другом зрительных актов продолжительностью около 150 мс. По окон-
чании зрительного акта происходит саккада (подергивание глазодвигательных мышц):
изображение на сетчатке смещается и начинается следующий зрительный акт. В результа-
те исследований размеров зон возбуждения рецептивных полей было установлено [2], что
размер их не остается постоянным в течение зрительного акта. Если в начале зрительного
акта (рис. 1) этот размер имеет максимальное значение, то к концу зрительного акта он
уменьшается до минимально возможного (1–2 рецептора). Позднее наличие этого явления
было подтверждено, а само явление было исследовано уже на современном уровне [3].
Было показано, что количество активируемых нейронов тестовым стимулом уменьшается
во время зрительного акта. Расположенный со смещением относительно центра рецептив-
ного поля нейрона стимул (в пределах максимального размера рецептивного поля, но за
пределами минимального размера рецептивного поля) в начале зрительного акта вызывал
отклик, который затем пропадал по мере уменьшения размера зоны возбуждения рецеп-
тивного поля до минимального. В терминах обработки сигналов и изображений это озна-
чает, что обработка производится при различных значениях разрешающей способности.
Под разрешающей способностью применительно к изображениям будем понимать размер
(площадь) пиксела, в пределах которого определяется единственное значение яркости.
В реальной действительности доступны только последовательности измерений на
конечных пространственных интервалах (например, пикселах) либо через конечные про-
межутки времени. Величина конечных пространственных интервалов либо конечных про-
межутков времени, через которые выполняются измерения, характеризуют разрешающую
способность реализации сигнала или
изображения.
Известны методы обработки
изображений, использующие раз-
личные значения разрешающей спо-
собности, которые получили назва-
ние “coarse-to-fine”. Идея этих мето-
дов заключается в прореживании
исходных данных для исключения
неподходящих объектов или нерелевантных областей изображения на ранних стадиях об-
работки, чтобы применить вычислительно затратную часть алгоритма к меньшему количе-
ству данных [4]. Один из вариантов такого подхода – использование модификации извест-
ного алгоритма, реализующей подход «coarse-to-fine», подходящей для решения конкрет-
ного класса задач.
ISSN 1028-9763. Математичні машини і системи, 2018, № 2 159
Например, в [5] модель эталонов, состоящих из отдельных частей, соединенных не-
жесткими связями, рассматривается с разным разрешением. Сформулирован алгоритм пе-
рехода от низкого разрешения к высокому. Предлагаемый метод обработки основан на
наблюдении, что поиск областей на изображении, соответствующих каждой части эталона,
является наиболее вычислительно затратной операцией по сравнению с обнаружением
значимых частей и расчетом их оптимальной конфигурации. Минимизация количества
операций сравнения частей эталонов с изображением подразумевает ускорение операции
обнаружения. Начиная с самого низкого разрешения эталонов, проводится их сравнение с
изображением. Отбираются только наиболее вероятные расположения. Затем найденные
локально оптимальные расположения рекурсивно распространяются на части модели с
большим разрешением. Рекурсивным удалением неподходящих расположений из про-
странства поиска множество возможных положений уменьшается так, что на максималь-
ном разрешении требуется провести лишь несколько сравнений эталонов с изображением.
Предложенный метод позволяет добиться десятикратного ускорения вычислений по срав-
нению со стандартным методом динамического программирования.
Рассматриваемый в [6] алгоритм использует схожую идею исключения больших
областей из пространства гипотез на ранних стадиях распознавания, однако на каждом
разрешении используется последовательность детекторов объектов. Результатом работы
детектора является количественная оценка рассматриваемой области, сравнивая которую с
некоторым порогом принимается решение о применении следующих детекторов из после-
довательности к этой области. Область будет рассмотрена при следующем разрешении,
если ее количественные оценки от каждого детектора превысили соответствующие поро-
говые значения. Все пороги устанавливаются автоматически на основании вероятностных
оценок.
При распознавании лиц процедура coarse-to-fine может быть реализована путем
применения разных методов распознавания для сокращения количества кандидатов на
каждом шаге.
В [7] процесс принятия решения проходит несколько стадий: 1) оценка принадлеж-
ности одному из всех возможных классов (one-against-all of SVM); 2) определение принад-
лежности каждого кандидата одному из пары классов (one-against-one of SVM); 3) алго-
ритм Eigenface; 4) метод RANSAC. Стадии 1) и 2) используют характеристики всего изоб-
ражения лица, полученные из дискретного косинусного преобразования. На стадии 3) рас-
сматриваются проекции изображений лиц в пространство характеристик. Пространство
лиц определяется собственными векторами множества лиц и на основании информации об
интенсивности изображения лица. Метод RANSAC применяется на последней стадии, где
пространственная информация, полученная методами эпиполярной геометрии для прове-
ряемого изображения, сравнивается с двумя эталонными изображениями и выбирается
изображение с наибольшим значением подобия и с кратчайшими расстояниями до соот-
ветствующих характерных точек.
Рассматриваемая в [8] задача установления соответствия между пикселами двух
изображений лиц человека (нахождения разметки) эффективно решается при помощи по-
строения «каскадов» разметок. Внутри одного каскада строится новая разметка для изоб-
ражений с разрешением в 2 раза меньше относительно исходного. После этого определяет-
ся начальное приближение для исходной разметки на основании новой разметки и ищется
поле движения относительно этого начального приближения, но с меньшим количеством
меток. Алгоритм решения задачи, использующий один «каскад», выполняется в восемь раз
быстрее, сохраняя при этом точность отыскания поля движения для двух изображений.
Динамическое программирование очень часто используется в задачах распознава-
ния: распознавание речи, распознавание символов, поиск соответствия по шаблону для
деформируемых объектов, отслеживание дороги. Однако постановки подобных задач
160 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
очень часто приводят к пространству состояний огромных размеров, из-за чего расчеты
могут стать невыполнимыми даже с использованием динамического программирования.
Для преодоления сложностей такого рода в [9] предлагается использовать динамическое
программирование coarse-to-fine (CFDP). Основная идея такого подхода – сформировать
ряд грубых приближений исходного графа динамического программирования путем объ-
единения состояний графа в «сверх состояния». Для каждой грубой аппроксимации опти-
мальный путь рассчитывается с «оптимистичными» стоимостями дуг между сверхсостоя-
ниями. Сверхсостояния вдоль этого оптимального пути пересматриваются, процесс повто-
ряется снова, пока не будет найден доказуемо оптимальный глобальный путь. Во многих
случаях глобальный оптимум достигается с гораздо меньшими затратами на вычисления,
чем при прямом использовании динамического программирования. Предложенный алго-
ритм особенно хорошо подходит для задач с большим пространством состояний. В соот-
ветствии с [10] скорость алгоритма CFDP зависит от структуры объединения и природы
задачи. В наилучшем случае CFDP позволяет получить значительное сокращение вычис-
лений по сравнению с обычным методом динамического программирования; в наихудшем
случае он, фактически, будет работать медленнее.
Целью применения методов с изменяющейся разрешающей способностью в рас-
смотренных выше случаях является определение частей исходного изображения или ча-
стей исходного набора данных, содержащих информацию, которая является полезной для
решения поставленной задачи. Сложные расчеты выполняются только над этими частями.
При этом природе механизма изменения разрешающей способности, используемого в каж-
дом конкретном случае, значения не придается.
В отличие от известных методов, вновь разработанный метод использует свойство
изменения разрешающей способности, присущее системе зрительного восприятия челове-
ка, для повышения надежности принятия решения при обработке сигнала.
2. Применение переменной разрешающей способности для обработки (сегментации)
графиков дискретных реализаций неизвестных функций
Обработка графика экспериментальной кривой выполняется, исходя из предположения,
что экспериментальная кривая представляет собой реализацию неизвестной функции
)(xfy , определенной на отрезке [ , ]a b и заданной некоторой дискретной последователь-
ностью ; 1,2...iy i I
вида “отсчет-значение”. В то же время для решения большого количе-
ства практических задач необходимо обрабатывать экспериментальные кривые, которые
могут быть представлены только кусочно-гладкими функциями. Кривая, определяемая
функциональной зависимостью ( ), ( )y f x a x b , является кусочно-гладкой, если функ-
ция )(xfy имеет конечное число разрывов на [ , ]a b и отрезок [ , ]a b может быть разделен
точками на конечное число N частичных сегментов так, что функция )(xfy будет
иметь непрерывные производные одновременно не равные нулю на каждом сегменте. То
есть, для сегментации экспериментальной кривой необходимо определить множество гра-
ничных точек сегментов },...,,{ 10 NtttT и их количество 1N .
Алгоритм проверки условия непрерывности функции )(xf в некоторой точке c ,
которое формулируется в математическом анализе, может быть представлен следующим
образом [11]: начиная с некоторого значения cx1 окрестность точки c уменьшается
( cxcx 21 , cxcx 32 , …), стремясь к нулю. Функция )(xf считается непрерыв-
ной в точке c , если окрестность )(cf так же стремится к нулю:
( 1 2( ) ( ) ( ) ( )f x f c f x f c , )()()()( 32 cfxfcfxf , …). То есть используется изме-
няющаяся окрестность точки c для анализа непрерывности функции в указанной точке.
ISSN 1028-9763. Математичні машини і системи, 2018, № 2 161
Уменьшение размеров зоны возбуждения рецептивного поля нейрона зрительной системы
может рассматриваться как уменьшение окрестности точки в центре рецептивного поля.
Процесс, аналогичный алгоритму проверки условия непрерывности в точке из математи-
ческого анализа, повторяется в зрительной системе человека и животных во время каждого
зрительного акта. Существенное отличие между изменением разрешения в зрительной си-
стеме и анализом непрерывности функции в точке в математическом анализе заключается
в том, что элементы рецептивного поля являются объектами дискретного пространства.
Поэтому определение условия непрерывности из математического анализа непригодно для
анализа непрерывности экспериментальных кривых, поскольку они являются реализация-
ми неизвестных функций и задаются последовательностями значений, которые, в свою
очередь, являются множествами точек в некотором дискретном пространстве. Но в начале
зрительного акта зона возбуждения рецептивного поля состоит из большого количества
точек (рецепторов). Пока множества рецепторов в зонах возбуждения рецептивных полей
нейронов остаются не пустыми, применение определения непрерывности к функции ярко-
сти, определенной в дискретном пространстве рецепторов, не противоречит классической
теории непрерывности функций. Описанный феномен, наблюдаемый в зрительной системе
человека и животных, может быть использован в качестве прототипа для нового метода
обработки сигналов с использованием концепции переменной разрешающей способности.
Метод сегментации на основе переменной разрешающей способности заключается
в том, что задают некоторую начальную, «грубую», разрешающую способность m , харак-
теризуемую начальным значением интервала mq , по которому определяют значение сиг-
нала на выбранном интервале одним из известных способов. Сеткой «грубых» отсчетов
называется последовательность без пропусков интервалов аргумента графика функции.
Для каждой разрешающей способности задают K взаимно сдвинутых сеток «грубых» от-
счетов. Под сдвигом одной сетки относительно другой одного и того же разрешения по-
нимают смещение в пространстве точных отсчетов границ всех интервалов одной сетки
относительно интервалов другой сетки на )( Kqm точных отсчетов. Смысл смещения
сеток заключается в том, чтобы наиболее точно определить совпадение значения аргумен-
та функции, для которого наблюдается разрыв непрерывности, с границей интервала сет-
ки. Для каждой сетки «грубых» отсчетов
),( kmI определяют значения сигнала ),( km
iy дис-
кретной реализации функции и в результате обработки получают значения аргументов,
при которых функция, возможно, претерпевает разрыв.
Если функция )(xfy имеет разрыв непрерывности в некоторой точке c , то, по
крайней мере, одна из реализаций функции
),( kmY в окрестности «грубого» отсчета, содер-
жащего точку c , испытает резкое изменение, которое будет фиксироваться при последу-
ющих разрешающих способностях (уменьшающихся окрестностях точки c ) и не будет
уменьшаться [12]. Результатом совместного рассмотрения частных ответов от некоторой
последовательности разрешений является определение значений аргументов разрывов
функции при “грубых” разрешающих способностях.
На каждом графике в примере (рис. 2) по оси абсцисс отложены номера отсчетов.
По оси ординат на графиках (а) и (б) отложены измеренные значения сигналов на каждом
отсчете, на графиках (а.1) и (б.1) – номера разрешений в последовательности разрешений,
которые были использованы для анализа экспериментальной кривой. Каждая горизонталь-
ная линия на рис. 2 а.1, 2 б.1 соответствует интервалам в пространстве точных отсчетов, на
которых обнаруживались разрывы непрерывности при конкретном разрешении. Непре-
рывными линиями обозначены резкие изменения – скачки – от меньшего к большему зна-
чению. Пунктирные линии обозначают скачки от большего к меньшему значению. Жир-
ными вертикальными линиями по сторонам графиков на рис. 2 а.1, 2 б.1 обозначены под-
множества одинаковых частных ответов от разрешений. Черным цветом выделены под-
162 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
множества ответов, которые считаются результатом сегментации. Информация о скачках
экспериментальной кривой, полученная при низких разрешениях (рис. 2 б.1), позволила
исключить из рассмотрения участки экспериментальной кривой, на которых были обнару-
жены скачки при максимальной разрешающей способности из-за влияния шума.
Таким образом, метод сегментации с переменной разрешающей способностью поз-
воляет принимать удовлетворительные устойчивые решения по сегментации сигналов,
искаженных помехами.
Покажем, что дискретная реализация непрерывной гладкой функции может быть
представлена как реализация кусочно-гладкой функции в дискретном пространстве.
Обычно точки дискретной последовательности рассматриваются в математике как
изолированные, но поскольку мы имеем дело с реализацией некоторой непрерывной
функции, эти точки должны быть последовательно соединены отрезками прямых (рис. 3).
Реализация сигнала или функции, рассмотренная при разном разрешении, может
восприниматься как непрерывная, либо как претерпевающая разрыв. Это зависит от выбо-
ра значения порога d , поскольку разрыв непрерывности первого рода для дискретной реа-
лизации функции определяется выражением dyy ii 1 .
Рис. 2. Примеры сегментации графиков функций в отсутствие помех (а)
и искаженных шумами (б) при изменяющейся разрешающей способности
a.1
а
б.1
б
Рис. 3. Дискретная реализация функции при максимальном разрешении (а)
и некотором грубом разрешении (б)
а б
ISSN 1028-9763. Математичні машини і системи, 2018, № 2 163
Подчеркнем, что математическое понятие «разрыв непрерывности» является аб-
стракцией, которую в реальной действительности можно наблюдать только в некотором
приближении. В самом деле, имеется в виду разрыв непрерывности некоторой функции в
точке, а именно в математической точке, размер которой является бесконечно малой вели-
чиной, либо для функций, аргументом которых является время. Конечное изменение зна-
чения функции происходит в течение бесконечно малого промежутка времени.
В то же время окрестность точки дискретной реализации кусочно-гладкой функции,
в которой проверяется наличие разрыва непрерывности первого рода, не может стать бес-
конечно малой. Минимальный размер окрестности точки в дискретном пространстве со-
ставляет 1 дискрету, а, значит, угловой коэффициент прямой, проведенной через 2 сосед-
ние точки дискретной реализации непрерывной функции, всегда конечный. -окрестность
точки непрерывного пространства в дискретном пространстве может быть охарактеризо-
вана первой конечной разностью в точке. В силу того, что расстояние между двумя сосед-
ними отсчетами составляет 1 дискрету, угловой коэффициент отрезка прямой, соединяю-
щего две соседние точки, (рис. 4) также может быть охарактеризован первой конечной
разностью. Поэтому отыскание разрывов непрерывности функции по ее реализации в дис-
кретном пространстве [11] может быть представлено как отыскание отрезков прямых, со-
единяющих 2 соседние точки дискретной реализации функции с угловым коэффициентом,
превышающим заданное пороговое значение d .
Рассмотрим участок графика дискретной реализации функции совместно при мак-
симальном и некотором грубом разрешении m (рис. 5).
Точки A и B являются точками в соседних отсчетах с номерами i и 1i при мак-
симальной разрешающей способности, точки 'A и 'B являются точками в соседних отсче-
тах mi и 1mi при некотором грубом разрешении. Точки A и 'A совпадают.
В треугольнике ABC угловой коэффициент отрезка AB определяется по форму-
ле BCACBC , так как на сетке максимального разрешения расстояние 1AC (1
дискрета). Чтобы между точками A и B на сетке максимального разрешения фиксировал-
ся разрыв непрерывности, необходимо, чтобы выполнялось неравенство
dBC . (1)
Выполнение этого неравенства будет свидетельствовать о том, что угловой коэф-
фициент отрезка AB больше порога d . Обозначим угловой коэффициент отрезка
'AE . Тогда , поскольку на сетке точных отсчетов ACAC' , а ''CEBC .
Чтобы определить значение порога, при котором на разных разрешающих способ-
ностях будут определяться отрезки прямых с угловым коэффициентом больше заданного,
рассмотрим подобные треугольники ABC и ''' CAB . Угловые коэффициенты отрезков AB
и ''AB совпадают в силу равенства углов при вершине A . Значит, выполняется равенство
'''' ACCBACBC . На сетке максимальной разрешающей способности 1AC , mqAC ' ,
тогда mqBCCB ''' и из (1) следует mqdCB ''' . Таким образом, поиск на графике от-
резков прямых с угловым коэффициентом больше заданного может быть выполнен мето-
дом поиска разрывов непрерывности при изменяющейся разрешающей способности с из-
меняющимся значением порога Ddm , mm qdd , индивидуальным для каждого разре-
шения. Если при некотором грубом разрешении m на интервале ]1,[ mm ii реализации
функции
)(mY обнаружен отрезок прямой с угловым коэффициентом больше порогового
значения Ddm , mm qdd , то при повышении разрешения внутри отображения этого
интервала на сетку отсчетов максимального разрешения так же будет обнаруживаться ми-
164 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
Рис. 4. Разрыв непрерывности первого рода для кусочно-гладкой функции (а)
и соответствующее ему резкое изменение на ее дискретной реализации (б)
c
y
x 0
а
i i+1
y
x 0
б
A≡A'
B
C C'
B''
B'
i i+1 i+3
E'
y
0 x
Рис. 5. Поиск участков графика, которые могут содержать отрезки прямых
с угловым коэффициентом больше некоторого наперед заданного значения
– точки дискретной реализации
функции при максимальном раз-
решении
– точки дискретной реализации
функции при некотором грубом
разрешении
– вспомогательные точки
i+2
im im+1
нимум один отрезок с угловым коэффициентом, превышающим соответствующее разре-
шению пороговое значение.
Следует отметить, что при рассмотрении дискретной реализации неизвестной
функции вместо производных используются конечные разности. Для поиска разрывов не-
прерывности (рис. 4) достаточно рассмотрения конечных разностей первого порядка. Для
поиска разрывов градиента функции (разрывов первой конечной разности) должны быть
рассмотрены конечные разности второго порядка.
3. Примеры обработки экспериментальных данных
Использование переменной разрешающей способности при обработке (сегментации) гра-
фиков функций представляется целесообразным и естественным, поскольку восприятие
визуальной информации зрительной системой человека вообще и графиков в частности
происходит в режиме изменяющейся разрешающей способности. Эффективность исполь-
зования изменяющейся разрешающей способности в прикладных задачах должна быть
проверена экспериментально.
ISSN 1028-9763. Математичні машини і системи, 2018, № 2 165
Рис. 7. Фрагмент сегментированного кардиосигнала с 25 по 30 секунду
Рис. 8. Фрагмент сегментированного кардиосигнала с 10 по 15 секунду
Для проведения экспериментов исходные данные были взяты из проекта «Медгрид»
[13]. Работа предложенного алгоритма проверялась на кардиосигналах, которые были по-
лучены в разное время и от разных пациентов. На всех графиках по оси абсцисс отложено
время в миллисекундах, по оси ординат – напряжение в милливольтах. Рассматривались
прошедшие предварительную фильтрацию кардиограммы продолжительностью 30 секунд
и кардиограммы без предварительной обработки продолжительностью 90 секунд.
На рис. 6 – 8 представлены 5 секунд фрагменты кардиосигналов продолжительно-
стью 30 секунд, сегментированные по R-зубцу с помощью предложенного метода. Рис. 6:
сигнал визуально не искажен, отсутствуют артефакты в виде экстрасистол, незначитель-
ный шум, изолиния нулевого уровня хорошо просматривается на графике. Рис. 7 – 8: сиг-
нал имеет незначительные искажения, обусловленные помехами, на графиках имеются
экстрасистолы.
Рис. 6. Фрагмент сегментированного кардиосигнала с 15 по 20 секунду
166 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
На рис. 9 а, б и рис. 10 а, б приведены примеры сегментации кардиосигналов с по-
мощью предложенного метода без предварительной обработки. На графиках присутствуют
сильный ВЧ шум, дрейф изолинии нулевого уровня, есть испорченные циклы, амплитуды
Т-зубцов превышают амплитуды R-зубцов.
4. Выводы
Предложен новый метод поиска разрывов непрерывности неизвестных функций по графи-
кам их дискретных реализаций. Данный метод использует понятие переменной разреша-
ющей способности и опирается на актуальные результаты, полученные в нейрофизиологии
зрения. Метод пригоден для обработки искаженных помехами графиков без дополнитель-
ной априорной информации о параметрах помех. Предложена интерпретация метода, поз-
воляющая на графиках дискретных реализаций функций устанавливать расположение от-
резков прямых, соединяющих пары соседних точек, с угловым коэффициентом больше
заданного порогового значения.
Выполнена программная реализация и проведена экспериментальная проверка ал-
горитма на примере сегментации кардиосигнала. Обработано более 100 кардиограмм раз-
личных пациентов. Получены положительные результаты.
Программа будет использована в дальнейших исследованиях кардиосигнала.
Рис. 9 а. Фрагмент сегментированного кардиосигнала без предобработки
продолжительностью 90 секунд, с 30 по 40 секунду
Рис. 9 б. Фрагмент сегментированного кардиосигнала без предобработки
продолжительностью 90 секунд, с 34 по 36 секунду
ISSN 1028-9763. Математичні машини і системи, 2018, № 2 167
СПИСОК ИСТОЧНИКОВ
1. Hubel H.D. Eye, brain, and vision / Hubel H.D. – New York: Scientific American Library; Distributed
by W.H. Freeman, 1988. – 240 p.
2. Подвигин Н.Ф. Динамические свойства нейронных структур зрительной системы / Подвигин
Н.Ф. – Ленинград: Наука, 1979. – 158 с.
3. Ruksenas O. Dynamics of Spatial Resolution of Single Units in the Lateral Geniculate Nucleus of Cat
During Brief Visual Stimulation / O. Ruksenas, A. Bulatov, P. Heggelund // J Neurophysiol. – 2007. –
N 97. – P. 1445 – 1456.
4. Sharypanov A. Joint study of visual perception mechanism and computer vision systems that use
coarse-to-fine approach for data processing / A. Sharypanov, A. Antoniouk, V. Kalmykov // Information
content & processing. – 2014. – Vol. 1, N 3. – P. 287 – 300.
5. Pedersoli M. A Coarse-to-fine approach for fast deformable object detection / M. Pedersoli, A. Vedaldi,
J. Gonz`alez // CVPR. – 2011. – June. – P. 1353 – 1360.
6. Moreels P. Probabilistic Coarse-To-Fine Object Recognition / P. Moreels, P. Perona // Technical report.
– Pasadena: California Institute of Technology, 2005. – 49 p.
7. Lee J.-D. A Multi-Stage Classifier for Face Recognition Undertaken by Coarse-to-fine Strategy, State
of the Art in Face Recognition [Електронний ресурс] / J.-D. Lee, C.-H. Kuo; J. Ponce, A. Karahoca (Ed.)
// Tech. – 2009. – Режим доступу: http://www.intechopen.com/books/state_of_the_art_in_
face_recognition/a_ multistage_ classifier_for_face_ recognition_undertaken_by_coarse-to-fine_strategy.
Рис. 10 а. Фрагмент сегментированного кардиосигнала без предобработки
продолжительностью 90 секунд, с 70 по 80 секунду
Рис. 10 б. Фрагмент сегментированного кардиосигнала без предобработки
продолжительностью 90 секунд, с 72 по 74 секунду
http://www.intechopen.com/books/state_of_the_art_in_
168 ISSN 1028-9763. Математичні машини і системи, 2018, № 2
8. Тищенко М.А. Тривимірна реконструкція людського обличчя в задачах ідентифікації особи: дис.
… кандидата техн. наук / Тищенко М.А. – Київ: Мiжнародний науково-навчальний центр інфор-
мацiйних технологiй та систем, 2012. – 120 с.
9. Raphael C. Coarse-to-Fine Dynamic Programming / C. Raphael // IEEE Transactions on Pattern Analy-
sis and Machine Intelligence. – 2001. – Vol. 23. – Р. 1379 – 1390.
10. Lucena O.B. Dynamic Programming, Tree-width and Computation on Graphical Models: PhD thesis.
– Division of Applied Mathematics / Lucena O.B. – Providence: Brown University, 2002. – 85 p.
11. Kalmykov V. Segmentation of Experimental Curves Distorted by Noise / V. Kalmykov, A. Sharypa-
nov // Journal of Computer Science Systems Biology. – 2017. – Vol. 10, Issue 3 OMICS International. –
Р. 50 – 55.
12. Kalmykov V. Approximation of the Experimental Curves by Piecewise Smooth Functions / V. Kal-
mykov, V. Vishnevskey, D. Masol // 5th International Conf. on Application of Information and Commu-
nication Technology and Statistics in Economy and Education (ICAICTSEE – 2015), (Sofia, Bulgaria,
November 13–14
th
2015). – Sofia, Bulgaria, 2015. – Р. 322 – 330.
13. Вишневський В.В. Еволюція технологічного задуму проекту «Медгрід» [Електронний ресурс] /
В.В. Вишневський // Научно-практ. конф. «Системы поддержки принятия решений. Теория и прак-
тика», СППР’2017, (Киев, 5 июня 2017 г.). – Киев, 2017. – Режим доступу:
http://conf.atsukr.org.ua/conf_files/conf_dir_38/Vishnevskey_sppr2017.pdf.
Стаття надійшла до редакції 12.03.2018
|