Image Sprite
LANGUAGE/Tool: matlab
Overview of the project
Motivation
- How to animate 2D image by the user control
Problem which I had
- When a image (A) transit to another (B), the system should choose optimal path (showing intermediate images between A and B) for smooth animation. The method to find optimal path needs to be studied.
Which features are included in this project
- Building all path network
- Efficient path finding
- Interpolating keyframe images to generate intermediate frame
How to solve the problem
- Built distance map to find all possible path and used Markov chain to find optimal path.
Detail of the project
1.Introduction
Markov Chain is the main theoretical basis, which is the system of the transition from one state to another. Using this, it is able to understand the relationship among frames and it is shown as a distance map defining the similarity of frames. As a result of this, transition between frames has been done if they are similar enough.
2. Specification
2.1 Finding optimal path
When the distance map is computed firstly, almost all nodes(frames) will have connection to each other. Since the weight between nodes are not considered to find the shortest path, threshold has to be taken into account to limit the number of connection. It is important because if there is not threshold in connection, the transition will be done even though two frames are less similar. Following graph is after thresholding.
When user picks a path, the first point will be the origin of video sprite algorithm (Assume that user selects nose as a initial point). Next step is to find new position from this origin. Using velocity map, it is able to find new position of nose in another frame if those frames have connection. For example, the the point on the nose is (230, 150) in frame 23 and the frame has connection with 41. Then we can look up velocity map for frame(23,41) and vx, vy in the point (230, 150) is 2.31 and -1.4 respectively. New position of the nose in 41 will be (232.31, 148.6).
In order to propagate new position, DFS (Depth-First Search) has been used.
In order to propagate new position, DFS (Depth-First Search) has been used.
From the initial point ‘1’ in the graph above, position ‘2’ will be computed using velocity map between two nodes and then from new position of ‘2’, positions for ‘3’ and ‘4’ will be decided. This process will be continued until every nodes are visited.
2.2 Generating intermediate frame
Since we know about the current and next frames, and their relationship from optical flow, it is possible to synthesise frames between them.
2.2 Generating intermediate frame
Since we know about the current and next frames, and their relationship from optical flow, it is possible to synthesise frames between them.
When we found intermediate position, the system generate intermediate frame.