United States Patent 19
`Lee
`
`|||||||III
`US005469212A
`5,469,212
`11) Patent Number:
`Nov. 21, 1995
`45) Date of Patent:
`
`54 APPARATUS FOR
`COMPRESSION-ENCODING AND
`DECODING WIDEO SIGNALS
`
`(75) Inventor: Choon Lee, Seoul, Rep. of Korea
`(73) Assignee: Goldstar Co., Ltd., Seoul, Rep. of
`Korea
`
`21 Appl. No.: 43,370
`22 Filed:
`Apr. 6, 1993
`30
`Foreign Application Priority Data
`Apr. 11, 1992 KR) Rep. of Korea .................... 6061/1992
`(51) Int. Cl." ........................................... H04N 7/48
`(52) U.S. Cl. .......................... 348/392; 348/409; 348/412;
`348/424
`(58) Field of Search ..................................... 348/392,409,
`348/412,415, 419,424; H04N 7/137
`
`56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,884,136 11/1989 Ninomiya................................ 348/392
`Primary Examiner-Howard W. Britton
`Attorney, Agent, or Firm-Fliesler, Dubb, Meyer & Lovejoy
`
`ABSTRACT
`(57)
`An apparatus for compression-encoding and decoding digi
`tal video signals, capable of additionally transmitting a
`differential signal indicative of a difference between an
`original video signal and an encoded video signal obtained
`by encoding the original video signal by an existing video
`compression system, so as to efficiently cope with a varied
`bandwidth of a recording medium or a channel. The appa
`ratus comprises an encoding device for encoding an original
`digital video in a sampling manner, encoding a differential
`signal indicative of a difference between each of the original
`video signals and a signal obtained by expanding each
`corresponding one of the encoded original video signals,
`together with edge information, adding the encoded com
`posite differential signal to the encoded original video
`signal, and outputting the resulting signal. The apparatus
`also comprises a decoding device for decoding each of the
`encoded original video signals, reading video signals,
`indicative of video portions including no differential signal,
`from video signals resulting from the decoding of the
`encoded original video signals, based on the edge informa
`tion, adding each of the differential signals to each corre
`sponding one of the read video signals, and outputting
`recovered video signals.
`
`9 Claims, 6 Drawing Sheets
`
`10
`
`CDED SIGNAL
`
`
`
`RIGINAL
`E.
`
`DECIMAIN
`UNIT
`
`ENCODER
`
`EXPAND
`UNI
`
`ENCODER 2
`
`WLC/
`T
`FORMER CHANNEL
`
`
`
`ELAY UNIT DELAYED RIGINAL
`VIDE SIGNAL
`
`40
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 1
`
`

`

`U.S. Patent
`
`Nov. 21, 1995
`
`Sheet 1 of 6
`
`5,469,212
`
`RIGNAL
`VEDECIMATION
`DATA
`UNIT
`
`PRIOR ART
`FIG - 1
`
`
`
`CMPRESSION
`ENCODED
`VIDED DATA
`FROM CHANNEL
`
`DECODED
`VIDED
`DATA
`
`PRIDR ART
`FIG -2
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 2
`
`

`

`U.S. Patent
`
`5,469,212
`
`
`
`
`
`~]</NOIS CIECIDJO
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 3
`
`

`

`Amazon / WAG Acquisition
`Exhibit 1018
`Page 4
`
`

`

`U.S. Patent
`
`Nov. 21, 1995
`
`Sheet 4 of 6
`
`5,469,212
`
`/9
`
`WOdCI
`
`>JIECIDIOTECI
`
`99
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`99
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 5
`
`

`

`U.S. Patent
`
`5,469,212
`
`091
`
`2GI
`
`IGT
`
`TWILNIE? JE + HICI
`
`TºNDIS
`
`
`
`
`
`
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 6
`
`

`

`Amazon / WAG Acquisition
`Exhibit 1018
`Page 7
`
`

`

