JP3529587B2 - Video list display method and recording medium storing video list display program - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention synthesizes a plurality of representative images, which are still images extracted from a video, on a computer screen or on paper so that the contents of the video can be displayed without observing them in chronological order. The present invention relates to a video list display method and a recording medium on which a video list display program is recorded so that an outline can be grasped in a short time.

[0002]

2. Description of the Related Art In order to find a desired screen from a tape using a VCR, there is no choice but to repeat fast-forward and rewind operations, which takes time.

As a conventional technique, a scene change (cut) is automatically detected based on a temporal change of a luminance or a color distribution of an image, and one or a plurality of images are extracted as a representative image for each scene. A method for displaying a list on paper (Prior Art 1) has been disclosed (Tonomura, Taniguchi, Akutsu: Paper Video: New Video Interface Using Paper, IEICE Technical Report, IE94-59, pp. 15). -20,1
994). As shown in FIG. 13 , by combining and displaying the images of the transitional scenes on paper, it is possible to roughly understand the outline of the image without reproducing it.

In the above-mentioned document, since all the representative images have the same size, no special device is required when laying out on a plane such as paper or computer display. It was good if the images were arranged at equal intervals from the upper left to the lower right. However, the size of the representative image extracted is not constant. That is, in the case of amorphous, in a simple layout method, as shown in FIG. 1 4, representative image P
In the case of laying out 301 to P307, there is a problem that useless margins (hatched portions in the drawing) are created, and the information that can be packed is reduced. Then, as shown in FIG. 1 5
As shown in (4), it is desirable to lay out so as to avoid useless margins as much as possible.

[0005]

Conventionally, there has been disclosed a method (prior art 2) for packing non-fixed shapes so that they do not overlap on a plane. For example, Column-Based Stirip
Packing Using Ordered and Compliant Containment, K
aren Daniels and Victor J, Milenkovic, Proceedings
of the First ACM Workshop on Applied Computationa
l Geometry (WACG), edited by Ming C. Lin and Dines
h Manocha, 1996, p.33-38, Lecture Notes in Compute
r Science, Springer-Verlag. The method of this reference 1 6
It was developed for the purpose of most efficiently cutting out a clothing pattern from a cloth of a fixed area as shown in.
Since the temporal order is important in the video targeted by the present invention and it does not mean that the representative images may be laid out in any order, the method of the above document cannot be applied as it is. If the method of the above-mentioned document is used, there is an inconvenience that the representative image is laid out regardless of the temporal context (for example, the representative image of the last scene is laid out at the top of the page). This is because it becomes impossible to understand the dynamic transition.

Further, as another problem, in the prior art 1, it is difficult to understand where there is a break in the image content. In the text, there are layout rules such as a line break at the beginning of a paragraph or a bold title at the beginning of a chapter that expresses the chapter concisely, and the layout allows intuitive understanding of breaks in the text. There is. Also in the case of video, there are breaks in the content like text, for example, a turning point of a topic, switching from a TV program to a CM, and a list reflecting such a structure is desirable.

An object of the present invention is to reduce wasteful margins when laying out a plurality of non-standard representative images and displaying a list, and to perform a layout that preserves the temporal context to intuitively identify video breaks. It is an object of the present invention to provide a video list display method and a recording medium on which a video list program is recorded, which can perform a layout that can be understood visually.

[0008]

[0009]

Image list display method of the present invention According to an aspect of the the atypical extracted or synthesized from the image a plurality of
Make sure the representative image does not overlap in a limited planar area
And satisfy layout constraints arising from temporal context
Video list display to be laid out and displayed under the condition
Method to extract multiple non-standard representative images from video
Or you can extract multiple images from a video and combine them.
To obtain a plurality of representative images, and
A rectangular representative image Pi (i = 1 to 1) that is the smallest enclosing rectangle
N) is laid out and has a predetermined rectangular length of W in the horizontal direction.
The rank K of the stepwise area already occupied by the shape area and each
Coordinates (xk, yk) (k =
1,2, ..., K) held and still occupied
The rectangular representative image Pi fits in the empty space, and
Due to the layout constraint, the rectangular representative image Pi is layered.
Maintains the minimum area of dead area, which is the area that can not be cut out
Initialize the variable AREAmin to a very large value
At the same time, hold the value of k that minimizes the area of the waste area.
INDEXmin is initialized to 1, and W−xk ≧ (rectangle
If the horizontal length W (Pi) of the encoded representative image Pi is
Calculate the area AREA of the useless area, AREA <AREA
If min, the value of AREA is AREA min, k
AREA ≧ AREAmi with the value as INDEXmin
If n, the value of k is incremented by 1 without doing anything.
Process from k = 1 to k = K sequentially, and in the middle of the above process
When W-xk <W (Pi) and the processing is completed
In case of INDEX min
A table image Pi is arranged, and coordinates (xk, yk) (k = 1 to 1
K) is updated, and the rectangular representative image Pi (i = 1 to 1) is updated.
N) the steps to be sequentially performed, and the rectangular representative images
The image on the display and / or in the determined position
Has a step of composite display on the printer. More details
For each representative image is still occupied
The representative image fits in the empty space, and the layout restrictions
The area of the area that is wasted in the layout that satisfies
The layout will be According to the present invention, it is not necessary to enumerate all possible layouts, so that the calculation cost can be reduced. Although an optimal solution that minimizes the space occupancy is not obtained, a solution that is close to the optimal one can be obtained at high speed.

