Generating videos

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating videos. In one aspect, a method comprises: receiving: (i) an input video comprising a sequence of video frames, and (ii) data indicating a target object type; processing the input video to generate tracking data that identifies and tracks visual locations of one or more instances of target objects of the target object type in the input video; generating a plurality of sub-videos based on the input video and the tracking data, including: for each sub-video, generating a respective sequence of sub-video frames that are each extracted from a respective video frame of the input video to include a respective instance of a given target object from among the identified target objects of the target object type; and generating an output video that comprises the plurality of sub-videos.

CROSS-REFERENCE TO RELATED APPLICATION

This application is a National Stage Application under 35 U.S.C. § 371 and claims the benefit of International Application No. PCT/US2020/038963, filed Jun. 22, 2020. The disclosure of the foregoing application is hereby incorporated by reference in its entirety.

BACKGROUND

This specification relates to generating videos.

The Internet facilitates the exchange of information between users across the globe. Content from multiple different providers, including videos, can be integrated into a single electronic document to create a composite document. For example, a portion of the content included in the electronic document may be selected (or specified) by a publisher of the electronic document. A different portion of content (e.g., third party content, including videos) can be provided by a third party (e.g., an entity that is not a publisher of the electronic document), and integrated into the electronic document to form a composite document that includes content from multiple different sources.

SUMMARY

This specification describes a system implemented as computer programs on one or more computers in one or more locations that can process an input video to extract multiple sub-videos from the input video that each show a respective object of a target object type. The system can combine the sub-videos showing the objects of the target object type to generate a “topical” video (e.g., that includes a target object type related to a given topic). The topical video may be integrated into a digital component that is transmitted for presentation with electronic documents at user devices, e.g., in blocks alongside search results or on third party websites.

According to a first aspect there is provided a method performed by one or more data processing apparatus, the method comprising: receiving: (i) an input video comprising a sequence of video frames, and (ii) data indicating a target object type; processing the input video to generate tracking data that identifies and tracks visual locations of one or more instances of target objects of the target object type in the input video; generating a plurality of sub-videos based on the input video and the tracking data, including: for each sub-video, generating a respective sequence of sub-video frames that are each extracted from a respective video frame of the input video to include a respective instance of a given target object from among the identified target objects of the target object type, wherein at least one of the sub-video frames is cropped from a respective video frame of the input video to include less than all content of the respective video frame; and generating an output video that comprises the plurality of sub-videos.

In some implementations, processing the input video to generate the tracking data comprises, for each instance of a target object of the target object type in the input video: determining, for each of multiple video frames of the input video, a respective bounding box that encloses the instance of the target object in the video frame.

In some implementations, for each sub-video, generating the respective sequence of sub-video frames comprises: cropping the respective bounding box that encloses the instance of the given target object corresponding to the sub-video from each of the multiple video frames of the input video.

In some implementations, for each sub-video, generating the respective sequence of sub-video frames comprises: determining, based on the tracking data, a same bounding box that encloses the instance of the given target object corresponding to the sub-video in each of multiple video frames of the input video; and cropping the same bounding box from each of the multiple video frames of the input video.

In some implementations, a sub-video frame of a first sub-video and a sub-video frame of a second sub-video are each cropped from a same video frame of the input video.

In some implementations, generating the output video that comprises the plurality of sub-videos comprises: assigning each sub-video of the plurality of sub-videos to a respective slot in a video template that defines a format for combining the plurality of sub-videos.

In some implementations, the method further comprises: receiving one or more additional data elements; and assigning each additional data element to a respective slot in the video template.

In some implementations, each additional data element comprises image data, text data, or both.

In some implementations, the output video concurrently shows at least two of the sub-videos of the plurality of sub-videos.

In some implementations, the method further comprises: receiving a request for a digital component; determining that a digital component that includes the output video is responsive to the request; and providing the digital component that includes the output video in response to the request to be presented alongside search results or on a third-party webpage.

In some implementations, receiving data indicating the target object type comprises: receiving data specifying a keyword; and mapping the keyword to the target object type in accordance with a mapping from keywords to a predefined set of possible target object types.

According to another aspect, there is provided a system comprising one or more data processing apparatus and one or more storage devices storing instructions that, when executed by the one or more data processing apparatus, cause the one or more data processing apparatus to perform the operations of the method described above.

According to another aspect, there is provided a computer-readable storage medium storing instructions that, when executed by one or more data processing apparatus, cause the one or more data processing apparatus to perform the operations of the method described above.