`APPARATUS FOR
`COMPRESSION-ENCODNG AND
`DECODING WIDEO SIGNALS
`
`10
`
`15
`
`20
`
`25
`
`30
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates to an apparatus for com
`pression-encoding and decoding digital video signals, and
`more particularly to an apparatus for compression-encoding
`and decoding digital video signals, which intends to recover
`fine information disappearing upon interpolating a digital
`video compressed by a decimation and to enable a circuit at
`the receiving side to be efficiently designed.
`2. Description of the Prior Art
`Generally, compression of digital video signals means
`that a great quantity of video data is efficiently converted
`into a small quantity of video data to meet the recording
`bandwidth of a recording medium or a channel, although
`there may be a degradation in picture quality of an original
`video.
`As conventional video compression techniques, various
`coding methods have been known, which include a trans
`form coding method, a predictive coding method, a hybrid
`coding method, a vector quantization method, and a sub
`band coding method. Recently, such video compression
`techniques have been making fast progress. In particular, as
`they have been applicable to technical fields such as ISDNs
`and multimedia, international standards relating to the video
`compression have been continuously reported.
`For example, the international standard so called a mov
`ing picture experts group (MPEG) for recording a com
`pressed video on a digital recording medium such as a
`CD-ROM is currently extending.
`In accordance with this MPEG standard, it is possible to
`achieve an encoding at a high compression ratio, using
`methods such as a discrete cosine transform (DCT), a
`motion estimation (ME) and a variable length coding
`(VLC).
`Referring to FIG. 1, there is illustrated a conventional
`device for compression-encoding video signals. As shown in
`FIG. 1, the compression encoding device comprises a deci
`mation unit 1 for reducing the amount of data for an original
`video in a sub-sampling manner, a first encoding unit 2 for
`encoding output data from the decimation unit 1 to compress
`it, and a VLC/formatter 3 for compression-formatting an
`encoded signal from the first encoding unit 2 in a VLC
`act.
`50
`On the other hand, FIG. 2 illustrates a conventional device
`for decoding compressed video signals. This decoding
`device comprises a decoder 4 for receiving compression
`encoded video data and decoding it, and an expand unit 5 for
`expanding video data decoded in the decoder 1.
`Operations of these devices for compression-encoding
`video signals and decoding them will now be described.
`As an original digital video signal is received in the
`compression encoding device, the amount of data thereof is
`reduced in the decimation unit 1, in a sub-banding coding
`manner. Thereafter, the video data reduced in data amount is
`encoded in the first encoding unit 2 to be compressed. The
`compression-encoded signal is then formatted in the VLC/
`formatter 3, in a variable length coding manner, so as to be
`compressed at a higher rate. This compressed video data is
`recorded on a recording medium or transmitted via a trans
`mitting medium.
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`5,469,212
`
`2
`On the other hand, when a signal obtained by reproducing
`the signal transmitted from the video signal compression
`encoding device or recorded on the recording medium is
`received in the decoding device, it is decoded in the decoder
`4 and then expanded to the size of the original video signal,
`in the expand unit 5, so as to be recovered.
`The first encoding unit 1 utilizes high technical video
`compression techniques, so as to transmit video data with a
`proper size and a proper amount within a certain limited
`bandwidth. For example, video compression techniques
`which are regarded as optimum ones for respective channels
`are selected in various fields such as HDTV fields, digital
`VCR fields, and multimedia fields.
`Where a higher compression ratio is desired, in spite of a
`degradation in picture quality, a device such as the decima
`tion unit 1 is used. In this case, there is used a method for
`reducing a video in size in the sub-sampling manner and
`then compressing it. When this method is used, fine infor
`mation of the video disappear during when the size of video
`information is optionally reduced.
`In cases of video data compression methods used in
`HDTV digital VCRs and digital broadcasting satellites
`(DBSs), the use of the decimation unit 1 is eliminated so that
`an original video subjected to no sub-sampling is compres
`sion encoded, in order to generate a video signal with a
`certain limited bandwidth. In this case, there are various
`problems relating to the data amount.
`Each of the above-mentioned video data compression
`techniques are designed for one selected channel or record
`ing medium. If a new application requiring a larger band
`width is made, an optimum video data compression tech
`nique will be newly developed. However, such a video data
`compression technique newly developed may have no rela
`tion with the known video data compression techniques. In
`this case, there is a problem about a compatibility to systems
`using the known compression techniques. For example, it is
`impossible to utilize the new compression technique in
`systems using the known compression techniques, since a
`new decoding technique should be used, in order to decode
`a video signal encoded according to the new compression
`technique. Furthermore, a new system to which a new
`decoding technique is applied can not decode video data
`encoded according to the known compression techniques.
`Due to such a problem about compatibility, the manufac
`turers need a long time for developing new systems. On the
`other hand, the consumers bear expenses for purchasing the
`systems. As a result, there is also a problem of requiring a
`long system replacement time for enabling a commercial use
`of more efficient video processing systems meeting new and
`larger bandwidths.
`Until an optimum video compression technique is devel
`oped, it is necessary to provide compression encoding/
`decoding devices capable of being applied to new band
`widths and yet minimizing an alternation of existing
`systems, even though they exhibit a slight degradation in
`picture quality.
`
`SUMMARY OF THE INVENTION
`Therefore, an object of the invention is to provide an
`apparatus for compression-encoding and decoding digital
`video signals, which is capable of additionally transmitting
`a differential signal indicative of a difference between an
`original video signal and an encoded video signal obtained
`by encoding the original video signal by an existing video
`compression system, so as to efficiently cope with a varied
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 8
`
`

`

