TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol.12, No.7, July 201 4, pp . 5522 ~ 55 2 8   DOI: 10.115 9 1 /telkomni ka. v 12i7.517 0          5522     Re cei v ed  No vem ber 1 9 , 2013; Re vi sed  Jan uar y 6, 20 14; Accepted  February 2, 2 014   Mathematical Programming Model on Joint and  Recovery of Paper Scrap      Jiang Zhixia * 1 , Yang Jianjun 2 , Luo Haifeng 3 , We n Zhengqian g 1 Departme n t of Appli ed Math e m atics, School  of  Science, Ch angc hu n Univ e r sit y  of Scie nce  and  T e chnolog y, C han gch un, Jili n ,  13002 2, Chi n 2- 4 School of Co mputer Scie nc e and T e chno l o g y , Cha ngc hu n Univ ersit y   of Scienc e an d T e chn o lo g y Cha ngch un, Jil i n, 130 02 2, Chi n a   *Corres p o ndi n g  author, e-ma i l : zhixia _ji ang @12 6 .com       A b st r a ct   T he jo int  and  r e covery  of p a p e r scrap  w a s a n  o p timal  matc hin g  iss ue. T h e a u to matic r e storation   techno lo gy for  the  broke n   d o cu me nt w a desi gne acco rdin g to  differ ent cuttin g  w a ys of the  pa p e shred der. As the frag me nt d a ta w a s an o ne-si de pr i n t file, a no nli near  progra mming  mo del w i th n o   constrai nt con d itio ns w a s establis he d for th e straig ht -cutting br oken  pa p e r scrap fro m   a giv en pr int fil e  of   the sa me  pag e ,  and  the  no nl i near  pro g ra mmi n g  mod e w i t h  restra int pr o g ra mmin mod e l w a estab lis hed   for the broke n   scrap w i th straight cut and cr o ss cut. F o r the  pap er scrap d a t a from a o ne- pag e pri n t file i n   Engl ish pri n ted  on both si des, the joi n t w a accomplis he d b y  the ant colo n y  algor ith m   Ke y w ords :  jo i n t, the least sq uare  meth od, a n t colony a l g o ri thm    Copy right  ©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1 . Introducti on  Curre n tly, a lot of re sea r ches  on the  a u toma tic  re storation te ch n o logy for the  bro k en   document ha ve been don e in most of the develop ed cou n trie s internation a l l y. However,  in   Chin a, the rese arch on t h is a r ea  started t oo late, and few  re search a c com p lishm ents  were   repo rted.  The  joint of  the  b r oken  do cum ent wa s wi del y applie d in  the ju dici al p h y sical  evide n c recovery, hi st orical  docum ent re storation and military inform ati on  acqui rem ent. T r aditionally, the  joint and  re co very wo rk  ne eded to b e  d one ma nually , which wo uld  lead to hig h   accuracy b u t low  efficien cy. Especi a lly a s  th e fra g ment  a m ount  wa h uge, the  ma n ual joi n t woul d cost  a l o o f   human a nd m a terial resource s.  The auto m atic joint issu belon ged to t he co mpute r   vision an d pa ttern re co gnition area,  whi c h was a c compli she d  by the comp uter proc essi ng to obtain  the informati on of the pa per  scrap, li ke  shape  and  color. T hen t he pa pe scrap wa s re stored autom atically  o r   semi- automatically. Curre n tly, most of the  pape scrap  joint wo rks  were a c com p lish ed ma n ually.  Although so me re sea r ch ers h a ve bee n done ab ro a d , little resea r ch findi ng s could be foun d for   the ap plicatio n ba ckg r oun d  sp ecifi c ity of the p ape scrap  autom atic re st oration t e ch nolo g y. T h e   descri p tion o n   the sh ape  matchin g   al g o rithm of  t he  simila r i s sue  wa s fou nd i n   some  a r ticle s  [1- 7]. For exam ple, in literatu r e [7], a meth od to a c comp lish the  pap er scra p joint b y  judging if t w o   profile s mat c hed by b oun dary a nd a r e a  pri n cipl es  from extra c ting  the contou r l i ne of the  pa per  scrap  wa given to achie v e t he pap er scra p auto m atic resto r a t ion ba sed  o n  the comp u t er  as sist a n c e .       2. Broke n  Paper Scrap o f  One-side Print Do cumen t   w i th  Only  Straight Cut    For a given b r oken pa pe r scra p from the  same p r int d o cum ent with  only straight  cut, the   fragme n t dat a of the d o cu ment with  19  items o n  two  page s in  Chi nese an d En glish  re spe c ti vely  wa s given by the comp uter  pro c e ssi ng, a nd then the jo int and re cov e ry we re do n e The lea s t sq uare met hod  wa s a mathe m atic optimi z ation techn o l ogy, which m i nimize d   the e rro sq u a re  an d fou n d  the  optimal  functio n  m a tch. T he  un kn own  data   cou l d be   cal c ulat ed  conve n iently  and th e e r ror sq uare b e tween th cal c ulated and a c tual data was  th mini m u m.  Nonli nea r le ast squa re  method  co ul d be  see n   as a  spe c ial  situation  fo r the u n restraint  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Mathem atical  Program m i ng Model on  Joint and Re cove ry of Pap e r Scrap (JIA NG Zhi x ia 5523 minimization,  which wa widely ap plie d in the area s like d a ta fitting, para m et er estim a tion  and   func tional approximation  [8]. The optimal mat c hin g  solution  for th e p a pe scrap  in  the   attachme nt by the least sq uare m e thod  and its value  wa s determin e d.  From th e b a sic  kno w led g e  of the im age  pro c e s sing, i t  wa kno w n   that the pixel  value   rang e of  ea ch pixel p o int  on the  pap er scra ps to   be   jointed wa s 0-25 5,acco rdi n to whi c h, the  figure  coul d b e  analyzed. T he figure wa s firstly bro k en  up into the p o int colle ction ,  and the pixe matrix of the  point  colle ct ion of the  fig u re  wa esta blish ed fo r a  ran dom fig u r e, which  wa s   assume d a s  j th  figure. It was  kn own  tha t  the matrix o f  the j th  figure  wa s 1 980* 7 2 , and th e pi xel  matrix of the i th  column of the j th  figure was:     hij ij ij ij p p p P 2 1 0 i 72 ,0 j 19     Firstly, for all  the pa per  scrap to  be  joint ed,  the fi rst  o ne o n  the  left  wa dete rmi ned if  all  of the left bounda ry point s we re  white,  namely t he pixel wa s 25 5, from whi c h the first pa per  scrap to be jo inted wa s fou nd.  Obviou sly, for a ra ndom f i gure, the  co rre sp ondi ng  pixel point color differen c e of the   other figu re  a nd it wa s n o t the sam e . Th e scre enin g  functio n   q p Q ,  was  defined, a n d t o  cal c ul ate  the squ a re  sum of the pixel point colo r value  differe nce b e twe e n  the right bo unda ry of the p th   figure an d co rrespon ding le ft boundary of  the q th  figure, the expressi on wa s a s  follows:    2 , 1 , 1980 1 , 72 , , ) ( q h h p h q p p p Q     Whe r e, hij p  mean t the h th  row a nd i th  column  of the pixel point colo r value matrix of the j th  figure.  For Fi gure p ,  as oth e r fi gure s   and it  match ed, e a ch  q p Q ,  was  ob tained, an what   need ed was the optimal  match, na m e ly the nonl i near  un rest raint mathem atic prog ram m ing  model.     Min   q p Q ,     Then Fig u re  p and q could  be jointed.   The program  was  written  with the Ma tlab so ftwa r e  in the Acer compute r  of  5750G  c o n f igu r ed   w i th  i5  pr oc es so r ,  th e   r u nn ing  time   wa s 0. 1s, the  joint  wa su ccessf ul and  the fig u re  of the recovery res u lt was  as  follows :           Figure 1. In Chine s e   Figure 2. In English   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5522 – 55 28   5524 3. Broke n  Paper Scrap o f  One-side Print Do cumen t   w i th Straigh t  and Cr oss  Cut    For a give n b r oken p ape scrap f r om th e sam e  pri n t document  with strai ght an d cross  cut, the  frag ment d a ta of  the  docume n t with  209  it ems on  two   page s i n   Chi nese a nd E n glish  respe c tively were given b y  the comput er proc essin g ,  and then the  joint and re covery wa s do ne.      3.1. Establis hment of  No nlinear Prog ramming Model   In the situati on of the  cro ss  cut, the m e t hod a bove  wa s imp r ove d . Firstly, ea ch p ape scrap i n  the  attachme nt was an alyze d , and the  mini mum vertical  distan ce b e twee n the whi t e   pixel  point on   the  top  of e a ch pap er scrap and  th e f i rst n on-white  pixel poi nt was utili zed  an d   analyzed in the com pute r  to roughly j udge the  sh ape match o f  the font. Accordi ng to the   literatures, th e geomet rica l characte ri stic of  the ro w wh ere the  paper  scra p lay could  be   obtaine d by e x isted te chn o l ogy, like  the  row hei ght  of  the characte r and  the  sp ace bet wee n  th c h arac ter lines  [9].  Ran dom pap er scrap s  we re  pi cked as the  i th  and j th   page, a nd if t he minim u vertical   distan ce s b e twee n the  whi t e pi xel point  on the top  of the i th  and j th   pape r scrap  and the first n on- white pixel po int were  mi d  and  mj d mj mi d d d - ij Acco rdi ng to  the figure s  in this pa p e r, the bo un dary value  o f   d  was  0 an d 5   respe c tively. If the value of  d  wa s between  0 and 5, it wa con s ide r e d  that the i th  and j th  pape scrap  could  b e  jointed  in th e same lin e,  or el se   the two could  not b e  jointed  in th e same lin e f o the big differe nce of the  ch ara c ter  stru ct ure, wh ich m eant that the  two pap er  scrap could n o t be   jointed. Th en  the dista n ces of the p e a ks  of i th  pape scrap  on the  lef t  and  right a n d  the first no n - white pixel  p o int ho rizo ntally were  cal c ulate d  an analyzed to f i nd the mi ni mum di stan ce   si x   and ti x , the bou ndary valu e o f  which was chosen a s  1 2 , 16 an d 6 to  28. By the sa me way, the   maximum character space  i y max,   bet ween  the top a n d  bottom p o i nt in anoth e r  re straint  con d ition was determin ed.         Figure 3. The  Characte r of  the ith Paper  Scra ps      In the  pro c e s s a bove, th binary z ation   method  was  adopte d . By  setting th e th reshold  value, the  co nversi on f r o m  the g r ay l e vel imag e t o  the  bina ryzation ima ge  wa s a c compli she d   [10]. The  gra y  level value   of the  white  pixel poi nt  was  marke d  a s  255,  whil e th e gray value s  of  the othe r pixe l points were   marked  as 0.  In this  pro c e ss, th e poi nt, who s pixel v a lue  wa clo s e   to that of the  white pixel,  was  con s id ere d  as  the  whit e point. Th Form  co uld b e  expresse as  follows   255 , 0, e l s e u t he po i n t  i s  w hi t e     Then, ba sed  on the theory  above, for all the  paper  scrap to be joint ed, the prog ram wa firstly compil ed to ran k  the pape r scraps in  the d e scen ding way accordi n g  to the minimum   prin ciple fo r the sum of  mi d  and si x , the pap er  scra p with th minimum val ue was  cho s e n  as th first eleme n t on the left top. Then ea ch of t he pa per scrap s was joine d  by the recu rren ce   d mi   y m a x,i   x si x ti  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Mathem atical  Program m i ng Model on  Joint and Re cove ry of Pap e r Scrap (JIA NG Zhi x ia 5525 algorith m  ba sed on th e pri n cipl e of from  left to right a nd from to p to bottom. In the joint p r o c e s the least squ a re meth od i n  the first mo del wa s u s ed  to screen th e pape r scra ps to be joint e d   with the  obj e c tive pa per scra p, the Min q p Q ,  was then  cal c ul ated, which me ant the  difference   of paper  scra p p and q wa s the minimu m, namely pa per scrap s p  and q were th e best mat c h.   The optimi z e d  model was  a nonlin ear  re straint optim a l  proble m   Min   q p Q ,   ma x , 05 12 16 .. 62 8 38 42 mi mj si ti i dd x st x y         As the pape scrap p a nd q  were joi n ted  cro s swi s e, th e obje c tive function  wa s:    min 2 , 1 , 1980 1 , 72 , , ) ( q h h p h q p p p Q     As the pape scrap p a nd q  were joi n ted  l ength w ays, the obje c tive functio n  wa s:     min 72 2 18 0 , , 1 , , 1 () ip i q i pp     Acco rdi ng to the model e s t ablishment a nd analy sis, the pro g ram was compile d with  Matlab software an d the in itial joint was  obtaine d.    3.2. Artificial  Interfe r enc e  Solution  In many situa t ions, as t w pape r scrap s   were both  co nsid ere d  a s  the suita b le o ne to be  jointed with  the  obj ective pape r scrap by  the  co mpu t er, the comp uter  would  au tomatically  ch ose   one of the m   whi c wa s co nsid ere d  the  better to join t  without the l o gical an alysi s . At this time , it  wa s ea sy to produ ce a la rg e-scal e and e x tensive join t error. He nce the artificial int e rferen ce wa of signifi can c e as the  solu tion erro r of the  comp uter  happ ened. A s  sho w n in  F i gure  4 a nd  5,  obviou s ly the  two fig u re s could  be totall y match ed  wi th the o b je ctive figure,  and  in thi s   situati on,  if the wron g f i gure  was pi cked  by the  compute r   (as  sho w n  in Fi g u re  2), th e ot her  pap e r scrap   woul b e   joi n ted with  oth e r pape r scra ps wro ngly  eith e r , which  woul d result in th e  domi n effect.  Mean while, if the artificial in terfere n ce wa s used  with t he logi cal thin king a nd an alysis of huma n it could  be  re alize d  that th e word  “cate n s” in th e fig u re to  be  join ted in Fi gure  5 didn’t  actu a lly  exist, hen ce t he joint  erro woul d be  fou nd a nd  co rre cted,  whi c would le ad to   a high  a c cura cy  and rig h t re storation  of the  literatures.           Figure 4. Join ted Corre c t F igure 5. Join ted Erro r                          Hen c e, the artificial interference nee ded  to  be added  after the initia l joint was o b t ained,  and th e inte rf eren ce   way  wa s: the  joint  co uple  of  th e pa pe scra ps i n  the  run n ing  re sult  of the  prog ram  was firstly foun d, and th en th e  se rial  numb e r a nd th e joi n t ord e we re  then  re corde d Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5522 – 55 28   5526 Another  se cti on of the  progra m  was then a dde i n  the initial j o int program  to achieve t he  desce nding o r de r of the sum of  mi d  and  si x  for each pa per scrap, the second  se quen cin g   value obtai ne d wa cho s e n  as th e first  element o n   the left top to find the p a per  scra p to  be   jointed ag ain,  the seri al nu mber a nd join t order  we re rec o rded, then the third, the forth etc .  were   found until n o  single  pap er scrap  wa s le ft or after the  prog ram  wa s run for th re e  times o r  more,  no n e w pa p e scra ps we re fo und  to  be joi n ted  wi th othe r p a p e scra ps.  T hen th e a r tificial  interferen ce  wa s finished,  and th e final  right  re sult   wa s a c hieve d  by the a r tificial joi n t with  the  logical analysis on the character a nd lan guag e.  In additio n , for En glish d o c ume n ts, th e  variabl e val ue rang e of t he rest raint  condition  coul d be  ch ange d app ro priately be ca use of the  differen c e b e t ween En glish and  Chin e s cha r a c ter, the  following  wa s used:     42 23 28 6 16 12 16 0 ma x y x x d d t s mj mi     The rig h t joint result obtai n ed wa s a s  Figure 6. an d F i gure 7:             Figure 6. In Chine s e   Figure 7. In English       4. Broke n  Paper Scrap o f  both Sides P r int Doc u me nt   For  a give n b o th si de s p r in t document  of  English ve rsi on fro m  the  same p a ge  wit h  both   straig ht an cro s cut by  the shredde r, the jo i n t a nd resto r atio n of the  pap er  scrap  were  accompli sh ed  with th e hel p of the  both  sid e frag m ent data  of 2 09 d o cument s give n by th comp uter.   The  pape scrap  coll ectio n  of the fi rst li ne &  colu mn  and  the l a st  line &  col u mn after  being j o inted  wa s firstly judged. Fo wh ich, a n e w v a riabl ni d  was   introduc e d to indicate the  minimum dist ance  b e twee the white p i xel  point  of  all the p e a k s at the  botto m of the i th  p a per  and the  first non-white  pix e l point ve rtically. From th e compute r  p r og ram, the ni d , mi d , si x  and   ti x  could be o b tained an d the four matrixes were e s tabli s he d for the pape r scrap give n.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Mathem atical  Program m i ng Model on  Joint and Re cove ry of Pap e r Scrap (JIA NG Zhi x ia 5527 Acco rdi ng to the prin ciple  that  mi d  of  the first line elem ents was big g er than oth e r eleme n ts,   and the  difference bet wee n   mi d   and t he el e m ents i n  ea ch line  sho u ld  not be too  big ,  and by the  artificial i n terf eren ce  to ob serve  the val ue of e a ch el ement in th matrix, the 1 9  pap er  scra ps in  the first line,  the la st li ne , the first  col u mn  and  the  last  column  co uld  be  fo und  so on. T hen  according to the prin cipl e that only one  comm on ele m ent existed  in a rand om li ne or colum n , the   first eleme n t in the first lin e coul d be d e termin ed so on, and the  optimal match for ea ch p aper  scrap  coul d b e  found a c cording to the pri n cipl e of fr om  left to right and from top to bottom. In the  same  way, the la st elem en t of the first li ne, the  first el ement of th e l a st lin e an d t he la st ele m e n of the l a st li n e  were d e termined,  and  e a ch  mat c h re sult coul d be   obtain e d   by taking   the   three  element s as t he initial obje c tive pape r scra p to be ma tched.    For the rest ri ction of the b o th side s p r in t, t he algorith m  accuracy  wa s lo we red. Hence, in   the matchin g  process of the obje c tive pape r sc rap and othe r pa per scrap s, the ant colo n y   algorith m  wa s ado pted.   The ant colo ny algorithm  wa s a prob a b ilisti c an d o v erall situatio n sea r ch method, and  the uncertai n ty property in  this algo rith m woul d le a d  to more o p p ortunitie s  to  find the optimal  solutio n  in  th e overall  situ ation [11 - 13].  The  ant  col ony alg o rith m co uld i n crease the  ma tch   accuracy for  the pape r scrap, it s optimi z ation p r o c e s s did not re ly on the rigo rous m a them atic  prop erty of itself, and it ha d the potenti a l parall e lism ,  which in cre a se d the efficiency an d instan rea c tion a b ility of the algo rithm. In the  matchin g  p r oce s s, the p aper  scrap n u mbe r  be ca me  large r , an d th e pixel of th figure s   wa smaller, h e n c e  the ant  col o n y  algorithm  was  use d  in  thi s   pape r to pro c ess optimally and in cre a se the match a c curacy.   The four m a tchin g  re sults from the proc e s s above  were  ob served, and the  artificial   interferen ce  wa s a dde d at  this time, wh ich  wa s to  re cord th right  joint  re sults,  adju s t the  wrong  jointed  pap er scrap s   whi c h was a r tifici ally re cog n ized, an re-m atch th wro ng joi n ted  pa per   scrap s   whi c h  could  not be  artificially re cog n ized fro m  the pape edge. Th e proce s s sh ould  be  repe ated until  the right matchin g  re sults  were obtain e d         Figure 8. Join t Result     5.  Conclusi on  The technolo g y  of  joint and re covery of  paper  scra p  are con s ide r ed in sh ape  before.  This pa pe r give a method com b ine d  ant colony  algorith m  an d the least  squ a re m e th od   according  to  the word s m e ssag e in  th e pa per  sc ra p. Ho weve r,  for the  pa per scrap  with  big  informatio n, a great amo u n t  of artificial interfere n ces  was ne ede d in this model.   Evaluation Warning : The document was created with Spire.PDF for Python.
                               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 7, July 201 4:  5522 – 55 28   5528 Referen ces   [1]  Da Gama Le i t ao, HC Stolfi  J. A Multiscale  Meth od f o r the Reass e mbl y  of T w o - dimens io na l   F r agmente d Ob jects.  IEEE. Pa ttern Analysis  and Mac h in e Intelli ge nce . 20 02; 24(9): 1 239 –12 51.   [2 Yi g i tsoy   M, Na va b N .  Structu r e  Prop ag a t ion for  Imag e R egistrati on . Medic a l  Imagi ng.  IEEE  T r ansactio n s o n . 2013; 3 2 (9): 165 7 – 16 70.   [3]  Kong WX , BB  Kimia.  On  S o lv ing 2D   an 3 D  Pu zz l e s Usi ng Curve  M a tchi n g Proce edi ngs  of Com pute r   Visio n  and P a ttern Rec ogn itio n,  Ha w a i i . USA. 2001; (2): 583-5 90.   [4]  Z hu LJ, Z hou ZT , Hu DW Globa ll y Co nsi s t ent Reconstr uction of Ri pp ed-U p  Docum ents.    Pattern  Analys is and M a chi ne Intel lig e n ce, IEEE Transactions o n , Issue: 200 8; 3.1 – 13.   [5]  Liu  HR, Ca o  SJ, Yan SC . Automated  Assembl y   of Shred d e d  Pie c es F r om Mu ltiple  Phot os,     Multimed ia.  IEEE Transactions on . 20 11; 1 3 ( 5): 1154  – 1 162.   [6]  Richter F ,  Ri es C X , Ce br on N. L i en ha rt R.   Learn i n g  to Re asse mble S h red d e d  Doc u ments,     Multimed ia , IEEE Transactions on . 20 13; 1 5 (3): 582 –  593 [7]  Jia HY, Z hu LJ, Z hou ZT , Hu DW .   A Shape Matchin g  Method for Auto matic Reass e mbl y   of Pape r   F r agments.  Co mp uter Si mu lat i on . 20 06; 23( 1 1 ): 180-1 83.   [8]  Yuan Y X , Sun  W Y Optimi z a t i on theory a nd  meth od , Bei jin g: Science pr e ss, 1997.   [9]  Luo Z Z .  Sem i -auto stitch in g of scra ppe pa per  bas e d  on  char acter char acterist ic.  Co mp ute r   Engi neer in g an g Appl icatio ns . 201 2; 48(5): 20 7-21 0.  [10]  Yao Y H , Ch en g Y. A Bi nar iza t ion M e t hod  to  Process Sc ann ed Ima ges  of ID Car d . Mac h i ne B u il din g   &   Autom a tion . 20 02; (5): 65-68.   [11]  Yang JF . Ant colo n y   alg o rithm  and its ap plic a t ion rese arch. Z heji ang U n iv e r sit y , doctor a l thesis. 20 07.   [12]  Qi CM. Vehicl e Routi ng Opti mizatio n  in L o g is tics Distrib u t ion Usi ng H y brid Ant Co lo n y  Al gorithm T E LKOMNIKA Indon esi an Jou r nal of Electric al Eng i ne eri ng  . 2013; 11( 9): 5308- 531 5 .   [13]  Len in Ka nag as aba i, B Ravin d r anath R e d d y M Sur y a K a lav a thi.  Optimal P o w e r F l ow  using Ant Colo ny   [14]  Search  Alg o rit h m to Eva l u a te L oad  Curta i lment  Inc o rpor ating  Volta g e   Stabil i t y  M a rg i n  Criter ion.   Internatio na l Journ a l of Electr ical  a nd Co mp uter Engi ne erin g (IJECE) . 201 3; 3(5): 603-6 1 1 .       Evaluation Warning : The document was created with Spire.PDF for Python.