情報処理学会研究報告 IPSJ SIG Technical Report Vol.2017-CG-166 No /3/ HUNTEXHUNTER1 NARUTO44 Dr.SLUMP1,,, Jito Hiroki Satoru MORITA The

一般化ハフ 変換によ る コ ミ ッ ク から のキャ ラ ク タ ーの抽出

地頭洋樹 守田 了

山口大学大学院創成科学研究科

755-8611

宇部市常盤台 2-16-1

人間の描いた絵の認識は難し く 、 コ ミ ッ ク から キャ ラ ク タ ーを 抽出する こ と は容易ではな い。 コ ミ ッ ク から 特定の キャ ラ ク タ ーを 抽出する 場合、 検出対象以外を 検出対象と 間違えたり 、 コ マ割り やフ キダシによ っ て絵の一部が隠れ たり する ため、 図形の一部が隠れている 場合でも 図形を 検出でき る ハフ 変換を 用いる 。 し かし 、 さ ら なる 問題点と し てコ ミ ッ ク のキャ ラ ク タ ーは同じ 大き さ 、 向き の顔であっ ても 少し ずつ異なっ て描かれる こ と 、 コ ミ ッ ク の中に抽出 対象以外の存在が多いこ と などが挙げら れる 。 本論文では人間が描いた絵に対応する ために同じ 分類のキャ ラ ク タ ー について縮尺を 合わせて重ね、 重なり の多い点を 有効な点と し て新たに汎用的なテン プレ ート 作成する 。 ま た、 半径 が小さ いキャ ラ ク タ ーは有効投票数が少なく なり 、 選ばれにく いと いう 問題に対し て、 実験結果から 得た近似式を 用 いて有効投票数の最大値を 正規化する こ と で半径に関係なく キャ ラ ク タ ーが抽出でき る よ う に改善する 。 そし て、 コ ミ ッ ク は画面がコ マで区切ら れている 、 セリ フ など絵以外の存在が多い、 基本的に白黒のみで描かれている と いっ た 問題や特徴を 持っ ている 。 こ れら の問題に対処し 、 一般化ハフ 変換によ る 検出率を 向上さ せる ため、 直線検出のハフ 変換によ る コ マの認識を 行い、 コ マごと に一般化ハフ 変換を 適用する 。 さ ら に、 複数のテン プレ ート から 調べた黒の 密度の平均と 分散を 用いて、 投票によ り 挙げら れた候補から よ り キャ ラ ク タ ーに近い点を 絞り 込む。 実際のコ ミ ッ ク

HUNTEXHUNTER1巻、 NARUTO44 巻、 Dr.SLUMP1 巻から キャ ラ ク タ ーを 抽出する 実験を 行い有効性を 示す。

キーワ ード ハフ 変換, 漫画, キャ ラ ク タ ー検出, パタ ーン 認識

Jito Hiroki Satoru MORITA

The Graduate School of Science and Engineering,Yamaguchi University

2-16-1 Tokiwadai, Ube, 755-8611, Japan

It is not easy to detect character from comic because it is difficurt to recognise a picture drawn by human . We use Hough transform to detect figure even if figure’s one copy is hidden because if you detect character from comic, you mistake detecting character or character’s one copy is hidden by other thing. But, we have another problem that characters are drawn defferent little by little even if they are same size and aspect and comics have many things being not character. We propuse the method making new template by plural template. We suggest the method resolving difference of votes for radius by normalization. We improve the detection rate by detecting some frame and density of black because comic have several characteristic such as comic is devided image by frame, drawn by black and white and many expecting characters exist in comic. We show effectiveness by exparment using comic ”HUNTERXHUNTER” volume 1, ”NARUTO” volume 44 and “Dr. SLUMP”,volume 1.

1

はじ めに