`5,469,212
`
`3
`bandwidth of a recording medium or a channel, and of
`having a compatibility with existing systems and yet mini
`mizing alternations in existing devices for compression
`encoding and decoding video signals, so as to enable a
`commercial use thereof in a short time.
`In accordance with the present invention, this object can
`be accomplished by providing an apparatus for compres
`sion-encoding and decoding digital video signals compris
`ing: encoding means for encoding an original digital video
`in a sampling manner to produce encoded original video
`signals, encoding a differential signal indicative of a differ
`ence between each of said original video signals and a signal
`obtained by expanding each corresponding one of said
`encoded original video signals, together with edge informa
`tion, to produce an encoded composite differential signal,
`adding said encoded composite differential signal to the
`encoded original video signal, and outputting the resulting
`signal; and decoding means for decoding each of the
`encoded original video signals and each corresponding one
`of the differential signals encoded in said encoding means
`and then received via a transmitting medium or played back
`from a recording medium, reading video signals, indicative
`of video portions including no differential signal, from video
`signals resulting from said decoding of the encoded original
`video signals, based on the edge information, adding each of
`the differential signals to each corresponding one of said
`read video signals, and outputting recovered video signals.
`In accordance with the present invention, the encoding
`means comprises a decimation unit for reducing the size of
`each of said original digital video signals in a sub-sampling
`manner, a first encoder unit for encoding each of signals
`subsampled by said decimation unit to video information
`proper to a limited bandwidth of said recording medium or
`said transmitting medium, an expand unit for expanding a
`signal from said first encoder unit up to the size of each
`original video signal, in reversely proportional to the reduc
`tion achieved by the decimation unit, a delay unit for
`delaying each original video signal for a predetermined time
`during which the original video signal is processed through
`the decimation unit, the first encoder unit and the expand
`unit, an adder unit for calculating a difference between each
`original video signal delayed by said delay unit and each
`corresponding expanded signal from the expand unit, a
`second encoder unit for encoding a differential signal from
`said adder unit, and a VLC/formatter unit for encoding a
`signal from said second encoder unit in a variable length
`coding and formatting it to send the resulting signal to a
`channel of the transmitting medium or the recording
`medium.
`The decoding means comprises a demultiplexor unit for
`receiving each of said encoded video signals from said
`encoding means via said transmitting medium or said
`recording medium, demultiplexing it to separate each cor
`responding composite differential signal therefrom and out
`putting them, a first decoder unit for decoding said separated
`encoded video signal from said demultiplexor unit and
`outputting it, an expand unit for expanding a decoded signal
`from said first decoder unit and outputting it, a frame
`memory unit for storing an output signal from said expand
`unit, a delay unit for delaying said separated encoded
`composite differential signal from the demultiplexor unit for
`a predetermined delay time, a second decoder unit for
`decoding the differential signal delayed by said delay unit
`and generating an address for reading a video signal indica
`tive of each of portions of the video stored in said frame
`memory unit, other than white video portions, and an adder
`unit for adding said differential signal decoded by said
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`10
`
`15
`
`20
`
`25
`
`30
`
`4
`second decoder unit to said read video signal outputted from
`the frame memory unit according to said address of the
`second decoder unit and outputting a decoded video signal.
`The second encoder unit comprises an edge detector for
`detecting information about edges of each of said original
`video signals, an edge information memory for storing said
`edge information detected by said edge detector, a Quadtree
`encoder for generating a control signal for controlling an
`encoding for each of said differential signals from said adder
`unit and encoding the edge information in a Quadtree
`manner, a differential signal encoder for receiving the dif
`ferential signal from the adder unit via a switch and encod
`ing it, a formatter for multiplexing the edge information
`encoded by said Quadtree encoder and the differential signal
`encoded by said differential signal encoder and outputting an
`encoded composite differential signal, and a threshold cal
`culator for receiving a bit count value obtained by counting
`the number of bits of said encoded differential signal from
`the differential signal encoder, varying a threshold for an
`edge detection, in reversely proportional to said bit count
`value and sending said varied threshold to the edge detector.
`The second decoder unit comprises a demultiplexor for
`separating said edge information and said differential signal
`from each of said composite differential signals including
`the edge information, a Quadtree decoder for decoding said
`Quadtree-coded edge information from said demultiplexor,
`an address generator for generating an address for reading a
`video signal indicative of each of portions of the video
`stored in said frame memory unit, other than white video
`portions, based on said edge information decoded in said
`Quadtree decoder, a switch for permitting outputting of said
`DPCM-coded differential signal from demultiplexor under a
`control of the Quadtree decoder, and a differential signal
`decoder for recovering the differential signal received
`through the switch.
`The encoding/decoding apparatus according to the
`present invention can be applied to all types of video
`encoding/decoding system, differently from conventional
`devices. The encoding/decoding apparatus according to the
`present invention require only a simple hardware and enable
`its use with existing encoding/decoding devices in a parallel
`manner. Accordingly, it is applicable to most technical fields
`utilizing the video compression. For example, the apparatus
`can be applied to the MPEG standard having a bit rate of
`1.15 Mbps, at a bandwidth increase of about 5 nbps. The
`present invention also makes it possible to apply video
`encoding/decoding devices of the NTSC grade to the band
`width of the HDTV grade. This provides an effect of
`maintaining the compatibility with the lower-grade format.
`BRIEF DESCRIPTION OF THE DRAWINGS
`Other objects and aspects of the invention will become
`apparent from the following description of embodiments
`with reference to the accompanying drawings in which:
`FIG. 1 is a block diagram of a conventional device for
`compression-encoding video signals;
`FIG. 2 is a block diagram of a conventional device for
`decoding compressed video signals;
`FIG. 3 is a block diagram of a device for compression
`encoding video signals according to the present invention;
`FIG. 4 is a block diagram of a device for decoding
`compressed video signals in accordance with the present
`invention;
`FIG. 5 is a block diagram of a second encoder unit
`included in the device shown in FIG. 3;
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 9
`
`

`

