US20180260960A1

US20180260960A1 - Method and apparatus for assisted object selection in video sequences

Info

Publication number: US20180260960A1
Application number: US15/533,031
Authority: US
Inventors: Tomas Enrique Crivelli; Fabrice Urban; Lionel Oisel
Original assignee: InterDigital CE Patent Holdings SAS
Current assignee: InterDigital CE Patent Holdings SAS
Priority date: 2014-12-04
Filing date: 2015-12-04
Publication date: 2018-09-13
Also published as: EP3029631A1; WO2016087633A1; EP3227858A1; EP3227858B1; TW201631553A

Abstract

A device performs a method for tracking an object in a video sequence with a bounding box for display on the device by selecting at least one point that belongs to the object, then motion processing an area of points around the selected at least one point to determine an estimated bounding box; and then color processing the points in the estimated bounding box to determine the bounding box for display on the device. The colour processing comprises computing averages of scores from pixel differences to the background model minus pixel differences from the foreground model per line as long as such average is above a threshold.

Description

BACKGROUND

The present disclosure generally relates to the field of image analysis and object/region selection.
Many problems in computer vision and image processing require a preprocessing step where objects of interests are segmented or located. For example, consider the problem of tracking an object of interest (object tracking), which requires locating the position of the object at every instant. The initial position of the object (target) can be manually defined in the first frame or as the output of an object detector in the case of dedicated trackers. Almost exclusively it is determined by a bounding box containing the object of interest. However, there are meaningful cases where the type of content, the user and the device require a more principled solution. Such as, e.g., when the user is not an expert and thus cannot provide a good selection of the object of interest from the point of view of the tracking algorithm; or the content is general and thus it is barely impossible to apply a dedicated object detector; or the device has a limited interface which requires a rapid, simple and intuitive input from the user.

SUMMARY

We propose a new approach for determining a bounding box containing an object of interest, which is then tracked along a video sequence. In particular, and in accordance with the principles of the present disclosure, at least a single point on an object of interest will initiate joint motion and color processing to determine the bounding box containing the object of interest.
According to the present principles, a method for determining a bounding box for display on a device, the bounding box containing an object in a video sequence, comprises selecting at least one point that belongs to the object; motion processing an area of points around the selected at least one point to determine an estimated bounding box; and color processing the points in the estimated bounding box to determine the bounding box.
The present principles also relate to a method for determining a bounding box for display on a device, the bounding box containing an object in a video sequence, the method comprising selecting at least one point that belongs to the object; and joint motion and color processing the at least one point to determine the bounding box comprising the object.
According to an embodiment, the selecting is performed by a user.
According to an embodiment, the motion processing uses motion flood-filling on a Delaunay triangulation.
According to an embodiment, for each side of the estimated bounding box, the color processing further comprises adding a new line of pixels; for each new pixel, measuring its distance to a foreground model and a background model; computing a score for each new pixel, wherein the score is equal to a difference of the distance to the background model minus the distance to the foreground model; averaging the scores for the new line of pixels; wherein if the average score for the new line of pixels is greater than a threshold, the new line of pixels is added to the estimated bounding box; wherein the bounding box is formed when no new line of pixels is added.
According to an embodiment, the joint processing further comprises motion processing an area of points around the selected at least one point to determine an estimated bounding box; and color processing the points in the estimated bounding box to determine the bounding box.
The present principles also relate to an apparatus comprising means for displaying a video sequence and for allowing a selection of at least one point on an object of interest in the displayed video sequence; means for storing a motion processing program and a color processing program; and means for processing the selected at least one point with the stored motion processing program and the stored color processing program for determining a bounding box for display on the touch screen display.
According to an embodiment, said means for displaying correspond to a display; said means for allowing a selection correspond to an input device; said means for processing correspond to one or several processors.
According to an embodiment, the input device is as least one of a mouse or keyboard.
According to an embodiment, the stored motion processing program includes instructions for motion flood-filling on a Delaunay triangulation to determine an estimated bounding box.
According to an embodiment, the stored color processing program includes instructions for adding a new line of pixels to the estimated bounding box; wherein for each new pixel, distance to a foreground model and a background model is measured; and wherein a score is computed for each new pixel, wherein the score is equal to a difference of the distance to the background model minus the distance to the foreground model; and wherein the scores for the new line of pixels are averaged; wherein if the average score for the new line of pixels is greater than a threshold, the new line of pixels is added to the estimated bounding box; and wherein the bounding box is formed when no new line of pixels is added.
In another illustrative embodiment the device is a mobile device such as a mobile phone, tablet, digital still camera, etc.
In view of the above, and as will be apparent from reading the detailed description, other embodiments and features are also possible and fall within the principles of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows an illustrative flow chart for providing a bounding box in accordance with the principles of the invention;