こ れま で顔認証や文字認識な ど コ ン ピ ュ ータ に よ り 様々 な識別が行われてき たが、 人間が描いた絵に関する 認識は難し い。 本論文ではコ ミ ッ ク から のキャ ラ ク タ ー の抽出を 目的と し て キャ ラ ク タ ーの認識を 行う 。 コ ミ ッ ク は抽出を 阻害する キャ ラ ク タ ー以外の存在、 コ マ で区切る こ と に よ る キャ ラ ク タ ーの情報の欠落な ど、 多く の問題を 含んでいる 。 本論文ではこ れら の問題 に対処し てコ ミ ッ ク から キャ ラ ク タ ーを 抽出する ために 画像情報の誤り や欠落があっ た場合でも 安定し た検出が 可能な 一般化ハフ 変換を 用いた検出を 行う 。 ハフ 変換は当初、 画像から 直線を 検出する 手法と し て 1962年 Hough に よ っ て 提案さ れ [1]、 そ れ以降様々 な 図形を 検出の対象に拡張さ れてき た。 そし て、 任意の形 状の検出を 目的と し た一般化ハフ 変換が Ballard によ っ て 提案さ れた [2]。 ハフ 変換と テン プレ ート マ ッ チン グ は基本的には等価な 処理を し て いる 考え ら れる [3]。 し かし 、 ハフ 変換は効率的な マ ッ チン グを 実現し て いる 。 コ ミ ッ ク 中のキャ ラ ク タ ーは人間が描く 以上、 例え同 じ よ う な絵であっ ても 完全に一致する こ と はない。 本論 文では複数のテ ン プレ ート から 新たに 汎用的な テ ン プ レ ート を 作成する 。 ま た、 コ ミ ッ ク の中にセリ フ や効果 線など検出対象以外の存在が多い、 コ ミ ッ ク が基本的に 黒白のみで描かれており 、 黒点が密な部分で投票が偏る と いっ た問題が挙げら れる 。 そのため、 直線検出のハフ 変換によ り コ マを 認識し 、 コ マごと の一般化ハフ 変換を 行う 方法と 複数のテンプレ ート から 調べた黒の密度の平 均と 分散によ り 偏っ た投票の候補を ある 程度除外する 処 理によ り 一般化ハフ 変換での検出率を 向上さ せる 。

2

コ ミ ッ ク から のキャ ラ ク タ ー抽出

の特徴

コ ミ ッ ク が通常の顔検出と 異な る 点はコ ミ ッ ク 中の キャ ラ ク タ ーは人間が描いた も のであ る と いう 点であ る 。 ま た、 コ ミ ッ ク には白黒のみで描かれている 、 画面 内がコ マで区切ら れている と いっ た特徴がある 。 コ ミ ッ ク から のキャ ラ ク タ ー抽出は通常の顔検出と 異なる 。 以 下にコ ミ ッ ク の特徴と 通常の顔検出と 異なる 点を 挙げる 。 • (1) コ ミ ッ ク 中のキ ャ ラ ク タ ーは人間が描いて いる た め同じ キャ ラ ク タ ーでも 完全に 一致する こ と が な い。 • (2) セ リ フ、 描き 文字な ど 通常の画像に はな い検出 対象以外の存在が多い。 • (3) 画面内がコ マ で区切ら れて いる た め、 同じ 画面 内にいく つかの場面が描かれて いる • (4) コ ミ ッ ク は基本的に 黒白のみで描かれて いる 。 こ れら の特徴はキャ ラ ク タ ーの検出を 困難にする 要因と なる 。 本論文では画面内がコ マで区切ら れている と いう 特徴と 画面内の黒の密度を 利用する こ と で検出率を 向上 さ せる 。

3

一般化ハフ 変換

3.1

一般化ハフ 変換の方法

テン プレ ート の任意の点 O を 基準と し て その基準点 を 中心に定め、 矩形のテンプレ ート の対角線の半分の大 き さ の半径 r を 持つ円を 考え る 。 基準点 O から テン プ レ ート の任意の点 p ま での距離 r′_{を こ の円の半径で割っ} た比率 R = r′_{/rを 保存する 。 図 1 テン プレ ート の半径} と 基準点から 黒点ま での距離のと り 方を 示し ている 。 保 存し た比率 R を 任意の半径 tmpR にかけ る こ と によ り も と のテン プレ ート を tmpR/r 倍に 縮小ま たは拡大し た場合の任意の点 p の極座標を 求める こ と ができ る 。 こ の方法は円でのハフ 変換を 各点に関し て適宜半径の大き さ を 変え て 行っ て いる のと 同じ である 。 任意の半径を r と し て 、 基準点を cx、 cy、 基準点か ら 画像の任意の点ま での距離を r′_{、 保存し ている 比率を} rate = r′_{/r、 角度を θ と する と こ のと き 画像の点の位} 置は媒介変数で表示する と 以下のよ う にな る 。 x = r · rate · cos(θ) + cx y = r · rate · sin(θ) + cy (1) こ の式を 利用し 、 円でのハフ 変換と 同様に x 座標、 y 座標、 半径、 回転の次元を 持っ た配列に投票を 行う こ と で投票数の比較を 行い画像を 検出する 。

