RU2101756C1 - Device of rank filtration of structured signals - Google Patents

Abstract

FIELD: computer engineering, in particular, real-time processing of information arrays, automatic image processing. SUBSTANCE: additional code converters, group of k-3 delay gates, group of binary rank filters and new connections are introduced to accomplish the goal of invention. EFFECT: increased functional capabilities due to possibility to estimate values of rank filtration. 3 dwg

Description

 The invention relates to computer technology and is intended for use in specialized computing devices when processing data arrays in real time, for example, for processing two-dimensional structural signals, in particular in automated image processing systems.

A device for comparing numbers, containing four counters, a memory unit, two registers, a comparison circuit, a clock, RS-trigger, D-trigger, five AND elements, three OR elements, two inverters, a delay element and a one-shot [1]
The device allows to calculate the results of the operation of extreme filtering of an array of N elements in N • n cycles, where n is the length of the filtering aperture.

 The disadvantage of this device is low speed and limited functionality.

Closest to the technical nature of the claimed device is a device for extreme filtering, containing a comparison element, an adder, three registers, three delay elements, an OR element, a calculator and a multiplier [2]
The device implements a method for calculating estimates of the result of the operation of extreme filtering by approximating the results of the operation of determining extreme values from the set of disjoint intervals of the signal sampling.

 The disadvantage of this device is limited functionality, because the device does not allow the formation of estimates of the results of the operation of ranking filtering.

 The aim of the invention is the expansion of functionality by forming estimates of the values of the results of the operation of ranking filtering.

блока элементов задержки соединены с соответствующими входами i-го бинарного рангового фильтра, выход которого соединен с входом второго преобразователя кодов, выход которого является выходом устройства, тактовые входы блоков элементов задержки объединены и соединены с тактовым входом устройства.This goal is achieved by the fact that the first and second code converters, a group of delay elements, all delay elements are combined into K blocks of delay elements, K binary rank filters, where K is the number of reference elements, are introduced into the device for ranking filtering of structural signals containing three delay elements signs, moreover, the information input of the device is connected to the input of the first code converter, the corresponding outputs of which are connected to the inputs of the corresponding blocks of delay elements, the outputs of the ith

the block of delay elements are connected to the corresponding inputs of the i-th binary rank filter, the output of which is connected to the input of the second code converter, the output of which is the output of the device, the clock inputs of the blocks of delay elements are combined and connected to the clock input of the device.

 Comparative analysis with the prototype shows that the claimed device is distinguished by the presence of new blocks: two code converters, k blocks of delay elements and k binary rank filters, as well as their interconnections.

 Thus, the proposed device meets the criterion of `` Novelty. ''

 A block of delay elements can be implemented as a series connection of the corresponding number of delay elements per one clock cycle or as a shift register of the corresponding length.

 As delay elements for one clock cycle, parallel registers or shift registers on MS triggers, which are widely known, can be used. A binary rank filter can be implemented as a block of read-only memory, in the cells of which the table computes the results of the addition function and then compares the result with a threshold. A binary rank filter can be implemented as a block of read-only memory, in the cells of which the table computes the results of the addition function and then compares the result with a threshold. A binary rank filter can also be implemented as a serial connection of a read-only memory block, in the cells of which a tabular calculation of the results of the function of adding values at its inputs and a comparator that implements the comparison operation is implemented.

 In FIG. 1 presents a block diagram of the inventive device; in FIG. 2 is a diagram of a block of delay elements for a neighborhood, where τ is a delay element for one clock cycle of the device, 3x3 element sizes figure 3 an example of a possible implementation of a binary rank filter using a multi-input adder (implemented as a ROM unit) and a comparator.

 The device contains a code converter 1, blocks 2.1, 2.2, 2.K of delay elements, binary rank filters 3.1, 3.2. 3.K, second code converter 4, information input 5 of the device, clock input 6 of the device, output 7 of the device.

преобразователя 1 кодов соединен с входом блока 2.i элементов задержки. Выходы блока 2.i элементов задержки соединены с входами бинарного рангового фильтра 3.i. Выход бинарного рангового фильтра 3.i соединен с i-ым входом преобразователя 4 кодов. Выход преобразователя 4 кодов является выходом 7 устройства. Тактовые входы блоков 2.1, 2.2,2.k элементов задержки объединены и соединены с тактовым входом в устройства.Information input 5 of the device is connected to the input of the converter 1 codes, i-th output

