Method for producing a visual rhythm using a pixel sampling technique

[0002] 1. Technical Field

[0003] The present invention relates to a method for producing a visual rhythm; and, more particularly, to a method for producing a visual rhythm which is a single image summarizing changes of video contents by using a pixel sampling technique, and employing the visual rhythm at various digital video application systems and each of digital video related software products.

[0004] 2. Description of the Related Arts

[0005] Presently, according as a digital application field, for example, a broadcasting digital video signal editing, a digital library, a video database, a multimedia video contents production, and a video streaming at an internet, increases, a video indexing research has become active.

[0006] As is well known, since a video signal comprises a sequence of image ‘frames’, all of the video contents are recognized through a control function of a VCR (Video Cartridge Recorder), i.e., a play function, a fast play function, a rewind function and a temporary stop function etc.

[0007] The video indexing is a mechanism capable of approaching to a certain portion of the video signal. The video indexing technique has two sorts: annotation-based indexing and content-based indexing. indexing. The annotation-based indexing technique searches a specified section of the video contents through the annotations that are keywords or texts made by an annotator.

[0008] On the other hand, the content-based indexing technique searches a specified section of the video contents through the analysis of the video signal characteristics.

[0009] Preferably, an effective video indexing technique may be to employ two techniques together, i.e., searching of a specific part of video contents is performed based on both annotations and contents-based indexes.

[0010] The most important thing in the content-based indexing technique is a ‘shot change detection’.

[0011] The video signal is made and edited by a ‘shot’ unit. The shot is a unit of action photographed without interruption and constituting a single camera view. In general, the duration of one shot is between one or ten seconds according to the contents of the video.

[0012] Since the video signal is made by the shot unit, it is necessary to index the video signal based on the shot unit.

[0013] In case that the shot change detection is performed manually, the detection cost and the detection time are increased. Therefore, a software has to be employed to automatically detect the shot change detection.

[0014] However, it is impossible to perfectly detect all of shots of the video signal with the software. During the automatic detection, there occur false positive shots and missing shots. This is originated from the editing effect.

[0015] The editing connects each of the shots by using cut, dissolve and wipe effects. The cut simply connects two adjacent shots. This is called as an abrupt change. On the other hand, the dissolve and the wipe gradually connect two shots through a number of frames. They are called as gradual changes.

[0016] A cut is simply a concatenation of two shots. In other words, no special effects are introduced. A dissolve is a simultaneous application of a fade-out (of an outgoing shot) and a fade-in (of an incoming shot). A wipe is another edit effect where an incoming shot appears at one or more parts of an outgoing shot, and then grows gradually until it covers the entire frame.

[0017] Recently, according as a digital editing equipment is advanced, three-dimensional editing techniques such as rolling, flying, and Doppler effects are also well known.

[0018] A shot boundary detection detects a shot boundary at the edited video signal.

[0019] Generally, the shot boundary at the abrupt change such as the cut is easily detected by using a pixel based comparison of signal characteristics, a frame-to-frame comparison of average signal characteristics, a histogram, and a motion. In this case, however, some cases such as shots having camera movements, i.e. panning and zooming, the shot boundary at a very bright or dark background, or a background having very fast moving objects may not be detected.

[0020] On the other hand, the shot boundary of the gradual changes such as the dissolves and the wipes is hardly detected.

[0021] The shot boundary detection error at a presently developed shot boundary detection algorithm ranges from 10 to 20% in case that the gradual change hardly occurs. Therefore, the confirmation or the verification of the boundary detection is required.

[0022] In the prior art, the confirmation or the verification of the shot boundary detection is performed only with the manual VCR functions, so that the exact verification is not possible.

[0023] It is, therefore, an object of the invention to provide a method for producing the visual rhythm by using the pixel sampling technique so as to detect and verify the shot boundary.

[0024] In accordance with an aspect of the present invention, there is provided a method for producing a visual rhythm in a video system, comprising the steps of: a) sampling a portion of pixels contained at each of frames; and b) producing the visual rhythm summarizing changes of video contents by using the result of the sampling.

[0025] In accordance with another aspect of the present invention, there is provided a computer-readable medium for producing a visual rhythm, comprising the steps of: a) sampling a portion of pixels contained at each of frames; and b) producing the visual rhythm summarizing changes of video contents by using the result of the sampling.

[0026] For a more complete understanding of the present invention and the advantage thereof, reference is now made to the following description taken in conjunction with the accompanying drawings in which:

