Устройство для определения медианы

 

Изобретение относится к вычислительной технике и может быть использовано для обработки статистической информации. Цель изобретения - упрощение устройства, которое достигается за счет выделения (выбора) двух столбцов элементов локального фрагмента изображения (ЛФИ) в первом цикле и выделения третьего столбца элементов ЛФИ во втором цикле при равной производительности с прототипом. Устройство для определения медианы состоит из 13 элементов выделения экстремумов и 8 элементов задержки. 1 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„Я0„„1460727

А1 (5П 4 06 F 15/36 описдни иэоьркткния

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Запишем элементы, упорядоченные в процессе первой и второй сортировок, р„ в следующем виде

П„ П„ П„

Da i D П23

Пу П 2. Пзъ гдеП;, Dla Dig i=1,3;

П, « П, «П.,„, 1 = 1,3.

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

Ь элементов, больших медианы, П, Dqq, D и ряд элементов, неопределенных по отношению к медиане, П „П, П,з.

Поиск медианы осуществляется среди элементов Dq„ Dz» D, . Медиана среди

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

flPH ГКНТ СССР (21) 4271376/24-24 (22) 29.06 ° 87 (46) 23.02.89. Бюл. 9 7 (72) К.И.Кучеренко (53) 681.3(088.8) (56) Авторское свидетельство СССР

К 1305715, кл. G 06 F 15/36, 1985. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МЕДИАНЫ (57) Изобретение относится к вычислительной технике и может быть исполь1

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

Цель изобретения — упрощение устройства.

На чертеже приведена структурная схема устройства.

Устройство содержит элементы 1-13 выделения экстремумов и элементы

14-21 задержки, информационные входы

22-24 и выход 25.

Устройство для определения медианы работает следующим образом.

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

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

ЛФИ во втором цикле при равной производительности с прототипом. Устройство для определения медианы состоит из 13 элементов выделения экстремумов и 8 элементов задержки. 1 ил.1460727

55 элементов П „ Р«, О, является медианой локального фрагмента иэображения на выходах элементов 1-3 и элементов

14-16, представляющих собой сортирующую сеть для трех элементов и осуществляющих сортировку столбцов локального фрагмента изображения размером в три элемента.

На входы 22-,24 поступают неупорядоченные по возрастанию элементы столбца, а с выходов элемента 3 и элемента 16 считываются упорядоченные по возрастанию элементы столбца, поступающие на входы 22-24 тремя циклами ранее.

Элементы 17-19 обеспечивают задержку на один цикл столбца упорядоченных по возрастанию элементов.

На выходе элемента 16 содержится минимальный элемент из трех элементов столбца, на выходе минимального значения элемента 3 — средний элемент столбца, а на выходе максимального значения элемента 3 — максимальный элемент столбца..Так как соседние пересекающиеся локальные фрагменты отличаются одним столбцом элементов, то для каждого последующего локального фрагмента возможно использовать результаты сортировки двух столбцов предыдущих локальных фрагментов.

Так как элементы D„, D, О,, П,, D>z, Р33, являющиеся меньшими и большими по отношению к медиане, исключаются после сортировки внутри строк локального фрагмента, то возможно упростить сортирующие сети для сортировки внутри строк. Таким образом выполняется не полная сортировка элементов внутри строк, а определяются лишь элементы 13<, D« Б.<,. Элементы 4 и 7 предназначены для определения элемента D», который является минимальным элементом из трех элементов строки, т.е. представляет собой сеть для определения минимального элемента из трех сравниваемых элементов.

Элементы 5, 8, 10 и 20 представляют собой сеть для определения медианы из трех элементов и предназначены для определения Р . Элементы,6 и 9 представляют сеть для определения максимального элемента из трех сравниваемых и предназначены для определения D,>, В течение каждого цикла на входы элемента 4 поступают два элемента строки с выхода максимального значе5

50 ния элемента 3 и выхода элемента 17.

Минимальный из двух Сравниваемых элементов строки локального фрагмента изображения с выхода элемента 4 и третий элемент строки с выхода максимального значения элемента 3 в следующем цикле поступают на входы элемента 7, на выходе которого, соединенном с входом элемента 11 получаем минимальный элемент строки D9<.

Аналогично на выходе элемента 9 получаем максимальный элемент строки

D, а на выходе элемента 10 — медиану строки D . В течение каждого цикла на входы элемента 6 поступают два элемента строки с выхода элемента

16 и выхода элемента 19. Максимальный из двух сравниваемых элементов строки с выхода элемента 6 и третий элемент строки с выхода элемента 16 в следующем цикле поступают на входы элемента 9. На выходе максимального значения элемента 9 получаем максимальный элемент строки из трех элементов D, В течение каждого цикла на входы элемента 5 поступают два элемента строки с выхода минимального значения элемента 3 и с выхода элемента 18.

Максимальный из двух сравниваемых элементов строки сохраняется в течение цикла посредством элемента 20, а. минимальный из двух сравниваемых элементов строки сравнивается в элементе 8 с третьим элементом строки, поступающим в следующем цикле с выхода минимального значения элемента 3.

Посредством элемента 10 определяется медиана строки D

Элементы 11, 13 и 21 представляют собой сортирующую сеть для определе-. ния медианы из трех элементов и позволяют определить медиану среди элементов D», D D „ которая является медианой и для всего локального фрагмента изображения. В каждый цикл на входы 22 — 24 поступает новый столбец элементов, а с выхода 25 считывается медиана для локального фрагмента изображения, последний столбец которого поступил девятью циклами ранее.

Формула изобретения

Устройство для определения медианы, содержащее тринадцать элементов выделения экстремумов и восемь эле1460727 ментов задержки, причем первый и второй входы первого элемента вьщеления экстремумов являются соответственно первым и вторым информационными входами устройства, вход первого элемента задержки является третьим информационным входом устройства, выход максимального значения первого элемента выделения экстремумов соединен с входом второго элемента задержки, а выход минимального значения — c первым входом второго элемента вьщеления экстремумов, выход первого элемента задержки подключен к второму входу второго элемента выделения экстремумов, выход второго элемента задержки соединен с первым входом третьего элемента вьщеления экстремумов, выход максимального значения второго элемента выделения экстремумов подключен к второму входу третьего элемента выделения экстремумов, а выход минимального значения — к входу третьего элемента 25 задержки, выход максимального значения третьего элемента вьщеления экстремумов соединен с входом четвертого элемента задержки и с первым входом четвертого элемента выделения Зо экстремумов, второй вход четвертого элемента вьщеления экстремумов подключен к выходу четвертого элемента задержки, выход минимального значения третьего элемента выделения экс35 тремумов соединен с первым входом пятого элемента выделения экстремумов и с входом пятого элемента задержки выход которого подключен к второму входу пятого элемента вьщеления экстремумов, выходу третьего элемента задержки непосредственно и через шестой элемент задержки соединен соответственно с первым и вторым входами шестого элемента вьщеления экстремумов, выход минимального значения .

1 четвертого элемента вьщеления экстремумов подключен к первому входу .седьмого элемента выделения экстремумов, выход максимального значения пятого

50 элемента вьщеления экстремумов соединен с входом седьмого элемента sa«

1 держки, а выход минимального значения — с первым входом восьмого элемента выделения экстремумов, выход максимального значения шестого элемента вьщеления экстремумов подключен к первому входу девятого элемента вьщеления экстремумов, выход седьмого элемента задержки соединен с первым входом десятого элемента выделения экстремумов, второй вход которого подключен к выходу максимального значения восьмого элемента выделения экстремумов, выход минимального значения седьмого элемента выделения экстремумов подключен к первому входу одиннадцатого элемента выделения экстремумов, второй вход которого соединен с выходом максимального значения девятого элемента выделения экстремумов, выход минимального значения десятого элемента выделения экстремумов подключен к первому входу двенадцатого элемента выделения экстремумов, второй вход которого соединен с выходом максимального значения одиннадцатого элемента выделения экстремумов, выход минимального значения которого подключен к входу восьмого элемента задержки, выход минимального значения двенадцатого элемента выделения экстремумов соединен с первым входом тринадцатого элемента выделения экстремумов, второй вход которого подключен к выходу восьмого элемента задержки, выход максимального значения тринадцатого элемента вьщеления экстремумов является выходом устройства, о тл и ч а ю щ е е с я тем, что, с целью упрощения устройства, второй вход седьмого элемента вьщеления экстремумов подключен к выходу максимального значения третьего элемента выделения экстремумов, выход минимального значения которого соединен с вторым входом восьмого элемента выделения экстремумов, выход третьего элемента задержки подключен к второму входу девятого элемента вьщеления экстремумов.

1460727

Составитель Л.Григорьян-Чтенц

Редактор В.Данко Техред М.Ходанич Корректор М.Пожо

Заказ 543/56 Тираж 667 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035» Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101