KR100460222B1 - Structural index informaion description method for multimedia stream, progressive video indexing method and system - Google Patents

Abstract

The present invention relates to an automatic video indexing system that automatically extracts scene information, shot information, and their relationships, which are structural information of a video.

The present invention includes detecting a new shot (Shot _cur ) and a shot histogram, measuring the dissimilarity between shots in a match window for the shot _cur and setting the link between shots according to the dissimilarity, and linking a scene in which a link is set. Registering as a linked scene, updating the association information between scenes / labels / shots, shot _cur-τo separated from the current shot by the match window size based on the match window size, and before. Depending on whether the shots of Shot _cur-τo-1 belong to the Broken Scene and the Linked Scene, respectively, and whether the scenes to which each shot belongs are the same, no action is taken. Or merge scenes to which two shots belong, or perform scene boundary declaration, and record and store scene information including the determined scene / label / shot information in a persistent storage device. For scene information Releasing the allocated dynamic memory region; Progressive video indexing algorithm made, including.

Description

Structural index informaion description method for multimedia stream, progressive video indexing method and system

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a video indexing system for searching, browsing, and summarizing multimedia content. In particular, the present invention relates to automatic video for automatically extracting scene information, shot information, and their relationships, which are structural information of video content. An indexing system.

In the multimedia browsing system that selects the data desired by the user for the multimedia content, the most basic research is analyzing the video content, and most of the nonlinear video browsing functions are shot segmentation and shot clustering. It is based on technology.

1 illustrates a relationship between shot segmentation and shot clustering, and FIG. 2 illustrates a video content summarization method using a shot segmentation technique and a shot clustering technique. The video stream is divided into shot units by the shot segmentation module, and shot clustering builds scene information based on the shot segmentation result. Referring to the example shown in Fig. 2, nine shots detected in the video stream are summarized into one scene by the clustering process, and one scene is represented by three keyframes. This clustering process allows for a much higher level of video content summarization than shot segmentation.

In a digital video environment, a user wants to selectively view only desired content, and may also want highlights. In addition, they may want to selectively watch only a desired portion of a piece of content. Non linear video browsing means that users can select and select only the parts they want to watch the video, and selectively browse the video to provide summary information in a short time. A series of browsing methods that provide a means to quickly move to the desired part.

In this sense, a story board based on a keyframe interface has been proposed, a Table of Contents (ToC) interface has been proposed to provide structural information, and structure-based skipping using video information's structural information. And video skimming techniques that provide summary information about video content in a short time.

3 summarizes the relationship between shot clustering techniques and non-linear video browsing. The shot clustering process is a process of detecting a logical story unit (LSU), which is a logical story unit, from the detected shot.

Through the shot clustering process, one content is divided into multiple scenes, and each scene is composed of sub-scenes or connection of individual shots. That is, structural information of one video content is extracted through the shot clustering process.

The structural information of the extracted video content is used for video content summary using keyframes. Typical examples are the ToC interface and the storyboard interface. It is difficult to control the number of keyframes based on the semantic information of video content using only the result of shot segmentation.However, using the structural information obtained as a result of shot clustering, the number of keyframes to summarize a single content can be adjusted. It is free and can provide multimedia contents in a compressed format that sufficiently conveys the meaning of contents to the user.

The structural information obtained through shot clustering is used as a key input for the automatic video skimming and automatic highlighting system, which provides a summary of video content as well as a key frame interface. That is, the video skimming system or the auto highlight system uses the structural information of the video content to determine the section to be displayed for each scene and display the high level video skimming and highlighting which is difficult to provide only by the result of the shot segmentation. Can be.

As a conventional shot clustering technique, there is a method of detecting a scene based on the repetition of similar shots in the same scene based on the difference between shots. In this method, a virtual image is generated from two or three keyframes extracted from each shot and used as a reference for comparing shots, and block matching is used to compare two shots. That is, in comparing the virtual keyframe F _A obtained from the shot _A with the virtual keyframe F _B obtained from the shot B. The difference between images is obtained through block sequence matching between F _A and F _B , and this is determined as the difference between shots. Based on the difference between shots, the scene was detected based on the repetition of similar shots in the same scene.

The shot clustering algorithm described above is a very notable research result in a shot clustering method using no template. However, block matching is used to find the difference between shots, and the shift matching of the blocks is time-consuming and requires additional memory.

In addition, a specific method for simultaneously performing shot segmentation and shot clustering has not been presented. In addition, the method for the algorithm when using the limited memory for the concrete implementation has not been presented. In addition, by using the above-described method, a portion in which similar scenes, such as a dialogue scene, repeatedly occurs can be detected as one scene, but the number of scenes increases rapidly in a portion composed of scenes having different characteristics. As a result, it is difficult to provide a satisfactory summary of general video content.

In general, for real-time processing systems or set-top box applications, shot segmentation and shot clustering should be performed simultaneously, limited memory should be used, and the execution speed should be very fast. Therefore, the existing algorithm is not suitable for the implementation of a set-top box such as a personal video recorder (PVR) that can simultaneously record, index, and browse.

However, as digital broadcasts become more common and set-top boxes are available on the market that can record and play simultaneously, research on providing nonlinear video browsing functions such as video summarization and navigation using keyframes and automatic skimming and highlighting on these devices is available. Is needed. However, since the existing shot clustering researches have been interested in extracting structural information about digital content, there has been little research on the application of shot clustering techniques in systems such as set-top boxes, and the algorithms also include memory efficiency and simplified calculations. This was not considered intensively. As digital broadcasting becomes more common, users will demand more additional functions, and thus the demand for non-linear video browsing in set-top boxes will increase. Therefore, shot clustering algorithms and systems applicable to set-top environments are required.

The present invention provides a method of summarizing and navigating video content using keyframes, as well as video archives such as VOD servers, and real-time video indexing that can be used to provide automatic video skimming and highlighting. It is an object of the present invention to provide a method and a video indexing system.

In particular, the present invention is directed to: 1. Extracting structural information (scene / shot structure) of video content, 2. Shot clustering process using shot segmentation results, 3. Fast execution time (using processed data in the compressed domain), 4. Limited memory 5. The shot segmentation and shot clustering processes are performed simultaneously in real time, 6. The detected scene is divided into a linked scene and a broken scene. 7.Effective and efficient index for nonlinear video browsing. It is an object of the present invention to provide a video indexing system and a video indexing method characterized by structure generation.

Unlike the existing algorithms or systems, the video indexing algorithm and system of the present invention according to the above features extracts features from the video compression domain and indexes them, which is very fast, uses limited memory, and shot segmentation. (Shot segmentation) and shot clustering (Shot clustering) process can be performed at the same time, and another object to provide an advanced video indexing algorithm that can be performed simultaneously with the recording, decoding, playback, encoding of the multimedia stream.

