KR100242635B1

Movatterモバイル変換

Info

Publication number: KR100242635B1
Application number: KR1019960001588A
Authority: KR
Inventors: 정제창; 전병우
Original assignee: 윤종용; 삼성전자주식회사
Priority date: 1996-01-25
Filing date: 1996-01-25
Publication date: 2000-02-01
Anticipated expiration: 2016-01-25
Also published as: CN1290067A; HK1033510A1; CN1179486C; CN1290069A; KR970060954A; MY118173A; HK1033508A1; GB9701440D0; HK1033509A1; CN1178396C; CN1652468A; GB2309613B; HK1033511A1; CN1290070A; GB2309613A; CN1290068A; CN1791218A; CN1178395C; CN100568742C

Abstract

Translated fromKorean

세그먼트들로 분할된 디지탈 데이터를 부호화 및 복호화하는 시스템은, 다양한 주사패턴들에 따라 세그먼트 데이터를 심볼들로 부호화하고, 가변장부호화된 데이터의 다양한 길이들을 적산하고, 최소의 적산된 길이에 대응하는 주사패턴을 선택하고, 선택된 주사패턴에 따라 부호화된 데이터를 저장 또는 전송하고, 부호화처리에 적용된 것과 동일한 주사패턴에 따라 전송되거나 복구된 데이터를 주사하여 주사된 데이터를 복호화한다. 그 결과, 데이터 압축 효율은 세그먼트 데이터의 부호화 및 복호화를 위하여 최적화된 주사패턴을 사용함으로써 개선될 수 있다.A system for encoding and decoding digital data divided into segments includes encoding segment data into symbols according to various scan patterns, integrating various lengths of variable length coded data, and corresponding to the minimum integrated length. The scanning pattern is selected, the data encoded according to the selected scanning pattern is stored or transmitted, and the scanned data is decoded by scanning the transmitted or recovered data according to the same scanning pattern applied to the encoding process. As a result, data compression efficiency can be improved by using an optimized scan pattern for encoding and decoding segment data.

Description

Translated fromKorean

가변장 부호화 및 가변장 복호화 시스템Variable length coding and variable length decoding system

제1도는 가변장 부호기를 이용하는 기존의 부호기의 실시예를 보여주는 블록도.1 is a block diagram showing an embodiment of a conventional encoder using a variable length encoder.

제2도는 가변장 복호기를 이용하는 기존의 복호기의 실시예를 보여주는 블록도.2 is a block diagram showing an embodiment of a conventional decoder using a variable length decoder.

제3(a)-3(c)도는 디지탈 데이터의 분할 뿐만 아니라 주사패턴 및 부호화처리를 위한 기존 방법의 예를 설명하기 위한 도면들.3 (a) -3 (c) are diagrams for explaining an example of an existing method for scanning pattern and encoding processing as well as division of digital data.

제3(d)-3(f)도는 다양한 대상물(object)들에 따른 디지탈 데이터의 분할 및 변환부호화를 위한 기존 방법의 다른 예를 설명하기 위한 도면들.3 (d) -3 (f) are diagrams for explaining another example of an existing method for dividing and transform encoding digital data according to various objects.

제3(g)도는 대상물에 따라 선택된 영상세그먼트의 본 발명에 따른 주사패턴의 일예를 보여주는 도면.3 (g) shows an example of a scanning pattern according to the present invention of an image segment selected according to an object.

제3(h)도는 POCS에 근거한 임의 모양변환의 흐름도.3 (h) is a flowchart of arbitrary shape transformation based on POCS.

제4도는 본 발명에 따른 가변장부호기의 실시예를 보여주는 블록도.4 is a block diagram showing an embodiment of a variable length encoder according to the present invention.

제5도는 본 발명에 따른 가변장복호기의 실시예를 보여주는 블록도.5 is a block diagram showing an embodiment of a variable length decoder according to the present invention.

제6(a)-6(c)도는 제4도 및 제5도에 관련하여 사용된 주사패턴들을 설명하기 위한 도면들.6 (a) -6 (c) are diagrams for explaining scan patterns used in connection with FIGS. 4 and 5;

제7(a)-7(c)도는 본 발명에 따른 다수 세그먼트들의 주사의 단순한 예들을 보여주는 도면들.7 (a) -7 (c) show simple examples of scanning of multiple segments according to the present invention.

제7(d)-7(e)도는 본 발명에 따른 다수의 세그먼트들을 위한 주사패턴의 단순한 예들을 보여주는 도면들.7 (d) -7 (e) show simple examples of scanning patterns for multiple segments according to the present invention.

* 도면의 주요부분에 대한 부호의 설명* Explanation of symbols for main parts of the drawings

41₁-41_N: 주사수단 CM₁-CM_N: 계수저장부41₁ -41_N : scanning means CM₁ -CM_N : coefficient storage

SAG₁-SAG_N: 주사번지출력부 VLC₁-VLC_N: 가변장부호기SAG₁ -SAG_N : Scanning address output part VLC₁ -VLC_N : Variable long code encoder

BF₁-BF_N: 버퍼 ACCM₁-ACCM_N: 적산기BF₁ -BF_N : Buffer ACCM₁ -ACCM_N : Totalizer

52 : 최소선택기 54 : 선택스위치52: minimum selector 54: selection switch

본 발명은 디지탈 데이터의 부호화 및 복호화 시스템에 관한 것으로, 보다 상세하게는, 다양한 주사패턴들중의 최적화된 주사패턴으로 기설정된 크기(size)의 디지탈 데이터를 부호화하며 부호화된 데이터를 복호화하여, 저장되거나 전송된 데이터의 압축을 더욱 개선한 부호화 및 복호화 시스템에 관한 것이다.The present invention relates to a system for encoding and decoding digital data, and more particularly, to encoding digital data having a predetermined size as an optimized scan pattern among various scan patterns, and decoding and storing encoded data. The present invention relates to an encoding and decoding system that further improves the compression of data transmitted or transmitted.

최근에, 비데오 및 오디오신호를 전송하거나 또는 저장매체에 저장할 디지탈 데이터로 부호화하며, 비데오신호 및 오디오신호를 재생하기 위하여 부호화된 디지탈 데이터를 복호화하는 다양한 방법이, 비데오신호 및 오디오신호를 전송 및 수신하기 위한 시스템에서 사용되었다. 그러나, 그러한 부호화 및 복호화 시스템에서의 데이터 전송효율을 증진시키기 위하여 전송데이터의 량을 더욱 압축하기 위한 기법이 요구되었다. 전송되거나 저장된 디지탈 데이터를 부호화하기 위한 방법들의 예로는 변환(transformation)부호화법, 차분펄스부호변조(Differential Pulse Code Modulation; DPCM)법, 벡터양자화법 및 가변장부호화법등이 있다. 이러한 부호화 방법들은 전송되거나 저장된 디지탈 데이터에 들어있는 여분의(redundant) 데이터를 제거하므로써 전체 데이터량을 압축한다.Recently, various methods of transmitting video and audio signals or encoding the digital data to be stored in a storage medium, and decoding the encoded digital data to reproduce the video and audio signals, transmit and receive video signals and audio signals. It was used in the system to However, in order to improve data transmission efficiency in such an encoding and decoding system, a technique for further compressing the amount of transmission data has been required. Examples of methods for encoding transmitted or stored digital data include transformation encoding, differential pulse code modulation (DPCM), vector quantization, and variable length encoding. These encoding methods compress the total amount of data by removing redundant data contained in transmitted or stored digital data.

