Method of motion segmentation in video using randomized voting and system having the same

Abstract

The video-motion segmentation method using a randomized voting is provided which includes receiving the video, extracting a plurality of feature points from the video, and grouping the plurality of feature points by applying a randomized voting method using a score histogram on each of the at least some feature points of the plurality of feature points.

Claims

1. A video-motion segmentation method using a randomized voting, comprising: receiving a video; extracting a plurality of feature points from the video; and grouping the plurality of feature points by applying a randomized voting method using a score histogram on each of at least some feature points of the plurality of feature points; wherein the grouping of the plurality of feature points comprises: randomly grouping the plurality of feature points based on the predetermined number of groups; selecting the at least some feature points from a plurality of groups, which are obtained by grouping the at least some feature points, based on the predetermined number of feature points selected by the group; obtaining a fundamental matrix on each of the plurality of groups from the at least some feature points; using a sampson distance method to calculate a distance between each of the at least some feature points and a fundamental matrix on each of the plurality of groups; updating the score histogram on each of the at least some feature points based on an objective function defined as the distance; and regrouping the at least some feature points based on the updated score histogram; and wherein a comparison of the locations of the at least some feature points from each of the grouping and the regrouping is used in analyzing movement of an object represented by the at least some feature points.

2. The video-motion segmentation method of claim 1, wherein the updating of the score histogram comprises: accumulating a score of a group corresponding to a fundamental matrix, which minimizes the objective function on the score histogram having an interval corresponding to each of the plurality of groups, with respect to the at least some feature points.

3. The video-motion segmentation method of claim 1, wherein the regrouping of the at least some feature points comprises: regrouping each of the at least some feature points into a group corresponding to the highest score on the updated score histogram.

4. The video-motion segmentation method of claim 1, wherein the using of the sampson distance method comprises: accumulating the distance with respect to at least two or more video frames, and wherein the updating of the score histogram comprises: updating the score histogram on each of the at least some feature points based on the objective function.

5. The video-motion segmentation method of claim 1, wherein the regrouping of the at least some feature points comprises: using a plurality of groups, which are obtained by regrouping the at least some feature points, in a next process to be repeated, when the randomized voting method is repeated.

6. The video-motion segmentation method of claim 1, wherein the regrouping of the at least some feature points comprises: stopping regrouping the at least some feature points by comparing the number of randomized voting methods performed with a predetermined repetition count or comparing the objective function on each of at least some feature points selected from the plurality of groups, which are obtained by regrouping at least some feature points, with a predetermined value.

7. The video-motion segmentation method of claim 6, wherein the regrouping of the at least some feature points comprises: selectively performing a spectral clustering on the at least some feature points.

8. The video-motion segmentation method of claim 1, wherein the extracting of the plurality of feature points comprises: extracting the plurality of feature points through at least two or more video frames.

9. The video-motion segmentation method of claim 1, wherein the extracting of the plurality of feature points comprises: applying a kanade-lukas-tomasi (hereafter referred as to KLT) method to extract the plurality of feature points from the video.

10. A non-transitory machine-readable recording medium storing a program for executing a method set forth in claim 1.

Description

DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a diagram for describing a randomized voting method applied in a video motion segmentation method.

(2) FIGS. 2A to 2D are diagrams for describing a video-motion segmentation method according to an embodiment of the inventive concept.

(3) FIG. 3 is a flow chart illustrating a motion segmentation method in a video according to an embodiment of the inventive concept.

(4) FIG. 4 is a flow chart schematically illustrating grouping of a plurality of feature points using a randomized voting method shown in FIG. 3.

(5) FIG. 5 is a block diagram illustrating a video motion segmentation system according to an embodiment of the inventive concept.

BEST MODE

(6) Mode for Invention

(7) Hereinafter, the attached drawings will be referred to describe an optical logic circuit operating with light reflection control, and a computation device using the optical logic circuit in accordance with embodiments of the present disclosure.

(8) Various embodiments of the present disclosure as described hereinafter are provided to detail features of the present disclosure, not to restrict or concretely define the scope of inventive concept thereof. Rather, it will be properly construed that all of modifications, alterations, or variations derivable by those skilled in the art may be included in the scope of the present disclosure.

(9) FIG. 1 is a diagram for describing a randomized voting method applied in a video motion segmentation method.

