# US 10,319,412 B2 · Robust tracking of objects in videos > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,319,412 B2 - Document ID: US10319412B2 - Status: Granted - Kind: B2 - Application number: 15/353,186 - Filed: 2016-11-16 - Published: 2018-05-17 - Granted: 2019-06-11 - Earliest claimed: 2016-11-16 - Assignees: Adobe Inc. - Applicants: Adobe Inc. - Inventors: Zhihong Ding; Zhe Lin; Xiaohui Shen; Michael Kaplan; Jonathan Brandt - Web page: https://patentgrep.com/patent/US10319412B2 ## CPC - G11B 27/11: by using information not detectable on the record carrier - G06T 7/97: {Determining parameters from multiple pictures (depth or shape recovery from multiple images G06T7/55; stereo camera calibration G06T7/85)} - G06T 11/60: Creating or editing images; Combining images with text - G06V 10/255: {Detecting or recognising potential candidate objects based on visual cues, e.g. shapes} - G06V 20/46: {Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames} - G11B 27/031: Electronic editing of digitised analogue information signals, e.g. audio or video signals - G11B 27/28: by using information signals recorded by the same method as the main recording {(G11B27/22 takes precedence)} - G11B 27/326: {used signal is a video-frame or a video-field (P.I.P.)} - G06T 2207/10016: Video; Image sequence - 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) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract The present disclosure is directed toward systems and methods for tracking objects in videos. For example, one or more embodiments described herein utilize various tracking methods in combination with an image search index made up of still video frames indexed from a video. One or more embodiments described herein utilize a backward and forward tracking method that is anchored by one or more key frames in order to accurately track an object through the frames of a video, even when the video is long and may include challenging conditions. ## Claims ### Claim 1 In a digital environment for tracking objects in videos, a method of identifying objects in videos comprising: receiving a video; extracting a plurality of video frames from the video; generating an image search index from the plurality of video frames; receiving an indication of a query object within one or more key frames of the plurality of video frames; and for each of the plurality of video frames in the image search index: determining a similarity score between a key frame and the video frame based on a search area in the key frame, wherein a size of the search area is determined based on a distance between the key frame and the video frame, and generating a voting map that utilizes the determined similarity score to localize the query object in the video frame. ### Claim 2 (depends on 1) The method as recited in claim 1, further comprising identifying one or more auxiliary key frames. ### Claim 3 (depends on 2) The method as recited in claim 2, wherein identifying one or more auxiliary key frames comprises: selecting a candidate video frame from the image search index; determining, based on a spatially-constrained area within the key frame, a similarity between the candidate video frame and each of the one or more key frames; and determining that the similarity between the candidate video frame and a key frame of the one or more key frames is greater than a predetermined threshold; re-categorizing, based on the similarity being greater than the predetermined threshold, the candidate video frame as an auxiliary key frame. ### Claim 4 (depends on 3) The method as recited in claim 3, further comprising: determining a first candidate query object for the video frame based on the key frame; determining a second candidate query object for the video frame based on the auxiliary key frame; weighting a similarity score for the first candidate query object using a time decay function; weighting a similarity score for the second candidate query object using the time decay function; and selecting as the query object one of the first candidate query object or the second candidate query object that has the maximum weighted similarity score. ### Claim 5 (depends on 1) The method as recited in claim 1, wherein generating the image search index comprises: identifying one or more video frames in the received video; extracting one or more features from each of the one or more video frames. ### Claim 6 (depends on 1) The method as recited in claim 1, further comprising redacting the query object from the video frames in which the query object is identified. ### Claim 7 (depends on 6) The method as recited in claim 6, wherein redacting the query object from the video frames in which the query object is identified comprises: identifying, within each of the video frames in which the query object is identified, an area around the localized query object; changing a color of pixels within the area around the localized query object. ### Claim 8 (depends on 1) The method as recited in claim 1, further comprising determining a location of the search area based on a location of the query object in a keyframe. ### Claim 9 (depends on 1) The method as recited in claim 1, further comprising: sequentially determining similarity scores working backward and forward from the key frame, adjusting the determined similarity scores using penalty variables, wherein a penalty variable for a given similarity score is based on the given similarity score, a penalty variable for a previous similarity score, and a lower threshold. ### Claim 10 A system for tracking objects in videos comprising: a memory comprising a video; a computing device, storing instructions thereon that, when executed by the computing device, cause the system to: extract a plurality of video frames from the video; generate an image search index from the plurality of video frames by extracting one or more features from each of the video frames; receive an indication of a query object within one or more key frames of the plurality of video frames and a location of the query object with the one or more key frames; and for each of the plurality of video frames: determine a similarity score between a key frame and a video frame based on a search area in the key frame by comparing features of the query object in the key frame to features of the video frame within the search area, wherein a size of the search area is determined based on a distance between the key frame and the video frame, and generate a voting map that utilizes the determined similarity score to localize the query object in the video frame. ### Claim 11 (depends on 10) The system as recited in claim 10, wherein the instructions, when executed by the computing device, further cause the system to: track backward from the key frame to identify the query object by performing acts comprising: identifying a bounding box around the query object in the key frame, identifying a preceding candidate video frame that has an earlier time stamp than the key frame, identifying a search area for the preceding candidate video frame based on a location of the bounding box and a distance from the key frame to the preceding candidate video frame, and track forward from the key frame to identify the query object by performing acts comprising: identifying a subsequent candidate video frame that has a later time stamp than the key frame, identifying a search area for the subsequent candidate video frame based on a location of the bounding box and a distance from the key frame to the subsequent candidate video frame. ### Claim 12 (depends on 11) The system as recited in claim 11, wherein the instructions, when executed by the computing device, further cause the system to redact the query object from the video frames in which the query object is identified; and generate a redacted video by merging the video frames in which the query object has been redacted with a remainder of the plurality of video frames based on time stamps associated with each video frame. ### Claim 13 A non-transitory computer-readable medium storing instructions thereon that, when executed by at least one processor, cause a computer system to: extract a plurality of video frames from the video; generate an image search index from the plurality of video frames by extracting one or more features from each of the video frames; receive an indication of a query object within one or more key frames of the plurality of video frames and a location of the query object with the one or more key frames; and for each of the plurality of video frames: determine a similarity score between a key frame and a video frame based on a search area in the key frame, wherein a size of the search area is determined based on a distance between the key frame and the video frame, and generate a voting map that utilizes the determined similarity score to localize the query object in the video frame. ### Claim 14 (depends on 13) The non-transitory computer-readable medium as recited in claim 13, further storing instructions thereon that, when executed by the at least one processor, cause the system to identify one or more auxiliary key frames. ### Claim 15 (depends on 14) The non-transitory computer-readable medium as recited in claim 14, wherein identifying one or more auxiliary key frames comprises: selecting a candidate video frame from the image search index; determining, based on a spatially-constrained area within the key frame, a similarity between the candidate video frame and each of the one or more key frames; and determining that the similarity between the candidate video frame and a key frame of the one or more key frames is greater than a predetermined threshold; and re-categorizing, based on the similarity being greater than the predetermined threshold, the candidate video frame as an auxiliary key frame. ### Claim 16 (depends on 15) The non-transitory computer-readable medium as recited in claim 15, further storing instructions thereon that, when executed by the at least one processor, cause the system to: determine a first candidate query object for the video frame based on the key frame; determine a second candidate query object for the video frame based on the auxiliary key frame; weight a similarity score for the first candidate query object using a time decay function; weight a similarity score for the second candidate query object using the time decay function; and select as the query object one of the first candidate query object or the second candidate query object that has the maximum weighted similarity score. ### Claim 17 (depends on 16) The non-transitory computer-readable medium as recited in claim 16, wherein generating the image search index comprises: identifying one or more video frames in the received video; extracting one or more features from each of the one or more video frames. ### Claim 18 (depends on 17) The non-transitory computer-readable medium as recited in claim 17, further storing instructions thereon that, when executed by the at least one processor, cause the system to redact the query object from the video frames in which the query object is identified. ### Claim 19 (depends on 18) The non-transitory computer-readable medium as recited in claim 18, wherein redacting the query object from the video frames in which the query object is identified comprises: identifying, which each of the video frames in which the query object is identified, an area around the localized query object; and changing a color of pixels within the area around the localized query object. ### Claim 20 (depends on 19) The non-transitory computer-readable medium as recited in claim 19, further storing instructions thereon that, when executed by the at least one processor, cause the system to determine a location of the search area based on a location of the query object in a key frame.