`5,469,212
`
`S
`FIG. 6 is a block diagram of a second decoder unit
`included in the device shown in FIG. 4; and
`FIG. 7 is a schematic view explaining a Quadtree encod
`ing in accordance with the present invention.
`
`6
`demultiplexing it to output the video signal and the com
`posite differential signal separated from each other, a first
`decoder unit 120 for decoding the encoded video signal from
`the demultiplexor unit 110 and outputting it, an expand unit
`130 for expanding a decoded signal from the first decoder
`unit 120 and outputting it, and a frame memory unit 160 for
`storing an output signal from the expand unit 130 therein. A
`delay unit 140 is also provided, which is adapted to delay the
`encoded composite differential signal from the demulti
`plexor unit 110 for a predetermined delay time. The decod
`ing device also comprises a second decoder unit 150 for
`decoding the differential signal delayed by the delay unit 140
`and generating an address for reading a video signal indica
`tive of a portion of the video stored in the frame memory unit
`160, other than white video portions, and an adder unit 170
`for adding the differential signal decoded by the second
`decoder unit 150 to the video signal outputted from the
`frame memory unit 160 according to the address of the
`second decoder unit 150 and outputting a decoded video
`signal.
`FIG. 6 is a block diagram of the second decoder unit 150
`shown in FIG. 4. As shown in FIG. 6, the second decoder
`unit 150 comprises a demultiplexor 151 for separating the
`edge information and the differential signal from the com
`posite differential signal including the edge information, a
`Quadtree decoder 152 for decoding the Quadtree-coded
`edge information from the demultiplexor 151, and an
`address generator 153 for generating an address for reading
`a video signal indicative of a portion of the video stored in
`the frame memory unit 160, other than white video portions.
`A switch 154 is also provided, which permits outputting of
`the DPCH-coded differential signal from demultiplexor 151
`under a control of the Quadtree decoder 152. The second
`decoder unit 150 also comprises a differential signal decoder
`155 for recovering the differential signal received through
`the switch 154. In the illustrated case, the differential signal
`decoder 155 is a DPCM decoder and so will be referred to
`as the DPCM decoder.
`Now, operations of the devices according to the present
`invention will be described, in conjunction with FIGS. 3 to
`7.
`When an original digital video signal is received in the
`encoding device shown in FIG. 3, it is subjected to a
`sub-sampling process by the decimation unit 10 so that its
`size is reduced. The size-reduced signal is compression
`encoded in the first encoder unit 20 and then expanded in the
`expand unit 30. The resulting expanded signal is applied to
`the adder unit 50 which also receives the original video
`signal delayed one frame by the delay unit 40. In the adder
`unit 50, a differential signal indicative of the difference
`between the expanded signal and the delayed original video
`signal. The differential signal is encoded in the second
`encoder unit 60. The differential signal encoded by the
`second encoder unit 60 and the signal encoded by the first
`encoder unit 20 are compression-formatted in a variable
`length coding manner, in the VLC/formatter unit 70 from
`which the resulting signal is sent to a channel of a trans
`mitting medium or a recording medium.
`The operation of the second encoder unit 60 will now be
`described in detail, in conjunction with FIG. 5. The edge
`detector 61 finds edge information about the original video,
`so as to encode fine information of the original video. As the
`edge detector 61, a sobel edge detector is used, which has an
`advantageous robustness for noise. The edge detector 61
`detects edges of the original video, based on a threshold
`received from the threshold calculator 64 and outputs posi
`tion information therefor. This position information about
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`FIG. 3 is a block diagram of a device for compression
`encoding video signals according to the present invention.
`As shown in FIG. 3, the compression encoding device
`comprises a decimation unit 10 for reducing the size of an
`original digital video signal in a sub-sampling manner, a first
`encoder unit 20 for encoding a signal sub-sampled by the
`decimation unit 10 to video information proper to a limited
`bandwidth of a recording medium or a transmitting medium,
`and an expand unit 30 for expanding a signal from the first
`encoder unit 20 up to the size of the original video signal, in
`reversely proportional to the reduction achieved by the
`decimation unit 10. A delay unit 40 is also provided, which
`is adapted to delay the original digital video signal for a
`predetermined time during which the original video signalis
`processed through the decimation unit 10, the first encoder
`unit 20 and the expand unit 30. The compression encoding
`device also comprises an adder unit 50 for calculating a
`difference between an expanded signal from the expand unit
`30 and the original video signal delayed by the delay unit 40,
`a second encoder unit 60 for encoding a signal from the
`adder unit 50 indicative of the difference, namely, a differ
`ential signal, and a VLC/formatter unit 70 for encoding a
`signal from the second encoder unit 60 in a variable length
`coding and formatting it to send the resulting signal to a
`channel of a transmitting medium or a recording medium.
`As shown in FIG. 5, the second encoder unit 60 comprises
`an edge detector 61 for detecting information about edges of
`the original video signal and an edge information memory
`62 for storing the edge information, indicative of the number
`of edges and each edge position, detected by the edge
`detector 61. A Quadtree encoder 63 is also provided, which
`is adapted to generate a control signal for controlling an
`encoding for the differential signal from the adder unit 50
`and encoding the edge information in a Quadtree manner.
`The second encoder unit 60 also comprises a differential
`signal encoder 66 for receiving the differential signal from
`the adder unit 50 via a switch 65 according to the control
`signal when the number of detected edges is not less than a
`predetermined reference value and encoding the received
`differential signal, a formatter 67 for multiplexing the edge
`information encoded by the Quadtree encoder 63 and the
`differential signal encoded by the differential signal encoder
`66 and outputting an encoded composite differential signal,
`and a threshold calculator 64 for receiving a bit count value
`obtained by counting the number of bits of the encoded
`differential signal from the differential signal encoder 66,
`varying a threshold for an edge detection, in reversely
`proportional to the bit count value and sending the varied
`threshold to the edge detector 61. In the illustrated case, the
`differential signal encoder 66 is a differential pulse coded
`modulation (DPCM) encoder and so will be referred to as
`the DPCM encoder.
`On the other hand, FIG. 4 is a block diagram of a device
`for decoding compressed video signals in accordance with
`the present invention.
`As shown in FIG. 4, the decoding device comprises a
`demultiplexor unit 110 for receiving encoded video signal
`from the channel of the encoding device of FIG. 3 and
`
`10
`
`5
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 10
`
`