(10) Referring to FIG. 1, a motion segmentation system according to an embodiment of the inventive concept may apply a randomized voting method using a score histogram 130 on each of at least a portion 120 of a plurality of feature points 110 in a motion segmentation process which divides feature points having different motions or groups feature points having the same motion in a video.

(11) Specifically, after randomly grouping the plurality of feature points 110 into a first group 140 and a second group 150, the motion segmentation system may regroup at least a portion 120 of the feature points 110 into a first group 140 or a second group 150 by selecting the at least a portion 120 from a plurality of groups 140 and 150 and utilizing the score histogram 130 on each of the selected feature points 120.

(12) Here, the motion segmentation system may obtain a fundamental matrix on each of the plurality of groups 140 and 150 and update the score histogram 130 on each of the selected the feature points 120 based on an objective function defined as a distance between each of the selected feature points 120 and a fundamental matrix on each of the plurality of groups 140 and 150, thereby making it possible to regroup the selected feature points 120 using the updated score histogram 130.

(13) As the randomized voting method is repeated, the selected feature points 120 of the plurality of feature points 110 may be continuously regrouped based on an objective function. Accordingly, feature points having different motions of the plurality of feature points 110 may be divided into different groups, and feature points having the same motion of the plurality of feature points 110 may be classified into the same group. The detailed description on the randomized voting method may be described as follows.

(14) Therefore, the motion segmentation system may perform a motion segmentation method which is robust to noise and improves a processing speed and accuracy by applying the randomized voting method.

(15) FIGS. 2A to 2D are diagrams for describing a video-motion segmentation method according to an embodiment of the inventive concept.

(16) Referring to FIG. 2A, a motion segmentation system may randomly group a plurality of feature points 210 extracted from a video based on the predetermined number of groups and select at least a portion 240 (illustrated by cross-marks having a circular or rectangular boundary) from a plurality of groups 220 and 230, in which the plurality of feature points 210 are randomly grouped, based on the predetermined number of feature points selected by the group.

(17) For example, when the predetermined number of groups is two and the predetermined number of feature points selected by the group is seven, the motion segmentation system may randomly group the plurality of feature points 210 into a first group 220 and a second group 230, select seven first feature points 241 (illustrated by cross-marks having a circular boundary) from the first group 220, and select seven second feature points 242 (illustrated by cross-marks having a rectangular boundary) from the second group 230.

(18) Referring to FIG. 2B, the motion segmentation system may obtain a fundamental matrix on each of the plurality of groups 220 and 230 from at least some feature points 240. Here, a process for obtaining a fundamental matrix may use existing calculating methods. The detailed description on the method may be omitted, because it gets out from the spirit and scope of the inventive concept. Here, the motion segmentation system may obtain a fundamental matrix to correspond to each of the plurality groups 220 and 230. Accordingly, the number of fundamental matrices to be obtained may be the same as the predetermined number of groups.

(19) For example, the motion segmentation system may obtain a first fundamental matrix on the first group 220 from first feature points 241 as illustrated in FIG. 2B (a) and obtain a second fundamental matrix on the second group 230 from second feature points 242 as illustrated in FIG. 2B (b).

(20) Next, the motion segmentation system may use a sampson distance method to calculate a distance between each of at least some feature points 240 and a fundamental matrix on each of the groups 220 and 230. In detail, the motion segmentation system may calculate a distance between each of the at least some feature points 240 and the first fundamental matrix and a distance between each of the at least some feature points 240 and the second fundamental matrix, respectively.

(21) For example, the motion segmentation system may calculate a distance between each of the at least some feature points 240 and a fundamental matrix on each of the groups 220 and 230, using the sampson distance method expressed by the following equation 1.

(22) $\begin{array}{cc}\mathrm{SD}\left(x,y,F\right)=\frac{y^T{F}_x}{{\left(F_x\right)}_1^2+{\left(F_x\right)}_2^2+{\left(F_y\right)}_1^2+{\left(F_y\right)}_2^2}& \left[\mathrm{Equation}1\right]\end{array}$

(23) In Equation 1, SD(x, y, F) may denote a distance between a specific feature point having coordinates (x, y) in a video and a fundamental matrix F. (F.sub.x).sub.j.sup.2 may denote a j-th item of the fundamental matrix F.sub.x.

(24) The motion segmentation system may accumulate a distance, which is calculated using the Sampson distance method, between each of the at least some feature points 240 and a fundamental matrix on each of the plurality of groups 220 and 230 with respect to at least two or more video frames.