[0027] FIG. 1 is a diagram of pixel sampling method for generating a visual rhythm in accordance with the present invention;

[0028] FIG. 2 shows a diagram of the visual rhythm for an individual pixel sampling;

[0029] FIG. 3 describes a flowchart of a method of generating the visual rhythm in accordance with the present invention;

[0030] FIGS. 4ato 4dare diagrams representing an editing effect of the visual rhythm in accordance with the present invention;

[0031] FIG. 5 is an exemplary drawing of the visual rhythm in accordance with preferred embodiment of the present invention;

[0032] FIG. 6 is an exemplary drawing representing the magnification and the reduction of the visual rhythm; and

[0033] FIG. 7 shows a diagram representing a user interface of a shot verification unit.

[0034] FIG. 1 is a diagram of pixel sampling method for generating a visual rhythm used in the present invention.

[0035] As shown in FIG. 1, the pixel sampling method has five approaches: a horizontal sampling la, a vertical sampling 1b, a diagonal sampling 1c, a crossing sampling 1dand a regional sampling 1e.

[0036] The visual rhythm is an single image summarizing a video contents. Especially, the visual rhythm using the diagonal sampling 1cenables the edited portion, which is edited by the cut, the wipe and the dissolve etc., to be expressed as a visible pattern, for example, a vertical line, an oblique line, a curved line and a gradual change of color. In addition, the visual rhythm enables the video portion effected by a camera movement, a light and an object movement to be expressed as some visible forms.

[0037] The visual rhythm is produced as follows.

[0038] If each value of the pixels of a video signal (V) is f_V(x,y,t) the video signal V is expressed as

[0039] V={f_v(x,y,t)}  Eq. (1)

[0040] x,y,tε{0,1,2, . . . }

[0041] From Eq. (1), the pixel value f_Thumbnail(x,y,t) of the reduced video signal V_Thumbnail, which is made by reducing each frame of the video signal by r times in both horizontal and vertical directions, is derived as

[0042] V_Thumbnail={f_Thumbnail(x,y,t)}  Eq. (2)

[0043] x,y,tε{0,1,2, . . . }

[0044] From equations Eq. (1) and Eq. (2), the relation between the video signal V and the reduced video signal V_Thumbnail, can be defined as

[0045] f_Thumbnail(x,y,t)=f_v(rx+k_x, ry+k_y,t)  Eq. (3)

[0046] x,y,tε{0,1,2, . . . }, k_x,k_yε{0,1,2, . . . , r−1}

[0047] wherein, k_xand k_ymean sampling offsets.

[0048] From Eq. (3), the visual rhythm VR of the video signal V is made by using the reduced video signal V_Thumbnail(x,y,t). Thus

[0049] VR={f_VR(z,t)}={f_Thumbnail(x(z),y(z),t)}  Eq. (4)

[0050] Referring to Eq. (4), the visual rhythm is a two dimensional image which is produced by sampling a portion of the pixel value f_Thumbnail(x,y,t) of the reduced three dimensional video signal.

[0051] As shown in FIG. 1, according to the each of samplings, the visual rhythm may be various. The selection of the sampling method is determined by the expressive power for the content changes of the video signal.

[0052] FIG. 2 shows the visual rhythm for each of the pixel samplings, i.e., the diagonal sampling 1c, the crossing sampling 1dand the regional sampling 1eof FIG. 1.

[0053] Referring to FIG. 2, the regional sampling 2ccan represent the contents of an entire frame at a side view of a signal processing. However, a number of horizontal lines are generated to hinder the user examining the shot boundaries. Also, the crossing sampling 2bgenerates a horizontal line to hinder the user examining the shot boundaries.

[0054] On the other hand, although the diagonal sampling 2acan not represent the contents of the entire frame, there are many good characteristics to verify the shot boundary detection.

[0055] The preferred embodiment of the present invention is described by using the diagonal sampling 2a.

[0056] The method of efficiently producing the visual rhythm is described as follows.

[0057] If a video is just digitized without compression, the pixel sampling is also simple. However, the video is stored in compressed form, it is necessary to decompress the stored video so as to produce the visual rhythm.

[0058] If, among various compression techniques, the video is compressed by DCT(Discrete Cosine Transform)-based techniques such as M-JPEG(Motion Joint Photographs Expert Group) or an inter-frame compression of MPEG(Moving Picture Experts Group), the pixel sampling of the compressed video is efficiently performed.

