(12) United States Patent
`Li et al.
`
`USOO6345279B1
`(10) Patent No.:
`US 6,345,279 B1
`(45) Date of Patent:
`Feb. 5, 2002
`
`(54)
`
`(73)
`
`ASSignee:
`
`METHODS AND APPARATUS FOR
`ADAPTING MULTIMEDIA CONTENT FOR
`CLIENT DEVICES
`(75) Inventors: Chung-Sheng Li, Ossining, NY (US);
`Rakesh Mohan, Stamford, CT (US);
`John R. Smith, New Hyde Park, NY
`(US)
`International Business Machines
`Corporation, Armonk, NY (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`Notice:
`
`(21)
`(22)
`(51)
`(52)
`
`(58)
`
`(56)
`
`Appl. No.: 09/298,576
`Filed:
`Apr. 23, 1999
`Int. Cl................................................. G06F 17/30
`U.S. Cl. ............................... 707/104; 707/3; 707/5;
`707/10; 707/501; 707/514; 709/224; 709/231;
`709/217
`Field of Search ............................ 707/103, 3, 102,
`707/10, 513, 104, 5,501, 203, 514; 709/224,
`203, 217, 226, 231, 232, 227, 246, 235;
`370/252; 713/201
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,636.216 A
`5,646,982 A
`5,712.907 A *
`5,724,355 A
`5.999.525 A
`
`* 6/1997
`7/1997
`:
`1/1998
`3/1998
`12/1999
`
`:
`
`:
`
`ROX et al. ................... 370/402
`Hogan et al. ................. 379/89
`Wegner et al. ....
`... 379/112
`Bruno et al. ................ 370/401
`Krishnaswamy et al. ... 370/352
`
`
`
`
`
`320
`
`CAPABILITIES
`
`330
`
`FILER WERSIONS ON CAPABILITIES
`
`OTHER PUBLICATIONS
`U.S. application No. 09/413,515, Liet al., filed Oct. 6, 1999.
`R. Mohan et al., “Adapting Multimedia Internet Content for
`Universal Access.” IEEE Transactions on Multimedia, vol.
`1, No. 1, pp. 1-35, Mar. 1999.
`R. Mohan et al., “Multimedia Content Customization for
`Universal Access,” SPIE East-Multimedia Storage and
`Archiving Systems III, Boston, MA, 9 pages, Nov. 1998.
`J.R. Smith et al., “Content-based Transcoding of Images in
`the Internet,” IEEE Inter. Conf. on Image Processing
`(ICIP-98), Chicago, IL, 5 pages, Oct. 1998.
`(List continued on next page.)
`Primary Examiner Jean M. Corrielus
`(74) Attorney, Agent, or Firm-Ryan, Mason & Lewis,
`LLP, Robert P. Tassinari, Jr.
`(57)
`ABSTRACT
`A method of adapting multimedia content to a client device,
`wherein the multimedia content includes one or more items
`and the client device has capabilities and resources associ
`ated therewith, is provided. The method includes transcod
`ing the multimedia content into a plurality of transcoded
`content versions, wherein the plurality of transcoded content
`versions have different modalities and resolutions associated
`therewith. Next, the transcoded content versions that are not
`compatible with client device capabilities are filtered out.
`Then, at least a portion of the resources associated with the
`client device are allocated among the one or more items of
`the multimedia content. Lastly, one or more of the
`transcoded versions of the multimedia content are Selected
`to generate a customized content based on allocation of the
`client device resources.
`
`31 Claims, 5 Drawing Sheets
`
`420
`
`450
`
`470
`
`RESOURCES
`
`ALOCATE CLIENT RESOURCES
`BETWEEN CONTENT ITEMS
`
`
`
`O- is H
`
`SELECT VERSIONS
`
`CUSTOMIZED DOCUMENT
`
`574
`
`VIDEOLABS, INC.
`EX2007
`NETFLIX, INC. v. VIDEOLABS, INC.
`IPR2023-00628
`
`

