A video hosting web site receives uploaded video content and processes the video to determine ad surfaces. The ad surfaces comprise spatio-temporal regions of the video suitable for placement of advertisement such as background surfaces or other regions of low interest. The uploaded video and ad surfaces are stored to a video database that is accessible to viewers visiting the video hosting web site. When a shared video is requested, the video hosting site provides the requested video content together with the ad surfaces and advertisements. The advertisements are blended with the ad surfaces in the video at playtime so that the advertisements appear as part of the video scene. This allows the video hosting web site to present advertisements to the viewer without significantly distracting the viewer from the requested content.