Note: Descriptions are shown in the official language in which they were submitted.
~3222~
METHOD AND SYSTEM FOR COMPRESSING AND DECOMPRESSING
DIGITAL COLOR VIDEO STATISTICALLY ENCODED DATA
BACKGROUND OF THE INVENTION
_
Field o~ the Invention:
This in~ention relates ~enerally to information
signal processing, and in particular to the field of
processing time sequential information signals, such as
video signals, for the purpose of reducing the amount of
mformation ~o be transferred from an encoding site to a
decodinq site. A particular use of the invention is in
the communication of color video data over telephone
~nes.
Prior Art:
Encoding of digital television signals
ordinarily requires a transmission rate of approximately
200 Mbits/s. Recent developments in coding systems have
permitted the transmission rate to be cut to less than 2
Mbits~s. Coding systems using block oriented analysis of
video picture frames and processing by a conventional
hybrid discrete cosine transform (DCT) coefficient permi~
tr
pixels and the length of the sequence of pixels having
~hat value or range o~ valuas. The values may be a
measure of the amplituda of a video signal, or other
properties of such video signals, such as luminance or
chrominance. An example of a system which utilizes run
length coding of amplitude of video signals is U. S.
Patent No. 3,609,244 (Mounts). In that system, a frame
memory also determmes frame to frame differences, so
~hat only those g o~ Monochrome and Color Images", IEEE
Transactions on Communications, Vol. COM-25, Mo. 11,
November 19, 1977. However, information transmitted at
such low data rates seriously affects the ability to
.~
.~
.,
.
~32~2~
reconstruct a sufficient number of ~ra.mes per second so
~hat a real time picture is acceptable to a viewer. High
capaity telephone l~nes are ava~lable which will carry
transmissions at a rate of up to 1.544 Ml~i~s~s, but such
lines are extremaly expensive at a dedicated use rate,
and are still qui~e expensive at a scheduled use rate.
Lower capacity telephone linas are available which permit
transmission at rates o~ up to 56 Kbits/s and 64
Kbits/s. Rel tlvely expensive video digital and coding
devices are commercially available which will transmi~ a
video signal at 56,000 bits par second, so that it is
necessary to utilize a combination of a device of this
nature with the high capacity 1.544 Mbitq/s t:elephone
~ne to allow a framLng speed much faster than about one
frame per second. The current transmission rate limi~ of
ordinary telephone lin~s approaches 18,000 bits per
second, so that transmission of real time sequencing of
video pictures o~er ordinary telephone lines has been
viewed in the prior art a~ not being feasible.
Various schemes for reducm g the amount of
redundancy of information to be transmitted in a digital
video signal have been used. one technique is to utiliza
a slow scan camera: and another technique is to transmi~
every nth scanning line for each frame. Another tech
nique involves the sending of only those parts of a
picture frame which are deemed to be important or to hav~
changed in some significant manner, by dividing the
picture frame into a number of segments or blocXs which
are typically 3X3 or 4X4 groups of pixels, and analyzing
the content o~ the blocXs. Th~se techniques tend to also
raduce the resolution o~ the video picture.
Another tachnique in the reduction of transmis
sion ti~e which does not d~crease the r2solution of a
picture transmitted is run length encoding. In run
length encoding, the scan lines of a picture frame are
encoded as a value of the color content of a series of
13222~0
3 --
pixels and the length of the sequence of pixels having
that value or range of values~ The values may be a
measure of the amplitude of a video signal, or other
properties of such video signals, such as luminance or
chromlnance. An example of a system which utilizes run
langth coding of amplitude of video signals is U. S.
Patent No. 3,609,244 (Mounts)O In thak system, a frame
memory also determ~nes frame to frame differenc:es, so
that only those di~ferences from one frame to the next
are to be ~ransmi~ted. Another example of a raethod for
transmit~ing video signals as compressed run length
values which also utilizes statistical coding of frequPnt
values to reduce the number of bits required to represent
data is U. S. Patent No. 4,420,771 (Pirsch).
Id~ally, compression o~ color video in~ormation
to allow real time sequenc1ng of picture frames at a ra~e
o~ up ~o 1~ frames per second, and at bit rates as low as
ll,SOo bits per second would be desirable, to allow the
communication of color video data over ord~nary t~lephon~
lin~ A vid~o data compression syE;tem able to achieve
equivalent data transmission rates a~ systems using
higher quality telephone l~nes with more efficient and
le~s costly equipment than is currently available would
also be desirable.
SUMM ARY O F THE INVENTION
The present ~nvention provides for a method and
sy~tem for compressing digi~al color video data in a
video communication system, for tra~smi~ting a plurality
of video picture frames ~rom digi~ized color video
signals in the form of run lengths and three digital
cQlox components. Up to a predeterm~ned number of the
mo~t visually significant combinations of the color
component:s in at least a portion of the pic~ure frame are
determined, and the digital color components in the
" ~ 3222~0
picture are encDd~d into a lo~k up table of digitally
compressed color codes which are also encoded along with
associated run lengths.
The present invention also provides for a method
and system of decompressing color video data in a video
communication system which utilizes a plurality o~
digi~ized signals represent~ng p~xel r~n lengths and
digitally ::ompressed color component codes, and a look up
table of the digitally compressed color component codes
for three corresporlding digital color components. The
digitally compre~sed color codes are decoded according to
the look up table to form a table of the three digi~al
color components for ea ::h of tha run lengths, and the run
lengths and corresponding color components axe s-tored in
an array in a bu~fer memory to represent run length and
color component data for the scan lines in a video pic-
ture frame. once this da~a is decoded in this fashion,
~he data can be further decompressed to represent indivld~
ual pix ls in the pic:ture~
Brie~ly and in gener~l terms, the me~hod of
compr~3ss~ng digital color video data utilizes a digitized
color video signal hav~ng three digi~al color components
and a run length component, wi~h the run length being of
a first digital word size, and the three digital color
components being of second, third and fourth word sizes,
respectively~ The st¢ps of the method comprise deter~
mining a histogram o:f up to a predetermined number of the
most visually significant com~inations of the color
components in at least a portion of the pichlre frame:
encodirlg all of the dlgital color c:omponents in the
picture frame to a lon3c up table as compressed color
code~ of the most visually signiPicant color combinations
of a fl~th digital word size which is s~aller than the
sum of the second, third and fourth digital word sizes;
and encoding a plurali~y of nln lengths and th~ digi~ally
compres~ed color cod~5 representing at least a port ' on of
.
.
: ' :
the picture frame. The method for decompressing khis
compressed digital color ~.ideo data generally comprise~
decoding the digital compressed color component codes
according to the look up table to form a table o~ the
three digital color components corresponding to each run
length; and storing at least a portion of the run length
and corresponding color components in an array in a
memory buffer means sf run length and color component
data, representing thP scan lines in the video picture
frame .
The ~ystem for compressing digital color video
data is fox use in a video communication system for
transmitting a plurality of video picture frame~9
utilizing a digitized color video signal having three
digital color components and a run length portion, with
the run length portion being o~ a first digi~al wsrd
size, and the three digital color components beinq of
second, third, and fourth digital word sizes, respec~
tively.G- The data compression sy~tem briefly arld
generally comprises means for determining a histogram of
up to a prpdetermLned number of the most visually
signifirant combinations of the color compone~ts in at
least a portion o~ the pictur~ ~rame. Also included in
data compression system are means ~or encoding all o~
the digital color cc~mponents ~n th~ picture frame to a
look up tabl2 of digitally compressed color codes of the
most visually significant color comhinations of a fifth
digital word size which is smaller than the sum o~ the
s~cond, third and fourth digital word sizes; and means
for encoding a plurality of run lengths and associated
digitally compressed color codes which represent at least
a portion of the picture ~rame. ~ The sy~tem of the
in~ention for decompressing this compressed digital color
video data brie~ly and generally comprises means for
decoding tha digitally compressed color component codes
according to the look up table of the thr~e digital color
~222~0 6294~ 121
components for each run length, said three decoded color component
codes having third, fourth and fifth diyital word sizes,
respectively; and means for storing at least a por~ion of the run
length and corresponding co]or components in an array in a memory
buffer of run length and color component data to represen~ the
plurality of scan lines in the video picture frame.
In a preferred embodiment, adjacent run lengths on each
scan line for which ~he adjacent run lengths have associated color
components which vary less than a predetermined amount are
concatenated to a ~ixth digital word siæe which may be larger than
the first diyital word size of the run len~ths. Either or bokh o~
the run length portion and the compressed color component cocle
portion of the combinations of run lenyth compressed color codes
are preferably stakistically encoded by determining the frequency
of occurrence of values of either or both portions. A plurality
of differerlt code tables are provided. The most fre~uent
occurrence of values in a portion is statistically encoded in a
first code table by a one bit size digital word. The next three
most frequent occurrences are selected and encoded in a second
code table by a two bit digital size word, and all of the other
values are likewise encoded in at least one additional code table
b'I a digital word size laryer than two bits. Provision is also
made for optionally encodiny line-to-line differences, frame-to~
frame differences, and determining and encoding movement o~
diskinc~ive edges of sequences of combinations of run lenyths and
compressed color codes from frame-to-frame.
In accordance with the present invention there is
provided a method of compressing digital color video data in a
.. ,, ~ , .
'
~32224~
6a 62~48-121
video communica~ion system for transmitting a plurality of video
picture frames, with each picture frame comprising a plurality of
scan lines composed of a plurality of pixels, utiliæing a
digitized color video signal having three digital color
components, said systern includiny means for determining a
luminance function for each pixel, means for determining which of
said pixels on each scan line represent decision points based upon
said luminance function, and means for encoding at least a portion
of said plurali~y of pixels in each scan line as a plurality of
combinations of run lengths and said three digital color
components, said run length being of a first digital word size,
and said ~hree digi~al color components being of second, thircl and
fourth digital word sizes, respeckively, comprising the steps of:
a) encodi.ng all of said digital color components in said
~- picture frame according to a look up table in a memory means of
digitally compressed color codes of the most visually signiflcant
color combinations of a fifth digital word size smaller than the
sum of said second, third and fourth digital word sizes; and
: b) encotling a plurality of run langths and said digitally
compressed color codes representing at least a portion of said
picture frame in said memory means.
In accordance with the present invention there is
further provided a system for compressing digital color video data
in a video communication system for transmitting a plurality of
: video picture frames, with each picture frame comprising a
plurality of scan lines composed of a plurality of plxels,
utilizing a digitized color video signal having three digital
~ color components, said video communication system including means
:
'~
, .
;
~3222~
6b 62948-121
for determinlny a luminance functi.on for each pixel, means for
determining wh:ich of said pixels on each scan line represent
decision points based upon said luminance furlction, and means for
encoding at least a portion of said plurality of pixels in each
scan line as a plurality of combinations of run lengths and said
t.hree digital color components in a memory means, said run length
being of a first digital word size, and said three digital color
components being of second, third, and fourth digital word sizes,
respectively, said sys~em of compressing digital color video data
comprising:
a~ means for encoding all of said digital color
components in said picture frame according to a look up table in a
memory means of digitally compressed color codes of the most
visually significant color combinations of a fifth digital word
size smaller ~han ~he sum of said second, third and fourth digital
word s.izes~ and
b) means for encoding a plurality oi run lengths and
said digitally compressed color codes representing ~t least a
portion of said picture frame in said memory means.
In accordance with the present invention there is also -
provided a method for decompressing digital color video data in a
video communication system utilizing a plurality of digitized
~ignals representing combinations of a plurality of run l~ngth of
a first digital word size and digitally compressed color component
codes of a second digital word size for at least a portion oi a
plurality of scan lines of a video picture frame, and a look up
table of said diqitally compressed color componen~ codes for three
correspond.ing digital color components, said method comprising the
' .'. ~
~32224~
6c 62948-121
steps of:
a) decoding said digitally compressed color component codes
according to said look up table to form a ~able in a memory means
of said three digi~al color components for each said run length,
said three decoded color components having ~hird, fourth, and
fifth digital word sizes, respectively; and
b~ storing at least a portion of said run length and said
corresponding color components in an array in a buffer memory
means of run lenyth and color component da~a representing said
plurality of scan lines in said video picture frame.
In acco~dance with the present invention there is
provided a system for decompressing digital color video data in a
video communication system utilizing a plurality of digitized
signals representlng combinations of a plurality of run length and
digitally compressed color component codes ~or at least a portion
of a plurality of scan lines of a video picture frame, and a look
up table for said digitally compressed color component codes, said
run length being of a first digital word size, and said compressed
color component codes being o~ a second digital word size,
respectively, comprising:
a) means for decoding said digitally compressed color
component codes according to said look up table to form a table in
a memory means of said three digital color components for each
said run length, said three decoded color components having third,
fourth, and fifth digital word sizes, respectively; and
b) means for storing at least a portion of said run length
and said corre.sponding color components in an array in a buffer
memory of run length and color component data representing said
;'''~
` A
~322`2~
6cl 62
plurality of scan llnes in s~ld ~ideo picture ~rame.
Other a~pects and advantayes o~ the inventiorl will
become apparent from the follo~ing detailed description and the
accompanying drawings illustrating by way of example the features
of the invention.
" ~
.
~7322~4~
BRIE F DES CRIPTION o F THE DRA~INGS
FIGURE 1 is a schematic diagram of the system
and m~thod for compressing color video data in a video
communication system;
FIG. 2 is a luminance plot across one scan lin~
~n a video picture:
FIG. 3 shows a run length repres~ntation of
features in a video scan line:
FIG. 4 shows a run length r~presentation o~
transitions about slope decision points o~ a video scan
line;
FIG~ 5 shows a representation of the recon-
structed video scan line ~or display;
FIG. 6 shows a representation o~ how the run
lPngth data is converted to display data with transitions
between runs; and
FIG. 7 is a schematic diagram of a method and
system for decompresslng color video data in a video
communication system;
FIG. 8 shows the system and method for com-
pressLng color video data in a video communication system
Lnclud1ng an additional procecsor subsystem;
FIG. 9 is a more detailed schematic diagram of a
co~bLned I/O control section, processor sec~ion, and
~nput ce~nstruction engine and reronstruction eng~ne:
FIG. 10 is ~ flow diagra~ illustra~ing the
compre56ion of digital word sizes of run length and colox
components;
FIG. 11 is a flow chart illustrat m g the addi-
tional signal processing of color video data;
FIG. 12 shows the system and method ~or dec:om-
pressing the color video data ln a video communication
system includLng an additional processor subsy~tem;
: FIG. 13 is a flow dia~ram of the dç~coding of the
addi~ional data compression processing from Fig. 11:
'
.
~3~22~0
~ 8
FIG. 14 is a fl4w diagram illustrating the
decompress1on of the processed digital words of run
length and color co~ponents of Fig. 10; and
FIG. 15 is an illustxatien of a three-dimen-
sional color cube.
DETAILED DESCRIPTION OF THE INVENTION
As is shown in the drawings for purpos~s o~
~lustration, the inv~ntion is embodied in a method and
sy~te~ for compressing digital color video data in a
video communication system for transmitting a plurality
of video picture fram~s. Each picture frame comprises a
plurality o~ scan lines composed o~ a plurality of
p1xels, and the digitized color video signal which is
used has three digital color components and a run length
por~ion, the run length portion being of a first digi~al
word size, and the three digltal color components being
o~ second, third and fourth digi~al word sizes, respec-
tively. A histogram is created of up to a predetermined
number of the most vi~ually significant combinations o~
the color co~ponents in at least a portion o~ the picture
frame. All of the digital color components in the picture
frame are encoded to a look up table of digitally com-
pressed color codes of a fifth digital word size smaller
than the sum o~ second, third, and fourth digi~al word
sizes; and the plurality o~ run lengths are encoded in
co~b m ation with the digitally compressed color co~e~.
The representation of color with such a limited number of
codes allows for a significant re~uction in the bit size
n~cessary to represent the color data: and the u~e of run
length~ allows ~or a ~urth2r signi~icant reduction in the
amount of data required to represent pixels in a picture.
The inventibn is also embodied in a method and
sys~em for decompressing ~his compressed co~or video
data. The digitally compressed color ~odes are décoded
~.,
~32224~
_ 9
according to the looX up table to form a table of the
three digital colox components for each o the run
lengths, and the run lengths and corresponding color
components are stored in an array in a buf~er memory to
represent run length and color component data ~or the
scan lines in a video picture frame.
In accordance with the present invention, there
~s provided a method of compressing digital color vid~o
data in a video communication system for transmitting a
plurality of video picture ~rames~ with eac:h pi~ure
frame comprising a plurality of scan lines composed o~ a
plurality of p~xels, utilizing a digitized color video
signal having thre~ digital color components, said video
communic:ation syst~m inc:luding means for determirl~ng a
lum~nance function for each p~xel; means for determ~rling
whlch of said pLxels on each scan line represent decision
poLnts bas~d upon said luminance function; and means ~or
encoding at least a portion o~ said plurality of plxel
in each scan line as a plurality o~ combinations of run
lengths and said three digi~al color components, said run
l~ngth being of a ~irst digital word size, and said three
dig~tal color component~ being of seco~d, third and
fourth digi~al word sizes, respectivaly; said method com~
prising the steps of dl~termin~ng up to a predetermined
number o~ the visually significant occurring co~binations
of said color components in at least a portioll of said
picture frame; encoding all of said digital color
components in said picture frame to a look up table iIl a
msmc: ry means of digitally compra~sed color codes of said
most visually significant cslor combination of a fifth
digi~al word size smaller than the sum of said second,
third and fourth digital word sizes; and encoding a
plurali~y o~ run lengths a~ld said digitally compressed
color codes reprasenting at least a por~ion of said
pic~ure frame m said memory means.
~ 3222~0
-- 10 --
The pres~nt inv2ntion al~o acsordingly provide
for a system ~or compressing digital color video data ~n
a vid~o communication system for transmittillg a plurality
of video picture frames, with each picture frame compris-
ing a plurali~y of scan lines composed of a plurality of
p~xels, utilizing a digi~ized color video signal havinq
three digital color components, said video communication
system includ~ng means ~or determin~ng a luminance
function for each pixel, means for det~rm1ning which of
said pixels on each scan line represent decision points
bas~d upon said luminance function, and means or
encoding at least a portion of said plurality o~ pl~els
in each scan l~ne as a plurality of combinations of run
l~ngths and said three digital color components, said run
lengths beLng o~ a first digital word size, ,~nd said
three digi~al color components being o~ second, hird,
and fourth digital word sizes, respecti~ely, said system
of compressing digital color video data comprising: means
for determining up to a predet~rmined number of the most
visaully significant com~inatisns of said color co~pon-
ents in at least a portion of said picture frame, m~ans
~or ~ncoding all of said digital color co~ponents in said
pic:ture frame to a look up table in a memory means of
digitally compressed color codes of said most frequently
occurring visually significant color combinatlons of a
fifth digital word SiZQ smaller than the sum of said
second, third and fourth digital word sizes: and mean~
for encoding ~ plurality o~ run lengths and said
digitally compressed color code repres~nting at least a
portion of said picture frame ~n said memory means.
The invention further pro~ides for a method for
decompressing digi~al color video data in a video
communication system utilizing a plurali~y o~ digitized
signals representing combination~ of a plurality of run
longths of a ~irst digital word size and digi~ally
compressed color compon2nt codes of at least a portion of
~3222AO
a plurality of scan lines of a video picture frame, and a
look up table of said digitally compressed color
component codes for three correspondlng digital color
components of second, third, and fourth digital word
sizes, respectively, said method compris~ng the steps o~
decoding said digitally compressed color component code~;
according to said look up table to form a tabls in a
memory means of said three digital color components for
each said run length; and storing at least a portion of
said run length and said corresponding color components
to an array in a buffer memory m~an~ of run length and
color component data representing said plurality of scan
lines ~n said video picture frame.
The in~7ention additionally provides for a system
for decompressing digital color video data in a video
communication system utilizing a plurality of digitized
signals representing combinations of a plurality of run
length and digitally compressed color component codes for
at least a portion of a plurality of scan lines of a
video picture frame, and a look up table for said
digitally compre~sed cols:r component codes, said rur
lengths being of a fixst digi~al word size, and said
compressed color component codes bem g of second, third,
and fourth digital word sizes, respectively, ccmprising
means for decoding said digitally compressed color
co~ponent codes according to said look up tablP to form a
table in a memory means of said ~hree digil:al color
components for each said run length; and mean~; for
stor~ng at leaqt a portion of said run length and said
corresponding color components ~n an array in a bu~fer
memory of run length and color compon~nt data represent-
Lng said plurality of scan lines in said video picture
frame.
As is illustrated in the draw~ngs, ~n a pre
ferred implementatiQn of the ~nvention, the video
communit:ation system is capable of producing a color
:132~2~
- 12 -
video picture using an RGB video camera, generating an
analog RGB signal at the normal 60 ~ields per second,
with each field representing half of the picture in an
Lnterlaced mode. The signal for the video picture ~rames
yenerated by the camera 10 is received by an analog ~o
digital converter 12, which converts the red, green and
blue (RGB) analog components into digital RGB components,
which are each digitized as 5iX bit digital word~,
form m g pack~ts of bits for the RGB components for each
pixel of the color video picture of eighteen bits.
The type of the davice used to gen~rate th~
source color video picture is not cru5ial to the inven-
tion, as a camera generating a standard NTSC composite
signal which is converted to an RGB di~ital output would
also be suitable as would a camera us1ng a field ra~e
o~her than the 60/sec. rate of a NTSC camera. The output
of the camera also does not ne~d to be stric~ly RGB,
since other thre color co~ponent groups may be used to
create and transmit color video pictures. For example,
~he three di~ital color component signals may be cyan,
magenta, and yellow; hue, saturation, and intensity; or
even two distin~t colors and a third parameter based upon
the entire video signal, such as hue, saturation or
intenslty o~ an original analo~ vid~o signal, so that
there would be some automatic weighting o~ the color
information generated by khe camera.
It is also not e~sential that the three color
components be repre~ented hy the same number of bit~,
sinc~ it is known in the tel~vision industry that certain
ranges of colors are not a~ easily perceived by tha human
eye. Such a w~ightm g of information could involve a
reduction in the number of bits used for th~ red compon
~nt in an RGB scheme, for example, thus permitting
transmission o~ more gradations of other color informa-
~ion that i~ actually perceptibl~.
~.3222~0
In addition, the source of the co10r video
pictur~s to be compressed may be a storage means, such as
a video disX, a computer file storage media, a vidQo
tape, or the like ~rom which the color vid~o in~ormation
can be processed for introduction into the ~olor video
data compression system of the invention.
The digi~ized RGB signal is received by the
transition engine portion 14 o~ the image capture eng~ne
16, which preferably includes mtegrated circuit means
and associated m~mory means. The first major part of the
Lmage capture engine is the transition engine which
Lncludes circui~ry for determining a lumlnance function
based upon the three color component video signal for
each picture element, or pixel, of each scan line in the
sequence of video picture frames genera~ed by the analoy
front end of the ~ystem. In the preferred mode, the
lumlnance converter 18 sums the bits from each of the
three digital color components for each pixel in th~ scan
lines of the video pictur2 fxame to get a lum m ance (or
intensi~y) va1ue and performs further process~ng o~ the
data obtained. In tha system of the present invention
each s¢an lm e preferably contains 480 pixels, which
m~tches the resolution o~ the camera and which provides
for bet~er resolution than is typically avai1ab1e in the
prlor art, in which generally only 256 pixels are
u~il ized pex scan 1ine. The lum~nance of the threç~ color
components may b~ weighted to ~ive greater significanc~3
to on~ color or two colors to provide the 1uminanc:e
~untio2l, and may also be based in part upon an original
source analog video signal. However, the luminance
function is pre~erably based in part at least upon tha
sum o~ the three digi~al color components. The luminance
function derived ~rom the sum of the thxe~ s~x bit co10r
component~ therefore ha~ a digital word siz~ of eight
bits. This luminance function for each pixel is utilized
in the input capture engine for evaluating one or more
1 322240
- 14 -
decision parameters based upon the luminance function for
detexmination of those pixels which operate as decision
points about wh$ch the one or more of the decision
parameters are found to vary from a prestored set of
threshold values.
The luminance funckion is an xcellent indicator
of color changes in the pictur~, or movements of objects
in thD picture. In the image capture engine the one or
more decision parameters ~ased upon the luminance func-
tion may also be used as the basis for determination of
dirferences from line to li~e, and of distinctive
sequences of plxels which define edges o~ objects which
can be determined to be moving from frame to I,~ame.
~anerally, the luminance, or other combination of color
components which comprise the luminance :~unction,
undergoes significant changes where there are changes in
the characteristics of the pic:ture.
The camera also ~ntroduces anomalies or arti
facts into the videc picture due to noise in thP colox
sa~pl~ng resclution which ideally should }: e eliminated to
reduce the amount of data to be transmitted since they
contr~ut~ nothing beneficial to the picture. When th~
pic:ture i5 displayed with a new field every 60th of a
second, the effect of such anomalies is averaged out by
the human eye. Areas having a smoo~h appearance and
li~tle actual d~tail upon close observation seem to
"crawl". Th~s appearance is also known as the "mosquito
ef~ect". When a picture is frozen so that only one field
or picture frame i~ bem g examined, the picture takes on
a grainy/ speckled appearanc~. The impact of the noise
on khe luminance data is in ~he form of t~ny variation~
~n the computed lu~nance. When the picture i~
digitized, the digitizing proces3 also converts all o~
these arki~acts to digital representation~., even though
~hey do not actually represent pictuxe detail. The
`~ .
, ~
~ 3222~0
- 15 -
processing of luminance in the image capture engine
operates to elim m ate such meaninglQss details~
one preferred method eliminatlng the non-essen
tial details caused by noise in the luminance data is to
determine the points of change hased at least in part on
~he lum m ance function for pixels in the scan lines by
comparing differences in one or more decision parameter
with corresponding adaptive thresholds. The decision
parameters are preferably comprised o~ differences of the
luminance function between pixels, determined betwQen
proximate pixels (Diff-l) in a scan line, n plus one n
plus two, or even a further distance away, where n
represents the position on a scan line of the plxel being
examLned for changes in lum m ance; between adjacent first
differences (Diff-2), and a cumulative parameter
(Cum-diff3 which is a sum of the indi~idual difference
functions Diff-l, and Di~f-2. Each decision parameter
has its own correspond~ng adaptive threshold, having a
default value which i5 subject ~o modification by the
system in re~ponse to operator or processor settings.
The adaptive threshold preferably has a de~ault value
which may be adjusted by the input capture engine
responsive to operator selections for resolution. The
selecting of the threshold parameters for de~erm ming
either the feature or transi~ion decision points is quite
subjective. The selection of the parameters determ m es
the number of data points required to define the picture
and it also determ~nes the overall perc@ptual quali~y of
the pictureO
Typic:ally for the feature rlan length de~ermina-
tion, two thresholds are usedO One is the cumula~ive
change in lum~nance s~nce the la t decision point,
Cumdiff. Cu~diff w~ll trigger a decision point if it wa~
greater than 6 and the number of p~xels since the last
decision pomt was greater than 5. Ano~her decision
paramet~r is the sum of two adjacent difference values,
~3622~o
Diff2 (this is the same as the di~ference between lumin-
ance values that are two p~xels apart3. I~ the Dil~2
value is computed to l~e. greater than typically 32, the
logic wil signify that the line i~ enter~rlg an edge,
which id~ntifies a decision po~nt, anc3 will stay in the
edge characteristic until the Dif~2 value falls below
20. When the edge mode is exited, the color of the next
p~xel is carried all the way back to th~ piæel where ~he
star1:ing edge determin~tion was made. ~lso, if Diff2
changes sign, it signifies a new decision point. Chang-
ing the values for the cumdiff thresholds greatly~ a~fects
the q~lality and data complexity of the picture.
In the slope determination of decision point~;
(apexes~, three general conditions ar~ used. An initial
slope is determined at the decision point and all
measurements are base on that slope. The initial slope,
l:NITS, is determined by computing the following function
termed N DI F F 2:
NDIFF2 = ~luminance (i+2) - lu~ainance (i) )/2
INITS is the value of NDIFF2 immediately a~ter the
der:ision po~nt.
CU~DIFF in the slope case is defined the following way:
.~ .
CUMDIFF (i) -- CUMDIFF (i_l) + NDIFF2 ~i)
If the absoluta value of the CU~DIFF is
typically greater than 2 o and the numb~r of pixels in the
run length is typically great~r than lo, then a decision
po~nt will ba triggered. Similarly, i~ the absolute
value of NDIFF2 is less than or equal to typically 4 and
the run length is kypically greater than 5, a decision
point will be triggered unless the last decision point
wa~ also trisgered in this mann~r. Th~ third dec:ision
parameter is also based upon NDIFF2:
~3222~0
- 17 -
TRIGVAL(i) = NDI~F2(i) INITS
The threshold for T~IGVAL is usually set m the
range of 4 to 10 and will trigger a decision point any
time the absolute value reaches or exceeds the set value
and the run length is at least 2 p~xels. Other techni-
ques may be used but these seem to give good quali~y
pictures with an acceptable number of data points.
A graphic representation o~ a typical plot of
lum mance across a line o~ a video picture is shown in
Flgure 2. The lumLnance function of the pixels inter
sected by the scan line 36 is graphically represented by
~ne 38. A~ is shown in Figura 3, a graph o~ the deci~
sion points based upon comparison of one of the decision
parameters with the corresponding adaptive difference
threshold in a feature encoding techni~ue, results ~n
stepped line 40, a sequence o~ horizontal straight linas
across the luminance pattern. Each horizontal line
represents a separate length of a specific color.
A second approach which may be used to eliminate
th~ non-e~sential details is a transition or slope encod-
iny technique, which is illustrated in Figure 4. In this
technique the rate of change of the differences in the
decision parameter between pixels is determined, and the
rates of change o~ these di~ferences are compared with an
adaptive, prestored difference ra~e o~ change threshold
to de~ermine d~cision points or apex points. Thes~
change points or decision points are indica~ed as X's on
line 39. They indicate the location of the next apax.
"Run length" is defined a~ the p~xel distance between
decision points, for both the f eaturP encoding and slope
encoding technique~. According to the transition or
slope encoding t~chnique, the lum~nanca data results in a
line 42 representing a series of apexes or slope decision
points, which may be used for controlling khe color
segm~nts between decision po~nts. A drawing ~ongine can
. . .
.
~3222~0
- 18 ~
producs a smooth transition of color values for the run
length between decision points when the encoded informa~
tion is to be retrieved. In thls technique, ~or each
scan line an initial color is transmitted, followed by as
many sequences of run length and color values as are
necessary to represent the pic:ture frame content. In
either implementation the information is displayed as a
series of slopes. For the run length encoded data
artifical color slopes are inserl:ed into the display l~ne
as shown in Fig. 5. In this case the slopes are gener-
ated a~ a function of the lum~nans::e shift between :runs
and the length of the adjoin~ng nlns as shown ~n Fi.g. 6.
In the image capture engine of ~ig. 1, the
decision point detector 26 for determin~ng dec:isioll
points may alternatively b~ abl~ to ut~ 1 iZQ either one of
these methods for fixing the decision po~nts ~n the color
of the pixels in the picture, as each method has ite:
re3pecti~e advantages and disadvantages. The feature
coding technique is typically more appropriate for
pictures with a complexity of ob~ects with dist m ctive
edges or lines. On the other hand, the slope encoding
technique is most suitable for encoding gradual
transitions in shading or gradual color changes, but may
require additional cod~ng to repres~nt complex pictures
with imageC having many edges and lines. In the
preferred implementation of the slope encoding technique,
a sequence o~ thresholds will be compared with decision
parameters, and the cumulati~e parameter (Cum-dif~) and
an adaptive cumulative threshold will also be utilized in
determin~ng decision points, to account for those slow,
gradual rates of change o~ lum~nance which would still
result in an accumulat~d luminance chang~ which is
signifioant enou~h to merit identification of a deoision
poLnt.
The threa component color codes are al o op~r-
ated on Ln the run length processor 28 to drop the two
:
1~222~0
-- 19 --
least significant ~its from thA six bit values for the
color components, reducing each of the color components
m the preferred mode to four bit digi~al words. Alterna-
tively, in one preferred embodiment, the transition
engine may also conta~n a predetermined color map repre-
sentation o~ three-component colors, with an n-bit code
corresponding to a particular color comb~nation. Here,
the colors of the image are matched as closely a~
possible with the colors in the color map. A~ a further
alternati~e, the color codes could also be rounded.
These truncated or reduced digital color components are
then encoded with the run lengths between decision points
Ln the run length processor 28. Although the preferred
bi~ size for the reduced color components is four bits,
ju~t as the input digital word size for the col~r
components from the analog front end can be of different
sizes to vary the info~aational content, the reduc:ed
digital color components may also be of different ~izes9
A particular comb~n~tion of digital word sizes for color
components may include a r~duced sixe for the red
component, due to the recognition in the industry of ths
reduced perceptibility of thls component.
Th~ feature and slope encoding techniques allow
for a variable number of bits to be used to represent an
mitial picture frame and then changes in subsequent
picture frames, m order to encode the mLnimum number of
bit~ for each picture frame. Thi~ is significant a
~mprovement over the pxior art which typically analyzes a
four by four or three by three block of pixels to
compress the infoxmation m su~h a block, which always
results m the same number of bits baing utilized to
repr2~ent khe informational content in the picture,
whether there ha~e been changes outside the segment or
not.
The second major portion of the image capture
engine is the capture buffer memory (CB~) 29, which
..
- 20- 13222~
receives the encoded run lengths and reduced color compon-
ents representing some 2 00 lines of data ~rom the picture
frame. Alternatively, i~ the data rate required becomes
too high to send pictures at a desired spead, lesser
numbers of scan lme~ can be stored, such as 150 or lO0
lines~ T~e run length and color component in~ormation ~n
the capture buffer memory is then transmitted to the
video data processor 3 0, which accesses the run length
and color data in the capture buffer memory by an access
control 35, and operates as an interface to transform and
transmit the video information ~n a format suitable for
transmission by the modem 32, conneated to the telephone
34, and which may include means for further com~pressing
the video data, at 33. The video data may als~ be
compared with a previous picture frame stored in an old
picture memory 3 l.
It is possible in a simplification processor 33
of a video data processor 30 to further analyze the
dif~erence between color values of pixels a~ter the color
codes have been truncated to provids the reduced color
component codes, and to concatenate run lengths of such
reducsd color component codes which vary less than a
given threshold value, or to further concatenate run
lengths of the reduced color cod2s ba ed upon variance o~
one or mor~ of the de~ision parameters with re~pect to a
correspond m g thr~shold. AR th~ ru~ length code is
typically at a maximum of four bits to be compatible with
run length and color code combinations of 16 bits, with
16 bit computer buses in the current implementation,
concatentation o a sequen~e of p~cels for each run
length would be expected to permit coding of up ~o
sixteen pixels per r~an length. ~owever, in the current
~mplementation the values O to 15 are u~;ed to represent
run lengths o~ from 2 to 17 p1~els, since run lengths of
O and 1 are not meanLngful. A7ternatively, longer run
lengths may be determined initially as well, as may be
- 21- 13222~0
compatible with different capacity computer buses, to
permi~ run lengths of greater thall 4 bits and run leng~h
color code combinations greater than 1~ bi~s.
As mentioned previously, it is expectQd that the
~mits of compr~ssion required for adequate smoothlng of
in~ormation in a real ti~ sequencing of video pictures
m telecommunication would be about 15 rames per second
for transrnission over con~entional telephone l~nes. It
would be poss~ble to use a modem at 1200 bps (bits per
second), but this would considerably slow the nu~ber of
frames p~r second possible in the communication system~
Ideally, the system is configured for half duplex mode,
and a full duplex mode of configuration would be expect~d
to requirD two telephone lines. Ideally the modem that
lS to be used is one which would utilize the largest
handwidth possible, and may be conventional 2400 bp~ or
9600 bpa modem or special modems providing higher b~t
tes may b~ used.
W i~h reference to Fig. 7, ~n the preferred
embodiment, a telephone 43 receives a transmitt~d signal
from a transmit~er modem over ordinary tel~phone line5
and the receiver modem 44 converts these signals to an
electronically digitized forma~ to be recaivable by video
data processor 46. The video data processor then adap~s
the digitized signals which represent encoded run length
and color informa~ion to a format which i5 acc~ptable for
reception by the draw m g englne 62. The drawing engine
o~ the reconstruction engine 48 converts the run length
data to slope form and presents i~ pixel by pixel to the
digtal to analog converter for use by the monitor. Alter~
natively, the video processox i~terface could be adapted
to receive the co~pressed calor video data from a com-
put2r system 66 re~rieving the information from mag~etic
media, such as a hard disc or high capaci~y floppy discs,
or from a video disc player ~or displaylng a much greater
length series of video picture frames, in a form such as
- 22 ~3~224~
for a video movie. The video data processor preferably
includes microprocessor means and assoGiated memory means
(not shown) programmed to carry out various functions. A
preferred function is to reconstruct a total picture
frame data repr sentation in terms of run length and
color ccdes from an old picture m~mo~y 52 of the last
picture frame data, and an array of the run lengths and
color codes which have changed from the last picture
frama. This difference reconstruction function 45
prepares picture fra~e data for run length recon~t:ruction
at 50 and color code reconstruc~ion 56, utilizma control
signals embedded in the run leng~h and color data.
As the run length and color information are
received by the video data processor 4 6 of the reconstruc-
tion engine 48, the digitized signals are typically of a
digi~al word size of s~xteen bits. The number may vary,
depending upon the type o~ statistical encoding used.
Alternatively a color code (which may b~ from 4 to 8 bits
in length) may be us~d to select speci~ic colors from a
map or pallet so that fewer bits need to be sent. AR
compressed and encoded from an input ~onstruction englne
a~ described earlier, tAe digital word size of the run
length portion actually procsssed would typically be four
bits, and the digi~al word size of the color code portion
would be twelve bi~s. A3 mentioned previously, ~he
preferred apportioning of bit sizes of the three color
component codes is such that e ch digital color code
component is of a digital word size of four bits. How-
ever, only small portions of the picture which haYe
ac*ually changed may be actually encoded, with appro~
priate control data for skipping run lengths which may
not have changed b~ g e~bedded in the trar~mitted
Ln~ormation. The run length reconstruction or decoder
~unction 50 of the video data processor oparates to
separate the run length por~ion from the digitized
signal~ and the color code reconstruction function 56 o~
- 23 ~ ~32~2~
the video data procassor, for decoding the colo:r codes,
can separate the digital color components from thP
mcom~ng digitiæed signal~. How ver, advanced signal
proc~ss~ng and comprassion of the data may also involve
the concatenation of run lengths to a digi~al word size
of eight or nine bits, so that the run length decoder
function would th~n also opexate to separate the eight or
nine bit digi~al word size into four bit digi~al w03:d
portiorls. In the event that the run length codes were
concatenated to an eight or nine bit digital word size,
the color code por~ion would have also have 3~een sub-
jected to advançed data compression techniques to reduce
the 'chree digital color codes aac~ of four bi~s ~o a
combined color code portion having a digital word size o~
eigh~ bi~s. The color xeconstruction function 56 would
then also operate tc: convert the eight bit digital color
codes to three digital color codes o~ the four b~t
digital word si2e.
Fro~ the r2::0nstnaction engine run length de-
c:oder and color codes sections the run length and color
code in~ormation is transferred fro~ the vid~o data
proces~or via the access and timing control circuitry 54
Ln the drawing engine 62 to a drawing engine display
bu~fer memory 57 which ideally co~prises dual memory
buffers, pingpong A 58 and pingpong B 60. The access and
timing control 54, under the direction of the video
processor, sends the reconstruçted run length and color
mformation for st~ring in one of the ping pong buf~er
memory portions until the in~ormation for an individual
picture frame i5 co~plekf~: that picture is then displayed
while the next se~uential picture information received by
the sy~tem is sent and storad in a si~ilar fashion in tha
second portioll of the display bu~fer memory. Each block
of the display buf~eer memory needs to be of a su~ficient
capacity to avoid overflow of the meDlory by the run
~ - .
- 24 ~ ~3222~
length and color code information, and it has been found
that a random access memory of a capacity of 32K 16 bit
digital words is adequate for the picture reconstructionD
The drawing engine 62 includes a pixel generator
61 for converting the run length a~d color codes stored
~n the individual p~ngpong memories to individual points
for display on a monitor 64. The accass and timing
control 54 of the drawing engine is re~ponsible ~or all
display timing and control for the pixel generator. ~he
drawLng engine generates a writ strobe to writ t:he runs
of color mformation to the series of points to be
converted from digital to analog for display.
In the preferred embodiment for pixel generation
from feature encoded run length data, each end of a run
length of a particular color combination is essentially
tap~red to provide 2 smooth color transition from one run
length to another. The resulting smoothed reconstructed
video lLne 41 is depicted in Figure 60 When a run length
is short, it usually is a~ indication that the color
level is changing rapidly. I~ the run length is long, it
usually indicates the color level is changing slowly.
W hen the change ~n thP luminance function, given by one
o~ the decision parameters, is large, it usually indi-
cates a high pro~ability o~ an edge in a picture, wherea~
if the change is small, it is probably an Lndication of a
shading effect. Based upon the run lengths and one or
more deci ion parameters, the pixel generator de~erm m es
where intermediate decision points should be placed, and
~nterpolates smooth color transitions for each of the RÇ;B
color co~nponents ~rom one intermediate decision point to
t~e next. The ends of each s~an line similarly transi-
tiOIl when they contact another color, ~o that th~
beginning and ending of a scan line may have a singl~
intermediate decision po~nt adja ::ent the end, to def~ne a
relatively sharp transition ~rom the edge of the picture
to the adjacenr. color. The ~nterpolatiorl is preferably
~1 3222~0
-- 25 --
performed linearly, but may also altarnatively be shaped
to more fai~hfully depict cu~red sur~aces. If the image
is slope encoded, th~o pixel generat2s a smooth transition
from one apex to the next without injecting an inter-
mediate decision point.
The piKel generator of the drawing eng m e
Lncludes all the necessary functional sections to imple-
ment the color interpolation between pairs of points
designated by the run lengths, and preferably converts
the four bit color compor,ents to either six or eight bi~ '.
digital wordst for SLX or e~ght bit precision, in three
~eparate channals, with one for each of the RGB
components. Increasing the bi~ size allows the pixel
generator to generate smoother gradations of color
transitions between pixels of different colors. For
example, although four bit digi~al word sizes permi~ up
to 4,096 color combinations of red, greRn and blue
components, only up to 16 gradations of any one of the
color components would b~ possible. Increasing the ~it
size up to 6 allows ~or up to 64 gradations of any
~ndividual component, and up to 262,144 total combina-
tions. An eight bit digital word size permits an even
greater range of gradations for an individual compon~nt.
However, as discussed previously, the full digi~al word
size~ for the color components need not be equal, and may
be in fact arranged so as to allow a broader range o~
colors for one or two of the color components, at thP
expense of one of the color components which would only
require a smaller digital word size to accommodate its
perceptlbility. The pixel generator therefore dynamical-
ly generates a complete digital representation of the
pixels sf a picture :Erame to be displayed on a p~xel-by-
pixel b is, and this information is transmitted on RGB
: three channels from the p1xel generator to the digital to
analog converter 63 which converts the video signal to
analog foxm for displaying on the monitor 64.
~ ~ .
- 26 - 13222~0
Re~erring to Figs. 1 ~ 9, elements bearing
referPnce numerals 110 to 134 correspond to elements
bearing re~erence numerals 10 to 34. Fig. 8 shsws
another embodiment with image capture engine 116 having a
video processor 130 ~unctioning to further simplify and
compress data from the transition engine 114. The output
from capture bu~fer memory 129 is received by the
processor subsystem 130 having standard input and output
and control 166. The stand2rd I/0 166 typically ~ight
mclude a keyboard, diskette control, a date and ~ime
clock, and a monitor output and control. Output :from the
processor subsystPm ia typically connected to a modem
132, which is in turn connected to a t~lephone 134 ~or
transmission of the compressed information oYer ordinary
telephone lm es. More than one modem may be used to
provide faster image displ~y rates or higher quality
color images.
With re~erence to Fig. 9, the video data proce~-
sor subsystem 168, which per~orms the compressLng and
decompressing functions of the video processor 130 and
the video proce~eor 146, to be explained further herein-
after, i5 most preferably adapted to be connected to both
an image capture englne (I~CaE~) and a reconstruction
en~ine (R.C.~.) for use in compressing and decompressing
video color data in a two-way com~unication sy~tem.
However, where tha processor subsystem iæ being used for
compressm g the color video information, it should be
apparent that the reconstruction engine nQed not be
connec*ed to the same processor subsystem as is connectad
to the input construction engine. I~ a video communica-
tion 5y8tem iS COllfigUrQd SO that the image capture
sy~tem circuikry is part of a camera, and ~he reconstruc-
tion engine circuitry is part of a display monitor,
different processor subsystam~ 130 and 1~6 would
generally be utilized by the image capture engine and the
reconstruction eng m e.
- 27 - ~322~
As is ~lustrated in Fig. 9, the ~hared video
data proce~sor subsyst~m receives input from shared
capture ma~ory bu~fer 170 for recei~ing input from the
Lmage capture engine, and pre~erably also ~ends output to
a shared display memory bu~er 172 which contalns section
154, 158 and 160 of the drawing engine, for output to the
raconstruction engLne. Each of these memory bu~fers
requir~s sufficient capacity to avoid overflow the
encoded information, and it has been ~ound in practire
that a memc:ry space of 32K by 16 bi~s is adequate for
these purposes. Memory bu~fer 170 is also pre~erably
shared for input and output between the image capture
engine and the video data processor; and the memory
buffer 172 with its dual pingpong memory section is
similarly shared for input and output betwe~n the
reconstructio~ engine and the video data proce~sor. The
processor subsy~tem includes two microprocessors, which
are preferably Motorola 68020 32 bit proces~ors, pro-
ce~sor "A" 174, and processor "B~ 176. As pro~essor "A~'
typically performs most o~ the processing functions of
the processor sub~;yst~m, i~ is provided with a pr~ate
data memory "A" 178 of 512K bytes~ Processor "B" is
provided with a lesser amount of memory in me~ory "B" 1~0
o~ 256K byte~. Also provided betw~en proc:essor "A" and
pXOCQssOr "B" for co~nmunication between the processors is
a dual port ram 182 of 16K byte~. Dual port RAMS 184 and
186 o~ 32K byte~ are also provided a~ buf~ers between
processors "A'l and "B'l and the V processox section 166.
The microprocessor "C" 188 for the I/0 control
seotion 166 is pre~erably an Intel 80286 having DRA~
r fresh and a direct memo~y access 190 ~or diskette
control and a DRAM 192 o~ 512K bytes. Input/output port5
194 ar~ designated generally for the standard I/0, which
may include disk drive~, k~yboard, a monitor, and ~he
like.
::;
:-
- 28 ~ 13222~
With reference to Figs. 8, 10 and 11, the opPra-
tion of the lmage capture engine and the proc~ssor
subsystem 130 ha~ing simplifying and compres~ing ~unc-
tions w~1 be descrihed. The run lengths 200 of a
sequence of pixels in a scan line havlng like color
values ar~ determined as nina hi~ digital words which axe
divided Ln the imaga cap-ture engine as four bit digital
words 201. The RGB color components 202a~ b, c as
utilized for determin1ng the luminance functions Ln
sec*ion 118 are six bit digital words used for deter
min1ng decision points for run lengths Ln the decision
point logic 126. These colors are truncated by ramoving
the two least significant bits from each six bit word in
~he color code truncation circuitry 120 to form ~our bit
digital words 204a, b, c. The run length encoder 1233
~aps a series of~ run length and R&B color code
combinations 205 to the capture buffer memory 129, ~r~
preparation for the ~urther process~ng oi~ the processor
subsystem 130. In the pre~erred embodiment of this
~vention, a predetermine~a de~ault c:olor map 214, irl the
color c:ode section 1~ 0 consisting of a look up table of
unique combinations of the three color components such as
RGB values and corresponding eight bit codes, maps 256 of
the most visually signi~icant color combLnations out o~ a
possible 4,096, obtained from the three RGB truncatQd
foux bit codes. The color map i5 preferably alterable by
the video data processor subsystem.
The 256 color code combinations to be included
in the color map are determlned on the follswing ba~is.
Given that each RGB color compone~t is repressnted a~ a
our bit code, a range of 16 gradations o~ each color
comE~onent is possible. How ver, in practice the colors
at th~ extremes oP each range o~ gradations rarely appear
~n ima~es captured by a video cameraO Stati stical
surveys of a wide variety of st::enes captured by video
cameras reveal a common distr:ibution of colors. To
-- 29 --
~3222~
;llustrate the distribution, a two-dimensional chart of a
range of from o to 16 of green downward along a ~ertical
axis, with a range of from o to 16 of blue to the right
across a horiæontal axis yields an oval shaped pattern ~n
the middle, along an axis from o,o to 15,15. Adding a
third dimension of r~d yields an sausage-shaped
distribution of the most visually significant color
combmations from a wide variety of possible scenes and
lmages. A combination selected from an extremity of this
sausage-shaped distribution has been found to be
virtually indistm guishable from a color combination at a
nearby extremity of the three-dimensional color blook,
and wlth~n the sausage-shaped distribution~ color
combinatiorls proximal to each other are also virtually
Lndistinguishable. By careful selection of 256
representative color combinations from block~ within thi~
sausage-shaped distribution, a color map can thus be
co~structed o~ th~ most visually significant color
combinations likely to be enco~ntered. In practice it
hPs been found that an RGB ratio o~ 4:3:2 produces colors
in the skin tone ranges, and this ~nformation ~an be used
to balance the color ratio distribution, with the primary
factor bem g subjective appear~nce.
The color mapping process makes use of the obs~r-
vation that most colors that occur in nature are not very
pure. Figure 15 show~ a color cube with no color, black,
in the front lower left corner and white which is the
maximum red, green and blue in the upper right back
corner. Graen increases to the right from the black, all
zeros, orig~n. Blue increases from th~ black toward the
lower left back corner and red is represented by a number
of plane~ representing constant levels of red. The red
mcrea~es in the direction of the top of the cubec Thus
all of the possiblP colors may be represen'ced in the cube
to a precision which is dependent on the number o bi~s
allocated to each colox component. Any specific color
- 30 - ~322~
may be represented by the cocrdinates of any point within
the cube.
All of the real colors seem to b heavily
bunched along a sausage shape which runs ~rom the black
corner in an upward arc to the white corn~x~ Since the
colors are concentrated wi~h no natural colors oc~urring
Ln the pure red, greent blue, magenta, cyan or yellow
corners, it is possible to reduce the number o~ color
codes ~orm the 4096 possible prepresented by 4 bits each
of red, gr~en and blue. The ovals r~presented by ~60,
identify tha areas which must be reproduced with some
precision because the real colors concentrate her~.
It is really only neces~ary to have flesh tones
be faithful reproductions with slight off-colors in other
areas being quite acceptable since the persons on the
receiv mg end do not know exactly what colors were pr~-
sent in the transmitting end of the system although a
correction process may b applled if it is important~
The approach for generatm g the color map has been to
d~fina fLne gradations in color m the flesh tones wi~h
more coarse gradations the ~urther the captured color is
away from the central "sausage". Tha map was empirically
d~rived fxom exam ming the color distributions in a large
number of pictures and adjusting the map parameters to
get acceptable results. The correction process consist~
o~ analyzing the actual colors which occur in each of the
map area~ and correcting the map segment so that it more
fai~hfully repressnts the d~tected coloxs in that scene.
The proce~s is quite subj~*i~e but seems to work well.
In the proces~or sub~ystem, a histoyram of the
R~i;B color codes 212 is sta~istically processed for all o~
the run length comb m ations to updat~ the color map 214
to be u~ed as a look up table. Even with the foux bi~
color code~ for each of the RGB components, up to 4,0g6
different color combina~ions would be ~h~oretically
a-hievableO In practica, it ha~ been found that a group
- 31- 132~2~L0
o~ carefully selected 256 color ::ombinal:ions is quite
adequate to serve as apex colors for the drawing eng~ne
to construct the image with up t~ 262,144 colors with s~x
bit color reconstruction of each of the three color
componen~sO Alternatively further gradation~ are poso
sible by recon~tructing each of th~ three coLor compo-
nents as eight blt codes. Therefore, the histogram o~
256 of the most frequent RGB color comb~nations may be
used to modify the colors enf~oded as a series of eight
bi~ digital words in the color code look up table or
color map 214. since each color combination in the color
map represents a block of ranges of colors, the color
frequency histogram may be used to substitute a more
frequantly occurring color combination within it~ cols:~r
bloc3c as a xepresentative color co~nbination, for more
faithIul color re~aroduction. A~: these repr~sentative
colors are within the color block ~or those colors, the
~ubstituted colors are determined by the system are
visually significant, and are not mexely selected upon
frequency of appearance ~n the pi~ture.
q~he RGB color information requirement for 12
bits to represent the maximum of 4,096 colors is thus
reduced to a table of 256 8 bit digi~al words to repre-
sent the 256 most visually significant colors. Lass
frequently occurring colors which may be over the limi~
of 256 colors may also forced to conform to the same
colora~ion a~ the nearç!st color code combination in kh~
color map, without significant 12ss~an~rlg of the accuracy
of the colors ~n the picture frame to be transmitted.
once l:he colLor codes are ~n the form oP eight bit digi1:al
words 206 which may be comb~ned wi~h the four bit run
length portion 2 00, the four bit run length code, which
actually represents a rtan length of from 2 to 17 p~xels
~n the pre~erred implementation of the encoding of run
lengths, can be statistically processed to provide a
varying leng h digital word 208 to be as~;embled in the
."; .
- 32 ~ 2 2 4 0
eventual :Eully proc~ssed run length color code combina-
tion 210. The run length codes may vary from one b~:t for
most ~ra~uent lengths up to ~ or 10 for rarely occurring
lengths. Thus, the run length may represent from 2 to
257 p~xels, which would be thaoretically adequate to
represent an entire scan line of 512 pixels in two run
length color code combinations. Thus, the four bit run
lengths are corlcatenated where possible at 216 finally
befsre encod~ng the run length and color code combina~
tions at 218. In order to accommodate the encoding o~
~he eight bi~ RGB color components in the run length
combinations, it is al50 necessary to construct and
encode the color code look up table 214 as a table of 256
mdi~ridual four bi~ color codes for each of the RGB
components, which would be transmitted wlth thQ color
code run length combinatior~s to enable a recaiver or
translator of the picture information to decode
compressed color information.
More advanced processm g and compres~ion of the
run length color oode combinations m~y also occur in the
advanced prccessing saction 220. Slmilar to the pixel to
pLxel differencm g and co~parison for determination of
decision points in the input construction eng m e,
adjacent scan lines may be compared to formulate a table
of scan lines which do not differ from the previous scan
line in the direction of scanning, so that the lines or
portions of linQs may be merely duplicated. Thus, this
would allow further compression of the run leng~h and
color code combinations 210 a~ a dif~erences table 222.
Another t~chnique termed subframe procesBlng may be used
to reduce the amount of data which mu~t be sent to update
a new picture on the receiving soation o~ a system. Thi
sub~ra~ne proces6~ng technique samples every nth l~ne and
continues procassmg only with those lLnes for any one
image. Distinctive segments of run length comb~nations
which appear to form an edge may be detected in an edge
:
- 33 - ~222~
detector 224 to monitor the displacement of ~uch segments
from frame-to-frame by movement analysis 226, whi~h
preferably could track the movement of such scan lm e
segments in groups of scan line segments according to any
horizontal shifting, shr~nkl~g, growing, or vertical
displacement of such segmen~s, or virtually arly combina-
tion of such movements. A further le~el of compression
involves ~he frame-to-frame differencing by comparison of
the run length and color codes combination information
from the last picture frame wi~h the current picture
~rame, and encodLng of a skip code to identify thos~
portions which have not changed, so that only the run
length and color code combination~ which have changed are
encod ed at 2 2 3 .
Finally, the processor subsystem also preferably
encodes the run length and color code combinations to be
transmitted from the proce~scr subsystem by determ1ning a
histogram o~ the occurrence of run length and color oode
combLnation~. The preferred form of statistical encoding
at this stage i5 similar to Huffman codLng, and in~olves
the a~ignment of the most frequently occurrm g combina-
tion to a table of one bit digital words, at 2 3 O. This
table is to be ut;lized at the receiving end of the
system by referring to one or the other of the bit stat~.
o~ the one bi~ diyital word to fill in this most fre-
quently occurring run length combination in a corre~
ponding run length color code table. For example, if the
table indicates a binary one, the receiving table would
be filled in wi~h th~ run lenyth color code co~bination,
and would otherwise be left with a marker of zero
indicatmg that the spot in the table was to be filled in
later. The next three most occurring combination are
therl represented as a two bit lengt}l digital word, with
one sf the binary bit states again indicating that the
receiving tal: le location was ~o be filled in latE:r, and
~he next three most frequently occurring combina~ions are
_ 34 _ ~3~22~(~
filled in their respective locations in the corresponding
receiving table. A three ~it digital word table can then
be constructad in a similar ~ashion to designate the next
seven most frequently occurr~ng values, with one of the
b~nary bit states represent~ng values to be filled in
later, and so on, with a final digital word size of eight
bits used to represent the remaining color code combina
tions. This process may be applied to other groupings
than the 1, 2, 3, n bit grouping sequences described
above. Most preferably, this statiqtical encoding of the
compressed run length color code information is performed
for at laasr the color codes, individually, with ~ha run
length portions then be~ng encoded and rec::eived as a
separate table of eight bi~ digital words, but i~ is also
pos~ible to sepaxately statistically encode the eight bit
run length portions in a simi1 ar fashion and transmit a
separate statistically encoded table for the run length
components of the run length-color code comb~nations.
Othsr similar statistical encoding approaches may al~o be
approi?riate as an alternative.
R~erring to Fig. 12, in whirh eLements 143 to
165 are essentially identical to those previously
described which b~ar reference numerals 43 to 66, ~n the
pre:Eerred mode of tha invention the telephone 143
recei~res the audio digitized sig~als from the transmi~ter
rnodem over ordinary telephone line~, which is ~n turn
received by the r~ceiv~ng modem 144, and the vîdeo data
processor 146, which prepares the digitized video signal
in a form and format adapted to the receivable by th~
draw~ng engine 162 . The video data processor 14 6 is
connected to the ~nput/output and control section 166.
The architecture of the processor subsystem is yenerally
as has b~en da~cribed and il lustrated in Fig. 9. The
digitized signal represerlting combinations of a plurality
of run lengths of a first di~ital word size and digitally
compressed color component code of at least a portion of
- 35~ ~32~2~
a plurality of scan lines of a video picture frame, and a
look up table o:~ the digitally compressed color component
codas, are subjected to dec:oding of the color component
codes according to the look up table to form a table of
the three digital color componen~ in the memory of the
processor color reconstruction at 156, and the run length
and colox components are sent to the display buffer
memory 157, which includes the dual memory space 172, the
access timing and control 154 and the two p~ngpong
buffers 158 and 150.
As with the signal processed by the reconstruc-
tion eng~ne discussed with reference to Fig. 7, the run
length decoder 150 receives the decompressed run length
information, and the color compon~nt information, for
decoding o~ the run length information, is reconstructed
in 156. Ths color and length information are compared
wi~h the prior picture 152 for mapping at 150 and 156 to
the display burfer memory 157 which comprises thP
pLngpo~g memory "A" 158 and the pLngpong mPmory "B" 160.
The p~xel g~nerator 161 is slaved by the di~play bufi~er
memory 157 from the pingpong msmories alternately, to
reconstruct the scan lines of the transmitted picture
pixel by pixel, which is then converted from digital form
to analog form in the digital to analog converter 163,
for display on the monitor 164.
With ref~rence to Figs, 13 and 14, in ~hs
preferred embodiment o~ the proce~or subsystem 146 of
the l~vention, prior to the dif~erence reconstruction at
145 occurring in video data prsce~sor, the statistical
cod~ng i~ decoded at 232 and possibly also at 234 by
:Eormation of a table in the m~ory of the processo~
subsystem of the run length and associate color codes, to
be filled ~n at 156 acc~rding to the look up table, as
explained previously. In the advanced difference
reconstruction operations 145, the frame-to-framQ
differences and line-to-line differences tables are
:
- 36- ~32224~
decoded at 234 for decoding the differences from
frame-to~frame at 236 or changes from line to-lin~ at
238, with re~erence to the old picture memor~ 152, Also
~n the difference reconstructiorl operation, the tables
representing the edges and movement are decoded at 240
and 242, with the plcture information between th~ edgs~s
be~ng constructed by interpolation. The division at 246
o~ run length~ c~f the conoatenated digital word size to
run lengths of a four bi~ digital word size occllrs in the
run leng~ reconstxuction operation 150. The dec:oding o~
the compressed color codes ~n the color recon~.kn~tion
operation 156, accordirlg to the look up table, occurs at
248, allowing the four bi~, six bit, or eight bit color
component codes to be as~igned to the run lengths, ~or
storage at 250 ~n the display buffer memory 157.
Thus, referring to Fig. 14, in the statistis~
decoding of the fully compressed digitized signal, the
tables reconstructed are of the four bit digi~al word
s~ze run length 256, and the eight bit digi~al word size
RGB compressed color code 254. l'he run length-color
decoder treats the run length portion separately to
provide the four bi~ digital word siæe run lens~th
portions 256; and the eight bit digital word size R~;B
compressed color codes are de ::oded to provide th!
~ndi~ridual four bit digital word size RGB componen~s
256a, 256b, and 256c. The four bit run length and four
bit digikal RGB color codes are mapped to the bu~er
memory, for process~ng by the reconstruction engine, a~d
transmission to the p~xel generator, where the f :sur bi~
dlg~tal color component~ are expressed as an interpola~r
tion of six bit digital RGB components 258a, 258b, and
258c, for individual pixels between start and stc~p points
represent~ng the run length.
Although the invention has been described in the
context of a video telephone confer~3ncing system, the
~nvention may be also be adapted for use ~n decompres~ing
- 37 ~ ~3222~
color vidao data from magnetic media, such as hard disks
or three and a half inch high capacity magnetic floppy
discs which may bE! used in storing and communicating such
data via computer systems, or from video discs for video
disc players which could transmit the information in the
form of a video movie.
In the foregoing description, it has been
demonstrated that the method and system of the invention
permit compression and retrieval of color video data by
~he truncation of least significant information from the
color component codes, and the statistical encoding of
the most visually significant color code combinations.
The invention also allows for compression and re~rieval
of video color data after further processing of the color
~rideo data by further compression of the data by encoding
concatenated run lengths, line-to-line differences,
movement of segments of picture frames and portions o~
picture frames which have changed to reduce the amount o~
nformation to be encoded to the minimum amount. The
~nvention further provides for the additional coding and
decoding of data according to a form of statistical
encoding, which permi~s a further reduction of the amount
o~ mformation which must be transmitted by the system.
:'
