`Bradium Technologies LLC - patent owner
`Microsoft Corporation - petitioner
`IPR2016-01897
`1
`
`
`
`U.S. Patent Sep. 9, 1980
`
`Sheet 1 of 6
`A/G / .
`
`13
`
`
`
`4,222,076
`
`|4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`RANDOM.
`ACCESS
`
`MEMORY
`
`H.
`
`ºl
`
`-
`
`PROCESSOR
`
`TRANSMITTER
`
`TRANSMISSION LINE
`
`DISPLAY
`UNIT
`
`20
`
`A/G 2
`
`2
`
`
`
`U.S. Patent Sep. 9, 1980
`
`Sheet 2 of 6
`A/G 3
`
`4,222,076
`
`
`
`DIFFERENTIATOR
`
`-
`
`COMPOSITE WALUE
`
`3
`
`
`
`U.S. Patent
`US‘. Patent
`
`Sep. 9, 1980
`Sep. 9, 1980
`
`Sheet 3 of 6
`Sheet 3 of 6
`
`4,222,076
`4,222,076
`
`.51:H;s:§_§,_._<E-Sm§ma;:_<:_E§<_:§E_._
`
`
`
`
`
`
`
`__.
`
`E‘
`
`V..0\.K
`
`E
`
`.§:__<
`
`
`
`
`
`:..e___:.s:
`
`
`
`
`
`I.I_s:§_§._n_<E.Eat.iiiiiiiInnufl«III._,_§w:11!“EuuuuuuuuuanWE
`
`
`
`
`
`
`
`
`
`lllllllIIIII:EI\§_:=_§_&<§__TrI
`
`
`
`
`
`4
`
`
`
`U.S. Patent Sep. 9, 1980
`US, Patent
`Sep. 9, 1980
`
`Sheet 4 of 6
`Sheet4 of6
`
`4,222,076
`4,222,076
`
`
`
`5
`
`
`
`U.S. Patent Sep. 9, 1980
`US“ Patent
`Sep. 9, 1980
`
`Sheet 5 of 6
`Sheet 5 of6
`
`4,222,076
`4,222,076
`
`FIG; 6
`
`
`
`($5.4-v;=~:.'.I.~<I
`
`
`
`
`
`6
`
`
`
`U.S. Patent sep. 9, 1980
`CS
`US. Patent
`m919,
`
`0..
`
`Sheet 6 of 6
`6fO6a
`
`4,222,076
`4,222,076
`
`|
`.35_.2~m25$8.
`:
`;
`3.3as3583‘.mama$8
`
`
`
`
`
`
`
`
`
`m.sm9K
`
`
`
`:
`:
`
`3533.SE2...3.3832%38
`
`
`
`
`
`
`
`7
`
`
`
`
`
`
`1
`
`PROGRESSIVE IMAGE TRANSMISSION
`
`5
`
`10
`
`FIELD OF THE INVENTION
`This invention relates to the transmission of pictorial
`images over narrow-band transmission channels in gen
`eral and, in particular, to two-dimensional gray-scale
`encoding of picture elements to facilitate the transmis
`sion of progressively better approximations of ultimate
`image details.
`BACKGROUND OF THE INVENTION
`Two-dimensional picture images in black and white,
`or more precisely in various shades of gray, are conven
`tionally prepared for transmission over channels of
`15
`restricted bandwidth by means of raster scanning. In
`raster scanning a moving beam of electrons or spot of
`light travels over the image mounted on a drum or
`flat-bed scanner in a regular pattern of lines sweeping
`from the top of a frame to the bottom. Typically, for a
`20
`slow-scan analog facsimile system, such as is afforded
`by the use of the Western Electric Data Set Type 602A,
`a transmission time of about six minutes is required to
`send over the switched telephone network a sketch,
`order or message of an 8% by 11-inch letterhead size
`25
`with a definition of 96 lines per inch at a speed of 180
`lines per minute.
`A digital system providing the same resolution for the
`approximate 7% by 10-inch sight area with an aspect
`ratio of three-to-four contains about 720 picture ele
`30
`ments (pixels) per line and 960 lines per sheet for a total
`of 691,200 pixels. If there are sixteen possible gray levels
`assignable to each pixel, then four bits are required to
`transmit each pixel for a total of 2,764,800 bits. A West
`ern Electric Data Set Type 208B operating at 4800 bits
`35
`per second in the voice-frequency band of the switched
`telephone network thus requires 9.6 minutes to transmit
`an image which is the size of a business letterhead. What
`the digital system lacks in speed of transmission relative
`to an analog system is made up in reliability and adapt
`ability to processing.
`Analog facsimile scanning systems are well known in
`the art and may be found described in Chapter 2 starting
`at page 2–67 in Communication Systems Engineering
`Handbook edited by D. H. Hamsher (McGraw-Hill
`45
`Book Company, New York 1967). Digital systems are
`disclosed in Digital Picture Processing by A. Rosenfeld
`and A. C. Kak, published by Academic Press in 1976.
`It is straightforward to encode the gray-scale values
`of individual pixels as binary numbers to as many as 6, 8
`or 10 digits as desired. An eight-bit number encodes, for
`example, 256 gray-scale levels, i.e., the digit two raised
`to the eighth power. Conversion of gray-scale values to
`digital numbers facilitates transmission of picture infor
`mation over pulse-code modulation (PCM) channels.
`55
`In line-by-line transmission, whether transmission is
`by analog or digital means, stationary images are
`Scanned as a sequence of rows, top row first and bottom
`row last. In order to view the entire image one must
`wait for substantially complete transmission. However,
`60
`if the image information is reorganized at the transmit
`ter terminal by means of high-speed apparatus, the low
`speed transmission can furnish the gross structure of the
`entire image soon after the beginning of transmission
`and add increasingly detailed refinements as transmis
`sion proceeds.
`-
`In a paper entitled “A Hierarchical Data Structure
`for Picture Processing” published in Computer Graphics
`
`4,222,076
`2
`and Image Processing (Vol. 4, No. 2, pp. 104-119, June
`1975) S. Tanimoto and T. Pavlidis have proposed for
`pattern recognition and data compaction purposes to
`process the digital representations of the pixels of high
`est resolution into progressively coarser levels of spatial
`resolution. The lower-resolution levels are coded by
`fewer bits of data and hence can be transmitted much
`faster than the final image. Picture analysis is said to be
`made more efficient by this type of image processing,
`The authors base their hierarchical structure on four
`cell true averages.
`-
`Important applications of the hierarchical arrange
`ment for image-processing data includes rapid remote
`browsing through a sequence of images. The recipient is
`thereby permitted to abort transmission of unwanted
`images as soon as they are recognizable, far short of
`complete transmission. Another application is telecon
`ferencing by way of telephone lines where visual mate
`rial, such as sketches and graphs, can be sent over auxil
`iary facsimile apparatus by presenting rough representa
`tions first and detail later. Other potential applications
`include interactive computer graphics and the sending
`of a picture from a transmitter threatened with immi
`nent destruction, as in a fire or with seismographic
`alarm apparatus, where one hopes for the best possible
`picture in whatever time remains for transmission.
`SUMMARY OF THE INVENTION
`According to this invention, a pyramid of image sub
`divisions of successive sizes is constructed by assigning
`approximate average gray-scale values to all pairs of
`cells from the elemental pixels to one encompassing the
`entire image. The cells at pyramidal nodes are hierar
`chically arranged such that the primary value at the
`apex of the pyramid stands for the approximate average
`gray-scale value of the entire image and the cells at the
`base are the gray-scale values of the elemental pixels.
`The cells at intermediate levels of the pyramid are occu
`pied by the approximate average gray-scale values of
`successively smaller subareas of the image. Viewing the
`successive images yields a progressively more detailed
`representation of the complete image. In order to avoid
`generating longer and longer numbers as successive
`exact averages of paired gray-scale values are taken,
`and to avoid truncating such averages, a two coordinate
`coding is proposed which uses the same number of bits
`for each approximate average as there is in each value
`averaged. Under this proposal the entire image can be
`transmitted progressively in exactly the same number of
`bits as is required for line-by-line transmission.
`In order to construct the hierarchical arrangement,
`the entire image must first be raster scanned to obtain
`the gray-scale value of each elemental pixel. These
`values are then stored in a gray-scale random-access
`memory (RAM). Thereafter, the stored values are pro
`cessed to form a tree of hierarchical approximate repre
`sentations of successive pairs of gray-scale values.
`When low-speed transmission is desired over a narrow
`band channel, the processed values can be read out level
`by level until the displayed image is aborted or com
`pleted. Since the coordinates for each hierarchical node
`are of equal length, the incremental transmission time
`for each successive level is double that of its predeces
`sor. Thus, the sooner the received image is recognized
`as other than that being sought, the lesser is the trans
`mission time expended.
`
`50
`
`65
`
`8
`
`
`
`10
`
`15
`
`4,222,076
`4
`3
`At the receiver terminal the gray levels are repro
`where the channel available has only voiceband capa
`bilities, for example, image information can be transmit
`cessed in an inverse manner using a frame buffer to
`ted at very slow rates measured in only thousands of bits
`excite the proper cells in the display unit.
`per second rather than millions. Accordingly, the pro
`BRIEF DESCRIPTION OF THE DRAWINGS
`cessed data in RAM 11 is fitted to the transmission
`A better understanding of this invention may be
`characteristics of transmission line 15, whether by am
`plitude, frequency, phase or time modulation, in trans
`gained from a consideration of the following detailed
`description, presented by way of example, with refer
`mitter 14.
`ence to the accompanying drawings, in which
`At receiver 16 the modulated digits encoding the
`FIG. 1 is a block diagram of a representative graphics
`image information being transmitted are restored to
`baseband by appropriate conventional means. Processor
`display transmission system;
`-
`FIG. 2 is a diagram illustrating successive subdivision
`17 then operates on the restored bits to reconstruct a
`of an image to facilitate progressive transmission
`beam intensity pattern for display unit 20 through the
`thereof;
`medium of frame buffer 19. Effectively frame buffer 19,
`FIG. 3 is a diagram of a scheme for encoding picture
`to which interactive access to processor 17 is provided
`elements of an image to be transmitted into integer
`over lead 18, furnishes timing and deflection control to
`composite and difference coordinates;
`display unit 20 in a conventional manner. By working
`FIG. 4 is a binary tree representation of the hierarchi
`down from the top of the hierarchical array of compos
`cal structure of encoded gray-scale values;
`ite averages and differentiators, as defined hereinafter,
`FIG. 5 represents a simplified sequence of progres
`20
`transmitted from processor 13, the desired image is
`sive images indexed by processing order and useful in
`reconstructed in gross form first—an overall gray level
`explaining the concept of this invention;
`—and then successively in halves, quarters and smaller
`FIG. 6 represents a simplified sequence of progres
`subdivisions until each picture element is revealed in its
`sive images with arbitrary gray-scale values assigned to
`correct gray-scale value.
`the ultimate image;
`25
`The scheme proposed is much less complex than
`FIG. 7 shows six stages of the development of a com
`analyzing the image to be transmitted into its Fourier
`plete image by a conventional line-by-line raster scan
`transform coefficients for the purpose of achieving
`ning method; and
`gross image structure by transmitting first the coeffici
`FIG. 8 shows six stages of the development of the
`ents of the lowest-frequency components and following
`image of FIG. 6 by the progressive method according
`with higher and higher frequency coefficients. The
`to this invention.
`Fourier transform method is described in Chapter 2 of
`the aforementioned Digital Picture Processing book.
`DETAILED DESCRIPTION
`A hierarchical system for picture subdivision in bi
`FIG. 1 is a block diagram of an image scanning and
`nary fashion is proposed. Successive levels of subdivi
`transmission system according to this invention which
`35
`sion are achieved, as diagrammed in FIG. 2, by splitting
`comprises scanner 10, random-access memory (RAM)
`the overall picture first into top and bottom halves; and
`11, processor 13 for scanned information, a transmitter
`next, into left and right halves. Subsequently, left and
`14, transmission line 15, receiver 16, processor 17 for
`right halves are themselves further split into top and
`received picture information, frame buffer 19 and video
`bottom segments alternately with side-by-side seg
`display unit 20.
`ments, which are split into more, but smaller, top and
`Scanner 10 provides a scanning spot, by way of exam
`bottom segments. The numbers 1 through 8 on the
`ple, which moves line-by-line in a horizontal direction
`drawing indicate the splitting progression for a part of
`during a downward sweep. Element-by-element on
`the image. The splitting of the remainder of the image
`each horizontal line gray-scale values are stored digital
`proceeds simultaneously. This subdivision process is
`fashion in gray-scale random-access memory 11. Gray
`45
`continued down to pixel size.
`scale values can be stored either sequentially in memory
`The proposed binary splitting scheme can be con
`11 or in preprogrammed locations which facilitate pro
`trasted with the Tanimoto-Pavlidis four-way split in
`gressive image transmission.
`which the original image is first split into four parts of
`It is to be understood that in principle color informa
`equal size and subsequently each of the four parts is
`tion can be obtained in an analogous manner using three
`further split into four more smaller parts of equal size
`simultaneous beams with appropriate filters and three
`until the ultimate resolution is achieved. The propsed
`separate memories or with an expanded single memory.
`scheme has been found to require smaller tables to en
`Gray-scale values are stored as digital numbers such
`code the successive splittings and to yield successive
`that, for example, a four-bit number can represent 16
`approximations more frequently.
`discrete light intensities from all white to all black.
`55
`The scheme of FIG. 2 can be visualized as successive
`Processor 13 operates on the stored cell-by-cell gray
`approximations of the ultimate image consisting, for
`scale values to form a hierarchical array of “composite
`illustrative purposes of 256 lines with 128 cells for each
`average values” and “differentiators” according to the
`line quantized into sixteen discrete gray levels. The
`principle of this invention, as explained more fully here
`zero-th approximation is a single full-screen monotone
`inafter. The processed values are also stored in RAM
`60
`area. The first approximation comprises two rectangles,
`11, to which interactive access is provided with proces
`an upper and a lower. Subsequent approximations com
`sor 13 over lead 12. The events occurring in blocks 10
`prise successive doublings of rectangles, each approxi
`through 13 take place at normally rapid scanning and
`mation containing 2" rectangles, where n is the order of
`computing speeds.
`the approximation, until an upper limit, such as the
`If a wideband channel were available, as in television
`fifteenth power of two yieldings 32,768 pixels, is
`broadcasting, there would be no need for processing the
`reached. Where the overall image has a 4 to 3 height-to
`scanned information and such information could be
`width aspect ratio, successive approximations alternate
`transmitted as rapidly as it is generated. However,
`
`65
`
`30
`
`50
`
`9
`
`
`
`5
`
`15
`
`10
`
`4,222,076
`6
`5
`gular. The processing proceeds from the sequence of
`between aspect ratios of 2 to 3 and 4 to 3, as is apparent
`gray-scale values of the elementary pixels in the final
`in FIG. 2.
`-
`image as obtained by the scanning device. In the explan
`In order to form a code for progressive image trans
`atory example of FIG. 4 the 32-pixel final image is five
`mission it is necessary to work backwards from individ
`approximations from the initially transmitted monotone
`ual pixels in what is effectively the fifteenth detailed
`image.
`approximation to the zero-th monotone. Consider the
`A practical system capable of handling an image .
`gray levels of adjacent cells determined in the rapid
`containing 32,768 pixels, as previously suggested, re
`scanning process. These levels are represented by bi
`quires fifteen approximations for full image develop
`nary numbers. If a true average of numbers identifying
`adjacent gray values is taken, it is found that a larger
`ment.
`The fourth approximation is realized from the true
`number of bits is required than for each of the original
`image as follows: for each pair of pixels a composite
`numbers because fractions are generated. These extra
`value and its corresponding differentiator are selected
`digits represent overhead which causes progressive
`from the chart of FIG. 3 or by lock-up in its equivalent
`transmission time to exceed unprocessed transmission
`RAM to complete a node. If the final image is defined
`time. To avoid this overhead a composite value Vc near
`by the gray-scale values of 25 pixels, there are 24, i.e.,
`the average of two adjacent values, but nevertheless an
`2*! nodes in the (n-1)th approximation. The next
`integer, is chosen followed by a differentiator d, which
`coarser or third approximation is in turn generated by
`indicates effectively how the available light is distrib
`forming new nodes between pairs of adjacent composite
`uted between the two pixels being averaged.
`-
`values of the previous fourth approximation and further
`FIG. 3 diagrams a composite averaging scheme
`20
`determining their differentiator values. The processing
`which avoids redundancy, as well as truncation and
`of composite values and differentiators continues to the
`roundoff errors. All possible 256 combinations of two
`top of the binary tree corresponding to the hierarchy of
`gray-level values are charted in sixteen segments of
`image subdivisions by coalescing pairs of composite
`equal size in such a way that V1/V2 intersections in
`values of each lower order into the next higher order.
`successive segments numbered from 0 to 15 correspond
`25
`The culmination of the zero-th approximation com
`roughly to increasingly larger average values. The seg
`prises a single primary value and its first differentiator.
`ments are constructed by first placing a unit width strip
`This primary value is the approximate gray-scale value
`0 with sixteen unit areas in the lower left corner and
`of an overall monotone image.
`adding on further unit width strips paralleling the first
`There are several schemes by which the tree of FIG.
`until the whole chart is filled. The strips represent in
`30
`4 can be built up. The principle can be illustrated con
`creasingly darker values from white in strip 0 to black in
`cretely by considering a rectangular image with thirty
`strip 15. The encircled numbers assigned to the strips
`two pixels to be scanned, as shown in block 56 of FIG.
`correspond with composite, i.e., near average, values.
`5. Each pixel in block 56 is numbered in a pattern divid
`Each strip in turn has each of 16 unit areas also num
`ing the image into four quadrants. Each quadrant is
`bered from 0 to 15. The latter numbers are the differen
`35
`uniformly numbered vertically in respective left and
`tiators d which serve to disambiguate or differentiate
`right halves. These pixel numbers appear at the base of
`among the value pairs that have the same composite
`the pyramid in FIG. 4. Whether the scanning proceeds
`value. As shown in FIG. 3 by dotted lines defining the
`line by line and from left to right or in the numerical
`intersection of a V1 value of 3 and a V2 value of 4, the
`sequence shown, the stored grey-level values are ac
`composite value Vc becomes 3 because the intersection
`40
`cessed in accordance with the tree of FIG. 4.
`falls in strip 3 and the differentiator d becomes 7, i.e., the
`One scheme processes all values level by level. In this
`intersection is seen to fall in the seventh unit area of
`scheme the values of the thirty-two pixels on the bottom
`strip 3. Since the highest values of Ve and d are 15,
`level are combined in pairs composing a left-hand odd
`four-bit numbers suffice to represent them. Therefore,
`numbered cell and its right-hand even-numbered com
`an eight-bit number can completely represent the two
`45
`panion to form the node directly above, including a
`values together. The 256 correspondences between Vi
`differentiator d and a composite value v found in a
`and V2 values on the one hand and Vc and d values on
`look-up table encoding the diagram of FIG. 3. Thus, the
`the other hand can be determined from the diagram of
`left-hand node on the fourth-approximation level is
`FIG. 3 and stored in RAM 11, as shown in FIG. 1, for
`look-up purposes.
`formed from cells 1 and 2 (coded as gray levels 15 and
`50
`14) by looking up values 15 and 8 for V1-2 and d1-2. The
`The values determined from the diagram of FIG. 3
`right-hand node is similarly formed from cells 31 and
`are identically stored at the display location in frame
`32. Intermediate nodes are further formed in an analo
`buffer 19.
`gous manner to complete the third-approximation level
`It may be noted from FIG. 3 that the composite val
`containing eight nodes. The second-approximation
`ues corresponding to equal V1 and V2 values fall on the
`55
`level is formed into four nodes by pairing the composite
`left-to-right upward diagonal and are these same values.
`values of the third-approximation level. After comple
`It can further be shown that the digit-conserving com
`tion of the two nodes of the first-approximation level
`posite values are never farther than 4 out of 16 gray
`the first differentiator and primary value on the zero-th
`scale levels away from the true average, and this only in
`level are formed in an analogous fashion.
`low-probability cases where one of the values is either a
`60
`A second scheme proceeds in a zigzag fashion by
`0 or 15 and the other value is at midrange.
`processing successively only those lower-level values
`FIG. 4 is a diagram of the hierarchical structure or
`needed to move to the next higher level. Thus, the
`tree of composite values V, and differentiators d into
`values of cells 1 and 2 (coded as graylevels 15 and 14)
`which the pixels of the final picture are processed. A
`simple image containing only thirty-two pixels is shown
`are combined, followed by those of cells 3 and 4 (coded
`65
`for discussion purposes. Four levels of approximation
`as 13 and 11) to form the two leftmost nodes of the
`fourth-approximation level with respective composite
`are shown for this rectangular image four pixels across
`values 15 and 13 and differentiators 8 and 9. Then in
`by eight lines high. Each elemental pixel is also rectan
`
`10
`
`
`
`10
`
`15
`
`4,222,076
`7
`8
`stead of going on with the remaining cells on the lowest
`ing the fourth approximation and block 66 shows the
`final, fifth-approximation image.
`level, the last-mentioned nodes are combined to form a
`node on the left of the third-approximation level. Treat
`FIGS. 7 and 8 compare portrait images transmitted
`ing cells 5, 6, 7 and 8 yields the next two nodes on the
`directly line by line and progressively according to a
`fourth level, and thus permits determination of the next
`fifteen-level tree similar in principle to the tree of FIG.
`node on the third level. The latter node, together with
`4. A tenth approximation, containing 1024 cells and
`the third-level node previously determined, permits the
`transmittable as 4096 bits in less than one second, pro
`formation of the first node on the second level. Cells
`vides the image shown at the left in FIG. 8. This image
`9–16 are similarly processed to allow a first-level node
`is recognizable as the head of a bearded man. This is one
`to be formed. The right half can now be processed in a
`thirty-second of the total image detail available. This
`similar fashion until its first-level node is found. Finally,
`can be compared with the corresponding left image
`the primary node 41 is generated.
`shown in FIG. 7 as the top thirty-second strip of the
`With either scheme all intermediate values are stored
`complete image resulting from a line-by-line scan of the
`for further use.
`same elapsed transmission time. This fraction of the
`FIG. 5 illustrates the progression of images obtained
`image is clearly not recognizable. The elapsed times for
`from the pyramid of FIG. 4 indexed by pixel numbers.
`the other images shown in FIG. 8 for the remaining
`Image 51 is the monotone composite average of all
`eleventh through fifteenth approximations are, respec
`pixels, or the zero-th approximation. Image 52 appears
`tively, approximately 2, 4, 8, 16 and 32 seconds. It is
`as top and bottom halves of the ultimate image averag
`thus clear that each approximate picture of the sequence
`ing pixels 1–16 and 17–32, respectively. The further
`20
`in FIG. 8 takes twice as long to transmit and process as
`splittings are represented by images 53 through 56.
`the previous one.
`Image 56 is the highest-resolution original image.
`With regard to the number of bits needed to transmit
`FIG. 6 illustrates the same progression of images as
`the entire image, the thirty-two pixel image of FIG. 6
`that shown in FIG. 5 but indexed and shaded by gray
`requires the transmission of 128 bits on a line-by-line
`scale values. These gray-scale values are the same as
`25
`basis. On a progressive basis there are four bits for each
`those entered in the cells and nodes of the pyramid of
`of the primary value and first differentiator. Only thirty
`FIG. 4. The original image varies in shade from black
`differentiators at four bits each remain to be sent. The
`(level 15) in the upper left-hand corner to white (level 0)
`same total of 128 is obtained. It is apparent that progres
`near the center. If FIGS. 5 and 6 are superposed, the
`sive image transmission according to this invention is
`cells contributing each composite value can readily be
`30
`nonredundant.
`seen. The corresponding composite and differentiator
`Once the image has been analyzed into a primary
`values shown in the nodes of FIG. 4 can also be seen to
`value and a tree of differentiators, there exist a variety
`have been derived from the conversion chart of FIG. 3.
`of ways that the picture can be transmitted and recon
`After processing of pixel values has been completed,
`structed. Rather than uniformly splitting all cells of one
`transmission begins. The order of transmission encom
`35
`level of approximation to yield the next, it can be ar
`passes the primary value contained in the upper half of
`ranged that a particular image area be given favored
`node 41 followed by the first differentiator contained in
`treatment in order to have its detail revealed sooner, for
`the lower half of node 41. Next in order are the differen
`example. The sender may wish to call attention to a
`tiators shown in the lower halves of each node level by
`particular feature or to send central data ahead of pe
`level.
`ripheral data.
`At the receiver the RAM values are demodulated
`Non-uniform development of the binary tree can be
`into digital form in block 16 of FIG. 1 prior to process
`achieved (1) by having the coordinates of the favored
`ing in image processor 17. When the primary value is
`area known in advance by both sender and receiver, (2)
`received and demodulated, processor 17 applies this
`by employing the same splitting algorithm at transmit
`value to frame buffer 19 which in turn furnishes conven
`45
`ter and receiver, and (3) by having the algorithm corre
`tional timing, deflection and intensity information for a
`spond to a development of the tree from existing nodes.
`full frame period to generate a monotone image, as
`shown in block 61 of FIG. 6. The primary value, con
`The entire hierarchical tree structure can be com
`puted and stored in an array of integrated-circuit (IC)
`taining only four bits, can arrive over a 4800-baud voice
`chips.
`telephone channel in less than one millisecond. Display
`unit 18 can typically generate an image in 1/60 second.
`While this invention has been described in terms of a
`specific illustrative embodiment, those skilled in the art
`The transmission of the first differentiator d, another
`will appreciate that many modifications are possible
`four-bit number, can occur in another millisecond. The
`within the spirit and scope of the appended claims.
`information contained in the primary value and its asso
`ciated differentiator, a total of eight bits, is sufficient to
`I claim:
`55
`look up the composite values defining the light levels of
`1. An image transmission system (FIG. 1) including a
`the top and bottom halves of the first approximation, as
`scanning device (10), an addressable memory (11) for
`gray-scale light-intensity values corresponding to each
`shown in block 62 of FIG. 6. These composite values
`combined with the next two differentiators, encoded in
`picture element of an image to be transmitted, a trans
`another eight bits taking less than two milliseconds to
`mission channel (15) for such image and an image dis
`60
`transmit, generate the second approximation compris
`play device (20) at the opposite terminal of such channel
`ing the four rectangles shown in block 63 of FIG. 6.
`CHARACTERIZED IN THAT
`These rectangles are in turn split laterally upon the
`numerical gray-scale values of discrete picture ele
`transmission and reception of the four differentiators of
`ments obtained in such scanning device (10) are
`the second level as shown in block 64 of FIG. 6.
`taken from said addressable memory (11) in succes
`65
`Transmission of further differentiators continues to
`sive pairs and transformed by interaction with the
`define shadings for smaller and smaller rectangles.
`contents of said addressable memory in a processor
`Block 65 of FIG. 6 shows a sixteen-cell image constitut
`(13) into a hierarchical array of integral values
`
`50
`
`11
`
`
`
`9
`according to their approximate averages from in-
`dividual-element pairs to the entire image,
`-integral values are transmitted from said addressable
`memory (11) in words of uniform length level-by-
`level of the hierarchical array from the topmost
`level downward to elemental level over said chan-
`nel, (15) and
`the transmitted image is progressively reconstructed
`(16, 17, 18 and 19) in successively finer detail in said
`image display device (20) at the opposite terminal
`of said channel adaptably to having transmission
`stopped at any hierarchical level up to the trans-
`mission of final detail.
`2. The image transmission system defined in claim 1
`further CHARACTERIZED IN THAT
`said addressable memory (11) is a random-access 15
`memory, and
`said processor (13) performs arithmetic and control
`address operations on digital words stored in said
`memory.
`3. The image transmission system defined in claim 1 20
`further CHARACTERIZED IN THAT
`said transmission channel (15) includes transmitter
`(14) and receiver apparatus (16) for translating
`between the passband characteristics of said chan-
`nel and the baseband characteristics of the respec-
`tive transmitting and receiving terminals.
`4. The image transmission system defined in claim 1
`further CHARACTERIZED IN THAT
`the receiving apparatus at the opposite terminal of
`said channel includes a frame buffer (19) for con- 30
`trolling the beam intensity characteristics of said
`display device (20) in accordance with received
`data words.
`5. The image transmission system defined in claim 1
`further CHARACTERIZED IN THAT
`each successive pair of numerical gray-scale values 35
`from said scanning device (10) is transformed by
`said processor (13) into afirst composite integer
`value having the same number of bits as an original
`gray-scale value and approximating the average of
`the pair of gray-scale values and into a second 40
`differentiator value of the same number of bits
`indicating the identity of the original individual
`values from which the associated composite value
`was formed, and
`the correspondence of each possible pair of gray-
`scale values to a respective composite and differen-
`tiator value is programmed into said addressable
`memory (11).
`6. The image transmission system defined in claim 5
`further CHARACTERIZED IN THAT
`pairs of composite values obtained from pairs of origi-
`nal gray-scale values are further processed into
`higher levels of combined composite and differenti-
`ator values to form additional levels of said hierar-
`chical array until a single primary composite value
`and corresponding first differentiator value are
`obtained and stored in said memory (11).
`7. The image transmission system defined in claim 1
`CHARACTERIZED IN THAT
`
`5
`
`10
`
`25
`
`45
`
`50
`
`55
`
`4,222,076
`
`10
`element of an image to be transmitted, a transmission
`channel for such image and an image display device at
`the opposite terminal of such channel, the method of
`progressively transmitting an image over such system
`comprising the steps of:
`generating numerical gray-scale values of discrete
`picture elements in such scannin