MPEG-1이나 MPEG-2와 같은 기존 압축방식에서의 모든 처리는 8×8(또는 16×16)과 같은 일정크기의 사각형 블록을 기본단위로 처리되어 왔다. 본 발명은 영상처리가 블록에 제한되는 것이 아니라. 영상내 의미있는 객체(이하, 세그먼트라 함)별로 처리하는 것에 관계된다. 즉, 각 프레임의 비데오 데이터는 기설정된 크기(size)의 세그먼트(segment)로 분할되며, 비데오신호의 저장, 전송 및 수신을 위해 부호화 및 복호화 시스템에서 데이터 처리된다. 각 세그먼트 데이터 또는 세그먼트 데이터간의 차분데이타는 직교변환(orthogonal-transform)되어, 비데오 데이타가 주파수영역(frequency domain)의 변환계수들로 변환된다. 알려진 세그먼트 데이터 변환방법들로는, 이산코사인변환(Discrete Cosine Transform; DCT), 월시-하다마르변화(Walsh-Hadama rd Transform; WHT), 이산퓨리에변환(Discrete Fourier Transform; DFT) 및 이산사인변환(Discrete Sine Transform; DST)등이 있다. 이러한 변환방법들에 의해 얻어진 변환계수들은 계수데이타의 특성에 따라 적절히 부호화되어, 압축 효율이 증가된다. 인간의 시각적 인지(認知)는 고주파보다 저주파에 더욱 민감하므로, 고주파 데이터는 데이터처리에 의해 감소된다. 따라서, 부호화된 데이터의 량은 감소되어질 수 있다.All processing in the existing compression schemes such as MPEG-1 or MPEG-2 has been processed in a basic unit of a rectangular block of a certain size such as 8 × 8 (or 16 × 16). The present invention is not limited to the image processing block. This is related to processing by meaningful objects (hereinafter, referred to as segments) in the image. That is, the video data of each frame is divided into segments having a predetermined size, and are processed in an encoding and decoding system for storing, transmitting, and receiving video signals. Each segment data or difference data between the segment data is orthogonal-transformed so that the video data is transformed into transform coefficients of a frequency domain. Known segment data transformation methods include Discrete Cosine Transform (DCT), Walsh-Hadama rd Transform (WHT), Discrete Fourier Transform (DFT) and Discrete Sine Transform. Transform; DST). The conversion coefficients obtained by these conversion methods are properly coded according to the characteristics of the coefficient data, thereby increasing the compression efficiency. Since human visual perception is more sensitive to low frequencies than high frequencies, high frequency data is reduced by data processing. Thus, the amount of coded data can be reduced.

본 발명의 목적은 각 세그먼트의 데이터 분포특성에 따라 최적화된 주사패턴을 채용하여 그 세그먼트 데이터를 부호화하는 부호화시스템을 제공함에 있다.An object of the present invention is to provide an encoding system for encoding segment data by employing a scanning pattern optimized according to data distribution characteristics of each segment.

본 발명의 다른 목적은 각 세그먼트 데이터의 부호화 처리에서 선택된 것과 동일한 주사패턴에 따라 세그먼트 데이터를 복호화하는 복호화시스템을 제공함에 있다.Another object of the present invention is to provide a decoding system for decoding segment data according to the same scan pattern as selected in the encoding process of each segment data.

본 발명의 목적을 달성하기 위한, 세그먼트들로 분할된 디지탈 데이터를 부호화하기 위한 방법은, 다양한 주사패턴들에 따라 세그먼트데이터를 주사하며, 주사된 데이터를 다양한 주사패턴들에 따라서 개별적으로 부호화하는 단계; 부호화단계에서 부호화된 데이터를 다양한 주사패턴들에 따라 제각기(separately) 적산하는 단계; 다양한 주사패턴들에 따라 적산단계에서 얻어진 가변장부호화된 데이터의 길이들의 적산된 값들중에서 최소의 값에 대응하는 주사패턴을 선택하는 단계; 및 부호화단계에서 부호화된 데이터를 선택단계에서 선택된 주사패턴에 따라 저장데이터 또는 전송데이터로 선택하는 단계를 포함한다.In order to achieve the object of the present invention, a method for encoding digital data divided into segments, scanning the segment data according to various scan patterns, and separately encoding the scanned data according to various scan patterns ; Separately accumulating the data encoded in the encoding step according to various scan patterns; Selecting a scan pattern corresponding to a minimum value among integrated values of the lengths of the variable length coded data obtained in the integration step according to various scan patterns; And selecting the stored data or the transmission data according to the scanning pattern selected in the selecting step.

본 발명의 다른 목적을 달성하기 위한, 세그먼트들로 부호화된 데이터를 복호화하기 위한 방법은, 선택된 주사패턴에 대응하는 부호화된 데이터와 주사패턴데이터, 그리고 세그먼트데이타의 선택정보를 나타내는 제어신호를 수신 및 복구하는 단계; 입력되는 부호화된 데이터를 가변장복호화하는 단계; 입력 주사패턴데이터에 대응하는 기설정된 주사번지를 출력하는 단계; 복호화단계에서 복호화된 심볼들을 그 주사번지에 따라 복호화하여, 심볼들을 기설정된 계수들로 변환하는 단계를 포함한다.In order to achieve another object of the present invention, a method for decoding data encoded into segments includes receiving and transmitting a control signal representing encoded data and scan pattern data corresponding to the selected scan pattern, and selection information of the segment data. Recovering; Variable length decoding the input encoded data; Outputting a preset scan address corresponding to the input scan pattern data; And decoding the decoded symbols according to the scanning address to convert the symbols into predetermined coefficients.

이러한 발명은 전송되거나, 반도체메모리, 자기 테이프 또는 디스크, CD-ROM, 디지탈 비데오 디스크, 또는 다른 저장매체로 저장되거나 그것으로부터 복구되는 데이터의 부호화 그리고/또는 복호화를 위해 사용될 것이다.This invention will be used for the encoding and / or decoding of data transmitted or stored on or recovered from a semiconductor memory, magnetic tape or disk, CD-ROM, digital video disk, or other storage medium.

본 발명의 목적들 및 특징들은 첨부한 도면들과 함께 다음의 상세한 설명의 고찰을 통해 보다 명확해질 것이다.The objects and features of the present invention will become more apparent from a review of the following detailed description in conjunction with the accompanying drawings.

본 발명의 바람직한 실시예는 선행기술과 첨부된 도면들을 참조하며 가변장 부호화 방법을 일예로 하여 아래에서 설명될 것이다.A preferred embodiment of the present invention will be described below with reference to the prior art and the accompanying drawings, with an example of the variable length encoding method.

