Versatile multipoint video composition and bridging system

Ό 96/08911

PCT/US9S/11857

VERSATILE MULTIPOINT VIDEO COMPOSITION AND BRIDGING SYSTEM

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention generally relates to the field of communication systems. More particularly, the present invention relates to a versatile multipoint video composition and bridging system for connecting a plurality of geographically dispersed locations during, for example, a video conference or broadcast.

2. Background Information

Systems for video conferencing and broadcasting over a communication network provide several advantages to users that are located at different remote locations. For example, suoh systems enable information and images to be transmitted quickly and in real time to a plurality of different locations, and reduce travel time and costs usually incurred by remotely located participants and users. Video conferencing and broadcasting systems may be used for many different applications, including business and work conferences, classroom and tutorial lectures, and courtroom proceedings where, for example, witnesses are located at geographically dispersed areas.

Several different types of video conferencing systems have been developed. For example, ASHIDA et al., U.s.

Patent No. 5,003,532, discloses a multipoint conferencing system for establishing a video conference among three or more remote sites, and POIRIER et al., U.S. Patent No. 4,054,908, discloses a video telephone conference system in which a plurality of remotely located sites are interconnected by a video switching network. Further, KIKUCHI, U.S. Patent No. 3,636,265, discloses a television conference telephone system that utilizes a telephone switching network or exchange to interconnect remotely located conference attendants.

WO 96/08911

PCT/ÜS95/11857

In such past attempts, the selection of the video image or signal to be transmitted to all locations has sometimes been done based on the determination of the location with the loudest audio signal (i.e., the dominant voice location), so that all participants receive the video image from the location of the conference attendant that is currently talking. Alternatively, the distribution of video images to remote locations has been based upon control signals which are received from each of the locations (see, for example, ASHIDA et al., U.S. Patent No. 5,003,532), or the video image seen at all locations has been selected by a designated chairperson. While such past attempts have facilitated video teleconferencing among a plurality of participants, they are limited in that only one, or in some cases the same, video image is transmitted to all participating locations at any given time.

Video conferencing system users often desire to simultaneously see more than one video image or signal at their location. As such, there have been attempts to provide a video conferencing system in which multiple video images, including that from the dominant voice location, are transmitted to all participants' locations. See, for example, STODDARD et al., U.S. Patent No. 4,931,872, which discloses a video teleconference system in which quad-split screens are provided at each remote location, so that video images from four other locations may be simultaneously displayed at a remote location. In multipoint video conferencing systems, analog quad-units have been provided to display video images from up to four locations on a single screen. Such analog quad-units accept up to four analog National Television Standards Committee (NTSC) video signals, and generate a single composite NTSC signal.

While quad-units facilitate the display of multiple images in video conferencing systems, for example, such units are limited in that they do not allow the simultaneous display of more than four images. Further,

-2WO 96/08911

PCT/ÜS95/II857 . the use of analog quad-units, such as those described above, results in degraded picture quality due to repeated translations between analog and digital signal representations. In addition, conferencing through the use of analog quad-units requires a pair of video codecs (coder-decoder) for each participating site and, thus, is an expensive solution. Moreover, video conferencing and broadcasting systems that incorporate quad-units do not allow for windowed display of multiple images in scaled and other arbitrary formats.

In order to overcome such drawbacks, attempts have been made to provide more versatile multipoint conferencing systems. For example, BOERGER et al-, U.S. Patent No. 4,650,929, discloses a video conferencing system that includes a central station for receiving control signals from each of the remote locations to control the splitscreen display of large and small video images at a user's or participant's terminal. Further, KASSATLY, U.S. Patent No. 5,157,491, discloses a video broadcasting and teleconferencing system in which participants may chose particular display formats and particular video images to be displayed at their location. See, also, for example, WEBER et al., U.S. Patent No. 4,995,071, which discloses a video conference system in which each location is provided with a split screen with control symbols for controlling various attributes of the received video and audio signals.

These past attempts have provided more versatility in multipoint conferencing systems, by enabling users to individually control the type of display at their location.

However, they have not provided a great degree of versatility, nor have they overcome all of the above-noted drawbacks and disadvantages of prior systems. There is still a need for a video conferencing and broadcasting system that provides each remotely located user with the option to display images from multiple locations

-3WO 96/08911

PCT/US95/11857 simultaneously in separate windows that can be selectively arranged by the user in arbitrary formats (e.g., scaled, translated, and partially or wholly occluded) in order to produce a video montage. Further, there is currently a need for such a system that efficiently resizes, cuts, and pastes, etc. the composited images while maintaining good image quality.

SUMMARY OF THE INVENTION

In view of the foregoing, the present invention, through one or more of its various aspects, embodiments and/or specific features or sub-components thereof, is thus presented to bring about one or more objects and advantages, such as those specifically noted below.

A general object of the present invention is to provide a versatile multipoint system for video signal composition and bridging of a plurality of geographically dispersed users.

More particularly, an object of the present invention is to provide a versatile multipoint conferencing system that enables each remotely located user to optionally display images from multiple locations simultaneously, in separate windows that can be arranged in arbitrary formats.

Another object of the present invention is to provide a video conferencing system that enables users to display video images from other locations simultaneously in separate windows that can be independently scaled, translated, and partially or wholly occluded, zoomed, and panned.

Still another object of the invention is to provide a flexible multipoint system that efficiently resizes, cuts and pastes composited images while maintaining good image quality. Yet another object of the present invention is to provide a versatile video composition and bridging system in which video montages are produced from digital signal representations, in order to avoid degradations due to

-4Ο 96/08911

PCT/US95/11857 repeated translations between analog and digital signal representations.

Digital signal representations signals are of two kinds, namely signal space representations and transform space representations. Compressed digital video is transmitted and received in a transform space. A receiving codec (coder-decoder) may perform an inverse transformation in order to recover the signal space representation. Further, motion compensation may be interwoven with the transformation processes.

