Method and apparatus for video sequential alignment

1. A method for video sequential alignment, comprising:

inputting a first video sequence and a second video sequence;

extracting features of the first video sequence and the second video sequence;

generating an expanded path using a hierarchical sequential alignment algorithm;

generating masks containing search space using keyframe matching;

calculating the lowest path cost within search space to find a minimal alignment path using a block A* algorithm; and

outputting a final alignment result after applying the block A* algorithm to search space;

wherein calculating the lowest path cost within search space to find a minimal alignment path using a block A* algorithm further includes:

dividing a cost matrix into blocks, therein a first dimension of the cost matrix represents the features extracted from the first video sequence, and a second dimension of the cost matrix represents the features extracted the second video sequence;

evaluating each block within the search space;

calculating heuristic cost function per block, wherein the heuristic cost function promotes diagonal movement;

calculating accumulated optimal path cost per block; and

updating the evaluated block.

2. The method according to claim 1 , wherein calculating the lowest path cost within search space to find a minimal alignment path using a block A* algorithm further includes:

dividing a cost matrix into blocks;

evaluating each block;

calculating heuristic cost function per block;

calculating optimal path cost per block; and

updating the evaluated block.

3. The method according to claim 2 , wherein:

the heuristic function that promotes diagonal movements is defined as a distance of a current position to a line u T , wherein u T is perpendicular to the diagonal; and

the heuristic cost function is defined by:

h

⁡

(

n

,

m

)

=

(

(

N

,

M

)

-

(

n

,

m

)

)

*

u



u



⁢

H

,

wherein H is a constant heuristic cost factor that is dependent on input data;

u



u



 is a diagonal unit vector; N and M are the dimension of the cost matrix; n and m are indexes from the two video sequences, respectively.

4. The method according to claim 2 , wherein:

an admissible heuristic cost is also defined by:

h ( n,m )=abs(( N−n )−( M−m ))* W

wherein N and M are the sequence length; the cost for nondiagonal movement W is a constant penalty; and n and m are indexes from the two video sequences, respectively.

5. The method according to claim 2 , wherein:

the A* algorithm only saves one accumulated optimal path cost ĝ-score of a block; and

the path cost of the block is calculated by:

f=h inter +ĝ

wherein h inter represents the heuristic cost from an upper right block corner to a goal, and ĝ represents a value for the ĝ-score of a current block.

6. The method according to claim 1 , wherein generating an expanded path using a hierarchical sequential alignment algorithm further includes:

extracting keyframes on the first video sequence and the second video sequence;

based on the obtained keyframes of the two video sequences, obtaining a path with minimum accumulated cost using a constrained dynamic time warping (CDTW) algorithm; and

creating path estimation by connecting all projected points with lines and providing masked region for the block A* algorithm.

7. The method according to claim 6 , wherein:

after creating path estimation by connecting all projected points with lines, the extended path is obtained by performing a morphological opening operation to the created path.

8. The method according to claim 6 , wherein the CDTW algorithm does not include a manually defined penalty.

9. The method according to claim 1 , wherein:

the path cost of the block is calculated by adding the accumulated optimal past cost of the block and a heuristic cost from an upper right block corner to a goal.

10. The method according to claim 1 , wherein

the heuristic function that promotes diagonal movements is defined as a distance of a current position to a line u T , wherein u T is perpendicular to the diagonal; and

the heuristic cost function is defined by:

h

⁡

(

n

,

m

)

=

(

(

N

,

M

)

-

(

n

,

m

)

)

*

u



u



⁢

H

,

wherein H is a constant heuristic cost factor that is dependent on input data;

u



u



 is a diagonal unit vector; N and M are the dimension of the cost matrix; n and m are indexes from the two video sequences, respectively.

11. A method for video sequential alignment, comprising:

inputting a first video sequence and a second video sequence;

extracting features of the first video sequence and the second video sequence;

generating an expanded path using a hierarchical sequential alignment algorithm;

generating masks containing search space using keyframe matching;

calculating the lowest path cost within search space to find a minimal alignment path using a block A* algorithm; and

outputting a final alignment result after applying the block A* algorithm to search space;

wherein generating an expanded path using a hierarchical sequential alignment algorithm further includes:

extracting keyframes on the first video sequence and the second video sequence;

based on the obtained keyframes of the two video sequences, obtaining a path with minimum accumulated cost using a constrained dynamic time warping (CDTW) algorithm; and

creating path estimation by connecting all projected points with lines and providing masked region for the block A* algorithm;

wherein extracting keyframes on the two video sequences further includes:

calculating differential dX and dY of the two video sequences X=[x 1 ,x 2 , . . . x N ] and Y=[y 1 ,y 2 , . . . y M ], wherein N and M are length of the two video sequences X and Y;

