# Patent

## Title
Method and system for progressive image transmission

## Abstract

A method and system for transmitting an image progressively is provided. The transmission system identifies a first region and a second region of the image. The transmission system also identifies a first resolution and a second resolution. The transmission system then transmits the image by transmitting, in the following order, the first region in the first resolution, the second region in the first resolution, the first region in the second resolution, and the second region in the second resolution. The transmission system may identify the regions based on the likelihood of being the focus of user attention.

## Background
TECHNICAL FIELD
The described technology relates generally to image transmission and particularly to progressive image transmission.
BACKGROUND
It can take a considerable amount of time to download and display an image using a low-speed connection such as a telephone line or a cellular phone connection. For example, it can take 60 seconds to transmit an 800-by-600 pixel image with 24 bits per pixel over a standard telephone line. This transmission time presents problems because users typically expect an image to be transmitted and displayed within 10 seconds. If the image is not displayed within that time, then users may become dissatisfied with the delay and even abort the transmission.
Progressive image transmission (“PIT”) techniques have been used to help overcome this long delay before a user can view an image. PIT techniques start by transmitting the image in low resolution followed by increasingly higher resolutions. Since the image in low resolution can be transmitted much faster than in high resolution, the image can be displayed to the user more quickly, albeit in a lower resolution. A user can abort transmission of the image in high resolution based on viewing the image in low resolution because it may be not of interest, rather than having to wait until the image in high resolution is displayed.
With such progressive image transmission techniques, however, users still need to wait until the entire image in low resolution is transmitted and displayed before a decision can be made as to whether the image is of interest. Some progressive image transmission techniques attempt to identify important areas of an image and transmit those important areas before transmitting less important areas. Such techniques typically use a minimal distortion principle to identify areas of high distortion and transmit those areas first. Relying on the minimal distortion principle, however, does not necessarily provide the best viewing experience when an image is transmitted progressively. The importance based on the minimal distortion principle does not correspond very well to what people perceive as important. In addition, since people perceive only part of an image to be important, the minimal distortion principle may be applied to unimportant parts.
It would be desirable to have a progressive image transmission technique that would automatically identify areas of an image that people would perceive as important and base progressive image transmission on that importance.
SUMMARY
A method and system for transmitting an image progressively is provided. The transmission system identifies a first region and a second region of the image. The transmission system also identifies a first resolution and a second resolution. The transmission system transmits the image by transmitting, in the following order, the first region in the first resolution, the second region in the first resolution, the first region in the second resolution, and the second region in the second resolution. The transmission system may identify the regions based on the likelihood of being the focus of user attention.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates an image with attention objects identified in one embodiment.
FIG. 2 illustrates a prior art progressive image transmission technique.
FIG. 3 illustrates the progressive image transmission technique of the transmission system in one embodiment.
FIG. 4 is a block diagram illustrating components of the transmission system in one embodiment.
FIG. 5 is a flow diagram that illustrates the processing of the transmit image component in one embodiment.
FIG. 6 is a flow diagram that illustrates the processing of the extract region of interest component in one embodiment.
FIG. 7 is a flow diagram that illustrates the processing of the transmit image using most appropriate resolution and region of interest component in one embodiment.
FIG. 8 is a flow diagram that illustrates the processing of the transmit region of interest component in one embodiment.
FIG. 9 is a flow diagram that illustrates the processing of the transmit background component in one embodiment.