According to the embodiment of the present invention, the switching of the video content is detected at a plurality of levels, and the representative image after switching is detected.
The rectangular representative image of is laid out by imposing the second layout constraint according to the switching level. It becomes possible to express the break of meaning clearly by imposing a layout constraint such as a line break when there is a big change of meaning, that is, contacting the left end, or putting it in the margin.

In another embodiment of the present invention, when the rectangular representative image is laid out spatially, the shape of the representative image is modified so that the height of the smallest rectangle surrounding all the laid out rectangles becomes small. It is characterized by When the representative image extends beyond the given plane area (window size or paper size), the representative image can be appropriately reduced so as not to extend. In this way, by making a slight correction to the representative image, it is possible to reduce the spatial occupation ratio without significantly deteriorating the appearance.

Another embodiment of the present invention estimates a motion of a camera and an image extracted as a representative image based on a cut that is a scene change that is a point of abrupt change of video luminance and color information. And based on the estimated camera movement
It is characterized in that it includes either or both of panoramic images composed by moving and transforming the images forming the video . By extracting the representative image based on the cuts, it is possible to save the labor of manually selecting the representative image by a person. By creating a panoramic image by offsetting the camera movement, a representative image that accurately represents the subject can be obtained.

Computer-readable recording medium of the present invention
The body implements the video list display method described above on a computer.
It has recorded the video list display program that Ru by line.

[0014]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described with reference to the drawings.

[0015]

[0016]

[0017]

[0018]

[0019]

[0020]

[0021]

[0022]

FIG. 1 is a flow chart of processing according to the first embodiment of the present invention.

The present embodiment is a method in which an optimum solution cannot be obtained but a solution close to the optimum can be obtained at high speed.