(25) $\begin{array}{cc}\begin{array}{c}E\left(X_k,F_g\right)=\underset{i=1}{\overset{f}{.Math.}}\underset{j=1}{\overset{f}{.Math.}}\mathrm{SD}\left(x_k^{\left(i\right)},x_k^{\left(j\right)},F_g^{\left(i,j\right)}\right)\\ 0\end{array}& \left[\mathrm{Equation}2\right]\end{array}$

(26) In Equation 2, E(X.sub.k, F.sub.g) may denote a value in which a distance between a k-th specific feature point X.sub.k of the at least some feature points 240 and a fundamental matrix F.sub.g is accumulated with respect to at least two or more video frames. Here, because g denotes a group in which the plurality of feature points 210 are grouped, F.sub.g denotes a fundamental matrix corresponding to a group g. X.sub.k.sup.(i) may denote a coordinate of a specific feature point X.sub.k in a i-th video frame. X.sub.k.sup.(j) may denote a coordinate of a specific feature point X.sub.k in a j-th video frame. F.sub.g.sup.(i,j) may denote a fundamental matrix which is obtained from a i-th frame and a j-th frame. f may denote the total number of video frames.

(27) When a specific feature point is grouped into a proper group, a distance between a specific feature point, accumulated with respect to at least two or more video frames, and a fundamental matrix, corresponding to the proper group, may approximate to 0. Therefore, the motion segmentation system may set an objective function, as expressed by Equation 2, using the described characteristic. Here, the objective function may be defined as a distance between each of at least some feature points 240, accumulated with respect to at least two or more video frames, and a fundamental matrix on each of the plurality of groups 220 and 230

(28) Referring to FIG. 2C, the motion segmentation system may update a score histogram 250 on each of at least some feature points 240 based on an objective function defined as a distance between each of the at least some feature points 240 and a fundamental matrix on each of the groups 220 and 230. Here, the score histogram 250 on each of the at least some feature points 240 may have an interval corresponding to each of the groups 220 and 230.

(29) Specifically, the motion segmentation system may select any group, corresponding to a fundamental matrix which minimizes the objective function, expressed by Equation 2, on the score histogram 250 with respect to each of the at least some feature points 240, according to Equation 3 and accumulate a score of the selected group according to Equation 4, thereby making it possible to update the score histogram 250 on each of the at least some feature points 240.

(30) $\begin{array}{cc}\hat{g}=\arg \underset{g}{\min }E\left(X_k,F_g\right)& \left[\mathrm{Equation}3\right]\end{array}$

(31) In Equation 3, may denote any group corresponding to a fundamental matrix which minimizes the objective function.
h.sub.i[g]h.sub.i[g]+e.sup.d.sup.i[Equation 4]

(32) In Equation 4, d.sub.i may be SD(x.sub.i.sup.(k), F.sub.g.sup.(k,l)) and denote a distance between a i-th specific feature point, having a coordinate x.sub.i.sup.(k) in a k-th frame and a coordinate x.sub.i.sup.(l) in a l-th video frame, and a fundamental matrix F.sub.g.sup.(k,l) obtained from the k-th frame and the l-th frame in the video. may denote a parameter for adjusting an accumulation intensity. h.sub.i[g] may denote an interval g of the score histogram 250 on the i-th specific feature point. Here, the interval g may correspond to any group corresponding to a fundamental matrix which minimizes an objective function.

(33) Here, the motion segmentation system may accumulate a score on remaining groups on the score histogram 250 on each of the at least some feature points 240 according to Equation 5 as well as accumulate a score of any group corresponding to a fundamental matrix which minimizes an objective function on the score histogram 250 on each of the at least some feature points 240.
h.sub.i[{tilde over (g)}]h.sub.i[{tilde over (g)}]e.sup.d.sup.i+1, for all {tilde over (g)}g[Equation 5]

(34) In Equation 5, h.sub.i[{tilde over (g)}] may denote an interval {tilde over (g)} of the score histogram 250 on the i-th specific feature point. Here, the interval {tilde over (g)} may correspond to the remaining groups except for any group corresponding to a fundamental matrix which minimizes an objective function.

(35) That is, the motion segmentation system may relatively more accumulate a score of any group corresponding to a fundamental matrix which minimizes an objective function the score histogram 250 on each of at least some feature points 240 and relatively less accumulate a score on the remaining groups, instead of accumulating only a score of any group corresponding to a fundamental matrix which minimizes an objective function on the score histogram 250 on each of at least some feature points 240.

