Tech-invite3GPPspaceIETFspace
959493929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 0809

UCL facsimile system

Pages: 99
Unclassified
Part 1 of 3 – Pages 1 to 29
None   None   Next

ToP   noToC   RFC0809 - Page 1
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.
ToP   noToC   RFC0809 - Page 2
                            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
ToP   noToC   RFC0809 - Page 3
     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
ToP   noToC   RFC0809 - Page 4
          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.
ToP   noToC   RFC0809 - Page 5
              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
ToP   noToC   RFC0809 - Page 6
     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
ToP   noToC   RFC0809 - Page 7
     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
ToP   noToC   RFC0809 - Page 8
                      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
ToP   noToC   RFC0809 - Page 9
     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.
ToP   noToC   RFC0809 - Page 10
     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.
ToP   noToC   RFC0809 - Page 11
       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.
ToP   noToC   RFC0809 - Page 12
       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.
ToP   noToC   RFC0809 - Page 13
       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.
ToP   noToC   RFC0809 - Page 14
             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
ToP   noToC   RFC0809 - Page 15
     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.
ToP   noToC   RFC0809 - Page 16
                     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
ToP   noToC   RFC0809 - Page 17
     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
ToP   noToC   RFC0809 - Page 18
     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.
ToP   noToC   RFC0809 - Page 19
       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
ToP   noToC   RFC0809 - Page 20
     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.
ToP   noToC   RFC0809 - Page 21
       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
ToP   noToC   RFC0809 - Page 22
          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
ToP   noToC   RFC0809 - Page 23
     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].
ToP   noToC   RFC0809 - Page 24
     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.
ToP   noToC   RFC0809 - Page 25
     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
ToP   noToC   RFC0809 - Page 26
     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.
ToP   noToC   RFC0809 - Page 27
       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.
ToP   noToC   RFC0809 - Page 28
       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
ToP   noToC   RFC0809 - Page 29
     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)

Next Section