Spatio-temporal graphical user interface for querying videos

FIELD OF THE INVENTION

p-0002The present invention relates generally to processing videos, and more particularly to querying and presenting spatial and temporal characteristics of videos.

BACKGROUND OF THE INVENTION

p-0003Videos are available from a large number of sources, such as entertainment, sports, news, web, personal, home, surveillance, and scientific cameras. It is a problem to analyze and summarize such a wide variety of video content to locate interesting objects, events and patterns.

p-0004Automatic methods are known for extracting meta-data from videos. For example, video processing methods can detect, recognize, and track objects, such as people and vehicles. Most of those methods are designed for a particular genre of videos, for example, sports videos or newscasts. However, the number objects in a typical video can be large, and not all objects are necessarily associated with interesting events. Because of the complexity and variety of videos, it is often still necessary for users to further view videos and extracted meta-data to gain a better understanding of the context, i.e., spatial and temporal characteristics of the videos.

p-0005Typically, the videos or meta-data are manually processed either in space or alternatively in time. For example, a user might select a surveillance video acquired from a particular location, and then examine that video in detail only for a specific time interval to locate interesting events. Obviously, this requires some prior knowledge of the content, as well as the temporal dynamics of the scene in the video. It would be better if temporal and spatial characteristics of videos could be examined concurrently and automatically.

p-0006Therefore, there is a need for a method to analyze and manipulate videos and meta-data extracted from videos temporally and spatially by the automatic techniques. In particular, it is desired to provide improved visualization techniques that can reduce the amount of effort required to process videos and meta-data manually.

p-0007Video Summarization

p-0008Rendering video in space and time requires large processing, storage, and network resources. Doing this in real time is extremely difficult. Therefore, summaries and abstracts of the videos are frequently used. Video summarization is typically the first step in processing videos. In this step, features in the video are extracted and indexed. In general, summarization includes two processes: temporal segmentation and key-frame abstraction. Temporal segmentation detects boundaries between consecutive camera shots. Key-frame abstraction reduces a shot to one or a small number of indexed key-frames representative of the content. The key-frames can subsequently be retrieved by queries, using the index, and displayed for browsing purposes.

p-0009Commonly, the segmentation and abstraction processes are integrated. When a new shot is detected, the key-frame abstraction process is invoked, using features extracted during the segmentation process. The challenge is to generate a video summary automatically based on the context.

p-0010Summarization methods can either rely on low-level features such as color, e.g., brightness and dominant color, and motion activity, or more advanced semantic analysis such as object and pattern detection. While those methods are useful and powerful, they are inadequate for real-time analysis.

p-0011Video Visualization

p-0012Visualization methods commonly combine video frames and extracted information, e.g., meta-data. The meta-data are usually associated with individual frames, and can include bounding boxes for objects and motion vectors.

p-0013One method arranges a spatial view in the center of a display and temporal summarized views on the sides to simulate a 3D visualization that gives a sense of the past and future, Mackay, W. E., and Beaudouin-Lafon, M., “DIVA: Exploratory Data Analysis with Multimedia Streams,” Proceedings CHI'98, pp. 416-423, 1998. That method requires a large display screen and meta-data, and can only visualize data from one temporal direction, e.g., either the past or the future.

p-0014In another method, the user selects key-frames, and the video is presented temporally as a ‘time tunnel’ to quickly locate interesting events, Wittenburg, K., Forlines, C., Lanning, T., Esenther, A., Harada, S., Miyachi, T, “Rapid Serial Visual Presentation Techniques for Consumer Digital Video Devices”, Proceedings of UIST 2003, pp. 115-124, and [CS-3124]. While that method provides convenient presentation and navigation methods for videos, that method does not support queries.

p-0015Another method summarizes a video using opacity and color transfer functions in volume visualization, Daniel, G., and Chen, M. “Video visualization,” Proceedings IEEE Visualization 2003, pp. 409-416, 2003. The color transfer functions indicate different magnitudes of changes, or can be used to remove parts of objects. That method also requires meta-data.

