ACCELERATING BITMAP REMOTING BY IDENTIFYING AND EXTRACTING 2D PATTERNS FROM SOURCE BITMAPS

• US 20140254926A1
• Filed: 05/23/2014
• Published: 09/11/2014
• Est. Priority Date: 12/11/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Abdo, Nadim Y., Albu, Voicu Anton, Zitnick, Charles Lawrence III
• Granted Patent: US 9,280,722 B2
• Time in Patent Office: Days
• US Class Current: 382/165
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Systems, methods and computer-readable storage media are disclosed for accelerating bitmap remoting by extracting non-grid tiles from source bitmaps. A server takes a source image, identifies possibly repetitive features, and tiles the image. For each tile that contains part of a possibly repetitive feature, the server replaces that part with the dominant color of the tile. The system then sends to a client a combination of new tiles and features, and indications to tiles and features that the client has previously received and stored, along with an indication of how to recreate the image based on the tiles and features.

Claims

1. A method, comprising:

identifying a boundary for a feature of an image, the feature corresponding to at least one tile of a tiling scheme for the image;

storing the feature in a cache when the feature is not already stored in the cache;

tiling the image according to the tiling scheme to produce at least one tile;

for each tile corresponding to the feature, replacing a portion of the tile occupied by the feature with a replacement image for the tile; and

storing each tile in the cache that is not already stored in the cache.

2. The method of claim 1, further comprising:

determining, based on the cache, whether a communications device has each tile, and the feature;

sending each tile and the feature that the communications device does not have across a communications network to the computing device for display; and

sending an indication of each tile and the feature that the communications device does have across the communications network to the computing device for display.

3. The method of claim 2, wherein determining, based on the cache, whether a communications device has the feature comprises:

determining that the communications device has the feature when caching the feature causes a cache hit of the cache; and

a cached feature of the cache represents the same image as the feature.

4. The method of claim 2, wherein identifying a boundary for a feature of an image is based on a feature granularity and is performed by a host communications device, and wherein the feature granularity is determined by a characteristic of the host communications device, the communications device, or the communications network.

5. The method of claim 2, further comprising compressing at least one tile or the feature before sending the tile or the feature to the communications device.

6. The method of claim 1, wherein identifying a boundary for a feature of an image further comprises:

producing a black-and-white representation of the image.

7. The method of claim 6, wherein producing a black-and-white representation of the image comprises:

processing the image according to a thresholding scheme.

8. The method of claim 1, wherein identifying a boundary for a feature comprises:

processing the image with a connected segments algorithm.

9. The method of claim 1, wherein the feature is already stored in the cache, further comprising:

identifying a second boundary for a second feature of the image;

determining that the second feature is not already stored in the cache;

producing a compound feature comprising the feature and the second feature; and

sending the compound feature across a communications network to a communications device, with an indication of how the feature and the second feature are stored within the compound feature.

10. The method of claim 1, wherein the feature comprises text, and identifying a boundary for the feature comprises:

processing the image with an optical character recognition (OCR) algorithm.

11. The method of claim 1, wherein the feature comprises a line, and identifying a boundary for the feature comprises:

identifying as the feature a plurality of linear pixels of a substantially similar color.

12. The method of claim 1, wherein the feature comprises a motion between the image and a prior image, and identifying a boundary for the feature comprises:

processing the image to determine a motion vector of a portion of the image relative to a portion of the prior image.

13. The method of claim 1, wherein a replacement image for a tile comprises a dominant color of the tile.

14. The method of claim 1, wherein identifying a boundary for a feature of an image is based on a feature granularity.

15. The method of claim 1, further comprising:

identifying a second boundary for a second feature of the image;

determining that the feature and the second feature represent the same image;

sending the feature across a communications network to a communications device; and

sending an indication that the second feature corresponds to the feature across the communications network to the communications device.

16-19. -19. (canceled)

20. A computer-readable storage medium bearing computer-readable instructions that, when executed by a computing device, cause the computing device to perform operations comprising:

identifying a boundary for a feature of an image, the feature corresponding to at least one tile of a tiling scheme for the image;

storing the feature in a cache when the feature is not already stored in the cache;

tiling the image according to the tiling scheme to produce at least one tile;

for each tile corresponding to the feature, replacing a portion of the tile occupied by the feature with an image for the tile to produce tiles;

storing each tile in the cache that is not already stored in the cache;

determining, based on the cache, whether a second computing device has each tile, and the feature;

sending each tile and the feature that the second computing device does not have across a communications network to the computing device for display; and

sending an indication of each tile and the feature that the communications device does have across the communications network to the computing device for display.

21. A computer system comprising a processor communicatively coupled to a computer-readable storage device, wherein the computer-readable storage device stores instructions that when executed on the processor cause the system to:

identify a boundary for a feature of an image, the feature corresponding to at least one tile of a tiling scheme for the image;

store the feature in a cache when the feature is not already stored in the cache;

tile the image according to the tiling scheme to produce at least one tile;

for each tile corresponding to the feature, replace a portion of the tile occupied by the feature with a replacement image for the tile; and

store each tile in the cache that is not already stored in the cache.

22. The system of claim 21, further comprising instructions to cause the system to:

determine, based on the cache, whether a communications device has each tile, and the feature;

send each tile and the feature that the communications device does not have across a communications network to the computing device for display; and

send an indication of each tile and the feature that the communications device does have across the communications network to the computing device for display.

23. The system of claim 22, wherein the determine operation comprises:

determine that the communications device has the feature when caching the feature causes a cache hit of the cache and a cached feature of the cache represents the same image as the feature.

24. The method of claim 22, wherein the identify operation is based on a feature granularity and is performed by a host communications device, and wherein the feature granularity is determined by a characteristic of the host communications device, the communications device, or the communications network.