JP3049962B2 - Stack filter - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION The present invention relates to a television or V
The present invention relates to a non-linear filter, particularly a stack filter, used for noise reduction in a video device such as a TR or a video camera.

[0002]

2. Description of the Related Art In recent years, a stack filter, which is a new processing form of a nonlinear digital filter represented by a median filter, has been proposed (for example, IEEE Trans. Acoust., Speech, Signal).
Process. ASSP-34, 898-911, 1986).

[0003] The processing of the stack filter will be briefly described below. Here, as an example, a description will be given of a process in which a stack filter having a window width (the number of data to be processed) of 3 realizes the characteristics of a median filter. FIG.
FIG. 3 is a block diagram showing a basic configuration of a stack filter. 6 and 7 show an outline of the processing.

First, the outline of the processing of the stack filter will be described first with reference to FIGS. In the figure, the processing by the conventional median filter is shown along the path of the thick arrow in the figure.

In the conventional processing, a data string (here, 2-bit data) shown as an input at the upper left of FIG.
The data string passes through the median filter shown at the top and becomes a data string shown as an output at the top right. Since the window width of this filter is 3, the filter outputs the second largest value for three input data.

When this processing is performed by a stack filter, the processing is performed along a path indicated by a thin arrow in the figure.

First, since the input data string is 2 bits, the possible values of the data are four levels. Of these, the input data value is observed at each level except 0, and a 1-bit data string is created using the observation level as a threshold.
The reason for excluding 0 is that even if this processing is performed at level 0, the resulting data string is all "1" and has no information.

This will be described with reference to FIG. As shown in the figure, when data having values of 1, 3, and 2 is input, first, the level of 1 is set as a threshold, and if the value of the input data is equal to or greater than the threshold, it is "1"; Data sequence (1,1,1)
Get. Similarly, a data string (0,1,1) is obtained using the level 2 as a threshold, and a data string (0,1,0) is obtained using the level 3 as a threshold. Hereinafter, this processing is referred to as decomposition processing.

As described above, the three types of data strings decomposed into 1 bit on each level are respectively passed through binary filters represented by Boolean algebra as shown in FIG. 6 to obtain 1-bit output data strings. Here, since a median filter is configured, the transfer function of the binary filter is such that the three input data are x ₁ , x _1
2 , x ₃

[0010]

(Equation 1)

It is assumed that In the above formula, “•” is a logical product,
“+” Represents a logical sum. In a stack filter, the transfer function of the filter is thus simplified.

In the conventional median filter, a sorting process for rearranging data in a large order was necessary, so that the circuit had to be complicated. However, if a stack filter process is performed, a transfer function can be realized by hardware. Becomes easier.

Finally, a 2-bit output data string is obtained by adding all the outputs of the respective binary filters. Hereinafter, this process is referred to as a combining process. The result is equal to the result of the path along the thick arrow in the figure.

The processing method using the stack filter has been described above. To perform this processing, the transfer function of the binary filter needs to satisfy certain conditions. Next, this point will be described.

As shown in FIG. 6, the input data is divided into a plurality of 1-bit data strings by the decomposition process in the stack filter. It can be found that there is a row of “0” above a row of “1” as shown in FIG. For example, when the input data value is 2, the decomposition result is "1" up to level 2 and "0" at level 3.

This is a natural consequence, but it must be noted that this property must also be maintained at the output of the binary filter.

For simplicity of description, this is represented by a mathematical expression.
I do. Input data string z₁, z_Two, ..., z _n2 different for
Two levels L₁And L_TwoThe result of the decomposition above

[0018]

(Equation 2)

And

[0020]

(Equation 3)

It is assumed that Now, for all k where 1 ≦ k ≦ n,

[0022]

(Equation 4)

When the following holds,

[0024]

(Equation 5)

Will be described. Using this, the property described above becomes

[0026]

(Equation 6)

Can be expressed as Where the binner
Let the refilter transfer function be S_(・)And the output is S_(x)You
And S _(y)In the expression, S_(x)And S_(y)Do not hold between
The property that must be