code converter 1 is connected to the input of delay element block 2.i. The outputs of the delay element block 2.i are connected to the inputs of the binary rank filter 3.i. The output of the binary rank filter 3.i is connected to the i-th input of the code converter 4. The output of the converter 4 codes is the output 7 of the device. The clock inputs of blocks 2.1, 2.2,2.k of the delay elements are combined and connected to the clock input of the device.

 Before starting the presentation of the principles of operation of the device, it is advisable to consider the following.

 The device is designed to generate estimates of the value of local ordinal statistics for structural signals. A structural signal is a set of extended sections characterized by approximately the same signal value; at the boundaries of the sections, a sharp abrupt change in the signal value occurs. An example of a two-dimensional structural signal is an image, in particular a television image.

The device implements the calculation of estimates of the values of the results of the ranking filtering operation: in each step of the operation, an estimate of γ _{k of the} value of R _{k of the} kth ordinal statistics for the current local neighborhood Q is formed.

The device implements the calculation of a function of the form
γ _k = ν ₁ • a _k + ν ₂ • b _k (1)
where γ _{k is the} estimate of the value of the kth ordinal statistics for the current local neighborhood (set);
a _{k an} estimate of the maximum possible value of the k-th local order statistics for the current local neighborhood Q;
b _{k an} estimate of the minimum possible value of the k-th local order statistics for the current local neighborhood Q;
ν ₁ and ν ₂ weights.

Значения a_k и b_k определяются следующим образом:

где α_j значение j-го разряда оценки a_k;
α_j ∈ {0, 1};
β_j значение j-го разряда оценки b_k;
β_j ∈ {0, 1};
P разность оценок a_k и b_k.ν ₁ and ν ₂ are defined as follows:

The values of a _k and b _{k are} defined as follows:

where α _{j is the} value of the jth digit of the estimate a _k ;
α _j ∈ {0, 1};
β _{j the} value of the jth digit of the estimate b _k ;
β _j ∈ {0, 1};
P is the difference between the estimates a _k and b _k .

где

-количество чисел X_i в множестве Q, для которых выполняется условие: в j старших разрядов числа x_i есть хотя бы одна единица;
s_j количество чисел X_i в множестве Q, значение j-го разряда у которых равно единице (не равно нулю);
N количество чисел в множестве Q;
k номер искомой порядковой статистики.The values of α _j and β _{j of the} jth digits of numbers (estimates) a _k and b _{k are} determined from the expressions

Where

- the number of numbers X _i in the set Q for which the condition is fulfilled: in j high digits of the number x _i there is at least one unit;
s _{j is the} number of numbers X _i in the set Q, the value of the jth digit of which is equal to one (not equal to zero);
N is the number of numbers in the set Q;
k is the number of the desired ordinal statistics.

где h₁(x_i;j) признак наличия в j-ом разряде числа x_i единицы;
h₂(x_i;j) признак наличия в j-старших разрядах числа x_i хотя бы одной единицы.

where h ₁ (x _{i; j} ) is a sign of the presence in the jth digit of the number x _i units;
h ₂ (x _{i; j} ) is a sign of the presence in the j-most significant digits of the number x _{i of} at least one unit.

где τ $\genfrac{}{}{0ex}{}{\text{j}}{\text{i/}}$ содержимое j-го разряда числа x_i

.

where τ $\genfrac{}{}{0ex}{}{\text{j}}{\text{i /}}$ the contents of the jth digit of the number x _i

.

Устройство работает следующим образом.Example. Let the current local neighborhood Q contain 5 (N = 5) four-digit numbers (P = 4):
Q14, 13, 14,3,2}
Based on the procedure described in (1) (10), we have the values of the estimates for the corresponding ordinal statistics:

The device operates as follows.

признаков наличия единиц в соответствующих разрядах числа x_i, которые затем поступают на соответствующие выходы преобразователя 1 кодов. Значения признаков h₁(x_i;j) и h₂(x_i;j) с соответствующих выходов преобразователя 1 кодов поступают на входы блоков 2.1, 2.2, 2.К элементов задержки (К=2р). Блок 2. m

элементов задержки представляет собой последовательное соединение элементов задержки на один такт работы. В блоке 2.m элементов задержки осуществляется задержка на заданное количество тактов работы значений, поступивших ранее в предшествующих тактах работы на вход блока 2.m.In the current i-th operation cycle, the P-bit parallel code of the current sample x _{i of the} signal from the information input 5 of the device is input to the first code converter 1. In the code converter 1, tabular formation of the corresponding values of h ₁ (x _{i; j} ) and h ₂ (x _{i; j} ) is carried out