3.2

基本図形に対する 実験

2値化し た複数のオブジェ ク ト の画像を 平面上にラ ン ダムな位置、 向き 、 大き さ で表示し た後、 ハフ 変換プロ グラ ムを 適用し 、 ハフ 変換後に検出さ れたオブジェク ト を 平面上に 表示する 。 10 回試行し た平均検出率を 表 1 に示す。

図 1: テン プレ ート におけ る 基準点と 半径と 黒点ま での 距離

Fig. 1 Length of black point from the reference point in template

表 1: 基本図形の平均検出率

Tab. 1 Average detection rate of basic shape

円 楕円 楕円 (回転) 三角形 87.9% 83.7% 59.5% 75.3%

4

正規化の手法

4.1

半径と 投票数の最大値の関係

こ の一般化ハフ 変換に おいて 任意の点の投票数はそ の点を 基準と し て 投票さ れた 半径で描いたテ ン プレ ー ト の各点と ハフ 変換を 実行し た画像上の黒点と の重な り の数に 等し く な る 。 そ のた め、 あ る 半径に おいて 考 え ら れる 投票数の最大値は、 そ の半径でテ ン プレ ート を 描いた と き の黒点の数に 等し い。 実際のコ ミ ッ ク に 対し て 実験を 行い投票数を 調べる 。 本論文では実験に HUNTERXHUNTER1巻 [4]、 NARUTO44 巻 [5] を 使 用する 。 図 2 は HUNTERXHUNTER に お い て 図 3 は NARUTOに おいて 実際に 用意し た いく つかのテ ン プ レ ート で、 半径ごと に考えら れる 最大の投票数を 調べた 結果を 示し ている 。 こ の結果から 元のテンプレ ート の大 き さ によ っ て差異はある も のの、 グラ フ は半径が大き く な る ほど 投票数の最大値も 大き く な る こ と がわかる 。 こ れら のデータ と 実際にハフ 変換を 行っ た結果から 、 半径が大き く なる ほど投票数も 大き く なり 、 画像上で半 径が大き な キャ ラ ク タ ーほど 検出さ れやすい、 ま た は キャ ラ ク タ ー以外で半径の大き なと き の投票で検出の候 補に挙がっ た座標での検出がなさ れる と いう 結果と なる こ と がわかる 。

4.2

投票数の正規化

半径が大き く な る ほど 投票数が増え る こ と に よ る 差 は妥当な差と は言えないため、 票数の正規化が必要と な る 。 し かし 、 半径の小さ なも のほど投票数の最大値に達 する ために必要な票数が少ないこ と と 、 画像上に黒点が 密集し ていた場合、 容易に投票が行われる こ と から 、 投 票数が最大になる 可能性が高く なる 。 最大の投票数に近 いと いう こ と はその半径においては元のテンプレ ート と 同じ 図形に近いこ と を 示し ている ため、 正規化する こ と で黒点が密集し た位置で検出がさ れやすく なる 可能性が ある 。 そのため、 ある 半径での最大の得票数を B、 ある 半径、 座標で実際に得ら れた票を C, 得票率を A = 100 · C/B と し ていく つかの画像についてハフ 変換を 行い得票率を 調べる 。 こ のと き 調べる 得票率は各半径において票数の 高いも のから 5 個である 。 調べた数値を グラ フ にし た結 果、 半径が小さ いも のほど得票率が大き く 、 半径が大き く なる につれて得票率が徐々 に下がっ ていく 傾向が明ら かにな っ た。 図 4 は調べた得票率のグラ フ である 。 調べた 6 つのデータ はほぼ一様になり 、 グラ フ を 近似 する こ と が可能であった。 グラ フ を 近似し た結果、 半径 x を 横軸と し た関数 f(x) は f(x) = 0.01/25.0 ·exp((−x+ 220)/18.0) + 40と な る 。 図 5 は得票率から 得ら れた近 似式のグラ フ を 示し ている 。 実際の得票率を 近似式から 得た仮想の得票率で割る こ と で概ね一様な値を 得る こ と ができ る ため、 こ の方法で正規化する 。 図 6 は 6 つの 得票率のデータ を 近似式で割っ た値のグラ フ を 示し てい る 。 実際の票数が多ければ正規化し た場合でも 数値が大 き く な る ため、 妥当な 比較が可能にな る 。 0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 0 20 40 60 80 100 120