Another object of the present invention is to provide a versatile video composition and bridging system in which video montages are produced from the signal space representations of the incoming images. The incoming images in transform space can be inverse transformed to the signal space through the use of an appropriate inverse transform operation, e.g., using the Inverse Blocked Discrete Cosine Transform (BDCT'¹) , together with inverse motion compensation. The choice of the inverse transform operation used for each video input may be determined by the forward transform operation used by the corresponding transmitting codec. Once montages are created in the signal space, they can be transformed from the signal space into transform space through the use of an appropriate forward transform operation, e.g., using the forward Blocked Discrete Cosine Transform (BDCT), together with motion compensation. The choice of the forward transform operation used for each montage may be determined by the inverse transform operation used by the corresponding

0 receiving codec.

The participating codecs need not all use an identical transform scheme, and may each work with digital frames that have different aspect ratios and different pixel counts in the horizontal and the vertical directions.

Accordingly, the present invention will permit the

<img file="CA2199477C_D0001.tif" />

PCT/US95/11857

WO 96/08911 0 2 i 9 interconnection of sites that employ different types of codecs, e.g., motion-JPEG, MPEG, or H.26l-based codecs.

According to the present invention, it is also possible in a multipoint conference to include sites that do not have codecs, but transmit and receive analog and digital video images without any type of compression. Alternately one or more sites may have codecs that perform only entropy coding and decoding, without doing transformbased noisy compression or transform-based decompression.

Still another object of the present invention is to provide a versatile multipoint composition and bridging system that reduces delay and hardware requirements by composing and bridging video signals directly in the transform domain.

The present invention is therefore directed to a versatile multipoint bridging system or method, or one or more sub-systems or sub-methods thereof, for bridging a plurality of users located at different terminal end locations of a communication network. Each of the locations include terminal equipment for transmitting and receiving video images and data signals, where the data signals include display configuration information for video images that are originating from one or more of the different terminal end locations. The video images and the data signals are received from each of the locations, and respective video montages are generated for each of the locations based upon the data signals received. In this regard, the received video images are selectively resized based upon the data signals, and the resized video images are montaged in order to produce the montage images based upon the data signals. The video montages that were generated are then transmitted to the locations so that they may be displayed by a display device provided at each of the locations.

The resizing of the incoming video images may be performed by selectively resizing the video images while

-6Ό 96/08911

PCT/US95/II8S7 the video images are represented in signal space, or in the alternative, while they are represented in transform space.

A mechanism may be provided for inputting display configuration information which defines the montage displayed by a display device provided at each of the locations. In this regard, the display configuration information may comprise information regarding the position, the relative width, and/or the size, on the display device, of a display window provided for each video montage. The display configuration information may also comprise information regarding the zoom and pan settings for each display window.

In accordance with a further aspect of the invention, the terminal equipment may be provided with one or more devices for capturing video and audio teleconferencing information for transmitting such information to other locations.

Further, the present invention may mix still images and conferencing props, such as electronic white-boards, computer screens, or slides, together with video in the montages that are created. The incoming still-images and props may be coded in accordance with a compression standard, such as JPEG, or may be input in a digital signal space form. In addition, video, still image, and prop windows may be circumscribed by borders, and may display associated soft-controls, icons, and annotations.

The above-listed and other objects, features and advantages of the present invention will be more fully set forth hereinafter.

WO 96/08911

PCT/US95/11857

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention is further described in the detailed description which follows, by reference to the noted plurality of drawings by way of non-limiting examples of preferred embodiments of the present invention, in which like reference numerals represent similar parts throughout the several views of the drawings, and wherein:

Fig. 1 is a general illustration of a flexible multipoint system for video signal composition and bridging;

Fig. 2 is a block diagram of a first illustrated embodiment of a multipoint control unit;

Fig. 3 shows an example window display organization for a display device;

Fig. 4 shows an implementation of a resampling circuit;

Fig. 5 is a block diagram of a second illustrated embodiment of a multipoint composition and bridging system;

Fig. 6 is a specific implementation of a resampler which may be provided with the multipoint bridging system illustrated in Fig. 5;

Fig. 7 illustrates an alternative implementation of a resampler;

Fig. 8 illustrates an example embodiment of a systolic array which may be utilized in the resampler illustrated in Fig. 7; and

Fig. 9 is a block diagram of an exemplary architecture for performing one-dimensional bridging.

DETAILED DESCRIPTION OF THE ILLUSTRATED EMBODIMENTS

Referring now to Fig. 1, a general description of an exemplary embodiment flexible multipoint system for video signal composition and bridging will now be provided.

As shown in Fig. 1, a plurality of remote locations AC (only three have been shown for the purposes of illustration) may be provided that are connected to a versatile multipoint composition and bridging unit 100

-8WO 96/08911

PCT/ÜS95/11857 across a communication network 70. Each of the remote locations includes terminal equipment 10 that is connected to communication network 70 by communication links 50 and 55. Each terminal equipment 10 may include a display device 12 and a display-control processor 13 for displaying video images, an input device 14, which may comprise, for example, a point-select-and-drag device, a remote control unit, a keyboard and/or mouse, for inputting data and control commands, and microphones 16 and speakers 17 for transmitting and receiving audio signals. Further, a video camera device 18 may be provided for gathering a video image for transmission to a remote location. Video camera device 18 may generate analog National Television Standards Committee (NTSC), Phase Alternating-Line (PAL), or

Sequential Coloeur Avec Mémoire (SECAM) images and may include analog/digital converting means (not shown) for converting the analog NTSC, PAL, or SECAM images into digital images suitable for transmission. In addition, or in the alternative, a video camera device 18 may be adapted to directly generate a digital video signal.

Each terminal equipment 10 may also include a codec 15 (i.e., a coding and decoding device) for source and channel coding and decoding, and a substream separator and integrator (not shown) for separating and integrating the video, audio and data substreams transmitted and received by terminal equipment 10. At each terminal equipment 10, codec 15 may be omitted such that analog or digital video are directly transmitted and/or received in a raw uncompressed state, or in a digital form that has been entropy encoded.

It is noted that a number of companies manufacture video codecs that conform to the standard H.261. Such companies include NEC, AT&amp;T, GPT, Compression Labs, Inc., PictureTel, and Vtel. The NEC codec is designated as NEC

TC500. The AT&amp;T codec is designated S4000. Compression

Labs manufactures Rembrandt. PictureTel makes model system 1000 and system 4000. Vtel makes MediaMax386.

-9WO 96/08911

PCT/ÜS95/11857

Display-control processor 13 may receive pointing and selection signals from input device 14 and generate the position, sizing, occlusion, zoom, and pan data to be sent from terminal equipment 10 to bridging unit 100. Based on this data, bridging unit 100 may produce a video montage to be displayed at the remote location. Display-control processor 13 may receive a digital video montage in signal space from codec 15, and overlay window frames, cursor, and icons. With irespect to outgoing video, display-control processor 13 may be adapted to perform the necessary analog-to-digital conversion on each frame and output a sequence of video frames in the signal space to codec 15.

In addition, terminal equipment may include a memory device (not shown) for storing still video images or other data for transmission and display at other remote locations.

The composition and bridging unit 100 may be located at a central location in communication network 70, as shown in Fig. 1, with each of the remote locations A-C being geographically dispersed at terminal end locations of the communication network 70. Bridging unit 100 may be connected to communication network 70 by a plurality of communication links 60, that include a pair of communications links 50 and 55 for each remote location. Communication links 50 and 55 carry signal streams to and from each terminal equipment 10 and bridging unit 100. Each signal stream may include a video substream, an audio substream, and a data substream. Although Fig. 1 depicts two separate communication links 50 and 55 for carrying these signal streams, a single two-way communication link may also be used for interconnecting each terminal equipment 10 to communication network 70. Communication links 50 and 55 may, e.g. , comprise one or more transmission links for transmitting signals from one point to another, with transmission media such as two-wire open lines, twisted pair lines, coaxial cable, optical fibers, satellite systems, terrestrial microwave links, and so on.

-ioΟ 96/08911

PCT/US95/11857

The links may be in the for π of multiple channel links for transmitting TDM signals, such as, e.g., DS1, or DS3-rate communication links; fractional DS1 or fractional DS3-rate communication links; SONET links; or ATM links. in addition, links 50 and 55 may comprise local connections in a LAN environment.

In view of the large bandwidth of the connection between bridging unit 100 and communication network 70, it is more advantageous to place bridging unit 100 at some central location in communication network 70. The bridging unit 100 may also be connected to communication network 70 through a single bi-directional link (not shown), having a bandwidth that is greater or equal to the aggregate bandwidth of all the communication links 50 and 55 connected to network 70 from each of the remote locations.

As described in more detail below, bridging unit 100 serves as a video bridge for each of the remote locations A-C during, for example, a video teleconference. The bridging unit 100 receives each of the incoming signal streams from the remote locations along communication links 55. These incoming signals are channel-decoded by the bridging unit 100 and then are separated into the three component signal substreams (i.e., the video substream, audio substream, and data substream) . Based on the data substreams from a given location, bridging unit 100 resizes, cuts and pastes the various video images into a composite or montage for display at that location. A video conference attendant, for example, at one of the remote locations may input data via input device 14, so as to optionally display video images from one or more other locations within separate display windows at a particular terminal or set of terminals. The display windows may be displayed in arbitrary formats, and may be zoomed, panned, scaled, translated and/or partially or wholly occluded based on the data substreams received from the user's location. Once the various montages have been developed

-11WO 96/08911

PCT/US95/11857 for each of the locations, bridging unit 100 integrates the video montages with the mixed and/or switched audio signals, and then channel codes the various integrated signal streams before they are delivered to the remote locations via communication links 50.

A more detailed description of the specific flexible multipoint bridging units illustrated herein will be provided hereinafter. A first illustrated example embodiment of the present invention includes a versatile multipoint composition and bridging unit which performs video signal composition and bridging in signal space (i.e., in the signal domain), and may be implemented as shown in Fig. 2. A second illustrated embodiment includes a versatile multipoint bridging unit that performs video signal composition and bridging in transform space (i.e., in the transform domain), and may be implemented as shown in Fig. 5.

Fig. 2 shows a block diagram of a first illustrated embodiment multipoint bridging unit 101 that performs video signal composition and bridging in the signal domain. For purposes of illustration, Fig. 2 shows bridging unit 101 serving as a video bridge for only three remote locations (i.e., remote locations A, B and C) with an incoming communication link 55 from each of these locations connected to the bridging unit on the left-hand side of the figure, and an outgoing communication link 50 to each of these locations being connected to the bridging unit on the right-hand side of the figure. In general, however, any arrangement and number of remote locations could be connected to bridging unit 101, with separate incoming and outgoing communication links or a single two-way communication link for each of the remote locations, to transmit the various signal streams. A single physical link may even be used to carry each of links 50 and 55.

Each of remote locations A, B, and C transmits a signal stream, which includes a video substream, an audio

-1296/08911 £199477

PCT/VS9S/118S7 substream and a data substream, to bridging unit 101 via a communication link 55. In the specifically illustrated embodiment, the frame structure of the signal stream may comply with ITU-T recommendations H.221, H.230, H.242, and H.261, although other formats could be used for the signal stream in the present invention. Communication links 55 may be full or fractional DS1 or DS3-rate links, SONET links, ATM links, or other suitable links.

In the illustrated embodiment shown in Fig. 2, each communication link 55 is connected to a channel decoder and separator device 110 of bridging unit 101. Each of the decoder and separator devices 110 receives various incoming signal streams from the remote locations and performs channel decoding on the signal streams. Then it separates the video, audio, and data substreams. Device 110 may, for example, include a T1 decoder and a signal substream separator. Further, the decoder and separator device 110 may comply with the applicable ITU-T recommendations.

The separated incoming audio substreams (AS) are fed to an audio mixer 130. Audio mixer 130 generates different outgoing audio substreams for each of the remote locations A, B and C. For example, an audio substream destined for one of the locations could consist of the sum of the incoming audio signals from the other remote locations; in other words, the audio substream to be sent to remote location A could consist of the sum of the incoming audio signals from locations B and C. In addition, the audio signals could be switched, rather than summed, if the summed noise is excessive or overwhelming. In Fig. 2, only one single audio substream is shown as being outputted from audio mixer 130 for purposes of illustration. In practice, audio mixer 130 may output an audio signal for each of the remote locations A, B and C. Further, audio mixer 130 includes means (not shown) for handling all source decoding and coding requirements of the audio signals.

-13WO 96/08911

PCT/US95/11857

The separated incoming data substreams (DS) , outputted from each channel decoder and separator 110, are inputted to a video system controller 120. The data substreams may include data or commands which indicate how a user or participant at each remote location would like to configure its video display. These commands are interpreted by controller 120, which sends the appropriate data and control signals to switches 150 and 155, to resamplers 160164, and to frame composers 170, which are described in greater detail below. The incoming data streams (DS) may include other information, not related to the display configuration, that is transmitted to some or all of the other remote locations. For this purpose, a data substream generator 125 may be provided to generate an outgoing data substream for each of the remote locations A, B and C. Similar to audio mixer 130, data substream generator 125 is shown with only a single data substream issuing therefrom, in order to simplify the illustration in Fig. 2.

In the embodiment illustrated in Fig. 2, each of the separated video substreams (VS), outputted from each channel decoder and separator 110, is inputted into a respective video source decoder 115. The incoming video substreams are decoded to undo the source coding. Source coding generally consists of compression and compaction coding and motion compensation. The source decoding performed by video source decoder 115 may include Huffman decoding, or another type of entropy decoding, to undo the compaction coding. The other parts of source decoding, i.e., compression decoding and inverse motion compensation, involve the inverse transformer 140 within the video source decoder 115. The inverse transformer 140 is discussed in detail below. Further, video source decoder 115 may perform source decoding which complies with ITU-T recommendation H.261 or with International Standards Organization's (ISO's) Motion Pictures Experts Group (MPEG) standard. For information on the H.261 standard see, for