`

`US 6,345,279 B1
`Page 2
`
`OTHER PUBLICATIONS
`J.R. Smith et al., “Transcoding Internet Content for Hetero
`geneous Client Devices.” Proc. IEEE Inter. Symp. on Cir
`cuits and Syst. (ISCAS), Special Session on Next Genera
`tion Internet, 4 pages, May 1998.
`C-S. Li et al., “Multimedia Content Description in the
`InfoPyramid,” Proc. ICASP'98, Special Session on Signal
`Processing in Modern Multimedia Standards, Seattle, WA, 4
`pages, May 1998.
`S. Paek et al., “Detecting Image Purpose in World Wide Web
`Documents, Symp. on Electronic Imaging: Science and
`Technology-Document Recognition, San Jose, CA, 8
`pages, Jan. 1998.
`T.W. Bickmore et al., “Digestor: Device-independent
`Access to the World Wide Web,” Proc. of the 6th Interna
`tional WWW Conference, pp. 1-10, 1997.
`
`G.C. Vanderheiden, “Anywhere, Anytime (+Anyone)
`Access to the Next Generation WWW,” Proc. of the Sixth
`Int’l WWW Conference, pp. 1-11, 1997.
`A. Ortega et al., “Soft Caching: Web Cache Management
`Techniques for Images.” IEEE Signal Processing Society
`1997 Workshop on Multimedia Signal Processing, Princ
`eton, NJ, pp. 1-8, Jun. 1997.
`A. Fox et al., “Reducing WWW Latency and Bandwidth
`Requirements by Real-time Distillation,” Proc. of the 5th
`International WWW Conference, 12 pages, 1996.
`A. Fox et al., “Adapting to Network and Client Variability
`Via On-demand Dynamic Distillation,” ASPLOS-VII,
`Cambridge, MA, pp. 1-11, Oct. 1996.
`
`* cited by examiner
`
`

`

`U.S. Patent
`
`Feb. 5, 2002
`
`Sheet 1 of 5
`
`US 6,345,279 B1
`
`FIC. 1
`
`100
`
`MULTIMEDIA DOCUMENT W
`
`CONTENT ITEM A
`
`120
`
`CONTENT
`ITE
`A.
`
`CONTENT
`ITE
`A.
`
`CONTENT
`ITE
`A.
`
`CONTENT ITEM A
`
`120
`
`FIC. 2
`
`
`
`CONTENT ITEM A
`
`120
`
`TRANSCODE
`
`/N
`... // N'-
`// AN
`
`
`
`

`

`U.S. Patent
`FIG. 3
`
`Feb. 5, 2002
`
`Sheet 2 of 5
`
`US 6,345,279 B1
`
`N
`
`100 - MULTIMEDIADOCUMENT W
`
`CONTENT
`ITE
`A
`
`CONTENT
`ITEM
`Al
`
`CONTENT
`ITEM
`Ai
`
`TRANSCODE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`250
`
`340
`
`
`
`350
`
`
`
`370
`
`310
`CLIENT PROFILE
`CAPABILITIES / 320
`
`RESOURCES - 330
`
`

`

`U.S. Patent
`
`Feb. 5, 2002
`
`Sheet 3 of 5
`
`US 6,345,279 B1
`
`FIC. 4
`550
`
`540
`
`280
`
`280
`
`320
`CAPABILITIES
`330
`
`RESOURCES
`
`FILTER VERSIONS ON CAPABILITIES / 20
`
`ALLOCATE CLIENT RESOURCES
`BETWEEN CONTENT ITEMS
`
`SELECT VERSIONS
`
`450
`
`470
`
`370
`
`
`
`CUSTOMIZED DOCUMENT
`
`