In addition, as described above, the video indexing system of the present invention can be applied to a real-time system, and the shot clustering process uses feature data used in the shot segmentation process and shot information as a result of the shot segmentation, so that a separate feature extraction operation is performed. This eliminates the need for very fast execution times and provides a way to separate scenes into connected and disconnected scenes, providing key clues for keyframe summaries, video skimming, and automatic highlight generation of video content. In addition, the concept of labeling of scenes provides important clues for video skimming, skipping, and automatic highlight construction, thereby creating an effective index structure applicable to various nonlinear video browsing methods.

1 illustrates the concept of shot segmentation and clustering.

2 is a diagram illustrating an example of a video summarization method using shot segmentation and clustering;

3 illustrates the relationship between shot clustering and nonlinear video browsing.

4 is a view for explaining the concept of the connection scene and disconnection scene in the present invention;

5 summarizes the concept of clustering in the present invention.

6 is a flowchart of the video indexing algorithm of the present invention.

7 illustrates an example of performing a video indexing algorithm of the present invention.

8 illustrates an example of an index data structure according to the video indexing system of the present invention.

9 illustrates a configuration of a video indexing system of the present invention.

Progressive video indexing method of the present invention for achieving the above object,

Extracting a new shot (Shot _cur ) and a shot histogram as shot information from the video content; Setting an inter-shot link based on the dissimilarity between shots using the extracted shot information, registering a scene in which the link is set as a connection scene, and setting association information between a scene, a label, and a shot; Information on whether the shot (Shot _cur-τo ) and the previous shot (Shot _cur-τo-1 ), which are separated by the match window size from the current shot (Shot _cur ), belong to the disconnected scene or the connected scene, respectively. And merge scenes between scenes to which the two shots (Shot _cur-τo and Shot _cur-τo-1 ) belong to each other according to whether the scenes to which each shot belongs is the same or different, or declare a scene boundary. And a step; Storing the merged or bounded scene information; Progressive video indexing method comprising a.

In addition, in the progressive video indexing method of the present invention, the dissimilarity measurement measures _{dissimilarity} between shots in a match window with respect to the shot and shots having a minimum dissimilarity using the measured dissimilarity. After detecting (Shot _min ), if the dissimilarity is less than a certain threshold, the link between shots is set and the scene in which the link is set is registered as the connection scene.

In addition, in the progressive video indexing method of the present invention, the scene is defined as a sequence of one or more consecutive shots, and the label is defined as a sequence of shots having a non-similarity between shots within a scene below a specific threshold (τ _shotdiff ), One label is characterized by including one or more shots.

In the progressive video indexing method of the present invention, the scene is represented by a list of labels, and the labels are represented by a list of shots.

In addition, in the progressive video indexing method of the present invention, the connected scene means a scene having a label having two or more shots as a component in the scene, and the disconnected scene has a label having two or more shots as a component in the scene. Characterized by a scene that does not.

In addition, in the progressive video indexing method of the present invention, the matching window from the detected time of the current shot (Shot _cur) in the FIFO structure array shot existing within several shots of the previous offset (τ _o) are in chronological order Characterized in that made.

In addition, in the progressive video indexing method of the present invention, a single scene, a single label, and single shot information are added to the newly input shot (Shot _cur ), and a newly input single scene / single label through link setting operation is added. It is characterized by updating the single shot information.

In the progressive video indexing method of the present invention, when configuring a link between the reference shot and the shot having the least dissimilarity Shot _min , two shots are assigned to the same label, and the label information is updated. Merge scenes containing shots, update the scene information by marking the scene with the new shot added as a linking scene, if no link is established, assign a new label to the new disconnected scene and assign the reference shot to it It is characterized by recording the information assigned.

Also in this the progressive video indexing of the invention method, the current shot each (Shot _cur) from matched window size shot separated by (Shot _cur-τo) and before the shot (Shot _cur-τo-1) with respect to the Determine whether the scene to which the shot belongs is a connected or disconnected scene, and determine whether the scene to which the two shots (Shot _cur-τo and Shot _cur-τo-1 ) belong are the same or different scenes. If the scene belongs to the scene (Shot _cur-τo-1 ), the scene (Shot _cur-τo ) to the scene to which the scene belongs to merge (merge), one of the two shots belong to the disconnect scene and the other If it belongs to the connected scene, it declares that a scene boundary has occurred, and changes the scene information to which the shot (Shot _cur-τo-1 ) belongs to a state that can be stored in the storage device. Both shots belong to the connected scene and two If the scene to which the shot belongs is the same, nothing happens, and both shots If the scene belonging to the connected scene and the two shots are different, the scene boundary is declared, and the scene information to which the shot (Shot _cur-τo-1 ) belongs is changed into a state that can be stored in the storage device. .

Further, in the progressive video indexing method of the present invention, in storing the scene information after the scene integration or scene boundary declaration, when using a policy of storing the scene information in a permanent storage device every time a new scene is registered, a new scene is determined. Store scene information for the storage device; In case of using the policy of storing the determined scene information at once after the predetermined scene information is filled, the information about the determined scenes is stored in the storage device only when the predetermined scene information has been registered in the predetermined amount or more. And branching to a shot information extraction step.

In addition, the progressive video indexing system of the present invention for achieving the above object,

Clustering control means for performing video indexing according to an external input and a clustering situation; Scene boundary detection means for scene boundary detection determination by clustering control means; Link setting means for measuring a dissimilarity of two shots in a shot clustering algorithm and establishing a link and updating scene / label / shot information of a memory based on the dissimilarity of two shots; Shot index determining means for extracting shot information from the media file; Feature extraction means for extracting a feature for segmentation and clustering by decoding the media file for shot index extraction; Shot index input means for managing a shot index input from the shot index determination means and informing the clustering control means; Managing the shot index input from the shot index input means, the scene / label index generated and updated from the link setting means, the scene boundary detecting means, and recording the index information in the storage device when necessary according to the control signal of the clustering control means; Indentation management means in charge; It is a progressive video indexing system characterized by extracting the structure index information describing the information about the scene / shot / label and the relationship between them by performing the shot segmentation and shot clustering at the same time, including.

Also, in the advanced video indexing system of the present invention, the feature extracting means receives information on media to be indexed by the video indexing system from the clustering control means, extracts features required for video indexing, and shot index when the data is ready. The data is transmitted to the determining means.

In addition, in the progressive video indexing system of the present invention, the shot index determination means receives a shot index extraction command from the clustering control means, extracts necessary information using the feature extraction means, transfers it to the shot index input means, and a new shot. It is characterized in that it is notified to the shot index input means whenever this is detected or when the shot segmentation on the media ends.

In addition, in the advanced video indexing system of the present invention, the shot index input means notifies the clustering control means after registering a new shot to the index management means when a new shot is input, and the clustering control means that the shot segmentation is terminated. It is characterized by informing.