This specification describes a video generation system that can process an input video to extract multiple sub-videos that each show a respective object of a target object type, and then combine the sub-videos to generate a topical video. The video generation system may combine the sub-videos, e.g., by slotting the sub-videos into a video template where multiple sub-videos may be concurrently shown. The topical video may effectively summarize the content of the input video that relates to the target object type, while potentially having a shorter duration than the input video, occupying less space in a memory than the input video, and/or requiring less bandwidth to transmit over a communications network (e.g., the Internet) than the input video. The topical video may occupy less space in a memory than the input video and/or require less bandwidth to transmit over a communications network than the input video, e.g., because each sub-video frame of each sub-video (e.g., that makes up the topical video) is cropped from a respective video frame of the input video to include less than all of the content of the video frame and/or because each sub-video comprises content from a subset of the video frames of the input video. In other words, each sub-video comprises a spatial and/or temporal subset of the content of the input video. Moreover, this subset of the content is based on generated tracking data that identifies and tracks visual locations of one or more instances of target objects of a target object type in the input video. This provides more efficient generation of videos through filtering content of an input video to identify and select targeted portions of the input video. Instead of the entire input video being transmitted to distributed systems, a topical video comprising a targeted subset of the input video can be generated and transmitted to a particular system. This can reduce the bandwidth required for transmitting content of the input video when requests are received for content included in the input video. Therefore, the video generation system may enable more efficient use of computational resources, e.g., memory, bandwidth, and computing power. Additionally, by summarizing the content of the input video that relates to the target object type by combining the sub-videos, the information about the target object type from the input video can be presented in a more condensed form and without requiring a user to view the entirety of the input video. This reduces the amount of network bandwidth required to present the information about the target object type to users, and also reduces the amount of time required to present the information about the target object type.

The video generation system described in this specification can rapidly generate visually pleasing topical videos (e.g., in a matter of minutes) while requiring little or no manual user input, e.g., beyond providing the input video and specifying the target object type. In contrast, manually generating topical videos may be expensive and time consuming, e.g., requiring hours or days, and a significant amount of expertise. Therefore, the video generation system described in this specification enables more efficient allocation of time and resources by automating the task of generating topical videos.

DETAILED DESCRIPTION

FIG.1shows an example video generation system100. The video generation system100is an example of a system implemented as computer programs on one or more computers in one or more locations in which the systems, components, and techniques described below are implemented.

The system100is configured to process: (i) an input video102, and (ii) data identifying a “target” object type104, to generate a topical video106.

The input video102may include a sequence of video frames, where each video frame may be represented as an array of numerical values and be associated with a respective time point in the input video102.

The system100processes the input video102and the target object type104to generate a topical video106that includes multiple “sub-videos” that are extracted (e.g., cropped) from the input video102, where each sub-video shows (e.g., depicts) a respective object of the target object type104. That is, the system100generates a topical video106that includes portions of the input video102which show objects of the target object type104.

The system100can be used for any of a variety of applications. For example, the system100may be used to generate topical videos that are integrated into digital components that are transmitted for presentation with electronic documents at user devices, e.g., in blocks alongside search results or on third party websites, as will be described in more detail with reference toFIG.3andFIG.4.

The system100includes a tracking engine108, a cropping engine110, and a synthesis engine112, which will each be described in more detail next.

The tracking engine108is configured to process the input video102and the data identifying the target object type104to generate tracking data114that identifies, labels, and tracks visual locations of one or more instances of objects of the target object type104in the input video102. For convenience, throughout this specification an object of the target object type104may be referred to as a “target object”.

The tracking data114may include data defining one or more “target object trajectories”, where each target object trajectory corresponds to a respective instance of a target object and tracks the position of the target object through each video frame in a sequence of multiple video frames. More specifically, a target object trajectory corresponding to a target object may specify the position of the target object in each video frame in a sequence of video frames, e.g., by specifying a respective bounding box corresponding to each video frame that encloses the target object in the video frame. A bounding box corresponding to a video frame may be defined, e.g., by the coordinates of the vertices of the bounding box, where the coordinates are expressed in the frame of reference of the video frame. As used throughout this specification, a “bounding box” in a video frame may specify a region of the video frame having any appropriate shape, e.g., a square shape, a rectangular shape, or a circular shape.

A bounding box specifying the position of a target object in a video frame may enclose less than all of the video frame, e.g., such that the bounding box excludes at least part of the video frame. (However, in some cases, a bounding box in a video frame may enclose the entirety of the video frame). Moreover, each target object trajectory may track the position of a corresponding target object through a sequence of video frames, which is a proper subset of the entire sequence of video frames of the input video.

The tracking engine108may use any appropriate object detection and tracking technique to generate the target object trajectories of the tracking data114. As an example, the tracking engine108may use the object detection and tracking techniques described in: J. Henriques, R. Caseiro, P. Martins, J. Batista, “High-speed tracking with kernelized correlation filters,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 3, pp. 583-596 (2014). As another example, the tracking engine108may use the object detection and tracking techniques described in: N. Wojke, A. Bewley, D. Paulus, “Simple online and realtime tracking with a deep association metric,” 2017IEEE International Conference on Image Processing(ICIP), pp. 3645-3649 (2017).