`

`U.S. Patent
`
`Feb. 5, 2002
`
`Sheet 4 of 5
`
`US 6,345,279 B1
`
`FIG. 5
`?t
`ASSIGN PRIORITIES TO EACH
`CONTENT ITEM
`
`
`
`
`
`
`
`
`
`ASSIGN WALUES TO EACH WERSION
`
`
`
`
`
`ALLOCATE RESOURCES BY MAXIMIZING
`PRIORITIZED WALUE GIVEN
`RESOURCE CONSTRAINTS
`
`SELECT VERSIONS BASED ON
`ALLOCATED RESOURCES
`
`520
`
`540
`
`560
`
`470
`
`FIG. 6
`470
`
`
`
`ALLOCATE CLIENT RESOURCES BETWEEN
`CONTENT ITEMS
`
`450
`
`
`
`640
`
`
`
`680
`
`
`
`
`
`
`
`FROM EACH INFOPYRAMID, SELECT THE
`VERSION THAT USES RESOURCES CLOSEST
`TO THOSE ALLOCATED BY (450).
`
`ORDER THE ITEMS (120) IN ORDER OF
`DECREASING PRIORITIZED WALUES, STARTING
`FROM THE ITEM WITH THE HIGHEST
`PRIORITIZED WALUE, WHILE THERE ARE ANY
`RESOURCES LEFT, SELECT FROM THE
`INFOPYRAMID OF EACH ITEM THE WERSION
`WITH THE NEXT HIGHER WALUE.
`
`
`
`CUSTOMIZED DOCUMENT
`
`370
`
`

`

`U.S. Patent
`
`Feb. 5, 2002
`
`Sheet 5 of 5
`
`US 6,345,279 B1
`
`FIG. 7
`SERVER-SIDE
`
`NETWORK
`705
`
`FIG. 8
`
`
`
`820
`
`PROCESSOR
`
`810
`
`I/O DEVICE(S)- 830
`
`FIG. 9
`
`SLOPEX
`
`O
`
`WALUE
`
`NoPIA.
`
`RESOURCE
`
`