In this embodiment, the representative images Pi are laid out in order of time (i = 1, 2, 3, ...) In an optimal position, and in step 15, the number of the representative image is laid out. Initialize the variable i representing 1 to 1. Step 16
Then, all possible layouts of the representative image Pi are listed under the condition that the representative images P1, ..., Pi-1 have already been laid out (representative images P1, ..., P.
(Since i-1 enumerates the possible layouts provided that they are already laid out, the number of layouts enumerated is greatly reduced). In step 17, the area of the wasted area is obtained for each layout, and the layout that minimizes the area is adopted. At step 18, 1 is added to the loop variable i, and at step 19, it is judged whether or not all the representative images have been laid out. When the layout is completed, the processing is ended, and if not so, the processing returns to step 16.

The operation of this embodiment will be specifically described with reference to the specific example shown in FIG. When the loop variable i = 1, there is no representative image that has already been laid out.
4 Only the layout of (1) can be taken. When i = 2,
Two types of layouts shown in FIG. 4 (2) and FIG. 4 (3) are possible. In the layout of FIG. 4 (2), there is no waste area, whereas in the layout of FIG. 4 (3), the shaded area A2 is wasted (the representative image Pj ( j> i) cannot be laid out). Therefore, adopting the layout of FIG. 4 (2) in step 17. When i = 3, there is only the layout of FIG. 4 (4), so the layout of FIG. 4 (4) is finally adopted. Although the optimum layout is not shown in FIG. 3 (2), the optimum solution (FIG. 3 (1)) is obtained next.

FIG. 5 is a detailed flow chart of steps 16 and 17.

As a prerequisite, the representative images P1, P2, ...
The number of steps in the area (step area) already occupied by Pi-1 is K, and the coordinate value of the corner of each stair is (xk, y
k), (k = 1, ..., K) are held (step 21). FIG. 6 shows representative images P1 and P.
2, ..., Pi-1 are diagrams showing a state in which a representative image Pi is being added in a state where layouts are already made. When i = 1, that is, in the initial state in which nothing is laid out, K = 1 and x1 = y1 = 0. In step 16, all possible layouts of the representative image Pi are enumerated. However, considering that the space occupancy rate is minimized under the layout constraint described above, the possible layouts are the representative images Pi at the corners of the stairs. Only in the case of K streets where the upper left corner overlaps. In step 22, the variable AREAmin that holds the minimum area of the dead area is initialized to infinity, and the variable INDEXmin that holds k that minimizes the dead area is initialized to 1. Initialize k to 1 (step 23) and repeat the following process for k = 1, 2 ... K. In step 24, it is checked whether or not the width of the representative image Pi falls within the kth row. If it does not fit, the process exits the loop and moves to step 30. If in step 25 if they fit, determined as the sum of the areas of the two regions A3, A4 showing the area AREA of the dead area by oblique lines in FIG. 6.
The area of the shaded area can be calculated from the width and height of each staircase. In step 26, AR that has been added up with AREAmin
EA is compared, and if AREA <AREAmin is established, step 27 is executed to execute INDEXmin, ARE.
Amin is updated to k and AREA , respectively. In step 29, it is inspected whether or not all the steps have been checked, and if there are remaining steps, the process returns to step 24. In step 30, INDE
A layout in which the representative image Pi is arranged at the corner of the Xminth stage is adopted. In step 31, the area occupied by the addition of the representative image Pi is expanded (xk, y
Update the coordinate value of k). In the example of FIG. 6 , the number of stairs K is 3, (xk, yk) is (x1 ′, y1 ′), (x2 ′, y
2 '), (x3', y3 ').

In the present embodiment, various modifications can be made regarding how to estimate the dead area.
If the average size of the representative image is given, the area in which the rectangle having the reference size cannot be laid out can be used as a waste area. It is also possible to optimize the space occupancy rate by re-laying out rectangles laid out immediately before or a few before the unit layout procedure as post-processing.

FIG. 7 is a flow chart of processing according to the second embodiment of the present invention.

Consider a case where the level of switching the contents of video is two levels. The point (cut) at which the image content changes significantly by switching the camera is called switching of the level L1. The cut can be detected as the place where the difference is large by taking the difference between the images. The switching of the level L2 is a more meaningful change, and is detected here on the assumption that a black image is inserted at a unit break in the video chapter. The representative images P11 to P21 are extracted every time the cut in FIG. 8 is detected, and the representative images P14 and P19 are the switching points of the level L2.

In FIG. 7 , steps 11, 15, 1
Since 6, 17, 18, 19, and 14 are the same as those in the first embodiment, the description thereof will be omitted. In step 32, it is checked whether or not the representative image Pi to be laid out is a black image. If not, the process proceeds to step 16 and the same process as in the first embodiment is performed. If the image is a black surface, the representative image Pi is deleted in step 33, and the representative image Pi + 1 is laid out so as to be in contact with the left end. Figure
Doing this process specific example of 8, FIG resulting 9
Get the layout of. Layout L11, L12, L1
3 is the unit corresponding to the video chapter. In this way, it becomes possible to clearly express a video break by detecting a break in the content at a plurality of levels and imposing a layout constraint such as a line break according to the switching level.

It should be noted that, in order to detect the semantic change of the video, in the present embodiment, it was detected that the representative image is black on the whole surface, but of course the invention is not limited to this. For example, it is possible to start a line break when the appearance of a telop is detected, or it is possible to start a line break when a dissolve, which is a special effect, is detected. In a system for a television program, it is possible to detect a place where the program is switched to a commercial or vice versa, and to break the page. Further, instead of using only the image information, the break of the audio information, for example, the place where the silent section is continued for a predetermined time, can be switched. Further, it is possible to change the layout constraint to take a layout such as a page break or centering instead of a line break.

FIG. 10 is a flow chart of processing according to the third embodiment of the present invention.

The steps 11, 15, 18, 19, and 14 are the same as the corresponding steps of the first embodiment, and therefore their explanations are omitted. In the present embodiment, in step 35, the user can set what percentage the representative image is allowed to be reduced. This rate is called the allowable reduction rate. Step 3
In FIG. 6, possible layouts are listed in consideration of the fact that reduction to the allowable reduction ratio is allowed when laying out the i-th representative image Pi. In step 37, the area of the wasted area is calculated, and the layout and reduction ratio that minimize it are adopted.

[0036] As a specific example will be described with reference to the example of FIG. 1 1. The state in which the representative image P100 has already been laid out
In FIG. 11 (1) , the representative image P101 (width v100,
Height h100) is about to be laid out. In the state where the image is not reduced, the layout cannot be performed on the right side of the representative image P100, or if the image is reduced by 50% like the representative image P102, the image is just placed in the gap and the space occupancy rate increases. Accordingly, the layout of this Figure 1 1 (2) is employed.
The closer the allowable reduction rate is to 0%, the lower the space occupancy rate becomes. However, if the reduction rate is too small, the visibility of the image will deteriorate, so it is necessary to set an appropriate value according to the application. When printing on paper, since the resolution of paper is high, the allowable reduction ratio may be set small, but when displaying on a computer screen, it is better not to make it too small.

In the third embodiment, only the reduction is permitted, but the enlargement or the cutout (the process of cutting a part of the image) may be performed. Also, after finishing the layout process of all the representative images, it is preferable to perform post-processing such as enlarging / reducing to fill the unnecessary margins or performing fine adjustment to make the spaces even. Suitable for

The present invention is not limited to the above embodiment. For the purpose of improving the appearance, it is possible to easily insert a blank space between the representative images by including a margin around the rectangle surrounding the representative image. In the above embodiment, the case where the representative images do not overlap at all has been described, but it is also possible to modify so as to allow a partial overlap. Figure 1 three as shown in 2 representative image P2
Consider a situation where the representative image P204 is to be laid out in a state where 01 to P203 are already laid out (occupied area A5). When the representative image P204 is arranged at the position shown in the figure, it protrudes from the plane area, but it can be packed if the representative image P203 is overlapped with a slight shift to the left. In order to reduce the space occupancy rate by allowing the overlapping in this way, the allowable margin width m is set, and the area A6 (area indicated by thick line) excluding the margin from the occupied area A5 is newly added. The method described above can be applied as it is by considering it as an occupied area. In addition, it is also preferable to display the overlapping areas after performing a semi-transparent combining process for obtaining an average value of the luminance between images, because it is possible to prevent the image information from being lost. Further, in addition to setting the margin width, it is possible to exclude an area where the brightness of the representative image changes little, for example, the area of the sky or the ground, from the occupied area by considering it as an area in which an important subject does not exist. Is.

The layout result can be displayed in the window area of the computer screen, or can be output as a file format in which the layout can be described, for example, a PostScript file or HTML (Hyper Text Markup Language). It is also preferable to provide a user interface that allows the user to modify the result of automatic layout. Further, the representative image is synthesized and displayed on the computer screen, and the original image is reproduced from the position of the representative image by pointing the representative image with a mouse or the like, so that the image can be used as a browser of the image. A telop (subtitle) is extracted as a representative image, the character string obtained as a result of recognizing the content of the subtitle is stored in association with the representative image, and the telop character string is used as a keyword when the representative image is clicked with the mouse. You may make it search a database and display a search result as related information.

Furthermore, various representative image extraction methods can be considered. As shown in the related art 1, the image immediately after cutting can be used as the representative image.
When a telop appears after a cut, it is preferable to use that image as a representative image for images such as news where the telop has an important meaning. Also, specify the section where the camera was moved by pan (operation to rotate the camera horizontally) or tilt (operation to rotate the camera vertically),
A panoramic image can be synthesized by obtaining camera parameters (a vector value indicating how much the camera has moved) for that section and synthesizing images according to the camera parameters. When a telop is displayed in the panoramic image, the panoramic image overwritten with the telop can be used as the representative image. Alternatively, a representative image may be obtained by cutting out only the telop portion from the image and enlarging it.

The program for executing the procedure shown in FIGS. 1, 5 , 7 and 10 is a floppy disk or CD-RO.
It is provided by being stored in a recording medium such as M or ROM tape, and the computer is controlled by the program to synthesize a plurality of representative images and display a display screen.

[0042]

As described above, the present invention has the following effects.

[0043]

According to the first aspect of the present invention, it is possible to lay out the plurality of representative images in time order, it is not necessary to list all the layouts, and the calculation cost can be reduced.

According to the second aspect of the present invention, the switching of the contents of the video is detected at a plurality of levels, and another layout constraint is imposed on the representative image after the switching according to the switching level, whereby the meaning breaks. Will be able to express clearly.

According to the third aspect of the invention, the space occupancy rate can be lowered by making a slight modification to the representative image.

According to the invention of claim 4 , as a representative image, an image extracted on the basis of a cut that is a scene change and a panorama obtained by superimposing continuous images while offsetting the movement of the camera. By using images, it is not necessary for a person to manually select a representative image, and it becomes possible to display a video list that accurately represents the subjects represented in the scene.

[0048]

[Brief description of drawings]

FIG. 1 is a flow chart of processing according to a first embodiment of this invention.

FIG. 2 is a diagram showing a representative image and a spatial region for explaining the first embodiment.

FIG. 3 is a diagram showing possible layouts of representative images P1, P2, P3.

FIG. 4 shows representative images P1 and P obtained in the first embodiment.
It is a figure which shows the layout of 2 and P3.

FIG. 5 is a flowchart of processing of a unit layout procedure (step 16) according to the first embodiment.

FIG. 6 is an explanatory diagram of a unit layout procedure of the first embodiment.

FIG. 7 is a flowchart of the process of the second embodiment of the present invention.

FIG. 8 is a diagram showing a representative image sequence for explaining the second embodiment.

FIG. 9 is a diagram showing an example of a layout obtained according to the second embodiment.

FIG. 10 is a flowchart of the process of the third embodiment of the present invention.

FIG. 11 is a diagram showing a layout accompanied by reduction processing.

FIG. 12 is an explanatory diagram of a layout that allows overlapping.

FIG. 13 is a schematic diagram for explaining conventional technique 1.

FIG. 14 is a diagram for explaining a problem of Prior Art 1.

FIG. 15 is a diagram for explaining a problem of Prior Art 1.

FIG. 16 is a schematic diagram for explaining conventional technique 2.

[Explanation of symbols]

11, 14 to 19, 21 to 37 Steps P1, P2, P3 Representative images P11 to P21, P100, P101, P102 Representative images P201 to P204 Representative images L11 to L13 Layouts A1 to A6 areas

Continuation of front page (56) Reference JP-A-2-39942 (JP, A) JP-A-7-50800 (JP, A) JP-A-10-213855 (JP, A) JP-A-7-162796 (JP , A) Yoshinobu Tonomura, Yukinobu Taniguchi, Akito Akutsu, “PaperVideo: A New Video Interface Using Paper”, IEICE Technical Research Report, The Institute of Electronics, Information and Communication Engineers, September 1994, Vol. ． 94, No. 248, p. 15-20 (58) Fields investigated (Int.Cl. ⁷ , DB name) G06T 1/00 G06T 11/60-17/50 H04N 1/38-1/393 H04N 5/76 H04N 5/80-5 / 95 G06F 17/30

Claims (5)

(57) [Claims] 1. A layout of a plurality of atypical representative images extracted or combined from a video under the condition that a layout constraint caused by temporal context is satisfied so that there is no overlap in a limited planar area. However , the method is to display a list of images to be displayed .
Multiple images are extracted from the
Obtaining an image, and a rectangular representative image that is the smallest rectangle surrounding each representative image
Horizontal length in which Pi (i = 1 to N) is laid out
Is a tiered area in which is already occupied by a given rectangular area of W
The floor rank K and the horizontal and vertical coordinates (x
Hold k, yk) (k = 1, 2, ..., K)
The rectangular representative image P in a space that is not yet occupied.
i is accommodated, and the rectangularization margin is due to layout constraints.
Wasted area where the front image Pi cannot be laid out
The variable AREAmin that holds the minimum area of the area is very large.
Initialize to a suitable value and minimize the area of the waste area.
INDEXmin holding the value of k is initialized to 1
W−xk ≧ (horizontal length W of the rectangular representative image Pi
If (Pi)), calculate the area AREA of the dead area
If AREA <AREAmin, the value of AREA
Is AREAmin and the value of k is INDEXmin,
If AREA ≧ AREAmin, do nothing and set the value of k
Increment processing by 1 from k = 1 to k = K sequentially
If W-xk <W (Pi) during the above process,
And when the above processing is completed, it is indicated by INDEXmin.
The rectangular representative image Pi is arranged at the corner of the step where the coordinates (x
k, yk) (k = 1 to K) update rectangular representation
A step of sequentially performing the images Pi (i = 1 to N), and a step of combining and displaying each of the rectangular representative images at a determined arrangement position on a display and / or a printer.
A method for displaying a list of videos. 2. The switching of the video content is detected at a plurality of levels, and the rectangular representative image of the switched representative image is laid out so as to satisfy a second layout constraint set in advance according to the switching level. The video list display method according to claim 1. 3. The shape of the rectangular representative image is modified such that, when the rectangular representative image is laid out spatially, the height of the smallest rectangle surrounding all the laid out rectangles is reduced. Or the video list display method described in 2 . 4. An image extracted as a representative image based on a cut that is a scene change that is a sudden change point of video luminance and color information, and a motion of a camera are estimated,
Either it comprises one or both, any one image list display process as claimed in claim 1 3 panoramic image composed while moving, deforming the images constituting the image based on the motion of the estimated camera. 5. recording the image list display program for executing the image list display method according to the computer in any one of claims 1 to 4, computer-readable recording medium.