KR20020035203A - Discrete wavelet encoder using quadrature mirror filter - Google Patents

Abstract

PURPOSE: A discrete wavelet encoder using a quadrature mirror filter is provided to perform compression of images, which requires fast processing, with a small amount of calculations in real time. CONSTITUTION: A discrete wavelet encoder using a quadrature mirror filter includes an input controller(301), a vertical filter bank(307), a line memory(304), and a horizontal filter bank(308). The input controller down-samples an input signal into column and row components and outputs the components simultaneously. The vertical filter bank filters the column component signals and divides the signals into low-frequency and high-frequency signals. The line memory outputs the row component signals, output from the vertical filter bank, in parallel, and stores the filtered signals. The horizontal filter bank filters the row component signals and outputs the signals as signals having different frequency bands.

Description

Discrete Wavelet Encoder using Quadrature Mirror Filter

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to image compression, and more particularly, to a discrete wavelet encoder for transforming an image into three levels using a grid of symmetric filter filters.

Recently, as commercialization of high-speed video media has accelerated, interest in image compression has increased.

The main goal of image compression is the elimination of redundancy that exists in space with frame and frame-to-frame. As a video compression standard, DCT (Discrete Cosine Transform) of block unit is adopted as a method to remove spatial redundancy. The change, that is, the block effect, causes the deterioration of the image quality of the reconstructed image.

The wavelet change method has emerged as a method to solve the degradation of the picture quality. This method removes the block effect generated in the DCT on a block-by-block basis by applying filtering to the entire image and can perform encoding with a high compression rate. .

In general, the discrete wavelet transform, which is a subband decomposition of a tree structure, is a hierarchical signal conversion method. At each level, the number of filters is equal to the number of frequency bands, and filtering is performed with downsampling to match the number of frequency bands.

1 is a diagram illustrating a general structure of a wavelet filter bank divided into octave bands according to the related art.

FIG. 1 shows the function of a wavelet transform composed of three octaves, for example, a high pass filter h ₀ (101b or 103b or 105b), a low pass filter h ₁ (101a or 103a or 105a) at each level, The low band filter 102b or 104b or 106b and the high band filter 102a or 104a or 106a form one stage to convert an image signal input from the outside into an octave band at each stage.

First, the external input signal v ₃ passes through the low band filter 102b and the high band filter 102a with the down sampling ratio 2. In particular, the signal passing through the low-pass filter 102b in which the energy component is concentrated is repeatedly repeated with the high pass filter h ₀ 103b, the low pass filter h ₁ 103a, and the low pass filter 104b. Are converted into level 2 signals w ₁ and v ₁ by the high band filter 104a. Similarly, the signal passing through the low pass filter 104b is again and again repeated high pass filter h ₀ 105 b, low pass filter h ₁ 105 a, low band filter 106 b, and high band filter 106 a. Is converted into a level 3 signal (w ₀ and v ₀ ).

Here, the level 1 (w ₂ , v ₂ ), level 2 (w ₁ , v ₁ ), level 3 (w ₀ , v ₀ ), and level 4 signals representing the octave band are variable in number by user selection. .

As described above, the same process is repeated at level 2 and level 3, so that the resultant signal of level 3 is divided into octave bands w ₀ and v ₀ .

2 is a diagram showing a general structure of a wavelet filter bank synthesized in octave bands according to the prior art.

FIG. 2 illustrates a process of reconstructing the video signal decomposed in FIG. 1, wherein each level includes a low band filter 201b or 203b or 205b, a high band filter 201a or 203a or 205a, and a high pass filter. h ₀ (202b or 204b or 206b) and low pass filter h ₁ (202a or 204a or 206a) form one stage to restore the image signal input from the outside step by step.

First, at the level 3, the low band filter 201b and the octave band signals w ₀ ′, v ₀ ′ input to the high band filter 201 a are upsampled at a rate of up sampling 2, and then the high pass filter. 202b and the low pass filter 202a are filtered, synthesized, and passed to the next level stage. This process is repeated at level 2 and level 1 to generate a signal v ₃ 'similar to the original video signal.

In FIG. 1 and FIG. 2, the filter banks of each level are the same and used repeatedly.

The discrete wavelet transform in the prior art has a high operating speed in hardware to process a video compression that requires high-speed processing in real time due to the complexity of the conversion method. There is a problem that generates.

In addition, the discrete wavelet transform method of the direct method is composed of N _tab multipliers and adders (N _{tab: number} of taps of the filter). Thus, the filter configuration is redesigned when the filter length is changed. There is a problem that the implementation process is complicated.

