2-D Cartoon Character Detection based on Scalable-Shape Context and Hough Voting

INTRODUCTION

---

Cartoon is well-liked by both children and adults for its comic characters and the funny drawing style. In history, lots of classic cartoon characters had been produced by artists and shown to readers which formed a big industry. The economic value of cartoon attracts both the cartoon fans and pirate, who may get and upload the cartoon media copy to sharing website to make a profit. Some pirates sometimes even re-edit the cartoon for advertisement, create new cartoon product based on the famous cartoon characters and publish as their own works.

A method to solve the pirate problem of cartoon is to block pirate’s way to the sharing website, so that the sharing website can be protected from legal liability for spreading pirate cartoons. Therefore, it is necessary for the sharing web sit to detect and then reject the cartoons with copyright statement.

The chief value of cartoons is the characters in them and the characters are also the most frequently pirated content. To the best of our knowledge, there is no previous proper method for detection the characters in the 2-D cartoon image. The central idea of the general object detection problem lies in finding matches between object features and the image features (Mikolajczyk and Schmid, 2005). Global features usually contain too much noise because the character usually localize in part of the whole picture (Szeliski, 2010; Deselaers et al., 2008). Plenty of local patch based feature have been proposed and successfully applied in object detection, such as Scale-Invariant Feature Transform (SIFT) (Lowe, 1999), Speeded Up Robust Features (SURF) (Bay et al., 2008), Maximally Stable Extremal Regions (MSER) (Matas et al., 2002) and scale and affine invariant interest point (Mikolajczyk and Schmid, 2004). These features are, to some extent, invariant to illumination, projective transformations and other common object variations. Most of the features work well in the natural images, producing abundant features with scale or rotation invariance; however, they are inadequate for the cartoon character detection. Compared to the natural image, 2D cartoon have simpler, more artificial contents and is composed of regions with simple coloring and explicit curves to separate different regions, as shown in Fig. 1. There is little texture information to localize the key points and descript them using the gradient based local feature, especially in the flash cartoon. The classic local features mentioned above will not perform well for the cartoon images.

In the cartoon image, curve is the essential element to present the content information, such as shape, motion and expression. It provides human with most of the information about the cartoon and can be extracted fast and accurately (Zhang et al., 2009, 2013). Modeling the curve information as the feature coincides with the human instinct.

Fig. 1:	Classic 2D cartoon image from a cartoon TV series (the main content is delivered by explicit curve and the large uniform regions)

Shape Context (SC), proposed by Belongie et al. (2002), is one of the most widely used features for curvilinear structure description. SC allows for measuring shape similarity between curvilinear structures and is used in digit recognition, silhouette similarity-based retrieval and 3D object recognition.

The basic idea of SC is to model the distribution of other curve pixels relative to the selected pixel. Diagram of log-polar histogram bins is used in computing the shape context, 12 equal divided bins for the relative angle and five exponential increasing radiuses for the relative distance as shown in the Fig. 2c. The amount of pixels falling into each bin forms the SC descriptor of the reference pixel. Taking the diagram into a 2-D axis with θ as the horizontal axis and log(r) as vertical axis, the feature extracted in Fig. 2a at the red square and b at the triangle can be shown as Fig. 2d and e. For the shape detection, SC provides a compact, rotation invariant, yet highly discriminating descriptor but it is very sensitive to the changing scale. If the radius of the diagram changes, the descriptor will change, as shown in the Fig. 2f.

Thought extracted from different handwriting, d-e are quite similar to each other. Due to the changing in scale, d-f are quite different, thought extracted from the same location on the same handwriting.

Fig. 2(a-f):

SC feature extraction and the sensitivity to the scale changing, (a) Outline of a handwriting of digit 9 by some person, (b) Outline of handwriting of digit 9 by another person, (c) Bin partition using the diagram of log-polar histogram bins, (d) Feature extracted on the red square in (a) at scale σt, (e) The feature extracted on the red triangle in (b) at scale σt and (f) The feature extracted on the red square in (a) at scale 2σt