FIG. 2 illustrates selection of a point on an object of interest;

FIG. 3 illustrates selection of a trace on an object of interest;

FIG. 4 shows an illustrative flow chart for motion processing in accordance with the principles of the invention;

FIG. 5 illustrates Delaunay triangulation on the object of interest;

FIG. 6 illustrates the final list of points considered part of the object of interest based on motion similarity;

FIG. 7 illustrates a bounding box based only on motion information;

FIG. 8 shows an illustrative flow chart for color processing in accordance with the principles of the invention;

FIG. 9 illustrates the final bounding box containing the object of interest for display on the device;

FIG. 10, illustrates the ability to have multiple bounding boxes for different objects of interest; and

FIG. 11 shows an illustrative device for use in executing the flow chart of FIG. 1.

DETAILED DESCRIPTION

Other than the inventive concept, the elements shown in the figures are well known and will not be described in detail. For example, other than the inventive concept, a device that is processor-based is well known and not described in detail herein. Some examples of processor-based devices are a mobile phone, table, digital still camera, laptop computer, desk top computer, digital television, etc. Further, other than the inventive concept, familiarity with video object processing such as Delaunay triangulation processing and flood filling (region growing) is assumed and not described herein. It should also be noted that the inventive concept may be implemented using conventional programming techniques, e.g., APIs (application programming interfaces) which, as such, will not be described herein. Finally, like-numbers on the figures represent similar elements. It should also be noted that although color processing is referred to below, the figures are in black and white, i.e., the use of color in the figures (other than black and white) is not necessary to understanding the inventive concept.
We propose a new approach for selecting an object of interest which (among other possible applications) will then be tracked along a video sequence being displayed on a device. In particular, and in accordance with the inventive concept, the idea is to combine a simple selection such as a single point, or trace, on an object of interest along with joint motion and color processing about the single point, or trace, in order to determine a bounding box containing the object of interest for display on the device.
FIG. 1 shows an illustrative flow chart for providing a bounding box for display on a device in accordance with the principles of the invention. In step 105, at least one point on an object of interest is selected, e.g., by a user of the device. This determines a list of at least one point that is now assumed to be associated with the object of interest. This selection is illustrated in FIGS. 2 and 3. A device, e.g., a mobile phone, displays a frame 131 of a video sequence on a display 130 of the mobile phone. For the purposes of this example it is assumed that display 130 is a touch screen display. However, the invention is not so limited and other mechanisms for selecting at least one point on an object of interest can also be used, e.g., a mouse. As shown in FIG. 2, frame 131 shows a picture of a soccer game. The user, using their finger or a stylus, touches the picture of the person (the object of interest) pointed to by arrow 140 where the touch selects at least one point in the picture of frame 131 as represented by white dot 136. Alternatively, the user can trace a sequence of points as shown in FIG. 3 for identifying the object of interest. Again, the user, using their finger or a stylus, touches the picture of the person (the object of interest) pointed to by arrow 140 and traces a sequence of points in the picture of frame 131 as represented by white trace 137.
In accordance with the principles of the invention, motion and color processing are then applied to the selected point(s), as represented by steps 110 and 115, of FIG. 1, to determine a bounding box containing the object of interest for display in step 120.
Turning now to FIG. 4, motion processing step 110 will be explained in more detail. In particular, the list of selected points (represented as two dimensional (2D) positions) are provided to step 205. As described above, this list of selected points comprises at least one point in the object of interest. In step 205, an interest area is first determined around the selected points. This interest area can be fixed or proportional to the image size. On this area, a set of interest points is obtained in step 210 by an interest point detector. Interest point detectors are known in the art, e.g., Scale-Invariant Feature Transform (SIFT), Speeded-Up Robust Features (SURF), Good Features To Track (e.g., see Carlo Tomasi and Takeo Kanade; “Detection and Tracking of Point Features”; Carnegie Mellon University Technical Report CMU-CS-91-132, April 1991; and Jianbo Shi and Carlo Tomasi; “Good Features to Track”; IEEE Conference on Computer Vision and Pattern Recognition, pages 593-600, 1994) or by random sampling. In step 215, a Delaunay triangulation is applied on the point lattice in order to determine neighboring points. This is shown in FIG. 5, where arrow 150 illustrates Delaunay triangulation (the white lines) among the interest points detected around the input position (list of selected points). Returning to FIG. 4, in step 220, a motion/displacement is then estimated for each interest point in the following image (frame) of the video sequence (e.g., see Bruce D. Lucas and Takeo Kanade; “An Iterative Image Registration Technique with an Application to Stereo Vision”; International Joint Conference on Artificial Intelligence, pages 674-679, 1981; and Carlo Tomasi and Takeo Kanade; “Detection and Tracking of Point Features”; Carnegie Mellon University Technical Report CMU-CS-91-132, April 1991). In step 225, a final point list is determined. In particular, in step 225, the interest point(s) closest to each input position of the trace (there might be no interest point where the user touched the screen) is considered as a current point and added to a final point list. Its neighbors, according to the triangulation, of step 215, are also added to the final point list if a motion related distance, from step 220, (e.g., norm of the difference between motion vectors) to such a current point is lower than a threshold and they are also close enough with respect to a spatial distance threshold. For each of those new added points the process is repeated by considering their neighbors in turn. The whole process works as a flood filling algorithm (or region growing algorithm) but on a sparse set of locations. Other than the inventive concept, region growing algorithms among motion values is known in the art (e.g., see I. Grinias G. Tziritas; “A semi-automatic seeded region growing algorithm for video object localization and tracking”; Image Communication. Volume 16, Issue 10, August 2001). A final point list is shown in FIG. 6, where arrow 155 illustrates the final list of interest points (black dots) considered part of the object of interest according to motion similarity. Returning to FIG. 4, the final point list determines an estimated bounding box in step 230. The estimated bounding box is a box that is big enough to contain all the points in the final point list. This is illustrated in FIG. 7 by estimated bounding box 138. The latter is determined using only motion information. Illustratively, the main component of the motion processing is the use of motion flood-filling on a Delaunay triangulation. The resulting estimated bounding box is provided to color processing step 115 of FIG. 1.
In color processing step 115, the list of points that result from motion processing step 110 (i.e., the estimated bounding box based on motion similarity) are introduced into a color-based bounding box estimation process for further refinement. Turning now to FIG. 8, color processing step 115 will be explained in more detail. In step 305, the estimated bounding box is processed such that a color model (foreground color model) is learned, e.g., by K-means clustering of pixel color vectors, according to the color vector Euclidean distance. The number of clusters is normally fixed to an initial value of 10. Then, the resulting clusters are analyzed in order to discard small clusters. The surviving color clusters are considered as belonging to the foreground. In a different variation, other clustering techniques can be used that automatically determines the best number of clusters. The color model is then represented by the set of cluster centers. Each pixel is assigned the color of the closest learned cluster in the color space. In step 310, a color model for the background is also estimated (background color model) by taking an external window (i.e., a ring around the estimated bounding box). The color vectors in the external window are clustered following the same procedure than for the foreground model. Once the foreground and background model are obtained, a post-processing on the models is applied. For Each foreground model cluster center, the minimum distance between itself and the background model clusters is computed. If this distance is lower than a threshold, we consider that the cluster is not discriminative enough and it is removed from the foreground model. Then in step 315, the bounding box is determined by a process of window growing. Starting from the estimated bounding box, the size of the window is iteratively enlarged as long as the newly added points of the region are more likely to belong to the foreground model than to the background model. More in detail, for each side of the bounding box (top, left, right, bottom) a new line (row or column) of pixels is added. For each new pixel its distance to the foreground and background models are computed as the minimum distance among the distances to each model cluster. A score is computed for each pixel that in a realization of the invention is the difference of the distance to the background minus the distance to the foreground, such that a high score implies that the pixel is far from the background model and close to the foreground model. The average of pixels scores for the new added line is calculated and if it is bigger than a threshold, the line is kept as part of the bounding box. The threshold is naturally set at 0, as the score can be negative (meaning “closer” to the background) or positive (“closer” to the foreground), and 0 means equal score. Anyways, it is a parameter that might be modified. In this way, taking each side in turn the window is enlarged until no new line is added. Finally, and as noted earlier, the bounding box is displayed containing the object of interest as illustrated in FIG. 9 by bounding box 139.
It should also be noted that assisted selection based on joint motion and color processing in accordance with the principles of the invention can be performed on multiple objects of interest as illustrated in FIG. 10, where the user initially selects at least a single point on each player of interest.
Turning briefly to FIG. 11, an illustrative high level block diagram of a device 500, e.g., a smart phone, for providing a bounding box in accordance with the principles of the invention, as illustrated by the flow charts of FIGS. 1, 4, and 8, is shown. Only those portions relevant to the inventive concept are shown. As such, device 500 can perform other functions. Device 500 is a processor based system as represented by processor 505. The latter represents one, or more, stored-program controlled processors as known in the art. In other words, processor 505 executes programs stored in memory 510. The latter represents volatile and/or non-volatile memory, e.g., hard disk, CD-ROM, DVD, random access memory (RAM), etc.) for storing program instructions and data, e.g., for performing the illustrative flow charts shown in FIGS. 1, 4 and 8, for providing a bounding box containing an object of interest. Device 500 also has communications block 130, which supports communications of data over a data connection 541 as known in the art. Data communications can be wired, or wireless, utilizing 802.11, 3G LTE, 4G LTE, etc. Finally, device 500 includes a display 530 for providing information to a user, e.g., displaying a video sequence showing the bounding box containing the object of interest. It is assumed that display 530 is a touch screen and, as such, enables selection by the user of an object of interest as illustrated in FIGS. 2 and 3. However, it should be noted that the inventive concept is not so limited and other input devices can be used, e.g., a keyboard/mouse input device.
As described above, we solve the problem of how to locate the bounding box on an object of interest on a display. Once a single point, or a trace, is selected on an object of interest, the system, or device, automatically determines the bounding box based on motion and color propagation. In other words, a single touch or trace determines a few points that belong to the object of interest, and the bounding box is then determined by flood-filling following motion and color features. In accordance with the principles of the invention, the region filling is determined by color propagation, and uses motion similarity as another feature for determining the pixels that are likely to belong to the same object as the selected points. That is why it is important to use motion information in order to determine which are the object's parts not only from the appearance point of view, but also on how the object coherently moves.
In view of the above, the foregoing merely illustrates the principles of the invention and it will thus be appreciated that those skilled in the art will be able to devise numerous alternative arrangements which, although not explicitly described herein, embody the principles of the invention and are within the scope. It is therefore to be understood that numerous modifications may be made to the illustrative embodiments and that other arrangements may be devised without departing from the scope of the present principles.