signs of the presence of units in the corresponding digits of the number x _i , which then go to the corresponding outputs of the converter 1 codes. The values of the signs h ₁ (x _{i; j} ) and h ₂ (x _{i; j} ) from the corresponding outputs of the converter 1 of the codes are fed to the inputs of blocks 2.1, 2.2, 2.K delay elements (K = 2p). Block 2. m

delay elements is a series connection of delay elements for one clock cycle. In block 2.m of delay elements, a delay is carried out for a given number of clock cycles of the values received earlier in the previous clock cycles at the input of block 2.m.

The outputs of the delay element block 2.m are connected to the outputs of the corresponding delay elements by one clock cycle. In each operation cycle, at the corresponding outputs of block 2.m, values of the corresponding attribute delayed by the corresponding number of operation cycles are generated for all samples belonging to the current local neighborhood. In the current cycle, at the corresponding outputs of block 2.m, the values of the corresponding attribute are generated for all samples x _j falling in the current local neighborhood Q with a central sample x _i , and then they are sent to the corresponding inputs of the binary rank filter 3. m. In the binary rank filter 3.m, at the inputs of which the values of the corresponding attributes are received, a tabular calculation of the value of the corresponding discharge of one of the estimates (a _k and b _k ) according to expressions (5) (8) is implemented. In other words, in a binary rank filter 3.m, the values received at its inputs are summed up and compared with a predetermined threshold value and a sign of the comparison result is sent to the output of the filter 3.m.

для заданной порядковой статистики. Значения α_j и β_j с выходов бинарных ранговых фильтров 3.1, 3.2,3.К поступают на соответствующие входы преобразователя 4 кодов. В преобразователе 4 кодов реализуется табличное формирование согласно (1), (3), (4) на основе полученных значений α_j и β_j значения γ_k заданной k-й локальной порядковой статистики. Значение γ_k с выхода преобразователя 4 кодов поступает на выход 7 устройства. С приходом очередного тактового импульса в блоках 2.1, 2.2,2.К элементов задержки осуществляется прием информации (по переднему фронту тактового импульса) и ее сдвиг (по заднему фронту тактового импульса), на информационном входе 5 устройства формируется параллельный код следующего отсчета x_i+1 сигнала и начинается следующий такт работы устройства.Thus, at the outputs of binary rank filters 3.1, 3.2, 3.K, values are formed, according to (5) and (6)

for a given ordinal statistics. The values of α _j and β _j from the outputs of the binary rank filters 3.1, 3.2,3. K go to the corresponding inputs of the converter 4 codes. In the code converter 4, tabular formation is implemented according to (1), (3), (4) based on the obtained values of α _j and β _{j of the} value γ _{k of the} given k-th local ordinal statistics. The value of γ _k from the output of the converter 4 codes goes to the output 7 of the device. With the arrival of the next clock pulse in blocks 2.1, 2.2.2. To the delay elements, information is received (along the leading edge of the clock pulse) and its shift (along the falling edge of the clock pulse), a parallel code of the next sample x _{i +} is generated at the information input 5 of the device ₁ signal and the next cycle of the device starts.

The device operates in parallel mode (calculation on the sides 2.1.2.K, 3.1.3K is carried out in parallel) and at each work step, the output γ 7 will generate the value γ _{k of the} specified k-th local ordinal statistics for the current moving neighborhood.

 The proposed device allows you to generate estimates of the values of the specified local ordinal statistics for one-dimensional and two-dimensional structural signals. This allows you to expand the functionality of the device and expand its scope.

 The device operates in parallel mode and has high speed. This allows its use in specialized systems for processing structural signals in real time, for example, in automated image processing systems.

 The proposed economic effect is to expand the functionality of the device and its scope, as well as to save machine time.

Claims (1)

 A device for ranking filtering of structural signals containing three delay elements, the clock inputs of which are connected to the clock input of the device, characterized in that the first and second code converters, groups of K3 delay elements are introduced into it, and all delay elements are combined into a block consisting of from K delay elements, K binary rank filters (where K is the number of controversial features), and the information input of the device is connected to the input of the first code converter, the i-th output of which is connected to the input, respectively of the existing block delay element, the outputs of the ith (i 1, K) block delay element are connected to the inputs of the i-th binary rank filter, the output of which is connected to the i-th input of the second code converter, the output of which is the output of the device, the clock inputs of the elements with fourth on the K-th delay block combined and connected to the clock input of the device.

Images