[0059] At the DCT-based techniques, an input frame is divide to 8×8 blocks. After performing the DCT, each of the blocks is represented with one DC(Direct Current) coefficient and 63 number of AC(Alternative Current) coefficients. Herein, the DC coefficient is the average value of 64 pixels. Thus, if a frame is constructed only with the DC coefficient, an image reduced by {fraction (1/64)} can be made.

[0060] In case that the reduced DC image is used as a thumbnail, the reduced video signal f_Thumbnail(x,y,t) and the pixel value of the video signal(V) have a characteristic like Eq. (5) $\begin{array}{cc}{f}_{\mathrm{Thumbnail}}\left(x,y,t\right)=\frac{1}{8}\sum _{k_x=0}^7\sum _{k_y=0}^7{f}_v\left(8x+k_x,8y+k_y,t\right)& \text{Eq. (5)}\end{array}$

[0061] x,y,t ε {0,1,2,3, . . . }

[0062] If the DC image is used as a thumbnail, an inverse DCT process is not necessary to shorten producing time of the visual rhythm.

[0063] FIG. 3 shows a flowchart of the method of producing the visual rhythm, wherein the video is of M-JPEG (or the I frames of MPEG)

[0064] At the M-JPEG technique, each of frames is compressed like the JPEG technique. At the JPEG technique, the image is divided to 8×8 pixel blocks. And then, the DCT transformation, a quantization, a run-length and a Huffman transformation are performed.

[0065] After performing above described process, 64 number of pixels in the 8×8 block are changed to one DC coefficient and 63 AC coefficients.

[0066] In order to generating the visual rhythm with the M-JPEG compressed video, each of the frames may be decompressed. That is, a series of decompression processes are performed. The decompression processes are an inverse Huffman transformation, an inverse run-length, an inverse quantization, and an inverse DCT transformation. However, if the inverse DCT transformation process can be omitted, the visual rhythm production time will be greatly reduced.

[0067] As shown in FIG. 3, in order to produce the visual rhythm, first a frame is read (S301). And then, the diagonal DCT blocks at the frame are read (S302). Thereafter, the inverse Huffman transformation, the inverse run-length transformation and the inverse quantization for the DC coefficient are performed for each of the DCT blocks to generate each of DC coefficients (S302-S306)

[0068] And then, the DC coefficients for each of the frames are accumulated to generate the visual rhythm of the entire video (S307).

[0069] Hereinafter, the characteristics of visual rhythm and the shot verification are described.

[0070] The visual rhythm is a single image representing the contents of an entire video.

[0071] The pixels extracted from a diagonal line of a frame contained at a certain shot have a similar visual characteristic. Therefore, visual changes (or shot boundaries) are presented as some visually identifiable patterns on the visual rhythm. These changes are easily detected with eyes.

[0072] The method for producing the visual rhythm in accordance with the present invention can be stored in a computer-readable medium, e.g. an optical disk, a hard disk and so on.

[0073] FIGS. 4ato 4dare diagrams representing the editing effect on the visual rhythm in accordance with the present invention.

[0074] Referring to FIG. 4a, the shot boundary connected with the cut is presented by a vertical line at the visual rhythm.

[0075] Referring to FIG. 4b, the shot boundary connected with a horizontal and left-to-right wipe, is presented by an oblique line. In addition, the shot boundary connected with a vertical and top-to-bottom wipe is also presented by the oblique line.

[0076] Referring to FIG. 4c, the shot boundary connected with an expanding and center-to-outskirts wipe, is presented by a curved line. In the other hand, the shot boundary connected with an absorbing and outskirts-to-center wipe, is presented by a curved line changed with 180 degrees.

[0077] Referring to FIG. 4d, the shot boundary connected with the dissolve is not represented by a line form. Instead, the gradual color change is presented.

[0078] As shown in FIG. 5, the visual rhythm from the actual video signal is depicted.

[0079] Referring to FIG. 5, without playing the video, the various editing effects are detected with the visual rhythm. That is, the visual rhythm 5aof the wipes and the cuts and another visual rhythm 5bof the dissolves and the cuts enable the editor to verify the shot boundary.

[0080] In addition, a camera movement such as zoom-ins or zoom outs, flashlights, and object movements are also shown on the visual rhythm 5c.

[0081] Hereinafter, in order to show the usefulness of the visual rhythm, a shot verifier is explained.

