Stroke Correspondence by Labeling Closed Areas

Many techniques have been proposed to automatically generate inbetweening frames from keyframes, which are composed of strokes (vector lines) [1, 2, 3, 4, 7, 8, 9, 10]. In general, stroke correspondences between keyframes are determined by imposing restrictions, such as drawing orders [13, 14]. However, in many cases, a keyframe is composed of hundreds of strokes, and users invest a lot of time and effort to determine the correspondence. In addition, several studies on automatic methods have focused on a narrower range of target strokes, such as boundary lines [15, 16], but they are difficult to determine inner strokes in closed area. Hence, recent studies discuss how to construct stroke correspondence.

In studies of Fujita et al.[6, 17], two keyframes are projected onto a three-dimensional virtual canvas. Several strokes set by the users in each keyframe will overlay each other when transforming the shape of the canvas, and the correspondence is estimated by combinatorial optimization based on distance. Whited et al. [18] construct a connection graph based on a relationship between the keyframes, estimating the correspondence by performing a depth-first search on the graph. However, this process fails when storkes are occluded in more complex scenes, or change in shapes and numbers of strokes between keyframes take place.

Yang et al. [11] utilize characteristics of neighboring strokes (e.g., stroke shapes), and propose a method to create a correspondence between keyframes by using a greedy algorithm. This system enables users to manually specify several constraints and handle the estimated results (correspondence). In addition, Yang et al. [19] extend Yang’s method [11] to establish characteristics of stroke connections, and improve the estimation accuracy. However, with these methods, the users must manually redraw keyframes with vector lines by tracing over the original character image in advance.

Therefore, we focus on closed areas of character images (i.e., the character parts) with a method to directly estimate stroke correspondence from character images. Note that the manual vector redrawing process can be skipped, hence users can concentrate on designing movements of each stroke.

Constructing closed area correspondences between two raster images has been thoroughly investigated [20]. In the field of reference-based colorization of line drawings, Sato et al. [21] utilize the positional and connection relationships of closed areas in the keyframes to construct their correspondence. Maejima et al. [22] propose a method to (i) estimate the corresponding closed areas in the reference keyframes and (ii)  color target inbetweenings based on (i) estmation. While these approaches are suitable for colorization tasks, they are unsuitable for inbetweening generation because they cannot make vertex correspondences to each pair of corresponding strokes. Consequently, we combine closed area and stroke-based methods that presume to be the optimum method. With this proposed frameworks, we can directly design inbetweenings from two keyframes without vectorization steps.

Figure 2 shows the overview of the proposed system to estimate the stroke correspondence between the two continuous keyframes. Closed areas in the two input keyframes are labeled, and the depth context relationship of the closed areas is estimated, followed by a greedy algorithm to estimate all closed area correspondences between the two keyframes. Finally, users correct the closed area correspondence if they consider it is necessary, and the area correspondence is updated from the corrected results. Stroke correspondence relationship between the two input keyframes is determined from the estimated closed area correspondence.

We first scan images $A$ and $B$ (keyframes) and import them into the PC. The color images are converted to grayscale to perform the labeling process with OpenCV, and then a median filter in kernel size $5$ removes fine noises and repairs broken strokes. Subsequently, closed areas in the keyframes are labeled with threshold binarizing $220$ pixels, which achieved the most stable results in multiple experiments. The labeled closed area of keyframe A is $\{A|(a_{1},a_{2},\cdots,a_{n})\}$, and the closed area of keyframe B is $\{B|(b_{1},b_{2},\cdots,b_{m})\}$, as shown in Figure 3.

Information such as assigning color, area, coordinates of the centroid, and the label and angle of the centroid in the adjacent closed area must be obtained from closed area $a_{i}(i=1,2,\cdots,n)$ and $b_{i}(i=1,2,\cdots,m)$ . At this time, the closed area that touches the greatest proportion of the screen’s outer circumferences is estimated as the background.

We extract the intersections in the input keyframe using OpenCV, and draw a circle with radius $r$ placing the intersections as a center point. The proposed system estimates the depth context of each closed area from the ratio of the closed areas in those circles. Radius $r$ is regarded as the square root of ($2*$(screen size-background label size) $/10000$) so that the area of the circle is $1/100$ the area of the character on the screen.

As a result, the information of the adjacent closed area in the same keyframe and its own depth context relationship are obtained as for the information of the closed areas $a_{i},(i=1,2,\cdots,n)$ and $b_{i}(i=1,2,\cdots,m)$.

Our proposed system focuses on estimating all closed area correspondence as the target problem. This problem can be solved with the estimation of the closed area correspondence near the seed pair, which is considered to be the pair among all combinations as sub-problem. Therefore, we use a greedy algorithm to solve this problem and seek local optimum solutions.

In our algorithm, the score of the closed area near the seed pair is calculated and updated. The first seed pair is the starting point of the greedy algorithm. Then, the pair with the highest score is considered as a new seed pair, and the score is updated iteratively. We repeat the calculation until the scores of all closed areas are updated at least once. Finally, we swap the first and the second keyframes to improve accuracy and update the scores accordingly.

To determine the seed pair, it is necessary to calculate the seed score by quantifying the similarity of the closed areas. The closed area of the labeled keyframe A is $\{A|(a_{1},a_{2},\cdots,a_{n})\}$. The closed area of the keyframel B is $\{B|(b_{1},b_{2},\cdots,b_{m})\}$. The formula for calculating the seed score of the closed area is $a_{i}(i=1,2,\cdots,n)$ ,as follows.