Further, in the progressive video indexing system of the present invention, the clustering control means sets a link through the link setting means based on information about the shot input from the shot index determining means, and the scene / label / shot managed by the index management means. Updates information, controls scene boundary detection means to check whether a scene boundary has occurred, and performs operations such as merging and boundary declaration for scene boundary inspection points to index information between scenes / labels / scenes in memory. Control to update through the management means, and when the scene boundary declaration occurs from the scene boundary detection means, control to store information on the scene in which the scene boundary is declared in the storage device by using the index management means again. do.

Further, in the advanced video indexing system of the present invention, the index management means stores the determined scene information in the storage device every time a scene boundary is declared according to a storage policy, or simultaneously extracts the scene information after a predetermined amount of scene information is extracted. It is characterized in that the memory structure for the stored scene information is automatically released.

In addition, the video index information description method of the present invention for achieving the above object, the multimedia content;

Defined as a list of scenes, which are a continuous sequence of one or more shots, each scene with interval information including start and end points, shot list information for storing one or more shots in the scene, and one in the scene It is a method of describing the structure index information for a multimedia stream, including label list information for storing the above label and flag information for designating whether the connection scene or the disconnect scene is included.

In addition, in the method of describing the structural index information for the multimedia stream of the present invention, the components of the shot list are individual shots, and the shot information is described using section information including a start time point and an end time point.

In addition, in the method of describing the structural index information for the multimedia stream of the present invention, the components of the shot list are individual shots, and the shot information includes section information including a start point and an end point, and keyframe information about the shot. It is characterized by.

In addition, in the method of describing the structure index information for the multimedia stream of the present invention, the component of the label list is an individual label, and the label information is a list of shots to which the corresponding label is assigned in the scene.

In addition, in the method of describing the structural index information for the multimedia stream of the present invention, the component of the label list is an individual label, and the label information includes a list of shots assigned the label in the scene and keyframe information on the label. It is characterized by what is described.

In addition, in the method for describing the structural index information for the multimedia stream of the present invention, the scene information is characterized by further including keyframe information for representing the scene.

As described above, the video indexing method according to the progressive video indexing system capable of extracting structural information according to the present invention, that is, the shot clustering method, includes a shot information extracting step, a link setting step, a scene boundary determination step, and determined scene information, such as a disk. And storing the data in a storage device.

More specifically, the first step of extracting the shot information is a step of receiving a result of the shot segmentation algorithm as an input, and the second step of setting a link is a match window (ie, a predetermined range) in the memory. The link is formed for the newly detected shot by measuring the dissimilarity between the shots and the shot detected in the first step, and the label is configured by setting the label information and the scene information. The third step, the scene boundary determination step, is a match. Detecting the scene boundary between the shot (Shot _cur-τo ) and the previous shot (Shot _cur-τo-1 ) that is separated by the match window size from the current shot based on the window size, the fourth step is the storage step Command to store the scene information on the disk that will no longer change when a scene boundary is declared, and the shot (Sh) to receive the next shot. ot _{cur- tau o-1)} is released so that the system can be efficiently managed to operate on the limited memory.

The video indexing method of the present invention uses the shot segmentation information and the shot histogram information in the first step, and sets the match window of the memory in the second step so that the memory can be limited regardless of the shot sequence. In the third step, the scene boundary is continuously determined, and the fourth step is implemented by an advanced algorithm that stores a changeable index in the main memory and ensures that a fixed index is stored in a permanent storage device such as a disk.

The following summarizes the video indexing method of the present invention and describes each step in more detail.

[Step 1]: Detecting a new shot (Shot _cur ) and a shot histogram (ShotHist (Shot _cur )) using a shot segmentation algorithm.

The first step is a process of detecting a new shot (Shot _cur ) using a shot segmentation algorithm, and detecting a shot histogram (ShotHist (Shot _cur )) for the detected shot.

Shot segmentation generally detects individual shots by detecting the continuity and discontinuity of motion, color distribution, audio, etc. in a stream and determining them collectively. For reference, shot clustering is generally a process of detecting a scene in which a video stream is a logical story unit by using similarities between shots or detecting a specific event centered on the basis of genre-dependent knowledge. The shot histogram can be obtained by two methods in the present invention, a first shot histogram, which is an "average histogram of color histograms of images sampled on a certain basis in one shot," and "sampling on a certain basis in one shot." The second shot histogram, which is the color histogram of the representative representative image, is obtained.

[Second Step]: Assigning a single break scene / single label / single shot structure to the shot obtained by the input of the first step, and measuring dissimilarity between shots obtained by the input of the first step and shots in the match window the and belongs to establish a link (link) information on the dissimilarity between shots with the minimum of the dissimilarity (shot _min) is not more than a certain threshold, the newly detected shots (shot _cur) and the shot (shot _cur) label And updating scene information. If a link is established, the scene to which the shot belongs is set as a linked scene.

First, a method of measuring dissimilarity between shots in the second step of the present invention will be described.

[Measurement of Similarity of Two Shots]

The most basic step for shot clustering is measuring similarity and dissimilarity between two shots. Although various methods may be used to measure similarity / dissimilarity between shots, the present invention uses a shot histogram for measuring similarity and dissimilarity between two shots. The histogram of the shot histogram can be obtained by two methods. As described above, the first shot histogram is "the average histogram of the color histograms of the images sampled on a certain basis in one shot", and the second shot histogram is " Color histogram of a representative image sampled on a certain basis in one shot.

The reason why we chose the shot histogram as a criterion for measuring similarity and dissimilarity between two shots is that since the color histogram of the image is already extracted during the shot segmentation process, the shot histogram for each shot can be efficiently obtained. Because it is very fast. Equation 1 below is the mathematical definition of the first shot histogram.

At this time, Hist (A) + Hist (B);

(Hist (A) + Hist (B)) [m] = (Hist (A)) [m] + (Hist (B)) [m] l = 0,1,2, ..., n-1; Is defined as

Both the shot histogram or the histogram are defined as an array, and for the purposes of the present invention, Hist (A) means a color histogram for frame A, ShotHist (S) means a shot histogram for shot S, and ShotHist ₁ ( S) means the first shot histogram for shot S, and ShotHist ₂ (S) means the second shot histogram for shot S.

the i-th shot is the number of frequency for the color having the m-th color index that appears in the title, and d j the number of the sampled image in Shot _i and, (Hist (A)) [ m] is the image A to Shot _i The total number of color indices of the color histogram is n.

The first shot histogram (ShotHist ₁ (Shot _i )) for the i th shot (Shot _i ) is each image frame (F _k : k = 1,..., extracted with the color histogram in the shot (Shot _i ) for shot segmentation. .., j) is the average histogram of the image histogram (Hist (F _k )), and the second shot histogram (ShotHist ₂ (Shot _i ) = Hist (F _R )) is the histogram for the particular image sampled within the shot. to be. The image histogram Hist (F _k ) is defined as an array, where each index means a color index, and its value refers to the frequency of the color corresponding to each color index in the image. Therefore, ShotHist (Shot _i ) is a data structure showing the distribution of how many colors appear in the _i shot (Shot _i ).