Accordingly, an object of the present invention is to provide a discrete wavelet encoder which does not require a redesign of the filter when the filter length is changed by using a symmetric symmetric filter. .

It is another object of the present invention to provide a discrete wavelet coder that is suitable for real-time processing of image compression requiring high-speed processing with a small amount of computation using a lattice symmetric filter.

According to an apparatus feature of the present invention for achieving the above object, the input control unit for down-sampling the input signal to the row and column components and outputs at the same time, and filtering the signal of the column component of the simultaneous output signal, and low frequency A vertical filter bank for separating and outputting a signal and a high frequency signal, a line memory for outputting a planetary signal among signals output from the vertical filter bank in parallel, and storing a filtered signal for the thermal component; And a horizontal filter bank for filtering out the row component signals outputted as the signals and outputting them as signals having different frequency bands.

Preferably, the input control unit and the down-multiplexer for downsampling the input signal by switching to an even row and an even column, an even row and an odd column, an odd row and an even column, an odd row and an odd column according to the position of the row and column It is composed of an input delay unit for delaying and outputting the sampled signals simultaneously.

In addition, each of the vertical filter bank and the horizontal filter bank includes a distributed arithmetic filter unit including a plurality of distributed arithmetic filters for separating and filtering an input signal into even and odd columns, and a signal output from the plurality of distributed arithmetic filters. It is composed of an adder composed of a plurality of adders that generate components and low frequency components.

The variance filter includes a pre-stored filtering result value for all input signals according to filter coefficients, a filtering result value according to an arbitrary input signal, and a bit shifted output from the ROM before the arbitrary input signal. And a latch for accumulating a filtering result value that has been delayed by one clock, a latch for shifting the accumulated filtering result value inputted from the sensitizer by one bit to re-enter the sensator for each clock, and the most significant bit of the input signal. And a bit shifter for shifting the filtering result value obtained by subtracting the filtering result value from the accumulated filtering result value by n bits to output the final filtering value.

The ROM has only a molecular value excluding all denominators of the filter coefficients so as to perform an integer operation, and the filtering result of the input signal in all cases is converted into two's complement and stored in the ROM. In addition, the address area of the ROM in which the filtering result value is stored has a size of 2 ^{Ntab / 2 according to} the number of tabs N _tab of the vertical filter bank.

Each of the vertical filter bank and the horizontal filter bank is downsampled by 1/2.

The line memory is composed of _Nhtab / 2 stages according to the number of taps N _htab of the horizontal filter bank. The line memory includes a parallel shift register for shifting and storing a bit of a thermal component signal among signals output from the vertical filter bank. do. Therefore, the row component signals of the signals output from the vertical filter bank are separated and provided in parallel to the horizontal filter bank.

1 is a schematic structural diagram of a wavelet filter bank divided into octave bands according to the prior art;

2 is a schematic structural diagram of a wavelet filter bank synthesized in octave bands according to the prior art;

3 is a structural diagram of a discrete wavelet coder according to the present invention;

4 is a diagram showing the structure of a lattice filter bank (vertical filter bank or horizontal filter bank) applied to the present invention.

FIG. 5 is a diagram illustrating the structure of an input control unit illustrated in FIG. 3. FIG.

FIG. 6 is a diagram illustrating a structure diagram of a distributed computation filter unit illustrated in FIG. 3.

FIG. 7 is a structural diagram of the line memory shown in FIG. 3; FIG.

8 is a data flow diagram of a line memory according to the present invention;

* Description of the symbols for the main parts of the drawings *

301: input control unit

302,305: First and second distributed computation filter unit

303, 306: first and second adders

304: line memory

307: vertical filter bank

308: horizontal filter bank

In the present invention, a discrete wavelet coder using a lattice symmetric filter is proposed.

Hereinafter, a configuration and an operation according to an exemplary embodiment of the present invention will be described with reference to the accompanying drawings.

3 is a block diagram of a discrete wavelet encoder using a lattice symmetric filter according to the present invention.

Referring to FIG. 3, downsampling is performed by switching signals input from the outside with respect to rows (hereinafter, horizontal) and columns (hereinafter, vertical), and delays the downsampled signals to the next vertical filter bank 307. An input control unit 301 for simultaneous input, a vertical filter bank 307 for filtering vertical components of a signal input from the input control unit 301, and separating the filtered signal into a high frequency signal and a low frequency signal, and outputting the same; Line memory 304 for outputting the horizontal signals in parallel among the signals input from the vertical filter bank 307 to be input to the horizontal filter bank 308, and filtering the parallel component signals input in parallel. And a horizontal filter bank 308 that separates and outputs the filtered signal into a high frequency signal and a low frequency signal.