The seed score is calculated for all combinations of $a_{i}$ and $b_{j}$, and the combination with the highest seed score is considered to be the first seed pair $(a_{seed},b_{seed})$. For determining the seed, the seed score of the other keyframe’s closed area is obtained as a tentative score for the information of closed areas $a_{i}(i=1,2,\cdots,n)$ and $b_{j}(j=1,2,\cdots,m)$.

To estimate correspondence near seed pair, the seed pair $(a_{seed},b_{seed})$ updated their scores using the positional relationship and depth context relative to the seed pair.

Let $\{A_{seed}|(a_{1},a_{2},\cdots,a)\}$ be the set of closed area near $a_{seed}$, and let $\{B_{seed}|(b_{1},b_{2},\cdots,j)\}$ be the set of closed area near $b_{seed}$. We calculate the score $R(a_{seed},b_{seed},a_{i},b_{j})$ as the relationship between $A_{seed}$ and $a_{seed}$. The formula for calculating this relationship is given below.

At this step, the paired closed areas $a_{i}$ and $b_{j}$ are determined as a new seed pair, the correspondence in the neighboring seed pair is estimated, and all the closed area scores are updated. This loop performs as many times as the number of the closed areas in the keyframes, and the highest score becomes the first seed pair. Then the score is updated again by swapping keyframes A and B. In order to prevent an infinite loop, a pair that has already been treated as a seed pair will not be retreated if an alternative seed pair can be selected.

Figure 5 shows the work process of the greedy algorithm, that estimates closed area correspondence.

When errors are found in the closed area correspondence estimated by the greedy algorithm, users can manually correct them with our interface. Based on the correction, the system re-calculates the scores and the correspondence. Theses corrections can also improve the accuracy of stroke correspondences.

Boundary lines of the closed areas in keyframes are regarded as strokes. Therefore, we construct stroke correspondences by adopting the estimated closed area correspondences. Figure 6 shows the process of the stroke correspondence estimation. For example, when (1) two closed areas in keyframe A ($a$ and $b$) are separated by one stroke $l$ (green) and (2) two closed areas in keyframe B ($a^{\prime}$ and $b^{\prime}$) are separated by one stroke $l^{\prime}$ (green), we can easily determine that stroke $l$ corresponds to stroke $l^{\prime}$. Therefore, we find correspondences between strokes that separated two or more closed areas.

This method for determining stroke correspondence between two consecutive keyframes suggests the possibility of avoiding the trouble of redrawing the keyframes in vector lines, which is a requirement in previous work. In addition, matching accuracy can be improved by considering not only the corresponding relationships of the position and connection, but also the depth relationships when determining closed area correspondence.

Our main objective is not to automatically construct the correspondence but rather provide a good starting point for manual editing. Hence, we incorporate a manual editing step to modify closed area correspondences in the keyframes. This process is similar to Cacani’s procedure: (1) initializing the correspondence using an inbetweening generator [13] and (2) modifying it manually. Therefore, this experiment adopted as eveluation criteria both the accuracy of closed area correspondences estimation (without user correction), and the number of user corrections until the closed area completely matched.

We conducted system evaluation with 9 graduate students aged 20–40 years working in information systems in Japan (6 males and 3 females) including experienced animators. We verified the burden felt by the users when determining the corresponding closed areas and estimating the corresponding strokes using the proposed method, versus determining the corresponding strokes using Cacani.

Figure 8 shows the estimated results of  $SCD$,  $SC$, and  $S$ methods. This figure also shows  the results of user-corrected correspondences,  the estimated stroke correspondence based on the closed area correspondences, and  the results of automatically generated inbetweenings of $C_{a\sim d}$ sequences based on the proposed estimated stroke correspondence. Note that the colors of the closed areas and strokes are randomly assigned, but the pairs of closed area/strokes are given the same colors. Table 1 and Table 2 show the matching accuracy of closed area correspondences and the average number of user corrections.

The shape-only approach $S$ is lower in the estimation accuracy than other methods ($SCD$ and $SC$), so the characteristics of connection relationship is needed to produce better estimations. On the other hand, from the results of $SCD$ (with the depth relationship estimation) and $SC$ (without the depth relationship estimation), we confirm that the quality of the proposed system depends on input scenes. If input keyframes have a similar depth relationship like $C_{d}$ (see Figure 9d), we can obtain plausible correspondences and reduce the number of user corrections. On the other hand, if it is difficult to determine the depth relationships (see Figure 9a,b,c), $SCD$ has lower accuracy than $SC$.

The average accuracy of stroke correspondence estimation using our methods is 59.513% ($C_{a}$: 69.595%, $C_{b}$: 58.670%, $C_{c}$: 41.304%, and $C_{d}$: 68.481%). A possible reason why the estimation accuracy is insufficient ($>$ 80%) is that the actual relationships between closed areas are changed in the input keyframes and strokes might disappear due to occlusion, so several strokes are identified as “no correspondence,” as shown in Figure 10.

In addition, the proposed system has difficulties automatically generating plausible inbetweening frames (see Figure 8) since the accuracy of the stroke correspondence estimation is insufficient. However, the current qualities are sufficient to automatically generate tight inbetweenings like $C_{a}$, the upper parts of $C_{b}$ & $C_{d}$, and the lower parts of $C_{c}$.

Figure 11 shows the post-experiment questionnaire results. We confirmed that participants who were more accustomed to draw illustrations felt more comfortable designing cartoon images with Cacani, but all participants answered that the proposed method was easier than working with Cacani. Regarding the ease of understanding the operation, they also answered that the proposed method was equivalent or easier to understand compared to Cacani. Note that the average operating time was 7 min 17 sec for Cacani and 1 min 6 sec for the proposed method. Therefore, we can conclude that the proposed method imposed fewer burdens on the participants than Cacani.