# US 6,724,933 B1 · Media segmentation system and related methods

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

- Number: US 6,724,933 B1
- Document ID: US6724933B1
- Status: Granted
- Kind: B1
- Application number: 09/627,762
- Filed: 2000-07-28
- Granted: 2004-04-20
- Earliest claimed: 2000-07-28
- Assignees: Microsoft Corporation
- Inventors: Tong Lin; Hong-Jiang Zhang
- Web page: https://patentgrep.com/patent/US6724933B1

## CPC

- G06T 7/20: Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51)
- G06V 20/40: in video content (extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44)
- G11B 27/28: by using information signals recorded by the same method as the main recording {(G11B27/22 takes precedence)}
- H04N 21/23418: {involving operations for analysing video streams, e.g. detecting features or characteristics (television picture signal circuitry for scene change detection H04N5/147; filtering for image enhancement G06T5/00; methods or arrangements for recognising scenes G06V20/00; arrangements characterised by components specially adapted for monitoring, identification or recognition of video in broadcast systems H04H60/59)}
- H04N 21/26603: {for automatically generating descriptors from content, e.g. when it is not made available by its provider, using content analysis techniques}
- G06T 2207/10016: Video; Image sequence
- G11B 2220/20: Disc-shaped record carriers
- G11B 2220/455: said record carriers being in one device and being used as primary and secondary/backup media, e.g. HDD-DVD combo device, or as source and target media, e.g. PC and portable player
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING
- G11B: INFORMATION STORAGE BASED ON RELATIVE MOVEMENT BETWEEN RECORD CARRIER AND TRANSDUCER (recording measured values in a way that does not require playback through a transducer G01D9/00; recording or playback apparatus using mechanically marked tape, e.g. punched paper tape, or using unit records, e.g. punched or magnetically marked cards G06K; transferring data from one type of record carrier to another G06K1/18; circuits for coupling output of reproducer to radio receiver H04B1/20; gramophone pick-ups or like acoustic electromechanical transducers or circuits therefor H04R)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

A method comprising receiving media content and analyzing one or more attributes of successive shots of the received media. Based, at least in part on the analysis of the one or more attributes, generating a correlation score for each of the successive shots, wherein scene segmentation is performed to group semantically cohesive shots.

## Claims

### Claim 1

A computer-implemented method comprising:
identifying successive shots of received media content;
generating color histograms associated with frames in the successive shots;
identifying dominant color objects within the color histograms;
tracking the dominant color objects in the color histograms across the frames;
detecting shot boundaries based, at least in part, on a relative position of the dominant color objects across the frames; and
generating correlation scores for the successive shots based, at least in part, on analysis of the dominant color objects.

### Claim 2 (depends on 1)

A computer-implemented method according to claim 1, wherein the media content is received from a remote provider and/or local storage.

### Claim 3 (depends on 1)

A computer-implemented method according to claim 1, wherein the correlation scores reflect semantic correlation between the successive shots.

### Claim 4 (depends on 1)

A computer-implemented method according to claim 1, wherein identifying dominant color objects within the color histograms comprises identifying the twenty top color objects having most significant color information for the frames as the dominant color objects.

### Claim 5 (depends on 1)

A computer-implemented method according to claim 1, wherein generating color histograms associated with frames in the successive shots comprises:
projecting pixels of a frame, and/or DC blocks of an intra-encoded frame, into a quantized color space; and
generating a normalized distribution of the pixels and/or blocks to create the color histogram for each frame.

### Claim 6 (depends on 5)

A computer-implemented method according to claim 5, wherein the quantized color space is the hue, saturation and value (HSV) color space.

### Claim 7 (depends on 1)

A computer-implemented method according to claim 1, further comprising:
generating a dynamically sized, expanding window of shots that defines a scene;
generating a correlation score between at least one of the shots in the dynamically sized, expanding window of shots and a new shot; and
adding the new shot to the dynamically sized, expanding window of shots based, at least in part, on the generated correlation score.

### Claim 8 (depends on 7)

A computer-implemented method according to claim 7, wherein the generated correlation score reflects, at least in part, a correlation of color objects in the shots.

### Claim 9 (depends on 7)

A computer-implemented method according to claim 7, wherein generating the correlation score comprises:
identifying an intersection of color histograms associated with each of two or more shots.

### Claim 10 (depends on 1)

A storage medium comprising a plurality of executable instructions including a subset of which that, when executed, implement a computer-implemented method according to claim 1.

### Claim 11 (depends on 1)

A computing system comprising:
a storage medium including a plurality of executable instructions; and
an execution unit, coupled to the storage medium, to execute at least a plurality of the executable instructions to implement a computer-implemented method according to claim 1.

### Claim 12

A computer-implemented method comprising:
analyzing color information associated with received media content in a color space to identify one or more color objects;
tracking the color objects through the received media content; and
quantifying a correlation between shots to identify a scene based, at least in part, on the tracking of the color objects.