p-0016Another method presents spatial relationships over time in a single image, Freeman, W., and Zhang, H. “Shape-Time Photography,” Proceedings of CVPR 2003, pp. 2003. That method requires a stationary stereo camera.

p-0017Another method presents the user with a detailed and view using successive timelines, Mills, M., Cohen, J. and Wong, Y. “A Magnifier Tool for Video Data,” SIGCHI '92: Proceedings of Human Factors in Computing Systems, Monterey, C A, pp. 93-98, 1992. The method uses a timeline to represent a total duration of a video, and the user can select a portion of the timeline and expand the selected portion to a second timeline. The timelines provide an explicit spatial hierarchical structure for the video.

p-0018Still Image Visualizations

p-0019Many techniques are used to visualize and understand still images. One method provides a ‘see-through’ interface called a ‘magic lens’, Bier, E. A., Fishkin, K., Pier, K., and Stone, M. C. “Toolglass and magic lenses: the see-through interface,” Proceedings of SIGGRAPH'93, pp. 73-80, 1993. A magic lens is applied to a screen region to semantically transform the underlying content as expressed by the pixels of the still image. The user moves the lens to control what region is affected. In practice, the magic lens is a composable visual filter that can be used for interactive visualization. The lens can act as a magnifying glass, zooming in on the underlying content. The lens can also function as an ‘x-ray’ tool to reveal otherwise hidden information. Multiple lenses can be stacked on top of one another to provide a composition of the individual lens functions. Different lens ordering can generate different result. The magic lens reduces screen space and provides the ability to view the entire context and detail of the still image concurrently. The lens enhances interesting information while suppressing distracting information.

p-0020The magic lens has been used in many applications, Bederson, B. B., and Hollan, J. “Pad++: a zooming graphical interface for exploring alternate interface physics,” Proceedings of UIST '94, pp. 17-26, 1994, Hudson, S., Rodenstein, R. and Smith, I. “Debugging Lenses: A New Class of Transparent Tools for User Interface Debugging,” Proceedings of UIST'97, pp. 179-187, and Robertson, G. G., and Mackinlay, J. D. “The document lens,” UIST'93, pp. 101-108, 1993.

p-0021However, the prior art magic lenses operate only in the spatial domain. It is desired to provide a magic lens that can operate concurrently in both the spatial and the temporal domain.

SUMMARY OF THE INVENTION

p-0022A method for querying and browsing videos using spatial and temporal components of the videos is provided. The method summarizes a video acquired of a scene spatially and temporally by specifying a spatial query and a temporal query. Frames of the video are selected according to the spatial query and the temporal query. Then, the selected frames are composited into an image that represents spatial and temporal characteristics of the scene.

BRIEF DESCRIPTION OF THE DRAWINGS

p-0023<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram of a system and method for querying and presenting spatial and temporal characteristics of videos; and

p-0024<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram of a spatio-temporal graphical user interface according to one embodiment invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

p-0025<figref idrefs="DRAWINGS">FIG. 1</figref> shows a system and method <b>100</b> according to one embodiment of our invention for analyzing, querying, browsing, and presenting a <b>102</b> video using spatial and temporal characteristics of the video. This embodiment combines spatial and temporal query components into a single query. The queries are used to select a spatial region and a temporal region of the video. The spatial region is a spatially contiguous set of pixels within a frame, and the temporal regions extend over temporally contiguous pixels in multiple adjacent frames. Then, the system presents a composite image that summarizes spatial and temporal characteristics of the selected regions.

p-0026Spatial Query