The vertical filter bank 307 is a first distributed operation filter unit 302 for filtering the vertical component of the down-sampled signal from the input control unit 301, and the filtered signal separated into a high frequency signal and a low frequency signal and output A first adder 303 is included.

The horizontal filter bank 308 includes a second distributed computation filter 305 for filtering horizontal components of an input signal input in parallel from the line memory 304, and converts the filtered signal into a high frequency signal and a low frequency signal. It is composed of a second adder 306 to separate and output.

In this configuration, the two-dimensional input signal input from the outside is switched to an even row and an even column, an even row and an odd column, an odd row and an even column, an odd row, and an odd column by the input control unit 301 to perform downsampling. The downsampled signals are delayed to be simultaneously input to the distributed computation filters 302a to 302d provided in the first distributed computation filter 302, respectively.

The distributed computation filters 302a to 302d of the first distributed computation filter 302 perform one-dimensional filtering on thermal components corresponding to vertical components among the downsampled signals from the outside. The filtered signals are respectively input to the adders 303a to 303d of the first adder 303, divided into high frequency components and low frequency components, and input to the line memory 304.

The line memory 304 outputs the row components corresponding to the horizontal components among the signals input from the adders 303a to 303d of the first adder 303 in parallel to the next horizontal filter bank 305. It is provided to the second dispersion calculation filter unit 305 provided in the.

The distributed computation filters 305a to 305d of the second distributed computation filter 305 filter signals in the one-dimensional row direction provided from the line memory 304. The filtered signals are separated into high frequency signals and low frequency signals by the adders 306a to 306d of the second adder 306 and output.

Each of the vertical filter bank 307 and the horizontal filter bank 308 shown in FIG. 3 performs filtering and signal separation according to the configuration principle as shown in FIG.

4 is a diagram showing a general structure diagram of a lattice filter bank (vertical filter bank or horizontal filter bank) applied to the present invention.

Referring to FIG. 4, a first filter unit 401 which separates an odd number signal and an even number signal of a downsampled input signal from the input control unit 301 and filters each signal, and the filtered signal A first adder 402 for separating and outputting a high frequency signal and a low frequency signal, a high frequency signal separated and output by the first adder 402, and a second filter unit 403 for filtering a low frequency signal; And a second adder 404 for outputting the high frequency signal filtered by the second filter unit 403 back to the high frequency signal and the low frequency signal, and outputting the low frequency signal to the high frequency signal and the low frequency signal.

The first filter unit 401 is configured by alternating even filters 401a and 401c and odd filters 401b and 401d to receive and filter the even and odd signals of the input data, respectively. The even-numbered signal is input to the even-numbered filters 401a and 403c, and the odd-numbered signal is input to the odd-numbered filters 401b and 401d.

The filtered signals are input to the first adder 402 including the adders 402a to 402d and output as high frequency signals and low frequency signals, respectively. The adders 402a to 402d add signals output from the even filter 401a or 401c and the odd filter 401b or 401d to generate a low frequency wave, thereby generating a high frequency wave.

The generated high frequency components and low frequency components are inputted to the second filter unit 403 including the even filters 403a and 403c and the odd filters 403b and 403d, respectively, and filtered again.

The filtered high frequency signal and the low frequency component are input to the second adder 404 including the adders 404a to 404d, and the low frequency component is again converted into the low frequency component LL and the low frequency component LH. The high frequency component is converted into a frequency band signal having four levels having a high frequency component (HL) and a high frequency component (HH).

As shown in FIG. 4, the lattice structure symmetric filter separately configures filters for receiving even and odd signals, and outputs the signals output from the filters as high frequency and low frequency components. Therefore, when the lattice symmetric filter is applied to the discrete wavelet coder according to the present invention, two-dimensional image data are separated into rows and columns to filter out a small amount of computation and output a desired number of frequency band signals. To do that.

The reason for this is generally divided into subbands using non-separated decomposition and separation decomposition. In the former case, quincunx and hexagonal downsampling are used to filter an image of size N × N to filter tap size L × L. In the case of N ² L ² , the latter requires 1-dimensional decomposition of the rows and columns of the image without analyzing the image signal two-dimensionally, and then downsampling and filtering are performed for each row and column. This is because a computation amount of 2N ² L is required, so a small computation amount is required. In addition to the reduction of the calculation amount, the hardware design of the small size can be easily performed.