In a particular example, to generate the tracking data114, the tracking engine108may process each video frame of the input video102using an object detection neural network that is configured to process a video frame to generate an object detection output. The object detection output may include: (i) one or more bounding boxes that each enclose a respective object depicted in the video frame, and (ii) for each bounding box, a label identifying a type of the object that is enclosed by the bounding box. The tracking engine108may maintain the bounding boxes that are labeled as enclosing objects of the target object type104, while discarding (e.g., refraining from further processing of) any other bounding boxes. The tracking engine108may determine that a first bounding box in a first frame and a second bounding box in a second (e.g., subsequent) frame enclose the same object by determining that a similarity measure between the first bounding box and the second bounding box exceeds a threshold value. The similarity measure may be based on: (i) a visual similarity between the contents of the first bounding box and the second bounding box, and (ii) an overlap between the first bounding box and the second bounding box. In response to determining that the first bounding box and the second bounding box enclose the same object, the tracking engine108may determine that the first bounding box and the second bounding box are included in the same target object trajectory, e.g., thereby tracking the position of the object from the first frame to the second frame.

The cropping engine110is configured to process the input video102and the tracking data114to generate one or more sub-videos116. More specifically, the cropping engine110may generate a respective sub-video116corresponding to each target object trajectory specified by the tracking data114. As used throughout this specification, a “sub-video” refers to a video having a sequence of video frames, referred to as “sub-video frames”, such that each sub-video frame of the sub-video is cropped from a respective video frame of the video102. A sub-video frame of a sub-video116that is cropped from a corresponding video frame of the video102may include less than all of the corresponding video frame, e.g., such that the sub-video frame excludes at least a portion of the corresponding video frame (however, in some cases, a sub-video frame may include the entirety of a corresponding video frame of the video102). In a particular example, a video frame may have dimensions a×b, where a is the width of the video frame (e.g., the number of pixels along the width spatial dimension of the video frame) and b is the height of the video frame (e.g., the number of pixels along the height spatial dimension of the video frame). In this example, the sub-video frame cropped from the video frame may have dimensions c×d, where c is less than a and d is less than b.

As used throughout this specification, the “dimensions” of a video frame (or a sub-video frame, or a bounding box in a video frame) may refer to data specifying: (i) the width of the video frame (e.g., the number of pixels along the width spatial dimension of the video frame), and (ii) the height of the video frame (e.g., the number of pixels along the height spatial dimension of the video frame).

The cropping engine110can generate a sub-video116corresponding to a target object trajectory of a target object in a variety of ways. A few example implementations of the cropping engine110are described in more detail next.

In one implementation, the cropping engine110may extract a respective sub-video frame from each video frame corresponding to the target object trajectory by extracting a portion of the video frame based on the position of the target object in the video frame. For example, the target object trajectory may specify a respective bounding box for each video frame that encloses the target object in the video frame, and the cropping engine110may extract the portion of each video frame that is enclosed by the bounding box for the video frame. That is, the cropping engine110may generate each sub-video frame by extracting the portion of the corresponding video frame that is enclosed by the bounding box specified by the target object trajectory as enclosing the target object in the video frame. In this example, the tracking engine108may be configured to generate target object trajectories that specify a bounding box having fixed dimensions (e.g., width and height) for each video frame, e.g., such that each of the extracted sub-video frames have the same dimensions.

In another implementation, to generate the sub-video116corresponding to the target object trajectory, the cropping engine110may determine the dimensions (e.g., width and height) and position (e.g., center) of a “super” bounding box. In particular, the cropping engine110may determine the dimensions and position of the super bounding box such that the target object is enclosed by the super bounding box in each video frame corresponding to the target object trajectory. For example, the target object trajectory may specify a respective bounding box for each video frame that encloses the target object in the video frame, and the cropping engine110may identify a super bounding box that encloses each of the bounding boxes specified by the target object trajectory. That is, the cropping engine110may identify a super bounding box that encloses the union of the set of bounding boxes specified by the target object trajectory (while still enclosing less than all of each video frame). After determining the dimensions and position of the super bounding box, the cropping engine110may generate each sub-video frame by extracting the portion of a corresponding video frame that is enclosed by the super bounding box. Generating the sub-video116using a super bounding box that is the same for each video frame may improve the visual quality of the sub-video116, e.g., by better preserving the cinematographic effects of the original video102, e.g., panning and zooming.