identifying a beginning and an end of every scene by applying a shot detection method on dX and dY; and

selecting a first and a last local minimum of dX and dY in each scene as keyframes.

12. The method according to claim 11 , wherein:

elements of the differential dX=[dx 1 ,dx 2 , . . . dx N−1 ] are calculated by:

dx n =|x n+1 −x n |,

wherein n is an integer between 1 and N−1; and

elements of the differential dY=[dy 1 ,dy 2 , . . . dy M−1 ] are calculated by:

dy m =|y m+1 −y m |,

wherein m is an integer between 1 and M−1.

13. The method according to claim 11 , wherein creating path estimation by connecting all projected points with lines and providing masked region for the block A* algorithm further includes:

calculating a scaling factor f i−1,i for line between a keypoint i−1 and i of a structure element by:

f

i

-

1

,

i

=

C

(

v

i

-

1

,

i



v

i

-

1

,

i



*

u



u



)

2

,

wherein C is a constant which regulates uncertainty in the path estimation;

u



u



 is a diagonal unit vector; i is an integer; and v i−1,i is a vector from the keypoint i−1 to i.

14. An apparatus for video sequential alignment, comprising:

an input video sequence module configured to provide two video sequences from any appropriate type of source for video contents;

a feature extraction module configured to extract the feature vectors of the first video sequence and the second video sequence;

a hierarchical sequential alignment (HSA) module configured to generate an expanded path using a hierarchical sequential alignment algorithm;

a keyframe matching module configured to generate masks containing search space;

a calculation module configured to calculate the lowest path cost within search space to find a minimal alignment path using a block A* algorithm; and

an output module configured to output a final alignment result after applying the block A* algorithm to the search space;

wherein the keyframe matching module further includes:

a keyframe extraction unit configured to extract keyframes on the first video sequence and the second video sequence;

a path obtaining unit configured to, based on the obtained keyframes of the two video sequences, obtain a path with minimum accumulated cost using a constrained dynamic time warping (CDTW) algorithm; and

a path estimation unit configured to, based on the obtained path, create path estimation by connecting all the projected points with lines and pass masked region to the calculation module;

wherein the keyframe extraction unit is further configured to:

calculate differential dX and dY of the two video sequences X=[x 1 ,x 2 , . . . x N ] and Y=[y 1 ,y 2 , . . . y M ], wherein N and M are length of the two video sequences X and Y;

identify a beginning and an end of every scene by applying a shot detection method on dX and dY; and

select a first and a last local minimum of dX and dY in each scene as keyframes.

15. The apparatus according to claim 14 , wherein:

elements of the differential dX=[dx 1 ,dx 2 , . . . dx N−1 ] are calculated by:

dx n =|x n+1 −x n |,

wherein n is an integer between 1 and N−1; and

elements of the differential dY=[dy 1 ,dy 2 , . . . dy M−1 ] are calculated by:

i dy m =|y m+1 −y m |,

wherein m is an integer between 1 and M−1.

16. The apparatus according to claim 14 , wherein:

calculating a scaling factor f i−1,i for the line between a keypoint i−1 and i of a structure element by:

f

i

-

1

,

i

=

C

(

v

i

-

1

,

i



v

i

-

1

,

i



*

u



u



)

2

,

wherein C is a constant which regulates uncertainty in the path estimation;

u



u



 is a diagonal unit vector; i is an integer; and v i−1,i is a vector from the keypoint i−1 to i.

17. The apparatus according to claim 14 , wherein:

a cost matrix is divided into blocks;

each block is evaluated;

heuristic cost function per block is calculated;

optimal path cost per block is calculated; and

the evaluated block is updated.

18. The apparatus according to claim 17 , further including:

the heuristic function that promotes diagonal movements is defined as a distance of a current position to a line u T , wherein u T is perpendicular to the diagonal; and

the heuristic cost function is defined by:

h

⁡

(

n

,

m

)

=

(

(

N

,

M

)

-

(

n

,

m

)

)

*

u



u



⁢

H

,

wherein H is a constant heuristic cost factor that is dependent on input data;

u



u



 is a diagonal unit vector; N and M are the dimension of the cost matrix; n and m are indexes from the two video sequences, respectively.

19. The apparatus according to claim 17 , wherein:

an admissible heuristic cost is also defined by:

h ( n,m )=abs(( N−n )−( M−m ))* W

wherein N and M are the sequence length; the cost for nondiagonal movement W is a constant penalty; and n and m are indexes from the two video sequences, respectively.

20. The apparatus according to claim 17 , wherein:

the A* algorithm only saves one accumulated optimal path cost ĝ-score of a block; and

the path cost of the block is calculated by:

f=h inter +ĝ

wherein h inter represents the heuristic cost from an upper right block corner to a goal, and ĝ represents a value for the ĝ-score of a current block.