제1도는 가변장 부호화 방법을 사용하는 기존의 비데오데이터 부호화 장치의 블록도를 개략적으로 나타낸다. 입력단(10)은 블록(block)방식으로 분할된 영상세그먼트들에 대응하는 데이터 세그먼트들을 수신한다. 블록형 세그먼트들은 일반적으로 M₁×M₂치수(dimensions)로 표현되나, 설명의 편이를 위해 M₁=M₂=M인 경우로 가정한다. 입력단(10)을 통해 입력하는 블록형 세그먼트데이터는 제1가산기(A1)에서 기설정된 피드백 데이터에 가산되어, 두 세트(set)의 데이터(즉, 입력 데이터와 피드백 데이터)간의 차분데이타가 계산된다. 직교변환기(11)는 입력하는 차분데이타를 이산 코사인 변환하여, 차분데이타가 주파수영역의 계수들로 변환되게 한다. 양자화기(12)는 변환계수들을 기설정된 양자화 처리를 통해 다양한 레벨들의 대표값들로 변경한다. 그때에, 양자화기(12)는 직교변환기(11)로부터의 출력데이타를 버퍼(14)로부터 입력하는 양자화레벨(Q)에 따라 가변적으로 양자화한다. 가변장부호기(13)는 양자화계수들의 통계적 특성들을 고려하여 세그먼트데이타를 가변장 부호화하여, 압축된 데이터(V_CD)를 생성한다. 비데오 데이터에 대한 가변장 부호화 절차는 아래에서 설명될 것이다. 버퍼(14)는 가변장부호기(13)로부터의 압축된 데이터를 수신하며, 그 데이터를 일정한 율(rate)로 전송채널로 출력한다. 그때의 양자화레벨(Q)은 전송 데이터에서의 오버플로우(overflow)나 언더플로우(underflow)를 방지하기 위하여, 압축된 데이터량을 제어하기 위한 출력이 된다.1 schematically shows a block diagram of a conventional video data encoding apparatus using a variable length encoding method. The input terminal 10 receives data segments corresponding to image segments divided in a block manner. Block-type segments are generally expressed in M₁ x M₂ dimensions, but for ease of explanation, assume that M₁ = M₂ = M. The block-type segment data input through the input terminal 10 is added to the feedback data preset in the first adder A1, and difference data between two sets of data (ie, input data and feedback data) is calculated. . The quadrature converter 11 performs discrete cosine transform on the input difference data so that the difference data is converted into coefficients in the frequency domain. The quantizer 12 changes the transform coefficients to representative values of various levels through a predetermined quantization process. At that time, the quantizer 12 quantizes the output data from the quadrature converter 11 in accordance with the quantization level Q input from the buffer 14. The variable length encoder 13 variable-length encodes the segment data in consideration of the statistical characteristics of the quantization coefficients to generate compressed data V_CD . The variable length encoding procedure for video data will be described below. The buffer 14 receives the compressed data from the variable length encoder 13 and outputs the data to the transmission channel at a constant rate. The quantization level Q at that time becomes an output for controlling the amount of compressed data in order to prevent overflow or underflow in the transmission data.

일반적으로, 비데오 데이터의 인접 프레임들간에는 유사한 패턴들이 존재한다. 따라서, 영상이 약간 이동하는 경우, 그 영상의 움직임은 현재 프레임과 이전 프레임들간의 비교에 의해 추정(estimation)된다. 동벡터(MV)는 동추정의 결과로 계산되며, 동보상(motion compensation)은 동벡터에 따라 이전 프레임들로부터 달성된다. 동보상으로부터 얻어진 세그먼트 데이터와 입력단(10)으로 입력하는 세그먼트데이타간의 차분데이타의 량은 매우 적으므로, 데이터는 위의 부호화 처리에 의해 더욱 압축될 수 있다. 동추정 및 동보상을 수행하기 위한 피드백 루프는 역양자화기(15), 역직교변환기( 16), 프레임메모리(17), 동추정기(18) 및 동보상기(19)를 구비한다. 역양자화기(15)는 양자화기(12)로부터 출력하는 양자화계수들을 역양자화하며, 역직교변환기(16)는 역양자화기(15)의 출력데이타를 역이산 코사인 변환하여 공간영역의 비데오데이타로 변환한다. 제2가산기(42)는 역직교변환기(16)로부터 출력하는 비데오 데이터를 제2스위치(SW2)를 통해 입력하는 피드백 데이터에 가산하여, 그 결과로서 생기는 세그먼트 데이터를 출력한다. 제2가산기(A2)로부터 출력하는 세그먼트 데이터는 프레임메모리(17)에 순차적으로 저장되어 프레임을 재구성한다. 동추정기(18)는 프레임메모리(17)에 저장된 프레임 데이터로부터 입력단(10)을 통해 입력하는 블록형 세그먼트 데이터와 가장 유사한 패턴의 블록형 세그먼트 데이터를 구하며, 두 세가먼트 데이터로부터 영상들의 움직임을 추정하기 위한 동벡터(MV)를 계산한다. 동벡터(MV)는, 복호화 시스템에서 사용되어지기 위하여, 수신기 및 동보상기(19)로 전송된다. 동보상기(19)는 프레임메모리(17)내의 프레임 데이터로부터 동벡터(MV)에 대응하는 세그먼트 데이터를 읽어내며, 읽어낸 데이터를 제1가산기(A1)로 인가한다. 상술한 것 처럼, 제1가산기(A1)는 입력단(10)으로부터 입력되는 세그먼트 데이터와 동보상기(19)로부터 입력되는 세그먼트 데이터간의 차분데이타를 계산하며, 그 차분데이타는 부호화되어 수신기로 전송된다. 한편, 제1도의 두 스위치들(SW1 및 SW2)은, 차분데이타의 누적으로 인한, 부호화된 프레임들의 데이터와 처리되지 않은 프레임들의 데이터간의 차이를 방지하기 위하여, 기설정된 크기의 프레임 또는 세그먼트 단위로 데이터를 리프레싱(refreshing)하는 리프레쉬 스위치들이다.In general, similar patterns exist between adjacent frames of video data. Thus, when the image moves slightly, the movement of the image is estimated by comparison between the current frame and the previous frames. The motion vector MV is calculated as a result of the motion estimation, and motion compensation is achieved from previous frames according to the motion vector. Since the amount of difference data between the segment data obtained from the motion compensation and the segment data input to the input terminal 10 is very small, the data can be further compressed by the above coding process. The feedback loop for performing the estimation and the compensation is provided with an inverse quantizer 15, an inverse orthogonal transformer 16, a frame memory 17, a copper estimator 18, and a compensator 19. The inverse quantizer 15 inverse quantizes the quantization coefficients output from the quantizer 12, and the inverse orthogonal transformer 16 inverse-discrete cosine-converts the output data of the inverse quantizer 15 to video data of the spatial domain. Convert. The second adder 42 adds the video data output from the inverse orthogonal transformer 16 to the feedback data input through the second switch SW2, and outputs the resulting segment data. The segment data output from the second adder A2 is sequentially stored in the frame memory 17 to reconstruct the frame. The motion estimator 18 obtains block-type segment data having a pattern most similar to the block-type segment data input through the input terminal 10 from the frame data stored in the frame memory 17, and estimates the motion of the images from the two segment data. Calculate the dynamic vector (MV). The motion vector (MV) is transmitted to the receiver and the compensator 19 to be used in a decoding system. The broadcast compensator 19 reads the segment data corresponding to the motion vector MV from the frame data in the frame memory 17, and applies the read data to the first adder A1. As described above, the first adder A1 calculates the difference data between the segment data input from the input terminal 10 and the segment data input from the broadcast receiver 19, and the difference data is encoded and transmitted to the receiver. In the meantime, the two switches SW1 and SW2 of FIG. 1 are configured in a frame or segment unit of a predetermined size in order to prevent a difference between data of encoded frames and data of unprocessed frames due to accumulation of difference data. Refresh switches that refresh the data.

