# US 7,609,271 B2 · Producing animated scenes from still images

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,609,271 B2
- Document ID: US7609271B2
- Status: Granted
- Kind: B2
- Application number: 11/428,195
- Filed: 2006-06-30
- Published: 2008-01-03
- Granted: 2009-10-27
- Earliest claimed: 2006-06-30
- Assignees: Microsoft Corporation
- Inventors: Zhouchen Lin; Lifeng Wang; Yunbo Wang; Jian Wang; Xiaoou Tang
- Web page: https://patentgrep.com/patent/US7609271B2

## CPC

- G06T 13/80: Two-dimensional [2D] animation, e.g. using sprites
- G09G 5/00: Control arrangements or circuits for visual indicators common to cathode-ray tube indicators and other visual indicators (image data processing or generation, in general G06T)
- G09G 2340/0414: Vertical resolution change
- G09G 2340/0421: Horizontal resolution change
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G09G: ARRANGEMENTS OR CIRCUITS FOR CONTROL OF INDICATING DEVICES USING STATIC MEANS TO PRESENT VARIABLE INFORMATION (arrangements for transferring data between digital computers and displays G06F3/14; static indicating arrangements comprising an association of a number of separate sources or light control cells G09F9/00; static indicating arrangements comprising integral associations of a number of light sources H01J, H01K, H10H, H05B33/12; scanning, transmission or reproduction of documents or the like, e.g. facsimile transmission, details thereof H04N1/00)

## Abstract

A strategy is described for producing an animated scene from multiple high resolution still images. The strategy involves: creating a graph based on an analysis of similarity among the plural still images; performing partial temporal order recovery to define a partial ordering among the plural still images; and extracting an output sequence from the plural still images using second-order Markov Chain analysis, using the partial ordering as a reference. The strategy can perform the above-described analysis with respect to multiple independent animated regions (IARs) within the still images. Further, the strategy can decompose any IAR with a significant amount of motion into multiple semi-independent animated regions (SIARs). The SIARs are defined to be weakly interdependent.

## Claims

### Claim 1

A computer-implemented method for producing an animated scene on a display device from plural still images, the method comprising:
receiving, by a computer including a processing unit executing an animation module, plural still images that are produced with an image capturing device at respective capture times;
decomposing, by the computer, a scene represented by the plural still images into one or more independent animated regions (IARs), wherein each of the one or more IARs comprise a portion of the scene and not the entire scene;
identifying, by the computer, an IAR having a level of motion above a defined threshold;
decomposing, by the computer, the identified IAR into plural semi-independent animated regions (SIARs), wherein the SIARs are defined to be interdependent;
with respect to each IAR, producing, by the computer, an animated scene by synthesizing the plural still images, wherein the synthesizing involves reordering the plural still images, thereby producing separate animated scene results for each respective IAR; and
storing, by the computer, the separate animated scene results in memory of the computer.

### Claim 2 (depends on 1)

The method of claim 1, wherein the image capturing device is a digital camera.

### Claim 3 (depends on 1)

The method of claim 1, wherein the producing of the animated scene with respect to each IAR comprises:
creating, by the computer, a graph based on an analysis of similarity among the plural still images;
performing, by the computer, partial temporal order recovery to define a partial ordering among the plural still images; and
extracting, by the computer, an output sequence from the plural still images, using the partial ordering as a reference.

### Claim 4 (depends on 3)

The method of claim 3, wherein the creating of the graph comprises using a Euclidian (L2) distance measure to assess similarity among images.

### Claim 5 (depends on 3)

The method of claim 3, wherein the creating of the graph comprises removing paths in the graph having a similarity measure beyond a defined threshold.

### Claim 6 (depends on 3)

The method of claim 3, wherein the performing of the partial temporal order recovery comprises finding extremal paths in the graph, wherein an extremal path links a node under consideration to a node which is farthest from the node under consideration.

### Claim 7 (depends on 6)

The method of claim 6, wherein the finding of the extremal paths further comprises deleting any extremal paths that are subsets of one or more other extremal paths.

### Claim 8 (depends on 3)

The method of claim 3, wherein the extracting of the output sequence comprises sampling the graph using second-order Markov Chain analysis.

### Claim 9 (depends on 1)

The method of claim 1, wherein the producing of the animated scene comprises combining and blending the separate animated scene results to produce the animated scene.

### Claim 10 (depends on 1)

The method of claim 1, further comprising defining, by the computer, at least one motion parameter for at least one IAR that governs behavior of the IAR in the animated scene.

### Claim 11 (depends on 1)

One or more computer readable storage devices containing machine-executable instructions, the instructions when executed by the computer, configuring the computer to perform the method of claim 1.

### Claim 12

An apparatus comprising:
a processing unit;
memory including an animation module, the animation module executable by the processing unit to:
receive plural still images that are produced by an image capturing device at respective capture times;
produce an animated scene by synthesizing the plural still images, wherein the synthesizing involves reordering the plural still images, wherein the producing the animated scene comprises:
creating a graph based on an analysis of similarity among the plural still images;
performing partial temporal order recovery to define a partial ordering among the plural still images by finding extremal paths in the graph, wherein an extremal path links a node under consideration to a node which is farthest from the node under consideration;
extracting an output sequence from the plural still images using the partial ordering as a reference; and
store the output sequence in the memory.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the producing of the animated scene comprises combining and blending the separate animated scene results to produce the animated scene.

### Claim 14

A computer-implemented method for producing an animated scene from plural still images, comprising:
providing plural still images that are produced at respective capture times using a digital camera;
decomposing a scene represented by the plural still images into a plurality of independent animated regions (IARs);
creating a graph based on an analysis of similarity among the plural still images;
performing partial temporal order recovery after creating the graph, wherein the partial temporal order recovery defines a partial ordering among the plural still images;
extracting an output sequence from the plural still images, using the partial ordering as a reference, wherein:
the creating, performing, and extracting are separately performed by a processing device with respect to the plurality of IARs,
an IAR that has a level of motion above a defined threshold is further decomposed into plural interdependent semi-independent animated regions (SIARs), wherein the creating, performing, and extracting are independently performed with respect to at least a first SIAR, while the creating, performing, and extracting of other SIARs are performed based on the dynamics of a respective reference SIAR as a constraint; and
storing the output sequence in a device memory.

### Claim 15 (depends on 14)

One or more computer readable storage devices containing machine-executable instructions, the instructions when executed by the processing device, configuring the machine to implement the method of claim 14.

### Claim 16 (depends on 14)

An apparatus comprising the processing device to produce an animated scene from plural still images comprising logic configured to implement the method of claim 14.

### Claim 17 (depends on 14)

The method of claim 14, further comprising defining at least one motion parameter for at least one IAR that governs behavior of the IAR in the animated scene.