DETAILED DESCRIPTION
A method and system for transmitting an image progressively is provided. In one embodiment, the transmission system identifies a first and second region of the image. For example, the first region may correspond to an area of the image that a person would perceive as important or of interest (e.g., a face), and the second region may correspond to an area of the image that a person would perceive as less important (e.g., the background). The transmission system also identifies a first resolution and a higher second resolution. The transmission system then transmits the image by first transmitting the first region in the first resolution followed by the second region in the first resolution. The transmission system then transmits the first region in the second resolution followed by the second region in the second resolution. When the image is displayed, a user first sees the region of interest in low resolution followed by the background in low resolution. In the following, the term “background” refers to the area of the image other than the region of interest. After viewing the region of interest in low resolution, the user may have enough information to decide whether to continue with the transmission. If the user continues with the transmission, then after viewing the background in low resolution, the user may have enough information to decide whether to continue with the transmission. After viewing the region of interest in high resolution, the user can again decide whether to continue with the transmission. In this way, a user first views the region of interest in low resolution followed by the overall image in low resolution. The user can thus decide at various times, based on the areas of the image that have been displayed so far, whether to continue with the transmission.
In one embodiment, the transmission system identifies the region of interest by applying an attention model to the image. The attention model identifies objects, referred to as attention objects, within the image that users are expected to focus their attention on and that thus are important objects. For example, a user may be expected to focus their attention on a face or text within an image. The transmission system calculates an attention value for each attention object, which indicates a likelihood that a user will focus their attention on that object. The attention objects may be identified by a rectangular area or some other shaped area. In one embodiment, the transmission system may apply the attention model to an image as defined in Chen L. Q., Xie X., et al., “A Visual Attention Model for Adapting Images on Small Displays,” ACM Multimedia System Journal, vol. 9, no. 4, pp. 353-364, 2003, or U.S. patent application Ser. No. 10/286,053, titled “SYSTEMS AND METHODS FOR GENERATING A COMPREHENSIVE USER ATTENTION MODEL,” filed on Nov. 1, 2002, which is hereby incorporated by reference. After identifying the attention objects, the transmission system then selects those attention objects with a high attention value to compose the region of interest. The transmission system may select the attention objects to ensure that the total region of interest is not too large and the number of attention objects within the region of interest is not too great. For example, the transmission system may ensure that the total region of interest is less than a certain percentage (e.g., 25%) of the total image and that the number of attention objects within the region of interest is less than an experimentally derived number such as six. If the region of interest is too large, it may take too long to transmit even in a low resolution. If the region of interest has too many attention objects, then the user may not be able to focus effectively on the most important attention objects. The region of interest may comprise overlapping and disconnected attention objects. In one embodiment, the transmission system may use a region of interest bitmap mask to identify the region of interest.
In one embodiment, the transmission system identifies the most appropriate resolution (“MAR”) for display of an image, which corresponds to the final resolution of the progressive image transmission. The most appropriate resolution of an image is related to its size and presentation context. A large image can have a most appropriate resolution that is lower than its actual resolution and may be even lower if the image is to be displayed as part of a web page. The transmission system may calculate the most appropriate resolution using the following equation:

MAR=max(H−max([(log2(1/K)],0),0)  (1)

where H is the maximum resolution and K is a zoom ratio for the display of the image. For example, if the possible resolutions are 800 (H=4), 400 (H=3), 200 (H=2), and 100 (H=1) pixels per inch and the zoom ratio is 0.5, then the most appropriate would be 400 (i.e., H=3 or 4−log2 2). In such a case, the transmission system transmits an image progressively in resolutions 100, 200, and 400. The transmission system determines the order of transmission for the region of interest and background in the various resolutions. For example, the transmission system may transmit, in the following order, the region of interest in resolutions 100 and 200, the background in resolutions 100 and 200, the region of interest in resolution 400, and the background in resolution 400. Alternatively, the transmission system may transmit, in the following order, the region of interest in resolution 100, the background in resolution 100, the region of interest in resolutions 200 and 400, and the background in resolutions 200 and 400. Alternatively, the transmission system may transmit, in the following order, the region of interest in resolution 100, the background in resolution 100, the region of interest in resolution 200, the background in resolution 200, the region of interest in resolution 400, and the background in resolution 400. In one embodiment, the transmission system transmits, in the following order, the region of interest in all resolutions lower than the most appropriate resolution, the background in all resolutions lower than the most appropriate resolution, the region of interest in the most appropriate resolution, and the background in the most appropriate resolution.

FIG. 1 illustrates an image with attention objects identified in one embodiment. An image 100 includes a person sitting on a statue of a horse with a date stamp on the image. The attention objects 101, 102, and 103 correspond to the face of the person, the body of the person, and the date stamp, respectively. These three attention objects compose the region of interest of the image. The rest of the image is considered to be background.
FIG. 2 illustrates a prior art progressive image transmission technique. In this example, the important area has been defined using a prior art technique, such as one based on minimal distortion. The prior art progressive image transmission technique transmits the important area in each of the resolutions before transmitting any of the not important area. In this example, rectangles 201, 202, and 203 correspond to the important area in resolutions 100, 200, and 400, respectively. Rectangles 204, 205, and 206 correspond to the not important area in resolutions 100, 200, and 400, respectively. The prior art progressive image transmission technique transmits the image, in the following order, important area 201 in resolution 100, important area 202 in resolution 200, important area 203 in resolution 400, not important area 204 in resolution 100, not important area 205 in resolution 200, and not important area 206 in resolution 400. A user thus views the important area in the highest resolution before viewing any of the not important area.
FIG. 3 illustrates the progressive image transmission technique of the transmission system in one embodiment. In this example, the transmission system has identified the region of interest and background using the attention model. Rectangles 301, 302, and 305 correspond to the region of interest in resolutions 100, 200, and 400, respectively. Rectangles 303, 304, and 306 correspond to the background in resolutions 100, 200, and 400, respectively. The transmission system transmits, in the following order, the region of interest 301 in resolution 100, the region of interest 302 in resolution 200, the background 303 in resolution 100, the background 304 in resolution 200, the region of interest 305 in resolution 400, and the background 306 in resolution 400. Thus, the user views the region of interest in resolution 200 before viewing any background, and views the background in resolution 200 before viewing the region of interest in resolution 400. The transmission system may also use variations of this ordering. For example, the transmission system may transmit, in the following order, the region of interest in resolution 100, the region of interest in resolution 200, the background in resolution 100, the region of interest in resolution 400, the background in resolution 200, and the background in resolution 400. Thus, the transmission system may interleave the transmitting of the region of interest and the background in different resolutions.
FIG. 4 is a block diagram illustrating components of the transmission system in one embodiment. The transmission system may execute on a server computer system 410 that is connected to client computer systems 420 via a communication link 430. The transmission system includes a transmit image component 411 that invokes an identify attention objects component 412, an extract region of interest component 413, a calculate most appropriate resolution component 414, and a transmit image using most appropriate resolution and region of interest component 415. The identify attention objects component processes the image to identify attention objects as rectangular areas where user attention is likely to be focused and calculates an attention value for each attention object. The extract region of interest component selects the attention objects with the highest attention values as the region of interest. The calculate most appropriate resolution component determines the appropriate final resolution for the image based on the highest possible resolution and viewing context (e.g., zoom ratio) of the image. The transmit image using most appropriate resolution and region of interest component progressively transmits the image by transmitting the background in a low resolution before transmitting the region of interest in the final resolution. The transmission system transmits images via the communication link to the client computer systems.
The computing device on which the transmission system is implemented may include a central processing unit, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), and storage devices (e.g., disk drives). The memory and storage devices are computer-readable media that may contain instructions that implement the transmission system. In addition, the data structures and message structures may be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communication links may be used, such as the Internet, a local area network, a wide area network, a point-to-point dial-up connection, cell phone network, and so on.
The transmission system may be implemented in various operating environments that include personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, digital cameras, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and so on. The client computer systems may be cell phones, personal digital assistants, smart phones, personal computers, programmable consumer electronics, digital cameras, and so on.
The transmission system may be described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, and so on that perform particular tasks or implement particular abstract data types. Typically, the functionality of the program modules may be combined or distributed as desired in various embodiments.
FIG. 5 is a flow diagram that illustrates the processing of the transmit image component in one embodiment. The component is passed an image and transmits it to a client computer system. In block 501, the component invokes the identify attention objects component to identify the attention objects of the image and their attention values. In block 502, the component invokes the extract region of interest component passing the attention objects and their attention values to identify the attention objects that compose the region of interest. In block 503, the component calculates the most appropriate resolution for the image using, for example, Equation 1. In block 504, the component invokes the transmit image using most appropriate resolution and region of interest component to transmit the image from the server computer system to the client computer systems.
FIG. 6 is a flow diagram that illustrates the processing of the extract region of interest component in one embodiment. The component sorts the attention objects by their attention values. The component then loops selecting the attention objects in attention value order until the attention objects would be too many or the region of interest would be too large. In block 601, the component sorts the attention objects by attention values. In block 602, the component selects the next attention object in attention value order. In decision block 603, if the number of attention objects that have been selected would be too great, then the component returns, else the component continues at block 604. In decision block 604, if the area of the selected attention objects would be too large for a region of interest, then the component returns, else the component continues at block 605. In block 605, the component marks the selected attention object as being part of the region of interest and increments the number of attention objects that have been selected. In block 606, the component increases the size of the region of interest by the size of the selected attention object. The component then loops to block 602 to select the next attention object. The component returns the marked attention objects as the region of interest.
FIG. 7 is a flow diagram that illustrates the processing of the transmit image using most appropriate resolution and region of interest component in one embodiment. The component is passed the most appropriate resolution and the image with the region of interest identified (e.g., using a bitmap mask). The component transmits the image in two phases in this embodiment. A phase is delimited by the region of interest and background having been transmitted in the same resolution. In phase 1, the component transmits the region of interest and the background in resolutions lower than or equal to a phase 1 resolution. In phase 2, the component transmits the region of interest and the background in resolutions greater than the phase 1 resolution. In block 701, the component invokes a transmit region of interest component passing an indication of the lowest resolution and the phase 1 resolution, which may be one or two resolutions less than the most appropriate resolution (e.g., MAR-c). In block 702, the component invokes a transmit background component passing an indication of the lowest resolution and the phase 1 resolution. In block 703, the component invokes the transmit region of interest component passing an indication of the resolution next larger than the phase 1 resolution and the most appropriate resolution. In block 704, the component invokes the transmit background component passing an indication of the resolution next larger than the phase 1 resolution and the most appropriate resolution. The component then returns. The transmission system may transmit images in more than two phases. Each phase would have a start resolution and an end resolution. The transmission system may transmit within each phase the region of interest in each resolution before the background or may interleave their transmissions in various resolutions as desired.
FIG. 8 is a flow diagram that illustrates the processing of the transmit region of interest component in one embodiment. The component is passed a start resolution and an end resolution. The component transmits the region of interest in each of the resolutions in the range of the start resolution to the end resolution. In block 801, the component selects the next resolution starting with the start resolution. In decision block 802, if all the resolutions have already been selected, then the component returns, else the component continues at block 803. In block 803, the component transmits the region of interest in the selected resolution and loops to block 801 to select the next resolution.
FIG. 9 is a flow diagram that illustrates the processing of the transmit background component in one embodiment. The component is passed a start resolution and an end resolution. The component transmits the background in each of the resolutions in the range of the start resolution to the end resolution. In block 901, the component selects the next resolution starting with the start resolution. In decision block 902, if all the resolutions have already been selected, then the component returns, else the component continues at block 903. In block 903, the component transmits the background in the selected resolution and loops to block 901 to select the next resolution.
From the foregoing, it will be appreciated that specific embodiments of the invention have been described herein for purposes of illustration, but that various modifications may be made without deviating from the spirit and scope of the invention. Accordingly, the invention is not limited except as by the appended claims.

