Устройство для определения медианы Советский патент 1989 года по МПК G06F17/18 G06F7/06 

1

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

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

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

Устройство содержит элементы 1-13 вьщеления экстремумов и элементы 14-21 задержки, информационные входы 22-24 и выход 25.

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

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

Поиск медианы осуществляется посредством трех последовательных во времени сортировок. Первая сортировка вьшолняется внутри столбцов ЛФИ, вторая сортировка - внутри строк и

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

D« D

21

D

31

0,1 D« D,z

где D D D;,

D.i D,j D

3J

D,i В„ D,5

1 j

lil;

1,3.

Ha основании упорядоченности элементов внутри строк и внутри столбцов можно определить ряд элементов, .меньших медианы, D, , D , Dj, , ряд элементов, больших медианы, D, Djj и ряд элементов, неопределенных по отношению к медиане, D,, D, 0,3.

Поиск медианы осуществляется среди элементов D,, Dji, D,j. Медиана среди

(Л

4iii 0 О vj

Ю

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

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

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

Так как элементы D,,, , D,, D,,, зг 33 являющиеся меньишми и большими по отношению к медиане, исключаются после сортировки внутри строк локального фрагмента, то возможно упростить сортирующие сети для сортировки внутри строк. Таким образом вьшолняется не полная сортировка элементов внутри строк, а определяются лишь элементы D,,, D, D,,. Элементы 4 и 7 предназначены для определения элемента D, котор.ый является минимальным элементом из трех элементов строки, т.е. представляет собой сеть для определения минимального элемента из трех сравниваемых элементов. Элементы 5, 8, 10 и 20 представляют собой сеть для определения медианы из трех элементов и предназначены дл определения D. Элементы ,6 и 9 представляют сеть для определения максимального элемента из трех сравниваемых и предназначены для определения D,.

В течение каждого цикла на входы элемента 4 поступают два элемента строки с выхода максимального значе0727

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

5

, а на выходе элемента 10 медиа0

5

0

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

В течение каждого цикла на входы элемента 5 поступают два элемента строки с выхода минимального значения элемента 3 и с выхода элемента 18. Максимальный из двух сравниваемых элементов строки сохраняется в течение цикла посредством элемента 20, а,- минимальный из двух сравниваемых элементов строки сравнивается в элементе 8 с третьим элементом строки, поступающим в следующем цикле с выхода минимального значения элемента 3. Посредством Элемента 10 определяется медиана строки D.

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

5

0

0

55

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

Устройство для определения медианы, содержащее тринадцать элемейтов выделения экстремумов и восемь чле51460727

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

де ни ме ма ме че та мо пе де то но де 15 но дел вом дел тор 20 ног дел ног дел вом 25 дел тор ног выд ног 30 вхо вых цат мов цат 22 мов к в вых цат мов 4оли цел вход экст сима 45 та в нима с вт деле элем gQ му в экст

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

держки, а выход минимального значения - с первым входом восьмого элемента вьщеления экстремумов, выход максимального значения шестого элемента вьщеления экстремумов подключен к первому входу девятого элемента вьщеления экстремумов, выход седьмого элемента задержки соединен с первым входом десятого элемента выделения экстремумов, второй вход которого подключен к выходу максимального значения восьмого элемента выделения экстремумов, выход минималь- 15 ного значения седьмого элемента выделения экстремумов подключен к первому входу одиннадцатого элемента выделения экстремзт ов, второй вход которого соединен с выходом максималь- . 20 ного значения девятого элемента выделения экстрем мов, выход минимального значения десятого элемента выделения экстремумов подключен к первому входу двенадцатого элемента вы- 25 деления экстремумов, второй вход которого соединен с выходом максимального значения одиннадцатого элемента выделения экстремумов, выход минимального значения которого подключен к 30 входу восьмого элемента задержки, выход минимального значения двенадцатого элемента вьщеления экстремумов соединен с первым входом тринадцатого элемента вьщеления экстрему- 22 мов, второй вход которого подключен к выходу восьмого элемента задержки, выход максимального значения тринадцатого элемента вьщеления экстремумов является выходом устройства, о т- оличающееся тем, что, с целью упрощения устройства, второй вход седьмого элемента вьщеления экстремумов подключен к выходу максимального значения третьего элемен- 5 та вьщеления экстремумов, выход минимального значения которого соединен с вторым входом восьмого элемента выделения экстремумов, выход третьего элемента задержки подключен к второ- Q му входу девятого элемента вьщеления экстремумов.

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