### Claim 13 (depends on 12)

A computer-implemented method according to claim 12, wherein analyzing color information comprises:
projecting pixels of each frame, or DC blocks of intra-encoded frame(s) into a quantized color space; and
generating a normalized distribution of the pixels and/or blocks to form a color histogram of the media content.

### Claim 14 (depends on 13)

A computer-implemented method according to claim 13, further comprising:
identifying local maximum points in the color histogram; and
defining a color object as a sphere of N quantization units surrounding each of the identified local maximums.

### Claim 15 (depends on 14)

A computer-implemented method according to claim 14, wherein the color object is defined as a sphere of three (3) quantization units surrounding identified local maximums.

### Claim 16 (depends on 14)

A computer-implemented method according to claim 14, wherein tracking color objects through the media content comprises:
selecting one or more color objects in the color space associated with two frames; and
generating a correlation score for the frames denoting a likelihood that a color object appearing in each of the frames is the same color object.

### Claim 17 (depends on 16)

A computer-implemented method according to claim 16, wherein generating the correlation score between frames comprises:
locating the center point of a color object in each of two frames; and
calculating a relative position of each of the center points of the color object in each frame, wherein if the relative position of the color objects do not deviate by a predetermined threshold, the color objects are identified as a common color object.

### Claim 18 (depends on 12)

A computer-implemented method according to claim 12, further comprising:
generating a shot color histogram to include only color objects with the longest duration across frames comprising an identified shot.

### Claim 19 (depends on 18)

A computer-implemented method according to claim 18, wherein quantifying a correlation between shots comprises:
calculating a histogram intersection between two shot color histograms to determine semantic correlation between shots.

### Claim 20 (depends on 19)

A computer-implemented method according to claim 19, further comprising:
grouping shots in an expanding window of semantically correlated shots when the correlation score between shots exceeds a predetermined threshold.

### Claim 21 (depends on 20)

A computer-implemented method according to claim 20, wherein the group of shots comprises a scene.

### Claim 22 (depends on 12)

A computer-implemented method according to claim 12, further comprising:
grouping shots in an expanding window of semantically correlated shots when the correlation score between shots exceeds a predetermined threshold.

### Claim 23 (depends on 12)

A storage medium comprising a plurality of executable instructions which, when executed, implement a computer-implemented method according to claim 12.

### Claim 24 (depends on 12)

A computing system comprising:
a storage medium including a plurality of executable instructions; and
an execution unit, coupled to the storage medium, to access and execute at least a subset of the plurality of executable instructions to implement a computer-implemented method according to claim 12.

### Claim 25

A computer-implemented method comprising:
identifying color objects within a color space associated with shots of received media;
tracking the color objects in the color space across shots to generate a correlation score between shots; and
segmenting the received media content into scenes based, at least in part, on the correlation score.

### Claim 26 (depends on 25)

A computer-implemented method according to claim 25, wherein the color objects are dominant color objects.

### Claim 27 (depends on 25)

A computer-implemented method according to claim 25, further comprising:
extracting one or more slices from frames of received media to analyze one or more spatio-temporal attributes of frame(s) of the received media;
generating a correlation score between frames based, at least in part, on the spatio-temporal attributes of the frames; and
selecting segment boundaries within a shot based, at least in part, on the correlation score between frames.

### Claim 28 (depends on 25)

A computer-implemented method according to claim 25, wherein segmenting comprises:
generating a correlation score between identified shots; and
populating a dynamically expanding window with shots whose correlation score exceeds a predetermined threshold.

### Claim 29 (depends on 28)

A computer-implemented method according to claim 28, wherein generating the correlation score comprises:
selecting one or more key-frames for each segment of an identified shot based, at least in part, on the spatio-temporal attributes of the frames; and
generating the correlation score between identified shots based, at least in part, on visual features of the key-frames of the shots.

### Claim 30

A storage medium comprising a plurality of instructions which, when executed, implement a media analysis agent to identify color objects within a color space associated with shots of received media, track the color objects in the color space across shots to generate a correlation score between shots, and segment the received media content into scenes based, at least in part, on the correlation score.

### Claim 31 (depends on 30)

A storage medium according to claim 30, wherein the color objects are dominant color objects.

### Claim 32 (depends on 30)

A storage medium according to claim 30, further comprising instructions to extract one or more slices from frames of received media to analyze one or more spatio-temporal attributes of frame(s) of the received media, generate a correlation score between frames based, at least in part, on the spatio-temporal attributes of the frames, and select shot boundaries based, at least in part, on the correlation score between frames.

### Claim 33 (depends on 30)

A storage medium according to claim 30, further comprising instructions to generate a correlation score between identified shots, and populate a dynamically expanding window with shots whose correlation score exceeds a predetermined threshold.

### Claim 34 (depends on 30)

