Устройство для определения количества локальных экстремумов
Изобретение относится к автоматике и вычислительной технике, может быть использовано для обработки изображений и является усовершенствованием устройства по а.с. СССР N 1401451. ЦЕЛЬ ИЗОБРЕТЕНИЯ - ПОВЫШЕНИЕ ТОЧНОСТИ ОПРЕДЕЛЕНИЯ КОЛИЧЕСТВА ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ. УСТРОЙСТВО СОДЕРЖИТ БЛОК 1 БУФЕРНЫХ РЕГИСТРОВ, СОСТОЯЩИЙ ИЗ П РЕГИСТРОВ 2, (П-1) СХЕМ 3 СРАВНЕНИЯ, (К-1) ГРУПП ПО ДВА ЭЛЕМЕНТА ИЛИ 4, К ШИФРАТОРОВ 5 И БЛОК 6 СУММАТОРОВ. ШИФРАТОРЫ 5 РЕАЛИЗОВАНЫ НА СХЕМАХ ПЗУ, в которых определенной кодовой комбинации, поступающей на вход ПЗУ, соответствует определенная кодовая комбинация на выходе, определяющая количество экстремумов на отдельных отрезках выборки, при этом на дополнительных выходах шифратора появляются кодовые комбинации знаков, характеризующие наличие или отсутствие в анализируемых кодах знаков ограничения справа знаками "больше" или "меньше" значений ординат в пределах отрезка. Поступление знаков "больше" или "меньше" об ограничении справа на следующий шифратор позволяет выявить все нестрогие экстремумы в выборке. Уточненные кодовые комбинации о количестве экстремумов с выходов шифраторов поступают на блок 6 сумматора, где производится общее суммирование количества локальных экстремумов в выборке. 2 ил. 1 табл.
СВОЗ СОНЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
„„80„„1501038 А 2 д11 1 С 06 F 7/06
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
t
) К ABTQPCKOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ НОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТНРЬП ИЯМ
ПРИ ГННТ СССР (61) 1401451 (21) 4375644/24-24 (22) 12.01.88 (46) 15.08.89. Бюп. У 30 (71) Научно-производственное обьединение космических исследований (72) В.В.Гамидов, Ю.И.Кузьмин, P.À.Øåéõîâ и В.Ф.Кашин (53) 681.325(088.8) (56) Авторское свидетельство СССР
Ф 1401451, кл. С 06 F 7/06. 1986.
2 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КОЛИЧЕСТВА ЛОКАЛЬНЫХ ЭКСТРЕМУМОВ (57) Изобретение относится к автотике и вычислительной технике, может быть использовано для обработки изображений и является усовершенствованием устройства по авт. св ° СССР
М 1401451. Цель изобретения — повышение точности определения кол ичества локальных экстремумов. Устройст1 501() 38 во содержит блок 1 буфсрных регис-.т— ров, состоящий из и регистров 2. (n-1) схем 3 сравнения, (К-1) групп по два элемента ИЛИ 4. К шифраторов
5 и блок 6 сумматоров. Пифраторы 5 реализованы на схемах ПЗУ, в которых определенной кодовой комбинации, поступающей на вход ПЗУ, соответствует определенная кодовая комбинация на выходе, определяющая количество экстремумов на отдельных отрезках выборки, при этом на дополнительных выходах шифратора появпяются кодовые комбинации знаков, характеризующие
Изобретение относится к области автоматики и вь)числительной техники и предназначено для определения количества локальных экстремумов функ° ций, представленных в виде дискретных выборок.
Целью изобретения является повышение точности подсчета количества локальных экстремумов.
На фиг. 1 представлена функциональная схема устройства, на фиг. 2 — примеры графиков распределения значений ординат выборки и их разбивка на отдельные отрезки.
В таблице приведена зашивка выходных кодов шифратора от входных на примере восьмивходового шифратора, выполненного на микросхеме .К 556 РТ 4, Функциональная схема устройства (фиг. 1) включает блок 1 буферных регистров, состоящий из и регистров
2, (п-1) схем 3 сравнения, (k-1) групп по два элемента ИЛИ 4, К шифраторов 5, блок 6 сумматоров.
Устройство реализовано на следующих микросхемах: регистры 2—
К555ТМ9, схемы 3 сравнения К555СП1, элементы ИПИ 4 К555ЛЛ1, шифраторы
5 К556РТ4, сумматоры 6 К555И16.
Устройство работает следующим образом.
В и регистрах 2 блока 1 буферных регистров записываются двоичные коды значений ординат выборки анализируемой функции. Двоичные коды значений ординат с выходов и регистров 2 блока 1 параллельно поступают на входы (n-1) схем 3 сравнения, где
55 наличие или отс, тствие в анализируемых кодах знаков ограничения справа знаками "больше или меньше" значений ординат в пределах отрезка, Поступление знаков "больше" или
11 It меньше об ограничении справа на следующий шифратор пбзволяет выявить все нестрогие экстремумы в выборке.
Уточненные кодовые комбинации о количестве экстремумов с выходов шифраторов поступают на блок 6 сумматора, где производится общее суммирование количества локальных экстремумов в выборке. 2 ил., 1 табл. происходит сравнение соседних значений ординат выборки. Если (i-1)-е значение ординаты меньше i-го значения огцинаты, то уровень "1" появляется на первом выходе схемы 3 сравнения, если больше — то на втором. В случае равенства двух соседних значений на обоих выходах схемы
3 сравнения будет присутствовать уровень "0". Результаты сравнения с выходов всех (п-1) схем 3 сравнения поступают на соответствующие входы k шифраторов 5. В результате подключения очередной группы, coc. m тоящей из (-) схем 3 сравнения, к очередному шифратору вся выборка значений ординат разбивается на отдельные отрезки. В каждом из отрезков количество анализируемых значений ординат определяется количеством входов шифратора 5, равное числу m, где m > 4 — число четное, а количество таких отрезков — количеством шифраторов, равное k. Причем так как выходы первых схем 3 сравнения каждой р-й группы подключены через . вторые входы соответствующих групп элементов ИЛИ 4 к первым входам р-ro шифратора 5, то обеспечивается сравнение значений ординат в окрестнос-. тях границ отрезков выборки. А для случаев, когда два или несколько значений ординат, следующих одна за другой, равны и попадают на границы отрезков или все значения ординат какого-либо отрезка или ряда отрезков выборки равны, то на двух дополнительных выходах шифратора 5, 1501038 где в анализируемом отрезке перед знаками "равно" имелся один из знаков "больше" или "меньше", появляется информация об одном из этих знаков, которая через первые входы соответствующих групп элементов ИЛИ поступает на два первых входа следующего шифратора 5, способствуя выявлению всех нестрогих локальных экстремумов выборки. Где кодовые комбинации на дополнительных выходах шифраторов соответствуют: 01 знаку "больше", 10 — знаку "меньше".
Нифраторы 5 реализованы на схемах
ПЗУ, на каждые два очередных входа которых с выходов схем 3 сравнения приходят двухразрядные кодовые комбинации, характеризующие один из знаков "больше", "меньше", "равно" и соответствующие: 01 — знаку "больше", 10 — знаку "меньше", 00 — знаку "равно".
Таким образом, на m входов шифра!
I! тора 5 параллельно поступает
2 двухразрядных кодовых комбинаций знаков, характеризующих наличие или отсутствие экстремумов на отрезке выборки, в которых определенным двухразрядным совокупностям кодовых комбинаций соответствуют кодовые комбинации на первой группе выходов, определяющих количество локальных экстремумов на соответствующих отрезках выборки. A на второй дополнительной группе выходов шифратора 5, состоящей из двух выходов, появляются двухразрядные кодовые комбинации, характеризующие один из знаков
"больше" или "меньше", поступающие в следующий шифратор 5 в случае, когда два или несколько соседних значений ординат равны и попадают на границы отрезков выборки или все значения ординат какого-либо отрезка или ряда отрезков выборки равны.
В результате после окончательного установления информации о всех знаках больше" или "меньше" на двух первых входах р-х шифраторов 5 на их первых группах выходов появляется уточненное значение о количестве всех экстремумов отрезков выборки.
Коды о количестве экстремумов поступают на входы блока 6 сумматоров, где производится общее суммирование значений с количестве экстремумов в. выборке.
Для общего случая ко !!!че< тво размещений с повторениями тг;винных кодовых комбинаций знаков "боllF,F!!å, "меньше", "равно" на т входах шифратора 5 определяется по Формуле (7)
Ttl
С, I Pe RHcJIo 3HBK0B С = 3 ° количество размещений знаков.
В качестве примера показана таблица зашивки для восьмивходового шифратора, в котором число всевозможных размещений с повторениями ко(Я довых комбинаций знаков И = 3 > =
I, 3 = 81. Каждой 81 комбинации знаков соответствует определенная информация о количестве локальных экстремумов в отрезках выборки и.информация о знаке "больше" или "меньше" в случаях наличия неограниченного в пределах отрезка выборки нестрогого локального экстремума.
Рассмотрим работу устройства для определения количества локальных экстремумов на конкретных примерах, приведенных на фиг. 2 и в таблице.
Для выборок, представленных на фиг. 2, количество отрезков, на которые разбивается вся выборка, определяется количеством шифраторов. Для выборки, представленной 14-ю значениями ординат и при восьмивходовых шифраторах, количество шифраторов равно:
2 (14 — 2) 8 — 2
Для первого отрезка (Π— 4) выборки
40 (фиг. 2 ) количество локальных экстремумов, определяемое в соответст- . вии с 79 порядковым номером таблицы равно 2 — код суммы 10. Для второго отрезка (3-7) в соответствии
45 с 54 порядковым номером таблицы количество экстр"мумов равно 1 — код суммы 01 ° Для третьего отрезка (610) в соответствии с 41 порядковым номером таблицы количество экстрему; мов равно 2 — код суммы 10. Для -тет»
50 вертого отрезка (9-13) в соответст-, вии с 66 порядковым номером таблиьы количество экстремумов равно 2 — код суммы 10. Ввиду того, что значение
55 ордикаты а> равно а4 не ограничено справа от значения ординаты а зна-. ками "больше" или "меньше" в пределах первого отрезка (0-4), то неизвестно, является ли значение орди1501038 наты а> экстремумом, поэтому код знака между значениями ординат а а
lt 1t меньше — 10 об ограничении слева с дополнительных выходов шифратора, анализирующего знаки между значениями ординат первого отрезка (0-4), поступает на первые входы следующего шифратора, анализирующего знаки между значениями ординат второго отрезка (3 — 7). Код знака "меньше" °
10 заменяет код знака "равно" — 00 между значениями а, а во втором шифраторе, а так как в анализируемом втором отрезке (3 — 7) имеется огра-, ничение справа значения ординаты а, т.е. а ) а . знаком "больше" н пределах этого отрезка, то на входах второго шифратора устанавливается кодовая комбинация, соответствующая
41 порядковому номеру таблицы, которая означает наличие количества локальных экстремумов, равное 2 — код суммы 10. Так как неопределенностей об ограничениях в пределах всех от- 25 резков выборки больше нет, то, суммируя коды сумм о количестве экстремумов из отрезков выборки, получаем, что для выборки, показанной на фиг. 2а, количество локальных . экстремумов равно 8, что соответствует истинному количеству экстремумов.
Для первого отрезка (Π— 4) выборки (фиг. 2 ) количество локальных
35 экстремумов, определяемое в соответствии с 9 порядковым номером табли— цы, равно Π— код суммы 00. Для второго отрезка (3 — 7) и четвертого отрезка (9 — 13) количество локальных
40 экстремумов в соответствии с 54 и
43 порядковыми номерами таблицы равно 1 — код суммы 01, а количество локальных экстремумов для третьего отрезка (6-10) в соответствии с 79 порядковым номером таблицы равно
2 — код суммы 10. Вниду того, что значения ординат а, а, а равны
11 а в пределах первого отрезка (Π— 4) и значение ординаты ag равное а в пределах третьего отрезка
S0 . .о (6 — 10) не ограничено справа соот" ветственно от значения ординат а1 и а„ знаками "больше" или "меньше", то коды знака между значениями ординат а < а и а z а меньше — 10
11 11 55
В I об ограничении слева с дополнительных выходов первого и третьего шифраторов поступают соответственно на первые входы второго и четвертого шифратора. Код знака "меньше" — 10 заменяет код знака "равно" — 00 между значениями a3 a < H a< a10 на втором и четвертом шифраторах, а так как в анализируемых вторых (3 — 7) и четвертых (9 — 13) отрезках имеется ограничение справа значения орди- . наты aq T е ° a + ) a < 3HaKDM "больше" в пределах второго отрезка (3—
7) и значение ординаты а„, т.е. а,, а„„ знаком "меньше" в пределах четвертого отрезка (9-13), то на входах второго и четвертого шифраторов устанавливаются кодовые комбинации, соответствующие 41 и 64 порядковым номерам таблицы, которые означают, что но втором отрезке количество локальных экстремумов равно
2, а в четвертом отрезке количество локальных экстремумов сохраняется, т.е. равно 1. Так как неопределенностей об ограничениях в пределах всех отрезков выборки больше нет, то, суммируя коды сумм о количестве экстремумов из отрезков выборки, получаем, что для выборки, показанной на фиг.2 количество локальных экстремумов равно 5, что соответствует истинному количеству экстремумов.
Для первого отрезка (Π— 4) и четвертого отрезка (9 — 13) выборки ! (фиг. 2 ) количество локальных экстремумов в соответствии с 18 и 64 порядковыми номерами таблицы равно 1, а количество локальных экстремумов для второго отрезка (3 — 7) и третьего (6 — 10) в соответствии с 1 и
11 порядковыми номерами таблицы равно О. Ввиду того, что значения ординат а, а равное а+ не ограничено справа от значения ординаты а знаками "больше" или "меньше" в пределах первого отрезка (Π— 4), то код знака между значениями ординат а1> а "больше" — 01 об ограничении слева с дополнительных выходов первого шифратора поступает на первые входы второго шифратора. Код знака
"больше" — 01 заменяет код знака
"равно" 00 между значениями а, а1., и на входах второго шифратора устанавливается кодовая комбинация, соответствующая 5 порядковому номеру таблицы, которая означает, что во втором отрезке количество локальных экстремумов равно О. и так как во втором отрезке между значениями ор1 501 038
10 динат а>, а стоит знак "равно", .т.е. в этом отрезке нет ограничения справа от значения ординаты а знаками "больше" или "меньше" в. пределах второго отрезка (3 — 7) то, код знака, установившийся между значениями ординат а > а4 "больше" — 01 об ограничении слева, с дополнительных выходов второго шифратора, поступает на первые входы третьего шифратора.
Код знака "больше" — 01 заменяет код знака "равно" — 00 между значениями а, а„р и на входах третьего шифратора устанавливается кодовая комбинация, соответствующая 27 порядковому номеру таблицы, которая означает, что в третьем отрезке (6 — 10) количество локальных экстремумов равно 1. Так как неопределенностей об ограничениях в пределах всех отрезков выборки больше нет, то, сум. мируя коды сумм.о количестве экстре-. мумов из отрезков выборки, получаем, что для выборки, показанной на . фиг. 2 6, количество локальных экстремумов равно 3, что соответствует истинному количеству экстремумов.
Для первого (Π— 4), второго (37) и третьего отрезков (6 - 10) выборки (фиг. 2 ) количество локальных экстремумов в соответствии с 5, 1 и
11 порядковыми номерами таблицы равно О, а количество локальных экстремумов для четвертого отрезка (9—
13) в соответствии с 69 порядковым номером таблицы равно 3 — код суммы
11. Ввиду отсутствия ограниченйя между значениями ординат справа в первом отрезке (Π— 4) знак между значениями ординат а > а "больше"01 об ограничении слева поступает на первые входы второго шифрата и на его входах устанавливается кодовая комбинация, соответствующая
5 порядковому номеру таблицы, озна,чающая отсутствие экстремумов во втором отрезке (3 — 7). A так как значения ординат второго отрезка (3 — 7) не имеют ограничения справа, то установившийся код между значе-. ниями ординат а ) а "больше" — 01 об ограничении слева поступает на первый входы третьего шифратора и на
его входах устанавливается кодовая комбинация, соответствующая 27 порядковому номеру таблицы, которая означает, что в третьем отрезке (6 — 10) количество локальных экстремумов равно 1. Так как неопределенностейоб ограничениях в пределах всех отрезков выборки больше нет, то, суммируя коды сумм о количестве экстре мумов из отрезков выборки, получаем, что для выборки, показанной на фиг. 2 ° количество локальных экст25 ремумов равно 4. Это соответствует истинному количеству экстремумов.
Формула и з о б р е т е н и я
Устройство для определения количества локальных экстремумов по авт. св. N- 1401451, о т л и ч а ю щ е ес я тем, что, с целью повышения точности подсчета количества локальных экстремумов, в .него введены (k-1)
35 групп по два элемента HJlH, причем выходы первой схемы сравнения каждой р-й группы, где р = 2, . ° ., k, соединены с первыми двумя входами р-ro шифратора через первые входы соотko .-. ветствующих элементов ИЛИ (р-1)-й группы, вторые входы которых подключены к соответствующим дополни тельным выходам (р-1)-го шифратора.
1 501038 д.у р " д l
d ) gz) (7
Я)() (7 8>" Д ) 1 1) j
ДР{Р) / (/
{Яl»/ 5д (7 / 1,.,д, л.? j/) j/3
Ю)(7, ) d!P u y (г1(7 дЗ
А»)! У1r21
P1/» (4 ф
/7 I!» . (i 1 »р»»
;{ {{ T (»" / {, .«»»», » {
»»» „:»{»:/ ю I,Ð:, . {»» i»
i »
{ j
1 50 l 038
Составитель Е.Иванова
Техрер Л, Олийнык Корректор. О.Ципле
Редактор О.Спесивых
Заказ 4868/44 Тираж 668 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям прн ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101 о