`

`US 6,345,279 B1
`
`1
`METHODS AND APPARATUS FOR
`ADAPTING MULTIMEDIA CONTENT FOR
`CLIENT DEVICES
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`The present application is related to U.S. patent applica
`tion Ser. No. 09/413,515, entitled: “Method and Apparatus
`For Transcoding Multimedia Using Content Analysis,' filed
`in the names of Li et al. on Oct. 6, 1999, which claims
`priority to U.S. provisional patent application Ser. No.
`60/103,303, entitled: “Method and Apparatus For Transcod
`ing Multimedia Using Content Analysis, filed in the names
`of Li et al. On Oct. 6, 1998.
`
`15
`
`FIELD OF THE INVENTION
`The present invention relates to delivery of multimedia
`content to client devices and, more particularly, to methods
`and apparatus for adapting Such multimedia content for
`diverse client devices.
`
`BACKGROUND OF THE INVENTION
`
`2
`June 1997: Intel Quick Web accessible on the Internet at
`http://www.intel.com/quickweb, Spyglass Prism accessible
`on the Internet at http://www.Spyglass.com/products/prism;
`A. Fox and E. A. Brewer, “Reducing WWW Latency and
`Bandwidth Requirements by Real-time Distillation.” In
`Proc. Of the 5th International WWW Conference, 1996; and
`T. W. Bickmore and B. N. Schilit, “Digestor: Device
`independent Access to the World WideWeb,” In Proc. Of the
`6th International WWW Conference, 1997. The proxy
`distills, or transcodes, the content from the Web server. This
`transcoding is primarily limited to the compression of
`images, or a reduction of their size or color Space. These
`Systems do not consider transcoding into different modali
`ties. The image compression and Size reduction policies are
`Static and do not dynamically account for resources on the
`client.
`
`SUMMARY OF THE INVENTION
`The present invention adapts multimedia content, e.g.,
`Web documents, to optimally match the capabilities of the
`client device requesting it. Each Web document is a set of
`items, each of which is authored in a particular modality
`Such as text or image. Each of these content items is then
`transcoded into multiple resolution and modality versions So
`that they can be rendered on different devices. For example,
`a Video item is transcoded into a Selected Set of images. So
`that it can be rendered on a device not capable of displaying
`Video. Each version of a content item requires different
`resources from the client device. The invention ensures that
`the resource requirements for the entire document, as given
`by the Sum of the resource requirements of its constituent
`items, can be met by the requesting client. The invention
`allocates the resources on the client among the items in the
`document. This resource allocation results in the Selection of
`appropriate resolution or modality of the content items. If
`the client has limited resources, e.g., Such as a PDA or pager,
`Some of the content items may not get any resources
`assigned and thus not be delivered to the client.
`In an embodiment of the invention, as will be explained,
`three technologies are employed to provide Such multimedia
`content adaptation: (i) a progressive data representation
`scheme referred to as the InfoPyramid as described in C-S.
`Li, R. Mohan and J. R. Smith, “Multimedia Content
`Description in the InfoPyramid.” Proc. ICASP98, Special
`Session on Signal Processing in Modern Multimedia
`Standards, Seattle, Wash., May 1998, the disclosure of
`which is incorporated herein by reference; (ii) a set of
`transcoding modules for converting modality or resolution;
`and (iii) an adaptation process that Selects the best repre
`Sentation to meet the client capabilities while delivering the
`most value to the client.
`The present invention provides many advantages over
`prior Solutions. For example, content is dynamically adapted
`to the client device allowing a wider variety of multimedia
`content and of client devices to be properly Supported. Also,
`in accordance with the invention, a content author has
`control over the adaptation process. The content author can
`edit and replace the transcoded versions of content items
`generated by the automated transcoding Systems. This con
`trol of the customization overcomes problems of publisher
`control and copyright issues faced by transcoding proxies.
`Further, the invention permits content to be authored in
`XML (Extensible Markup Language, as is known in the art),
`allowing the author to provide more information to the
`transcoding and adaptation Systems than can be deduced
`from an HTML (hyper text markup language) page. One
`
`25
`
`Web documents delivered on the Internet are multimedia
`presentations that may include Video, images, graphics, text
`and audio. Due to the recent rapid growth of devices that are
`connected to the Internet, there is a growing demand for
`providing universal access to Such multimedia content to a
`wide variety of devices over a wide range of network
`environments. For example, personal computers on a local
`area network (LAN), personal digital assistants (PDAS) on
`dial-up modems and Smart cellular phones have drastically
`different client resources in terms of, for example, Screen
`size, resolution, color depth, network bandwidth and com
`35
`puting power. Internet users also vary in their ability to pay
`for Internet Services and in the time they are ready to wait
`for a page to download. Therefore, to provide universal
`access to the Internet, multimedia delivery methods need to
`account for the composite nature of Web documents, and the
`variety of client platform capabilities, user interests, network
`constraints and authoring policies.
`In this context, Video-conferencing Systems have been
`proposed that adjust the bandwidth available to the client by
`Selecting a Suitable compression factor or codec. In these
`Systems, only a single type of multimedia item (namely
`Video) is considered. Also, clients that can not handle video
`are not considered.
`One option for content adaptation is to manually develop
`multiple versions of multimedia content, each Suitable for a
`class of client devices. Given the variety of client devices, it
`is difficult for content publishers to anticipate and accom
`modate the wide spectrum of client capabilities. For com
`posite multimedia documents, Such as Web pages, a number
`of Systems have been proposed that employ a proxy between
`the Web server and the client. For example, various proxy
`approaches are described in: J. R. Smith, R. Mohan, and
`C-S. Li, “Transcoding Internet Content for Heterogeneous
`Client Devices.” In Proc. IEEE Inter. Symp. on Circuits and
`Syst. (ISCAS), Special Session on Next Generation Internet,
`June 1998; A. Fox, S.D. Gribble, E. A. Brewer, and E. Amir,
`“Adapting to Network and Client Variability Via
`On-demand Dynamic Distillation,” In ASPLOS-VII,
`Cambridge, Mass., October 1996; A. Ortega, F. Carignano,
`S. Ayer, and M. Vetterli, “Soft Caching: Web Cache Man
`65
`agement Techniques for Images,” In IEEE Workshop on
`Multimedia Signal Processing, pg. 475-480, Princeton, N.J.,
`
`40
`
`45
`
`50
`
`55
`
`60
`
`

`