In some cases, certain sub-videos116generated by the cropping engine110may be “temporally overlapping”, e.g., such two or more of the sub-videos include respective sub-video frames that are extracted from the same video frame of the input video102. This may occur, e.g., when the tracking engine108tracks two different instances of target objects through the same video frame in the video.

The synthesis engine112is configured to process the sub-videos116and a video template118to generate the topical video106. The video template118defines a format for combining multiple sub-videos116into a composite video (e.g., the topical video106) that includes each of the sub-videos. For example, the video template may define a partition of a two-dimensional (2-D) region (e.g., having a square or rectangular shape) into one or more sub-regions, referred to as “slots”. The synthesis engine112generates the topical video106by assigning each sub-video116to a respective slot in the video template118. The video template118may dynamically change over the duration of the topical video106, e.g., slots may be removed, slots may be added, or the sizes of slots may be changed over the duration of the topical video.

An example video template200is illustrated with reference toFIG.2. The video template200includes three slots—i.e., slot202, slot204, and slot206. The synthesis engine112may generate the topical video106by assigning a respective sub-video116to each slot of the video template200, e.g., such that the sub-videos in each slot are shown concurrently. In the example illustrated with reference toFIG.2, the target object type may be “vehicle”, and each slot may be assigned a respective sub-video showing an instance of a vehicle.

In another example, the video template118may be defined such that each sub-video116is shown consecutively, e.g., one after another, rather than any sub-videos being shown concurrently.

As part of generating the topical video106, the synthesis engine112may modify a sub-video116prior to assigning it to a slot in the video template118. For example, the synthesis engine112may modify (e.g., reduce) the dimensions (e.g., width and/or the height) of the sub-video frames of a sub-video, e.g., to cause the dimensions of the sub-video to match the dimensions of a corresponding slot in the video template118. As another example, the synthesis engine112may reduce the duration of a sub-video (e.g., by removing one or more sub-video frames of the sub-video) to cause the duration of the sub-video to match the duration of a slot. The duration of a slot may refer to the length of time the slot is included in the template, e.g., before being removed from the template.

The synthesis engine112may determine the assignment of the sub-videos116to the slots of the video template118in any of a variety of ways. In one example, the synthesis engine112may randomly assign sub-videos116to respective slots of the video template118. In another example, the synthesis engine112may assign each sub-video116to a corresponding slot having dimensions that are most similar (e.g., from amongst all the slots) to the dimensions of the sub-video116, e.g., to minimize the modifications applied to the sub-videos to cause them to fit their assigned slots.

In some cases, prior to assigning the sub-videos116to slots in the video template118, the synthesis engine112may determine a respective score for each sub-video, where the score for a sub-video characterizes a quality of the sub-video. The synthesis engine112may determine the score for each sub-video based on one or more criteria, e.g., the sharpness of the sub-video and the amount of motion in the sub-video. The sharpness of a sub-video may be computed using any appropriate sharpness measure, e.g., by computing the maximum pixel intensity value in the sub-video frames after convolving the sub-video frames with a Laplacian kernel. The amount of motion in the sub-video may be computed, e.g., by computing the average value of a set of optical flow frames corresponding to the sub-video frames. The synthesis engine112may generate the overall score for a sub-video based on, e.g., a linear combination of a sharpness score characterizing the sharpness of the sub-video and a motion score characterizing the amount of motion in the sub-video. The synthesis engine112may generate higher scores for sub-videos that are sharper and include more motion.

The synthesis engine112may use the scores for the sub-videos116to determine which sub-videos116should be included in the topical video106. For example, the synthesis engine112may determine that only a proper subset of the sub-videos116having the highest scores should be included in the topical video106. As another example, the synthesis engine112may determine that any sub-video116having a score that fails to satisfy a predefined threshold value (e.g., by exceeding the threshold value) should not be included in the topical video106.

In some implementations, the system100may receive one or more data elements120to be included in the topical video106, e.g., other than sub-videos116extracted from the input video102. The data elements120may include, e.g., images or portions of text. The synthesis engine112may include the data elements120in the topical video106by assigning the data elements to respective slots of the video template118.

The topical videos106generated by the video generation system100can be used in any of a variety of applications. A few example applications are described in more detail next.

In one example, topical videos106generated by the video generation system100may be included in digital components that are provided in response to digital component requests, e.g., as described in more detail with reference toFIG.3andFIG.4.

In another example, the video generation system100may process: (i) input videos that are generated, e.g., by one or more surveillance cameras (security cameras), and (ii) target object types104that are specified by a user, to generate corresponding topical videos106. The input videos generated by the surveillance cameras may be lengthy, e.g., having a duration of hours or days. The video generation system100may enable rapid processing of videos generated by surveillance cameras to generate topical videos showing objects of interest to a user, e.g., pets, people, or vehicles. A surveillance camera may refer to a camera that is placed at a given position (e.g., beside the front door of a home) and continuously captures video of a region in the vicinity of the given position.