A computing system comprising:
a disk drive to removably receive a storage medium according to claim 30; and
an execution unit, coupled to the disk drive, to execute at least a subset of the plurality of instructions on the removably receive storage medium to implement the media analysis agent.

### Claim 35

A computing system comprising:
a memory device, to receive and provide media content; and
a media analysis agent, coupled to the memory device, and configured to generate color histograms associated with shots in the media content, identify color objects from local maximums in the color histograms, track the color objects across shots to identify shots with semantically similar frames, and segment the received media content into scenes having shots with semantically similar frames.

### Claim 36 (depends on 35)

A computing system according to claim 35, wherein the media analysis agent comprises:
a color object analyzer to project pixels of media frame(s), and/or DC blocks of intra-encoded frame(s), into a quantized color space and generate a color histogram of the frame(s).

### Claim 37 (depends on 35)

A computing system according to claim 35, wherein the color objects are dominant color objects.

### Claim 38 (depends on 35)

A computing system according to claim 35, wherein the media analysis agent further comprises:
a correlation detector, to receive one or more attributes associated with a plurality of shots from the color object analyzer and calculate a correlation score between two or more of the shots.

### Claim 39 (depends on 38)

A computing system according to claim 38, wherein the media analysis agent further comprises:
a dynamically sized expanding window, coupled to the correlation detector, to retain semantically correlated shots defining a scene until all shots are statistically analyzed for inclusion in the scene.

### Claim 40 (depends on 35)

A computing system according to claim 35, wherein the media analysis agent comprises:
a temporal slice analyzer, to extract one-dimensional slice(s) from one or more frames and analyze one or more spatio-temporal attributes of the slices to detect shot boundaries.

### Claim 41 (depends on 40)

A computing system according to claim 40, wherein the media analysis agent further comprises:
a correlation detector, to receive one or more attributes associated with a plurality of shots from the temporal slice analyzer and calculate a correlation score between two or more of the shots.

### Claim 42 (depends on 41)

A computing system according to claim 41, wherein the media analysis agent further comprises:
a dynamically sized expanding window, coupled to the correlation detector, to retain semantically correlated shots defining a scene until all shots are statistically analyzed for inclusion in the scene.

### Claim 43

A computer-implemented method comprising:
analyzing color information associated with received media content in a color space to identify one or more color objects, comprising:
projecting pixels of each frame, or DC blocks of intra-encoded frame(s) into a quantized color space;
generating a normalized distribution of the pixels and/or blocks to form a color histogram of the media content;
identifying local maximum points in the color histogram; and
defining a color object as a sphere of N quantization units surrounding each of the identified local maximums;
tracking the color objects through the received media content to identify shots, comprising:
selecting one or more color objects in the color space associated with two frames; and
generating a correlation score for the frames denoting a likelihood that an object appearing in each of the frames is the same object; and
quantifying a correlation between shots to identify a scene based, at least in part, on the analyzed color information associated with the received media content.

### Claim 44 (depends on 43)

A method according to claim 43, wherein generating the correlation score between frames comprises:
locating the center point of a color object in each of two frames; and
calculating a relative position of each of the center points of the object in each frame, wherein if the relative position of the objects do not deviate by a predetermined threshold, the objects are identified as a common object.

### Claim 45 (depends on 43)

A method according to claim 43, further comprising:
generating a shot color histogram to include only color objects with the longest duration across frames comprising an identified shot.

### Claim 46 (depends on 45)

A method according to claim 45, wherein quantifying a correlation between shots comprises:
calculating a histogram intersection between two shot color histograms to determine semantic correlation between shots.

### Claim 47 (depends on 46)

A method according to claim 46, further comprising:
grouping shots in an expanding window of semantically correlated shots when the correlation score between shots exceeds a predetermined threshold.

### Claim 48 (depends on 47)

A method according to claim 47, wherein the group of shots comprises a scene.

### Claim 49

A computing system comprising:
a memory device, to receive and provide media content; and
a media analysis agent, coupled to the memory device, to analyze one or more attributes of media content to identify semantic similarity between elements of the received content, and segment the received media content into scenes of semantically correlated elements, the media analysis agent further comprising:
a color object analyzer to project pixels of media frame(s), and/or DC blocks of intra-encoded frame(s), into a quantized color space and generate a color histogram of the frame(s), the color object analyzer being further configured to identify color space objects from local maximums in the color histogram, and tracks color space objects across frames to identify shots of semantically similar frames.

### Claim 50 (depends on 49)

A computing system according to claim 49, wherein the media analysis agent further comprises:
a correlation detector, to receive one or more attributes associated with a plurality of shots from the color object analyzer and calculate a correlation score between two or more of the shots.

### Claim 51 (depends on 50)

A computing system according to claim 50, wherein the media analysis agent further comprises:
a dynamically sized expanding window, coupled to the correlation detector, to retain semantically correlated shots defining a scene until all shots are statistically analyzed for inclusion in the scene.