부호화된 비데오데이터(V_CD)는 저장매체에 저장되거나 수신기로 전송되어 제2도에서 보인 것 같은 복호기로 입력한다. 가변장복호기(21)는 입력 비데오데이터(V_CD)를 가변장 부호화의 역과정을 통해 복호화한다. 역양자화기(22)는 가변장복호기(21)로부터 입력하는 양자화계수들을 복호화하여, 주파수영역의 변환계수들을 출력한다. 역직교변환기(23)는 역양자화기(22)로부터 입력하는 주파수영역의 변환계수들을 공간영역의 비데오 데이터로 변환한다. 부호기의 동추정기(18)로부터 출력하는 동벡터(MV)는 복호기의 동보상기(24)로 입력한다. 동보상기(24)는 프레임메모 리(25)에 저장된 프레임데이터로부터 동벡터(MV)에 대응하는 세그먼트 데이터를 읽어내며, 읽어낸 데이터를 가산기(A)로 인가한다. 가산기(A)는 역직교변환기(23)로부터 출력하는 차분데이터를 동보상기(24)로부터 입력하는 세그먼트 데이터에 가산하여, 그 결과로 생기는 재구성된 세그먼트 데이터를 출력한다. 스위치(SW)는 동보상기(24)의 출력단에 연결되어 위에서 설명된 제1도의 부호기에서의 리프레쉬 스위치들과 동일한 역할을 수행한다.The encoded video data V_CD is stored in a storage medium or transmitted to a receiver and input to a decoder as shown in FIG. The variable length decoder 21 decodes the input video data V_CD through a reverse process of variable length coding. The inverse quantizer 22 decodes the quantization coefficients input from the variable length decoder 21 and outputs transform coefficients in the frequency domain. The inverse orthogonal transformer 23 converts the transform coefficients of the frequency domain input from the inverse quantizer 22 into video data of the spatial domain. The moving vector MV output from the encoder estimator 18 of the encoder is input to the decoder 24 of the decoder. The broadcast compensator 24 reads out the segment data corresponding to the motion vector MV from the frame data stored in the frame memory 25, and applies the read data to the adder A. The adder A adds the difference data output from the inverse orthogonal transformer 23 to the segment data input from the broadcast processor 24, and outputs the resulting reconstructed segment data. The switch SW is connected to the output terminal of the broadcast compensator 24 and performs the same role as the refresh switches in the encoder of FIG. 1 described above.

기존의 부호화 시스템에서는 가변장 부호화를 위해 허프만(Huffman)부호화 기법이 사용되었다. 허프만 부호화는 입력 데이터에 기설정된 심볼의 확률에 따라 길이가 서로 다른 부호(code)들을 할당한다. 즉, 확률이 높을수록 짧은 길이의 부호가 할당되며, 확률이 낮을수록 긴 길이의 부호가 할당된다. 허프만 알고리듬에 의한 부호화에서, 수많은 서로 다른 심볼들이 존재하며 특정 심볼들이 낮은 확률을 갖는 경우에, 긴 부호들이 허프만 알고리듬에 의해 드물게 나타나는 복수개의 심볼들에 할당될 때, 데이터처리는 부호화 및 복호화 처리에서 더욱 복잡해지게 된다. 이러한 문제들을 해결하기 위하여, 기설정된 고정된(fixed) 길이의 부호가 드물게 나타나는 복수개 심볼들의 분포영역(이하로는“에스케이프 영역(escape area)”이라 함)을 위해 할당되는 경우, 데이터처리의 복잡함은 평균 부호길이가 원래의 허프만 부호들의 평균값 이상으로 증가되는 경우에서 조차도 크게 감소된다.In the conventional coding system, Huffman coding scheme is used for variable length coding. Huffman coding allocates codes having different lengths according to a probability of a symbol preset in the input data. That is, the higher the probability, the shorter the length of the code is assigned, the lower the probability, the longer the sign is assigned. In the encoding by the Huffman algorithm, when a large number of different symbols exist and certain symbols have a low probability, when long codes are assigned to a plurality of symbols which are rarely represented by the Huffman algorithm, the data processing is performed in the encoding and decoding process. It becomes more complicated. In order to solve these problems, when a predetermined fixed length code is allocated for a distribution area of a plurality of rarely appearing symbols (hereinafter referred to as an "escape area"), The complexity is greatly reduced even when the average code length is increased above the average of the original Huffman codes.

제3(a)도는 데이터가 8×8크기의 세그먼트들로 분할된 데이터 구조의 예를 보여주며, 제3(b)도는 8×8 세그먼트데이타의 주파수영역으로의 변환 및 변환된 데이터의 양자화에 의한 8×8 양자화계수들을 보여주고, 제3(c)도는 많은 양자화계수들이 주파수영역의 “0”인 점을 고려한, 저주파로부터 고주파로의 양자화계수들의 지그재그(zigzag)주사 및 주사된 계수들의 [런,레벨]심볼들로의 부호화를 보여준다. 런(run)은 “0”이 아닌 계수들간의 “0”의 발생 횟수를 의미하며, 레벨은 “0”이 아닌 계수의 절대값을 의미한다. 제3(a)-3(c)도의 8×8 데이터의 경우, 런은 “0”부터 “63”까지의 값들을 가질수 있으며, 양자화 출력이 “-255”부터 “255”까지의 정수값인 경우, 레벨은 “1”부터 “255”까지의 값이며 그 부호(sign)는 별도로 표시된다.Fig. 3 (a) shows an example of a data structure in which data is divided into 8 × 8 size segments, and Fig. 3 (b) shows the conversion of 8 × 8 segment data into a frequency domain and quantization of the transformed data. Fig. 3 (c) shows the zigzag scanning of the quantization coefficients from low frequency to high frequency and the run of the scanned coefficients, taking into account that many of the quantization coefficients are “0” in the frequency domain. , Level] shows the encoding into symbols. Run means the number of occurrences of "0" between coefficients that are not "0" and level means the absolute value of the coefficient that is not "0". For 8x8 data in Figures 3 (a) -3 (c), the run can have values from "0" to "63", where the quantization output is an integer value from "-255" to "255". In this case, the level is a value from "1" to "255" and its sign is indicated separately.

