# US 10,482,126 B2 · Determination of similarity between videos using shot duration correlation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,482,126 B2 - Document ID: US10482126B2 - Status: Granted - Kind: B2 - Application number: 15/365,699 - Filed: 2016-11-30 - Published: 2018-05-31 - Granted: 2019-11-19 - Earliest claimed: 2016-11-30 - Assignees: Google Inc. - Applicants: Google LLC - Inventors: Yongzhe Wang; Anthony Mai - Web page: https://patentgrep.com/patent/US10482126B2 ## CPC - G06F 16/7837: {using objects detected or recognised in the video content} - G06F 16/738: Presentation of query results - G06F 16/9535: Search customisation based on user profiles and personalisation - G06V 20/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames} - G06V 20/48: {Matching video sequences} - G06V 20/49: {Segmenting video sequences, i.e. computational techniques such as parsing or cutting the sequence, low-level clustering or determining units such as shots or scenes} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract A content system identifies shots in a first video and shots in a second video. Shot durations are determined for the identified shots of each video. A histogram is generated for each video, each histogram dividing the identified shots of the corresponding video into a set of buckets divided according to a range of shot durations. The system determines confidence weights for the buckets of each histogram, with the confidence weight for a bucket based on a likelihood of a particular number of identified shots occurring within the range of shot duration for that bucket. A correlation value is computed for the two videos based on a number of identified shots in each bucket of each respective histogram and based on the confidence weights. The content system determines whether the two videos are similar based on the correlation value and a self-correlation value of each video. ## Claims ### Claim 1 A computer-implemented method comprising: identifying a first plurality of shots in a first video and a second plurality of shots in a second video; determining shot durations for each of the plurality of identified shots of the first video and the second video; generating a histogram for each of the first video and the second video, each histogram dividing the plurality of identified shots of the corresponding video into a set of buckets divided according to a range of shot durations; determining confidence weights for each bucket in the set of buckets of each histogram, wherein a confidence weight for a bucket is based on a likelihood of a particular number of identified shots occurring within the range of a shot duration for that bucket; computing a correlation value of the first video and the second video based on a number of identified shots in each bucket of each respective histogram and based on the confidence weights; and determining a similarity between the first video and the second video based on comparing the correlation value with a self-correlation value associated with each of the first video and the second video. ### Claim 2 (depends on 1) The method of claim 1, wherein the identifying a first plurality of shots in a first video and a second plurality of shots in a second video further comprises: for each of the first video and the second video: identifying intra-frame scores for frames of a video, the intra-frame scores indicating an amount of change between the frames of the video; determining that one or more of the intra-frame scores indicates a shot boundary in the video; and identifying the plurality of shots in the video, a shot in the plurality of shots separated by consecutive shot boundaries in the video. ### Claim 3 (depends on 1) The method of claim 1, wherein the determining shot durations for the identified shots of each of the first video and the second video further comprises: determining a number of frames within the identified shot of the video; and determining as a shot duration for the identified shot the number of frames within the shot. ### Claim 4 (depends on 1) The method of claim 1, wherein the generating the histogram for each of the first video and the second video further comprises: identifying a consecutive series of shot range durations; and assigning the identified shots of each of the first video and the second video to each bucket in the set of buckets of the histogram for each of the first video and the second video, the set of buckets of the histogram corresponding to the shot range durations, the identified shots assigned to each bucket the set of buckets such that the duration of the identified shots corresponds to the shot range duration of each bucket the set of buckets. ### Claim 5 (depends on 1) The method of claim 1, wherein the determining the confidence weights for each bucket the set of buckets of each histogram further comprises: determining probabilities of shot counts for each bucket the set of buckets in each histogram, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the probability for that bucket indicating the likelihood that a video would have a number of shots within the shot duration range of that bucket equal to the shot count of that bucket; and determining a confidence weight for each bucket the set of buckets of the histogram, the confidence weight for the bucket having an inverse relationship to the probability of the shot count for that bucket. ### Claim 6 (depends on 5) The method of claim 5, wherein the probability for the bucket is further computed based on determining a Poisson probability of the shot count, the Poisson probability for the bucket computed based on an average shot count of shots in a set of sample videos that have shot durations within the shot duration range of that bucket. ### Claim 7 (depends on 6) The method of claim 6, wherein the set of sample videos is retrieved from a content store and shares one or more characteristics with at least one of the first video or the second video. ### Claim 8 (depends on 1) The method of claim 1, wherein the computing the correlation value further comprises: computing an inner product of the shot counts of each bucket the set of buckets of each histogram of the first video and the second video, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the shot counts for every bucket modified by the corresponding confidence weight for that bucket. ### Claim 9 (depends on 1) The method of claim 1, wherein the self-correlation value for each video is computed by: computing an inner product of the shot counts of each bucket the set of buckets of the histogram for each video with the shot counts of the same buckets of the same histogram, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the shot counts for every bucket modified by the corresponding confidence weight for that bucket. ### Claim 10 (depends on 9) The method of claim 9, wherein the determining the similarity between the first video and the second video further comprises: determining a comparison ratio between the correlation value and a square root of a product of the self-correlation values of the first video and the second video; and in response to determining that the comparison ratio is above a threshold value, determining that the first video and the second video are similar. ### Claim 11 (depends on 1) The method of claim 1, wherein the confidence weight for a bucket is based on a likelihood of a particular number of identified shots occurring within the range of shot duration for that bucket for videos in the content store. ### Claim 12 A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to: identify a first plurality of shots in a first video and a second plurality of shots in a second video; determine shot durations for each of the plurality of identified shots of the first video and the second video; generate a histogram for each of the first video and the second video, each histogram dividing the plurality of identified shots of the corresponding video into a set of buckets divided according to a range of shot durations; determine confidence weights for each bucket in the set of buckets of each histogram, wherein a confidence weight for a bucket is based on a likelihood of a particular number of identified shots occurring within the range of a shot duration for that bucket; compute a correlation value of the first video and the second video based on a number of identified shots in each bucket of each respective histogram and based on the confidence weights; and determine a similarity between the first video and the second video based on comparing the correlation value with a self-correlation value associated with each of the first video and the second video. ### Claim 13 (depends on 12) The computer program product of claim 12, wherein the non-transitory computer readable storage medium has further instructions for the identification of the first plurality of shots in a first video and a second plurality of shots in a second video, that when executed by a processor, cause the processor to: for each of the first video and the second video: identify intra-frame scores for frames of a video, the intra-frame scores indicating an amount of change between the frames of the video; determine that one or more of the intra-frame scores indicates a shot boundary in the video; and identify the plurality of shots in the video, a shot in the plurality of shots separated by consecutive shot boundaries in the video. ### Claim 14 (depends on 12) The computer program product of claim 12, wherein the non-transitory computer readable storage medium has further instructions for the determination of shot durations for the identified shots of each of the first video and the second video, that when executed by a processor, cause the processor to: determine a number of frames within the identified shot of the video; and determine as a shot duration for the identified shot the number of frames within the shot. ### Claim 15 (depends on 12) The computer program product of claim 12, wherein the non-transitory computer readable storage medium has further instructions for the generation of the histogram for each video, that when executed by a processor, cause the processor to: identify a consecutive series of shot range durations; and assign the identified shots of each of the first video and the second video to each bucket in the set of buckets of the histogram for each of the first video and the second video, the set of buckets of the histogram corresponding to the shot range durations, the identified shots assigned to each bucket the set of buckets such that the duration of the identified shots corresponds to the shot range duration of each bucket the set of buckets. ### Claim 16 (depends on 12) The computer program product of claim 12, wherein the non-transitory computer readable storage medium has further instructions for the determination of the confidence weights for each bucket the set of buckets of each histogram, that when executed by a processor, cause the processor to: determine probabilities of shot counts for each bucket the set of buckets in each histogram, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the probability for that bucket indicating the likelihood that a video would have a number of shots within the shot duration range of that bucket equal to the shot count of that bucket; and determine a confidence weight for each bucket the set of buckets of the histogram, the confidence weight for the bucket having an inverse relationship to the probability of the shot count for that bucket. ### Claim 17 (depends on 16) The computer program product of claim 16, wherein the probability for the bucket is further computed based on determining a Poisson probability of the shot count, the Poisson probability for the bucket computed based on an average shot count of shots in a set of sample videos that have shot durations within the shot duration range of that bucket. ### Claim 18 (depends on 17) The computer program product of claim 17, wherein the set of sample videos is retrieved from a content store and shares one or more characteristics with at least one of the first video or the second video. ### Claim 19 (depends on 12) The computer program product of claim 12, wherein the non-transitory computer readable storage medium has further instructions for the computation of the correlation value, that when executed by a processor, cause the processor to: compute an inner product of the shot counts of each bucket the set of buckets of each histogram of the first video and the second video, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the shot counts for every bucket modified by the corresponding confidence weight for that bucket. ### Claim 20 (depends on 12) The computer program product of claim 12, wherein the self-correlation value for each video is computed according to further instructions in the non-transitory computer readable storage medium, that when executed by a processor, cause the processor to: compute an inner product of the shot counts of each bucket the set of buckets of the histogram for each video with the shot counts of the same buckets of the same histogram, the shot count for a bucket corresponding to the number of shots assigned to that bucket, the shot counts for every bucket modified by the corresponding confidence weight for that bucket. ### Claim 21 (depends on 20) The computer program product of claim 20, wherein the non-transitory computer readable storage medium has further instructions for determination a similarity between the first video and the second video, that when executed by a processor, cause the processor to: determine a comparison ratio between the correlation value and a square root of a product of the self-correlation values of the first video and the second video; and in response to the determination that the comparison ratio is above a threshold value, determining that the first video and the second video are similar. ### Claim 22 (depends on 12) The computer program product of claim 12, wherein the confidence weight for a bucket is based on a likelihood of a particular number of identified shots occurring within the range of shot duration for that bucket for videos in the content store.