-14Ο 96/08911

PCT/US9S/118S7 example, American National Standards Institute, ANSI Tl.314-1991: Digital Processing of Video Signals - Video Coder/Decoder for Audiovisual Services at 56 to 1536 Kbits/s, ANSI, New York, 1991, the disclosure of which is expressly incorporated herein by reference in its entirety.

The type of video source decoder 115 that is used for each incoming signal may depend upon the source coding method used by the corresponding transmitting codec 15 at the remote location. An appropriate choice of the channel decoder and separator 110 and the video source decoder 115 will permit a remote location equipped with any kind of codec 15, or not equipped with a codec 15, to be connected to bridging unit 101, such that a signal representation is obtained at the output of the corresponding video source decoder 115.

As a result of the source decoding and inverse motion compensation performed by video source decoder 115, a CIF (Common Intermediate Format) image may be recovered in the case of a H.261 codec, or a SIF (Standard Input Format) image may be recovered in the case of a MPEG codec, or another type of digital picture format may be recovered. The CIF and SIF formats are a digital frame formats that are based upon the CCIR Recommendation 601. CCIR 601 recommends that a frame in the signal space be represented by a collection of three separate matrices: Y, Cr, and Cb.

The Y or the luminance matrix encodes the black and white information. The Cr and Cb or color difference matrices encode the color information. The CIF representation allows video coder/decoder standards to apply worldwide, and allows teleconferencing across national boundaries.

Accordingly, video source decoder 115 may accept NTSC, PAL, or SECAM source based signals.

The video source decoder 115 includes inverse transformer 140. The transformation of the image frame from the transform space to the signal space is performed

-15wo9«₈9n Q2199 47 7

PCT/US95/11857 φ by separating the image frame into blocks that are eight pixels wide by eight pixels deep, and then computing the Inverse Discrete Cosine Transform (DCT'¹) for each block. The process of dividing the image frame into blocks, followed by the DCT¹ operation on each block, is referred to as the inverse Blocked Discrete Cosine Transform (BDCT'¹) hereinafter. The Discrete Cosine Transform (DCT) for R^N is defined by the orthonormal basis &lt;p^(n) =C_rcos (2n+l) itr/2N, where _r _;2V~^1/2 , n=0 ^r (.2/N)^1/2 ,n*0

