Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
~ ~79778
BACKGROUND OF THE INV~rION
Field of the Invention
The present invention relates to encoding techniques,
and more particularly to a method for encoding electric signals
which ~e obtained during the scanning of graphic pattern with
a mixed content of text and pictures.
Description of the Prior Art
A method is known from the German published
application 2,516,332, for encoding electric signals which are
obtained during the ccanning of a graphic pattern having a
mixed content of text and pictures which is characterized in
that the graphic pattern is subdivided into sub-regions and a
picture code is used for encoding electric signals obtained
during the scanning of sub-regions essentially containing
picture portions, while for the coding of remaining sub-regions,
a text code îs used.
Picture codes and text codes can be selected from
a multiplicity of known codes according to different criteria
in such a manner that as favorable an encoding as possible of
the picture and text regions is guaranteed.
Typical criteria for the selection of a code are,
for example: a small requirement for memory space or transmission
time for the code signal generated by encoding; small suscepti-
bility to interference of the code signal; optimum quality--
according to aesthetic or other viewpoints--of the graphic
pattern which is reproduced from the code signal by decoding;
and compatibility with standardized codes.
~ 1~9778
Typical text codes are described in ~e article
"Facsimile Run Length Coding Using Run Length Prediction" by
P.A. Stern and W.E. Heinlein in the Siemens Research and
Development Reports, Vol. 3 (1974), No. 3, and tynical picture
codes are described in the article "Adaptive Delta Modulation
Systems for Video Encoding", by T.L.R. Lei, ~. Scheinberg and
D. L. Schilling in the IEEE Transactions on Communications,
Vol. COM-25 (1977~, pp. 1302--1314. The text codes discussed
in the first-mentioned article can, as is shown t~erein in an
example, also be used for encoding drawings. As is shown in a
further example,they are also suitable for encoding black and
white pictures which, as is customary in graphic patterns, are
printed in a raster method, whereby different levels of gray
are represented by larger or smaller black or white dots on a
bright or dark background. The encodin~ of half-tone pictures
by ~he text code set forth in the Stern and Heinlein article is,
however, advantageous only under the assumption that the
resolution or sharpness of the scanning suffices for the
reproduction of the position and size of the raster dots. The
same also holds true for the encoding of color pictures which
consists of several color components printed over one another.
For such pictures, the methods set forth above as well as the
method of the present invention, can find use in two alternative
obvious variations:
a) with the help of color filters, each color
component is detected indlvidually or is
calculated from a red/green/blue (R~B) scanning
signal as is provided by a color T.V.camera with
the help of a color computer which, according to
pattern of a known color T.V. coder, forms a
~ ~ 797~8
linear combination characteristic ~or each color
component out of thé three components of the
RGB signals;
each color component will now be encoded accGrding
to the method which is suitable for black-white
pictures whereby "white" is interpreted as "white"
and "colored" is interpreted as "black"; and
b) only the chrominance signal is encoded, whereby
parts of the pattern which are different from
white are interpreted as "black" regardless of
their color, so that, of course, this method cannot
reproduce the color values of the original in the
code signal.
However, it can also be advantageous, when the
scanning sharpness suffices for the resolution of the print
raster, to use one of the codes described in the article by
Lei, Scheinberg and Schilling for encoding half-tone pictures.
However, in an advantageous manner, with the use of a further
development as set forth in the German published application
2,516,332, of the method described therein, which is
characterized in that the scanning signal to be encoded with
the picture code is obtained by scanning with a decreased sharp-
ness such that the raster structure of the graphic pattern is
suppressed, whereby the scanning signal of decreased sharpness
is recovered, where applicable, from the scanning signal of
undecreased sharpness with the aid of a computer which copies a
scanning of decreased sharpness.
~ 179778
Another further development of the known method
is characterized in that a scanning signal obtained during the
scanning of a sub-region with unknown content is encoded with
a text code and the same scanning signal, or a second scanning
signal, is encoded with a picture code, that the two code
signals obtained are intermediately stored, and that the code
signal encoded with a text code is used in the case that its
length is not greater than the product of the area of the sub-
region and a predetermined proportionality factor, while other-
wise, the code signal generated with the picture code is used.
The use of this further development is, however,
advantageous only under the assumption that the scanning sharp-
ness suffices for the resolution of the raster in which the
picture content of the graphic pattern is printed; in other
words, the same is sufficient for the reproduction of the
position and size of the raster dots.
If the above assumption is fulfilled, then, on
the one hand, a picture region will be encoded with a picture
code having a great probability, while, on the other hand, even
when such a region is encoded by a text code, no impairment of
the picture content will occur due to encoding. Only the sub-
regions in which a false decision was made during encoding will
be encoded with a longer code signal than necessary.
However, if this assumption is not fulfilled, tnen,
on the one hand, during the encoding of a picture region with
a tex~ code, frequently such a short code signal will arise
that an encoding with a text code takes place; on the other hand,
the encoding of a picture region with a text code will bring
about a significant falsification of the picture content which
~ 179778
will noticeable in the picture which is reproduced after
decoding by the occurrence of large black or white spots. When,
herein, "encoding of a sub-region" is discussed, the encoding
of an electric signal is understood which is obtained during
encoding of the sub-region. When, furt~er, the "scanning
signal of a su~-region" is discussed, then the scanning signal
is understood which is obtained during the scanning of the sub-
region.
SUMMA~Y OF THE INVENTION
The object of the present invention is to provide
a method for the selection of a code for encoding sub-regions,
which is improved with respec~ to kno~m methods, which is
suitable even for such patterns and/or scanning models in which
the known method fails. In addition, the present invention has
the object of providing a refin2ment of the encoding in this
direction: that a selection is made possible not only between
two codes, namely, picture and text codes, but rather also
between several codes for picture and/or text.
The above objects are achieved, according to the
present invention, in a method for encoding electric signals
which are obtained during the scanning of a graphic pattern
with a mixed content of text and pictures which is characterized
in that, in an analysis of a first kind (boundary analysis),
at least one sub-region within the graphic pattern is detected,
that ~he scanning sîgnal originating from the scanning of a
sub-region is subjected to a following analysis, or several
following analyses of a second kind (region analysis), that the
results of the region analyses are evaluated for obtaining, in
each case, a code statement and where applicable a backup
statement and, that based upon an evaluation of all code and backup state-
ments, one of at least two predetermined codes is selected for encoding the
sub-region.
The present invention offers the advantage that a method for the
encodillg of electric signals which are obtained during the scanning oF a
graphic pattern with mixed content of text and pictures is made available
which is suitable also for such patterns and/or scanning models whereby
the methods heretofore known :fail.
According to another broad aspect of the invention there is pro-
vided a circuit arrangement for encoding electric scanning pulse signals
obtained from scanning a graphic pattern having a mixed content of text
and pictures, comprising: a scanning value decoder including a signal
input for receiving the scanning pulse signals, a signal output and a
reset output, and operable to produce output signals at said signal output
representing recognized scanning values and reset signals at said reset
output representing end of scan; first and second interval decoders connected
in series, each of said interval decoders including an input, a thresllold
value circuit having a respective thresllold connected to said input, and
first and second decision outputs, said first decision output of saicl
first interval decoder connected to said input of saicl seconcl inteIval
decoder, eacll of said interval decoclers operable to procluce OUtpllt sigllcllson said decision outputs re~resenting tlle magnitu(lc? of thei:r i~ ut siglla:Lsin relation to their tlrresllold values; a three-st;lge ;nterv;ll coullter,
each stage including all input connected to a precleter~ led clec:ision OUtpllt,a reset in~ut connectecl-to saicL resc?t outllut of said scallll:i llg clc?coclcr, ~mcl
an Outpllt; a calculatillg :register For calculating a characte:r:ist-ic n~ll)er,
including data inputs conllectecl to saicl co-lnter outputs, allcl an output Eorthe characteristic number; a code selection sw:itcll For selectillg a coclc?;
and a decision circuit connected between said out1-ut of sa:id calculatillg
regis-ter and saicl code selection switcll for contrc)ll:illg cocle selc?ct:ioll in
accordance \~ith the characteristic n~mlber.
3~3i~
According to another broad aspect of the invention there is
provided a circuit arrangement for encoding electrical scanning signals
obtained by scanning the graphic pattern having a mixed text and picture
contact, comprising: a scanning device for producing scanning signals
in digital form; a first buffer connected to said scanning device for
storing the digital signals; a first analysis device connected to said
first buffer and operable in response to buffer content to determine the
limits of regions within the graphic pattern; a second analysis device
connected to said first analysis device and to said first buffer for
analyzing the region content within the limits of the region determined
by said first analysis device; a decision device connected to said second
analysis device and operable in response to the analysis of region content
to determine which of at least two predetermined codes is to be used for
encoding the determined region; and an encoder connected to said first
buffer and to said decision device for receiving the digital signals from
said first buffer and encoding the same in accordance with the decision
of said decision device.
BRIEF DESCRIPTION OF TIIE DRAWINGS
Other objects, features and advantages of the invention, its
organization, construction and operation, will be best understood from
the following detailed description, taken in conjunction with the
accompanying drawings, on which:
Figure 1 is a plan view of the sub-division of a graphic pattern
M into sub-regions Tl--Tll which, with the exception of the sub-region T4,
are partially bordered by wllite blocks Wl--W16 and partially by a column
boundary S;
Figures 2 and 3 illustrate typical arrangcments of scanning dots
in the same graphic pattern in each case;
Figure 4 schematically illustrates a mode for a two-dimensional
quantization;
Figure 5 illustrates scanning signals Sl(t) and S2(t~ of the two
- 6a -
7 ~
first lines of a sub-region;
Figure 6 is a table having, altogether, nine two-dimensional
~uantization intervals;
- 61~ -
1. 17g~'~8
FIG. 7 is a schematic illustratîon of the
structure of an exemplary embodiment of a circuit arrangement,
or, respectively, a flow chart, for executing the method of
the present invention;
FIG. 8 is a schematic representation of a graphic
pattern having a rectangular sub-region T;
FIG. 9 graphically illustrates the energy spectrum
of a text region;
FIG. 10 schematically illustrates the energy
spectrum of a picture region;
FIG. 11 graphically illustrates a print raster
whereby the locations of black raster dots are characterized by
dots and the locations of white raster dots are indicated by
circles;
FIG. 12 is a quantization table for 3 x 5 two-
dimensional intervals; and
FIG. 13 is a schematic illustration of a device
for the statistical evaluation of the scanning values.
DESCRIPTION OF THE PREFERRED EMBODIME~TS
As was set forth above, FIG. 1 illustrates an
exemplary embodiment of the division of a graphic pattern M
into sub-regions Tl--Tll with the exception of the sub-region
T4, are, in part, bordered by white blocks Wl--W16 and, in
part, by a column boundary S. It is assumed that the sub-
regions Tl--T3 and T5--Tll can be determined corresponding to
a method set forth in the German published application
25 16 323 because of these boundaries. It is further assumed
that the limits of the sub-region T4 are previously known and
1. l7s~a
can be adjusted manually for the purpose of encoding. The
limits Gl and G2 indicated in FIG. 1 result in the case of the
use of a device described below by the realization of a method
practiced in accordance with the present invention.
FIG. 2 and FIG. 3 illustrate, as was also
previously set forth, typical arrangements of scanning dots for
the same graphic pattern. Associated with each dot of the
graphic pattern is a pair of coordinates (x,y), the origin of
which was selected in the left, upper corner of the pattern.
The orientation of the coordinate axes x and y were selected as
illustrated. In FIGS. 2 and 3, in each case a selection of
scanning dots in two variants of a column-related and line-
related arrangement, and further, the limits of a rectangular
sub-region are illustrated. These limits are to be interpreted
in that all scanning dots lying within the limits belong to the
same sub-region.
The graphic pattern is scanned with the aid of a
suitable device, for example, with a video camera or a facsimile
scanner, for example, with the video camera described in
Computer Design, Vol. 18, March 1979, p. 225, having the
designation "C-1000" or the facsimile scanner described in
Auerbach, Guide to Facsimile Equipment, p. 50, publlshed in
1975 by Auerbach Publishers Inc., 121 N. Bond Street,
Philadelphia PA. 19107, with the name "Model 500" (transmitter),
at whose output the electrical signal obtained during the
scanning, in the following designated as a scanning signal,
stands ready in a digital form or an analog form. The term
"digital", is understood in that the scanning signal is ready
in the form of a sequence of digital code words which, in general,
-- 8 --
I 179778
state the local brightness of the pattern for each dot of a
regular do~ raster (scannîng dot) as characterized in FIGS. 2
and 3. The code in which the scanning device states the
brightness of the scanning dots will be designated in the
following as a "scanning code". In the following, one proceeds
from the assumption that the scanning code is not compressed,
that is, in each case a code word having an n bit length
reproduces the brightness of a scanning dot with an accuracy of
2n brightness level, where _ is a natural number. As a
compressed scanning code, a code is designated from which, by
means of decoding with the help of a known method, for example,
a method described by Stern, Heinlein: "Facsimile Run Length
Coding Using Run Length Prediction", Siemens Research and
Development Reports, Vol. 3 (1974), No. 3 or in Lei, Scheinberg,
Schilling: "Adaptive Delta Modulation Systems for Video
Encoding", IEEE Trans. on Communications, Vol. COM-25 (1977)
pp. 1302--1314, a scanning code, ~hich is not compressed, can
be obtained. The scanning signal is now supplied to an
analysis of a first kind--where applicable after conversion of
the analog form into a digital form--for example, with the help
of an analog/digital converter which is known per se.
In the analysis of the first kind, at least one sub-
region is detected within the graphic pattern, that is, the
limits of the sub-region--represented, for example, by the
coordinates of two opposing corners of the sub-region--are made
ready in a digitally-coded form. The standardization of the
coordinates of the dot within a pattern is, in itself,
unimportant with respect to the present invention. However, it
is recommended to undertake the orientation of the two
1 ~79778
coordinates x and y as indicated by the arrows in FI5, 1,
whereby the origin of the coordinates coincides with the left,
upper corner of the pattern. In the case that the scanning
of the pattern takes ~lace line-by-line and within a line point-
by-point, it is recommended to use as a unit of the x-
coordinate the distance of two neighboring scannin~ dots and
as a unit of the y-coordinate the distance of two neighboring
lines.
Corresponding to a method set forth in the German
published application 25 16 332, it is advantageous to use white
blocks and/or print column limits as limits of sub-regions. As
is known according to customary language usage, an element
determining the limit of a region, for example, a ~arden fence,
in general is to be seen as a constituent of one of the regions
which it limits in ~he German published application 25 16 332,
however, nothing is said regarding the sub-regions which a
white block limits that it is seen to be as a constituent of
or, respectively, whether the white block is encoded with a
picture or a text code in the case that the white block is
detected as a limit between a picture region and a text region.
The lack of such information in the German published application
25 16 332 is based on the fact that the decision for the one
measure or the other measure under the requirements described
above for the use of a method of the German published appli-
cation 25 16 332 is not important. This applies to a limited
degree, also, for the present invention.
However, it is also practical to see a limiting
white block or portions of the same as a sub-region and to
encode the same with a selected code. For this purpose,prefer-
- 10 -
I 1797~8
ably a code comes into question which otherwise is provîded
for the encoding of text regions.
Another ad~antageous method for encoding a white
block region is that a scanning dot of a white block in each
case is assigned to that one of the sub-regions which it limits
and from which it is least removed. Regarding this, it is to
be noted that frequently, also, white blocks are located on
the limits of print columns as indicated in the upper half of
FIG. 1. A difference between the use of print columns and the
use of white blocks consists, for one thing, in that print
column limits can be used only as vertical limits of sub-
regions, whereas white blocks, on the other hand, can be used
as vertical and horizontal limits, and, secondly, in that print
column limits at least for a specific kind of pattern, for
example, a newspaper or maga~ine, in general, have a uniform
position with respect to the pattern and, t~erefore, can be set
ahead of time, while white blocks, in general, can be determined
by means of an analysis of the scanning signal (further above
called the analysis of the first kind).
For clarification, in FIG. 1, differently-limited
sub-regions are illustrated. For example, the sub-region T2
is limited on all sides by the white blocks, the sub-region T6
is limited on three sides and the sub-region T7 is limited on
two sides.
It is advantageous in using the method described
in the German published application 25 16 332, according to
which, preferably, white blocks are used as sub-region limits
to connect the analysis of a first kind which leads to the
determination of sub-region limi~s, where applicable) with the
3 ~79778
decision between the selection of a first code Cfixed code)
for encoding of the sub-region (decision A) and the further
analysis of the sub-reglon (decision B).
According to the invention, the decision A takes
place when the sub-region is limited rectangularly and at at
least two opposing sides by whlte blocks and/or column limits
and t~e distance of opposin~ white blocks falls below a preset
minimum value. This method rests upon the fact that pictures
in graphic patterns of a specific kind do not fall below a
specific minimal extension either in the horizontal direction
or in the vertical direction. However~ it is not out of the
question that in pictures themselves, white blocks appear. It
is therefore advantageous to make the parameters of this
decision, namely that these of the mentioned minimum value as
well as the number of the white blocks detected as limits,
adjustable, so that an optimum compromise can be made, where
applicable, dependent upon the kind of pattern to be encoded,
between the efficiency and the accuracy of the method of the
present invention.
In the case of the decision B, there takes place
at least one analysis of a second kind according to a method
suitable for the same for each of the sub-regions detected in
the analysis of the first kind. As soon as the results of the
analysis (es) for a specific sub-region is available, by means
of evaluation of these results, the decision is made as to
which code is to be used for encoding the sub-region.
As soon as the decision is present concerning the
code to be used for all detected sub-regions, one continues,
where applicable, with the detection of further sub-regions as
l 179778
described ahove. This process is repeated until the total
graphic pattern is sub-divide~ in sub-regions without gaps and
a code is determined for each sub-region.
It is advantageous when specific method elements
of the method of the present invention--be it in the detection
of sub-regions, be it in the detection of an optimum code for
a specific sub-region--are replaced by means of the withdrawal
of the data which would occur as a result of the method step
from a data memory or by manual adjustment, in the case that
the data in each case are known.
It is advantageous when the data memory for a
specific kind of graphic pattern, for example, for specific
magazines or specific pages of a magazine, is filled with data
which are characteristic for this kind of pattern. This applies,
in the general sense, for a manual adjustment. For this, the
operator adjusts a specific type of encoding, for example,
"only picture code for this and that page" manually. This can
result in an advantageous gain of time in specific cases.
The encoding of the sub-regions with the code
determined in each case or, respectively, the generation of the
code signal, as well as its transmission to a memory or to a
partner can, according to a measurement of the available buffer
memory and computer capacity, occur at any later point in time,
sequentially for the individual sub-regions or simultaneously
for several sub-regions. It is, where applicable, advantageous
also to generate an encoding of a sub-region with several
different codes or with a preferred code already before the
determination of the code which is to be used for this sub-
region, to store the code signals and, in each case, after
1 lL7977~
determination of the code to be used for the sub-region, w~ere
applicable, to generate the code signal not by new encoding
but rather by selection from the stored code signals. This
method also makes possible an advantageous gain of time.
As was already set forth above, FIG, 7 illustrates
schematically the structure of an exemplary embodiment of the
invention for circuit arrangement or, respectively, a flow chart
~or the execution o~ ~he method of the present invention. By
scanning the pattern M with the help of a scanning device A,
a scanning signal is obtained in digital form and via an output
3 of the scanning device A is stored in digital form in a first
buffer memory Pl by way of its input 4. The storage occurs,
for example, such that a selection of scanning dots of the
pattern M arranged line-wise and column-wise, as illustrated
in FIGS. 2 and 3, to each scanning dot, in case eight-bits of
the memory are associated which state the pattern brightness in
this dot. It is assumed in this example that, because of the
limited capacity of the first buffer memory Pl, first only a
partial section, for example, a strip Sl of the patt~rn, is
scanned and stored. The lower boundary of the strip is
designated as SlR.
A first analysis device Al sub-divides the strip
into sub-regions in which it takes scanning values from the
first buffer memory Pl via its output 7 and subjects the same
to an an~lysis whose results are the limits of the partial regions
or, respectively, the limits of white blocks which, for their
part, limit the sub-regions. Where applicable, the strip Sl is
determined to be a single sub-region. By way of an output 23,
the first analysis device Al transmits to an encoder CD the
- 14 -
l ~7977~
limits of sub-regions for which a decision is already possible
in favor of a specific code to.be used for the encoding of the
sub-region because of their dimensions and their boundaries
according to the method of the present invention, as well as,
where applicable, the identification of this code.
The encoder CD, if required, takes over from the
first buffer memory Pl the scanning values obtained from the
sub-regions, encodes the same with the use of the identified
code or a stipulated code and stores the code signal which is
generated in a second buffer memory P2 from which the output
is provided to a further memory or to a partner. Scanning
values obtained from white bloc~s must not absolutely be
transferred from the first buffer memory Pl, but rather can,
where applicable, be replaced by a uniform white value.
The limits of those sub-regions for which a
decision is not possible in favor of a specific code according
to the above method are transmitted by the first analysis device
Al via an output 10 to a second analysis device A2 which
derives analytical results for each sub-region from an analysis
of the scanning values originating from the sub-regions which
are taken via the output 6 of the first buffer memory Pl and
via an output 14 and provides the same to a decision device E.
This makes the decision, which of at least two
preset codes is to be used for encoding of the sub-region, in
each case, and provides the identification of this code to the
encoder CD which carries out the encoding of the sub-region, as
described above.
~ ~ 79778
As soon as the encoding of the sub-regions
detected in the strip Sl of the pattern S and the transmission
of the code signals in each case into the second buffer memory
P~ is concluded, the scanning of the pattern stri~ S2 occurs
adjacent to the strip Sl and the transmission of the scanning
values obtained are input into the first buffer memory Pl.. With
this, the scanning values originating ~rom the stri~ Sl can
be overwritten if the subdivision undertaken by the first
analysis device Al of the strip Sl into sub-regions was
complete. The lower limit of the strip S2 is designated into
FIG. 1 as G2.
It is advantageous that pattern elements of the
analyzed segment or, respectiyely, strip, under certain
circumstances are not associated to a sub-region but rather to
a so-called residual class. This will apply particularly
frequently for pattern elements which are located on the
lower edge of the strip. In this case, according to the
present invention, one proceeds as follows. the scanning values
of the sub-strip of the strip Sl next to the strip S2 (SlR in
FIG. 7) in which the scanning values are located which are
associated with the residual class are kept in the first
buffer memory Pl and--in the case of limited memory space--the
strip S2 will be selected to be correspondingly narrower so
that the scanning values of both the sub-strip SlR and the
strip S2 may be accommodated in the first buffer memory Pl.
This is indica~ed by the different sizes of the strips Sl and
S2 in FIG. 1.
Followi.ng this, the analysis and encoding of the
scanning values stored in the first buffer memory Pl takes
- 16 -
~ ~79~8
place, to the extent that t~e same do not belong to a sub-
region which is already detec~ed and encoded.
The sequential description ~ the method of the
present invention does not exclude the possibility that with
respect to a saving of time, several of the method s~eps
described above occur simultaneously. For example, during the
analysis of the second kind of a sub-region, an analysis of
the first kind can occur for the determination of further sub-
regions. Also, during the analysis of the second kind of a
sub-region, the encoding of another sub-region can take plaee
whose optimum encoding was already determined. Finally, it
can be advantageous to apply the method ~ the invention for
carrying out analyses of the first kind and the second kind
both for the encoding of sub-regions simultaneously on
several sections of the pattern, for example, the strips
designated in FIG. 7 as Sl and S2, whereby, however, the
method mentioned for residual class formation cannot be used.
In any case, during a simultaneous progress of the
method, certain devices for the realization of the method of
the invention must be multiply present. To the extent that
this concerns devices for the controlling of the progress of
the method, for the carrying out of transformations of the
encoding and for the analysis, for this, a multi-processor
system can be used.
In place of different decision feedback connections
which, as needed, can be directed between random elements of
the circuit arrangement of FIG. 7, two decision feedback
connections are illustrated, in particular, from the output 13
of the decision device E to the input 9 of the first analysis
1 17~3778
device Al and from the output 19 of the encoder CD to the
input 2 of t~e scanning device A in FIG. 7, They signal, for
example, the completion of an operation which is to be carried
out, for example, the analysis or, respectively, the encoding
of a sub-region, and thus signal readiness for carrying out
~he next operation.
The decision feedback connection mentioned above,
in particular, has the task of rejecting the determination of a
sub-region which proceeded by means of the first analysis
device Al if the analysis of the sub-region carried out in the
second analysis device A2 does not result in a sufficient
accuracy statement concerning the code to be used for the sub-
region. In this case, the scanning dots contained in the
rejected sub-region are assigned to the residual class of the
analyzed strip and one proceeds as described above.
In contrast to the method set forth in the ~erman
published application 25 16 332 for the differentiation of
text and picture regions, scanning sharpness signals which
suffice for the resolution of the printing raster structure of
scanned pictures are not required, according to the present
invention, for the analysis of the first kind (region limits
analysis) or for specific methods set forth below for carrying
out, again according to the present invention, the analysis of
the second kind. It is, however, possible that methods
according to the invention reauire the variable adjustment of
specific parameters in dependence upon the printing raster
freedom of pictures which are scanned, in particular, a special
adjustment for such pi.ctures whereby the scanning sharpness
does suffice for the resolution of the printing raster structure.
1 179~78
- In order to make an accommodation of method
parameters to the printing raster structure unnecessary,
entirely or to a large extent, it is advantageous in the case
of the use of such analyzing methods which are not dependent
upon a resolving of the print raster structure to subject the
scanning signal to a pre-filtering ~efore execution of the
limit and/or the region analysis which corresponds to a
scanning with a sharpness which is reduced to such an extent
that the raster structure is suppressed. Hereby, it suffices
if the decreasing of the sharpness takes place only in a
specific direction, for example, in the case of line-by-line
scanning, in the line direction.
The method can also be used in the apparatus
constructed in accordance with the present invention and
schematically illustrated in FIG. 7. Devices for pre-filtering
are not îllustrated in FIG. 7, nor are the devices for
decreasing of the scanning sharpness corresponding to the
German published application 25 16 332. Rather, in FIG. 7,
they are considered as components of the analysis devices Al
and/or A2. or, respectively, of the encoder CD.
A further development of the method of the present
invention is characterized in that for a selection of scanning
dots for the sub-region, from a scanning signal, the pattern
brightness and/or the quality of gradients of the pattern
brightness is determined in a transformed and quantized form,
that a selection of the single-dimensional intervals or,
respectively, two-dimensional intervals which arise by means of
the quantization have associated thereto, in each case, an
analysis result value per interval and that the frequency with
- 19 -
~ ~L79778
which an interval occurs within the sub~reg~on is transmitted
to the analysis result value which is associated with this
interval.
For the understanding of the following ex~lanations,
it will first be explained what is to be understood by "pattern
brightness" and "gradient of t~e pattern brightness".
Each dot within the gra~hic pattern can be stated
by means of a pair of coordinates (x, y~ whereby the axes of
the coordinates are defined corresponding to FIG, 1~ As
pattern brightness, here a function h Cx,y) is designated
which states the reflection factor or the light Permeability
for light of a given spectral composition measured in the dot
with the coordinates (XJY?-
As gradient of the pattern brightness, a vector isdesignated having the two components:
gl (x,y~ h (x,y)
g2 ~x,y) = ~y H (x,y~.
The quantity of the gradients of the Pattern
brightness is desi~nated in the following as b (x,y), where
b (x,y) is given by the following relationship:
b (x,y) = ~ g2 (x,y) + g2 (x.y).
From the scanning signal, for a sele.cted quantity
of dots Pi of the sub-region, ~referably in the qub-region
corresponding to FIG, 1, equidistantly arranged dots, a
transformation h' Cxi,yi~;b' Cxi,Yi) of the value pair
h (xi,yi~; b Cxi,yi~ is determined and subjected to a two-
dimensional quantization in that h' (xi,yi~ is quantized at ~A
- 20 -
~ ~ 79778
quantization levels and b' Cxi,yi~ i5 quantized at NG
quan~ization levels. Hereby, each value pair h' (xi,yi);
b' (xi,yi~ is associated with ~ne of the t~tal NA:NG two-
dimensional quantizati~n intervals.
For the clarification, in FIG. 4, the six two-
dimensional quantization intervals are schematically illustrated
which result in, for the quantization of the transformed
pattern brightness, NS=3 was selected with the quantization
thresholds 1 and 3 and when for the quantization of the
transformed amount of the gradient of the pattern brightness
~G = 2 was selected with the quantization threshold 2. The
six quantization intervals are numbered 1--6, Of these, the
intervals 3--6 are opened on one of two sides.
In accordance with this, for example, the pair of
valuesC2, 5: 1, 5~ are associated with the quantization
-
interval 2 and the value pair (O, 5; 3, 1) are associated with
the quantization interval 4. In FIG. 4, 1 cm was selected as
a unit.
A transformation of the value pair h (xi,yi);
b (xi,yi) consists, for example, of:
an integration of the pattern brightness over an
environment of the dot (xi,yi)(such an integration
proceeds unavoidably by means of the optical and
electronic lack of sharpness of the scanning
device, however, it can be intentionally intensified
or changed for the filtering out of interferences
within the pattern~;
~ 179778
a non-linear transformation o the ~îcture
- brîghtness which is caused b~ the scanning device
or is applied subsequently to the scanning signal;
a sLmplification of the com~utation of the
gradient amount, for example, such that the
di~ferential quotient of the ~rightness is
replaced by the differential quotient of the
transformed brightness corresponding to the
equation
b' (xi,yi) =
¦~h (Xi+l Yi) ~ h CXi-l~ Yi) 1 2 ~ ~ (xi Yi*l)-h (Xi-l~Yi) 1 2;and
l Xi+l - Xi 1 ~ ~ Yi+l - Yi-l
Another simplification of a computation of the
gradient amount would consist in that the amount of the gradient
is replaced by the sum of the amounts of its components or by
the maximal value of the amounts of its components or another
function of the amounts of its components which represents a
measurement for the steepness of the brightness transitions
at the selected scanning dots of the ~raphic pattern.
Further, and according to the invention, for n
two-dimensional quantization intervals which represent a
selection from the total of NA:NG intervals noted above, one
counter each is present into which is read the number of the
selected dots Pi of the sub-region which are associated with
the interval in that the value pair h' (xi,yi); b' (xi,yi)
falls into th.e interval in each case. The reading in can
occur, for example, such that all counters are set to zero,
that then the associated intervals are determined seauentially
1 ~1.797~8
for all dots Pi and thereby in each case the counter
associated with the interval is incremented by one, to the
extent that a counter is provided for this interval. After
completion of read-in, the counts of the counter are ~ailable
as analysis results.
A further advantageous form of this selection
consists in that a transformation is undertaken by means of
integration of the pattern brîghtness--as mentioned above--
which simulates such a decreasing of the scanning sharpness
that the raster structure of raster pictures is suppressed,
The selection of this transformation can frequently be made
uniformly for a specific kind of pattern, for example, a
specific magazine.
It is advantageous to associate no counters to
specific intervals when the evaluation of their frequency is
not required for the code statement by the decision device E.
Whether this applies can be tested, where applicable,
experimentally. To the extent that the result of this test
turns out differently for different classes of patterns, it is
advantageous to select the association of a counter to a
specific pair of numbers in dependence upon the class to which
the graphic pattern to be encoded belongs, for example, a
specific magazine.
Correspondingly, it is advantageous to select the
characterizing Eeatures of the transformation and of the
quantization, in particular the limits of the quantization
intervals as well as their number NA or, respectively, NG,
based upon experimental investigations, for example, in
accordance with the v:iewpoint that an optimum compromise is
l 179778
found between the expense for the decision devices E and the
reliab;lity and speed of t~e code statement. This selection
can be made for different pattern classes in a different
manner.
A particular ~orm of this selection consists in
that either NA or NG i9 selected equal to`l. In this case,
the determination of. h' (xi.,yi~ or, respectiveIy,.b.' (xi,yi)
-
becomes unnecessary because for the determination of the
quantization interval associated with the pair of values, only
one of the two val.ues must be quantized, The corresponding
devices for the determination h' or, respectively,`b', can
then, where applicable, be eliminated.
Another advantageous further development of the
method of the present invention is characterized in that for
a selection of scanning dots of the sub-region arranged line-
wise and column-wise, by means of a first quantization at NA > 2
levels, quantized brightness values are determined which
represent the pattern brightness values are determined which
represent the pattern brightness in a quantized form in the
scanning dots in each case, that from the quantized brightness
values with the help of a second quantization at NL > 2 levels,
run lengths are determined in quantized form, that in each case
one analysis result value per interval is associated with a
selection of the two-dimensional intervals which arise by means
of the first and second quantizations, that the frequency with
which an interval occurs within the sub-region is transmitted
to the analysis result value which is associated with this
interval. This further development will be explained more
precisely in the following, with the use of FIG, 5 and FIG. 6.
- 24 -
I ~ 7977a
FIG. 5 illustrates t~e scanning signals SlCt~ and
S2Ct~ of the two first lines of a su~-region as weIl as, b~
means of a quantization, scanning values ~7hich are quantized
at three levels with the thresholds `1,` 5 an* 2`, 5, which
represent the pattern brightness in the scanning dots of these
two lines. In FIG, 5-0`.5 cm was selected as a unit for
representing Sl(t) and S2(t~,
Further, in FIG, 5, run lengths Lll, L12,,,L21,
L22...L31, L32...are illustrated. Hereby, for example, L23
signifies the third sequence of brightness values of the second
quantization level which occurs within the sub-region.
FIG. 6 illustrates, in tabular form, the nine two-
dimensional quantization levels numbered 1--9 which occur by
means of the first quantization and the second quantization,
whereby for the second quantization, three levels were assumed
with the thresholds 1, 5 and 3, 5.
Further, in FIG. 6, for each quantization interval
set forth in parentheses, the number of the run length is
stated which drop out at the interval in each case when only
the run lengths depicted in FIG. 5 are considered.
For illustrating the quantization intervals, 1 cm
was selected as a unit for both coordinates.
The levels of the first quantization and the
second quantization (NA or, respectively, NL) as well as the
quantization thresholds in each case can be determined
experimentally for a specific pattern class in view of random
optimality criteria, just like the optimum selection of the
quantization intervals with which an analysis value is
associated.
l 179778
An advantageous modification in the senæ of a
simplification of the method results in that, to an analysis
result value, in place of the frequency of the two-dimensional
quantization interval, the sum of the frequencies of several
two-dimensional quantization întervals is transmitted, in
particular, the sum of the fre~uencies of all quantization
intervals which are associated with the same scanning value-
quantization level.
For example, if one proceeds from the quantization
intervals illustrated in FIG. 6, the sum of the frequencies
of the intervals 1, 2 and 3_would be transmitted as a first
analysis value, the sum of the frequencies of the intervals
4, 5 and 6 as a second analysis value> and the sum of the
frequencies of the intervals 7, 8 and 9 would be transmitted
as a third analysis value, from which the analysis values 6,
10 and 2 result.
_
To what extent the optimum number NA of the
quantization levels of the first quantization depend upon the
pattern class to be encoded can be shown with the following
example.
If the sharpness of the scanning suffices for the
resolution of the picture print raster, a two-level quantization
(NA=2) of the scanning values suffices for the application of
the method of the present invention. In the case that this
prerequisite is not fulfilled, better results can be expected
from a multi-level quantization (~ > 2),
This further development of the invention is
characterized in that an analysis result value is associated
with a selection of two-dimensional spatial frequencies in each
- 26 -
l~977~
case, that for e~ch of these frequencies, the amount of the
spatial energy spectrum of the su~-region is determined,
where applicable, in transformed form which is averaged over
the environment of the frequency and that the amount is
transmitted as the associated an~lysis result value~
A more precise explanation of this technique is
given below with respect to FIGS, 8--10.
FIG. 8 represents a graphic pattern having a
rectangular sub-region T. If, as in FIG. 8, ~e designates the
coordinates of the two corner dots lying opposite one another
with (xl,yl) and (x2,y2), then, in a known manner, the two-
dimensional complex spectrum of the sub-region is calculated
for a two-dimensional spatial frequency (x',y') which consists
of two components, namely, the single-dimensional spatial
frequencies x' and y~, according to the relationship
H(x ,y ) = 3 12 h(x,y) ei27r (xx +YY') dx dy (1),
y Yl x=xl
where h (x,y) is the curve of the pattern brightness
represented as a function of the coordinates.
By the amount of the energy spectrum of the sub-
region, here a function E (x',y') of the spatial freauency is
understood which, for its nart, is defined as a function of
the complex frequency H (X I Y I ) through one of the following
two equations
E (x ,y ) = ¦H(XI YI)I (2)
E (X Y ~ H(X ,Y~)I 2 + ¦H(X~,_Y~)I (3~
depending upon whether the frequency pairs (x',y') and (x', -y')
i ~ 79778
are associated with a common two-dimensional spatial frequency
(x',y'~ or not--whereby x' and y' are not negative.
The efficiency of the method of the present
invention is not decisively dependent upon one of the other
depiction of the ener~y spectrum is obtained corresponding to
the one or the other formula.
The determination of the energy spectrum or,
respectively, of t~ complex spatial spectrum is only possible
in more or less approximated or transformed form. Suitable
transformation methods are, for example,
a~ the integral equation (1~ is replaced
by a summation corresponding to the
equation
H(x',y') = ~ h(xi,yk)e i ~ (Xix + Yk Y ) (4)
summed over a selection of dots ~xi,yl), for example, dots
arranged regularly as in FIG, 2; and
b) the amount obtained through formula 2
or, respectively, formula 3, is replaced by
a monotonic non-decreasing function of the
amount or by the sum of the amounts of the
imaginary portion and the real portion of
H(x',y') or by the maximal value of the two
amounts.
In any case, according to the invention, the
determination of the energy s~ectrum takes place for a selection
of spatial two-dimensional frequencies which, similarlv to the
pattern dots in FIG. 2~ can be arranged in regular frequency
intervals within a preset fr~quency range.
- 28 -
~ ~797~8
It is, where applicabIe, advantageous to eaualize
local fluctuations of the energy spectrum ~y means of averaging
over the environment of the sPatial frequency in each case.
Such an averaging can be described by the formula:
00 ~,o
FCx~,y`~ = J ~ ~TCu,v~ E(x'-u,y'-v~ du dv (5),
wherein ~(u,v) signifies a weighting function which is select-
able according to need and experience, E is the energy snectrum
as descri~ed above and F Cx',y') is the energy spectrum
averaged over the environment of the frequency (x',y'). Again,
the integral can be replaced by a summation.
For example, the determination of F (-x`',y') for a
selectlon of spatial frequencies Cxl-',-yl'),(`x2`', y~ ,etc
takes place by averaging of, in each case, four neighboring
values of the energy spectrum corresponding to the formula:
F (x',y') = 1/4 (E(x'- ~\x',y'- y'~+E(x'+ ~x',y'- ~ y')+
E (x'- ~ x',y'+ ~ y')+ E (x'+ ~ x',y'+ /\y')) (6)
wherein x' and ~ are predetermined frequency intervals.
The values of the energy spectrum obtained, where
applicable in averaged and transformed form, can now be turned
over to a decision device which, from this, can derive a
decision regarding the code which is favorable for the sub-
region, because the energy spectra of ~icture regions and text
regions, in general, differ significantly. This is illustrated
in FIGS. 9--11.
FIG. 9 schematically represents the energy spectrum
of a text region, while FIG, 10 schematically represents the
energy spectrum of a picture regîon as a function of the
- 29 -
l 1797~
spatial tw~-dimensional frequenc`~ x'~,`v~', In eac~ case~ those
frequency ranges are hatched in which the avera~e ener~y
spectrum exceeds a specific threshold. In FIG. 10, secondary
spectra (Nl, N2...2 are identifiable which arise by means of
the structure of the printing raster illustrated in FIG, 11
In FIG. 11, the locations of the black raster dots are
identified by dots, and the white raster dots are identified
with circles.
A further advantageous development of the
invention provides a method for obtaining a code and a back-up
statement out of a pregiven number of analysis values as
result in the case of the use of the further developments of
the invention which concern the advantageous analysis methods.
This metnod is characterized in that, for all
except one analysis value, the relative portion of the
analysis value is determin~d from the sum of all analysis
values, that by means of quantization of such portions, a
multi-dimensional interval is determined, that a memory is
provided in which a memory region is assîgned to each possible
interval, that each memory region contains a code statement
and, where applicable, a back-up statement and that the code
statement and, where applicable, the back-up statement or
accuracy statement is taken from the memory region which is
assigned to the interval which is determined.
This method will be explained in ~reater detail
below with the use of equations, as well as with a numerical
example.
- 30 -
1.~797~8
Here, it is assumed that N designates the number of
the analysis values, `z(`I~, ZC2).~.ZCN~ designate the analysis
values themselves. It is assumed that the analysis values are
not negative.
~ ith this assumption, the reIative portion of the
analysis value z(k) is provided ~y
p (k) = z Ck~ / ~ z (i)-
The end portion p (_)are not independent of oneanother because their sum is 1. Therefore, they are
unam~iguously determined by a selection of (N-l) portions. Let
the portion which is considered to be p(k'), where k' is a
number selected from the region (l, N).
If now for all portions p (_~with the exception of
p (k'), which did not need to be determined, one undertakes a
quantization with in each case S (_)levels, then this signifies
that one associates the analysis result represented by the
N analysis values to one of a total of
1~ S(k)
k = 1, k'
(N~ dimensional quantization intervals. This will be
explained below with the following example, as well as by means
of FIG. 12.
Let N=3 and let the three analysis values be:
z (1) = 2,
z (2~ = 3,
z (4) = 5.
- 31 -
~ ~7~77~
Let k = 2 be selected, that is, the second
analysis value is not considered in the selection of (N-1~= 2
analysis values. ~Jith this it is determined
p (1~ = 2/10 = 0,2, and
p c3~ = 5/10 = ~,5-
Let the following quantizations be selected forthe analysis value p(l) and ~
for ~) the level number S(l) = 3 with the
threshold 0.05 and 0.15; and
for ~5~) the level number S(3) = 5 with the
thresholds of 0.1, 0.2, 0.4, and 0`.7.
By means of this quantization, the 3 x 5 = 15 two-
dimensional intervals illustrated in FIG. 12 are defined. The
analysis result provided above as an example is associa~ed with
the interval designated 14 in FIG. 12.
The scale of FIG. 12 was selected corresponding to
1 cm = 0.1.
-
The association of a memory region with a specificmulti-dimensional interval can, for example, occur as follows.
The possible quantization intervals are successively
numbered beginning with 1, for example, according to the
pattern illustrated in FIG. 12. As soon as an interval is
determined, the product of the interval number (C) and a pre-
determined natural number B is determined.
The product C x B is used as a distance address
measured in bits at the beginning of a memory field which is
used as a table within a data memory. In this table, in B
consecutive bits in each case, the number is stated for the
- 32 -
~. 1797~
optimum code for the pertaining sub-reg;on.
For B = 1, by means of the content of the table,
the decision is set ~etween a text code in the case of a
specific table place content, for example, O, or a picture
code in the case of another table place content, namely, l~
The content of the table is determined by statistical
evaluation of a given quantity of representative patterns.
The characteristic number C is determined for one
or several sub-regions of each pattern of the re~resentative
quantity. From the characteristic number C, in addition, a
memory region of the table is determined. This memory region
is filled with the number of the optimum code for sub-region
in each case, whereby it is presumed that this optimum code is
known. After an evaluation of all graphic patterns of the
representative quantity, it is checked, for each value of the
characteristic number C which can appear in the class of
graphic patterns to be encoded during evaluation of a sub-
region, whether the pertaining table position has been filled,
For checking of the pertaining table positions, an
auxiliary memory is used in which a bit is associated with each
value of the characteristic number C. Before the beginning of
an evaluation of the graphic patterns of the representative
quantity, the binary value O is assigned to all bit positions
of the auxiliary memory field. During the evaluation of these
graphic patterns, in each case when a value is determined for
the characteristic number C, the binary value 1 is assigned to
the bit position of the auxiliary memory field corresponding
to this.
- 33 -
~ l7s7~a
~ fter the discovery of a non-filled table ~osition,
the characteristic num~er C' which is most similar to this
associated characteristic number C is determined. The
pertaining table position is filled with a conten~ of the
table position which is associated with the most simî-lar
characteristic number C'.
The characteristic number C' which is most
simîlar to a specific characteristic number C îs determined by
means of a distance functîon in that all characteristic numbers
to which the binary value 1 was associated in the auxiliary
memory are compared with the characteristic number C. That
number is selected as the most similar characteristic number
C' for which the distance function Produces the smallest
deviation between the characteristic number C and the most
similar characterîstic number C'. As a distance function, for
example, the summation of the absolute differences of the
positions of the two characteristic numbers C, C' can be used,
For the case that n > 1 characteristic numbers
Cl'...Cn' having the same similarity, namely, with the same
distance function, are found, that a characteristic one of the
numbers Cl'...Cn' is selected which differs least by means of
the algebraic difference from the associated characteristic
number C.
According to another further development of the
invention, ln a portîon of the memory field of the B bit which
is associated with each characteristic number C, there is
contained a second statement concerning the accuracy of the
statement determined in the remaining positions of the memory
field.
- 34 -
I. 1797~
According to anot~er further development of t~e
invention, the selection is made from a num~er of alternative
codes under consideration further evaluation composition
associated thereto in each case.
The second statement mentioned above concerning
the accuracy is determined according to another further
development of the invention from the number and nature of the
code statements found for the most similar n characteristic
numbers Cl'...Cn', whereby the distance in each case to the
characteristic number C is considered.
If during the setting-up of the table, a table
position is recognized to be already filled, then the character-
istic number C which has just been determined is marked with a
number of the optimum code in an additional table. This
additional table is checked after the setting-up of the table.
For all characteristic numbers C which appear in the additional
table in multiple with different code numbers, an optimum code
is determined by means of a compromise decision. This
compromise decision can be made according to an exemplary
embodiment of the invention by means of a majority decision,
whereby that code is finally entered into the table which
appears most frequently for the same characteristic number C
in the table and in the additional table. The compromise
decision mentioned above can also be made advantageously in that
one proceeds according to the principle of minimum damage, where-
by that code is entered into the table which for a transmission,
a reproduction or other process represents the optimum compromise
both for the picture reglons and for the text regions,
- 35 -
1 ~797~8
Devices ~hich are suitable for the realization of
the method of the present invention for o~taining a code
statement and a ~ack-up accuracy statement are well known in
the art. For example, for this purpose a programmed process
computer is suitable which.at N inputs, the N anal~sis values
are input in analog or digital form and which makes available
at an output the code statement and the accuracy statement
associated with the analysis result in the form of a digital
signal. Programma~le process computers are obtainable on the
market on a great nuM~er of different embodiments.
FIG. 13 illustrates a circuit arrangement for
executing a portion of the method of the present invention
whereby a scanning value coder 1~ is Provided with a si~nal
input E for the inputting of scanning pulses generated by a
scanning element, with a signal output iw for the out~utting
of output signals representing recognized scanning values and
a reset ouput CL for outputting reset signals, In addition,
two interval decoders IWl and I~J2 are provided whid~are
connected in cascade, em~odied in each case as threshold value
circuits, and which are equipped in each case with a first
decision output.N and a second decision output I and, in each
case, a decision input EE. The decision input E~ of the first
interval decoder IWl of the cascade is connected with the
signal output iw, its first decision output N is connected with
the decision input EE of the second interval decoder IW2 of
the cascade, the first decision output N of the second interval
decoder IW2 is connected with the signal input of an interval
counter Z3 and in each case, the second decision output I of
the first or, respectively, second interval decoder IWl or,
respectively, IW2 is connected with the signal input of an
- 36 -
I 17977~
interval counter Zl or, respectively~ Z2' The counting outputs
of the interval counters Zl ? Z2 and Z3 are connect:ed with
corresponding data inpùts of the calculating register R for
the determination of the characteristic number C, One output
of the calculating register R is connected for the transmission
of the characteristic number C which has been determined to a
data input,of a decider E~ Its signal output is connected to
the control input of a code transfer switch U,
The calculating register R has a further output
Si which emits an accuracy signal, For resetting of the
interval counters Zl~ Z2 and Z3, the reset output ZL of the
scanning value decoder WD is connected with reset inputs of
the counters Zl' Z2 and Z3.
Although I have described my invention by reference
to particular illustrative embodiments thereof, many changes
and modifications of the invention may become apParent to those
skilled in the art without departing from the spirit and scope
of the invention. I therefore intend to include within the
patent warranted hereon all such changes and modification~ as
may reasonably and properly be included within the scope of my
contribution to the art,