p-0027As shown in <figref idrefs="DRAWINGS">FIG. 1</figref>, a spatial query <b>111</b> specifies <b>110</b> a spatial region <b>101</b> of interest in the video <b>102</b> of a scene <b>103</b> acquired by one or more stationary or moving cameras <b>104</b>. It should be noted that the video can be acquired and processed in real-time, or the video can be stored, and the archived video can be ‘browsed’ off-line at some later time.

p-0028The user can select the spatial region manually, e.g., by ‘drawing’ on a frame <b>105</b> with a mouse and cursor, stylus, or other input device. Alternatively, the system can specify the region automatically using object, event, color detection, or other techniques.

p-0029Temporal Query

p-0030A temporal query <b>121</b> specifies <b>120</b> a temporal region <b>106</b> of interest in the video, e.g., a starting time, and an ending time or duration. The spatial query can also be specified <b>120</b> according to indexed frames. The temporal region can be selected automatically or manually. The user can select the temporal region manually by specifying start and stop times of the temporal region of interest, along with the number of total frames to consider. Alternatively, the system can specify the region automatically using moving object, event, color or motion detection techniques. For example, the temporal region includes the frames in which a particular object appears.

p-0031The temporal query can also be specified in terms of a trajectory to constrain the spatial query. The trajectory can be specified by a directed line <b>213</b>, see <figref idrefs="DRAWINGS">FIG. 2</figref>. The trajectory specifies a spatial region of interest and a pattern of movement so only frames including moving objects with similar trajectories are selected.

p-0032It should be noted that the spatial and temporal queries can be specified in any order or in parallel.

p-0033The spatial query and the temporal query can be combined <b>125</b> into a spatio-temporal query <b>122</b>. The spatio-temporal query is used to select <b>130</b> frames <b>131</b> from the video. The selected images can be filtered <b>145</b> according to the number of moving objects detected in the frames, for example. Frames without objects can be discarded as they only show the background and do not contribute any new information to the user. The exclusion of ‘empty’ frames improves the view by minimizing blurring or fading of the context.

p-0034Compositing and Rendering

p-0035We generate <b>140</b> a composite image <b>141</b> for rendering by ‘blending’ the selected frames. The composite image summarizes the spatial and temporal characteristics of the selected frames. When compositing <b>140</b> the selected frames, a predetermined order <b>143</b> and predetermined blending opacities <b>142</b> determine the appearance of the composite image. The composite image can be rendered <b>150</b> as an output image <b>151</b> on a display device <b>160</b>.

p-0036The composite image includes regions of the selected frames over time, i.e., multiple frames. The user can distinguish which regions come from which period of time. The user can then further explore that time period in greater detail.

p-0037Setting appropriate opacities for the selected frames is non-trivial when multiple sequential frames are composited. Conventional methods typically composite spatially fixed and unrelated images, Harrison, B. L., Ishii, H., Vicente, K. and Buxton, W. “Transparent Layered User Interfaces: An Evaluation of a Display Design Space to Enhance Focused and Divided Attention,” Proceedings of CHI'05, pp. 317-324, 1995, and Zhai, S., Buxton, W. and Milgram, P. “The partial-occlusion effect: Utilizing semi-transparency in 3D human-computer interaction,” ACM Transactions on Computer-Human Interaction, 3(3), pp. 254-284, 1996.

p-0038However, our frames are also temporally related. It is desired to make a frame of interest clearer while playing back video. To do this, we interpolate frames. Given the starting and ending time period, and the number of frames to composite, we determine a time interval between consecutive selected frames.

p-0039We determine the opacities using the Equations (1) and (2) and the overlaying order so that all images can be perceived with the same opacity value:

p-0040<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></munderover><mo>⁢</mo><mrow><msub><mi>α</mi><mi>i</mi></msub><mo>×</mo><mfrac><mi>i</mi><mi>n</mi></mfrac></mrow></mrow><mo>=</mo><mn>1</mn></mrow><mo>,</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>and</mi></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mrow><msub><mi>α</mi><mi>i</mi></msub><mo>×</mo><mfrac><mi>i</mi><mi>n</mi></mfrac></mrow><mo>=</mo><mrow><mrow><msub><mi>α</mi><mi>j</mi></msub><mo>×</mo><mfrac><mi>j</mi><mi>n</mi></mfrac><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>for</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>all</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>i</mi></mrow><mo>≠</mo><mi>j</mi></mrow></mrow><mo>,</mo></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><br /> where α_iis the opacity for an i^thlayer in the composite image, n represents the number of selected images, and i/n represents the weight of α_i. The multiplication ‘x’ provides a heuristic value, i.e., the user perceived value, for a certain layer. The condition when the user perceived all composite frames with the same opacity level is defined as a balanced view. Thus, we solve α_i=1/i. The equations maintain a continuous transparency spectrum, from the most recent frame, to a balanced view, and then to the oldest frame. The order of the compositing can be changed to better understand the temporal structure of the video.

p-0041For example, when compositing two frames, both frames are seen as clear as possible when the opacity value for the bottom frame is 1.0 and the opacity value for the top frame is 0.5. Then, the composite image is perceived as having an opacity of 0.5. With three frame, the composite image appear to be equally weighted when in fact the frames are weighted with α=1.0 for the bottom frame, 0.5 for the middle frame, and 0.33 for the top frame. Starting from the balanced view, the users can decide which frame, most recent or oldest should be most distinguished changing the opacity values.

p-0042Graphical User Interface

p-0043<figref idrefs="DRAWINGS">FIG. 2</figref> shows a graphical user interface (GUI) <b>200</b> according to one embodiment of the invention. The interface includes icons <b>110</b> for specifying the spatial query, e.g., virtual buttons. For example, the user can draw a rectangles <b>211</b> around a spatial region in a frame displayed in a play back window <b>212</b> of the video displayed on the left side of the interface.

p-0044Small vertical bars <b>236</b> show the temporal location of these frames. The inter-bar spacing indicates relative temporal positions, and the gray-levels of the bars indicate their relative opacities for compositing. In this example, the frames are spaced evenly. Recent frames are more heavily weighted by the opacities to make them clearer in the composite image. The order, opacities, and inter-frame spacing are described in greater detail below.

p-0045For the compositing, the interface includes a time pointer <b>231</b> indicating the current frame or starting time. The user can move this pointer, or the pointer moves automatically as the video is played back. A duration bar <b>231</b> is used to specify length of time period. The time period specified can span the current frame into the past and the future. The number of frames that are selected can also be shown.

p-0046An interval scrollbar <b>233</b> specifies the temporal query. The interval scroll bar is used to compress time and to ‘zoom’ in on a particular time period. That is, the interval bar controls a sampling of the video. For example, if the interval is set to ten, only every tenth frame is process, and an hour video can be viewed in six minutes. Thus, the interval scroll bar functions as a fast-forward.

p-0047An opacity bar <b>234</b> determines the relative opacities for the frames during the blended compositing. The blending gives a ‘ghosting’ effect as a preview of “future” or “past” events. For example, moving object in the past appear as transparent ‘ghosts’ while the object at the present location is shown clearly. Thus, it is possible where moving objects where in the past, now, and the future.

p-0048Thumbnail images <b>240</b> of the selected frames can be displayed on the right side of the interface. In the example shown, eight frames are composited. The user can interact with the thumbnail images using a mouse. Selecting a particular thumbnail plays back the video from that point, with colored rectangles consistent with the object histogram, around any moving objects in the frames.

p-0049An object histogram <b>250</b> indicates the number of moving objects, and when the objects occur in the video. The heights of the histograms indicate the number of objects, and different colors distinguish the different objects. Selecting one of the histograms positions the video to play back the frames including the object in the play back window <b>212</b>.

p-0050Although the invention has been described by way of examples of preferred embodiments, it is to be understood that various other adaptations and modifications may be made within the spirit and scope of the invention. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.