[0028]

(Equation 7)

Therefore, the following condition is derived from (Equation 6) and (Equation 7).

[0030]

(Equation 8)

After all, the transfer function S _{(·) of the} binary filter
Is required to satisfy the condition (8). The transfer function having such properties is
It is known that none of the product terms contain negation.

If the above processing is performed faithfully, a hardware configuration as shown in FIG. 5 is required.

FIG. 5 is a block diagram showing a configuration when input data is 8-bit data.

The serial-parallel conversion means 1 synchronizes three data input from the input terminal 8. Vector generation means 4
-1 to 4-255 decompose the output of the serial-parallel conversion means 1 at each level from 1 to 255,
Is generated. This can be regarded as a three-dimensional vector having binary elements.

The binary filters 5-1 to 5-255 perform, for example, an operation as shown in (Equation 1) on the output vectors of the vector generating means 4-1 to 4-255.

The adder 19 performs a synthesizing process on the output values of all the binary filters to obtain an output.

[0037]

However, in the above-described method, the above-described decomposition and combination processing does not cause much problem if the input data is 2 to 3 bits. However, as shown in FIG. For data, 255 vector generation means and binary filters are required, which is impractical.

An object of the present invention is to solve the above-mentioned conventional problems, and an object of the present invention is to provide a stack filter for performing practical decomposition / synthesis processing.

[0039]

In order to achieve this object, a stack filter according to the present invention comprises a serial-parallel conversion means for converting n (n ≧ 3) serial data into parallel data from an input signal; Of the n outputs of the serial-parallel conversion means,
Removed phase two different was magnitude comparison, and _n C ₂ pieces of magnitude comparator for generating a comparison signal, said _n C ₂ pieces of magnitude comparator
Select (n-1) different outputs from each output,
generate a vector composed of n binary components
That the n vectors generating means, with respect to n components of each vector outputted from the n vector generation means, 1
N filter means for performing a logical AND operation of bits, and n vectors which are the output of the n vector generation means under the condition that the outputs of the n filter means become a predetermined value. Among them, a minimum value detector that detects a minimum value and outputs a detection signal, and one of the n outputs of the serial / parallel conversion means corresponding to the output of the minimum value detector It has a configuration with selection means for selecting and outputting an output.

[0040]

According to the present invention, with the above-described configuration, the magnitude comparison is performed between two different data, and a minimum necessary binary data sequence is obtained using the result, and these data sequences are passed through a binary filter. After that, the output level of the binary filter is to be 1 and the resolution level which generates the data string having the maximum number of 0 is obtained and output.

[0041]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing a stack filter having a window width of 3 (ie, n = 3) according to a first embodiment of the present invention.

First, the concept of the decomposition process in the present invention will be described first. Now, since the window width is 3, input data as shown in FIG. 2 is considered. Data and x _1, x _2, x ₃ from temporally older, the value is set to m _1, m _2, m _3, respectively. However,

[0044]

(Equation 9)

Is as follows. If this data string is decomposed on an arbitrary level L (1 ≦ L ≦ 255), the obtained 1
The bit data sequence is as follows.

[0046]

(Equation 10)

That is, no matter how many bits of input data are, if the window width is 3, there are at most four types of data strings obtained as a result of the decomposition. In addition, the first data string (0, 0, 0) is not required in the synthesizing process as described above, so that only the three types of data strings need to be processed. Therefore, three binary filters are sufficient.

Next, a process for obtaining the above three types of data strings will be described. Looking at the point at which changes the data string is changed from 1 to 255 L, and the between m ₁ and m ₁ +1, between m ₂ and m ₂ +1, and m is between ₃ and m ₃ +1. This is level m
Performing decomposition on ₁ , m ₂ and m ₃ means that all necessary data strings can be obtained. That is, the input 3
That is, it is only necessary to create a data string using the values of two data as thresholds.

This will be specifically described with reference to FIG. The data input from the input terminal 8 becomes _three parallel data x ₁ , x ₂ , x _{3 in the} serial-parallel converter 1.