vote total [number]

radius [pixel] hunterxhunter number 1-8 FN.n1.".txt" FN.n2.".txt" FN.n3.".txt" FN.n4.".txt" FN.n5.".txt" FN.n6.".txt" FN.n7.".txt" FN.n8.".txt" 図 2: 半径に対する 投票数の最大値の推移 (HUNTERX-HUNTER)

Fig. 2 Transition that number of votes for radius(HUNTERXHUNTER)

0 500 1000 1500 2000 2500 0 20 40 60 80 100 120

vote total [number]

radius [pixel] naruto number 1-13 FN.n1.".txt" FN.n2.".txt" FN.n3.".txt" FN.n4.".txt" FN.n5.".txt" FN.n6.".txt" FN.n7.".txt" FN.n8.".txt" FN.n9.".txt" FN.n10.".txt" FN.n11.".txt" FN.n12.".txt" FN.n13.".txt" FN.n2.".txt" 図 3: 半径に対する 投票数の最大値の推移 (NARUTO) Fig. 3 Transition that number of votes for radius(NARUTO) 0 20 40 60 80 100 0 20 40 60 80 100 120

vote total [number]

radius [pixel] pnaruto number 2-7 FN.n2.".txt" FN.n3.".txt" FN.n4.".txt" FN.n5.".txt" FN.n6.".txt" FN.n7.".txt" 図 4: 半径に対する 得票率の推移 Fig. 4 Percentage of votes for radius

0 20 40 60 80 100 0 20 40 60 80 100 120 1.0/(1.0+exp((-x/T100)/T0 1 +x0))+y0 x sigmoid1 e14(x) 図 5: 得票率から 得ら れた近似式のグラ フ Fig. 5 Graph of approximating the percentage of vores 0 0.2 0.4 0.6 0.8 1 1.2 1.4 0 20 40 60 80 100 120

vote total [number]

radius [pixel] hunterxhunter number 1-8 FN.n2.".txt" FN.n3.".txt" FN.n4.".txt" FN.n5.".txt" FN.n6.".txt" FN.n7.".txt" 図 6: 半径の違いに対する 投票数の正規化 Fig. 6 Normalization of votes for the radius of the difference

5

一般化ハフ 変換の拡張

5.1

キャ ラ ク タ ーの抽出に用いる ための一般

化ハフ 変換の拡張の必要性

コ ミ ッ ク に対し てハフ 変換を 行う 上で、 以下のに挙げ る よ う な 問題が存在する • (1) 同じ 大き さ 、 向き の顔であっ て も 少し ずつ異なっ て 描かれる • (2) 検出対象以外の存在が多い ま ず、 描かれたキャ ラ ク タ ーは類似し たも のでも 一つ 一つが少し ずつ違う 形状を し て いる こ と が挙げら れる 。 こ の問題によ り 、 テン プレ ート に類似し たキャ ラ ク タ ー を 検出し よ う と し て も 、 う ま く 投票が行われな い場合 がある 。 そし て、 コ ミ ッ ク の中には検出対象のキャ ラ ク タ ー以外の存在が多いために検出対象以外の座標におい ても 投票数が増え、 誤っ た検出がなさ れる 可能性が高く なる 。 ま た、 コ ミ ッ ク は一般的に白い紙に黒イ ン ク で描 かれ、 黒白のみな ので検出のための手がかり が少な く 、 キャ ラ ク タ ーの検出を 困難にする 要因と な っ て る 。 以下にこ れら の問題を 改善する 手法を 提案する 。