In the present invention, not all frames in the shot are used to extract the shot histogram. F _k means only an image whose color histogram is extracted by sampling according to a predetermined rule for shot segmentation. For video content using a compression scheme such as MPEG, only I frames in a shot are used as F _k . Also, color histogram is extracted from DC image for fast color histogram extraction without restoring the original image for fast algorithm.

In this way, based on the shot histogram extraction to obtain the degree of similarity and dissimilarity between the two shots, Equation 2 is two shot claim a first dielectric based on a first shot Histogram (Shot _i and Shot _j) Apostles (ShotDiff ₁ ( Shot _i , Shot _j )) and a second dissimilarity (Shot Diff ₂ (Shot _i , Shot _j )) based on the second shot histogram.

In this way, the dissimilarity between shots ShotDiff (Shot _i , Shot _j ) may be obtained using the first dissimilarity or the second dissimilarity. The choice of how to use the first dissimilarity diagram or the second dissimilarity diagram may be changed by the clustering algorithm, the situation of the system, or an external input. Equation 3 shows how to obtain the similarity between shots 'ShotDiff (Shot _i , Shot _j )'.

Here, if the sum of each bin of the image histogram is 1, the sum of each bin of the shot histogram is also 1, and the dissimilarity between shots ShotDiff (Shot _i , Shot _j ) is a value from 0 to 2 at the minimum. Have