제3(d)도는 기존처럼 8×8 크기의 블록으로 영상을 분할하는 방법대신 영상내에 존재하는 다양한 대상물별로 분할하여 세그먼트를 구성하는 예를 보여준다. 각 데이터 세그먼트는 일반적으로 독단적으로 모양지어진 대상물에 대응한다. 제3(e)도는 대상물에 대응하는 데이터 세그먼트의 변환부호화 예를 보여준다. 즉, 대상물의 모양이 독단적이므로, 전통적인 블록에 기초한 직교변환을 그대로 사용할 수는 없다. 이 문제를 개선하기 위한 한 방법은 주어진 대상물을 둘러싼 직사각형(또는 정사각형)을 구한후, 이를 기반으로 직교변환을 사용하는 것이다. 이때, 주어진 대상물의 바깥이면서 둘러싸는 직사각형의 안쪽이 되는 화소값들은 적응적으로 선택되어, 선택된 수의 변환계수들로써 주어진 대상물이 가장 충실하게 재구성될 수 있게 한다. 제3(f)도는 변환계수들을 선택하는 예를 보여준다. L개의 화소들을 갖는 영상부분을 나타내는 데이터 세그먼트의 경우, 변환영역(transform domain)에서 최대로 L개의 의미있는 변환계수들이 존재할 수 있다. 제3(f)도의 해칭된 영역에 해당하는 계수들의 숫자를 L′이라 하면, L′은 주어진 대상물을 둘러싼 사각형내의 화소수에서 데이터세그먼트내의 화소 즉, L값을 뺀 값이다. 제3(e)도의 외부 화소들의 값들을 선택함에 의해 L′개의 여분의 변환계수가 생긴 것이다. 본 발명은 제3(g)도에 보여진 일예와 같이, 제3(f)도의 선택된 L개 또는 더 작은 객수의 변환계수들만을 최적의 주사패턴으로 주사한 후 가변장부호화하여 압축효율을 더욱 향상시키기 위한 것이다.FIG. 3 (d) shows an example in which a segment is formed by dividing the image into various objects existing in the image instead of the method of dividing the image into 8 × 8 blocks. Each data segment generally corresponds to an arbitrarily shaped object. 3 (e) shows an example of transform encoding of a data segment corresponding to an object. That is, since the shape of the object is arbitrary, the orthogonal transformation based on the traditional block cannot be used as it is. One way to improve this problem is to find a rectangle (or square) around a given object and then use an orthogonal transformation based on it. At this time, the pixel values outside the given object and inside the enclosing rectangle are adaptively selected so that the given object can be most faithfully reconstructed with the selected number of transform coefficients. FIG. 3 (f) shows an example of selecting conversion coefficients. In the case of a data segment representing an image part having L pixels, there may be up to L significant transform coefficients in a transform domain. When the number of coefficients corresponding to the hatched area of FIG. 3 (f) is L ', L' is the number of pixels in the rectangle surrounding the given object minus the pixel, that is, the L value. By selecting the values of the external pixels in FIG. 3 (e), L 'extra conversion coefficients are generated. As in the example shown in FIG. 3 (g), the present invention scans only the selected L or smaller transform coefficients of FIG. It is to let.

변환계수들의 선택 및 외삽(extrapolation) 처리는 제3(h)도의 흐름도를 참조하여 더 설명된다.Selection and extrapolation processing of the transform coefficients are further described with reference to the flowchart in FIG. 3 (h).

주어진 대상물 외부의 화소값들은 POSC에 기초한 반복 방식을 통하여 최적 선택될 수 있다. 첫 번째 반복에서, 외부 화소값들은 독단적으로 설정될 수 있으나, 내부 화소값들을 반복하거나 반영하여 사용하면 더욱 효과적인 것으로 알려졌다[S. F. Chang and D. G. Messerschmitt, “Transform Coding of an Arbitrarily-shaped Image Segment” Proceedings of ACM Multimedia, August, 1993]. 외부 화소값들이 선택되면, 직사각형블록은 L또는 적은 수의 변환계수들을 얻기 위하여 전방(forward) 변환된다. 각 변환계수의 크기는 그 계수에 관련된 에너지에 대응하므로, 계수선택의 한 방법은 L개(또는 기설정된 작은 수)의 가장 큰 변환계수들을 선택하는 것이다.Pixel values outside a given object may be optimally selected through an iterative method based on POSC. In the first iteration, the external pixel values can be arbitrarily set, but it has been found that it is more effective to use the internal pixel values by repeating or reflecting them. F. Chang and D. G. Messerschmitt, “Transform Coding of an Arbitrarily-shaped Image Segment” Proceedings of ACM Multimedia, August, 1993]. If external pixel values are selected, the rectangular block is forward transformed to obtain L or a small number of conversion coefficients. Since the magnitude of each transform coefficient corresponds to the energy associated with that coefficient, one method of coefficient selection is to select the L (or predetermined small numbers) of the largest transform coefficients.

계수들이 선택되면, 선택되지 않은 다른 것들은“0”으로 설정된다. 이러한 계수“0”으로 두기(zeroing)는 여지없이 공간영역의 신호에 왜곡을 일으키므로, 선택되지 않은 위치들에서 “0”으로 된 계수들의 역변환 이후에, 대상물의 내부 및 경계상의 화소값들은 원래의 값들에 의해 대체된다.If coefficients are selected, others that are not selected are set to "0". Since zeroing these coefficients invariably distorts the signal in the spatial domain, after the inverse transformation of the coefficients to "0" at unselected positions, the pixel values on the inside and the boundary of the object are inherently original. Replaced by the values of.

외부 화소값들만이 전방변환, 역변환 및 내부화소대체에 의해 영향받으며, 선택되지 않은 위치들의 계수값들은 더 이상 “0”이 되지 않는다. 이런 이유로, 이전의“전방변환→“0”으로 두기→역변환→내부화소대체”처리들은 수렴할 때까지 반복된다. 수렴은 (H.H. chen, M.R. Civanlar, and B.G. Haskell, “A Block Transform Coder for Arbitrarily Shaped Image Segments”Proceedings of IEEE International Conference on Image Processing, 1994, Vol. 1, 85-89에서 보인 것 처럼) 보증된 것으로 알려졌다. 수렴되면, 모양 적응 변환이 완료된다. 그 밖에도, 대상물에 대응하는 데이터 세그먼트를 DCT등을 통해 주파수영역으로 변환하며, 그 데이터 세그먼트와 마찬가지의 크기를 갖는 계수에서 대상물 모양(shape)에 따라 적응적으로 계수를 선택하는 방식이 알려져 있다[IEEE Trans. Circuit, System, and Video Technology, 1995 Feb. vol.5 pp.59-62 “Shape-Adaptive DCT for Generic Coding of Video”by T. Sikora and B. Makai].Only external pixel values are affected by forward transform, inverse transform and internal pixel replacement, and the coefficient values of the unselected positions no longer become "0". For this reason, the previous "forward conversion->" zero "-> inverse conversion-> internal pixel replacement-processes are repeated until convergence. Convergence is guaranteed (as seen in HH chen, MR Civanlar, and BG Haskell, “A Block Transform Coder for Arbitrarily Shaped Image Segments” Proceedings of IEEE International Conference on Image Processing, 1994, Vol. 1, 85-89). Became known. Once converged, the shape adaptation transformation is complete. In addition, a method of converting a data segment corresponding to an object into a frequency domain through a DCT or the like and adaptively selecting coefficients according to the shape of the object from coefficients having the same size as the data segment is known. IEEE Trans. Circuit, System, and Video Technology, 1995 Feb. vol. 5 pp. 59-62 “Shape-Adaptive DCT for Generic Coding of Video” by T. Sikora and B. Makai.

