RFC 0809
UCL facsimile system
Pages: 99
Unclassified
Unclassified
Part 1 of 3 – Pages 1 to 29
INDRA Note 1185 INDRA Feb. 1982 Working RFC 809 UCL FACSIMILE SYSTEM Tawei Chang ABSTRACT: This note describes the features of the computerised facsimile system developed in the Department of Computer Science at UCL. First its functions are considered and the related experimental work are reported. Then the disciplines for system design are discussed. Finally, the implementation of the system are described, while detailed description are given as appendices. Department of Computer Science University College, London NOTE: Figures 5 and 6 may be obtained by sending a request to Ann Westine at USC-Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, California, 90291 (or WESTINE@ISIF) including your name and postal mailing address. Please mention that you are requesting figures 5 and 6 from RFC 809. OR: You can obtain these two figures online from the files <NETINFO>RFC809a.FAX and <NETINFO>RFC809b.FAX from the SRI-NIC online library. These files are in the format described in RFC 769.
Contents
1. INTRODUCTION...........................................1
2. SYSTEM FUNCTIONS.......................................2
2.1 Communication......................................4
2.2 Interworking with Other Equipment..................8
2.2.1 Facsimile machines............................8
2.2.2 Output Devices................................9
2.3 Image Enhancement..................................11
2.4 Image Editing......................................15
2.5 Integration with Other Data Types..................16
3. SYSTEM ARCHITECTURE....................................17
3.1 System Requirements................................17
3.2 Hierarchical Model.................................19
3.3 Clean and Simple Interface.........................20
3.3.1 Principles....................................21
3.3.2 Synchronisation and Desynchronisation.........21
3.3.3 Data Transfer.................................22
3.4 Control and Organisation of the Tasks..............22
3.4.1 Command Language..............................23
3.4.2 Task Controller...............................23
3.5 Interface Routines.................................26
3.5.1 Sharable Control Structure....................26
3.5.2 Buffer Management.............................27
4. UCL FACSIMILE SYSTEM...................................28
4.1 Multi-Task Structure...............................29
4.2 The Devices........................................29
4.3 The Networks.......................................30
4.4 File System........................................31
4.5 Data Structure.....................................32
4.6 Data Conversion....................................34
4.7 Image Manipulation.................................35
4.8 Data Transmission..................................39
5. CONCLUSION.............................................41
5.1 Summary............................................41
5.2 Problems...........................................42
5.3 Future Study.......................................46
Appendix I: Devices
Appendix II: Task Controller and Task Processes
Appendix III: Utility and Data Formats
Reference
1. INTRODUCTION
The object of a facsimile system is to reproduce
faithfully a document or image from one piece of paper
onto another piece of paper sited remotely from the
first one. Up to now, the main method of facsimile
communication has been via the telephone network. Most
facsimile machines permit neither the storage of image
page nor their modification before transmission. With
such machines, it is almost impossible to communicate
between different makes of facsimile machines. In this
respect, facsimile machines fall behind other
electronic communication services.
Integration of a facsimile service with computer
communication techniques can bring great improvements
in service. Not only is the reliability and efficiency
improved but, more important, the system can be
integrated with other forms of data communication.
Moreover, the computer enables the facsimile machine to
fit into a complete message and information processing
environment. The storage facilities provided by the
computer system make it possible to store large amounts
of facsimile data and retrieve them rapidly. Data
conversion allows facsimile machines of different types
to communicate with each other. Furthermore, the
facsimile image is edited and/or combined with other
forms of data, such as text, voice and graphics, to
construct a multi-media message, which can be widely
distributed over computer networks.
In the Department of Computer Science at UCL, a
computerised facsimile system has been developed in
order to fully apply computer technology, especially
communication, to the facsimile field. Some work has
been done to improve the facsimile service in several
areas.
(1) Adaptation of the facsimile machine for use with
computer networks. This permits more reliable and
accurate document transmission, as well as
improving the normal point-to-point transfers.
(2) Storage of facsimile pages. This permits the
queueing of pages, so saving operator time. Also,
standard documents can be kept permanently and
transmitted at any time.
(3) Interworking with other facsimile machines. This
permits different makes of facsimile machines to
exchange images.
(4) Compression of the facsimile images. This allows
more efficient transmission to be achieved.
Different compression schemes are investigated.
(5) Display of images on other devices. A colour
display is used so that the result of image
processing can be shown very vividly.
(6) Improvement of the images. The ability to 'clean'
the facsimile images not only allows for even
higher compression ratio, but also provide a
better result at the destination.
(7) Editing of facsimile pages. This includes the
ability to change pictures, alter the size of
images and merge two or more images, all
electronically.
(8) Integration of the facsimile service with other
data types. For the time being, coded character
text can be converted into facsimile format and
mixed pages containing pictures and text can be
manipulated.
This note first considers the functions of the
facsimile system, the related experimental work being
reported. Then the discipline for the system design is
discussed. Finally, the implementation of the UCL
facsimile system is described. As appendices, detailed
description of the system are given, namely
I. Devices
II. Task controller and task processes
III. Utility routines and Data format
2. SYSTEM FUNCTIONS
The computerised facsimile system we have developed
is composed of an LSI-11 micro-computer running the MOS
operating system [14] with two AED62 floppy disk drives
[17], a Grinnell colour display [18], a DACOM facsimile
machine [16], and a VDU as the system console. This
LSI-11 is also attached to several networks, including
the ARPANET/SATNET [21], [22] and the UCL Cambridge
Ring. A schematic of the system is shown in Fig. 1.
facsimile machine bit-map display
+------+ +------+
! ! ! !
+------+ +------+
+------+ \ / VDU
! disk ! +----------+ +-----+
+------+ ---- ! LSI-11 ! -- ! !
! disk ! +----------+ +-----+
+------+ |
+------+
! NI !
+------+
Network Interface
Fig. 1 Schematic of UCL facsimile system
In this system, a page is read on the facsimile
machine and the image data produced is stored on the
floppy disk. This data can be processed locally in the
micro-computer and then sent to a file store of a
remote computer across the computer network. At the
remote site, the image data may be processed and
printed on a facsimile machine.
On the other hand, we can receive image data which is
sent by a remote host on the network. This data can be
manipulated in the same way, including being printed on
the local machine.
Section 2.1 dicusses the problems concerned with
transmission of facsimile image data over a network,
while the following sections deal with those of local
manipulation of image data.
In order to interwork with other facsimile machine,
we have to convert the image data from one
representation format to another. Interworking with
other output devices requires that the image be scaled
to fit the dimension of the destination device. These
are described in section 2.2.
Being able to process the image by computer opens the
door to many possibilities. First, as considered in
section 2.3, an image can be enhanced, so that the
quality of the image may be improved and more efficient
storage and transmission can be achieved. Secondly, a
facsimile editing system can be supported whereby a
picture can be changed and/or combined with other
pictures. This is described in section 2.4.
In our system, coded character text can be converted
into its bit-map representation format so that it can
be handled as a facsimile image and merged with
pictures. This provides an environment where multi-type
information can be dealt with. This is discussed in
section 2.5.
2.1 Communication
The first goal of our computerised facsimile system
is to use a computer network to transmit data between
facsimile machines which are geographically separated.
Normally, facsimile machines are used in association
with telephone equipment, the data being sent along
telephone lines. Placing the facsimile machines on a
computer network presents a problem as the facsimile
machine does not have the ability to use a computer
network directly. To perform the network tasks a
computer is required, and so the first phase was to
attach the facsimile machine to a computer.
The facsimile machine is not like a standard piece of
computer equipment. We required a special hardware
interface to enable communication between the facsimile
machine and a small computer. This interface was made
to appear exactly like the telephone system to the
facsimile machine. Furthermore, the computer was
programmed to act exactly as if it were another
facsimile machine on the end of a telephone line. Thus
the local facsimile machine could transmit data to the
computer quite happily, believing that it was actually
talking to a remote facsimile machine on the other end
of a telephone wire. Because of the property of the
DACOM 6450 used in the experiment [16], the interface
could be identical to one developed for connecting to
an X25 network. The binary synchronous mode of the chip
used (SMC COM5025) was appropriate to drive the DACOM
machine.
At the other side of the computer network there was a
similar computer with an identical facsimile machine.
The problem of transmitting a facsimile picture now
appeared simple: data was taken from the facsimile
machine into the computer, transmitted over the network
as if it was normal computer data, and then sent from
the computer to the facsimile machine at the remote
end. The data being sent over the network appears
exactly as any other computer data; there is nothing
special about it to signify that it came from a
facsimile machine. The schematic of such facsimile
transfer system is shown in Fig. 2.
facsimile
machine
+---+ interface
! ! +--+ +-----+
! ! == ! ! == ! ! computer
+---+ +--+ +-----+
|
- - - - - - computer
/ \ network
\ / facsimile
- - - - - - machine
| interface +---+
+-----+ +--+ ! !
computer ! ! == ! ! == ! !
+-----+ +--+ +---+
Fig. 2 Facsimile transfer system
The experimental system was used to perform a joint
experiment between UCL and two groups in the United
States. Pictures were exchanged via the ARPANET/SATNET
[21], [22] between UCL in London, ISI in Los Angeles,
and COMSAT in Washington D.C. (Fig. 3). This
environment was chosen because no equivalent group was
available in the UK.
One problem concerned with such image data
transmission is the quantity of data. Even with data
compression, a single page of facsimile data can
produce as much computer data as would normally be
sufficient for sending over 20,000 alphabetic
characters - or over a dozen typed pages. Thus for a
given number of pages put into the system, an immense
amount of computer data is produced. This means that
the transmission will be slower than for sending text,
and that far more storage will be required to hold the
data.
Another problem was encountered which became only too
apparent when we implemented this system. The network
we were using was often unable to keep up with the
speed of the facsimile machine. When this happened the
US UK
satellite
COMSAT __
+---+ +--+ / \
! ! -- ! ! / \
+---+ +--+ / \
| \ / \
+---+ \ / \ UCL
!fax! \+--+/ \+--+ +---+
+---+ ARPANET ! ! SATNET ! ! -- ! !
/+--+ +--+ +---+
/ |
ISI / +---+
+---+ +--+ !fax!
! ! -- ! ! +---+
+---+ +--+
|
+---+
!fax!
+---+
Fig. 3. The three participants of the facsimile experiments
computer tried to slow down the facsimile machine. The
facsimile machine would detect this 'slowness' as a
communication problem (as a telephone line would never
act in this manner), and would abandon the transfer
mid-way through the page.
This is because the the facsimile machine we were
using was never intended for use on a computer; it was
designed and built for use on telephone lines. Indeed,
being unaware that it was connected to a computer, the
facsimile machine transmitted data at a constant rate,
which exceeded the limit that the network could accept.
In other words, the computer network we were using was
not designed for the transfer rate that we were trying
to use over it.
Both these problems are surmountable. Facsimile
machines are coming on the market that are designed for
direct communication with a computer. These machines do
not mind the delays on the computer interface and are
tolerant of the stops and re-starts. On the other hand,
if there were a serious use of facsimile machines on a
computer network, the network could be designed for the
high data rate required. Our problem was aggravated by
using a network that was never designed for the data
rates required in our mode of usage.
Despite the problems we encountered being a result of
the experimental equipment we were working with, we
still had to improve the situation to permit more
extensive communications to take place. The easiest way
to do this was to introduce a local storage area in our
computer where the data could be held prior to
transmission. The transfer of a page is now done in
three stages. First, the facsimile data is read from
the facsimile machine and stored on a local disk. This
takes place at high speed as this is just a local
operation. When this is complete, the data is sent
over the network to a disk on the remote computer.
Finally, the data from that disk is output to the
remote facsimile machine. This improved system is
shown in Fig. 4.
computer network
fax computer - - - - computer fax
+---+ +-----+ / \ +-----+ +---+
! ! = ! ! = ==> = ! ! = ! !
+---+ +-----+ \ / +-----+ +---+
- - - + | - - - - | + - - >
| | + - - - - - - - - - + | |
| | | | | |
V | | V | |
+---+ +---+
! ! ! !
! ! ! !
+---+ +---+
disk disk
Fig. 4. The improved facsimile transfer system
The idea behind this method is to decouple the
facsimile machine from the network communications. The
data is read from the facsimile machine at full speed,
without the delays caused by the computer network.
This also has the effect of being more acceptable to
the human operators: each page is now read in less than
a minute. The transmission over the network then takes
place at whatever speed the network can sustain. This
does not affect the facsimile machines at all; they are
not involved in the sending or receiving. Only when all
the data has been received at the remote disk is the
remote facsimile machine told that the data is ready.
The facsimile machine is then given the data as fast as
it will accept it.
The disadvantage of such a system is that the person
sending the pages does not know how long it will be
before they are actually printed at the other side. If
several pages are input in quick succession by the
operator, they will be stored on disk; it may then be
some time before the last page is actually delivered to
the destination. This is not always a disadvantage;
where many operators are sending data to the same
destination, it is a definite advantage to be able to
input the pages and have the system deliver them when
the destination becomes free. Such a system is
preferable to use of the current telephone system where
the operator has to keep re-dialing the remote
facsimile machine until the call is answered.
2.2 Interworking with Other Equipment
2.2.1 Facsimile machines
As was mentioned earlier, facsimile machines produce
a large amount of data per page due to the way in which
the pages are encoded. To reduce the data that has to
be transmitted, various compression techniques are
employed. The manufacturers of facsimile machines have
developed proprietary ways in which the data is
compressed and encoded. Unfortunately this has meant
that interworking of different facsimile machines has
been impossible. In the system described in the last
section, exchange of pictures was only possible between
sites that had identical facsimile machines. The new
set of CCITT recommendations will reduce the extent to
which differences in equipment persist.
Having the data on a computer gives us the
opportunity to manipulate data in any way we wish. In
particular we could convert the data from the form used
in one facsimile machine to that required by another.
This means that interworking between different types of
facsimile machines can be achieved.
The development of this system took place in two
stages: the decompression of the facsimile data from
the coded form used in our machine into an internal
data form and the recompression of the data in the
internal form into the encoded form required for the
destination machine. Two programs were developed to
perform these two operations.
At the same time we were developing compression and
decompression programs for machines that use other
techniques. In particular, we developed programs to
handle the recently approved CCITT recommendation for
facsimile compression [15]. The CCITT came up with two
varieties of compression, depending upon the resolution
being used.
Unfortunately there were no facsimile machines on the
network that use the CCITT compression technique.
However, the programming of the new methods achieved
two goals: it proved that the data could be converted
inside a small computer, so that machines of different
types could be supported on the network, and it enabled
us to compare the compression results. These are
described in more detail in [13]. Essentially, these
show that the DACOM technique used by our facsimile
machine is comparatively poor, and that considerably
less data need be transmitted if some other method is
used. This brings up another possibility: we could
change the compression of the data to reduce the volume
for transmission and then change the data back again at
the destination. This may save considerable
transmission time, especially if fast computers or
special hardware was easily available. This has not
been tried yet in our system, as none of the other
users on the network have the capability of changing
the data format back into that required by their
machines.
There are many other more efficient compression
schemes, e.g. block compression [7] and predictive
compression [8], but we have not yet incorporated them
into our system.
2.2.2 Output Devices
One area that we have explored is the use of devices
other than facsimile machines for outputting the data.
Facsimile machines are both expensive to buy and
relatively slow to operate. We have investigated the
use of a TV-like screen to display the data, just as
character VDUs are commonly used to display text. This
activity requires bit-map displays, with an address in
memory for each postion on the screen. Full colour and
multiple shades can be used with appropriately large
bit-map storage. Although simple in principle, the
implementation of the relevant techniques took
considerable effort.
The problems arise in the way that the facsimile
image is encoded. Raw facsimile images consist of rows
of small dots, each dot recorded as a black or white
space. When these dots are arranged together they build
up a picture in a similar manner to the way in which a
newspaper picture is made up. Unfortunately the number
of dots used in a facsimile page is not the same as the
number used on most screens. For instance, the DACOM
facsimile machine uses 1726 dots across each page, but
across a screen there are usually just 512 dots. Thus
to show the picture on the screen the 1726 dots must be
'squeezed' into just 512 dots; stated another way, 1214
dots must be thrown away without losing the picture!
It is in reducing the number of picture elements that
the problem arises. We could just every third dot or
so from the facsimile page and just display those.
Alternatively, we could take three or more at a time
and try to convert the group of them into a single
black or white dot. Unfortunately, in both these
cases, data can get lost that is necessary to the
picture. For instance, a facsimile encoding of an
architect drawing could easily end up with a complete
line removed, radically changing the presentation of
the image.
After much experimentation, we developed a method of
reducing the number of dots without destroying the
picture. This is a thinning technique, whereby key
elements of the picture are thinned, but not removed.
Occasionally, when the detail gets too fine, some
elements are merged, but under these circumstances the
eye would not have been able to see the detail anyway.
The details of this technique are described in [3] and
[4].
It may also be required that a picture be enlarged.
This enlargement can be done by simply duplicating each
pixel in the picture. For a non-integral ratio, the
picture can be expanded up to the nearest integer and
then shrunk to the correct size. However, this method
may degrade the image quality, e.g. the oblique contour
may become stepped, especially when the picture is
enlarged too much. This problem can be solved by using
an iterative enlargement algorithm. Each time a pixel
is replaced with a 2x2 array of pixels, whose pattern
depends on the original pixel and the pixels
surrounding it. This procedure is repeated until the
requested ratio is reached. If the ration is not a
power of 2's, the same method as that for non-integral
ratios is used.
As a side effect of developing this technique, we
could freely change the size and shape of an image.
The picture can be expanded or shrunk, or it can be
distorted. Distortion, whereby the horizontal and
vertical dimensions of the image may be changed by
different amounts, is often useful in image editing.
The immediate consequence of this ability to change
the image size meant that we could display the image on
a screen as well as output the image on a facsimile
machine. To a user of a computerised facsimile system
this could be a very useful feature: images can be
displayed on screen much faster than on a facsimile
machine, and displays are significantly cheaper than
the facsimile machines as well. It is possible that an
installation could have many screen displays where the
image could be viewed, but perhaps only one facsimile
machine would be available for hard copy. This would be
similar to many computer configurations today where the
number of printers is limited due to their cost, and
display screens are far more numerous.
2.3 Image Enhancement
One aspect of computer processing that we wanted to
investigate was that of image enhancement. Enhancing
the image is a very tricky operation; as the name
implies it means that the image is improved in some
sense. Under program control this is difficult to
achieve: what the program thinks is an improvement, the
human might judge to be distinctly worse.
Our enhancement attempts were aimed particularly at
printed documents and other forms of typed text. The
experiment was double pronged: we hoped to make the
image easier to read by humans while also making the
image easier for the computer to handle.
In our earlier experiments we had noticed that the
encoding of printed matter was often very poor. This
was especially noticeable when we enlarged an image.
Rather than each character having smooth edges as on
the original document, the edges were very rough,
unexpected notches and excrescences being caused by the
facsimile scanner. They not only degrade the image
quality but also decrease the compression efficiency. A
typical enlargement of several characters is shown in
Fig. 5.
Fig 5. An enlargement of an typed text
The enhancement method we adopted was first employed
at Loughborough University [5]. This method has the
effect of smoothing the edges of the dark areas on the
image. The technique consists of considering each dot
in the image in turn. The dot is either left as it is
or changed to the opposite colour (white to black or
black to white) depending upon the eight dots that
surround it. The particular pattern of surrounding dots
that are required to change the inner dot's colour is
used to control the harshness of the algorithm [6],
[8].
In our first set of experiments the result was
definitely worse than the original. Although square-
like characters such as H, L, and T came out very well,
anything with slope (M, V, W, or S) became so bad that
the oblique contours were stepped. The method was
subsequently modified to produce a result that was far
more acceptable; the image looked a lot cleaner than
the original. Fig. 6 shows the same text as that in
Fig. 5, but after it has been cleaned.
Fig. 6 A cleaned text
The effect of these can be difficult to see clearly.
We have used the colour on our Grinnell display to show
the original picture and the outcome of various picture
processing operations superposed in different colours.
This brings out the effect of the operations very
vividly.
It was mentioned above that the enhancement was done
not only to improve the image for reading but also for
easier processing by the computer. As described
earlier, the image from the facsimile machine is
compressed in order to reduce the amount of data. The
cleaning allows a higher compression rate so that more
efficient transmission and/or storage can be achieved.
We learned some important lessons from the
enhancement exercise. Originally we thought that the
main attraction in enhancement would be to improve the
readability. In the end, we found that improving the
readability was very difficult, especially because the
facsimile image was so poor. Instead we found that the
effect of reducing the compressed output was more
important. By reducing the data to be transmitted by a
quarter, significant savings could be made. But before
such a technique could be used in a live system, the
time it takes to produce the enhancement must be
weighed against the time that would be saved in
transmission.
2.4 Image Editing
By editing we mean that the facsimile picture can be
changed, or combined with other pictures, while it is
stored inside the computer. In previous sections it
was mentioned that we could change the size and shape
of a facsimile image. This technique was later combined
with an overlaying method that enabled one picture to
be combined with another [12].
In order to perform any editing it is necessary to
have the picture displayed for the user to see. In our
case we displayed the picture on the bit-map screen.
The image took up the left-hand side of the screen, the
right side being reserved for the picture that was
being built. The user could select an area of the
left-hand screen and move it to a position on the
right-hand screen. Several images could be displayed
in succession on the left, and areas selected and moved
to the right. Finally, the right-hand screen could be
printed on the facsimile machine.
The selection of an area of the picture was done by
the use of a coloured rectangular subsection,
controlled by a program in the computer, that could be
moved around on the screen. The rectangular subsection
was moved with instructions typed in by the operator;
it could be moved up or down, and increased or
decreased in size. When the appropriate area of the
screen had been selected, the program remembered the
coordinates and moved the coloured rectangular
subsection to the right-hand side of the screen. The
user then selected an area again, in a similar manner.
When the user finished the editing, the program removed
the part of the picture selected from the left-hand
screen and converted it to fit the shape of the
rectangular subsection on the right-hand screen. The
result was then displayed for the user to see.
When an image was being edited, the editor had to
keep another scaled copy for display. This is due to
the fact that the screen had a different dimension to
that of the facsimile machine. The editing operations,
e.g. chopping and merging, were performed on the
original image data files with the full resolution
available on the facsimile machine.
2.5 Integration with Other Data Types
The facsimile machine can be viewed in a wider
context than merely a facsimile input/output device. It
can work as a printer for other data representation
types, such as coded character text and geometric
graphics. At present, text can be converted into
facsimile format and printed on the facsimile machine.
Moreover, mixed pages containing pictures and text can
be manipulated by our system. The integration of
facsimile images with geometric graphics is a topic of
future research.
In order to convert a character string into its
facsimile format, the system maintains a translation
table whereby the patterns of the characters available
in the system can be retrieved. The input character
string is translated into a set of scan lines, each of
which is created by concatenating the corresponding
patterns of the characters in the string.
The translation table is in fact a software font,
which can be edited and modified. Even though only one
font is available in our system for the time being, it
is quite easy to introduce other character fonts.
Furthermore, it is also possible for a font to be
remotely loaded from a database via the communication
network.
This allows for more interesting applications of the
facsimile machine. For example, it could serve as a
Teletex printer, provided that the Teletex character
font is included in our system. In this case, the text
images may be distorted to fit the presentation format
requested by the Teletex service. Similarly, Prestel
viewdata pages could be displayed on the Grinnell
screen.
Moreover, pictures can be mixed with text by
combining this text conversion with the editing
described in the previous section. This should be
regarded as a notable step towards multi-type
processing.
Not only does this support a local multi-type
environment but multi-type information can be
transmitted over a network. So far as this facsimile
system is concerned, a mixed page containing text and
pictures can be sent only when it has been represented
in a bit-map format. However, much more efficient
transmission would be achieved if one could transmit
the text and pictures separately and reproduce the page
at the destination site. This requires that a multi-
type data structure be designed which is understood by
the two communication sites.
3. SYSTEM ARCHITECTURE
Now let us discuss the general disciplines for design
and implementation of a computerised facsimile system
which carries out the functions described in the
previous sections. Having discussed the requirements
of the system, a hierarchical model is introduced in
which the modules of different layers are implemented
as separate processes. The Clean and Simple interface,
which is adopted for inter-process communication, is
then described. The task controller, which is
responsible for organising the tasks involved in a
requested job, is discussed in detail. Some efforts
have been made in our experimental work to provide a
more convenient user programming environment and a more
efficient data transfer method. This is finally
described.
3.1 System Requirements
In a computerised facsimile system, the images are
represented in a digital form. To carry out this
conversion, a page is scanned by the optical scanner of
the facsimile machine, a digital number being produced
to represent the darkness of each pixel. As high
resolution has to be adopted to keep the detail of the
image, the facsimile data files are usually rather
large. In order to achieve efficient storage and
transmission, the facsimile data must be compressed as
much as possible.
Currently, the facsimile machines made by different
manufacturers h different properties, such as
different compression methods and different resolution.
There are also some international standards for
facsimile data compression, which are employed for the
facsimile data to be transferred over the public data
network. These require that the facsimile data be
converted from one representation form to another, so
that users who are separated geographically and use
different machines can communicate with each other.
More sophisticated applications, e.g. image editing,
request processing facilities of the system as well.
When being processed, the facsimile image should be
represented in a common format or internal data
structure, which is used to pass the information
between different processing routines. For the sake of
convenience and efficiency, the internal data structure
should be fairly well compressed and its format should
be easy for the computer to manipulate. In our
experimental work, the line vector is chosen as a
standard unit, a simple run-length compression being
employed [3]. Some processing routines may use other
data formats, e.g. bit-map, but it is the
responsibility of such routines to perform the
conversion between those formats and the standard one.
The system should contain several processing
routines, each of which performs one primitive task,
such as chopping, merging, and scale-changing. An
immense variety of processing operations can be carried
out as long as those task modules can be organised
flexibly. The capability for flexible task organisation
should be thought of as one of the most important
requirements of the system.
One possibility is for the processing routines
involved to be executed separately, temporary files
being used as communication media. Though very simple,
this method is far too inefficient.
As described above, the information unit for the
communication between the processing routines is the
line vector, so that the routines can be organised as
embedded loops, where a processing routine takes the
input line from its source routine located in the inner
loop, and passes the output line to the destination
routine located in the outer loop [3]. Obviously this
method is quite efficient. But it is not realistic for
our system, because it is very difficult to build up
different processing loops at run-time and flexible
task organisation is impossible.
In a real-time operating system environment, the
primitive tasks can be implemented as separate
processes. This method, which is discussed in detail in
the following sections, provides the required
flexibility.
3.2 Hierarchical Model
As shown in Fig. 7, the modules in a single computer
fall into three layers.
+---------+
! ! task controller
+---------+
tasks
+---+ +---+ +---+ +---+ +---+
! ! ! ! ! ! ! ! !
+---+ +---+ +---+ +---+ +---+
| | |
+---+ +---+ +---+
! ! ! ! device drivers ! !
+---+ +---+ +---+
- - - | - - | - - - - - - - - - | - - - -
+---+ +---+ +---+
! ! ! ! physical | !
! ! ! ! devices ! !
+---+ +---+ +---+
Fig. 7 The hierarchical model
These are:
(1) Device Drivers, which constitute the lowest layer
in the model. The modules in this layer deal with
I/O activities of the physical devices, such as
facsimile machine, display and floppy disk. This
layer frees the task modules of upper layer from
the burden of I/O programming.
(2) Tasks, which perform all processing primitives and
handle different data structures. Above the driver
of each physical device, there are one or more
such device-independent modules, which work as
information source or sink in the task chain (see
below). A file system module allows other modules
to store and retrieve information on the secondary
storage device such as floppy disk. Decompression
and recompression routines convert data structures
of facsimile image information so that the
facsimile machines can communicate with the rest
of the system. Processing primitives, e.g.
chopping, merging, scaling, are implemented as
task modules in this layer. They are designed such
that they can be concatenated to carry out more
complex jobs. So far as the system is concerned,
the protocols for data transmission over computer
networks are also regarded as task modules in this
layer.
(3) Task Controller, which organises the task
processes to perform the specified job. It
provides the users of the application layer with a
procedure-oriented language whereby the requested
job can be defined as a chain of task modules.
Literally, the chain is represented by a character
string:
<source_task>|{<processing_task>|}<sink_task>
According to such a command, the task controller
selects the relevant task modules and concatenates
them in proper order by means of logical links.
Then the tasks on the chain are executed under its
control, so that the data taken from the source
are processed and the result is put into the sink.
3.3 Clean and Simple Interface
It is important, in this application, to develop the
software in a modular way. It is desirable to put
together a set of modules to carry out the different
image processing tasks. Another set of transport
modules must be developed for shipping data over the
different networks to which the UCL system is attached.
In our computerised facsimile system, these task
modules are implemented as separate processes. The
operation of the system relies on the communication
between these processes. The interface which is used
for such communication has been designed to be
universal; it is independent of these modules, and has
been termed the Clean and Simple interface [20]. This
interface is discussed in this section.
3.3.1 Principles
The Clean and Simple interface is concerned with the
synchronisation and transfer of full-duplex data
streams between two communicating processes. Thus the
interface has three major components: connection
synchronisation, data transfer and connection
desynchronisation. These components are discussed
below.
The connection between two processes is initiated by
one of them, which, generally speaking, belongs to a
higher layer. For example, the interface between
protocols of different layers is always initiated by
the higher layer, though, sometimes, the connection is
initiated passively by the primitive 'listen'. It will
be seen in the next section that task processes can
communicate with each other via the connections to the
higher layer (task controller) and this makes it
possible to achieve flexible task organisation.
The process initiating the connection is called the
'master' process, while the other is called the 'slave'
process. The 'master' process is also responsible for
resource allocation for the two communicating
processes. Here 'resource' refers mainly to the memory
areas for the message structure and data buffer. This
asymmetric definition of the interface eliminates any
possible confusion in resource allocation.
The interface is implemented by using the signal-wait
mechanism provided by the operating system. A data
structure called CSB (Clean and Simple Block), which
contains function, data buffer, and other information,
is sent as the event message, when one process signals
another [20].
3.3.2 Synchronisation and Desynchronisation
The procedure for connection synchronisation is
composed of two steps. First, the two processes
exchange their identifiers for the specific connection
by means of a getcid primitive. Usually, the pointer
to the task control structure of the process is used as
the connection identifier.
Then, the 'master' sends an open CSB with appropriate
parameter string passing the initialisation
information. This information, which can also be called
open parameter, is process dependent, or more
accurately, task dependent. For example, the parameters
for the file system should be the file name and the
access mode. Provided the 'slave' accepts the request,
the connection is established successfully and data can
be transferred via the interface.
In order to desynchronise the connection, the
'master' initiates a 'close' action. On the other hand,
an error state or EOF (end of file) state can be
reported by the 'slave' to request a connection
desynchronisation.
The listen primitive in our system is reserved for
the processes that receive a request from the remote
hosts on the networks.
3.3.3 Data Transfer
While the Clean and Simple interface is asymmetric in
relation to connection synchronisation, data transfer
is completely symmetric so long as the connection has
been established. Data flows in both directions are
permitted, though the operations are quite different.
The interface provides two primitives for data
transfer -- read and write. To transfer some data to
the 'slave', the 'master' signals it with a CSB
containing the write function and a buffer filled with
the data to be transferred. Having consumed the data,
the 'slave' returns the CSB to report the result status
of the transmission.
On the other hand, in order to receive some data from
the 'slave', the 'master' uses a read CSB with an empty
buffer. Having received the CSB, the 'slave' fills the
buffer with the data requested and, then, returns the
CSB.
3.4 Control and Organisation of the Tasks
Another important aspect of the multi-process
architecture of the UCL facsimile system, is the need
to systematise the control and organisation of the
tasks. This activity is the function of the task
controller, whose operations are discussed in this
section.
3.4.1 Command Language
As mentioned earlier, the task controller supports a
procedure-oriented language by means of which the user
or the routines of the upper layers can define the jobs
requested. A command should contain the following
information:
1. the names of the task processes which are involved
in the job.
2. the open parameters for these task processes.
3. the order in which the tasks are to be linked.
The last item is quite important, though, usually,
the same order as that given in the command is used.
A command in this language is presented as a zero-
ended character string. In the task name strings and
the attribute strings of the open parameters, '|', '"',
and ',' must be excluded as they will be treated as
separators. The definition is shown below, where '|',
which is the separator of the command strings in the
language, does not mean 'OR'.
<command_string> ::= <task_string>
<command_string> ::= <task_string>|<command_string>
<task_string> ::= <task_name>
<task_string> ::= <task_name>"<open_parameter>
<open_parameter> ::= <attribute>
<open_parameter> ::= <attribute>,<open_parameter>
3.4.2 Task Controller
In our experimental work, the task controller module
is called fitter. This name which is borrowed from
UNIX hints how the module works. According to the
command string, it links the specified tasks into a
chain, along which the data is processed to fulfil the
job requested (Fig. 8).
tasks
+-----+ +-----+ +-----+
! a ! -> ! b ! -> ! c !
+-----+ +-----+ +-----+
Fig. 8 The task chain
Since all modules, including fitter itself, are
implemented as processes, the connections between
modules should be via the Clean and Simple interfaces.
Upon receiving the command string, the fitter parses
the string to find each task process involved and opens
a connection to it. Formally, the task processes are
chained directly, but, logically, there is no direct
connection between them. All of them are connected to
the fitter (Fig. 9).
fitter
+-------------+
+-- ! ! --+
| +-------------+ |
| | |
V V V
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
Fig. 9 The connection initiated by the fitter
For each of the processes it connects, the fitter
keeps a table called pipe. When the command string is
parsed, the pipe tables are double-linked to represent
the specified order of data flow. So far as one process
is concerned, its pipe table contains two pointers: a
forward one pointing to its destination and a backward
one pointing to its sources. Besides the pointers, it
also maintains the information to identify the task
process and the corresponding connection.
Fig. 10 illustrates the chain of the pipe tables for
the job "a|b|c". Note that the forward (output) chain
ends at the sink, while the backward (input) chain ends
at the source. In this sense, the task processes are
chained in the specified order via the fitter (Fig.
11). The data transfer along the chain is initiated and
controlled by the fitter, each process getting the
input from its source and putting the output to its
destination.
+-----+ +-----+ +-----+
! * -+--> ! * -+--> ! 0 !
+-----+ +-----+ +-----+
! 0 ! <--+- * ! <--+- * !
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
! ! ! ! ! !
! ! ! ! ! !
+-----+ +-----+ +-----+
Fig. 10 The pipe chain
fitter
+-------------+
+-> ! * -> * -> * ! --+
| +-------------+ |
| | A |
| V | V
+-----+ +-----+ +-----+
! a ! ! b ! ! c !
+-----+ +-----+ +-----+
Fig. 11 The data flow
This strategy makes the task organisation so flexible
that only the links have to be changed when a new task
chain is to be built up. In such an environment, each
task process can be implemented independently, provided
the Clean and Simple interface is supported. This also
makes the system extension quite easy.
The fitter manipulates one job at a time. But it must
maintain a command queue to cope with the requests,
which come simultaneously from either the upper level
processes or other hosts on the network.
3.5 Interface Routines
In a modular, multi-process system such as the UCL
facsimile system, the structure of the interface
routines is very important. The CSI of section 3.3 is
fundamental to the modular interface; a common control
structure is also essential. This section gives some
details both about the sharable control structure and
the buffer management.
3.5.1 Sharable Control Structure
Though the CSI specification is straightforward, the
implementation of the inter-process communication
interface may be rather tedious, especially in our
system, where there are many task processes to be
written. Not only does each process have to implement
the same control structure for signal handling, but
also the buffer management routines must be included in
all the processes.
For the sake of simplicity and efficiency, a package
of standard interface routines is provided which are
shared by the task processes in the system. These
routines are re-entrant, so that they can be shared by
all processes.
The 'csinit' primitive is called for a task process
to check in. An information table is allocated and the
pointer to the table is returned to the caller as the
task identifier, which is to be used for each call of
these interface routines.
Then, each task process waits by invoking the
'csopen' primitive which does not return until the
calling process is scheduled. When the connection
between the process and the fitter is established, the
call returns the pointer to the open parameter string
of the task, the corresponding task being started. A
typical structure of the task process (written in c) is
shown below. After the task program is executed, the
process calls the 'csopen' and waits again. It can be
seen that the portability of the task routines is
improved to a great extent. Only the interface routines
should be changed if the system were to run in a
different operating environment.
static int mytid; /* task identifier */
task()
{
char *op; /* open parameter */
mytid = csinit();
for(;;) {
op = csopen(mytid);
... /* the body of the task */
}
}
3.5.2 Buffer Management
The package of the interface routines also provides a
universal buffer management, so that the task processes
are freed from this burden. The allocation of the data
buffers is the responsibility of the higher level
process, the fitter. If the task processes allocated
their own buffers, some redundant copying would have to
be done. Thus, the primitives for data transfer,
'csread' and 'cswrite', are designed as:
char *csread(tid, need);
char *cswrite(tid, need);
where 'tid' is the identifier of the task and 'need' is
the number of data bytes to be transferred. The
primitives return the pointer to the area satisfying
the caller's requirement. The 'csread' returns an area
containing the data required by the caller. The
'cswrite' returns an area into which the caller can
copy the data to be transferred. The copied data will
be written to its destination at a proper time without
the caller's interference. Obviously the unnecessary
copy operations can be avoided. It is recommended that
the data buffer returned by the primitives be used
directly to attain higher performance.
(next page on part 2)