As can be seen from Equation 3, the dissimilarity between shots (ShotDiff (Shot _i , Shot _j )) is used only the first dissimilarity (ShotDiff ₁ (Shot _i , Shot _j )), or second dissimilarity (ShotDiff ₂ (Shot) _i , Shot _j )) or by applying weights (α, β) to both, that is, (α × ShotDiff ₁ (Shot _i , Shot _j ) + β × ((ShotDiff ₂ (Shot _i ,) Shot _j ) is used.

As described above at the beginning of the second step of the present invention, the present invention defines and uses the concept of a connected scene and a disconnected scene for a scene.

For shot clustering according to the video indexing method of the present invention, a linked scene and a broken scene are defined as follows. A connected scene is a scene in which similar scenes appear repeatedly in a scene, and a disconnect scene is a scene that is not. For example, in the case of a conversation scene, a connection scene is used a lot, and a disconnect scene is used for an action scene or a fast story development.

In addition, the concept of a label (Label) is defined to explain the clustering algorithm of the present invention. The label is defined as "sequence set of similar shots within a certain shot offset within one scene", and the scene is defined as "sequence of labels".

A concatenation scene is a scene with one or more labels defined by two or more shot sequences, and a disconnect scene is an unlabeled scene defined by two or more shots.

4 is a view for explaining a scene, a label, a connection scene, a disconnect scene, and the like of the present invention. In FIG. 4, each of A1, A2, A3, B1, ..., etc. denotes individual shots, and FIG. 4 (a) is an example of the structure of the three-linked scene, and FIG. 4 (b). Is an example of the structure of a disconnected scene with six labels and six shots (A, B, C, D, E, F). Referring to (a) of FIG. 4, a link is set for each individual shot, and a label is used to express the concept.

As such, the above-described link establishment step is necessary for shot clustering of the present invention. The following describes how to set up a link.

Once a new shot is entered into the shot clustering process, a single scene / single label / single shot structure is assigned. The link setting between shots uses the method of measuring dissimilarity between shots and the shot offset described above. The shot offset between the i-th shot Shot _i and the ik-th shot Shot _ik is defined as k = i- (ik). . In the indexing algorithm of the present invention, when the offset k between the i-th shot Shot _i and the ik-th shot Shot _ik is within a certain range τ _o and the _{dissimilarity} of the shot is within a certain range τ _shotdiff . Set a link between the i-th shot Shot _i and the ik-th shot Shot _ik ; otherwise, do not set a link between the i-th shot Shot _i and the ik-th shot Shot _ik . Equation 4 below summarizes the method for establishing a link between two shots. The two shots in which the link is set belong to one label and belong to the same scene.

As described above, an operation for updating a scene and a label to which a shot, which is newly input in the shot clustering process, belongs is performed in the link setting step. That is, once the link is established according to the condition of Equation 4, the label ID for the i-th shot is updated with the same label ID as the i-kth shot, and the shots i-k to i belong to the same scene. If the shots of l to m where the relationship of l ≤ ik ≤ m are registered as a scene by the previous clustering process, the shot sequence from l to i become one scene, and the i th shot is It belongs to this scene.

Since the algorithm of the present invention designates the number of shot information to be managed in advance in advance, it can be implemented on a system using limited memory.

5A is an example of configuring and using a FIFO that limits shot memory to six shots. The size of the shot memory may vary for implementation environment and algorithm performance.

[Step 3]: The scene between a shot _cur-τo and a previous shot (Shot _cur-τo-1 ) separated from the current shot by the size of the match window based on the size of the match window. Check the boundary. Skip, Scene Merge, Scene Bound, depending on whether the two shots belong to the disconnected scene, to the connected scene, to the same scene, or to another scene. Perform the setting operation.

In the third step of the present invention, a method and an operation of inspecting a scene boundary will be described.

As described above, the video indexing algorithm of the present invention is characterized in that the shot segmentation operation and the shot clustering operation are simultaneously performed. From the point of view of the shot clustering algorithm, newly detected shots are continuously input by the lower shot segmentation operation. Based on this, the shot clustering process establishes a link between the shots and detects a scene break.

5 (a) and 5 (b) illustrate the algorithm of the present invention. When a new shot is input to the shot clustering algorithm by the shot segmentation algorithm, the shot clustering algorithm checks whether similar shots exist for shots having an offset within a range (match window) as described above.

Match measure the dissimilarity between the standard shots (Shot _cur) for each of the shots in the window, and if that dissimilarity is the smallest shots (Shot _min) within a dissimilarity a certain threshold (τ _shotdiff) with reference shots (Shot _cur) and the dissimilarity of the most establish a link between small shots (shot _min) is determined by the label ID of the reference shot with the smallest dissimilarity label ID (ID) shot (shot _cur) (shot _min), and the dissimilarity of the most The shot sequence from the scene to which the small shot (Shot _min ) belongs to the reference shot (Shot _cur ) is determined to belong to one scene and the scene is regarded as the connected scene.

In FIG. 5A, when the k + 6 th shot (Shot _cur = Shot _{k + 6} ) is input, the dissimilarity between the reference shot Shot _{k + 6} and the shots Shot _{k + 1} to Shot _{k + 5} is measured. . If the k + 4th shot Shot _{k + 4} is determined to be the minimum _{dissimilarity} shot Shot _min and the _{dissimilarity} is smaller than the predetermined threshold τ _shotdiff , the reference shot Shot _{k +} is shown in FIG. 5A. ₆ ) and the k + 4th shot (Shot _{k + 4} ), and the k + 1st to k + 5th shot (Shot _{k + 1 to} Shot _{k + 5} ) Since the scene is registered as a scene and the scene is defined as the connected scene, the k + 1st shot to the k + 6th shot (Shot _{k + 1} to Shot _{k + 6)} are registered as one scene.

However, based on shots (Shot _cur) and its dissimilarity with the smallest shots (Shot _min) and the dissimilarity a certain threshold (τ _shotdiff) is greater than the reference shots give a new scene and a new label for the (Shot _cur) and the new scene Is recorded as the disconnect scene.

With respect to the newly detected based on shots (Shot _cur) When all the settings and the link label assigned work, as the shot away matches in the current window size shots (Shot _cur-τo) and the previous shot (Shot _{cur-τo- 1)} the thin lines between detection.

The scene boundary detection method includes information about whether two shots are determined to be connected or disconnected scenes, and whether two shots (Shot _cur-τo and Shot _cur-τo-1 ) belong to the same scene. Use or not. In some cases, you can declare a scene boundary, merge two shots into the same scene, or wait for input of the next shot without a separate operation.

Therefore, for the video indexing algorithm of the present invention, information about the relationship between the shot and the label and the relationship between the label and the scene should always be described in the memory. In addition, when a new shot is detected, the video indexing algorithm of the present invention configures a progressive algorithm by detecting the scene boundary with respect to the previous shot as large as the match window size without checking the scene boundary with respect to the detected shot. It is done.

The scene boundary detection method described so far is described in more detail with reference to FIG. 5B as follows.

[Case 1]: When two shots (Shot _cur-τo and Shot _cur-τo-1 ) both belong to the disconnect scene.

In this case, merge the two shots into the same scene. Merge operations (Merge Operarion) is achieved by adding a current of shots (Shot _cur) match window sizes as shots (Shot _cur-τo) away from the information on the previous shot _{(Shot cur-τo-1)} .

The reason for doing this merge is to make the video content more compressed and summarized by composing an action scene or a quick story summary section into a single scene.

[Case 2]: One of two shots (Shot _cur-τo , Shot _cur-τo-1 ) belongs to the disconnected scene and one belongs to the connected scene.

In this case, the link setting operation for the newly detected shot and the shot (Shot _cur-τo-1 ) is not performed even in the case of the subsequent algorithm execution, and two shots (Shot _cur-τo and Shot _cur-τo-1 ) are performed. Since they belong to different scenes, they no longer belong to the same scene. Therefore, at this time, it is possible to declare that a scene boundary exists between two shots and store information of the previous scene (the scene to which the shot _cur-τo-1 belongs) in the persistent storage device.

[Case 3]: When two shots (Shot _cur-τo and Shot _cur-τo-1 ) both belong to the connected scene.

The operation in this case is divided into two cases. That is, two shots (Shot _cur-τo , Shot _cur-τo-1 ) belong to the same scene and different scenes, and two shots (Shot _cur-τo , Shot _cur-τo-1 ) If it belongs to this same scene (Case3-1), no operation is performed. If two shots belong to different scenes (Case3-2), the link setting process between the two shots is no longer performed. You can declare that there is a scene boundary and store the information from the previous scene (the scene to which the shot _cur-τo-1 belongs) in persistent storage.

[Step 4]: After performing the third step, the previous shot (Shot _cur-τo-1 ) is released from the shot memory, and the scene to which the previous shot (Shot _cur-τo-1 ) belongs when the scene boundary is declared. Save the information to permanent storage and free memory information for the scene.

The first to fourth steps of the video indexing method of the present invention described above may be represented by the flowchart of FIG. 6.

The shot clustering process initializes the environment variables τ _o , τ _shotdiff described above in the start phase and other variables (cur = 0) (step 601).

Shot clustering, and waits until the required shot segmentation information in the shot segmentation engine after detecting a shot segmentation engine is new shot (Shot _cur) or reached the end of the media (step 602). If a new shot is detected, the process branches to step 603 to perform a shot clustering operation. Otherwise, the process branches to step 613 to finish clustering on scene, label, and shot information remaining in the memory. The operation after branching to step 613 is performed when the total number of shots detected in the media is τ _o or less (ie τ _o <= cur) or when no more new shots are present at the end of the clustering process. Subroutine.

That is variable corresponding to the number of shot at step 613, the current shot number (cur) than τ _o is "0" after the user set to τ _o is step 614 branches to τ _o = τ _o -1 in step 615. If there is more than If not small, the operation branches to step 608, and if smaller than '0', the operation branches to step 618, and the scene information remaining in the memory is stored in the permanent storage device (disk) and terminated. In step 613, the current shot number (cur) is If τ _o or less, branch to step 616 and set τ _o = cur-1. In step 617, it is determined whether the current shot number (cur) is '0'. If so, the process branches to step 618, and the scene information remaining in the memory is stored in the persistent storage and then terminated.

On the other hand, if the clustering process branches to step 603, it increments the current shot number (cur) and adds a single break scene / single label / single shot structure for the shot to memory. In the memory shot list, a shot (Shot _min ) having the least similarity between shots with a newly detected shot (Shot _cur ) is found. Here I found compared to the minimum dissimilarity shot (Shot _min) and the syatgan dissimilarity ShotDiff (Shot _cur, Shot _min) a predetermined threshold value (τ _shotdiff) (step 604).

Establish a link between the minimum dissimilarity shots (Shot _min) and the syatgan dissimilarity ShotDiff (Shot _cur, Shot _min) is less than a certain threshold (τ _shotdiff) branches to step 605 shots (Shot _cur, Shot _min), and The label information and the scene information associated with the shot are updated, otherwise branching to step 606 to determine if the scene boundary needs to be examined. That is, by comparing the number of shots ShotNum with τ _o , if the shot boundary detection step requirement is satisfied (ShotNum> τ _o ), the clustering process branches to step 607; otherwise, branches to step 602 and the next shot is Wait for detection or wait for an end of segmentation on the media.

Steps after step 607 are steps of detecting a scene boundary and performing an appropriate operation accordingly. First, in step 607, it is determined whether the two shots of the scene boundary detection belong to the connected scene or the disconnected scene, and whether the two shots belong to the same scene or the other scene, Cases (Case1, Case2, Case3-1, Case3-2) are determined (step 608), and each operation is performed from step 609 according to each case (Case) determined by step 608.

That is, in step 607, L1 = IsLinked (Shot _cur-τo-1 ), L2 = IsLinked (Shot _cur- τo), bSame = ISSame (SceneOf (Shot _cur- τo _-1 ), SceneOf (Shot _cur- τo)) Set each case (Case1, Case2, Case3-1, Case3-2) according to the value of L1, L2 (True or False) in the next step 608, and in the next step 609 In this case, the operation is performed in each case.

Here is the operation by case.

First, when both shots belong to the disconnected scene (Case1), the process branches to step 610 and the subsequent shots (Shot _cur-τo ) in the scene to which the previous shot (Shot _cur-τo-1 ) belongs in time between the two shots. If one of the two shots belongs to the disconnected scene and one belongs to the connected scene (Case2), the process branches to step 611 to determine the scene boundary between the two shots (Shot _cur-τo and Shot _cur-τo-1 ). It declares that it exists, and branches to step 612 to store the information of the scene to which the previous shot (Shot _cur-τo-1 ) belongs to the disk and release the corresponding memory to which the shot (Shot _cur-τo-1 ) belongs.

If both shots belong to the connected scene and the two scenes are the same scene (Case3-1), no operation is performed, and both shots belong to the connected scene and the scene to which each shot belongs is different. In case 3 (Case3-2), the process branches to step 611 to declare that a scene boundary exists between two shots (Shot _cur-τo and Shot _cur-τo-1 ), and to step 612, the previous shot (Shot _{cur-τo). -1} ) Save the information of the scene to disk and release the memory.