`

`5,469,212
`
`O
`
`15
`
`8
`lated. Thereafter, the resulting histogram with Laplacian
`distribution is subjected to a quantization, so as to obtain
`quantized levels. These quantized levels are stored to form
`a table which includes the quantized levels classified into a
`plurality of groups. The t, able is used upon the DPCN
`encoding operation.
`Thereafter, the edge position information signal
`Quadtree-encoded in the Quadtree encoder 63 and the
`differential signal DPCM-encoded in the DPCM encoder 66
`are multiplexed by the formatter 67 in the following manner.
`For example, assuming that '00', '01" and '10' are
`Quadtree codes for a black block B, a white block W and a
`gray block G, respectively, a video shown in FIG. 7 is
`scanned from its left uppermost end, in clockwise. By the
`scanning, the black portion B, and the gray portion G are
`encoded to "00 and '10, respectively. The gray portion G is
`also partitioned into four blocks which are, in turn, scanned
`from the left uppermost end, in clockwise. The white portion
`W is encoded to "01". A differential signal of each pixel in
`the white portion W is DPCM-encoded. The white portion
`Wis a block determined to have the number of edges not less
`than a predetermined threshold, that is, a large amount of
`fine information.
`In this case, the DPCM codes are assumed to be of four
`bits. Also, the Quadtree-encoding direction is assumed to be
`clockwise. That is, the encoding is carried out in a recursive
`manner, according to the order of the left upper block, the
`right upper block, the right lower block, and the left lower
`block.
`At this time, the formatter 67 counts the number of bits of
`the encoded differential signal from the DPCM encoder 66
`and then send a bit count signal to the threshold calculator
`64 which, in turn, varies the threshold for the edge detection,
`in reversely proportional to the bit count value.
`This operation will now be described in detail.
`The amount of bits encoded by the second encoder unit 60
`of FIG. 5 is not varied, depending on the kind of frame (that
`is, an intraframe coding or an interframe coding). It is fixed
`for frames to meet a target rate.
`For example, when the target rate and the frame rate are
`a bits/sec and 30 Hz, respectively, the number of bits
`allocated in each frame is a/30 bits. This bit number can be
`controlled, using the edge detector 61 of FIG. 5.
`That is, as the amount of edge information is control led
`by varying the threshold for the edge detection, the number
`of allocated bits. However, this method is difficult to meet
`the number of allocated bits precisely.
`Where the number of bits of a differential signal encoded
`in the above-mentioned manner is less than the number of
`allocated bits, it is stuffed with dummy bits corresponding to
`the shortage of bits. On the other hand, when the number of
`bits of the differential signal is less than the number of
`allocated bits, the surplus bits are cut off.
`The threshold calculator 64 calculates thresholds for next
`frame, based on the bit count value obtained by continuously
`counting the number of encoded bits in the present frame.
`Such a calculation can be expressed by the following
`equations:
`
`7
`the detected edges outputted from the edge detector 61 is
`stored in the edge information memory 62. The edge posi
`tion information stored in the edge information memory 62
`is sent to the Quadtree encoder 63 in which it is encoded by
`video portions.
`That is, the Quadtree encoder 63 partitions continuously
`the video into four blocks until the video is partitioned into
`blocks of the minimum size. The partition operation of the
`Quadtree encoder 63 is repeated according to the edge
`information about the video. The condition for partitioning
`the video into four blocks will now be described.
`When the number of edge information in an optional
`block from the same-sized blocks obtained by partitioning
`the video is less than a first predetermined threshold t-black,
`it is determined that the block has no fine information. In this
`case, the switch 65 is switched to its OFF state and prevents
`the differential signal from passing therethrough. When the
`number of edge information in the block is more than a
`second predetermined threshold t-white, it is determined that
`the block has sufficient fine information. In this case, the
`switch 65 is switched to its ON state so that all pixels for the
`block is encoded in a DPCM manner, by the DPCM encoder
`66.
`On the other hand, when the number of edge information
`is not less than the first predetermined threshold t-black, but
`not more than the second predetermined threshold t-white, it
`is determined that the block has more or less edge informa
`tion. In this case, the block is partitioned into four blocks,
`each of which will be repeatedly subjected to the above
`process.
`The two thresholds t-black and t-white needed in the
`Quadtree encoder 63 are defined in the following manner.
`Assuming that one video block has a longitudinal length
`X and a lateral length Y and the number of Quadtree levels
`is four,
`the size of the first Quadtree level is X* Y,
`the size of the second Quadtree level is (X/2) * (Y/2),
`the size of the third Quadtree level is (X/4) * (Y/4), and
`and
`the size of the fourth Quadtree levelis (X/8) * (Y/8). That
`is, each lower level size is reduced in the number of
`pixels at a rate of 4, as compared with the just higher
`level size. Accordingly, it is required to adjust the
`thresholds so that they meet the reduction rate.
`For example, when the thresholds t-black and t-white of
`the first Quadtree level are t and t, respectively, the
`thresholds at the second Quadtree level become t/4 and t?4,
`the thresholds at the second Quadtree level become t116 and
`t/16, and the thresholds at the second Quadtree level
`become t/64 and t?o4.
`When the Quadtree encoder 63 determines that a suffi
`cient amount of white portions, namely, fine information are
`present in a block of a certain level, it sends a control signal
`to the switch 65, so as to switch the switch 65 to its ON state.
`Accordingly, the DPCM encoder 66 encodes respective
`differential signals from all pixels in the blocks determined
`to have a sufficient amount of fine information, in the DPCM
`coding manner.
`As the DPCM coding method, a nonlinear quantization
`method is used, in accordance with the present invention.
`The nonlinear quantization utilizes a test video, to obtain a
`histogram for a differential signal indicative of a difference
`between an original video portion corresponding to the
`white portion of the test video and a video portion obtained
`by encoding the original video portion and then recovering
`it. From the obtained histogram, a variance is also calcu
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`T +o,
`T+1 = Tin,
`T - 0,
`
`if N > af30
`if N = af30
`if N Caf30
`
`wherein, Trepresents a threshold for edge in the n-th frame,
`T represents a threshold for edge in the n+1-th frame, and
`N represents the number of bits for the n-th frame. That is,
`
`Amazon / WAG Acquisition
`Exhibit 1018
`Page 11
`
`

`

`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`a predetermined value O is added to or deducted from the
`threshold, depending on the number of bits N.
`Accordingly, the edge detector 61 detects edge informa
`tion of the video, based on the varied