5.2

同じ 大き さ 、 向き の顔も 描かれた顔が異

なる 問題

類似し たキャ ラ ク タ ーでも 描かれたキャ ラ ク タ ーの一 つ一つが少し ずつ異な る 問題を 挙げた が、 こ の問題を 改善する 最も 信頼でき る 方法と し て、 あら かじ め顔の向 き ごと に分類し たテンプレ ート の中で、 同じ 顔の向き の テンプレ ート を 複数重ね、 重なり が多い点を 有効な点と し 、 それ以外を 排除し て作っ た新たなテンプレ ート を 利 用する 方法を 提案する 。 こ の方法で作成さ れたテンンプ レ ート は確率によ り 平均的なテンプレ ート と なっ ている ため、 あら ゆる 類似し たキャ ラ ク タ ーに対応さ せる こ と ができ る 。 図 7 は NARUTO に お いて 、 図 8 は HUNTERX-HUNTERに お いて 、 顔の向き ごと に キャ ラ ク タ ーを 分類し たも のを 示し て いる 。 分類する 顔の向き は正面、 左向き 、 右向き 、 上向き 、 下向き 、 左斜め向き 、 右斜め 向き 、 斜め上向き 、 左斜め上向き 、 右斜め上向き 、 斜 め下向き 、 左斜め下向き 、 右斜め下向き であ る 。 こ こ で、 調査する コ ミ ッ ク に Dr.SLUMP1 巻 [6] を 加え る 。 コ ミ ッ ク 中に存在し ない顔の向き 、 素材の少ない顔の向 き も ある が、 基本的に正面が一番多く 存在し 、 右向き 、 左向き 、 右斜め向き 、 左斜め向き も 比較的多く 存在す

る 。 表 2 は正面、 左向き 、 右向き 、 上向き 、 下向き の、 表 3 は右斜め向き 、 左斜め向き 、 斜め上向き 、 斜め下向 き の、 表 4 は右斜め上向き 、 左斜め上向き 、 右斜め下向 き 、 左斜め下向き のコ ミ ッ ク 中の顔の向き の分布の程度 を 示し て いる 。 図 7: 顔の向き の分類 (NARUTO)

Fig. 7 Classification that orientation of face(NARUTO)

図 8: 顔の向き の分類 (HUNTERXHUNTER) Fig. 8 Classification that orientation of face(HUNTERXHUNTER)

表 2: 顔の向き の分布 (正面他)

Tab. 2 Distribution that orientation of face(front face and other) コ ミ ッ ク 正面 右 左 上 下 HXH 36.3% 19.8% 16.5% 0% 0% NARUTO 43.2% 4.4% 9.1% 0% 0% Dr.SLUMP 14.3% 14.3% 22.7% 0% 0%

5.3

検出対象以外の存在が多い問題

コ ミ ッ ク には検出対象以外の描き 文字やセリ フ、 ま た は、 ベタ や書き 込みによ り 黒点が密な部分が存在し 、 投 表 3: 顔の向き の分布 (右斜他)

Tab. 3 Distribution that orientation of face(right slanting face and other)

コ ミ ッ ク 右斜 左斜 斜上 斜下

HXH 14.3% 13.2% 0% 0%

NARUTO 15.9% 14.8% 2.3% 1.1%

Dr.SLUMP 16.3% 28.1% 0% 0%

表 4: 顔の向き の分布 (右斜上他)

Tab. 4 Distribution that orientation of face(right upward slanting face and other)

コ ミ ッ ク 右斜上 左斜上 右斜下 左斜下 HXH 0% 0% 0% 0% NARUTO 0% 6.8% 0% 1.1% Dr.SLUMP 0.5% 2.0% 1.5% 0% 票の偏り が生じ る 可能性がある 。 そのため各テンプレ ー ト の黒点の割合を 調べ、 そ の割合の平均と 分散を 求め る 。 投票を 比較する 際、 対象のピク セルから 任意の半径 で黒点の密度を 調べ、 平均と 分散から 得た閾値の範囲外 の場合は比較の対象から 取り 除く 。 そし て、 コ ミ ッ ク の 持つページ内がコ マ で区切ら れて いる と いう 特徴を 利 用し 、 コ マを 認識し てコ マごと に投票を 比較する 。 こ の 際、 コ マ の検出に直線を 検出する ハフ 変換を 用いる 。