In this study, we propose a new local invariant features, namely Scalable-Shape Context (SSC), based on the Harris-Laplace corner detector (Mikolajczyk and Schmid, 2004) and the Shape Context descriptor for the cartoon character detection. To solve the scale sensitive problem of Shape Context, we first use the Harris-Laplace corner detector to localize the key points and corresponding scale in the cartoon image. Then, the scale of each key point is used as a reference scale by Shape Context to describe the curvilinear structure around the key points, so that the feature can be extracted at a consistent scale among images. Given the features, we formulate the matching between the cartoon character and the testing cartoon image as a weighted bigraph matching problem and then find the optimal matching. Then a Hough voting scheme is introduced to localize the character. The experimental results show the effectiveness of the proposed SSC-based detection method.

SCALABLE SHAPE CONTEXT (SSC) BASED OBJECT DETECTION

The cartoon character detection method is shown in Fig. 3.

We first extracted the SSC features and match the features extracted from the cartoon character and the testing image. Then the Hough voting rules are learned from the cartoon image. Finally, the matched features in the testing image vote for the center and the scale of the character based on the voting rule.

Scale shape context
Multi-scale harris corner detection: Multi-scale Harris corners are detected by the scale-adapted Harris function and selected in scale-space by the Laplacian-of-Gaussian operator, also called Harris-Laplace corner. It shows high repeatability and localization accuracy inherited from the Harris detector. The Harris detector which is one of the most reliable interest point detectors, is based on the second moment matrix (the auto-correlation matrix). To detect corners in multi-scale, this matrix must be adapted to scale changes to make it independent of the image resolution. The scale-adapted second moment matrix can be defined by Eq. 1 (Mikolajczyk and Schmid, 2004):

(1)

With:

(2)

(3)

where, σ_I is the smooth filter scale and the σ_D is the differentiation scale. I(x) is the given image, x = (x, y), L_x, L_y is the derivative computed in the x and y direction at scale σ_D, respectively. The Matrix describes the gradient distribution in a local neighborhood of a point. The Harris corner of certain scale can be localized by finding the local maxima in the Harris measure (Harris and Stephens, 1988), as shown in Eq. 4:

(4)

Then, we verify for each of the scales if the local maxima of certain scale is also the maxima in the scale-space. Harris corners of different scale may shift more or less while the scale changing, so a search around the maxima of R is needed. This search is time consuming.

Fig. 3:	Scalable Shape Context-based cartoon character detection

There is also a fast approximate solution based on the observation that the scale Harris corner arise together with the local maxima of the Laplacian-of-Gaussian over scale. The local maxima of the Laplacian-of-Gaussian are computed by Eq. 5 to verify the scale of the corner:

(5)

The cartoon corner detected using Harris-Laplace corner detector can be shown in the Fig. 4b. The center of the red circle is the location of the Harris-Laplace corner and the radius r is the scale at which Harris measure R reaches its maxima over scales.

Descript using the shape context: Once given the key point location and the corresponding scale, we use shape context to describe the local feature. We extract all the curves, including edge and decoration lines in the cartoon image, using the method by Zhang et al. (2013). Afterwards, we use the SC to describe the key points.

There are several differences between the Shape Context and our SSC. Firstly, our method uses the Harris Corner, rather than the curve pixel, as the reference point which is more stable and much less than the curve pixel. Secondly, we use the Harris Corner scale as reference scale, rather than the size of the image as in Shape Context.

Consider a reference point (a Harris corner) as p_i, iε(1, 2…m) and the curve pixels as pixel₁, lε(1, 2…M). The Harris corner’s scale is s, we use bins that are uniform in log-polar² space, with 12 bins for the angular direction and 5 bins for the polar direction (Fig. 2c), with radius sx2^t, tε(0, 1…4), as shown in Fig. 5b.

Fig. 4(a-b):	(a) Cartoon image for testing and (b) Red circles are the Harris corners detected by the Harris-Laplace corner detector on the cartoon image

Fig. 5(a-b):	(a) Curve and the corner (centered at red circle) extracted from Fig. 1 and (b) SSC diagram locating at one of the corners. The radius of the inner circle diagram is equal to the corner’s scale and radius of the ex-circle is 24 times of the scale

s is relative stable over images, so that shape context can be computed in a stable scale to be invariant to the scale changing from image to image. We compute the histogram h_i as follows:

(6)

Let C_ij = C (p_i, q_j) denote the matching cost between two feature points. We use the χ² test statistic to compute C^ij, as shown in Eq. 7:

(7)

where, h_i(k) and h_j(k) denote the K-bin normalized histogram at p_i and q_j, respectively. χ² test is a measure for the independence. If the features of p_i and q_j are different, C_ij will be relatively large and if the features of p_i and q_j are the same, C_ij will reach a minimum of 0.