If all of the above operations are performed, the process branches to step 602 to wait for the next shot to be detected or to wait for the end of segmentation for the media to be declared.

7A and 7B are diagrams for explaining an execution example of an algorithm of the video indexing system of the present invention. For explanation, it is assumed that an offset for checking dissimilarity between shots is '5'. Looking at the application of the algorithm step by step using Figure 7 as follows.

In Figs. 7A and 7B, A, B, C, ... are shots, serial numbers 1, 2, 3, ... shown below the shots are shot numbers, and L are links, and the match windows described above are respectively shown. Notation.

[a] When Shot ₁ is input (step a in FIG. 7A)

There is no previous shot, so there is no need to set up links or check scene boundaries. Information about this shot is added as single scene / single label / single shot information, and there is a total of 1 disconnect scene in memory.

[b] When Shot ₂ is input (step b in Fig. 7A)

In this case, since there is no matched shot in the match window, it is added as single scene / single label / single shot information, and there are two disconnected scenes in memory, and there is no need to perform scene boundary checking.

[c] When Shot ₃ is input (step c in Fig. 7A)

In this case, since there is no matched shot in the match window, it is added as single scene / single label / single shot information, and there are three disconnected scenes in memory, and there is no need to perform scene boundary checking.

[d] When Shot ₄ is input (step d in FIG. 7A)

In this case, since there is a matched shot (Shot ₁ ) in the match window, register Shot ₁ to Shot ₄ as one scene and display it as a linking scene (link setting), and a total of 1 linking scene (Shot ₁ to Shot) in memory. ₄ ) is present and there is no need to perform scene boundary checking. That is, three labels exist in the connection scene (A, B, C).

[e] When Shot ₅ is entered (step e in Fig. 7a)