기존의 가변장 부호화 시스템은, 비데오 신호의 에너지가 AC성분들의 중심이 되는 낮은 주파수영역에 집중되어 있는 이유로, 비데오 데이터의 가변장 부호화에서는 M×M 양자화계수들을 위하여 (제3(a)-3(c)도에 묘사된) 지그재그 주사패턴을 사용하였다. 그러나, 비데오 신호의 에너지는 비데오 신호의 패턴에 따라 수평방향 또는 수직방향의 주파수 성분들 쪽으로 보다 광범위하게 분포할 수 있다. 그러므로, 기존의 지그재그 주사패턴이 비데오 데이터의 가변장 부호화를 위한 최적의 주사 패턴인 것은 아니다. 따라서, 비데오 데이터의 분포특성들에 따라 융통성 있게 수평방향 또는 수직방향으로 기울일 수 있는 주사패턴들이 가변장부호화 및 가변장복호화를 위하여 소망되었다. 또한, 독단적으로 모양지워진 대상물에 대응하며 변환이 둘러싸는 직사각형에 대해 연습된 영상세그먼트들에 대응하는 데이터 세그먼트들의 경우에, 주사패턴이 반드시 모든 주파수성분들을 망라(cover)할 필요는 없다. 그래서, 본 발명은 주파수영역에서 수평방향 또는 수직방향으로 각기 선택되는 변환계수를 알 수 있는 정보를 사용하여 선택된 계수들에 해당하는 주파수성분들만을 주사할 수 있도록 한다.In the conventional variable length coding system, since the energy of the video signal is concentrated in the low frequency region where the centers of the AC components are centered, in the variable length coding of the video data, for the M × M quantization coefficients (3 (a) -3 A zigzag scan pattern (as depicted in Figure (c)) was used. However, the energy of the video signal can be more widely distributed toward frequency components in the horizontal or vertical direction depending on the pattern of the video signal. Therefore, the existing zigzag scan pattern is not an optimal scan pattern for variable length coding of video data. Accordingly, scan patterns that can be flexibly tilted in the horizontal or vertical direction according to the distribution characteristics of the video data have been desired for variable length coding and variable length decoding. Furthermore, in the case of data segments corresponding to arbitrarily shaped objects and corresponding to image segments trained on the rectangle surrounding the transform, the scan pattern does not necessarily cover all frequency components. Thus, the present invention enables to scan only the frequency components corresponding to the selected coefficients by using information which can know the transform coefficients respectively selected in the horizontal or vertical direction in the frequency domain.

제4도는 본 발명의 실시예에 따른 가변장부호기를 보여준다. 제4도의 부호기는 제3(f)도에 보인 양자화된 세그먼트 데이터와 같은 양자화된 세그먼트 데이터의 양자화계수들을 개별적으로 저장하는 N개의 계수저장부들(CM₁-CM_N)과, 별개의 주사번지들을 계수저장부들의 각각에 제공하는 N개의 주사번지출력부들(SAG₁-SAG_N)로 이루어진 N개의 주사수단(41₁-41_N);개별 주사패턴들에 따라 계수저장부들 각각의 계수들을 가변장부호화테이블에 따라 가변장부호화하는 N개의 가변장부호기들(VLC₁-VLC_N); 가변장부호기들 각각의 가변장부호화 데이터를 저장하는 N개의 버퍼들(BF₁-BF_N); 가변장부호기들 각각으로부터 출력하는 가변장부호화된 데이터의 길이들을 제각기 적산하는 N개의 적산기들(ACCM₁-ACCM_N); N개의 적산기들에서 적산된 길이들중에서 최소값을 선택하는 최소선택기(52); 및 최소선택기(52)에서 선택된 가변길이부호화 채널들의 버퍼출력을 선택 및 전송하는 선택스위치(54)를 포함한다.4 shows a variable length encoder according to an embodiment of the present invention. The encoder of FIG. 4 has N coefficient storage units CM_{1 to} CM_N for separately storing quantization coefficients of quantized segment data, such as the quantized segment data shown in FIG. 3 (f), and separate scan addresses. coefficient storage means N number of scanning of N scan address output units (SAG -SAG₁_N) provided for each of the portions (41₁ -41_N); Chapter coefficients storage sections, each of the coefficients according to the respective scan pattern variable the N variable-carrying exhalation to variable-length encoded according to the encoding table (VLC₁ -VLC_N); N buffers BF₁ -BF_N for storing variable length encoding data of each of the variable length codes; N accumulators (ACCM₁ -ACCM_N ) for respectively integrating the lengths of the variable length coded data output from each of the variable length coders; A minimum selector 52 for selecting a minimum value among the lengths accumulated in the N totalizers; And a selection switch 54 for selecting and transmitting a buffer output of the variable length encoding channels selected by the minimum selector 52.

우선, 기설정된 크기의 세그먼트로 양자화된 양자화계수들은 N개의 계수저장부들(CM₁-CM_N)의 각각에 저장된다. 제1, 제2 및 제N계수저장부들은 제1, 제2, 및 제N주사번지출력부들로부터 개별적으로 출력된 제1, 제2 및 제N주사번지들을 각각 수신한다. 물론, 하나의 계수저장부만을 사용하여 계수저장부에 저장된 양자화계수들을 N개의 주사번지들 각각에 순차적으로 주사되도록 할 수도 있다. N개의 주사번지들 각각에 의해 주사되는 N개의 계수저장부들중에서 제1계수저장부(CM₁)에 대한 부호화채널을 아래에서 설명한다.First, quantization coefficients quantized into segments having a predetermined size are stored in each of the_N coefficient storage units CM_{1 to} CM_N. The first, second and N-th coefficient storage units receive the first, second and N-th scan addresses respectively output from the first, second and N-th scan address output units. Of course, only one coefficient storage unit may be used to sequentially scan the quantization coefficients stored in the coefficient storage unit to each of the N scan addresses. A coding channel for the first coefficient storage unit CM₁ among the N coefficient storage units scanned by each of the N scan addresses will be described below.

제1계수저장부(CM₁)에 저장된 양자화계수들은 제1주사번지에 의해 기설정된 주사방향으로 주사된다. 이때, 제1계수저장부(CM₁)는 인가되는 제어신호(Dcontrol)에 의해 저장된 양자화계수들이 모두 주사되지 않고, 선택된 계수들만 주사된다. 여기서, 제어신호(Dcontrol)는 이전에 설명한 수평방향 또는 수직방향으로 선택된 계수를 알 수 있는 정보로서, 선택된 계수의 갯수 등으로 나타낸다. 예를 들어, 제1주사번지출력 부(SAG₁)에서 지그재그주사패턴에 근거한 주사번지를 출력하고 제3(f)도와 같이 계수들이 선택된 경우, 제1계수저장부(CM₁)에 저장된 양자화계수들은 제어신호(Dcontr ol)에 의해 제3(g)도에 보여진 바와 같이 수평방향으로 각각 6개, 6개, 5개, 4개의 계수들만 주사된다. 물론, 제어신호(Dcontrol)는 계수저장부 대신 주사번지출력부에서 인가받아 사용할 수도 있다. 제1가변장부호기(VLC₁)는 기설정된 가변장부호화테이블에 따라 주사된 계수들을 가변장부호화하고, 가변장부호화된 데이터(D_VLC)와 가변장부호화된 데이터의 길이(L_VLC)를 개별적으로 출력한다. 제1가변장부호기(VLC₁)로부터 출력하는 가변장부호화된 데이터(D_VLC)는 제1버퍼(BF₁)에 저장되고, 가변장부호화된 데이터의 길이(L_VLC)는 제1가변장부호기(VLC₁)에 의해 부호화된 부호들의 길이(L_VLC)들을 적산하는 제1적산기(ACCM₁)로 입력되어 적산된다. 제1적산기(ACCM₁)는 가산기(A₁)와 제1적산길이저장부(LM₁)로 구성된다. 제 1가변장부호기(VLC₁)로부터 입력된 가변장부호화된 데이터의 길이(L_VLC)는 가산기(A1)에서 제1적산길이저장부(LM₁)로부터 피드백된 적산된 길이에 가산된다. 제1적산길이저장부(LM₁)는 가산기(A₁)로부터 출력하는 갱신된 적산된 길이를 저장한다.Quantization coefficients stored in the first coefficient storage unit CM₁ are scanned in a preset scanning direction by the first scan address. In this case, the first coefficient storage unit CM₁ does not scan all of the quantization coefficients stored by the control signal Dcontrol, and scans only selected coefficients. In this case, the control signal Dcontrol is information for identifying a coefficient selected in the horizontal or vertical direction described above, and is represented by the number of selected coefficients or the like. For example, when the scan address based on the zigzag scan pattern is output from the first scan address output unit SAG₁ and the coefficients are selected as shown in FIG. 3 (f), the quantization coefficient stored in the first coefficient storage unit CM₁ . As shown in FIG. 3 (g), only 6, 6, 5, and 4 coefficients are scanned in the horizontal direction by the control signal Dcontr ol. Of course, the control signal Dcontrol may be applied from the scan address output unit instead of the coefficient storage unit. The first variable length encoder VLC₁ performs variable length encoding on the coefficients scanned according to a predetermined variable length encoding table, and separately stores the length L_VLC of the variable length coded data D_VLC and the variable length coded data. Will print The first is stored in the variable-carrying exhalation (VLC₁₎ variable-length coded data (D_VLC) to output from the first buffer (BF_1), a first variable-carrying exhalation length (L_VLC) of coded data variable-length It is input to the first accumulator ACCM₁ that integrates the lengths L_VLC of the codes encoded by the VLC₁ , and is integrated. The first accumulator ACCM₁ includes an adder A₁ and a first integration length storage unit LM₁ . Claim 1 is added to the cumulative length of the feedback from the variable carrying exhalation (VLC₁₎ Length (L_VLC) of the sheet of the input variable-coding data from the adder are stored in the first accumulation length (A1) unit (LM_1). The first integration length storage unit LM₁ stores the updated integrated length output from the adder A₁ .

이러한 일련의 부호화 채널들은 제2, 제3 및 제N계수저장부들(CM₂,CM₃, CM_N)의 양자화계수들에 적용된다. 그러나, 다른 패턴들이 N개의 계수저장부들에 개별적으로 저장되는 한 세그먼트의 양자화계수들을 주사하기 위해 사용된다. 제6도는 여러 다른 주사패턴들의 구현 예들을 보여준다. 제6(a)도는 0도(degree)의 주사방위(orien tation)를 지닌 주사패턴, 제6(b)도는 30도의 주사방위를 지닌 주사패턴, 그리고 제6(c)도는 45도의 주사방위를 지닌 주사패턴을 묘사한다.These series of coding channels are applied to the quantization coefficients of the second, third and Nth coefficient storage units CM₂ , CM₃ and CM_N. However, other patterns are used to scan the quantization coefficients of one segment, which are stored separately in the N coefficient storage units. 6 shows implementation examples of different scan patterns. 6 (a) is a scanning pattern having an orientation of 0 degrees, 6 (b) is a scanning pattern having a scanning orientation of 30 degrees, and 6 (c) is a scanning pattern of 45 degrees. Describe the scanning pattern with

다양한 주사패턴들에 따른 가변장부호화 채널들에서, N개의 적산기들(ACCM₁-ACCM_N)은 적산길이저장부들의 각각에 저장된 적산길이데이터를 최소선택기(52)의 N개의 입력단들로 개별적으로 공급하며, 최소선택기(52)는 적산길이들의 최소값을 결정한다. N개의 유형의 주사패턴들에 따라 가변장부호화된 데이터를 저장하는 N개 버퍼들(BF₁-BF_N)의 출력단들 각각은 선택스위치(54)의 N개의 입력단들에 개별적으로 연결된다. 최소선택기(52)는 N개의 적산길이저장부들(LM₁-LM_N)의 각각으로부터 입력된 적산길이데이터중에서 최소값을 선택한다. 최소선택기(52)는 적산길이들중의 선택된 최소값을 지닌 가변장부호화채널들의 주사패턴들을 나타내는 주사패턴데이터(D_SCAN)를 출력하고, 적산길이들중의 선택된 최소값에 대응하는 소정의 선택제어신호(SEL)를 선택스위치(54)에 공급한다. 선택스위치(54)는 N개의 입력단들로 개별적으로 입력되는 입력데이터중에서 적산길이들중의 최소값에 맞는 가변장부호화된 데이터(D_VLC)를 선택하여 출력한다.In variable length coding channels according to various scan patterns, the N accumulators ACCM₁ to ACCM_N individually store the accumulated length data stored in each of the accumulated length storage units into the N input terminals of the minimum selector 52. The minimum selector 52 determines the minimum value of the integration lengths. Each of the output stages of the_N buffers BF₁ -BF_N storing the variable length coded data according to the N types of scanning patterns is individually connected to the N input terminals of the selector switch 54. The minimum selector 52 selects a minimum value from the integration length data input from each of the_N integration length storage units LM_{1 to} LM_N. The minimum selector 52 outputs scan pattern data D_SCAN representing scan patterns of the variable length coding channels having the selected minimum value among the integration lengths, and selects a predetermined selection control signal corresponding to the selected minimum value among the integration lengths. (SEL) is supplied to the selector switch 54. The selector switch 54 selects and outputs the variable length coded data D_VLC from among the input data input to the N input terminals individually according to the minimum value of the integration lengths.

최소값이 선택될 때마다, 즉, 매 세그먼트 데이터의 가변장부호화가 완료될 때마다, 최소선택기(52)는 리셋신호(RST)를 발생하여, N개의 버퍼들(BF₁-BF_N)과 N개의 적산길이저장부들(LM₁-LM_N)을 리셋한다. 가변장부호화된 데이터(D_VLC)와 주사패턴 데이터(D_SCAN), 그리고 주사대상이 되는 계수들의 선택정보를 나타내는 제어신호(Dcontrol)는 디지탈 데이터로 저장되거나 복호화를 위하여 수신기로 전송된다.Each time a minimum value is selected, i.e., every time variable length encoding of each segment data is completed, the minimum selector 52 generates a reset signal RST, so that N buffers BF₁ -BF_N and N are generated. Reset the accumulated length storage units LM_{1 to} LM_N. Variable length coded data D_VLC , scan pattern data D_SCAN , and a control signal Dcontrol indicating selection information of coefficients to be scanned are stored as digital data or transmitted to a receiver for decoding.

제5도는 본 발명에 따른 가변장복호기의 실시예를 보여준다. 제5도를 참조하면, 가변장복호기(61)로 입력하는 가변장부호화된 데이터(D_VLC)는 가변장복호화테이블에 따라 가변장부호화되기 이전 상태로 복원된다. 더욱이, 부호기로부터 전송된 주사패턴 데이터(D_SCAN) 및 제어신호(Dcontrol)는 역주사(inverse scan)부(62)에 입력한다. 역주사부(62)는 제6도에서 보인것과 같은, 다양한 주사패턴들(1, N 스캔들)에 대응하는 주사번지들의 각각을 저장한다. 역주사부(62)는 입력된 주사패턴 데이터(D_SCAN)에 대응하는 주사번지들(ADDR_S)에 따라 가변장복호기(61)로부터 입력하는 데이터들을 이차원 양자화계수로 변환한다. 이때, 역주사부(62)는 입력된 제어신호(Dcontrol)에 따라 주사번지들중 해당하는 주사번지만으로 가변장복호기(61)에서 복호화된 데이터들을 이차원 주파수영역상의 선택된 주파수성분의 양자화계수들로 변환한다. 그 후에, 양자화계수들은 역양자화기로 공급된다.5 shows an embodiment of a variable length decoder according to the present invention. Referring to FIG. 5, the variable length coded data D_VLC input to the variable length decoder 61 is restored to a state before the variable length encoding is performed according to the variable length decoding table. Furthermore, the scan pattern data D_SCAN and the control signal Dcontrol transmitted from the encoder are input to the inverse scan unit 62. The reverse scanning section 62 stores each of the scanning addresses corresponding to the various scanning patterns (1, N scans), as shown in FIG. The inverse scanning unit 62 converts data input from the variable length decoder 61 into two-dimensional quantization coefficients according to the scanning addresses ADDR_S corresponding to the input scanning pattern data D_SCAN . In this case, the inverse scanning unit 62 converts the data decoded by the variable length decoder 61 into quantization coefficients of the selected frequency components in the two-dimensional frequency domain according to the input control signal Dcontrol to only one of the scanning addresses. do. Thereafter, the quantization coefficients are fed to an inverse quantizer.

전술한 바와 같이, 본 발명에 따른 가변장부호화시스템은 다양한 주사패턴들에 따라 각 세그먼트 데이터를 가변장부호화한 다음, 가변장부호화된 데이터의 길이를 최소하하는 주사패턴과 그 주사패턴에 따라 가변장부호화된 데이터를 전송하거나, 차후의 복호화를 위해 디지탈 기록매체에 저장한다. 본 발명에 따른 가변장복호화시스템은 저장되거나 전송된 가변장부호화된 데이터를 가변장부호화 과정에서 이용된 것과 동일한 주사패턴에 따라 복호화한다. 그 결과, 가변장부호화 및 가변장복호화를 위한 시스템은 전송데이터를 더욱 압축할 수 있다.As described above, the variable length coding system according to the present invention variable length codes each segment data according to various scan patterns, and then varies according to the scan pattern and the scan pattern that minimizes the length of the variable length coded data. The encoded data is transmitted or stored in a digital recording medium for later decoding. The variable length decoding system according to the present invention decodes the stored or transmitted variable length encoded data according to the same scanning pattern used in the variable length encoding process. As a result, the system for variable length coding and variable length decoding can further compress the transmission data.

본 발명에서, 각 세그먼트 데이터는 영상 부분들의 다양한 크기(size)들과 모양(shape)들을 고려하여 결정된다. 즉, 본 발명은 디지탈 데이터가 어떤 식으로 세그먼트 데이터로 분할되는 지에 상관없이 세그먼트 데이터를 부호화하고 복호화하는 데 사용된다. 이는 제3(d)-3(h)도를 참조함에 의해 더 잘 이해될 것이다.In the present invention, each segment data is determined in consideration of various sizes and shapes of the image portions. That is, the present invention is used to encode and decode segment data regardless of how digital data is divided into segment data. This will be better understood by reference to Figures 3 (d) -3 (h).

본 발명은 가변장 부호기/복호기를 이용하여 묘사 및 설명되었으나, 다른 유형의 부호화기/복호화기가 본 발명에 사용될 수 있다. 예를 들면, 허프만이나 산술(arithmet ic) 부호기/복호기가 대체될 수 있다. 게다가, 본 발명의 이점은 부호기/복호기의 유형에 무관한 최적의 주사패턴을 사용하여 얻어지므로, 본 발명은 가변장 부호화기/복호화기 없이도 사용할 수 있다.Although the present invention has been depicted and described using variable length encoders / decoders, other types of encoders / decoders may be used in the present invention. For example, Huffman or arithmetic coders / decoders may be substituted. In addition, since the advantages of the present invention are obtained by using an optimal scanning pattern independent of the type of encoder / decoder, the present invention can be used without a variable length encoder / decoder.

더욱이, 본 발명은 이차원 데이터와 관련하여 묘사 및 설명되었으나, 다차원 데이터를 이용하는 부호화 및 복호화 시스템에 적용될 수 있다.Moreover, although the present invention has been depicted and described with respect to two-dimensional data, it can be applied to encoding and decoding systems using multidimensional data.

다차원으로의 확장은 동시에 다수의 세그먼트들을 함께 주사함으로써 실현될 수 있다. 제7(a)도는 다수의 세그먼트들이 동일 화상으로부터 얻어진 경우의 특정한 예를 보여준다. 그러나, 다른 시간들에서의 세그먼트들 또한, 제7(b)도에서 그 예로 보인 것 처럼, 동시에 주사될 수 있다. 어떠한 제한 없이, 제7(a)도와 제7(b)도의 두 경우들은 제7(c)도에 보인 것처럼 혼합될 수 있다. 제7(d)도와 제7(e)도는 다중 세그먼트들을 위한 주사패턴들의 예들을 보여준다. 제7(d)도 및 제7(e)도에 표기된 숫자들은 제3(a)도 또는 제3(c)도에서 데이터 세그먼트의 주사순서를 표시한다.Expansion to multiple dimensions can be realized by scanning multiple segments together at the same time. 7 (a) shows a specific example in the case where multiple segments are obtained from the same image. However, segments at other times may also be scanned at the same time, as shown by way of example in FIG. 7 (b). Without any limitation, the two cases of Fig. 7 (a) and Fig. 7 (b) can be mixed as shown in Fig. 7 (c). 7 (d) and 7 (e) show examples of scan patterns for multiple segments. The numerals shown in FIGS. 7 (d) and 7 (e) indicate the scanning order of the data segments in FIGS. 3 (a) or 3 (c).

본 발명은 다차원적인 경우들에 대해 어떠한 제한없이 항상 적용될 수 있다.The present invention can always be applied without any limitation for multidimensional cases.