The Blocked DCT (BDCT) basis {&lt;J$_r£z_K for R^N, for any

N e Z⁺ and block-size B e Z⁺, is defined in terms of the DCT basis set for ^rB; &amp;^N(n) = { V™°dB(n-r+r+r_B) , (r-r_B) &lt;n&lt; (r+B-r_s) ^Γ o , otherwise.

In the above equation, r mod B is written as r_B for 15 brevity. In addition, the above equations apply for onedimensional signals. Thus, in the case of two-dimensional images, these equations would have to be applied separately along the rows and columns of each image. Further, the still image and video coding standards JPEG, MPEG and H.261 are all based on the BDCT with a block-size B of eight.

-161WO 96/Q8911

PCT/US95/11857

The basis for BDCT'¹ may be derived and deduced from the BDCT basis described above.

The video source decoder 115 may produce a succession of CIF frames in the signal space. The GIF format is a digital frame format in which the Y matrix is specified to be 352 columns wide by 288 rows deep. The Cr and the Cb matrices are specified to have half as many columns and half as many rows. For a more detailed description of the CIF format, see, for example, American National Standards Institute, ANSI Tl.314-1991: Digital Processing of Video

Signals --- Video Coder/Decoder for Audiovisual Services at to 1536 Kbits/s, ANSI, New York, 1991.

It is noted that video source decoder 115 and inverse transformer 140 may be configured so as to recover transQuarter CIF (QCIF) and QCIF frames in addition to or instead of trans-CIF and CIF image frames. Standard H.261 defines QCIF images as having half the number of pixels, in both the horizontal and vertical directions, as compared to CIF images. As will be appreciated by those of ordinary skill in the art, the present invention could handle any combination of CIF and QCIF images.

Video source decoder 115 outputs luminance and color difference matrices that constitute a signal space frame representation (e.g. , the CIF, QCIF, or SIF representation). The signal space frame representation is the frame representation in signal space that the transmitting codec 15 at a remote location started out with, together with noise or perturbation that is added by the quantization and motion compensation processes. The image frames that are provided in the signal space from video source decoders 115 can be resized using fractional resampling along the rows and columns of the luminance and color-difference matrices. For example, a frame image from location A may need to be resized to a number of different sizes such that the resized frames satisfy the size requirements of all the destination displays. In Fig. 2,

-17WO 96/08911

02199*77

PCT/ÜS95/11857 resizing is performed by resamplers 160-164. Each of the resamplers 160-164 produces a single resized image at its output. Although Fig. 2 only shows five resamplers, more than (or less than) five resamplers may be provided. More resamplers would provide a greater degree of freedom in resizing (by allowing users to choose among more than five different sizes for windowed displays).

Once all of the various incoming frames have been resized, they may be composed to produce CIF frames for display at each of the remote locations. In Fig. 2, the video composition of the final outgoing frames is performed by frame composers 170. Resamplers 160-164 and frame composers 170, as well as switches 150 and 155, are all controlled based on the control signals from video system controller 120. As noted above, video system controller 120 interprets the data substreams from each remote location. These data streams indicate how and what images should be composed and displayed at each user's location.

The illustrated embodiment may be configured so that a user or participant at each remote location may instruct bridging unit 101 to generate a video montage for display at their display device 12 in a desired fashion, by specifying a set of four numbers X_iz Y_iz Z_if and S_iz for each of the images from the participating locations. These numbers may be inputted by a user through an appropriate user interface (e.g., a graphical user interface - not shown) using input device 14 which, as discussed above, may consist of a keyboard and/or mouse device. The numbers X_Aand Y_± give the position of the top left corner of a video originating from remote location L_iz and the number Z_£indicates the relative depth of the display window for remote location L_à with respect to the other display windows. S_± indicates the size of the display window for the image originating at location L_x. S₁ may give the window-length in units of pixels, for example; and, the

-182199477

PCT/US9S/118S7 ^wo 96/08911 number of pixels down the window could be derived based on the window-length and the aspect ratio.

Fig. 3 shows an example of a window display organization for display screen 12. In Fig. 3, it is assumed that there are three participating conferencing locations L_o - L₂, and that X corresponds to a coordinate along the horizontal axis, Y corresponds to a coordinate along the vertical axis, and that Z corresponds to relative depth based upon a coordinate along an axis which is orthogonal to the horizontal and vertical axes, and which goes into the sheet of the drawing (.which is into the screen of the display) . Each of the display windows in Fig. 3 is assigned a unique Z coordinate, and the relative depth of each of the display windows determines which display windows are partially or wholly occluded.

In accordance with another aspect of the present invention, S_± may correspond to a scaling factor for determining the size of each of the display windows. In such a case, a window may be displayed at X^s times the full-screen size, where X and S are integer values. For example, the display windows may be scaled by factors of the powers of X=2, such that when the size of number S is increased, the size of the window displayed on the screen is decreased. Of course, other scaling conventions and other meanings of the scaling factor Si can be used, e.g., in order to provide more flexibility in the resizing of the display windows. For example, the windows could be scaled and displayed at 3'^s or 4’^B times that of a full-screen size, or S could be a real number with the windows being scaled and displayed at S times the full-screen size.

Referring now back to Fig. 2, based on the various sets of numbers X_±, Y_±, Z_iz and S_± that are provided in the data substreams from each of the locations, video system controller 120 sends the appropriate control signals to switches 150 and 155, resamplers 160-164 and frame composers 170. These control signals control the various

-19wo 96/08911 02199477

PCT/US95/11857^9^ components in bridging unit 101 so that an incoming frame image from, for example, location A, is distributed by switch 150 to none or one or more of the resamplers 160164, depending upon how many different sizes of the video images from a given location are requested by the other locations. Each of the resamplers 160-164 produces a single sized image at its output that is distributed to the various frame composers 170 by switch 155 based on the various video images and sizes to be composed at each of the frame composers 170. Frame composers 170 receive the various resized images and composes them into new Y-Cr-Cb arrays, one set per participating location, where each set carries the composite montage of images requested by each location.

The montages are outputted from frame composers 170 to video source coders 180, as shown in Fig. 2. Video source coders 180 perform transformation, quantization, entropy coding, and motion compensation. Transformation may be based on the BDCT, which is described above with respect to inverse transformer 140. The resultant source-coded image is then input to an integrator and channel coder 190, as illustrated in Fig. 2. The resultant video substream is then integrated with the audio and data substreams and, thereafter, channel coded (to produce, for example a T1 signal stream) by integrator and channel coder 190 for transmission to one or more of the remote locations A, B, and C. As shown in Fig. 2, the resulting signal streams may be transmitted to locations A, B, and C via outgoing communication links 50.

In Fig. 4, an exemplary embodiment of a onedimensional resampling circuit of resamplers 160-164 is illustrated. Each of the resamplers 160-164 may include two identical one-dimensional resampling circuits that are connected in tandem, wherein one of the resampling circuits scales along the x (horizontal) axis and the other resampling circuit scales along the y (vertical) axis. For

-20CA 02199477 2005-01-31 the purposes of illustration, an example of one of the resampling circuits that may be used in resamplers 160-164 is shown in Fig. 4.

A one-dimensional discrete-time signal can be resized, with minimal loss in quality, through the use of a digital fractional-resampling system, such as that illustrated in Fig. 4. As shown in Fig. 4, such a system may include an upsampling filter 167, followed by a smoothing and anti-aliasing filter

168, and then followed by a downsampling filter 169. For a further description of such filters, see, for example, P.P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice Hall, Englewood Cliffs, New Jersey, 1993, or A.V. Oppenheim and R.W. Schafer, Discrete-Time Signal Processing, Prentice Hall, Englewood Cliffs, New Jersey, 1989.

Figure 4 shows the logical arrangement of the filters 167169. This arrangement, however, could be further simplified in a physical realization. The arrangement of these digital filters 167-169 allows signal size reduction or increase, in principle, by any rational factor. However, if the rational factor in its reduced form has large integers in the numerator and the denominator, then a different method that uses polynomial fitting and filtering may be used, which is more cost-effective. In this regard, reference can be made to T.A. Ramstad, Digital Methods for Conversion Between Arbitrary Sampling Frequencies, IEEE Trans. ASSP, Vol. ASSP-32, pp. 577591 (June 1984). If the numerator or denominator are highlycomposite numbers with small factors, resampling can also be done with a cascaded arrangement of filters where each filter upsamples or downsamples by a component factor (see, e.g., P.P. Vaidyanathan, Multirate Systems and Filter Banks, Prentice Hall, Englewood Cliffs, New Jersey, 1993, noted above). As noted above, the resizing of the display windows may be performed in accordance with Si representing a scaling factor, and based on the various powers of X (X’^s) , where X is an integer. For example, X may be set to 2, so that scaling is

-21CA 02199477 2004-05-12 performed based on the various powers of two (2^_s) . This type of resizing arrangement provides certain simplicity in terms of avoiding upsampling and fractional-sampling digital filter structures (see, e.g., page 109 in the P.P. Vaidyanathan reference noted above). If reduction by integral factors only is performed by resamplers 150-164, then the upsampling filter 167 can be omitted.

The smoothing and anti-aliasing filter 168 can be designed using a number of different methods. For example, anti-aliasing filter 168 may be designed through the use of a truncated sine window, or the use of the product of a truncated sine window with a smooth but rapidly decaying function (e.g., similar to a Kaiser window; see, e.g., the P.P. Vaidyanathan and A.V.

Oppenheim et al. reference noted above), which improves sidelobe suppression from 21 to 40 db over the truncated sine. In addition, the anti-aliasing filter 168 may be designed through the use of wavelets, such as those described in M. Frazier and A. Kumar, Introduction to the Orthonormal Wavelet Transform or Discrete Sets, pages 51-95 in Benedetto and Frazier (eds.) in the book Wavelets: Mathematics and Applications, published by CRC Press, New York, 1993.

Zooming and panning may be accomplished by resizing a suitable segment of the signal space image, instead of resizing the entire image.

As described in detail above, bridging unit 101 of Fig. 2 performs video signal composition and bridging in the signal domain (i.e., signal space) and entirely in the

-22I WO 96/08911

PCT/ÜS95/11857 digital domain. Since video images are frequently transmitted in the transform space rather than the signal space (according, for example, to video compression methods used in motion-JPEG, H.261 and MPEG), the bridging unit 101 of Fig. 2 calculates the inverse and forward transforms (based on the BDCT) of the incoming video substreams during source-decoding and source-coding. As an alternative, the present invention may perform video composition and bridging directly in the transform space, so as to avoid the need for the computation of the inverse and forward transforms. Such an approach reduces delay and hardware requirements, and is advantageous where video images are transmitted in the transform space.

Referring now to Fig. 5, a description of a second embodiment of a bridging unit, i.e., of an example flexible multipoint bridging unit 201, which performs video signal composition and bridging directly in the transform space, will be described.

Fig. 5 shows a block diagram of a multipoint bridging unit 201 for bridging a plurality of locations during, for example, a video conference. While Fig. 5 only shows three geographically dispersed locations A, B, and C, more than three locations may be bridged by bridging unit 201. The block diagram of Fig. 5 is similar to that of Fig. 2, except that the video source decoder 115 and the video source coder 180 have been replaced by a trans-CIF decoder 116 and a trans-CIF coder 181, respectively, and a lookup table 121 and a Lambda memory 220 have been included. The following description generally discusses only the differences of Fig. 5 from that of Fig. 2; a detailed description of the various elements and parts in Fig. 5 that are similar to that in Fig. 2 (e.g., channel decoder 110, integrator and channel coder 190, etc.) has been provided above with respect to Fig. 2.

In Fig. 5, bridging unit 201 composites (e.g., by resizing, zooming, panning, cutting and pasting) the

-23WO96/08911 0 2 19 9 47 7

PCT/US95/11857I various video signals directly in the transform space or domain. The trans-CIF decoder 116 receives a succession of video frames in which blocks of the Y, Cr, and Cb matrices have been transformed following motion compensation, and converts those matrices to a trans-CIF” representation in which the effects of entropy encoding and motioncompensation have been undone, but the image remains in the transform domain. Thus, the output of the trans-CIF decoder 116, defined to be the trans-CIF image, is the transform space image (e.g., the BDCT image, in the case the transmitting codec uses H.261 or MPEG) of the signal space representation of the matrices Y, Cr, and Cb. In the case the transmitting codec uses motion-JPEG, no motion compensation is performed by the transmitting codec, and the trans-CIF decoder 116 has no motion-compensation to undo. Effects of motion compensation can be removed by using the displacement vector information.

The resized transform space frame (a collection of the Y, Cr, and Cb matrices) may be calculated by resamplers 260-264 through interpolation, by the use of digital .filters connected in tandem, or based on a matrix multiplication of the vectors of the transform space representation of an incoming frame with certain matrices stored in a Lambda memory 220. A detailed description of a theorem, which explains how a resized transform space frame can be calculated from the transform space representation of an incoming frame, is provided below. In addition, a description of the design considerations for the digital filters connected in tandem will be provided below with reference to Fig. 6.

The matrix multiplication may be performed by resamplers 260-264, which may be configured to multiply the incoming row and column vectors of a frame image (either Y, Cr, or Cb) with the appropriate matrices stored in Lambda memory 220. The matrices stored in Lambda memory 220 are selected and sent to resamplers 260-264 based on the data

-24two 96/08911 rcr/i7Sy5/i 1857

Si received in the data substreams. For this purpose, video system controller 120 may include a Look-Up Table (LUT) 121, that is implemented by a suitable memory storing device (e.g., a RAM). In such a case, size parameters S_± may be used as indices to LUT 121 to get addresses which point to the appropriate matrices stored in Lambda memory 220. The located matrices could then be output from Lambda memory 220 to one or more of the resamplers 260-264. Lambda memory 220 may be implemented using any one of various storage mediums, such as DRAM or a magnetic disk.

A specific illustrated example embodiment of resamplers 260-264 for performing the above-noted matrix multiplication is described below with reference to Figs. 7 and 8.

Each resized transform space frame from resamplers

260—264 in Fig. 5 is selectively distributed by switch 155 to one or more frame composers 170, based on the data commands and selected video images to be displayed at each of the remote locations A, B, and C. With the images of a frame being directly provided in the transform space, frame composers 170 would pick and place blocks in different component image frames based on the control signals from video system controller 120 in order to output the resultant video montages. The trans-CIF coders 181 may perform motion compensation and entropy coding on the outgoing video streams directly in the transform space. In general, the trans-CIF coders 181 may complete source coding in such a way as to make the outgoing video stream compatible with the corresponding receiving codec. The integration and channel coding of the signal substreams and the operation of integrator and channel coders 190 in Fig. 5 are similar to that in Fig. 2, and will thus not be described in detail again herein.

Resamplers 260-264 in Fig. 5 may be implemented through the concatenation of two one-dimensional scaling circuits, including one that operates or resizes along the

-25ν,ο^η 02199 47 7

PCT/US95/11857 χ (horizontal) axis and the other which resizes along the y (vertical) axis. As such, each of the resamplers 260-264 may receive two matrices from Lambda memory 220 when resizing an image from one of the locations. This is necessary since a frame in the video sequence is actually a two-dimensional signal, and since scaling needs to be done both along the x and y axes.

More particularly, the embodiment illustrated in Fig. 5 may be implemented in accordance with the following additional details. In the description that follows, a Notation section will be provided to discuss the notation used in the following description, and, thereafter, a Frame Composition Problem (FCP) section will be provided for describing the challenges of composing frame images provided in the transform space. Further, a Scaling in the Transform Space section is provided in which a theorem that gives a solution to the problem of scaling or resampling in the transform domain is discussed. In addition, with reference to Fig. 6, the constraints, shape and level of a filter h that could be used for smoothing and anti-aliasing performed by resamplers 260-264 will be provided below in separate sections (i.e., Constraints on the Support of the Filter h; The Shape of the Filter h; and, The Level of the Filter h).

1. Notation

C, R, Z, and Z⁺ respectively represent the set of complex numbers, the set of real numbers, the set of integers (positive, negative, and zero), and the set of positive integers. If a e C, then â is its complex conjugate. The ceiling function I -1 : R -+ Z maps a real number to the smallest integer greater than or equal to the given real number. The floor function I ·] : R -+ Z maps a real number to the largest integer less than or equal to the given real. The function [ · ] : R -» Z is the rounding function. For r e R, [r] = I rl if r - I rl &lt;0.5, else [r] = f rl . If a, b e Z, then a|b means that a divides b. If

-2696/08911

PCT/US95/11857 a does not divide b, we write a /b. The highest common factor (hcf) of a, b e Z is written (a,b). For a, b e Z; a &lt; b; [a, b] is the set {a, a + I,...,b - 1, b} of all integers from a to b. Z_N denotes the ring of integers {0,____ N - 1}.

If f is a function from a discrete set U to C, f : u -+ C, then the support of f is defined as that subset of U where f does not vanish: supp(/) = {u e U : f(u) *0}. A bar over f denotes the complex conjugate function / : U -* C such that f (u) = f (u) . For x, y e {f | ft Z_N -» C}, their (circular) convolution will be written as:

x * y; (x * y) (n) = S_meZjx (m)y{n-m) , neZ_N.

The inner product operation in an inner product space H is written as &lt;· , · )_h:H x H -+ C. The norm induced by this inner product is written as || · ||_H : H -+ R. For h e H, Il M ²h ⁼ r h) h ·