The first magnitude comparator 3a compares the magnitudes of x ₁ and x ₂ , and compares the magnitudes of x ₁ with a threshold level (“1” if x ₂ ≧ x ₁ and x ₂ <x ₁ and simultaneously outputs if "0") if the first vector generating means 4a as a _12, a comparison result a ₂₁ in which the x ₂ and threshold level, and outputs the second vector generating means 4b.

[0051] Similarly, the second the magnitude comparator 3b performs magnitude comparison between x ₁ and x _3, the comparison result a ₁₃ in which the x ₁ and threshold level to the first vector generating means 4a, x ₃ the threshold level and it outputs the comparison result a ₃₁ which is the third vector generation means 4c and.

Similarly, the third magnitude comparator 3c compares magnitudes of x ₂ and x ₃ , and compares the comparison result a ₂₃ with x ₂ as a threshold level to the second vector generation means 4b, and outputs x ₃ to x _3.
And outputs the comparison result a ₃₂ which are used as threshold levels to a third vector generation means 4c. As described above, n = 3
In the case, ₃ C ₂ = 3 magnitude comparators 3a, 3b, 3c
It may be provided. That is, when the window width is n (n ≧ 3), n
Select two data from the data and compare the size
In, the required amount of _n C ₂ pieces of magnitude comparator of the combination
Become.

The first vector generating means 4a outputs the outputs a ₁₂ and a _{13 of} the first and second magnitude comparators 3a and 3b.
Thus, a three-element vector is generated.

When the above operation is applied to the case where the data shown in FIG. 2 is input, x ₂ and x ₃ are both x ₁
Since it is larger, a ₁₂ and a ₁₃ both become “1”.

Now, suppose that the above-mentioned magnitude comparison is performed for x ₁ and x ₁ and the result is expressed as a _11.
Since ₁₁ is naturally "1", vector generated _{(a 11, a 1 2,} a 13) is

[0056]

[Equation 11]

Is as follows. This is an exploded results on the level m _1. The generated vector is output to the first binary filter 5a and the minimum value detector 6.

[0058] Similarly, in the second and third vector generation means 4b and 4c, respectively Level m ₂ on the decomposition result _{(a 21, a 22, a} 23) and m ₃ on the decomposition result (a _31, a ₃₂ , a ₃₃ )

[0059]

(Equation 12)

Is obtained. These vectors are also the second
And the third binary filters 5b and 5c, and at the same time, to the minimum value detector 6.

First to third binary filters 5a to 5c
In, an arithmetic process represented by a 1-bit logical sum is performed. FIG. 3 shows a specific example of the binary filter having the transfer function of (Equation 1). This will be described in more detail. For example, when (a ₁₁ , a ₁₂ , a ₁₃ ) is substituted into (Equation 1), as described above, a ₁₁ is “1”.

[0062]

(Equation 13)

Thus, it can be constituted only by the OR circuit 11-1. Similarly, (a ₂₁ , a ₂₂ , a ₂₃ ) and (a ₃₁ , a ₃₂ ,
a ₃₃ ), the OR circuits 11-2 and 11-2
It can be composed of only -3.

If the transfer function of the binary filter is a median filter as shown in (Equation 1), the output values S _{1 to} S ₃ of the _first to third binary filters 5a to 5c are respectively

[0065]

[Equation 14]

Is obtained. Here, considering (Equation 10),
Since it can be seen that the output value of the binary filter is 0 for a data string decomposed on an arbitrary level L satisfying m ₂ <L ≦ 255 and m ₃ <L ≦ m _2, a value between the decomposition level L and the filter output is obtained. The following equation holds.

[0067]

(Equation 15)

This is supported by (Equation 8). The output of each binary filter is output to the minimum value detector 6.

In the minimum value detector 6, among the output vectors of the first to third vector generating means 4a to 4c, the output vectors of the first to third binary filters 5a to 5c become "1". To detect the one having the smallest size, and output a detection signal to the selection means 7. Here, the algorithm will be described. In the original method, all the output values of the binary filter are added and output. In this case, the sum of m ₃ “1” s from level 1 to m ₃ , that is, m ₃ is the sum of the synthesis result and Become. Since m ₁ <m ₃ <m ₂ , it can be seen that this stack filter operates as a median filter.