[0082] The shot verifier is a software tool and enables the shot detection errors to be shown with eyes and to be corrected in hand.

[0083] The shot verifier may be utilized with a shot detector, which is a tool implemented with the shot boundary detection algorithm. In case that the shot verifier is used alone, shot boundaries could be detected in hand.

[0084] The shot verifier has a number of functions: a function of summarizing entire video contents, a function of showing the editing effects with eyes, a function showing a certain section of the video with frame-accurate controls, a VCR function, a shot boundary hand-operated setting and removal. These functions reduce the time for shot verification in contrast to the verification with the VCR functions.

[0085] In the preferred embodiment of the present invention, the shot verifier is implemented by using the visual rhythm of 720×480 M-JPEG video. FIG. 6 shows the change of the visual rhythm during eight minutes.

[0086] FIG. 7 is a diagram representing a graphical user interface of the shot verifier in accordance with the preferred embodiment of the present invention. With this shot verifier, by viewing the visual rhythm and using frame-accurate controls, the operator determines the frames that appear to be candidates for false positives and/or undetected shot boundaries. The shot verifier provides a sequence of 90×60 thumbnails to aid the operator for such operations. These thumbnails are sixty-four times smaller than the original 720×480 frames. The shot verifier can also provide the original frames at the user request. In addition, it provides VCR functions for shot-by-shot playing and frame-accurate random positioning. With these frame-accurate controls and VCR functions, the operator can manually delete false positives and add newly found shots. The operator navigates the three major parts of the interface: the visual rhythm along with certain markers, the list of thumbnails surrounding the current frame, and the frame accurate play controls. We describe these individual parts in detail.

[0087] At the top of the interface, the visual rhythm is displayed with automatically detected shot boundaries marked at their corresponding locations with small inverse triangles or shot boundary markers. On the upper right corner of the visual rhythm, small buttons for zooming (enlarging and reducing) and scrolling the visual rhythm is provided. On top of a visual rhythm, a cursor is provided to indicate the current position (time code or frame number). By dragging and dropping the cursor at any position of the visual rhythm, the user can change the location of the current frame.

[0088] At the middle of the interface, the thumbnail list of twenty-one frames surrounding the current frame is displayed. At the center of the list, showing “Shot 183”, is the current frame, as indicated by the cursor on the visual rhythm. Other thumbnails, ten above and ten below, are the frames immediately preceding and following the current frame, respectively.

[0089] At the bottom of the interface, various options/buttons for frame accurate controls are provided. For instance the operator is able to move the current frame by 1, 5, 30 frames forward or backward. Recall that the current frame can also be updated by moving the cursor on the visual rhythm. In any case, such current frame update results in redisplay of the thumbnail list. When the play button is selected, a new window appears to play from the current frame. The “Play Range” option indicates whether to play the entire video or the current shot. Currently, no fast forward nor rewind buttons are provided as we have provided the random positioning function.

[0090] Following the automatic shot detector, the shot verification process may proceed as follows. If a certain frame appears suspicious, upon viewing the visual rhythm, the cursor is moved near that frame. For instance, FIG. 7 shows the visual rhythm where there appears to be a shot boundary without the boundary marker (inverse triangle). Therefore, the cursor has been moved near that frame by the drag and drop operation. Then, twenty-one thumbnails are redisplayed according to this new current frame. Quick glance over the thumbnail display indicates that the fourth thumbnail is actually the first frame of a new shot, missed by the automatic detector. False positive shots are detected similarly. In any case, when detected, deletion and/or addition of shot boundaries is processed with a left mouse button click, at which a small menu appears as shown in FIG. 7. The menu is self-explanatory; it basically provides the mechanics for deleting and adding shot boundaries. Such updates to shot boundaries result in redisplay of the markers (inverse triangles) on top of the visual rhythm at the top of the interface. For instance, the user may select “New Shot” to insert a missing shot or “Delete Shot” to discard a false positive. The user may also select the “Key Frame” for the current shot (183). Other interface is also available for clustering various shots in segments and scenes.

[0091] In this manner, the visual rhythm enables the user to correct the missing shot and the false detected shot without playing the video.

[0092] Various modification and alterations of this invention will become apparent to those skilled in the art without departing from the scope and spirit of this invention. It should therefore be understood that this invention is not unduly limited to the illustrative embodiments set forth above, but it to be controlled by the limitations set forth in the claims and equivalents thereof.