FIG. 5 is a diagram illustrating a structure diagram of the input controller illustrated in FIG. 3.

Referring to FIG. 5, the input control unit 401 shown in FIG. 3 stores two-dimensional input data input from an external device evenly and evenly, evenly and evenly, oddly and evenly, oddly and evenly. A demultiplexer 501 for switching down to a column to perform downsampling, and delaying the downsampled signals, respectively, for each of the distributed arithmetic filters 302a through the first distributed arithmetic filter 302 shown in FIG. 3. And a delay unit 502 which is simultaneously input to 302d.

FIG. 6 is a diagram illustrating a structure diagram of the first and second distributed computation filter units illustrated in FIG. 3.

In FIG. 3, the first and second distributed calculation filters are each composed of four distributed calculation filters 302a to 302d and 305a to 305d, and each of the distributed calculation filters 302a to 302d and 305a to 305d. Is a ROM in which a filtering result value of a horizontal (row) component or a vertical (column) component of the input signal is stored in an area corresponding to an address of a value input from the input controller 301 shown in FIG. And a filter for adding a filtering result value output from the ROM 601 and accumulating a filtering result delayed by one clock after being outputted from the ROM 601 one bit shifted before the input value (ADD / SUB). 602, a latch 603 for delaying the accumulated filtering result output from the sensitizer 602 by one clock, and re-entering the sensitizer (ADD / SUB) 602, and the input signal Become the most significant bit (sign bit) (MSB), so that the filtering result has a negative value, and this negative filtering result The final filtered result value to be subtracted to the output value from the filtered result stacked n-bit-shifting by the bit-shifting is composed of 604 to output.

The ROM 601 is a storage device having a distributed computing structure. The ROM 601 stores preliminarily calculated filtering result values for all input signals for each filter coefficient value. Therefore, when 5 bits of input value are inputted from the input control part or line memory of FIG. 3, these 5 bits become an address of the ROM 601, and output the filtering result stored in this address area, and this output value is Passed through the sensitizer (ADD / SUB) 602, it is shifted one bit to the right by the latch 603 and re-entered into the sensitizer 602. Then, the filtering output value of the ROM 601 for the next input value and the clock delayed result value are added.

The process of adding the clock delayed value with the output of the next ROM 601 is repeated. Finally, when the most significant bit MSB (sign bit) of the input signal becomes the address of the ROM 601, the ADD / SUB In step 602, the difference from the previously accumulated values is output as a final filtering value by n-bit shifting by the bit shifter 604 as a final result, that is, a value for which filtering is completed.

In order to calculate the equation 3 by designing the ROM 601 according to the filter coefficients of the floating point in the ROM 601, a floating point operation must be performed. Designed.

For this purpose, the filtering result of the signal represented by the two's complement calculated in advance in consideration of the input signal in all cases with only the molecular value excluding the denominator of the filter coefficient is stored in the ROM 601. At this time, the address of the actual ROM 601 is 2 ^{Ntab / 2} (N _tab : the number of taps of the vertical filter bank) according to the number of taps of the symmetrical filter.

The general filter equation of the ROM 601 is as follows.

In Equation 1, C _k represents a filter coefficient and X _k represents a filtering result value.

When X _k is expressed as two's complement, Equation 2 is obtained.

In Equation 2 a _k0 denotes the most significant bit (sign bit) (MSB), wherein a _kn has a value of 0 or 1.

Substituting Equation 2 represented by the two's complement into Equation 1 is expressed as Equation 3, which is used to calculate a stored filtering result of the ROM 601 illustrated in FIG. 6.

=

FIG. 7 is a diagram illustrating a structure of the line memory illustrated in FIG. 3.

_Referring to FIG. 7, the line memory includes a parallel shift register composed of N _htab / 2 (N _htab : number of taps of a horizontal filter bank).

Thus, the parallel shift register includes a vertical filter bank output values derived from the filter that is, an even number column high-frequency component shown in Fig. 3 (H _{r, 2c)} and the low-frequency component (L _{r, 2c),} the odd-numbered column, the high-frequency component (H _{r, 2c + 1} ) and low frequency components (L _{r, 2c + 1} ).

The values of the first register of each stage, that is, the horizontal signals in the image, enter the input of the horizontal filter bank shown in FIG. 3 through the parallel data output. This process is shown through the internal data flow diagram of the line memory as shown in FIG.

8 is a flowchart illustrating an internal data flow of a line memory according to the present invention.