However, paying attention to (Equation 15), in order to obtain a synthesis result, the maximum decomposition level (m _{3 in this} case) that gives a data string in which the output result of the binary filter is “1” is given. It turns out that it suffices to find it.

How to determine this level will be described below. First, all data strings in which the output of the binary filter becomes “1” are obtained. In this case, (0,1,1) and (1,1 ,,
1).

If the largest number of "0" is obtained, the decomposition level for providing the data string becomes the required level. In this case, since the maximum number of “0” is (0, 1, 1), the decomposition level that gives this is m
It becomes ₃ .

Since m ₃ is the value of the input data x ₃ , a composite output can be obtained by using x ₃ itself as the output value.

The above algorithm is arranged and rewritten.
The data strings on the decomposition levels m ₁ , m ₂ , and m ₃ are represented by y ₁ ,
y ₂ , y ₃ , that is,

[0075]

(Equation 16)

Are represented as follows. Further, representative of the output value of the binary filter for the y _1, y _2, y ₃ and S _1, S _2, S _3, respectively. At this time, (a) First, if S ₁ = 1, the provisional output value is set to x ₁ . S ₁
= 0, then remove the x ₁ from the output value candidate.

(B) Next, if S ₂ = 1, y ₁ and y ₂ are compared. If y _{2 has} a larger number of “0” s, the provisional output value is x ₂
And If S ₂ = 0, x ₂ is excluded from output value candidates.

(C) Further, if S ₃ = 1, y ₁ and y ₃ or y ₂ and y ₃ are compared. If y _{3 has} a larger number of “0” s, the provisional output value is x ₃ . . If S ₃ = 0, x ₃ is excluded from the output value candidates.

(D) The final provisional output value is output as a result of the processing of (a) to (c). Based on the above algorithm, one of the three outputs of the serial-parallel converter 1 is selected by the selection means 7 and the output terminal 9
Output to

FIG. 4 shows a specific circuit for realizing the above algorithm. The output signal S _{1 of} the first binary filter 5a is input to the NAND circuit 12, and when S ₁ = 1, the values of S ₂ and S ₃ are checked. If S ₂ = 1, y ₁ and y ₂
Are compared, and if S ₃ = 1, y ₁ and y ₃ are compared.

As described in the description of the decomposition processing, for example, between y ₁ and y ₂

[0082]

[Equation 17]

Since the relationship holds, the condition that is satisfied when the number of “0” s is larger in y ₂ than in y ₁ is as follows:

[0084]

(Equation 18)

Is as follows. However, considering that a ₁₁ and a ₂₂ are always “1”, the second condition in the above equation does not hold, so

[0086]

[Equation 19]

This can be simplified as follows. This condition is the AND circuit 10
-1 and the OR circuit 11-4. Therefore, S
If (Equation 19) holds when ₂ = 1, the AND circuit 10-4 outputs "H".

Similarly, in comparing y ₁ and y ₃ ,

[0089]

(Equation 20)

[0090] if the following condition is satisfied, more than y ₁ of y ₃ is that the number of "0" is large. This condition is AND circuit 1
0-2 and the OR circuit 11-5. Therefore,
If (Equation 20) is satisfied with S ₃ = 1, the AND circuit 10-5 outputs “H”.

S ₁ = 1 and AND circuits 10-4 and 1
0-5 NAND circuit 12 when the output is "L" of the outputs "L", the switching selection means 7-1 to the "L" side, and selects and outputs the x _1.

When S ₁ = 0, or when the output of the AND circuit 10-4 or 10-5 is "H", the NAND circuit 12 outputs "H" and sets the selection means 7-1 to the "H" side. Switch to
Remove the x ₁ from the output value candidate.

The case where x ₁ is out of the output value candidates will be described below. First, if S ₂ = 1, the value of S ₃ is checked in the same manner, and S ₃ =
1, then performs a comparison of y ₂ and y _3.