`US 6,345,279 B1
`
`3
`benefit of the server-based system of the invention is that
`due to the guidance provided by the author, a significantly
`greater level of customization can be performed than is
`possible in previous transcoding proxies. Still further, the
`invention permits the transcoded versions of the content
`items to be generated prior to any requests. Thus, the
`invention can handle media items. Such as Video and audio
`which are difficult to handle in conventional proxies. This
`off-line transcoding also leads to lower response latencies
`than proxies. Also, the Server shares the benefit of transcod
`ing proxies in Speeding content delivery as the customized
`content is often much Smaller than the original content.
`These and other objects, features and advantages of the
`present invention will become apparent from the following
`detailed description of illustrative embodiments thereof,
`which is to be read in connection with the accompanying
`drawings.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a diagram illustrating an example of a multi
`media document;
`FIG. 2 is a diagram illustrating transcoding a content item
`into an InfoPyramid;
`FIG. 3 is a flow chart illustrating a method of adapting a
`document to a client device according to an exemplary
`embodiment of the invention;
`FIG. 4 is a flow chart illustrating an adaptation proceSS
`according to an exemplary embodiment of the invention;
`FIG. 5 is a flow chart illustrating a method of obtaining an
`adaptation proceSS according to an exemplary embodiment
`of the invention;
`FIG. 6 is a flow chart illustrating a method of selecting
`versions of content items for a customized document accord
`ing to an exemplary embodiment of the invention;
`FIG. 7 is a block diagram illustrating deployment of an
`adaptation process in the Internet according to an exemplary
`embodiment of the invention;
`FIG. 8 is a block diagram illustrating an exemplary
`hardware architecture of a Server or computing device for
`implementing the invention; and
`FIG. 9 is a graphical representation illustrating a resource
`allocation technique according to an exemplary embodiment
`of the invention.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`It is to be appreciated that the term “processor as used
`herein is intended to include any processing device, Such as,
`for example, one that includes a CPU (central processing
`unit). The term “memory” as used herein is intended to
`include memory associated with a processor or CPU, Such
`as, for example, RAM, ROM, a fixed memory device (e.g.,
`hard drive), a removable memory device (e.g., diskette), etc.
`In addition, the term “input/output devices” or “I/O devices”
`as used herein is intended to include, for example, one or
`more input devices, e.g., keyboard, for making requests for
`multimedia content and inputting data to the processing unit,
`and/or one or more output devices, e.g., CRT display and/or
`printer, for presenting requested multimedia content and
`providing results associated with the processing unit. It is
`also to be understood that various elements associated with
`a processor may be shared by other processors. Accordingly,
`Software components including instructions or code for
`performing the methodologies of the invention, as described
`herein, may be stored in one or more of the associated
`
`4
`memory devices (e.g., ROM, fixed or removable memory)
`and, when ready to be utilized, loaded in part or in whole
`(e.g., into RAM) and executed by a CPU.
`Referring to FIG. 1, an example of a multimedia docu
`ment is shown. As is well known, a Web user (client) makes
`a request from his client device for some particular Web
`document(s) or other multimedia content which may contain
`Video, images, graphics, text, audio. The request is Sent to a
`Web server which satisfies the request by returning the
`requested document to the client. AS shown, a multimedia
`document W, denoted as reference numeral 100, is com
`posed of a number of content items A, denoted as reference
`numeral 120, where i=1, 2, ..., n. Thus, the multimedia
`document may be represented as W={A}. Each content item
`A, can be an atomic unit of media Such as, for example, an
`image. A content item A can also be composed of other
`items. For example, a document can have a number of
`Stories as content items, and each Story item may be com
`posed of image items, text items, etc.
`Referring to FIG. 2, a diagram illustrating an example of
`transcoding a content item into an InfoPyramid according to
`the invention is shown. Particularly, a content item 120 is
`transcoded, in process 250, into an InfoPyramid 280. For
`each original content item A, an InfoPyramid represented as
`M.-M}j=0, m, is computed by transcoding A, into j
`versions with different resolutions and modalities. The origi
`nal version is denoted as Mo-A. A null version, which
`corresponds to an item being deleted from the delivered
`content, is denoted as:
`(1)
`M=(p.
`The transcoding process 250 can convert the input modal
`ity associated with the content item to a new modality Such
`as, for example, text to audio, or audio to text. Alternatively,
`the transcoding process can Summarize, compress, or elabo
`rate on the content within the given modality of the input
`data Such as, for example, by image compression or text
`Summarization. Further, it is to be appreciated that transcod
`ing processes may alternatively be performed in accordance
`with the techniques described in U.S. patent application Ser.
`No. 09/413,515, entitled: “Method and Apparatus For
`Transcoding Multimedia Using Content Analysis,” filed in
`the names of Li et al. on Oct. 6, 1999, which claims priority
`to U.S. provisional patent application Ser. No. 60/103,303,
`entitled: “Method and Apparatus For Transcoding Multime
`dia Using Content Analysis, filed in the names of Li et al.
`on Oct. 6, 1998, the disclosure of which is incorporated
`herein by reference.
`The InfoPyramid 280 can be viewed as a generalization of
`multi-resolution representations, e.g., Gaussian image
`pyramids, to multimedia. The InfoPyramid provides a multi
`modal, multi-resolution representation hierarchy for
`multimedia, for example, as described in the above
`referenced C-S. Li, R. Mohan and J. R. Smith, “Multimedia
`Content Description in the InfoPyramid.” Proc. ICASP'98,
`Special Session on Signal Processing in Modem Multimedia
`Standards, Seattle, Wash., May 1998. The InfoPyramid 280
`is a data structure in which the multiple representations of a
`multimedia item can be organized into a pyramid-like
`structure, as illustrated in FIG. 2. The cells of the pyramid
`correspond to different representations of the objects using
`different modalities Such as, for example, Video 281, image
`282, audio 283 and text 284, and fidelities Such as in the
`range of full-resolution (bottom of pyramid) to low
`resolution (top of pyramid). A specific version of a multi
`media item can be referred to by one of the cells. The
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`US 6,345,279 B1
`
`15
`
`25
`
`S
`InfoPyramid may include procedures and rules for translat
`ing and Summarizing (transcoding) between modalities and
`resolutions. The InfoPyramid may also contain meta-data
`for each constituent version Such as, for example, size, color,
`bandwidth requirements, publisher preferences, etc.
`The transcoding process 250 populates the InfoPyramid
`280 structure with multi-resolution, multi-modal versions of
`the content item, as explained herein. The transcoding
`process 250 can be performed on a version by following the
`transcoding paths in FIG. 2, for example, as denoted by
`reference numerals 285 through 290. By following the
`horizontal paths, e.g., paths 285 and 286, a version can be
`translated to another version in a new modality. For
`example, text can be converted to audio in path 286.
`Similarly, video can be converted to images in path 285. By
`following the vertical paths, e.g., paths 287, 288, 289 and
`290, a version can be changed into versions at different
`fidelities. For example, text passages can be Summarized in
`path 288, video can be compressed in path 287 and/or
`images can be compressed in path 289. Furthermore, the
`image can be compressed to a greater degree in path 290.
`Such transcoding processes can be done in a "lazy' fashion,
`i.e., the actual transcoding need not be performed, but rather,
`only a place holder for the transcoded version can be created
`and the meta-data filled in. The actual version is generated
`only if required.
`Some exemplary transcoding processes 250 are listed
`below by modality of the version and the conversions
`performed to generate versions at different resolutions and
`modalities:
`(i) images
`resolution-Spatial size reduction, color depth reduction,
`lossy/lossless compression
`modality-related text, embedded text, Semantic labels;
`(ii) video
`resolution-Spatial and temporal resolution, lossy/
`lossleSS compression
`modality-key-frame images, audio track, closed caption;
`(iii) text
`resolution-key-terms, text Summarization, document
`headings
`modality-Speech Synthesis, language translation;
`(iv) audio
`resolution-bit-rate reduction, Sampling rate change, Ste
`reO to mono
`modality-Speech recognition.
`That is, Such known transcoding operations are capable of
`transcoding multimedia content in a variety of ways. Some
`illustrative examples of the exemplary conversions men
`50
`tioned above include: (i) compressing data with or without
`information loss; (ii) reducing the size or resolution of the
`data Such as by Spatial reduction; (iii) reducing the color
`content of the data Such as reducing the number of colors,
`(iv) Summarizing content Such as text passages and video
`Sequences, (v) reducing or expanding the amount of data or
`altering the fidelity of the information; (vi) translating the
`data to different modalities Such as text to speech, Video to
`images, and speech to text; (vii) translating text to a different
`language Such as English to Japanese; and (viii) removing,
`Substituting, blocking, emphasizing or de-emphasizing indi
`vidual multimedia objects, modal elements, or other content.
`Referring to FIG. 3, a flow chart of a method 300 of
`adapting a multimedia document 100 to a client device
`according to the invention is shown. A client device is
`characterized by a client profile 310. As shown in FIG. 2, the
`content items 120 of a multimedia document 100 are
`
`6
`transcoded (250) into multiple modality and fidelity versions
`to generate a set 340 of InfoPyramids 280.
`A client device is characterized by its profile 310 which
`lists the capabilities 320 and resources 330 of the device.
`The types of client devices that can access the Internet are
`rapidly expanding beyond the typical WorkStation on a LAN
`for which most multimedia Internet content is authored.
`A client may have a different number of capabilities 320
`and resources 330. It is to be appreciated that the term
`“capability” is the ability for a client device to handle a
`particular media type. Examples of capabilities that may be
`Specified include: (i) screen color; (ii) audio capability; (iii)
`Video capability; (iv) image display capability, (v) Software
`Such as Video decompression; and (vi) hardware Such as a
`Sound card, to name a few. So, by Specifying the capabilities
`that a client device has, it is implied that capabilities not
`Specified do not exist on the client device. For example, a
`handheld personal computer (HPC) may not be capable of
`displaying Video and a PDA may not be capable of display
`ing color imageS. The “resources' of a client can be divided
`up among Several items on a Web page. Examples of
`resources are: (i) Screen size including width, height and
`area; (ii) bandwidth, for example, network bandwidth; (iii)
`memory and other client storage capacity; (iv) wait time
`(including preferred and limits) as determined by the prod
`uct of the bandwidth and the time a client is ready, Willing
`or able to wait to receive the complete document, (v)
`payment ability (including preferred and limits), that is,
`money client is ready, willing or able to pay for the
`document, to name a few.
`The client device profile can be obtained by a number of
`mechanisms. For example, the User-Agent fields in the
`HTTP(hyper text transport protocol) request header contain
`information about the browser and often the operating
`System. Also, Windows-CE devices Specify the Screen size,
`color depth and processor. Standardization efforts are under
`way to allow these request fields to contain more informa
`tion about the client device. Further, many sites require users
`to log-in or place cookies at the user location allowing client
`capabilities to be retrieved from stored profiles. The client
`may also specify their capabilities explicitly, for example,
`through forms or applets.
`A content adaptation process 350 uses the client profile
`310 to select from among the InfoPyramids 280 the versions
`374 that best satisfy the particular client profile. These
`Selected versions are rendered into a document 370 which is
`an adaptation (i.e., customization) of the original multimedia
`document 100. The client device receives the customized
`document 370.
`Referring to FIG. 4, a flow chart illustrating an adaptation
`process 350 according to the invention is shown. First, in
`step 420, the versions from the InfoPyramids 280 that do not
`meet client capabilities 320 are filtered out. For example, all
`versions that are in video modality can be filtered out if the
`device is not capable of displaying Video. Similarly, all
`versions that are color images can be filtered out for a device
`that has only a black and white or gray-level Screen.
`Next, in step 450, the client resources are allocated
`between the InfoPyramids 280 and the content items. The
`resources can be allocated by using any allocation resource
`policy. For example, the resources can be distributed in
`proportion to the resources used by the original versions. A
`method for allocating resources may be based on
`optimization, as will be explained in the context of FIG. 5.
`Then in step 470, the resources allocated for each InfoPy
`ramid are used to Select the appropriate version 374, which
`has not been previously filtered out in step 420, to render the
`customized multimedia document 370.
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`

`