In another example, the video generation system100may process: (i) input videos that are generated by a user device, e.g., a video camera of a smartphone, and (ii) target object types104that are specified by a user, to generate corresponding topical videos106.

FIG.3shows an example digital component generation system300. The digital component generation system300is an example of a system implemented as computer programs on one or more computers in one or more locations in which the systems, components, and techniques described below are implemented.

The digital component generation system300is configured to receive one or more keywords302and an input video102from a content provider, and to generate one or more digital components306that include topical videos106relevant to respective keywords302. The content provider may be, e.g., a publisher, advertiser, or other content source.

As used throughout this specification, the phrase digital component refers to a discrete unit of digital content or digital information that can include one or more of, e.g., images, video clips (e.g., topical videos), audio clips, multimedia clips, text segments, or uniform resource locators (URLs). A digital component can be electronically stored in a physical memory device as a single file or in a collection of files, and digital components can take the form of video files, audio files, multimedia files, image files, or text files and include streaming video, streaming audio, social network posts, blog posts, and/or advertising information, such that an advertisement is a type of digital component. A digital component can be enhanced with data from one or more sources (e.g., weather information, real time event information, or other information obtained from other sources).

The system300includes a keyword mapping engine308and a video generation system100(as described with reference toFIG.1). In addition, the system300may be associated with a user interface (e.g., a graphical user interface, or any other appropriate sort of user interface) that enables the content provider to interact with the system300, as will be described in more detail below.

The keyword mapping engine308is configured to map each keyword302to a corresponding target object type104from a set of possible object types, e.g., in accordance with a predefined mapping from keywords to possible object types. For example, the keyword mapping engine308may map the each of the keywords “spectacles”, “specs”, “reading glasses”, “sunglasses”, and “eyeglasses” to the possible object type of “glasses”. The set of possible object types may be the set of object types that the tracking engine of the video generation system100is trained (or otherwise configured) to identify and track in videos. In some implementations, the system300may provide an indication of the target object types104corresponding to the keywords302to the content provider, and request that the content provider “approve” (e.g., perform an action to accept) each of the target object types104.

The system300may use the video generation system100to generate one or more respective topical videos106corresponding to each target object type104, e.g., by processing the target object type104and the input video102using the video generation system100. The video generation system100may generate multiple topical videos106corresponding to a single target object type104, e.g., by generating topical videos106using different video templates from a set of possible video templates310, by generating topical videos106using different combinations of sub-videos extracted from the input video, by generating topical videos106where the sub-videos of the input video102are assigned to different combinations of slots in a video template, or by overlaying different audio soundtracks over the topical videos106. The system300may enable the content provider to specify (e.g., through the user interface) various factors controlling the generation of the topical videos106, e.g., which video templates310and/or audio soundtracks should be used by the video generation system100to generate the topical videos106.

In addition to the keywords302and the input video102, the content provider may also provide one or more other data elements (e.g., images or portions of text) to the system300to be included in the topical videos106. The video generation system100may include the provided data elements in the topical videos, e.g., as described with reference toFIG.1.

The system300may enable the content provider to select one or more of the topical videos106to be included in respective digital components306. Each digital component306may include a topical video106and other data elements (e.g., videos, images, portions of text, URLs) that may be provided by the content provider.

The content provider may provide the digital components306generated by the system300to a digital component distribution system, e.g., the digital component distribution system410described with reference toFIG.4. The digital component distribution system can transmit the digital components306in response to requests for digital components to be presented with electronic documents at user devices, e.g., in blocks alongside search results or on third party websites.

In a particular example illustrating the utility of the system300, a content provider may provide the system300with an input video102that includes several hours of footage of a fashion show, and the keyword302“handbag”. The system300may process the input video102and the keyword302to generate a corresponding set of topical videos106, each of which include multiple sub-videos of the input video that show instances of handbags, where the sub-videos are automatically edited into visually pleasing video templates, and omit portions of the input video, such that the populated video templates have a shorter duration (e.g., 30 second, 1 minute, 2 minutes, or another duration) than the duration of the input video102(e.g., the several hours of footage of the fashion show). The content provider may then select one or more of the topical videos106to be included in digital components that are provided to the digital component distribution system.

FIG.4is a block diagram of an example environment400in which a digital component distribution system410transmits digital components from a digital component database416for presentation with electronic documents. A content provider may generate digital components using the digital component generation system300(described with reference toFIG.3) and provide the generated digital components to the digital component distribution system410.