2. The Frame Composition Problem (FCP)

If the set B = { $&gt;%: Z_N~C }_IeZn, NeZ*, is an orthogonal basis for C^N, then any vector x= (x(0) ,x(l) , . . . , x(7\T-l) ) eC^N can be written as a weighted sum of vectors in . such a sum is called a decomposition of x over B. The weights in the sum are given by the inner products of x against the various φί, divided by the squared norms of the φ (see, e.g., Chapter 4 in N. Young, An Introduction to

Hilbert Space, Cambridge U. Press, Cambridge, England (1988)). Thus, the decomposition of x over B is written:

-27WO 96/08911

02199477

PCT/US95/11857 where x(n) = £ ^±(r) &lt;j&gt;? (n) , (1)

J?(r) = &lt;x, &lt;t£&gt; = £ χ·(η)φ^(η) (2)

Equation 1 shows the decomposition of x over B. The space C^N that contains the vector x will be called the signal space. The space C^N that contains the vector ft will be called the transform space. The mapping

T : C^N -+ C^N, such that x-*Tx=ft, from the signal space to the transform space is called a transform, and is defined by the choice of the orthogonal basis B. We will say that the vector ft is the image of x under T, and x the pre-image of ft under T.

In the following description, in order to reduce any ambiguity or confusion, some vectors, φχ for example, are given superscripts that declare the dimension of the vector space in which they lie.

Let T : C^N -* C^N be a transform defined by some suitable choice of basis. Let the images Tx_B,Tx_lf... ,Tx_K-1 e C^N of signals x0, . . . , xK_! e C^N be given. Also considered given are three numbers (or parameters) PPL e [-(N -1), (N - 1)], SPi e Z, and 0P_± e Z⁺, for each i e Z_K. The integer PP_± will be called the position parameter of signal Xi,· SPi the size parameter; and OP_± the occlusion parameter.

-28WO 96/08911

PCT/ÜS95/11857

The Frame Composition Problem (FCP) is defined as the problem of calculating the image Ty e C^N of a signal y from the images TXi of signals Xi- The signal y is required to consist of scaled copies of the signals x_iz placed with their left edges at PP_if with extents determined by SPi· If 0P_± &gt; 0P₃, then signal x_± may occlude signal Xj.

A signal is indicated herein as having an indention of one if it consists of a sequence of samples that are thought of as being distributed along a line, such as in the case of a sampled speech waveform. A signal is indicated herein as having an indention of two if it consists of samples thought to be distributed over a plane, as in the case of a digital image. The word indention is new, and the terminology proposed herein is non-standard. Conventionally, the signals called one-indentional and twoindentional herein are said to be one-dimensional and two-dimensional, respectively. The conventional terminology is misleading, or at best ambiguous, because it fails to distinguish between the dimension of the vector space in which a signal lies, ’and the way signal samples are distributed. Thus, the two terms will be kept distinct in the description that follows.

So far the FCP has been stated in the one-indentional form (II—FCP hereinafter) . It is easy to see that the twoindentional analog of the 1I-FCP is the problem of composing frames from transform-coded video flowing into a device that connects a number of video sources to each other, such as in a multipoint video conference system.

One way to solve the FCP is to compute x_± from the given Tx_±; then resample, cut, and paste the in the signal space to generate y; and finally to compute Ty. One implementation of this method is described above with reference to Fig. 2. However, in order to reduce hardware requirements and reduce delay, it would be advantageous if the resampling, cutting, and pasting could be done directly in the transform space.

—29—

CA 02199477 2004-05-12

3. Scaling in the Transform Space

Let x be a signal defined on N points, x e C^N. Let y be a desired representation of x, except that y is required to be defined on E points, y e C^E. E could be larger or smaller than N; i.e., y may be an upscaled or downscaled representation of x. Let M, L e Z⁺ be defined such that E/N=M/L and (M,L)=1.