Referring to FIG. 8, signals of the high frequency and low frequency components of the column components inputted from the vertical filter bank illustrated in FIG. 3 are stored in the parallel shift register, and the row components are stored in the horizontal filter bank through the parallel data output. Is entered.

In FIG. 8, L _mn is a component that passes through the low pass filter of the vertical filter bank, and H _mn is a component that passes through the high pass filter. Where m is a row and n is a column.

As described above, in the present invention, since the discrete wavelet coder follows a distributed computation structure, the result value is stored in a ROM in advance without using a multiplier and processed in the same way as a multiplier, compared to a general FIR scheme. This has the effect of reducing the processing speed in filtering, which takes the most computation time in compression.

In addition, a structure that can adapt to changes in filter length provides an advantage for discrete wavelet coders according to the lattice structure.

In addition, the size of hardware that increases exponentially with each level can be reduced by repeatedly applying it.

When analyzing and implementing the video signal as a two-dimensional signal, a lot of hardware and computational amount is required. In this case, since the row and column of the image are designed by one-dimensional decomposition, the computational amount can be reduced and the filter can be easily and effectively designed. In addition, the structure of the one-dimensional filter is designed to adapt to the coefficients of the filter of different length using a distributed operation structure, and can reduce the amount of computation.

In addition, the discrete wavelet structure of the present invention can be effectively used not only for video compression but also for voice compression.

Those skilled in the art will appreciate that various changes and modifications can be made without departing from the spirit of the present invention.

Therefore, the technical scope of the present invention should not be limited to the contents described in the examples, but should be defined by the claims.

Claims (9)

An input controller which downsamples the input signal into row and column components and simultaneously outputs the input signal; A vertical filter bank for filtering a signal of a thermal component among the simultaneously output signals and separating and outputting the low frequency signal and the high frequency signal; A line memory for outputting a signal of a row component in parallel among the signals output from the vertical filter bank, and storing a filtered signal for the column component; And a horizontal filter bank for filtering the row component signals output in parallel and outputting them as signals having different frequency bands. The demultiplexer of claim 1, wherein the input control unit down-samples the input signal by switching the input signal to an even row and an even column, an even row and an odd column, an odd row and an even column, and an odd row and an odd column according to the position of the row and the column. A discrete wavelet encoder using a lattice structure symmetric filter, comprising: a delay unit and an input delay unit for delaying and outputting the downsampled signals. The method of claim 1, wherein the vertical filter bank, the horizontal filter bank A distributed arithmetic filter unit comprising a plurality of distributed arithmetic filter for separating and filtering an input signal into even and odd columns, and a plurality of adders for generating signals output from the plurality of distributed arithmetic filters with high frequency and low frequency components. Discrete wavelet encoder using a lattice symmetric filter, characterized in that the addition unit. The method of claim 3, wherein the dispersion calculation filter A ROM storing preliminary filtering result values for all input signals according to the filter coefficients; A sensitizer for accumulating a filtering result value according to an arbitrary input signal and a filtering result value output from the ROM before the random input signal and shifted by one bit and delayed by one clock; A latch shifting the accumulated filtering result value inputted from the sensitizer by one bit and re-entering the sensitizer every one clock; And a bit shifter for shifting the filtering result obtained by subtracting the filtering result value for the most significant bit of the input signal from the accumulated filtering result value by n bits and outputting the result as a final filtering value. Discrete Wavelet Coder Using Symmetric Filter. 5. The method of claim 4, wherein the ROM is converted to a two's complement and stored in the ROM by filtering the result of filtering the input signal in all cases with only the molecular values except for all the denominator values of the filter coefficients. Discrete Wavelet Coder Using Grid Symmetric Filter. 5. The discrete wavelet of claim 4, wherein the address region of the ROM storing the filtering result has a size of 2 ^{Ntab / 2 according to} the number of tabs (N _tab ) of the vertical filter bank. Encoder. 2. The discrete wavelet coder of claim 1, wherein the vertical filter bank and the horizontal filter bank are downsampled by 1/2. The method of claim 1, wherein the line memory It consists of _Nhtab / 2 stages according to the number of taps N _htab of the horizontal filter bank, and a parallel shift register for shifting and storing a bit of the thermal component signal of the signal output from the vertical filter bank by one bit Discrete wavelet coder using a lattice symmetric filter. The method of claim 1, wherein the line memory A discrete wavelet encoder using a lattice symmetric filter, characterized in that the row component signal of the signal output from the vertical filter bank is separated and provided to the horizontal filter bank in parallel.