The example environment400includes a network402, such as a local area network (LAN), a wide area network (WAN), the Internet, or a combination thereof. The network402connects electronic document servers404, client devices406, digital component servers408, and the digital component distribution system410(also referred to as the “distribution system”410). The example environment400may include many different electronic document servers404, client devices406, and digital component servers408.

A client device406is an electronic device that is capable of requesting and receiving resources over the network402. Example client devices406include personal computers, mobile communication devices (e.g., mobile phones), and other devices that can send and receive data over the network402. A client device406typically includes a user application, such as a web browser, to facilitate the sending and receiving of data over the network402, but native applications executed by the client device406can also facilitate the sending and receiving of data over the network402.

An electronic document is data that presents a set of content at a client device406. Examples of electronic documents include webpages, word processing documents, portable document format (PDF) documents, images, videos, search results pages, and feed sources. Native applications (e.g., “apps”), such as applications installed on mobile, tablet, or desktop computing devices are also examples of electronic documents. Electronic documents can be provided to client devices406by electronic document servers404(“Electronic Doc Servers”). For example, the electronic document servers404can include servers that host publisher websites. In this example, the client device406can initiate a request for a given publisher webpage, and the electronic server404that hosts the given publisher webpage can respond to the request by sending machine executable instructions that initiate presentation of the given webpage at the client device406.

In another example, the electronic document servers404can include app servers from which client devices406can download apps. In this example, the client device406can download files required to install an app at the client device406, and then execute the downloaded app locally.

Electronic documents can include a variety of content. For example, an electronic document can include static content (e.g., text or other specified content) that is within the electronic document itself and/or does not change over time. Electronic documents can also include dynamic content that may change over time or on a per-request basis. For example, a publisher of a given electronic document can maintain a data source that is used to populate portions of the electronic document. In this example, the given electronic document can include one or more tags or scripts that cause the client device406to request content from the data source when the given electronic document is processed (e.g., rendered or executed) by a client device406. The client device406integrates the content obtained from the data source into the given electronic document to create a composite electronic document including the content obtained from the data source.

In some situations, a given electronic document can include one or more digital component tags or digital component scripts that reference the digital component distribution system410. In these situations, the digital component tags or digital component scripts are executed by the client device406when the given electronic document is processed by the client device406. Execution of the digital component tags or digital component scripts configures the client device406to generate a request for one or more digital components412(referred to as a “component request”), which is transmitted over the network402to the digital component distribution system410. For example, a digital component tag or digital component script can enable the client device406to generate a packetized data request including a header and payload data. The component request412can include event data specifying features such as a name (or network location) of a server from which the digital component is being requested, a name (or network location) of the requesting device (e.g., the client device406), and/or information that the digital component distribution system410can use to select one or more digital components provided in response to the request. The component request412is transmitted, by the client device406, over the network402(e.g., a telecommunications network) to a server of the digital component distribution system410.

The component request412can include event data specifying other event features, such as the electronic document being requested and characteristics of locations of the electronic document at which digital component can be presented. For example, event data specifying a reference (e.g., URL) to an electronic document (e.g., webpage) in which the digital component will be presented, available locations of the electronic documents that are available to present digital components, sizes of the available locations, and/or media types that are eligible for presentation in the locations can be provided to the digital component distribution system410. Similarly, event data specifying keywords associated with the electronic document (“document keywords”) or entities (e.g., people, places, or things) that are referenced by the electronic document can also be included in the component request412(e.g., as payload data) and provided to the digital component distribution system410to facilitate identification of digital components that are eligible for presentation with the electronic document. The event data can also include a search query that was submitted from the client device406to obtain a search results page, and/or data specifying search results and/or textual, audible, or other visual content that is included in the search results.

Component requests412can also include event data related to other information, such as information that a user of the client device has provided, geographic information indicating a state or region from which the component request was submitted, or other information that provides context for the environment in which the digital component will be displayed (e.g., a time of day of the component request, a day of the week of the component request, a type of device at which the digital component will be displayed, such as a mobile device or tablet device). Component requests412can be transmitted, for example, over a packetized network, and the component requests412themselves can be formatted as packetized data having a header and payload data. The header can specify a destination of the packet and the payload data can include any of the information discussed above.

The component distribution system410chooses digital components that will be presented with the given electronic document in response to receiving the component request412and/or using information included in the component request412. In some implementations, a digital component is selected (using the techniques described herein) in less than a second to avoid errors that could be caused by delayed selection of the digital component. For example, delays in providing digital components in response to a component request412can result in page load errors at the client device406or cause portions of the electronic document to remain unpopulated even after other portions of the electronic document are presented at the client device406. Also, as the delay in providing the digital component to the client device406increases, it is more likely that the electronic document will no longer be presented at the client device406when the digital component is delivered to the client device406, thereby negatively impacting a user's experience with the electronic document. Further, delays in providing the digital component can result in a failed delivery of the digital component, for example, if the electronic document is no longer presented at the client device406when the digital component is provided.