The resampling circuit in Figure 6, which may be used for each of resamplers 260-264, will deliver a suitable y (see, e.g., Chapter 4 of P.P. Vaidyantathan and Chapter 3 of Oppenheim and Schafer under some restrictions on a filter 268 (i.e., filter h). The output y is sometimes called a fractionallyresampled representation of x. The operation of the circuit in Figure 6 is described below.

The input to the circuit is a signal x e C^N which when unsampled by filter 267 generates u e C^MN. The equation { x (n/M), ΜIn

U(n)={ (3) (0 , M/n' where n e Z_MN, defines the upsampling operation performed by filter 267. The signal u is filtered by filter 268 (i.e., filter h) having an impulse response h e C™ to give V e C^MN, which is in turn downsampled by a filter 269 to obtain y e C^MN/L. The equation y (n) = v (Ln) , (4 ) where n e Z_ZM/L, defines the downsampling operation performed by filter 269. The filter h (i.e., filter 268) may be a low pass filter whose support in the Fourier space is controlled to smooth the result of upsampling by filter 267 and to avoid aliasing due to downsampling by filter 269. The necessary constraints on filter h are discussed in detail in the sections provided below. See, also, e.g., Section 4.1.1 of Vaidyantathan and Section 3.6 of Oppenheim and Schafer, each of which was noted above. These

-3096/08911

PCT7ÜS9Si'H8S7 references discuss constraints on the filter h for input signals in 1²(Z), the Hilbert space of absolutely square summable sequences defined on the entire line of integers.

From Fig. 6 and equations (3) and (4), the following relation may be obtained between the vectors x and y. For ^{n e} t y{n) =u(Ln) =]£_Zloiu(^) ^h(Ln-m) h(Ln-m) .

In transform space video bridging, the signal x is generally not known. Only the image of signal x under some transform is known. In addition, only the image of the output y under some transform is wanted. The following theorem establishes a relationship between the transform space images k and ÿ of x and y. The theorem makes no assumptions concerning any constraints on the filter h (i.e., filter 268) in Fig. 6.

4. A Transform Space Scaling Theorem

Let N,M,L e Z⁺ be fixed. Define E = MN/L e Z⁺. Let BN - (Φ9«ζ„ be an orthonormal basis for C^N, and BE = ^be an orthonormal basis for C^E, Let T_N be the transform defined by B_N, and T_E the transform defined by B_E. Let £=2^,^=2^. Define vector x^_neC^w by

[ψ^(_n+^) ,l| (n+Mp) . [o , LX (n+Mp) ' p&amp;Z_1}.

Define tensor λ e C^NxExMN by λ ( s, r, η) =(φ, Xrn) ; seZ_N, reZ_E, neZ_w.

Define matrix Λ e C^ExN by

A(r,s) =^_Ζιοιλ (s,r,n) h(n) ; reZ_E, seZ_N.

-31WO 96/08911 'men,

02199477

<img file="CA2199477C_D0002.tif" />

ÿ(ï) =5ζΛ^(γ' :reZ_E.

5. Constraints on the Support of the Filter h

The filter h (i.e., filter 268) in Fig. 6 has a dual purpose. It has to be designed to smooth the result of the upsampling operation performed by filter 267, and also to forestall any aliasing that may result from the downsampling performed by filter 269. This section establishes two constraints on the support of the Fourier space image 7h of filter h that are found necessary for the proper operation of the resampling circuit in Fig. 6.

Define the Fourier transform fx e C^N of a signal x e C^Nby the following equation:

(^x) (m) =(x, e~^:,2Km'^,li)_cN

<img file="CA2199477C_D0003.tif" />

for m e Z_N. Now consider the Fourier space image Λι of u € tf® in Fig. 6. For m e Z^, j2iunn

J™ x(n/M) e

<img file="CA2199477C_D0004.tif" />

= (9x)(m mod N).

From the above equation (5) , Zu consists of M copies of £x, evenly spaced along Z^. In order to smooth u, i.e., in order to interpolate u at those points where it does not consist of values inherited from x, all but one (the baseband) copies of &amp;x must be eliminated by a low pass filter - filter h in Fig. 6. Therefore, the Fourier image of filter h must not spill outside of the interval

-3296/08911

02199477

FCTfVS95fli857

[O, U\r/2J] U [2^-2\Mn/2J+1, ACY-l] cZjjp,. That gives us one constraint on the filter h.

Next consider the relationship between the Fourier space images of y and v in Fig. 6. For m e Z_E, (^y) (m) =%_Ziyin) iz,v(Ln) _eJ²^^/E

Ί 7iTmO

<img file="CA2199477C_D0005.tif" />

Define a picket-fence vector Il^eC*®⁷:

Then,

<img file="CA2199477C_D0006.tif" />

<img file="CA2199477C_D0007.tif" />

= (^(^)) (/77) *(^Π7)) (m).

MN j—ll

The Fourier space image of a picket-fence vector is another picket-fence vector. Specifically, where E = MN/L. From the last two above-noted equations, for m e Z_E, the following equation (6) is derived:

(/2/) =A (£J^ * ( JTv) ) (/73) . (6

The above equation (6) has to be interpreted with some care because (JJ^ * (^v) ) eC^w, while Zy e C^E. Further, equation (6) indicates that the Fourier image of y consists of a sum of shifted copies of the Fourier image of v, where the shifting is done along Zmj,. Therefore, aliasing will result, unless the support of £v is constrained. Because supp (^v) = supp (Λι) , a second constraint is inferred on filter h in Fig. 6, that is:

-33CA 02199477 2004-05-12 supp (^h) e [ O, |_J57/2J] [MN-F+LE/2J+1, MN-1 ] εΖ_Μ With this constraint, equation (6) will produce no aliasing. In fact, when this constraint holds, equation (6) can be written as the following equation ( 7 ) :

(^y) (m) = 1 (^v) (m) , (7)

L for m e Z_E.

Combining the two constraints on ^h, the following relation (8) is derived:

supp(^h) &lt;= [O,min{|£/2J, [W/2J} U [MN+l-max{E-|E/2J, W-LN/2J}, MN-1} (8)

6. The Shape of the Filter h

The design of a low-pass finite impulse-response (FIR) filter begins, conventionally, with the specification of filter pass and stop bands in the Fourier space, and with the specification of admissible ripple in these bands. The more stringent these constraints are, the larger is the number of taps needed. The requirements for filter h (i.e., filter 268) of Fig. 6 are a little different from those of classical approach. The support of filter h need not be constrained in the signal space. Instead, hard Fourier-space support constraints that are required by the relation (8) are imposed on filter h.

The simplest filter h that meets the constraints of the relation (8) is a filter with rectangular pulse shape in the Fourier space. With this choice of shape for filter h in the Fourier space, the signal space image of h will decay inversely with distance from the origin. This is so because the Fourier space image is, in some sense, discontinuous. The smoother the Fourier space image of the filter h is, i.e., the larger the number of its derivatives that exist, the faster will h decay in the signal space (see, e.g., pp. 19-20 in A. Kumar, TimeFrequency Analysis and Transform Coding, D.Sc. dissertation,

Dept. Comp. Sc., Wash. U., St. Louis (1990).

-34CA 02199477 2004-05-12

The fast signal-space decay of the filter h is a desirable property, because the numerical value of a pixel will be highly correlated with the numerical values of the pixels in its immediate neighborhood, and not at all with the values of pixels far away. Because there are brick-wall bounds (i.e., rigid boundaries) on the support of the filter h in the Fourier space, the signal space filter h will smear the entire line Z_MN. That cannot be helped, but the decay of the filter h can be controlled.

At least two classes of methods may be used for shaping the filter h. The first class of methods involves modelling ^h as a B-spline in the Fourier space. The cubic B-spline, which will give a fourth-order polynomial decay in the signal space, is the convolution of two triangular waveforms (see, e.g., p. 48 in Y. Meyer, Wavelets: Algorithms and Applications, Soc. for Indust.

&amp; Appl. Math., Philadelphia, PA (1993)). Higher order splines can be built by convolving the cubic spline with rectangular waveforms. Each successive convolution will improve the smoothness of the waveform. Each convolution also enlarges the support of the spline function, but initial supports can easily be chosen such that the final result fits within the interval in the relation (8).

A second class of methods for shaping the filter h involves the iterative calculation of an eigenvector of a certain double projection operator (see, e.g., pp. 1703-1704 in A. Kumar, D. R. Fuhrmann, M. Frazier, and B. Jawerth A New Transform for TimeFrequency Analysis, IEEE Trans. SP, Vol. 40. No. 7, pp. 16971707 (July 1992) and pp. 19-20 in M. Frazier and A. Kumar, An Introduction to the Orthonormal Wavelet Transform on Discrete Sets, pp. 51-95 in Benedetto and Frazier (eds.), Wavelets: Mathematics and Applications, CRC Press, New York (1993). It is also possible to refine the double projection method discussed in those references.

7. The Level of the Filter h

-35WO 96/08911

PCT/US95/11857

The shape of the filter h in the signal and Fourier spaces has then been established. The next issue is how large should the magnitude of h be.

A governing principle is that the average illumination produced by the signal x and that produced by the derived signal y, should be the same, despite the change in their physical dimensions. An image painted on the face of a cathode-ray tube will illuminate a pixel in direct proportion to the appropriate sequence-element of the signal in the signal space. Since the zero'th Fourier coefficient, given the definition of the Fourier transform herein, is the sum of all scalar elements of the signal in the signal space, the governing principle requires the following relation (9):

% (^y) (0) =4 (^X) (0) . (9)

E N

If the vector x represents an image, then it can be assumed that x(i)£0,Vi. This will be so if the black-level is represented by a zero and maximum brightness by the integer 2ⁿ - 1 for some n e Z⁺, as is usually the case. Then (&lt;7x)(0)&gt;0, if the image is not all dark.

From the equation (7), and under the assumption that the relation (8) holds

L(Jy)(0) = (Jv)(0). (10)

Because v is the output of filter h with input u, (^v) (0) = (7h) (0) (Λι) (0) . (11)

From the equation (5), (Zu) (0) = (*x)(0). (12)

From relations (9)-(12) and given the knowledge that (7x) (0) and (^y) (0) are both positive, it is easy to see that:

(£h) (0) = M.

This completes the design of a particular example embodiment of the filter h.

Resamplers 260-264 may be implemented through a matrix multiplication architecture instead of the filter design and resampling circuit of Fig. 6. Referring now to Fig. 7, a more detailed description of the matrix multiplication

-36φί WO 96/08911

PCT/US95/H8S7 that may be performed by resamplers 260-264 will be discussed below.

As noted above, resamplers 260-264 may resize the various frame images in the transform space by performing matrix multiplication of the vectors of each frame with a particular matrix provided from Lambda memory 220. Fig. 7 illustrates a block diagram of a matrix multiplication architecture that may be used to implement resamplers 260264.

As shown in Figure 7, resamplers 260-264 may include a local controller 300, that may, for example, be implemented with a microcontroller for controlling the various components of the resampler based on the control signals received from video system controller 120. The local controller 300 may control the timing of the operations performed by the various components of the resamplers 260-264, including Lambda cache 310, a column register 320, a row register 330, a systolic array 340, an adder 350, and a product register 360.

Lambda cache 310 receives and stores a matrix table A_± transmitted from Lambda memory 220. A suitable cache memory device may be used for Lambda cache 310 for storing such matrices. By providing Lambda cache 310, the Lambda memory 220 may be freed to provide matrix data to the other resamplers without being tied up by any one particular resampler. The matrix A_± stored in Lambda cache 310 may be loaded into row register 330 one row at a time. In addition, the image x_x from switch 150 is loaded into column register 320. If N is a large integer, then column register 320 and row register 330 may be made to hold only short vector segments at a time. In Fig. 7, column register 320 and row register 330 are shown as being each three numbers wide, whereas N is shown to equal 6.

Under the control of local controller 300, column register 320 and row register 330 feed systolic array 340.

The systolic array 340, which is further described below with reference to Fig. 8, has a width that is equal to that of the column register 20 and row register 330. Systolic array 340 calculates the matrix-vector products based on data provided by column register 320 and row register 330.

-37WO 96/08911

2199 47 ⁷

PCT/US95/11857^

If the width of the column and row registers 320 and 330, and of the systolic array 340, is less than N, then an adder 350 may be provided to add partial sums in order to build up the elements of the resized units γ_ά. For this purpose, a product register 360 may be provided so that the partial sums may be added by adder 350. The final output y_± from Fig. 7 is selectively provided to the frame composers 170 by switch 155 (see, for example, Fig. 5).

As shown in Fig. 8, the systolic array 340 may 10 comprise a triangular array of multipliers 370 and adders

372 which store their respective results in a node register 374, so that the result is available for the next set of operations. Node registers 374 may include dynamic shiftregisters (not shown) that run on a two-phase clock (see, 15 for example, pages 100-101 in J. Mavor, M. A. Jack, and P.

B. Denyer, ’’Introduction to MOS LSI Design, AddisonWesley, Reading, MA (1983) or Chapter 3 in C. Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, MA (1980). Because of the speed at which these registers are required to operate, they will not be required to work in a static mode. Instead, once the inputs to the array are primed, the array will produce, at each and every clock cycle, a complete partial sum at the apex of the inverted triangular array of multipliers and adders.

Fig. 8 shows a systolic array of order eight, and how the product of a matrix in C^ExS with a vector in C^s may be computed.

Multipliers 370 in the first row of systolic array 340 30 must be implemented to perform the operations in a fast manner in order to match the speed of the adders in the subsequent rows. The multipliers in Fig. 8 may themselves be implemented as systolic arrays with rows adders, each row handling a single sum in Booth's algorithm. In this case, the numbers in the row register 33 0 and column register 320 must be presented in two's-complement notation. In addition, a single Manchester-carry adder cell may be used to build full-adders or, if the timing of the operation is tight, a carry-lookahead cell, or a combination of Manchester and carry-lookahead cells, could

-38WO 96/08911

PCT/US95/II857 be employed (see, for example, pages 118-124 in the Mavor et al. reference noted above).

As noted above, each of the resamplers (160-164 and 260-264) of the present invention may consist of two one5 dimensional'’ scaling circuits, with one that resizes the rows and another that resizes the columns. Each of the scaling circuits of a given resampler may be placed in tandem, with a frame buffer being provided in series between, before and after the two scaling circuits.

Fig. 9 illustrates in more detail the interconnection between the lookup table (LUT) 121, Lambda memory 220, resampler 260-262, and frame composer 170 illustrated in Fig. 5. As illustrated in Fig. 9, a single frame composer chip 170' may be provided for performing frame composing of frames from each of resamplers chips 401, 402, and 403.

Each resampler chip 401, 402, and 403, may be configured to perform matrix multiplication utilizing the appropriate matrix information input from Lambda-memory 220 and the video image in transform space

As shown in Fig. 9, the resampling-related circuitry is shown to include a multiplexer 410, a lookup table (LUT) 412 (which corresponds to LUT 121 in Fig. 5) , and a Lambdamemory 220, which are connected in a cascaded fashion. An output of Lambda-memory 220 is then connected to a plurality of respective inputs of resampler chips 401, 402, and 403. Each of the illustrated resampler chips 401-403 has an output register 401a, 402a, and 403a, which holds an output value ÿq. Each of the output registers 401a-403a is connected to an input of frame composer chip 170', which also has an output register 170a'. Each of the size parameters SP_± is connected to an input of multiplexer 410. Multiplexer 410 is provided with a selection input sel for selecting between the various size parameters when controlling the video image of one or more of the particular locations at a particular time. The resulting selected size parameter SP_± is then outputted from multiplexer 410 into lookup table 412, which outputs a parameter ΡΛ_± which is then input into Lambda-memory 220 in order to cause a particular matrix to be outputted by

-39WO 96/08911 ggl99 477

PCT/US95/11857

Lambda-memory 220 and input into the respective resampler chips 401-403.

Frame composer chip 170' accepts position parameters PP_± and occlusion parameters OP_± as input, which further define the positioning of image windows to be utilized for each of the resampled video images, (i.e., the amount of occlusion) of each of the image windows.

Several additional or alternative features may be provided in an video teleconferencing system that are compatible with the various embodiments disclosed herein. Such features may include pull-down menus for allowing a user to interface and thus control the video composition and the bridging systems, help menus, multimedia display support, and site-identification icons. In addition, the system may be provided with a bridge reservation system, an accounting and billing system, and party add/drop options. Other features may also be provided such as dial access, audio-only connections, side-conference support, flashing window signalling for signalling that a particular party is currently speaking, and an automatic foregrounding of a current speaker's window.

Using RNS Arithmetic in Galois Fields A Galois field is a finite-field of order qeZ⁺. See,

e.g., Chapter 5 in I.N. Herstein, Topics in Algebra, 2 ed., John Wiley &amp; Sons, New York, 1975; Chapters 2 and 5 in R.E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley, Reading, Mass., 1985; and W.K. Jenkins, Finite Arithmetic Concepts, pp. 611-675 in Mitra and Kaiser (eds.), Handbook for Digital Signal Processing, John Wiley &amp; Sons, New York, 1993. A Galois field with q elements is written as GF(q) . If q is a prime number, then 3ge GF(q) such that the (q-1) integer powers g¹, g², ..., g^q' ¹ of g equal every number in GF(q) but zero. The number g is called a generator because it generates, in the stated sense, every number in GF(q) but zero. For q prime, when a generator exists, multiplication and division in GF(q) are very easy and very fast. They can be accomplished through the addition of the integers that are the generator-indices of the operands. This is just like multiplication and division using logarithms. Zeros and

-40WO 96/08911

PCTfUS9Sai8S7 multiplications by zeros must be handled as exceptions, with a special flag bit. Thus, in the above-described embodiments (e.g., in the architecture in Fig. 8), where a number of additions and divisions must be performed very quickly, arithmetic in a Galois field is an attractive alternative.

On the down side, data must be embedded in a Galois field before arithmetic can be performed, and the size of the Galois field must be large enough to accommodate the desired precision of calculation. The embedding of data in a field also produces a new source of noise, quite akin to finite-word-length and quantization noise. Once the embedding is done, however, all ensuing arithmetic is error-free, and is not subject to any round-off or finiteword length effects.

Whenever arithmetic operations are performed in any finite field or ring, greater computational efficiency can be gained through the use of residue arithmetic using a set of relatively-prime moduli. Arithmetic operations are performed on residues relative to the given moduli, and the results can be stitched back together using a theorem called the Chinese Remainder Theorem (CRT), See, e.g., pp. 55-61 in R.E. Blahut, Fast Algorithms for Digital Signal Processing, Addison-Wesley, Reading, Mass., 1985; and p. 617 in W.K. Jenkins, Finite Arithmetic Concepts, pp. 6Ï1675 in Mitra and Kaiser (eds.), Handbook for Digital Signal Processing, John Wiley &amp; Sons, New York, 1993. This method of computation is called residue number system (RNS) arithmetic, and can sometimes yield extremely efficient machine architectures.

Galois field and residue arithmetic methods may be used when the frame-composing computational burden is too large to be handled in real-time by more usual arithmetic, as might happen, for example, if the composer or bridge is used for HDTV images. Galois fields and RNS arithmetic may also be considered for use in less onerous applications like bridging H.261 streams.

With respect to timing and delay, in order to have maximum-rate operation, American National Standards Institute document ANSI Tl.314-1991 (Digital Processing of

-41WO 96/08911

PCT/US95/11857 φΐ

Video Signals-Video Coder/Decoder for Audio Visual Services at 56-1536 kbit/s, ANSI, New York (1991)) requires the processing of 30 CIS images per second. In a case that is most computationally stressful, a CIF frame would be resized from 352 x 288 to 344 x 280. For the Y (luminance) component, this means 352 x 344 + 288 x 280 &lt; 202,000 multiplications per second for the rescaling operation. The Cr, Cb color-difference components will together need half as many multiplications per frame, bringing the total to 303,000 multiplications per frame = 303,000 x 30 * 9.1 million multiplications per second. This translates to (9.1)^_1 x l0’⁶s - 110 ns per multiplication.

The multipliers can be fixed-point devices. The incoming Rq are arrays of 4 digit numbers in the range -2048 to 2047. The entries in the resampling matrix Λ can be rounded to about 6 digits without adding any noise that could be of magnitude comparable to the inevitable quantization noise introduced by modified Huffman or arithmetic coding. Commercial state-of-the-art fixed-point multiplier-accumulators can work at 50 ns per operation, for bipolar devices, while unipolar MOS devices are available for 100 ns operation. One multiply-accumulator chip per incoming connection and per outgoing connection per bridge, operated under microcontroller control, can be used to do the resizing, as an alternative to the systolic array illustrated in Fig. 8. The systolic array will be useful in still higher-speed operation, e.g., in bridging high-definition video.

The delays in both the systolic array and the commercial multiplier-accumulator approaches will be less than four frame-intervals = 4 x 1/30 = 133 ns, as evident from the frame buffer requirements referred to above for a two-indentional transform space video bridge.

The various embodiments of the video signal composition and bridging system disclosed herein may be utilized in several different manners. An example operation of the same will now be described. Referring to Fig. 1, each of user locations A, B, and C may be located at different parts of the country, e.g., Los Angeles, California; New York, New York; and Washington, D.C.,

-42φίνο 96/08911

PCT/ÜS9S/H8S7 respectively, and the system may be provided in a video teleconferencing system. When user A in Los Angeles is speaking with users B and C in New York and Washington, D.C., respectively, user A may control, by use of an appropriate input device 14 at its terminal equipment 10, the manner in which each of the image windows of each of the respective participants in the video teleconference is displayed. For example, as shown in Fig. 3, user A may specify the relative depth of each image window A, B, and io c (which show participants A, B, and C, respectively) by specifying a Z_± (occlusion parameter) accordingly, and may specify the position of each of the windows A, B, C, by specifying position parameters Χ_1Λ Υ_χ. In addition, participant A may specify the size of each of the image windows by specifying a scaling factor s_±. As noted previously, the particular types of parameters and interpretation of the values assigned to those parameters (used to control the position of the image windows, the amount of occlusion (i.e., relative depth) and the size/scaling factor of each of the image windows), may be varied without substantially detracting from the benefits associated with the video signal composition and bridging system disclosed herein.

Each participant of a video teleconference, including participants A, B, C, and any other participants participating in the teleconference, may specify each of these parameters at its associated terminal equipment 10, in order to define the manner in which he or she may view the images of each of the other participants (and his or

0 her self) . A user interface may be provided, which utilizes input device 14, for allowing the user to choose among various parameter values to control the manner in which the various image windows are placed on the screen 12. Such parameters may be specified by the participant/user before the video teleconference is set up, may be initially set to default values, which will remain set unless changed by the user, and/or may be changed by the user while the video teleconference is going on.

The video signal composition and bridging control system disclosed herein allows user/participants at each of

-43WO 96/089110 2 1 9 9 4 7 7

PCT/ÜS95/11857 φ the respective locations to be able to modify these display configuration parameters, and thus to control the manner in which the image of each participant can be viewed at each respective location/terminal equipment. Thus, each display screen at each location/terminal equipment can be set so that it displays the image windows in a different manner.

Different video teleconferencing sites may receive and transmit images with different aspect ratios. The standard aspect, ratio is 4:3, while the aspect ratio for HDTV is 16:9. The illustrated embodiments of the video signal composition and bridging system disclosed herein will allow a video teleconferencing site having one specific aspect ratio (e.g., 4:3) to be interfaced with another video teleconferencing site. For example, the video signal composition and bridging control system disclosed herein can be used to allow video teleconferencing traffic to be transferred between two different kinds of site installations in a V-Chan video teleconferencing system (developed by Southwestern Bell). The V-Chan network carries SBC video teleconferencing traffic, and may have at least two different kinds of sites, including VW (Video Window) sites and ordinary 4:3 aspect ratio sites. VW sites use the same DS1 codecs that are used by 4:3 sites, except that the input video is deliberately distorted through the use of an anamorphic lens on the camera. This lens exaggerates the horizontal field of view in order to capture a picture that has a 16:9 aspect ratio. So far as the codec is concerned, it treats the captured image exactly as it would a 4:3 image conforming to the NTSC standard. At the receiving end, the VW projector is adjusted to overscan horizontally, so that the displayed image recaptures its 16:9 aspect ratio.

The VW sites (and other HDTV aspect-ratio sites) and 4:3 sites will not interoperate. The cross-bridging system disclosed herein is capable of cross-bridging such varying aspect-ratio sites. Within the specific context of a VChan system, a VW site may be configured to identify itself as a VW site to the cross-bridging control system, e.g., by transmitting a prearranged code word to the cross-bridging control system. Once that is done, the cross-bridging

-44Ο 96/08911

PCTOJS95f 11857 control system will know that it should expect a scrunched image from that site (having a higher aspectratio) , and that it should in turn transmit such high aspect-ratio images to that site. The horizontal and vertical resampling rates may be appropriately adjusted to a certain aspect-ratio, depending upon the site that a particular video image is originating from and the site to which the video image is being transmitted. This flexibility, i.e., the ability to cross-bridge between sites having different aspect ratios is possible because of several particular features provided in the cross-bridging system disclosed herein, including, among other things, the use of digital filters to perform the resampling. It is noted that resampling by rational factors is necessary in order for the video signal composition and bridging control system to cross-bridge VW and 4:3 sites. Resampling by integer factors alone will not suffice.

Accordingly, two advantages of the present invention are the ability for each user/participant at each separate location to control the manner in which the various image windows (which illustrate or show the various participants of the video teleconference) are displayed on its particular display screen, and further the ability to cross-bridge video information between sites having different video formats and/or different aspect ratios, (e.g., sites having a 4:3 aspect ratio may be interfaced or cross-bridged with sites having an HDTV aspect ratio, i.e., a 16:9 aspect ratio).

The composition and bridging unit described herein may also connect remote sites that use different kinds of codecs, and that transmit/receive at different rates, and can do so without dropping quality to the lowest common denominator.

While the invention has been described with reference to several exemplary embodiments, it is understood that the words which have been used herein are words of description and illustration, rather than words of limitation. Changes may be made, within the purview of the appended claims, without departing from the scope and spirit of the invention and its aspects.

-4502199 477

PCT/US95/11857

Although the invention has been described herein with reference to particular means, materials and embodiments, the invention is not intended to be limited to the particulars disclosed herein; rather, the invention extends to all functionally equivalent structures, methods and uses, such as, within the scope of the appended claims. For example, modifications may be made to the specific circuits illustrated herein without detracting from the desired overall functionality of the system, by, e.g., providing only one channel decoder and separator instead of separate channel decoders and separators 110 as illustrated in Figs. 2 and 5. Further, other compression and transform methods may be used instead of operations that are based on the BDCT discussed above. For example, transform methods based on Differential Pulse Code Modulation (DPCM), Vector

Quantization (VQ), or Wavelets may be utilized.