The shot match in the matching window also in this case (Shot ₃₎ is so Shot ₃ ~ Shot ₅ is present in a scene, in which it previously Shot ₁ ~ Shot ₄ is already registered as a scene in Shot ₁ ~ Shot Register ₅ as a scene. In addition, there is a total of one connected scene (Shot ₁ to Shot ₅ ) in memory, and there is no need to perform scene boundary checking. The result is three labels in the connection scene (A, B, C).

[f] When Shot ₆ is entered (step f in Fig. 7a)

In this case, there are no matched shots in the match window, so it is added as single scene / single label / single shot information, and there is a total of one connected scene (Shot ₁ to Shot ₅ ) and a total of one broken scene (Shot ₆ ) in memory. No need to do scene boundary checking.

[g] When Shot ₇ is entered (step g in FIG. 7A)

In this case, since there is no match in the match window, we add it as single scene / single label / single shot information and check the scene boundary between the two shots (Shot ₁ and Shot ₂ ), both shots in the same connected scene. There is no operation of the scene boundary check result because the scene belongs to and the two shots belong to the same scene. That is, the case described above (Case3-1). There are a total of one connected scene (Shot ₁ to Shot ₅ ) and two disconnected scenes (Shot ₆ and Shot ₇ ) in memory.

[h] When Shot ₈ , Shot ₉ is input, and Shot ₁₀ is input (step h in FIG. 7B)

In this case, there are no matched shots in the match window, so we add them as single scene / single label / single shot information, we need to check the scene boundary between Shot ₄ and Shot ₅ , and both shots belong to the same connected scene and Since the scene to which the shot belongs is the same, there is no operation of the scene boundary check result (Case3-1). There will be a total of one connected scene (Shot ₁ to Shot ₅ ) and five disconnected scenes (Shot ₆ to Shot ₁₀ ) in memory.

[i] When Shot ₁₁ is entered (step i in Fig. 7b)

In this case, since there are no matched shots in the match window, it is added as single scene / single label / single shot information, and a scene boundary check between Shot ₅ and Shot ₆ is performed so that Shot ₅ belongs to the connected scene and Shot ₆ is in the disconnect scene. Declare the scene boundary because it belongs (Case2). After declaring the scene boundary, information about the scene to which Shot ₁ to Shot ₅ belongs is written to disk, and the memory information for the scene to which Shot ₁ to Shot ₅ belongs is released. ((Shot ₆ to Shot ₁₁ ) is present.

[j] When Shot ₁₂ is input (step j in Fig. 7B)

In this case, there is no shot matches in the Match window, so adding a single thin single / label / single-shot information, and a thin border checks between Shot ₆ to Shot ₇ makin made, both the Shot ₆ to Shot ₇ belong to disconnect the scene ( Case1) Shot ₇ information is added to the scene to which Shot ₆ belongs, and there are six disconnected scenes (Shot ₆ + Shot ₇ , (Shot ₈ to Shot ₁₂ )) in memory.

[k] When Shot ₁₃ is input (step k in Fig. 7b)

In this case, because there is a shot (Shot ₉₎ matching in the matching window, and registers the Shot ₉ ~ Shot ₁₃ as one scene, and displays the information to connect the scene, in the thin boundary checking between Shot ₇ and Shot _8, and Shot ₇ Since all Shot _8s belong to the disconnect scene (Case1), we add the information of Shot ₈ to the scene to which Shot ₇ belongs, and there is a total of one disconnect scene (merge of Shot ₆ to Shot ₈ ) and a total of one connected scene (Shot) in memory. ₉ ~ Shot ₁₃ ) is present.

[l] When Shot ₁₄ is input (step l in Fig. 7b)

In this case, the shot match in the matching window (Shot ₁₁₎ is so Shot ₁₁ ~ Shot ₁₄ is to present a single scene, in which it previously Shot ₉ ~ Shot ₁₃ is registered as a scene in Shot ₉ ~ Shot ₁₄ Register as a scene. A scene boundary check is performed between Shot ₈ and Shot ₉ , and declares scene boundaries because Shot ₈ belongs to the disconnect scene and Shot ₉ belongs to the connected scene (Case2). After declaring a scene boundary, save the information about the scene to which Shot ₆ to Shot ₈ belongs to the disk, and release the memory information for the scene to which Shot ₆ to Shot ₈ belongs, and as a result, the memory contains a total of one connected scene (Shot ₉ to Shot). ₁₄ ) It exists.

Using the video indexing algorithm proposed in the present invention described above, an index structure is stored in a file. FIG. 8 illustrates an index structure in which structural information obtained as a result of performing the algorithm of the present invention is represented.

The content description 80 of the content is defined as a list of scenes (Scene ₁ , Scene ₂ , ..., Scene _k , Scene _{k + 1} ) 81, and each scene is Section information [Start _k , End _k ], Scene type flag, ie Linked / Broken, List of Shot, List of Label, Keyframe List KFs), and the keyframe list may be omitted in some cases.

The section information of the scene indicates the start time information (Start _k ) and the end time information (End _k ) on the media of the scene, and the scene type flag is a flag indicating whether the scene is linked or disconnected. to be. A list of lower shots refers to a list of shots belonging to a scene, and a list of labels is a list for representing information of labels extracted by a shot clustering process.

The components of the list of shots are individual shots (S ₀ ^k , S ₁ ^k , S ₂ ^k , ..., S _m ^k ) 84, and the components of the list of labels are Label (L ₀ ^k , L ₁ ^k , L ₂ ^k , ..., L _n ^k ) (2). The shot information 85 is defined by section information (eg, Start ₂ ^k , End ₂ ^k ) and a corresponding key frame Shot KF, and key frame information Shot KF may be omitted. In addition, the information 83 of the label is defined as a corresponding list of shot and a key frame (Label KF), and the key frame information may be omitted here. The shot list of the label describes shot information (eg, S ₁ ^k , S ₅ ^k , S ₈ ^k ,...) Assigned the label in the shot clustering process. The algorithm of the present invention makes it possible to assign keyframes for labels and scenes. Keyframe assignment for labels and scenes is performed in the fourth step of this algorithm.

The label information is a data structure for enabling browsing by summarizing the entire contents in a short time in an application such as video skimming, and the scene keyframe and the label keyframe are data structures for structurally summarizing the content.

If you have label information about a shot like this, you can construct a more implicit video skimming system by not playing shots that belong to the same label as much as possible. You can prevent keyframes from being extracted.

In addition, the connection scene is a scene structure mainly used for dialogue scenes or scenes in which the characters' interactions are repeatedly expressed, and the disconnect scene contains semantic information mainly used for rapid story development, summary, and action scenes. Therefore, the data structure of the present invention can provide different keyframe summaries according to whether they are disconnected scenes or connected scenes in keyframe summaries or skimmings, or to apply different segment regeneration methods. Enable video browsing. Therefore, the use of the index data structure of the present invention enables a higher level of nonlinear video browsing compared to a video indexing system or algorithm that does not provide label information.

9 is a block diagram of an advanced video indexing system that can extract the structural information of the present invention and uses a limited memory.

The indexing system of the present invention shown in FIG. 9 includes a clustering controller 91 for performing video indexing according to an external input and a clustering situation, a scene boundary detector 92 for a function of determining a scene boundary detection by the clustering controller, The shot setter 93, which measures the dissimilarity between two shots in the shot clustering algorithm, establishes a link and updates scene / label / shot information in memory, and a shot input from a shot index determiner. The shot index input unit 94 which manages the index and informs the clustering controller, the shot index input from the shot index input unit, and the scene / label index generated and updated from the link setter and the scene boundary detector are managed and the control signal of the clustering controller If necessary, write index information to disk as permanent storage. The index manager 95 in charge, the index file 96 managed by the index manager 95, the shot index determiner 97 for extracting shot information from the media file, and the media file for decoding the shot index as a whole. A feature extractor 98 extracts a feature for segmentation and clustering by partially decoding the data, and a video stream 99 for providing a media file to the feature extractor.

The feature extractor 98 receives information on the media to be indexed by the video indexing system from the clustering controller 91, extracts the features required for video indexing from the video stream 99, and when the corresponding data is prepared, the shot index determiner Send data to (97).

The shot index determiner 97 receives a shot index extraction command from the clustering controller 91, extracts necessary information using the feature extraction unit 98, and transfers the necessary information to the shot index input unit 94. In this case, the shot index determiner 97 notifies the shot index input unit 94 each time a new shot is detected or when the shot segmentation for the media ends.

When a new shot is input, the shot index input unit 94 registers a new shot in the index manager 95 and informs the clustering controller 91 of the new shot. The shot index input unit 94 also informs the clustering controller 91 that the shot segmentation ends.

The clustering controller 91 establishes a link through the link setter 93 based on the information about the shot input from the shot index input unit 94 and updates the scene / label / shot information managed by the index manager 95. The scene boundary detection unit 92 controls the scene boundary to determine whether a scene boundary has occurred, and performs an operation such as merging and declaring a boundary of the scene boundary inspection point to display information between scenes, labels, and scenes of the memory. (95), and when the scene boundary declaration occurs from the scene boundary detection unit 92, the index management unit 95 can be used to store information on the scene in which the scene boundary is declared in the permanent storage device. Responsible for control to ensure

Here, the index manager 95 may record the determined scene information on the disc every time the scene boundary is declared, or may use a system that stores the scene information on the disc at once after the scene information is extracted for a predetermined amount or more. The memory structure for the scene information stored in the disk may be released under the control of the index manager 95.

Using such a system, structural information on a multimedia stream can be extracted using an advanced algorithm. In other words, as the shot segmentation progresses, there are delays for several shots, but by determining the maximum value, it can be applied to a real-time system, and at the same time as the shot segmentation for the media is terminated, Indexing is complete

By using the video indexing system, the video indexing method, and the structure of the present invention, it is possible to extract structural information including a shot index, a scene index, and repetition information of shots in one scene at a time. In addition, the algorithms and systems of the present invention are characterized by advanced algorithms, which are very fast in execution and require only a small amount of memory. It can be used as a system. In addition, the present invention extracts not only the relationship between scenes / shots, but also scenes and labels, and labels and shots at the same time, so that label information is not provided in keyframe summaries or video skimming and automatic highlight generation for video content. More information than the clustering system. Therefore, the indexing algorithm and system of the present invention can be applied to any indexing system for non-linear video browsing.

Claims (22)

By performing shot segmentation and shot clustering at the same time to extract information about the scene / shot / label for the multimedia content and the index information describing the relationship between them, Extracting a new shot (Shot _cur ) and a shot histogram as shot information from the video content; Setting an inter-shot link based on the dissimilarity between shots using the extracted shot information, registering a scene in which the link is set as a connection scene, and setting association information between a scene, a label, and a shot; Information about whether the shot (Shot _cur-τo ) and the previous shot (Shot _cur-τo-1 ), which are separated by the match window size from the current shot (Shot _cur ), belong to the disconnected scene or the connected scene, respectively. Depending on whether the scenes to which each shot belongs is the same or different, merge the scenes to which the two shots (Shot _cur-τo and Shot _cur-τo-1 ) belong or make a scene boundary declaration. Making a step; Storing the merged or bounded scene information; Progressive video indexing method comprising a. The method of claim 1, wherein the measuring _{dissimilarity} measures _{dissimilarity} between shots in a match window with respect to the shot _cur , and measures shot _min having a minimum dissimilarity using the measured dissimilarity. And after detection, if the dissimilarity is less than or equal to a certain threshold, establish a link between shots and register the scene in which the link is set as a connection scene. The method of claim 1, wherein the scene is defined as a sequence of one or more consecutive shots, wherein the label is defined as a sequence of shots in which a similarity between shots within the scene is less than or equal to a certain threshold τ _shotdiff , and one label is defined as one sequence. An advanced video indexing method comprising more than one shot. The method of claim 1, wherein the scene is represented by a list of labels and the labels are represented by a list of shots. The scene of claim 1, wherein the connected scene is a scene having a label having two or more shots as a component in the scene, and the disconnected scene is a scene having no label having two or more shots as a component in the scene. Progressive video indexing method, characterized in that. The method of claim 1, wherein the match window comprises a FIFO structure in which shots existing within several previous shot offsets τ _o from a time when a current shot _cur is detected are arranged in a time sequence. Progressive video indexing method. The method of claim 1, wherein a single scene, a single label, and single shot information are added to the newly input shot (Shot _cur ), and the newly input single scene / single label / single shot information is added through link setting. An advanced video indexing method, characterized in that for updating. The method of claim 1, wherein the shot (Shot _cur) and when configuring a link between at least the relative shot with the Angel (Shot _min) has updates the label information to assign the same label to the two shots, the two shots Merge the included scenes, update the scene information by marking the scene with the new shot added as a linking scene, and if no link is established, assign a new label to the new disconnected scene and assign a reference shot to it. An advanced video indexing method, characterized by recording one piece of information. The _scene of claim 1, wherein a scene to which each shot belongs to a shot (Shot _cur-τo ) and a previous shot (Shot _cur-τo-1 ) spaced apart by a match window size from the current shot (Shot _cur ). Determines whether the scene is a connected scene or a disconnect scene, and determines whether the scene to which the two shots (Shot _cur-τo and Shot _cur-τo-1 ) belong is the same scene or another scene, and when both shots belong to the disconnect scene Merge the scene to which the shot (Shot _cur-τo ) belongs to the scene information to which the shot (Shot _cur-τo-1 ) belongs, one of the two shots belongs to the disconnected scene, and the other to the connected scene Declares that a scene boundary has occurred and changes the scene information to which the shot (Shot _cur-τo-1 ) belongs to a state that can be stored in the storage _device.The two shots belong to the connected scene and the scene to which the two shots belong If they are the same, no action is taken, both shots belong to the connected scene and two shots If the scene is different progressive video, the indexing method according to claim to declare the thin boundary has occurred to change the shot scene information to which it belongs (Shot _cur-τo-1) to be stored in the state storage device. The method of claim 1, wherein in storing the scene information after the scene integration or scene boundary declaration, when using a policy of storing the scene information in a permanent storage device every time a new scene is registered, the scene information of the new scene is determined. Store in storage; In case of using the policy of storing the determined scene information at once after the predetermined scene information is filled, the information about the determined scenes is stored in the storage device only when the predetermined scene information has been registered in the predetermined amount or more. Progressive video indexing method, characterized in that branching to the shot information extraction step. Clustering control means for performing video indexing according to an external input and a clustering situation; Scene boundary detection means for scene boundary detection determination by clustering control means ; Link setting means for measuring a dissimilarity of two shots in a shot clustering algorithm and establishing a link and updating scene / label / shot information of a memory based on the dissimilarity of two shots; Shot index determining means for extracting shot information from the media file; Feature extraction means for extracting a feature for segmentation and clustering by decoding the media file for shot index extraction; Shot index input means for managing a shot index input from the shot index determination means and informing the clustering control means; Managing the shot index input from the shot index input means, the scene / label index generated and updated from the link setting means, the scene boundary detecting means, and recording the index information in the storage device when necessary according to the control signal of the clustering control means; Indentation management means in charge; Progressive video indexing system comprising extracting the structural index information describing the information about the scene / shot / label and the relationship between them by performing a shot segmentation and shot clustering at the same time. 12. The method of claim 11, wherein the feature extracting means receives information on the media to be indexed by the video indexing system from the clustering control means, extracts the features required for video indexing, and when the data is ready, the data is extracted to the shot index determining means. Progressive video indexing system, characterized in that for transmitting. 12. The method of claim 11, wherein the shot index determination means receives a shot index extraction command from the clustering control means, extracts the necessary information by using the feature extraction means, transfers it to the shot index input means, and each time a new shot is detected. Or notifying the shot index input means when the shot segmentation with respect to the media is ended. 12. The method of claim 11, wherein the shot index input means registers a new shot in the index management means when a new shot is input and notifies the clustering control means, and notifies the clustering control means that the shot segmentation is terminated. Progressive video indexing system. 12. The apparatus of claim 11, wherein the clustering control means establishes a link through the link setting means and updates the scene / label / shot information managed by the index managing means based on the information about the shot input from the shot index determining means, Scene boundary detection means is controlled to check whether a scene boundary has occurred, and operations such as merging and boundary declaration of scene boundary inspection points are performed to update information between scenes / labels / scenes in memory through index management means. And, when the scene boundary declaration occurs from the scene boundary detection means, using the index management means again, so that information about the scene in which the scene boundary is declared can be stored in the storage device. . 12. The apparatus of claim 11, wherein the index managing means stores the determined scene information in a storage device every time a scene boundary is declared according to a storage policy, or stores the scene information at a time after the predetermined amount of scene information is extracted. Progressive video indexing system for automatically releasing a memory structure for. Multimedia content; Define as a list of scenes, which is a continuous sequence of one or more shots, Section information including a start point and an end point of each scene, Shot list information for storing one or more shots belonging to a scene, Label list information for storing one or more labels belonging to the scene, A method of describing structure index information for a multimedia stream, comprising: flag information indicating whether a connection scene or a disconnect scene is included. 18. The method of claim 17, wherein the components of the shot list are individual shots, and shot information is described using interval information including a start point and an end point. 18. The multimedia stream according to claim 17, wherein the components of the shot list are individual shots, and the shot information is described by including section information including a start point and an end point, and keyframe information about the shot. Method for describing the structured index information. 18. The method of claim 17, wherein the components of the label list are individual labels and the label information is a list of shots assigned the label in the scene. 18. The multimedia stream of claim 17, wherein the components of the label list are individual labels, and the label information is described including a list of shots assigned the label in the scene and keyframe information about the label. Method of describing structured index information. 18. The method of claim 17, wherein the scene information further includes keyframe information for representing a scene.