# US 8,786,785 B2 · Video signature > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,786,785 B2 - Document ID: US8786785B2 - Status: Granted - Kind: B2 - Application number: 13/080,494 - Filed: 2011-04-05 - Published: 2012-10-11 - Granted: 2014-07-22 - Earliest claimed: 2011-04-05 - Assignees: Microsoft Corporation - Applicants: Seth Hendrickson; George Randell Dong; Saswata Mandal; Charles Lawrence Zitnick, III - Inventors: Seth Hendrickson; George Randell Dong; Saswata Mandal; Charles Lawrence Zitnick, III - Web page: https://patentgrep.com/patent/US8786785B2 ## CPC - H04N 21/8352: involving content or source identification data, e.g. Unique Material Identifier [UMID] - G06F 16/70: of video data - G06V 20/47: {Detecting features for summarising video content} - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Video signatures are generated when a small change in video information between consecutive frames N−1 and N is followed by a large change in video information between consecutive frames N and N+1. Information from frames N and/or N+1 is used to form a video signature. ## Claims ### Claim 1 A method of finding a signature for a video, the method comprising: dividing a frame N of the video into a plurality of cells; calculating a video attribute of each cell of frame N; dividing a frame N+1 into the plurality of cells; calculating a video attribute of each cell of frame N+1; dividing a frame N−1 of the video into a plurality of cells; calculating a video attribute of each cell of frame N−1; calculating a difference metric between frame N and frame N+1 that includes, for each cell of the plurality of cells, a difference between the video attribute of frame N and the video attribute of frame N+1; calculating a difference metric between frame N and frame N−1 that includes, for each cell of the plurality of cells, a difference between the video attribute of frame N and the video attribute of frame N−1; and generating a video signature that includes information from one or both of frame N and frame N+1 responsive to the difference metric between frame N and frame N+1 exceeding a first threshold and a difference metric between frame N and frame N−1 not exceeding a second threshold. ### Claim 2 (depends on 1) The method of claim 1, wherein the plurality of cells includes M cells, and where an M-dimensional vector for each frame includes the video attribute for each of the plurality of M cells. ### Claim 3 (depends on 2) The method of claim 2, wherein calculating the difference metric between frame N and frame N+1 includes calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N+1. ### Claim 4 (depends on 1) The method of claim 1, where the video attribute is an average luminance for that cell. ### Claim 5 (depends on 1) The method of claim 1, where the video attribute is an average luminance for that cell normalized with respect to an average luminance for all cells of that frame. ### Claim 6 (depends on 1) The method of claim 1, where the video signature includes each of the video attributes of frame N concatenated with each of the video attributes of frame N+1. ### Claim 7 (depends on 1) The method of claim 1, where dividing frame N of the video into the plurality of cells includes dividing the frame N into a four by four grid of cells. ### Claim 8 (depends on 1) The method of claim 1, where frame N+1 immediately follows frame N and frame N−1 immediately precedes frame N. ### Claim 9 (depends on 1) The method of claim 1, wherein frame N−1 is divided into M cells and an M-dimensional vector for frame N−1 includes the video attribute for each cell, and wherein calculating the difference metric between frame N and frame N−1 includes calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N−1. ### Claim 10 (depends on 1) The method of claim 1, comprising associating a timestamp with the video signature. ### Claim 11 (depends on 1) The method of claim 1, wherein the first threshold and the second threshold are equal. ### Claim 12 A method for generating signatures of a video comprising: dividing a frame N of the video into a grid of M cells comprising an average luminance value for each cell of frame N; dividing a frame N+1 into the grid of M cells comprising an average luminance value for each cell of frame N+1; dividing a frame N−1 into the grid of M cells comprising an average luminance for each cell of frame N−1; calculating an M-dimensional vector for each of frame N, frame N+1, and frame N−1 that includes, for each different dimension, a luminance value of a different cell from that frame; calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N+1; calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N−1; and generating a video signature that includes the M-dimensional vector for frame N concatenated with the M-dimensional vector of frame N+1 responsive to the Euclidean distance between frame N and frame N+1 exceeding a first threshold and the Euclidean distance between frame N and frame N−1 not exceeding a second threshold. ### Claim 13 (depends on 12) The method of claim 12, wherein the average luminance value for each cell of a frame is normalized with respect to an average luminance for all cells of that frame. ### Claim 14 (depends on 12) The method of claim 12, wherein the grid of M cells is a four by four grid. ### Claim 15 (depends on 12) The method of claim 12, further comprising iteratively advancing to subsequent frames to search for additional signatures within the video. ### Claim 16 (depends on 12) The method of claim 12, comprising associating a timestamp with the video signature. ### Claim 17 A data-holding subsystem holding instructions executable by a logic subsystem to: iteratively test a series of three consecutive frames within a video for a shot change, each test comprising: dividing a frame N of the video into a grid comprising M cells; calculating an M-dimensional vector for frame N that includes, for each different dimension of the M-dimensional vector, an average luminance value of a different cell from frame N; dividing a frame N+1 of the video into a grid comprising M cells; calculating an M-dimensional vector for frame N+1 that includes, for each different dimension of the M-dimensional vector, an average luminance value of a different cell from frame N+1; dividing a frame N−1 of the video into a grid comprising M cells; calculating an M-dimensional vector for frame N−1 that includes, for each different dimension of the M-dimensional vector, an average luminance value of a different cell from frame N−1; calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N+1; if the Euclidean distance between frame N and frame N+1 exceeds a first threshold, calculating a Euclidean distance between the M-dimensional vector for frame N and the M-dimensional vector for frame N−1; generating a video signature that includes the M-dimensional vector for frame N concatenated with the M-dimensional vector of frame N+1 responsive to the Euclidean distance between frame N and frame N−1 not exceeding a second threshold, and iteratively test a next series of three consecutive frames within the video for a next shot change. ### Claim 18 (depends on 17) The data-holding subsystem of claim 17, wherein the average luminance value for each cell of a frame is normalized with respect to an average luminance for all cells of that frame. ### Claim 19 (depends on 17) The data-holding subsystem of claim 17, comprising associating a timestamp with the video signature. ### Claim 20 (depends on 17) The data-holding subsystem of claim 17, wherein the grid is a four by four grid.