In some implementations, the digital component distribution system410is implemented in a distributed computing system that includes, for example, a server and a set of multiple computing devices414that are interconnected and identify and distribute digital components in response to requests412. The set of multiple computing devices414operate together to identify a set of digital components that are eligible to be presented in the electronic document from a corpus of millions of available digital components (DC1-x). The millions of available digital components can be indexed, for example, in a digital component database416. Each digital component index entry can reference the corresponding digital component and/or include distribution parameters (DP1-DPx) that contribute to (e.g., condition or limit) the distribution/transmission of the corresponding digital component. For example, the distribution parameters can contribute to the transmission of a digital component by requiring that a component request include at least one criterion that matches (e.g., either exactly or with some pre-specified level of similarity) one of the distribution parameters of the digital component.

In some implementations, the distribution parameters for a particular digital component can include distribution keywords that must be matched (e.g., by electronic documents, document keywords, or terms specified in the component request412) in order for the digital component to be eligible for presentation. In other words, the distribution parameters are used to trigger distribution (e.g., transmission) of the digital components over the network402. The distribution parameters can also require that the component request412include information specifying a particular geographic region (e.g., country or state) and/or information specifying that the component request412originated at a particular type of client device (e.g., mobile device or tablet device) in order for the digital component to be eligible for presentation.

The distribution parameters can also specify an eligibility value (e.g., ranking score, bid, or some other specified value) that is used for evaluating the eligibility of the digital component for distribution/transmission (e.g., among other available digital components), for example, by the component evaluation process. In some situations, the eligibility value can specify a maximum amount of compensation that a provider of the digital component is willing to submit in response to the transmission of the digital component (e.g., for each instance of specific events attributed to the presentation of the digital component, such as user interaction with the digital component).

The identification of the eligible digital component can be segmented into multiple tasks417a-417cthat are then assigned among computing devices within the set of multiple computing devices414. For example, different computing devices in the set414can each analyze a different portion of the digital component database416to identify various digital components having distribution parameters that match information included in the component request412. In some implementations, each given computing device in the set414can analyze a different data dimension (or set of dimensions) and pass (e.g., transmit) results (Res 1-Res 3)418a-418cof the analysis back to the digital component distribution system410. For example, the results418a-418cprovided by each of the computing devices in the set414may identify a subset of digital components that are eligible for distribution in response to the component request and/or a subset of the digital components that have certain distribution parameters. The identification of the subset of digital components can include, for example, comparing the event data to the distribution parameters, and identifying the subset of digital components having distribution parameters that match at least some features of the event data.

The digital component distribution system410aggregates the results418a-418creceived from the set of multiple computing devices414and uses information associated with the aggregated results to: (i) select one or more digital components that will be provided in response to the request412, and (ii) determine transmission requirements for the one or more digital components. For example, the digital component distribution system410can select a set of winning digital components (one or more digital components) based on the outcome of one or more component evaluation processes. In turn, the digital component distribution system410can generate and transmit, over the network402, reply data420(e.g., digital data representing a reply) that enables the client device406to integrate the set of winning digital components into the given electronic document, such that the set of winning digital components and the content of the electronic document are presented together at a display of the client device406.

In some implementations, the client device406executes instructions included in the reply data420, which configures and enables the client device406to obtain the set of winning digital components from one or more digital component servers. For example, the instructions in the reply data420can include a network location (e.g., a Uniform Resource Locator (URL)) and a script that causes the client device406to transmit a server request (SR)421to the digital component server408to obtain a given winning digital component from the digital component server408. In response to the request, the digital component server408will identify the given winning digital component specified in the server request421(e.g., within a database storing multiple digital components) and transmit, to the client device406, digital component data (DC Data)422that presents the given winning digital component in the electronic document at the client device406.

To facilitate searching of electronic documents, the environment400can include a search system450that identifies the electronic documents by crawling and indexing the electronic documents (e.g., indexed based on the crawled content of the electronic documents). Data about the electronic documents can be indexed based on the electronic document with which the data are associated. The indexed and, optionally, cached copies of the electronic documents are stored in a search index452(e.g., hardware memory device(s)). Data that are associated with an electronic document is data that represents content included in the electronic document and/or metadata for the electronic document.

