単純な図形の組み合わせによる分類アルゴリズム

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2010-MPS-77 No.1 2010/3/4. 1cJÂNH_go;Khk,`"k4j:` g ? I J. †1,†2. p D * R. †1. a/$h|'1dh|,`NWa,b^j?/Nj!,sF5lF$k%=Ne=*J bNH7FKe<ikMCHo</$FsWl<H^CAs0$5]<HY/?<^7s JSupport Vector Machine(SVMKyrQ$?j!,"2ilk%Ke<ikMCHo</ OkgYErG,=9k3HGM9JD-K,~G-$h|'1K,Q5lF$k %7+ 7$Ke<ikMCHo</O,~D-K~8Fs),O,DgKJkH$&]j,"k% FsWl<H^CAs0O$'1P]Nh|Hp`ÂJFsWl<HKrhG1LGfS 9kj!G$JsP<Wl<HN8z'1 ddA*"k4j:`JGenetic Algorithm( GAK HH_go;?'1 K,Q5lF$k%7+7$FsWl<H^CAs0OhG1 LGHg9k?a$h|N5$:d,r=KhCFh}~V,}C9k]j,"k%SVM O$a/m\5lF$kj!G$2 /i9Ns~A,%djK,7?,òG"k3H,N ilF*j$ih|N'1 JIK,Q5lF$k%7+7$?+F4jXN,QO)W9 k,W,"js)=.,#(=9kdj,"k%3Nh&K>hNe=*Jj!OM9JD -K,~,D=G"k,$s),ON}g$s)=.N#(=,]jHJk%=3G$3s Q/HJs),OH7sWkJs)=.GFQ-Nb$,`"k4j:`N+/r\X7 Fe\7?N,MVNÂ'1a+K:`G"k% MVNÂ'1a+K:Ò$1cJÂNH_go;G#(JÂr'19k!=G" kHM(ilF$k%3l,H Â"kU!YCH>bIG"j$3liN1cJÂO^ A"kU!YCHHFPlF$k %f9O$3NÂ"kU!YCH>bNM(}rH f S*1cJÂ2Nf+i*r5l?ÂNH_go;KhCF#(JÂr'19k! = IHHi($3sTe<?KhkQ?<s,`XN~QrsF9k %sFj!GO$^ A"kU!YCHNAurrHuNICHN[sQ?<sG=7? N × N hGNICHQ ?<sJAlphabet Dot Pattern(ADPKH9k%^?$,`KHQ9k ADP r M DH 7$=N ADP N8gr ADP 2H9k%=7F$1cJÂNH_go;G#(JÂr '19k!=r$P]ÂJ+F4jKNÂH ADP 2NO_s0w%rQ$F+F4j. 9 x R 2. †1. MVNÂ'1a+K:Ò$1cJÂNH_go;G#(JÂr'19k! =G"kHM(ilF$k%3l,H Â"kU!YCH>b IG"k%f9O3N M(}rH fS*1cJÂ2Nf+i*r5l?ÂNH_go;KhCF#(J Âr'19k!= IHHi($3sTe<?KhkQ?<s,`XN~QrsF9 k%sFj!GO$1cJÂH>j7? N × N hGNICHQ?<sJAlphabet Dot Pattern(ADPKH'1P]ÂNO_s0w%rC'LH7F,`9k%\@ 8GO$^:sFj!N79F`KD$FRYk%^?$B3NlcH7FsFj! r^kAU)sHÂN'1K,Q7?kLKD$F(9%3NkL$sFj!GO fSj!hjbb$,`5z(,@il?%. 1). 2). 3). †1. 6). It is thought that human being recognizes a complicated figure by combining simple figure. This is ”figure alphabet hypothesis” and these simple figures are called a figure alphabet. We considered ”the mechanism in which a complicated figure is recognized with the combination of the figure chosen from comparatively simple figure groups”, and applies it to a pattern classification. The proposed method assumes the figure alphabet to be the dot pattern (Alphabet Dot Pattern ADP) of an N N pixel. Because there are many kinds of ADP, ADP group is optimized by the genetic algorithm (GA). And, the hamming distance of an input figure and an ADP group is calculated, and classifies a figure. In this research, the proposed method was applied to recognition of a multifont figure as an example of an experiment, and the validity of the proposed method was verified. Consequently, the result of the proposed method was able to obtain the correct answer rate higher than the result of a comparative experiment. This paper describes the way of thinking and experiment result of the proposed method.. (. 4). 5). Classification Algorithm by the Combination of a Simple Figure Ryoji Ohira,†1,†2 Noriko Yata and Tomoharu Nagao†1. O8aK. 1.. 7). _. #Mq)gXgX!D-psX\ Graduate School of Environment and Information Sciences, Yokohama National University †2 -E$)Ht0qR †1. Oki Electric Industry Co., Ltd. 1. ⓒ2010 Information Processing Society of Japan.

(2) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2010-MPS-77 No.1 2010/3/4. r,`9k!=H9k%33G$M(ilk ADP 2NoÒ 2 × M DHDgG"j$ ,`P]K,7? ADP rj0G*r9k3HOsoK$qG"k%=3G$ADP 2r+ 0*K=[9k?aK$GA rQ$k% \@8GO$1cJÂNH_go;GP]Âr,`9k"k4j:`H GA rQ$ F ADP 2r+0*K=[G-k79F`KD$FRYk%^?$p\*J!$B3Nlc H7F$sFj!r^kAU)sHÂN'1djK,Q9k% N ×N. 2.. ,`"k4j:`. \79F`N5W ^ 1 KsFj!N79F`=.He=C'LNaa}r(9%\79F`^ 1(a) O$GA Nh}tHC'jPtH,`tG=.5lk%^:$+F4j4HK#tgNh|rQU 7$X,h|H$Nh|K,1k%3liNh|NhGtO K × K hGG ADP NhGt N0t\H9k%ADP O$rHuNICHN[sQ?<sG=7? N × N hGNICH Q?<sG"k% 2.2 79F`N0n 2.2.1 X,U'<: X,U'<:GO$X,h|rQ$F GA G ADP rG,=7$X,h|H ADP NO_ s0w%+ie=C'Lraak%3N GA GG,=9k}!O 2.3 GRYk% ^ 1(b) Ke=C'LNaa}r(9%e=C'LO$ADP rHg7FX,h|HNO _s0w%r0 (1) Gaa$3NO_s0w%rX,h|NgtG?Q7?bNG"k%W ;}!r0 (2) K(9%Je$\@8GOO_s0w%rmhGtG|;7F5,=7?b NrO_s0w%HhV% 2.1. Hj =. K X K X 1 d(P (x, y), A(j, x, y)) K ×K. ^. R(i, j) =. d(n1 , n2 ) =. 0. if (n1 = n2 ). 1. otherwise. Ci 1 X H(i, j, k) Ci. (2). k=1. 33G$R(i, j) O i V\N+F4jN j V\N ADP Ne=C'L$C O i V\N+F4 jNX,h|Ngt$H(i, j, k) O i V\N+F4jN k V\NX,h|H j V\N ADP HNO_s0w%G"k% 2.2.2 ,Ù'<: ,Ù'<:GO$$Nh|,=l>lIN+F4jK09k+r=j9k%,`Nh} O$ADP rHg7F$Nh|HNO_s0w%rW;7$=NO_s0w%H+F4j4 HNe=C'LNf</jCIw%r0 (3) GW;9k%3N~$f</jCIw%,G. HJC?+F4jr$Nh|N,`kLH9k% i. (1). x=1 y=1. (. 79F`=.. 1 Fig. 1 System configuration.. v u M uX (R(i, j) − Hj )2 Ei =t. 33G$P (x, y) OX,h|$H OX,h|H j V\N ADP NO_s0w%G"k%. (3). j=1. j. 33G$R(i, j) O i V\N+F4jN j V\N ADP Ne=C'L$H O$Nh|H j V 2. j. ⓒ2010 Information Processing Society of Japan.

(3) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2010-MPS-77 No.1 2010/3/4. ^. dAR?H==?. 2 Fig. 2 Genotype and phenotype. %. \N ADP HNO_s0w%$E O i V\N+F4jK*1ke=C'LHO_s0w% Nf</jCIw%JE f 0KG"k% 2.3 GA rQ$? ADP 2N+0=[ ADP O N × N hGNrHuNICHN[sQ?<sG=5l$=Nmt M O 2 × M DG"k%c(P$N =5$M =10 NH-$M Os 3.4 × 10 DHJj$= NtODgG"k%=3G$3N M Nf+i,`P]NÂK,7? ADP 2r=[ 9k?aK GA rQ$k% 2.3.1 dAR?H==? ^ 2 K N =3$M =4 NH-NdAR?H==?Ncr(9%\&fGQ$kdAR?O$ N × N × M N 2 !5SCHsG=7$dAR,F 1 GG"kH-KP~9k==?NIC HOuHJj$F 0 GNH-OrHJk%\@8GO$3N N H M O=wB3KhCFh j7$N =5$M =10 H9k% 2.3.2 r5HM3Q[ 2 !5NdAR?Nr5KO$2 !5VmC/r5JI,M(ilk,$\@8GOb> r9@ C He?r9@ C ris@`Kha$b>r5He?r5r 1 $e4HKr_K T&$QA1@r5rQ$k%^ 3 K$3N 2 $e,Nr5KhCF88kR9N==? N8.cr(9% M3Q[O$M3Q[(NdgG 1 hGNdAR,?>9k%^ 4 O\&fGQ$k= =?NM3Q[NMRr(7?bNG$dAR a OM3Q[0HM3Q[eGr+iuK ?>7F$k% 2.3.3 ,~YXt \&fGO$G,J ADP 2r=[9k?aK$GA N,~YH7F!NrorM89k% (a) +F4jNe=C'LVNw% (b) +F4jbNO_s0w%N,6 (c) ADP N?Mi. i. ^. max. r5Nc. 3 Fig. 3 Example of the crossover. max. N ×N. 8. %. max. v. ^. M3Q[Nc. 4 Fig. 4 Example of the mutation. %. X,h|N,`-= (e) ADP N1c0 (4) K(9,~YXtO0 (5) +i0 (9) K(95DNXt$F $F $F $F $F N ~ABH7F=5lk% (d). H. 1. 2. 3. f itness = α1 F1 + α2 F2 + α3 F3 + α4 F4 + α5 F5. 4. 5. (4). 33G$α $α ...α OjtG"k%\@8GO=wB3NkL+i$X,h|N,`-= H ADP N1c-KE-rV$F$α = 1$α = 1$α = 1$α = 1.5$α = 2 H9k% (a) +F4jNe=C'LVNw% +F4j4HNe=C'L,%lF$k[IH)-,b/$$Nh|XNmP9H-r |T9k3H,G-k%=3G$+F4j4HNe=C'L,%lF$k3Hr>A9 k?aK$0 (5) G(5lk F r,~YKC(k% 1. 2. 5. 1. 2. 3. 4. 5. 1. 3. ⓒ2010 Information Processing Society of Japan.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. V −1. F1 =. V X X. Vol.2010-MPS-77 No.1 2010/3/4. i1 =1 i2 =i1 +1. v u M uX ×t (R(i1 , j) − R(i2 , j))2. uhGN8^jOÂNC'rhjh/=9%=3G$uhG,8^C? ADP r>A 9k?aK$0 (9) G(5lk F r,~YKC(k%. (5). 5. j=1. 33G$V O+F4jtG"k% (b) +F4jbNO_s0w%N,6 +F4jK09kX,h|NO_s0w%N,6,.5$HC'uVeG=N+F4 j,8^CF$kH$($=N+F4jNC'rhjh/=7F$k3HKJk%=3 G$0 (6) G(5lk F r,~YKC(k%. F5 =. Ci V M 1 XX 1 X × (H(i, j, k) − R(i, j))2 V Ci i=1 j=1. 3.. B3D-N_j 3.1.1 B3KQ$?h| \@8GO$B3NlcH7F$sFj!r^kAU)sHÂN,`K,Q7$sFj !N-z-r!Z9k%= 1 KB3GQ$?h|N_jr(9% ^kAU)sHQzh| N+F4jO!K(9J1K$^kAU)sHtzh|N+F4jO!K(9J2KG"k% ( 1 ) A$B$C$D$E ( 2 ) 0$1$2$3$4$5$6$7$8$9 B3KQ$?h|O$Microsoft office rQ$FF+F4jKP7F 88 o`NU)sH+ i 88 gNh|rn.7?%^ 5 K^kAU)sHÂN5sWkh|r(9%n.7?h | 88 g+iis@`K*s@ 25 grX,h|H7$=N>Nh|r$Nh|H9k%^ kAU)sHQzOX,h|, 125 gG$Nh|, 315 g$^kAU)sHtzOX,h |, 250 g$$Nh|, 650 gG"k% 3.1.2 B3KQ$?Qia<? ADP 2r+0*K=[9k?aKQ$k GA NQia<?r= 2 K(9%^?$\@8 GO=wB3NkL+i ADP NhGtr 5 × 5 hG$Dtr 10 DHha?% 3.2 fSB3N_j sFj!N-z-r!Z9k?aK$!K(9fSB3rT&% ( 1 ) fSB3 1. (6). k=1. 3. M −1. X. M X. j1 =1 j2 =j1 +1. g1 (n1 , n2 ) =. (. N X N X 1 ×g1 (A(j1 , x, y), A(j2 , x, y)) N ×N. (7). x=1 y=1. 1. if (n1 = n2 ). 0. otherwise. X,h|N,`-= X,h|N,`-=,b$ A r>A9k?aK$0 (8) G(5lk F r,~YKC (k%. (d). 4. F4 =. Ci V 1 X 1 X g1 (i, g2 (Sk )) V Ci i=1. =. B3KQ$?h|N_j. 1 Table 1 Setting of experiment images. (8). k=1. Gradation of the images Font Type of characters Pixel of images. 33G$g O k V\NX,h|,,`5l?kL S N+F4jVfG"k% (e)ADP N1c2. ^kAU)sHÂrQ$?B3. 3.1. 33G$H(i, j, k) O i V\N+F4jN k V\NX,h|H j V\N ADP HNO_ s0w%G"k% (c)ADP N?MADP 2K`w7? ADP ,"kH$;P5lkO_s0w%ba$MHJj$C'L N!5t,:/7F7^&?a$?M-r>A7?$%=3G$0 (7) G(5lk F r,~YKC(k% F3 =. (9). j=1 x=1 y=1. 2. F2 =. M X N X N X 1 ×g1 (A(j, x, y), A(j, x ± 1, y ± 1)) M ×N ×N. k. 4. %. Binary images Multifont Alphabet Number 75 × 75. $. ⓒ2010 Information Processing Society of Japan.

(5) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2010-MPS-77 No.1 2010/3/4. ^ 6 8zh|rbGk=7?ICHQ?<s'‘A’,‘B’,‘C’,‘D’,‘E’ Fig. 6 Modeled dot patterns-‘A’,‘B’,‘C’,‘D’ and ‘E’% ^. ^kAU)sHÂ. 5 Fig. 5 Sample of multifont images. (2). % ^ 7 8zh|rbGk=7?ICHQ?<s'tz Fig. 7 Modeled dot patterns of number%. fSB3 1 O$M,h|D<krQ$F8zh|rbGjs07?ICHQ?<s JModeled dot pattern(MDPKrQ$?B3G"k%^ 6$^ 7 KB3GQ$? MDP 2r(9%3NB3GO$sFj!N ADP 2r MDP 2KV-9(F$Nh |K,Q5;FT&% fSB3 2 fSB3 2 O$FsWl<H^CAs0rQ$?B3G"k%X,h|H$Nh|N hGtO 20 × 20 hGH9k%^?FsWl<HO$X,h|NF+F4jbN?Q MKGba$h|r*V%\@8G*s@FsWl<Hr^ 8 K(9%=7F$Fs Wl<HH$Nh|N9,r0 (10) Gaak% B=. 20 X 20 X 1 | T (i, j) − P (i, j) | 20 × 20. ^. ^kAU)sHÂNB3kL ^ 9$^ 10 O,`P]N^kAU)sHÂNX,h|rQ$F GA GG,=5l? ADP 2G"k%3N^ 9$^ 10 N ADP 2rQ$?sFj!r$,`P]N^kAU)s HÂK,Q7?kL,$= 3$= 4 =G"k%3NkL$sFj!OfSB3hjb$5 z(r(7?%3N3H+i$sFj!,QzdtzN^kAU)sHÂN'1djKP 7F-zG"kH$(k% !K$GA KhCFG,=5l? ADP 2NEv-r!Z9k?aNB3H7F$^ 9 N ADP 2rQ$?sFj!r,`P]0N^kAU)sHÂK,Q7?%3NkLr= 5 K(9%3NkL$,`P]NÂN5z(,,`P]0NÂN5z(KfYFb$5z (r(7?%3N3H+i$,`P]K,7? ADP 2, GA KhCF+0*K=[G-? H$(k% 3.4 M ! sFj!r^kAU)sHÂK,Q7?kL$fSB3hjbb$5z(,@il?% 3NkLKhCF$GA GG,=5l? ADP 2rbA$ADP HNO_s0w%rC'L H7FÂr,`9kH$&77$h|,`79F`,-zG"k3H,o+C?%^?$ = 5 K(9kL+i$,`P]NÂN5z(,,`P]0NÂN5z(KfYFb$5. (10). 33G$i$j OhGNB8$T (i, j) OFsWl<H$P (i, j) O$Nh|$B OFsWl< HH$Nh|N9,G"j$B ,.5$[IFsWl<HH$Nh|N`wY,b$3H r(9% =. NQia<?. Change of generation Population size Generation number Selection type Crossover rate Mutation rate Crossover type. %. %. 3.3. i=1 j=1. 2 GA Table 2 Parameter for GA. FsWl<H^CAs0NFsWl<H. 8 Fig. 8 Standard images of the template matching. K. SGA(Simple Genetic Algorithm 100 15000 roulette + elite preservation 0.8 0.03 Deformation one point crossover. 5. ⓒ2010 Information Processing Society of Japan.

(6) 情報処理学会研究報告 IPSJ SIG Technical Report. ^9. Vol.2010-MPS-77 No.1 2010/3/4. GG,=5l?^kAU)sHQzh|. N. Ke\7$Â"kU!YCH>bNM(}rHfS*1cJÂ2Nf+i*r5l?^ ANH_go;KhCF#(JÂr'19k!=IHHi($3sTe<?KhkQ?< s,`XN~QrsF7?%^?$B3NlcH7F$sFj!r^kAU)sHÂN' 1djK,Q7$fSB3HN-=fSrTC?%3NkL$sFj!GOfSB3hjb $5z(,@il$sFj!N-z-rN'G-?%^?$GA KhCF+0*K=[7? ADP 2r,`P]0NÂK,Q9kB3rT$$,`P]NÂK,7? ADP 2,M @G-?3HrN'7?%3liNkL+i$1cJÂNH_go;GP]Âr,`G -k77$M(}Nh|,`79F`rB=G-?H$(k% #eO$\@8G=[7?h|,`79F`r,4h|N,`B3H7Fih|JIN, `K,Q9k%9K$'psrM87?h|,`79F`N!$rT$$+i<h|N,` K,Q9k=jG"k%. 2 %. GA ‘A’,‘B’,‘C’,‘D’,‘E’ ADP Fig. 9 ADP group of the multifont alphabets ‘A’,‘B’,‘C’,‘D’ and ‘E’. ^ 10. GG,=5l?^kAU)sHtzh|N. GA ADP Fig. 10 ADP group of the multifont number. %. 2. z(,@il$GA KhCFG,=5l? ADP 2,+0*K=[G-?3H,o+C?% Je$sFj!HfSB3NkL+i$1cJÂNH_go;GP]Âr,`G-k 77$M(}Nh|,`79F`rB=G-?%9K$ADP 2NEv-r!Z9kB3k L+i$\79FÒ GA KhCF ADP 2r+0*K=[G-k79F`G"k3Hr (7?% 4.. 2 M 8 %. <?4K[+'Ke<ikMCHo</rQ$?V>h|'1$ERpsL.Xq; Q&fsp$NLP, s~Adj$ Vol.97, No.53, pp.69–76 (1997). 2) b65R[+'?MFsWl<H^CAs0rQ$?JsP<Wl<H'1!](;^ )U#k?H8z[V,'NzL*xQ]$ERpsL.Xq@8o! D-II$ Vol.J87D-II, No.7, pp.1451–1461 (2004). 3) Bo!T, 9xR2 : 8'MF#C/"k4j:`, <82 (1993). 4) eD;W[+'dA*"k4j:`rQ$?FsWl<H^CAs0Khk79U) sHN+01L$|\!JX;QXqo$ Vol.11, No.1, pp.77–93 (2006). 5) mn(jJ$Yf ;$nP mM'ih|KhkModj;Q$ERpsL.Xq;Q &fsp$PRMU, Q?<s'1&aG#"}r$ Vol.103, No.452, pp.19–24 (2003). 6) Fujita, I., Tanaka, K., Ito, M., Cheng, K'Columns for visual features of objects in monkey inferotemporal cortex$Nature, 360, pp.343–346 (1992). 7) Kenji Saiki, Ryoji Ohira, Tomoharu Nagao'Finding optimized object alphabet using GA$IWAIT2008 (2008).. 1). *ojK. \@8GO$MV,Âr'19ka+K:`HM(ilF$kÂ"kU!YCH>b = 3 ^kAU)sHQzh| ‘A’,‘B’,‘C’,‘D’,‘E’ N5z( Table 3 Correct answer rate -‘A’,‘B’,‘C’,‘D’ and ‘E’% Proposed method Comparative experiment1 Comparative experiment2. =. Learning images 97.6% 76.0% 88.0%. Unknown images 96.2% 84.8% 88.9%. ^kAU)sHtzh|N5z(. 4 Table 4 Correct answer rate of multifont number images Proposed method Comparative experiment1 Comparative experiment2. Learning images 98.4% 85.6% 88.8%. %. =. ^ N. 2rQ$?>AB3. 5 9 ADP Table 5 Evaluation experiment of ADP group. Unknown images 95.9% 84.4% 89.5%. Alphabet images‘A’,‘B’,‘C’,‘D’,‘E’ Number images. 6. !. Learning images 97.6% 91.2%. %. Unknown images 96.2% 93.7%. ⓒ2010 Information Processing Society of Japan.

(7)