[0094]

(Equation 21)

[0095] if the following condition is satisfied, more than y ₂ of y ₃ is that the number of "0" is large. This condition is AND circuit 1
0-3 and the OR circuit 11-6. Therefore,
If (Equation 21) holds when S ₃ = 1, the AND circuit 10-6 outputs “H”.

When S ₂ = 1 and the output of the AND circuit 10-6 is “L”, the NAND circuit 13 outputs “L”, switches the selection means 7-2 to the “L” side, and sets x ₂ Select and output.

[0097] S ₂ = 0 or, when the output of the AND circuit 10-6 is at "H", NAND circuit 13 outputs "H", the switching selection means 7-2 to the "H" side, the x ₃ Select and output.

As a result, among the outputs of the first to third vector generating means, the vector having the largest number of zeros among the vectors for which the output value of the binary filter is "1" is detected, and the vector is generated. Level can be determined.

As described above, in the present invention, as shown in the embodiments,
Even for 8-bit data, a stack filter can be configured with a relatively small amount of hardware.

In the present embodiment, the transfer function of the binary filter is represented by (Equation 1) taking a median filter as an example. However, when realizing another characteristic, as described in the section of the conventional example, If the expression does not include a negation in any product terms,
The above argument holds similarly.

[0101]

The present invention as described above, according to the present invention includes a serial-parallel conversion unit, and _n C ₂ pieces of magnitude comparator includes n vector generation means includes n filter means, and a minimum value detector, And selecting means for performing magnitude comparison between two different data,
Using the result, a minimum required binary data string is obtained, and after passing these data strings through a binary filter, a data string having the largest number of zeros among the ones whose output value of the binary filter becomes 1 is generated. By obtaining and outputting the decomposition level to be performed, a stack filter using relatively small-scale hardware can be realized, and the implementation effect is large.

[Brief description of the drawings]

FIG. 1 is a block diagram showing a configuration of a stack filter according to an embodiment of the present invention.

FIG. 2 is a schematic diagram for explaining processing in FIG. 1;

FIG. 3 is a logic circuit diagram showing an example of a binary filter in FIG. 1;

FIG. 4 is a block diagram illustrating an example of a synthesis processing circuit.

FIG. 5 is a block diagram showing a configuration of a conventional stack filter.

FIG. 6 is a schematic diagram showing an outline of processing of a conventional stack filter.

FIG. 7 is a schematic diagram for explaining the concept of decomposition processing in a conventional stack filter.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 Serial-parallel conversion means 3 Large-small comparator 4 Vector generation means 5 Binary filter 6 Minimum value detector 7 Selection means

──────────────────────────────────────────────────続 き Continuation of front page (56) References JP-A-57-155671 (JP, A) JP-A-2-29020 (JP, A) JP-A-2-150113 (JP, A) JP-A-3-3 268604 (JP, A) JP-A-4-120981 (JP, A) JP-A-5-251998 (JP, A) JP-A-6-62284 (JP, A) (58) Fields investigated (Int. Cl. ⁷ , DB name) H03H 17/00 613 H03H 17/02 661 H03H 17/02 671 H04N 5/21

Claims (1)

(57) [Claims] 1. A serial-parallel converter for converting n (n ≧ 3) serial data into parallel data from an input signal, and extracting two different outputs from the n outputs of the serial-parallel converter. and compares Te, and _n C ₂ pieces of magnitude comparator for generating a comparison signal, among the output of said _n C ₂ pieces of magnitude comparator, different phases (n
-1) selecting n outputs, generating n vectors each composed of n binary components, n vector generating means, and n vectors of each vector output from the n vector generating means. N filter means for respectively performing a 1-bit AND operation on the binary component; and the n vector generation means under the condition that the output of the n filter means becomes a predetermined value. A minimum value detector for detecting a vector having a minimum size and outputting a detection signal among the n vectors as outputs, and n serial conversion circuits corresponding to the output of the minimum value detector. And a selecting unit for selecting and outputting one of the outputs of the stack filter, and using the output of the selecting unit as an output signal.