Note: Descriptions are shown in the official language in which they were submitted.
~49L:~
PHD 76--073
The invention relates to a method ~or transmitting
facsimile picture signals obtained from an element-by-element
scanning of an original by allocating code numbers to the
pluralities of successive element:s having the same luminence
value (1 run-length), and to a device suitable therefor.
Such methods for data compression by means o codin~
are used in facsimile systems to save transmission band-
width or transmission time are known. A coding method may
be used which operates with a ternary intermediate coding
and which ~urnishes optimum results ~or many documents.
Depending on the contents of the document to be transmitted,
(for example a weather map), other methods are, however,
possible which yield still slightly better results, the
differences being, however, relatively small. A method
which is generally used and which accomplishes a consider-
able reduction in the transmission bandwidth or transmission
time by means of a particularly ingenuous coding only may,
consequently, not be expected.
It is therefore an object of the invention to
provide a method with which the signals to be transmitted
are so processed prior to coding that in the subsequent
coding shoxter code words, at least on an average, occur.
According to the invention this is realized because each
run-length having the value 1 is extended to the run-length
~ ~ .
P~ 73
23-~1977
~ 3
having ~he value 2~ or~ should this result in a xelati~e
shift of the extended run-length by more than one picture
element~ is suppressed ancl that when allocating code numbers
only the converted run-lengths are taken into account and
that at the receiver end the recovered, converted run-lengths
are dir~ctly released.
As with most documents the short-run-lengths occur
most frequently a considex;able improvement o~ the data com-
pression can be obtained in this manner as the code words
for the short~run-lengths are still further compressed by
the method according to the invention. Namely, in many
coding methods the number o~ bits in the code word exceed
~or short run-lengths the number of picture elements to be
coded, for example~ with said coding ~et ~ s with ternary
intermediate coding the run-length 1 is represented by 1.6
bits, the run-length 2 and 3 by 3.2 bits and the run-length
4 by 4 A 8 bits In these cases the code word was longe~ than
the run-length itself. By means of the method according to
,
the invention no code word is allocated anymore to the run-
length 1 J as this run-length is no longer included in the
coding action but the run-length 2 is allocated to the
; shortest code word eto. so that, for example, with ternary
intermediate coding all run-lengths having the value
2n(n = 1, 2, 39~..) can be represented by 1.6 bits less. In
this man~er substantially all code words become shorter
than the run-length itselfO
The inorease in the grain size which is caused by
extending a length~1 is acceptable in substantially all
: . ~ :
~ ~3~
:: .: :
:
~ :
,- . . : :
PHD 76-073
cases and is often even hardly noticea~le. It was namely
found that a document which, for example, contains a
machine-written text and which therefore imposes already
certain requirements on the resolution of the scanning and
recording arrangement can be represented, even at an
element density of only four elements per mm at the record-
ing side by run-length the shortest of which consists for
both luminance values of two picture elements. Extending
the run-length 1 should not be confused with an increase
of the grain size of the total scan to double the value,
that is to say to half the scanning density, for the odd
run-length from the value 3 upward are retained. Further-
more, scanning a line having a width b, if it is located
between two scanning points which ara spaced from one
another at a distance b furnishes already, depending on
the setting of the threshold value of the scanning device
a run-length 0, 1 or 2. So ext~nding the run-length 1 to
the value 2 acts to a certain degree as changing the thres-
hold value of the scanning device.
It is known in principle to extend short signals
in ~he scanning of documants. However, this always refers
to a continuous scanning without clock control, the length
of the picture signals from a given minimum value being
transmitted in analog form and directly. Consequently these
methods operate with analog means and a coding of the sig-
nals to be transmitted is not provided.
:
~ 4 ~
:
:~
.. . . . .. . ~ :
.
P~JD 7~-073
23~2--1977
~ n accordance with Qn e~lbodiment o~ the Method
according to the invention extending the run length having
the value 1 can be per~ormed because each run-length having
the value 1 is extended with the last picture el~ment of
the preceding run-length having the other luminance value~
provided the preceding run-Length retains, wllen converted, at
least the value 2 and, otherwise is extended with the ~irst
picture element of the next following run~lcngth having the
other luminance value provided the following run-length, when
converted~ retains at least the valuo 2 and9 is completely
suppressed. In this manner it is accomplished that extending
the run-length having the value 1 to the detriment of a
preceding or next run-length takes place only then when these
connecting run-lengths retain at least $he value 2.
Performing the method according to the invention
can be done by a substantially dircct conversion o~ the
conditions indicated with the method in a loglc switching
network in conformity with the rules of the switchlng algebra.
To check whether the preceding and the ~ollowing run-length
retains at lea~t the value 2 a shi~t register can be provided
~or both of them.
An embodiment of $he invention will be further
, , ,
explained with re~erence to the drawing, in which-
` ' ~igure 1 is a block diagram of a device for per-
`~ 25 ~orming the method according to the in~ention,
~ igure 2 shows the succession o~ logic signals
in various points o~ the block diagram according to ~igure 1
at a variable succession of scanning signals,
::
,
::
.
P~ID 76-o73
23-2-l 977
1,
~igure 3 is an extensive circuit ~iagram of the
block diagram of Figure 1.
The scanned picture si~nal is applied in Figure 1
to the first storage element P2 of a shi~t register SR1~ In
the embodiment shown here the shift register SR1 comprises
only three stages~ storage elements P2 9 P1 and P0 respecti~ely~
as only these three stages are necessary for converting the
run-length 1. Each ti~le a new picture signal is applied to the
storage element P2 the contents of all storage elements are
simultaneously transferred one step to the right. The outputs
of the storage elements P2, P1 and P0 are connected to inputs
- of a s~Yitching network SW.
The output of the switching ~etwork SW leads to
the first storage element U0 of a shift register SR2 which,
in this example~ comprises two ~urther storage elements U1
and U2 which is sufficient for controlling the conversion of
the run-length having the value 1. A clock signal CP is
applled for controlling the storage elements P2, P1, P09 U1
. and U2~ whereas the storage element U0 is controlled by an
`20 inverse clock s:ignal CP. The outputs o~ the second and the
. third storage element U1 and U2 respectively are also con-
I nected to inputs of the switching network SW and the output . .
~ of the last storage element U2 is connected to a coder K. In
~ ~ .
the coder X code words are allocated in accordance with one
of the prior art methods to the run-lengths supplied by the
,
shi~t register SR2~ which code words are then transferred
. to the reoeiYer (not shown in the drawing) and reconverted
: into the run-lengths applied to the coder K at the *ransmitter
~ ~ .
:
6_ ,
. .
Pl-~ 76-o73
23~-1977
side and directly released.
The switching network SW consists of three sub_
switching networks SN1, SN2 a.nd SN3 which each consist of
logic switching elementsO ~'or the various input signals these
sub-switching networks suppl.y the output signals indicated
in the following table:
- TABLE
SN1 - L .for U1 ~ U2
SN1 - 0 for U1 = U2
SN2 = L for U1 = P0 - P1 = P2
SN2 = 0 for . ~.all other cases
SN3 = U1 for SN1 = L
SN~ P0 for SN1 = 0
SN2 = L
SN3 = P0 for SN1 = 0
- S~2 = 0
It should be born in mind that owing to *he control
. with *he clock signals ~P and CP the out;put of the third sub-
switching network SN3 is at the same ti~e the input of the
first storage element U0 of the second shift register SR2. ..
The meaning of these signals is further explained herebelow~
If the contents of the storage elements U1 and U2 is
di~ferent, it is a must that the output signal of the second
storage element U1 is supplied to the first storage element
U0 of the second shift register SR2~ to a~bid tha-t the contents
of this storage element differs from its neighbour U1 for
:; '
this would mean t,hat a run-Iength with the value 1 is supplied
-7-
: ~ .
` : ' . . :
. .
P~ID 76~o73
~3~2-1977
to the coder K. This condition is recognized by the sub-
switching network SN1 (Ul ~ U2 results in SN1 = L) and the
third sub-switching network SN3 is controlled in a corres-
ponding manner (SN1 = L results in SN3 = U1) as indioated
in the table so that the actual value of the next picture
element which is stored in the last storage element P0 of the
first shi~t register SR1 is suppressed. This condition has
priority to all other conditions for therea~ter changing the
contents of the shift register SR2 is no longer possible. This
results in the fact that any possible run-length with the
value 1 is extended *o the right to the detriment of the
nei~hbouring next picture element,
The sub-switching network SN2 checks the condltion
whether the storage element P1 o~ the first shift register
SR1 contains a run-length having the value 1 (P2 and P0 both
differ from P1) and whether at least the run-length 2 (P0 =
U1) precedes this run-length 1. As this condition (U1-P0=P1 =
P2 results in SN2 = L) only becomes effectiYe when the first
sub-switching network SN1 h~s the~output signal 0~ so U1 =
U2, it is ':herewlth established that a run-length of at
least 3 precedes the run-length 1 in the storage element P1.
So~ in this oase the run-length 1 may be extended to the
.. . .
~; left to the detriment of the preceding run-length which
~ is achievecL because $he third sub-switching network SN3 sup-
;~ 25 plies at its output the in~erted output signal of the last
storage element P0 of the first shift register SR1 (SN1 = 09
SN2 = L results in SN3 = P0) for with this condition this
;~ is just the non-in~erted ~alue o~ the last but one storage
'
,
8-
:.,
:~ .
. . ..
P~ 76-o~3
23--2~1977
element Pl
When neither the first SNl nor the second sub-
switching networ~~SN2 supplies an output signal L (SNl = 0,
SN2 = 0) the possibility does not exist that in the second
shift register SR2 a run-length 1 is present which must be
extended to the right or in the first shift register SRl a
run-length 1 which must be extended to the left, so that
consequently the scanned signal which has arived in the last
storage element P0 can be directly taken over in the first
storage element U0 of the second shift register (SNl - 0 ,
SN2 = 0 results in SN3 = P0).
The operation of the switching device of ~igure 1
will be described with reference to the time diagram in~
~igure 2 which shows the variation for a randomly scanned
signal sample, wherein the black elements in an original to
be transmitted are represented in the first line of the diagram
by means of crosses. The subsequent lines represent ihe
- contents of the storage elements of the first and the second
shift register SR1 and SR20 Tlle last lines represent the output
signals of the first and the second sub-switching network
SNl and SN2 whereas the output signal of the third sub-
; ~ switching network SN3 is equal to the contents of the first
storage element U0 of the second shift register SR2. T~e solid
.
.
crosses below the signal SN2 represent the black elements ~hich
correspond to the output signal U2 and which are printed
~ 25 : out in a recei~er. For comparison the dashed orosses in
;~ Fi~ure 2 represent the bl~ck elements of the original to be
transmitted~ a delay of four elements being present which is
produced b~ the device according to ~igure 1, The digits in
.
~ ~igure 2 represent a few o~ the columns.
,
g_ ,
:
P~ID 76-o73
23-2 1977
4'~3
At the beginning of the scan (at the beginning of
a line) the storage elements U1 and U2 are adjusted to a
given value (0) which corresponds to the background of the
document which is normall~ white. The contents of the storage
elements P0~ P1 and P2 directly ~ollow'~rom the scanned
signals, wherein, owing to the direction of shift to the
right in the shi~t register SR1 the s~orage element P0 con-
tains the signal ~hich was scanned first and the other storage
elements the corresponding subsequent signals. This means
in the diagra'm of Figure 2, at the chosen time axis t, that
with the three signal rows P0, P1 and P2 a shift upwards to
the right takes place and with the three signal rows U0 to
U2 a shift each time downwards to the right.
In the'co~umn 3 neither of the sub-swit¢hing net-
1~ works SN1 and SN2 furn~shes a signal as ¢an be easily checked,
' ' so that U0 directl~ takes o~er the state of P0~ (U0 = P0 = L).
In this respect attention should be paid to the ~act that the
storage element U0 owing to the use of the in~erse block
signal CP is not wxitten in before the other signals in this
column~ particularly on the outputs oP the sub-switching
~ ~ .
networks SN1, SN2 and SN3 ha~e assumed the right position.
' ' In oolumn 4 the contents of U1 and U2 are different
' so that U~ ta~es over the contents of U1 (=L) so that it is
certain no-run-length 1 can be produced in the second shift
25 ' register SR10 However,~as the scanned succession of signals
indeed contains in this place a run-length exceeding 1 (P0
ie also equal to L) the soanned succession of signals is
not changed thereby. The same applies for column 6~ where
:, ~
- 1 0-
.. .
: . '
~ PIlD 76-o73
,, , , _ 23-2-'l977
4 ~ 3
the ~irst white signal (U1 = 0) is au-toma-tically extended
by another white element (U0 - U1), the scanned signal
(P0 = 0) having, however the same value in spite thereof~
. A change does not occur until in oolumn 7. ~rom the
contents of P0, P1 and P2 it can be deduced that the ~irst
shift register SR1 contains a black run length having the
value 1 (O,L90). At the same time it can be deduced ~rom the
corresponding contents (0) o~ U2~ ~1 and P0 that this run-
le,ngth i.s preceded by a white run length having the value 3.
This causes the sub-switching network SN2 to supply a signal
L so that the inverted contents o~ P0, that is to say the
contents of P1 - L~ is *~ken over in U0. Herewith this black-
run-length having the value 1 is completed with an element
on the le~t-hand side9 that is to say to the detriment of the
,5 preceding whlte run-length having the value 3. By way Or
illustration re~erence is made to the solid and dashed crosses
in Figure 2 at the columns 7 to 10 inclusive. In column 8
bhe same takes place as in the columns 4 and 67 that is to say
the complementary picture element of column 7 is extended by
~: 20 the following pictu~e element which, however~ again corres-
ponds to the scanned signal so that again no change occurs.
A rollowing special ~eature occurs'in column 10, whtch
ollows a white run-length having the value 1, which in the
,~ , , .
original signal pattern occurs in column 7. Owing to the
devlating oontents o~ U1 a~d U2 and the signal L obtained
thereby at the out'put'of the ~irst sub-switching network
: SN1 ~he contents o~ U1 (= 0) is here taken over in U0
although the scanned signal in this place has~the opposite
::
,
: ~ : :: :
'-
.
.
PlrD 7G-073
23-2~19~
value (P0 = L). So thc white run-leng~th having the value 1
~U1 = 0 bet~een U2 = P0 = L) is here completed with one
picture clement to the right (U0 becomes 0)~ tha-t is to say
to the detriment of a ~ollowing run-length as the preoeding
r~n-length only has the value 2 and, consequently~ cannot
be shortened, it being irrelevant i~ this prcced:ing run-
length has the values 2 owing to a corresponding, scanned
signal or as the result of an extension. Here is shown the
advantage o~ the measure to per~orm an extension~ i~ possible,
~irst to the detrimcnt of the preceding run-length ~or in
t}Lis manner two successive run-lengths having the value 1 and
a dif~erent signal value can be extended and consequently
retained. Extending the white run-length to the right, per-
~ormed in the column 10 (and recorded in the columns 11
and 12) oauses the next black run-length to be shifted to
the right~ also oyer one picture element7 in the case this
run-length should have the value 2 and this also applies ~or
all immediately following run-lengths until a run-length occurs
which exceeds 2. In the example o~ ~igure 2 this is already
the next black run-length itsel~ (columns 12, 13 and 14)
so that shi~`ting ends at the end o~ this run-length.
In column 16 a shi~t to the le~t of a black run-
length having the value 1 occurs again (U0 becomes L)~ which
takes plaoè in the same manner as the shi~t lll the column 7
and which ~urnishes the crosses at the columns 1S and 19.
; : :
; In llke manner the next white run-Iength having in cclumn 17
P0 - L~ P1 = 0~ P2 = L and U1 ~ U2~ is shifted one place to
the right which results on recording in the white run-length
- ~ ,
12_
P~ID 7G - o ~3
23 -2~1977
...
in the columns 20 and 21. ~n col-~mn 18~ ho~ever, a black
run-length having thevalue 1 is presen-t in the scanned
signal (P1 _ L, P0 = P2 = 0). This run-length cannot af~ect
column 19 as extending the preceding white run-length has
priority as U1 ~ U2. An ex-tension to the right is also im-
possible as then a shift over more than one place would occur
so that the scanned signal values P1 = L in the column 18 is
suppressed in column 19 where U0 = U1 = 0, Also the sub-
sequent white run-length having the value 1 is suppressed
namely owing to the fact that therea~`ter aga~n a black run-
length having the value 1 follows. The latter is again
extended to the left (crosses at the columns 22 and 23) for
then the preceding white run-length in the succession of
output signals which reaches as fas as column 19 retains at
1~ least the value 2 which~ consequently~ is still permissible.
~he subsequent short white run length is again extended by
one place to the right etc. So, in this manner, a scanned
sucoession of signals having successi~e run-lengths of the
value 1 is converted into a succession of signals having
suocessive run-lengths of the value 2 and a corresponding
half-rate occurrence of th-e signal values so that the
succession ~ se ls retained albeit~ by necessity, with
only half the resolutlon.
igure 3 shows the details of the switching arrange-
m~nt o~ Figure~1. The two-shift registers SRI and SR2 com-
; prise storaee elemsnts which are designed as D-~lip.flops,
which transfer the signaI at the input D to the outputs Q and
Q under the control of~a clock signal to be supplied to
. ~
~,
.
~ -13-
: : ,
.. :
,,~
:
~ ~ .
;, ~ .. ~ ., :,
.
P~l]) 7G-o73
23-2-1 977
clock il1pUtS T, Herewith the storage elements P2, P1 and
PO as well as U1 and U2 receive the same clock signal CP9
while a dela.yed and the in~erse clock signal CP respect.ively
are supplied to storage elcment UO. The switching network
SW is again divided into three sub-swi.-tching network.s SN1
SN2 and SN3 to obtain a better comparison to the block
diagram of Figure 1. The sub-switohing network SN1 should
supply a signal L, when the contents of the storage elements
U1 and U2 is dif~erent. This is accomplished by the exclusive
OR-gate G1, which is connected to the output Q o~ these
storage elements. The signal L at the output of the exclusive
OR-gate G1 ef'~ects that in the sub-switching network SN3 the
output Q of the storage element U1 is con~ected via the
AND-gate G6 and the OR gate G9 to -the input D of storage
element UO, while at the same time the ~ND gates G8 and G7
and consequently the other input o~ the OR gate G9 are
blocked through the invertor I1.
The sub-switching network SN2 comprises the two
. AND gates G2 and G3 the inputs o~ which are each connected
to similar outputs of the storage elements P2~ PO and U1 and
to the opposite output o~ the storage element P1r The out-
puts o~ these AND-gates are combined in the OR-gate G4 whose
~ output consequently represents the output o~ the second
;~ sub-switching network SN2. When the OR gate G4 supplies a
signal L and the e~clusive OR~gate G1 simult~neously the
signal O *he AND gate G7 is released, which gate connects
.
the output Q o~ the storage element PO to the input D of
the storage element UO. When~ on the contrary, the -two
: : ~
~ 1 4-
~: .
, . . .. . ... ~ . . . . .. . . . . . .
P~ 76-o73
23 2-1~77
~ 3
logic switching elements Gi and G1~ supply the signal O the
AND.-gate G8 is released through the invertors Il and I2 ~ihich
AND-gate then connects the output Q of the storage element
PO to the input D of the storage element UO. In this manner
all conditions for the switching ne-twork SW are taken into
account,
In conformity wit:h the known rules of -the switching
algebra the switching network described can be simplified
in various manners~ depending on the ~act whether the
maximum number Or consecutively connected logic switching
elements~ the number o~ swl-tching elernents themselves or the
inputs thereof should be reduced to a minimum.
~: .
,
':
. ~ '': :
' .'. ,; " . :, .. ' , .~ ' , . :' .
. :~ . . : : . ; .