Bipartite graph matching: Given the set of costs C_ij, between all pairs of feature points p_i from the cartoon character and q_j from the testing image, we want to find an optimal matching that minimizes the cost:

(8)

where, π is a permutation of j. This is a weighted bipartite matching problem which can be solved efficiently by Jonker and Volgenant (1987). While matching, parts of the feature points may not be matched because outliers or occupation, so dummy key points are added, for both the data balance and the anchoring the mismatched feature point. The match cost between dummy and the feature points are set to a low value, so that the outliers are tend to match with the dummy.

Hough voting for character detection: Here, we present the cartoon character model as a set of scalable shape context feature points. The matching between the character model and the testing image induces a translation and scale transformation, we let each match pair vote for the presence of a cartoon character at a certain image location and scale (Leibe et al., 2004; Maji and Malik, 2009). Let _if denote the features at location l_i and S(O, x) denotes score that object O arise at location x:

(9)

While the _if and I_i is independent to each other and Eq. 9 is equal to Eq. 10:

(10)

C_i is the match feature in the model. Because the matching has no relation with the position, so p(C_i|f_j, l_j) = p(C_i|f_j). So the Eq. 10 can be written as Eq. 11:

(11)

where, p(C_i|f) is the feature matching probability, between the feature f from the testing image and C_i from the cartoon character model. p(x|O, C_i, I_j) is the probability of the location if C_i is matched to a feature in location I_j, can be written as a. p(O|C_i, I_j) is the probability that C_i for the existence of the object. In this study, we define p(C_i|f) as Eq. 12:

(12)

where, Z is the constant for p(C_i|f) to make the integral equal to 1, t and γ are positive real number. Then Eq. 11 can be written as Eq. 13:

(13)

where, s_r is the relative scale between testing image and the model and is computed by the relative ration of the matched features, P is the relative positive from center of the model to the feature C_i.

Local maxima in the voting space, S(O, x), give the center location of the object and the relative scale defines the corresponding window’s size. The score is computed by the following equation:

(14)

where, M is the number of the matched feature points which fall into the location window; m is the number of the model feature points. S_maxima stands for the local maxima of S(O, x). Herein, α = 0.9. The more feature points vote for the maximum of the S(O, x), the bigger are the two terms of Eq. 14.

EXPERIMENTAL RESULTS

We extract the scaling shape context feature from the cartoon image and find the optimal matching between the cartoon character model and the testing images. A Hough-style voting scheme is used to locate the cartoon character in the testing image. The simulation is carried on a cartoon images database, containing three famous cartoon characters, such as doraemon, xiyangyang, snoopy etc., collected from cartoon TV series and internet. Each class of the character contains at least 40 images with different positions, angles or different backgrounds. The dataset also includes one character image as model for each class of character. During the detection, we use all images in the database as test set for each class which make for a large negative test set. It allows getting a reliable value for the incidence of false-positives generated by the detection algorithm. We counts a detection to be correct if the overlap of the detected and ground-truth bounding box is greater than 50%, according to the PASCAL criterion. Figure 6 shows the feature matching between the given model and one of the test image, as well as the Hough voting space generated in the voting. Figure 7 shows some of the detection result and the corresponding Hough space. It is clear that the maximum value in the Hough space indicate the existence of a character.

The results in Fig. 8 shows that our method gains a much higher detection rate than the SIFT and SC.

Fig. 6(a-c):	(a) Matches between the model of Xiyangyang and the testing image, (b) Red points in are the feature location, the blue line connect matching points and (c) Hough voting space and the red square is the detected object window

Fig. 7(a-b):	Result of detection the cartoon character Xiyangyang (a) Original images with the red square marking the detection results and (b) Hough voting space of each image in (a)

Fig. 8(a-c):	Detection rate (DR) vs. False Positive per Image (FPPI) curve for evaluating the cartoon character detection (a) Detection rate vs. False positive for xiyangyang, (b) Detection rate vs. False positive for doraemon and (c) Detection rate vs. False positive for snoopy

Table 1:	Comparison of detection rate over methods

SIFT get a low detection rate is that the cartoon image is lack of texture and number of SIFT feature is much less than that in the natural images. The mismatching between different cartoon images is very serious. SC feature is sensitive to the scale changing, so that it performs well if the object scale is similar to the model but perform much worse if the scale is not agree.

Table 1 shows the numerical differences between features.