(36) Accordingly, referring to FIG. 2D, the motion segmentation system may regroup each of at least some feature points 240 into a group corresponding to the highest score on the updated score histogram 250 on each of the at least some feature points 240 according to Equation 6.

(37) $\begin{array}{cc}\hat{g}=\arg \underset{g}{\max }{h}_i\left[g\right]\mathrm{for}i=1,\mathrm{.Math.},n& \left[\mathrm{Equation}6\right]\end{array}$

(38) In Equation 6, may denote a group, corresponding to the highest score, from among a plurality of groups 220 and 230.

(39) For example, a first feature point 260 may be included in the first group 220 in a first random grouping process. However, when a group corresponding to the highest score on a score histogram on the first feature point 260 is the second group 230, the first feature point 260 may be regrouped into the second group 230. A second feature point 270 may be included in the second group 230 in a first randomly grouped process. However, when a group corresponding to the highest score on a score histogram on the second feature point 270 is the first group 220, the second feature point 270 may be regrouped into the first group 220.

(40) The randomized voting method may be repeated. When the randomized voting method is repeated, a plurality of groups, which are obtained by regrouping at least some feature points 240, may be used in a next process of the randomized voting method. For example, the motion segmentation system may use the plurality of groups 220 and 230 obtained through regrouping of at least some feature points 240 in selecting the at least some feature points 240 from the plurality of groups 220 and 230 in which the plurality of feature points 210 are randomly grouped. Accordingly, the motion segmentation system may select at least a portion from a plurality of groups, in which at least some feature points 240 are regrouped, instead of selecting the at least some feature points 240 from the plurality of groups 220 and 230, in which the plurality of feature points 210 are randomly grouped.

(41) Here, the randomized voting method which is repeated may terminate by comparing the number of randomized voting methods performed with a predetermined repetition count or comparing an objective function on each of at least some feature points selected from the plurality of groups, in which the at least some feature points 240 are regrouped, with a predetermined value. Furthermore, the randomized voting method may terminate by stopping regrouping at least some feature points 240.

(42) FIG. 3 is a flow chart illustrating a motion segmentation method in a video according to an embodiment of the inventive concept.

(43) Referring to FIG. 3, a motion segmentation system according to an embodiment of the inventive concept may receive a video (310).

(44) Next, the motion segmentation system may extract a plurality of feature points from the video (320). Here, the motion segmentation system may extract a plurality of feature points from at least two or more video frames. Moreover, the motion segmentation system may apply a kanade-lukas-tomasi (hereafter referred as to KLT) method to extract a plurality of feature points from the video.

(45) After that, the motion segmentation system may group a plurality of feature points by applying a randomized voting method using a score histogram on each of at least some feature points of the plurality of feature points (330). This will be more fully described with reference to FIG. 4.

(46) FIG. 4 is a flow chart schematically illustrating grouping of a plurality of feature points using a randomized voting method shown in FIG. 3.

(47) Referring to FIG. 4, the motion segmentation system according to an embodiment of the inventive concept may randomly group a plurality of feature points based on the predetermined number of groups (410).

(48) The motion segmentation system may select at least some feature points from a plurality of groups, which are obtained by randomly grouping the plurality of feature points, based on the predetermined number of feature points selected by the group (420).

(49) Next, the motion segmentation system may obtain a fundamental matrix on each of a plurality of groups from at least some feature points (430).

(50) After that, the motion segmentation system may use a sampson distance method to calculate a distance between each of at least some feature points and a fundamental matrix on each of a plurality of groups (440).

(51) Here, the motion segmentation system may accumulate a distance between each of the at least some feature points and a fundamental matrix on each of a plurality of groups with respect to at least two or more video frames in a process for applying the sampson distance method. Accordingly, when updating a score histogram on each of the at least some feature points (450), the motion segmentation system may update a score histogram on each of the at least some feature points based on an objective function defined as the distance between each of the at least some feature points, which are accumulated with respect to at least two or more video frames, and a fundamental matrix on each of a plurality of groups.

(52) Next, the motion segmentation system may update a score histogram on each of the at least some feature points based on an objective function defined as a distance between each of the at least some feature points and a fundamental matrix on each of a plurality of groups (450).

(53) Here, the motion segmentation system may accumulate a score of any group corresponding to a fundamental matrix which minimizes an objective function on a score histogram having an interval corresponding to each of a plurality of groups, thereby making it possible to update a score histogram on each of the at least some feature points.