Client devices406can submit search queries to the search system450over the network402. In response, the search system450accesses the search index452to identify electronic documents that are relevant to the search query. The search system450identifies the electronic documents in the form of search results and returns the search results to the client device406in a search results page. A search result is data generated by the search system450that identifies an electronic document that is responsive (e.g., relevant) to a particular search query, and includes an active link (e.g., hypertext link) that causes a client device to request data from a specified network location (e.g., URL) in response to user interaction with the search result. An example search result can include a web page title, a snippet of text or a portion of an image extracted from the web page, and the URL of the web page. Another example search result can include a title of a downloadable application, a snippet of text describing the downloadable application, an image depicting a user interface of the downloadable application, and/or a URL to a location from which the application can be downloaded to the client device406. In some situations, the search system450can be part of, or interact with, an application store (or an online portal) from which applications can be downloaded for install at a client device406in order to present information about downloadable applications that are relevant to a submitted search query. Like other electronic documents, search results pages can include one or more slots in which digital components (e.g., advertisements, video clips, audio clips, images, or other digital components) can be presented.

To select a digital component to be transmitted in response to a component request, the distribution system410may identify a set of digital components that are eligible to be transmitted in response to the component request. The distribution system410may then select one or more of the eligible digital components to be transmitted through, e.g., an auction procedure. In some implementations, the distribution system410performs an auction procedure by ranking the eligible digital components in accordance with their respective eligibility values, and selecting one or more highest-ranked digital components to be transmitted in response to the component request.

FIG.5is a flow diagram of an example process500for generating a topical video. For convenience, the process500will be described as being performed by a system of one or more computers located in one or more locations. For example, a video generation system, e.g., the video generation system100ofFIG.1, appropriately programmed in accordance with this specification, can perform the process500.

The system receives: (i) an input video including a sequence of video frames, and (ii) data indicating a target object type (502). For example, the system may receive data specifying a keyword (e.g., “sunglasses”), and then map the received keyword to a corresponding target object type (e.g., “glasses”) in accordance with a mapping from keywords to a predefined set of possible target object types. Optionally, the system may also receive one or more additional data elements, e.g., images, portions of text, or both.

The system processes the input video to generate tracking data that identifies and tracks visual locations of one or more instances of target objects of the target object type in the input video (504). For example, for each instance of a target object of the target object type in the input video, the system may determine a respective bounding box that encloses the instance of the target object in each of multiple video frames of the input video. The system may use any appropriate object detection and tracking technique to generate the tracking data, e.g., as described with reference toFIG.1.

The system generates multiple sub-videos based on the input video and the tracking data (506). For each sub-video, the system may generate a respective sequence of sub-video frames that are each cropped from a respective video frame of the input video to include (i) less than all content of the respective video frame and (ii) a respective instance of a given target object from among the identified target objects of the target object type. In some implementations, instead of each of the sub-video frames being cropped to include less than all content of the respective video frame, at least one of the sub-video frames is cropped from at least one respective video frame of the input video to include less than all content of the at least one respective video frame. In such implementations, one or more of the sub-video frames may comprise all content of the respective video frames, for example because a target object occupies all of the respective video frames or most of the respective video frames in those respective video frames. A sub-video frame may comprise a subset of all content of the respective video frame, with the subset being less than or equal to all content of the respective video frame. In some implementations, the system may generate the sequence of sub-video frames of a sub-video corresponding to an instance of a given target object by cropping a respective bounding box that encloses the instance of the given target object from each of multiple video frames of the input video. The bounding boxes enclosing instance of the given target object may be specified by the tracking data. In some implementations, to generate the sequence of sub-video frames of a sub-video corresponding to an instance of a given target object, the system may determine, based on the tracking data, a same bounding box that encloses the instance of the given target object in each of multiple video frames of the input video. The system may then generate the sequence of sub-video frames of the sub-video by cropping the same bounding box from each of the multiple video frames of the input video.

In some cases, certain sub-videos may be “temporally overlapping”, e.g., such two or more of the sub-videos include respective sub-video frames that are extracted from the same video frame of the input video. This may occur, e.g., when the system tracks two different instances of target objects through the same video frame in the input video.

The system generates an output video that includes the sub-videos (508). For example, to generate the output video, the system may assign each sub-video to a respective slot in a video template that defines a format for combining the sub-videos. As part of generating the output video, the system may determine a respective score for each sub video (e.g., based on the sharpness of the sub-video), and select a proper subset of the sub-videos for inclusion in the output video (e.g., a predefined number of sub-videos with the highest scores). In some cases, the output video may concurrently show at least two of the sub-videos, while in other cases, the output video may show each of the sub-videos consecutively, e.g., one after another. As part of generating the output video, the system may assign each of one or more additional data elements (e.g., textual or image data elements, as described with reference to502) to a respective slot in the video template.

The output video generated by the system may be included in a digital component that is provided in response to a digital component request and subsequently presented alongside search results or on a third-party webpage.

Data processing apparatus for implementing machine learning models can also include, for example, special-purpose hardware accelerator units for processing common and compute-intensive parts of machine learning training or production, e.g., inference, workloads.