## Claims

1. A method in a device for transmitting an image, the method comprising:
identifying a first region and a second region of the image;
identifying by the device a first resolution and a second resolution, the second resolution is a most appropriate resolution that is identified by calculating the most appropriate resolution for the image according to the following:


MAR =max (H−max([(log2(1/K)],0),0)

where MAR is the most appropriate resolution, H is a maximum resolution, and K is a zoom ratio for display of the image; and

transmitting the image by transmitting, in the following order, the first region in the first resolution, the second region in the first resolution, the first region in the second resolution, and the second region in the second resolution for progressive display of the image.

2. The method of claim 1 wherein the first region is a region of interest and the second region is background.

3. The method of claim 2 wherein the identifying of the region of interest includes identifying attention objects.

4. The method of claim 2 wherein the region of interest is limited to a certain fraction of the size of the image.

5. The method of claim 4 wherein the fraction is 25 percent.

6. The method of claim 1 including identifying a final resolution that is the second resolution.

7. The method of claim 6 wherein the final resolution is a most appropriate resolution.

8. The method of claim 7 wherein the first region is a region of interest and the second region is background.

9. The method of claim 8 wherein the identifying of the region of interest includes identifying attention objects.

10. The method of claim 7 wherein the most appropriate resolution is identified based on the zoom at which the image is to be displayed.

11. A computer-readable storage medium containing instructions for controlling a computer system to display an image, by a method comprising:
receiving a transmission of the image, in the following order, a first region of the image in a first plurality of resolutions, a second region of the image in the first plurality of resolutions, the first region in a second resolution, and the second region in the second resolution, the second resolution being a most appropriate resolution calculated for the image according to the following:


MAR =max (H−max([(log2(1/K)],0),0)

where MAR is the most appropriate resolution, H is a maximum resolution, and K is a zoom ratio for display of the image; and

displaying the regions of the image in the resolutions in the order received
wherein a user viewing the displayed regions of the image can direct the stopping of the transmission when the user deems the display of the regions of the image to be of sufficient resolution.

12. The computer-readable medium of claim 11 wherein the first region is a region of interest and the second region is background.

13. The computer-readable medium of claim 12 wherein the region of interest includes attention objects.

14. The computer-readable medium of claim 13 wherein the region of interest comprises attention objects with high attention values.

15. The computer-readable medium of claim 11 wherein the second resolution is an appropriate resolution.

16. A computing device for transmitting an image, the device comprising:
a processor;
a memory;
a component that identifies a plurality of regions of interest of the image;
a component that calculates a most appropriate resolution for the image according to the following:


MAR =max (H−max([(log2(1/K)],0),0)

where MAR is the most appropriate resolution, H is a maximum resolution, and K is a zoom ratio for display of the image;

a component that transmits, in the following order, the regions of interest in a first resolution, the regions of interest in a second resolution, a region other than a region of interest in the first resolution, the region other than a region of interest in the second resolution, the regions of interest in the most appropriate resolution, and the region other than a region of interest in the most appropriate resolution; and
a component that receives an indication that a user wants to stop the transmission of the image and that controls the component that transmits to stop transmission before transmission of the image in the most appropriate resolution is complete.

17. The computing device of claim 16 wherein the component that identifies regions of interest identifies regions of interest that are limited to a certain number of attention objects.

18. The computer system computing device of claim 16 wherein the component that identifies regions of interest limits the regions of interest to a certain fraction of the size of the image.

19. The computing device of claim 16 wherein the transmission of the image is stopped before the region other than a region of interest is transmitted in the first resolution.