`US 6,345,279 B1
`
`8
`
`7
`Referring to FIG. 5, a flow chart illustrating a method 450
`of allocating client resources using optimization according
`to the invention is shown. First, in step 520, each content
`item is assigned a priority. The author of the Web document
`may have a mental priority ordering of the items in the
`document. The priorities may be assigned by the author of
`the page. Many Internet applications, Such as Search
`engines, customized news Sites, etc., generate documents
`dynamically in response to a user request. In these
`applications, there is often a priority implicitly assigned to
`the items. For example, in image Search engines, the match
`Scores of the returned imageS Serve as priorities. Priorities
`can be assigned based on match Scores for various dynami
`cally generated pages. For classes of multimedia documents,
`priorities can be assigned on attributes of content items. For
`example, titles can be given a higher priority than headings
`which can be given a higher priority than paragraphs.
`Content analysis or heuristics give hints to Semantics or
`purpose of various content items. Such content analysis, for
`example, is described in S Paek and J. R. Smith, “Detecting
`Image Purpose in World Wide Web Documents.” In Symp.
`On Electronic Imaging: Science and Technology
`Document Recognition, San Jose, Calif., January 1998, the
`disclosure of which is incorporated herein by reference,
`while heuristics are, for example, described in J. R. Smith,
`R. Mohan and C-S. Li, “Content-based Transcoding of
`Images in the Internet,” In IEEE Inter. Conf. On Image
`Processing (ICIP-98), Chicago, Ill., October 1998, the dis
`closure of which is incorporated herein by reference. For
`example, one can categorize imageS as pictures, graphics,
`advertisements, etc. These categories can be used to assign
`priorities. Also, priority may be assigned to items based on
`Subjective or objective importance. In any case, let P be the
`priority assigned to item i.
`Next, in step 540, each version of a content item in an
`InfoPyramid is assigned a value. A value is a Subjective
`measure of fidelity and may be represented as:
`
`1O
`
`15
`
`25
`
`35
`
`(2)
`
`40
`
`(3)
`
`3X i {). v} such that 2. R. s. Relient
`
`(5)
`
`where Ve{V(M)} and Re{R (M)} are the values and the
`resources used by the i' item M. of the multimedia docu
`ment. While V, and R are discrete, we will first consider
`them to be continuous, and then deal with the discrete case.
`R
`is the maximum resource available at the client.
`Let the value V, be Some function of the resource R, i.e.,
`V=f(R). We convert the above constrained optimization
`problem (equation (5)) to an unconstrained optimization
`problem by considering the Lagrangian optimization tech
`nique described in R. Fletcher, “Practical Methods of
`Optimization,” John Wiley & Sons, 1987. Using the
`Lagrangian technique, equation (5) may be expressed as:
`
`L(R., A) = {). V. tle. X. R} with > 0.
`
`i
`
`(6)
`
`Then, if Ro is an optimal Solution to equation (5), there exists
`a
`such that VL(R,0)=0. Thus, the candidate solutions for
`the maximum are given by:
`
`8L
`L
`R a R.
`
`L
`L
`= . . . - = ... -- = 0
`8 R.
`8.
`
`(7)
`
`Given that the items and their values are independent of each
`other, we get:
`
`0L df (R)
`d R. - .
`a R,
`
`(8)
`
`Therefore, the candidate Solutions to equation (5) are given
`by:
`
`df (R) df (R) df (R).
`
`(9)
`
`First we consider analytic functions. Content value, as an
`alternative distortion, makes it possible for authors or users
`to Specify value judgements about various transcoded Ver
`Sions of the content. However, manually assigning the
`values is not a practical proposition in most Scenarios. To
`mitigate this problem, we introduce functional mappings
`between content value and resource utilization.
`Let us assume a function f, V=f(V). Note that f, and
`therefore, the Solution, is dependent on the choice of units
`for R. If f is concave, equation (9) gives us the optimal
`Solution. We will first however consider the case when f is
`not concave followed by the case when it is concave.
`Non-concave case: We will limit the discussion to the case
`when f is either linear or convex. Let us assume that the
`value of an item is linearly proportional to the resource that
`it utilizes, i.e., V=c.R. From the definition of V we have that
`f(R)=0 when item i is absent from the delivered document,
`i.e., R=0 and f(R)=1 for the original version of item i, i.e.,
`R=R". Thus:
`
`1
`
`(10)
`
`We term c. to be the resource utilization factor RUF because
`it measures how well the item i utilizes its resources to
`
`perceived value of transc