6

実際のコ ミ ッ ク に対する 実験

コ ミ ッ ク は画像がコ マによ り 区切ら れている ため、 直 線検出のハフ 変換を 用いてコ マを 検出し 、 キャ ラ ク タ ー を 検出し やすく する 。 ま た、 人間が描いた絵は同じ 顔の 向き であっ ても 完全に一致する こ と はないため検出の際 に使用する テンプレ ート は複数のテンプレ ート から 作成 し た平均的なテンプレ ート を 使用する 。 その後一般化ハ フ 変換を 実行し 、 投票数によ り キャ ラ ク タ ーの候補を 絞 り 、 テン プレ ート から 調べたキャ ラ ク タ ーの黒の密度の 平均と 分散を 用いいて絞り 込んだ候補から さ ら に信頼性 の高い候補を 絞り 込む。 実際のコ ミ ッ ク に 対し て 直線検出のハフ 変換を 実行 し 、 全体のコ マの数の内区切る こ と のでき たコ マの数か ら コ マ 枠の検出率を 計算する 。 こ のと き 、 コ ミ ッ ク 10 ページに 対し て コ マ 枠検出のプロ グラ ム を 実行し て コ マ枠の検出率の平均を 求める が、 高い精度は求めていな

い。 表 5 はコ マの検出率を 示し ている 。 以上の方法を ふ ま え 、 図 9 に検出ま での処理の流れを 示す。

表 5: 実際のコ ミ ッ ク のコ マ 枠の検出率 Tab. 5 Detection rate of frame in comic

コ ミ ッ ク 検出率

HXH 53% 

NARUTO 93% 

表 6: キャ ラ ク タ ーの検出率 Tab. 6 Detection rate of charcter

コ ミ ッ ク 検出率 HXH(正面) 86%  NARUTO(正面) 86%  Dr.SLUMP(正面) 92%  HXH(未知画像) 70%  NARUTO(未知画像) 80%  Dr.SLUMP(未知画像) 80%  実際のコ ミ ッ ク 10 ページに対し て コ マ の検出、 平均 と 分散によ る 閾値を 利用し た場合の一般化ハフ 変換での 検出率を 確かめる 。 表 6 は正面顔、 合成テン プレ ート の 作成に使用し なかっ た未知のキャ ラ ク タ ーを 対象と し た 実験の検出率を 示し て いる 。 図 10 は抽出結果の例を 示 し ている 。 こ れら の処理によ る 各コ ミ ッ ク での検出率は 未知画像において 70% から 80% と いう 結果と なっ た。

7

おわり に

本論文では一般化ハフ 変換に よ り コ ミ ッ ク の中から キャ ラ ク タ ーを 抽出する 手法を 提案し た。 今後処理時間 と 認識率を 向上さ せて いく 。

参考文献

[1] Hough, P. V. C. ”Method and maens for recognzing complex patterns”, U. S. Patent No. 3069654, 1962. [2] Ballard, D. H. ”Generalizing the Hough transform to

detect arbitrary shapes”, PR, Vol. 13, No. 2, pp. 111-122, 1981

[3] Stockman, G. C. and Agrawala, A. K. ”Equivalence of Hough Curve Detection to Template Matching”, Com. of ACM, Vol. 20, No. 11, pp. 820-822, 1977

[4] 冨樫 義博, ”HUNTERXHUNTER”, 1巻,集英社, 1998 [5] 岸本 斉史, ”NARUTO”, 44巻,集英社, 2008 [6] 鳥山 明, ”Dr.SLUMP”, 1巻,集英社, 1980 図 9: 処理の流れ Fig. 9 Processing 図 10: 一般化ハフ 変換によ る キャ ラ ク タ ーの抽出結果 Fig. 10 Result of detection