Claims

1. A method for determining a bounding box for display on a device, the bounding box containing an object in a video sequence, the method comprising:

selecting at least one point that belongs to the object;

motion processing an area of points around the selected at least one point to determine an estimated bounding box; and

color processing the points in the estimated bounding box to determine the bounding box;

the color processing further comprising:

adding a new line of pixels;

computing a score for each new pixel, wherein the score is equal to a difference between a distance to a background model and a distance to a foreground model;

averaging the scores for the new line of pixels; wherein if the average score for the new line of pixels is greater than a threshold, the new line of pixels is added to the estimated bounding box;

wherein the bounding box is formed when no new line of pixels is added.

2. The method of claim 1, wherein the selecting is performed by a user.

3. The method of claim 1, wherein the motion processing uses motion flood-filling on a Delaunay triangulation.

4. An apparatus comprising a memory associated with at least one processor configured to:

display a video sequence and for allowing a selection of at least one point on an object of interest in the displayed video sequence;

stores in the memory a motion processing program and a color processing program; and

process the selected at least one point with the stored motion processing program and the stored color processing program for determining a bounding box;

wherein the stored motion processing program comprises instructions for motion flood-filling on a Delaunay triangulation to determine an estimated bounding box; the stored color processing program further comprising instructions:

for adding a new line of pixels to the estimated bounding box;

for computing a score for each new pixel, wherein the score is equal to a difference between a distance to a background model and a distance to a foreground model; and

for averaging scores for the new line of pixels and adding the new line to the estimated bounding box if the average score for the new line of pixels is greater than a threshold

wherein the bounding box is formed when no new line of pixels is added.

5. The apparatus of claim 4, wherein said means for displaying correspond to a display and said means for allowing a selection to an input device.

6. The apparatus of claim 5, wherein the input device is as least one of a mouse or keyboard.