(54) After that, the motion segmentation system may regroup the at least some feature points based on the updated score histogram (460). In detail, the motion segmentation system may regroup each of the at least some feature points into a group corresponding to the highest score on the updated score histogram.

(55) Moreover, the motion segmentation system may determine an end condition to repeat or cease the aforementioned randomized voting method (470).

(56) For example, the motion segmentation system may stop regrouping the at least some feature points, by comparing the number of randomized voting methods performed with a predetermined repetition count or comparing an objective function on at least some feature points selected from the plurality of groups, which are obtained by regrouping the at least some feature points, with a predetermined value.

(57) When the randomized voting method is repeated, the motion segmentation system may use a plurality of groups, which are obtained by regrouping the at least some feature points, in the next process to be repeated.

(58) Further, although not shown in figures, when the randomized voting method is ceased, the motion segmentation system may selectively perform spectral clustering on the at least some feature points.

(59) FIG. 5 is a block diagram illustrating a video motion segmentation system according to an embodiment of the inventive concept.

(60) Referring to FIG. 5, a motion segmentation system according to an embodiment of the inventive concept may include a video input unit 510, a feature point extracting unit 520, and a randomized voting method applying unit 530.

(61) The video input unit 510 may receive a video.

(62) The feature point extracting unit 520 may extract a plurality of feature points from the video. Here, the feature point extracting unit 520 may extract a plurality of feature points through at least two or more video frames. Moreover, the feature point extracting unit 520 may use a KLT method to extract a plurality of feature points from the video.

(63) The randomized voting method applying unit 530 may apply a randomized voting method using a score histogram on each of the at least some feature points of the plurality of feature points, to group the plurality of feature points.

(64) Here, although not illustrated in figures, the randomized voting method applying unit 530 may include a grouping unit, a feature point selecting unit, a fundamental matrix obtaining unit, a distance calculating unit, a score histogram updating unit, and a regrouping unit.

(65) The grouping unit may randomly group a plurality of feature points based on the predetermined number of groups.

(66) The feature point selecting unit may select the at least some feature points from a plurality of groups, in which a plurality of feature points are randomly grouped, based on the number of feature points selected by the group.

(67) The fundamental matrix obtaining unit may obtain a fundamental matrix on each of a plurality of groups from at least some feature points.

(68) The distance calculating unit may use a sampson distance method to calculate a distance between each of at least some feature points and a fundamental matrix on each of a plurality of groups.

(69) Here, when applying the sampson distance method, the distance calculating unit may accumulate a distance between each of at least some feature points and a fundamental matrix on each of a plurality of groups with respect to at least two or more video frames, thereby making it possible for the score histogram updating unit to update a score histogram on each of at least some feature points based on an objective function. Here, the objective function may be defined as a distance, which is accumulated with respect to at least two or more video frames, between each of at least some feature points and a fundamental matrix on each of a plurality of groups.

(70) The score histogram updating unit may update a score histogram on each of at least some feature points based on the objective function.

(71) Here, the score histogram updating unit may update a score histogram on each of at least some feature points by accumulating a score of any group corresponding to a fundamental matrix, which minimizes an objective function on a score histogram having an interval corresponding to each of a plurality of groups, with respect to each of at least some feature points.

(72) The regrouping unit may regroup at least some feature points based on the updated score histogram. In detail, the regrouping unit may regroup each of at least some feature points into a group corresponding to the highest score on the updated score histogram.

(73) Moreover, the regrouping unit may determine an end condition to repeat or cease a randomized voting method.

(74) For example, the regrouping unit may cease regrouping the at least some feature points by comparing the number of randomized voting methods performed with a predetermined repetition count or comparing an objective function on each of at least some feature points selected from the plurality of groups, which are obtained by regrouping at least some feature points, with a predetermined value.

(75) When the randomized voting method is repeated, the regrouping unit may use a plurality of groups, which are obtained by regrouping at least some feature points, in the next process to be repeated.

(76) Furthermore, when the randomized voting method is ceased, the regrouping unit may selectively perform a spectral clustering on the at least some feature points.

(77) The aforementioned device may be implemented with a hardware component, a software component, and/or a combination of a hardware component and a software component.

(78) A method according to an embodiment of the inventive concept may be implemented with a program command shape which can be performed through various computer means and be recorded to a computer-readable medium.