I nte rna t io na l   J o urna l   of   I nfo r m a t ics   a nd   Co mm u n ica t io n   T ec hn o lo g y   ( I J - I CT )   Vo l. 8 ,   No . 1 ,   A p r il   201 9 ,   p p .   1 ~ 12   I SS N:   2252 - 8776 ,   DOI :   1 0 . 1 1 5 9 1 /i j ict. v 8 i1 . p p 1 - 12       1       J o ur na l   ho m ep a g e :   h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / I JI C T   A   no v el   s k et ch - ba sed   3D   m o del   retr iev a l   a ppro a ch     ba sed   o n   s k eleton       J ing   Z ha ng ,   B a o   s heng   K a n g ,   Bo   J ia ng ,   Di   Z ha ng     No rth w e st   Un iv e rsit y /De p a rt m e n t   of   In f o rm a ti o n   S c ien c e   a n d   T e c h n o l o g y ,   Ch in a       Art icle   I nfo     AB ST RAC T   A r ticle   his to r y:   R ec eiv ed   Oct   9,   20 18   R ev i s ed   Dec   20,   2 0 1 8   A cc ep ted   J an   11,   2 0 1 9       S in c e   th e   sk e leto n   re p re se n ts   th e   to p o l o g y   stru c tu re   of   th e   q u e ry   sk e tch   a n d   2D   v iew s   of   3D   m o d e l,   t h is   p a p e r   p ro p o se s   a   n o v e l   sk e tch - b a se d   3D   m o d e l   re tri e v a l   a lg o rit h m   w h ich   u ti li z e s   sk e leto n   c h a ra c teristics   as   th e   f e a tu re s   to   d e sc rib e   th e   o b jec t   sh a p e .   F irstl y ,   we   p ro p o se   a d v a n c e d   sk e leto n   stre n g t h   map   ( A S S M )   a lg o rit h m   to   c re a te   th e   sk e l e to n   w h ich   c o m p u tes   th e   sk e leto n   stre n g th   m a p   by   iso tro p ic   d if f u sio n   on   t h e   g ra d ien t   v e c to r   f ield ,   se lec ts   c rit ica l   p o in ts   f ro m   th e   s k e let o n   stre n g th   m a p   a n d   c o n n e c ts   th e m   by   Kru sk a l' s   a l g o rit h m .   T h e n ,   we   p ro p o se   h isto g ra m   f e a tu re   c o m p a riso n   a lg o rit h m   w h ich   a d o p ts   th e   ra d ii   of   th e   d isk s   at   s k e leto n   p o in ts   a n d   th e   len g th s   of   sk e leto n   b ra n c h e s   to   e x trac t   th e   h isto g ra m   f e a tu re ,   a nd   c o m p a re   th e   sim il a rit y   b e t w e e n   t w o   sk e le to n s   u sin g   th e   h isto g ra m   f e a tu re   m a tri x   of   sk e leto n   e n d p o in ts.   Ex p e rim e n t   re su lt s   d e m o n stra te   th a t   our   a p p ro a c h   w h ich   c o m b in e s   th e se   t w o   a lg o rit h m s   sig n if ica n tl y   o u tp e rf o r m s   se v e r a l   lea d in g   sk e tch - b a se d   re tri e v a l   a p p ro a c h e s .   K ey w o r d s :   A d v an ce d   s k eleto n   s tr en g t h   m ap   His to g r a m   f ea tu r e   co m p ar is o n   Sk eleto n   f ea t u r es   S k etc h - b ased   3D   M o d el   R etr iev al   Co p y rig h t   ©   2019   In stit u te   of   A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .     All   rig h ts   re se rv e d .   C o r r e s p o nd ing   A uth o r :   J in g   Z h a n g,     Dep ar t m en t   of   I n f o r m atio n   Sc ien ce   an d   T ec h n o lo g y ,   No r th w est   U n i v er s it y ,   C h a n g   An   Q u . ,   Xi ' an ,   C h in a .   E m ail:   m y w an g w a n g 1 2 3 @ 1 6 3 . co m       1.   I NT RO D UCT I O N   W ith   t h r ap id   in cr ea s i n   t h e   n u m b er   o f   a v ailab le  3 m o d els,  ac cu r atel y   a n d   ef f ec ti v el y   s ea r ch   3 m o d el  i s   i m p o r tan f o r   m an y   a p p licatio n s   s u ch   as  i n d u s tr ial  d esig n ,   en g in ee r i n g ,   an d   m a n u f ac t u r in g   ar ea .   T h e   m o s p o p u lar   w a y   f o r   r etr iev i n g   3 m o d els   is   e x a m p le - b as ed   p ar ad ig m ,   w h er th u s er   p r o v id es  an   e x is t in g   3 m o d el  as  q u er y   i n p u an d   th r etr iev a s y s te m   c a n   r e tu r n   s i m ilar   3 m o d els  f r o m   th d atab ase  [ 1 ] .   Ho w e v er ,   it  i s   d if f ic u lt  f o r   u s er   to   h a v a n   ap p r o p r iate  ex am p le  3 m o d el  a h a n d .   An   al ter n ati v w a y   is   to   u s 2 D   s k etch   as  a   q u er y   w h e r u s er s   ca n   d escr ib tar g et   3 m o d el  b y   q u ic k l y   d r a w i n g   it.  B u a   2 s k etc h   is   m er el y   co ar s a n d   s i m p le  r ep r esen tatio n   w h ic h   o n l y   co n tain s   p ar tial i n f o r m atio n   o f   a n   o r ig in al  3 m o d el.   Hen ce ,   it is   m o r ch alle n g in g   t o   r ea lize  s k etch - b ased   r etr iev al  th a n   a n   ex a m p le - b ased   r etr iev al  [ 2 ] .   T h s k eleto n   is   w id el y   r ec o g n iz ed   as  o n o f   th e   m o s i m p o r tan s h ap d escr ip to r s   in   s k etch - b ased   3 m o d el  r etr iev al  p r o ce s s .   T h s k eleto n   e x tr ac tio n   a lg o r ith m s   g e n er all y   ar cla s s i f ied   in to   f iv t y p es:  t h th i n n i n g   al g o r ith m   [ 3 ] ,   t h d is cr ete  d o m ain   al g o r ith m   b ased   o n   t h Vo r o n o d iag r a m s   [ 4 ] ,   th a n al y tic   co m p u tatio n   o f   th o b j ec co n to u r   alg o r it h m   [ 5 ] ,   th al g o r ith m   b ased   o n   m at h e m atica m o r p h o lo g y   [ 6 ] ,   an d   th al g o r ith m   b ased   o n   d i s tan ce   tr an s f o r m   [ 7 ] .   B er tr an d   et  al  [ 8 ]   f o u n d   t h at  t h t h i n n in g   al g o r ith m   is   q u it e   s en s iti v to   n o i s a n d   ca n   ac h iev e   lar g a m o u n o f   ca lc u l atio n ,   w h ich   is   e x p ec ted   to   eli m i n ate  lo ca n o is e   w it h o u i n tr o d u cin g   d is to r tio n s   an d   r etai n   s i g n i f ican t   f ea t u r es  o f   t h p atter n .   G iese n   J   et  al  [ 9 ]   r esear ch ed   o n   th d is cr ete  d o m ai n   alg o r it h m   b ased   o n   th Vo r o n o d iag r a m s   w h ich   ca lc u lates  t h Vo r o n o d iag r a m s   v ia  s u f f icie n t la r g e   s et  o f   p o in t s   s a m p led   f r o m   its   b o u n d ar y .   I f   t h a m o u n t o f   s a m p led   p o in ts   is   ex tr e m e l y   lar g e,   it   w o u ld   lead   to   th n u m er ical  i n s tab ili t y   i n   th co m p u tatio n   o f   Vo r o n o d iag r am s .   Kr in id i s   et  al  [ 1 0 ]   f o u n d   th at  t h a n al y tic   co m p u tatio n   o f   t h o b j ec co n to u r   al g o r ith m   w o u ld   lead   to   t h al g o r ith m s   in ac c u r ac y   d u to   Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   2252 - 8776   IJ - I C T   Vo l.   8 ,   No .   1 ,   A p r il   2 0 1 9   :   1 12   2   th p o l y g o n al  ap p r o x i m atio n   is   m o s tl y   n o s u f f icie n f o r   b io lo g ical  s h ap d escr ip tio n .   Mitr A   et  al  [ 1 1 ]     f o u n d   th a t h al g o r ith m   b ase d   o n   m at h e m atica l   m o r p h o lo g y   ca n   lo ca lize  t h ac c u r ate  s k eleto n ,   b u m a y   n o t   g u ar a n tee  t h e x ac co n n ec ti v it y   o f   th s k eleto n .   Ya n   T   et  al  [ 1 2 ]   f o u n d   th a t h alg o r ith m   b ased   o n   d is tan ce   tr a n s f o r m   co m p u te  t h s k eleto n   b y   d etec ti n g   r id g es  o n   th d i s ta n ce   tr an s f o r m   s u r f ac e,   w h ic h   en s u r e s   th ac c u r ate  lo ca lizatio n   o f   s k eleto n   p o i n ts .   Ho w e v er ,   th alg o r ith m   b ased   o n   d i s tan ce   t r an s f o r m   is   lack   o f   co n n ec ti v it y   a n d   co m p leten e s s ,   w h ich   m ea n s ,   th ex tr ac ted   b r an ch es  m a y   b d is co n n ec te d   an d   n o b e   ab le  t o   r ep r e s en t a ll th s ig n i f ica n t v i s u al  p ar ts .     Ho w   to   co m p ar th s k e leto n   s i m ilar it y   b et w ee n   t h q u er y   s k etc h   a n d   2 v ie w s   o f   3 D   m o d el  i s   cr u cial.   T h er ar t h r ee   t y p es   o f   a lg o r it h m s   to   co m p ar t h s k eleto n   s i m ilar it y ,   r e s p ec ti v e l y   tr ee   m atc h i n g   alg o r ith m   [ 1 3 ] ,   p ath   s i m ilar it y   alg o r it h m   [ 1 4 ]   an d   g r ap h   r ep r esen tatio n   al g o r ith m   [ 1 5 ] .   Dr ag an   et   al  [ 1 6 ]   f o u n d   th at  th tr ee   d escr ip to r   r ep r esen ts   t h to p o lo g ical  f ea t u r es  o f   t h s k eleto n ,   b u t h m ax i m a is o m o r p h ic   s u b tr ee s   ar o b tain ed   b y   s ea r ch in g   f o r   th lo n g est   m atc h i n g   s u b s tr i n g s   w h ic h   w o u ld   l ea d   to   h ig h er   ti m e   co m p le x it y .   B ai  et  al  [ 1 4 ]   m atc h ed   th s k e leto n   g r ap h s   b y   co m p ar in g   t h g eo d esic  p a th s   a m o n g   s k e leto n   en d p o in ts .   Ho w e v er ,   th eir   ap p r o ac h   is   o n ly   m o t iv ated   b y   t h v i s u a ll y   s i m i lar   s k elet o n   g r ap h s ,   w it h o u t   co n s id er in g   th to p o lo g ical  g r ap h   s tr u ct u r e.   Yo u s s ef   R   et  al  [ 1 7 ]   f o u n d   th at  th g r ap h   r ep r esen tatio n   alg o r ith m   is   w id el y   i n v e s ti g a ted   r eg ar d in g   m atc h i n g   is s u e s ,   d u to   th co r r esp o n d en ce   b et w ee n   s k eleto n   b r an ch es   w it h   g r ap h   ed g es   a n d   n o d es   is   n a tu r al   a n d   i n t u it iv e.   Ho w e v er ,   t h s o lu tio n s   i n   t h liter atu r e   ar b ased   o n   s h o ck   g r ap h s   [ 1 8 ]   o r   attr ib u ted   r elatio n al  g r ap h s   [ 1 9 ]   w h ic h   ar o n l y   u s ed   i n   ce r tain   ap p licatio n   d o m ai n s   a n d   u s u all y   w it h   h ig h er   ti m co m p le x it y .   T o   tack le  th ese   p r o b le m s ,   t h i s   p ap er   p r o p o s es  n o v el   s k e tch - b ased   3 m o d el   r etr iev al   ap p r o ac h     w h ic h   co m b i n es  t h ad v a n ce d   s k eleto n   s tr e n g th   m ap   ( A S S M)   alg o r ith m   w it h   h is to g r a m   f ea t u r co m p ar is o n   alg o r ith m   to   cr ea te  t h s k eleto n   an d   co m p ar t h s i m i lar it y .   Ou r   A S SM  alg o r it h m   o r ig i n s   f r o m   t h al g o r ith m   b ased   o n   d is tan ce   tr an s f o r m ,   w h ic h   en s u r es  t h ac cu r ate  lo ca lizatio n   o f   s k eleto n   p o in t s .   Fu r t h er ,   o u r   A SS M   alg o r ith m   s elec t s   cr itical  p o in ts   f r o m   t h s k eleto n   s tr en g th   m ap   an d   co n n ec t s   th e m   b y   K r u s k al ' s   al g o r ith m   [ 2 0 ] ,   w h ic h   s o l v es  t h co n n ec tiv it y   an d   co m p lete n es s   p r o b l e m   o f   p r ev io u s   alg o r it h m .   T h h is to g r a m   f ea tu r e   co m p ar is o n   alg o r it h m   o r ig i n s   f r o m   th g r ap h   r ep r esen tatio n   alg o r ith m ,   w h ich   ex p r ess es  t h s k eleto n   b r an ch es  n at u r all y   a n d   in tu i ti v el y   [ 2 1 ] .   Ou r   h is to g r a m   f ea t u r co m p ar is o n   al g o r ith m   ad o p ts   th r ad ii  o f   t h e   d is k s   at  s k ele to n   p o in ts   a n d   th len g t h s   o f   s k eleto n   b r an c h es   to   ex tr ac th h i s to g r a m   f ea tu r e.   T h r ad ii  o f   th e   d is k s   an d   len g t h s   o f   s k e leto n   b r an c h es   ar i n v ar ia n u n d er   th e n v ir o n m en o f   n o n - r i g id   tr an s f o r m atio n s   w h ic h   w o u ld   h elp   t o   g et  h i g h - p r ec is io n   r etr iev al  r e s u l t.  A d d itio n all y ,   w co m p ar t h s i m i lar it y   b et w ee n   t w o   s k eleto n s   u s in g   th e   h i s to g r a m   f ea t u r m a tr ix   o f   s k e leto n   e n d p o in ts ,   w it h   r elat iv el y   less   q u a n tit y   t h a n   s k eleto n   p o in ts ,   w h ic h   lead s   to   lo w er   co m p u tatio n al  co m p le x i t y .   T o   ev alu ate  o u r   ap p r o ac h ,   w t est  o u r   ap p r o ac h   o n   th p u b lic   s ta n d ar d   d ataset  an d   also   co m p ar ed   w it h   o t h er   lead in g   3 m o d el  r etr ie v al  ap p r o ac h es.  T h e   ex p er i m e n ts   d e m o n s tr ate  th at  o u r   ap p r o ac h   is   s ig n i f ica n tl y   b etter   th an   s e v er al  lead i n g   s k etch - b ased   r e tr iev a l   ap p r o ac h es.       2.   RE S E ARCH   M E T H O D   T h e   f r a m e w o r k   of   s k etch - b as ed   3D   m o d el   r etr iev al   b ased   on   ad v a n ce d   s k eleto n   s tr e n g t h   m ap   an d   h is to g r a m   f ea t u r e   co m p ar is o n   alg o r ith m   is   p r o p o s ed   as   s h o wn   in   Fig u r e   1.       2 D   Q u e r y   S k e t c h   I n p u t S t a r t 3 D   M o d e l   S e t 2 D   P r o j e c t i o n   V i e w   o f   3 D   M o d e l H i s t o g r a m   F e a t u r e   E x t r a c t i o n   S k e l e t o n   D i s t a n c e   C o m p u t a t i o n   2 D   P r o j e c t i o n   V i e w   F e a t u r e   S e t R e t r i e v a l   R e s u l t s E n d A d v a n c e d   S k e l e t o n   S t r e n g t h   M a p H i s t o g r a m   F e a t u r e   E x t r a c t i o n   2 D   S k e t c h F e a t u r e   S e t A d v a n c e d   S k e l e t o n   S t r e n g t h   M a p     Fig u r e   1.   T h e   f r am e w o r k   of   o u r   s k e tch - b ased   3D   m o d el   r etr iev al   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - I C T     I SS N:   2252 - 8776       A   n o ve l   s ke tch - b a s ed   3D   mo d el   r etri ev a l   a p p r o a ch   b a s ed   on   s ke leto n   ( Jin g   Zh a n g )   3   2 . 1 .     P re - pro ce s s ing   I n   th d atab ase  ea c h   3 m o d e h as  a n   ar b itra r y   p o s itio n ,   o r i en tatio n   a n d   s ca le  i n   t h s p ati al  s p ac e,   it  is   n ec es s ar y   to   n o r m alize   ea ch   3 m o d el  b ef o r p r o j ec th em   in to   2 v ie w s .   Af ter   3 m o d e ls   in   th d atab ase   h av b ee n   n o r m alize d ,   w co m p ar t h q u er y   s k e tch   w it h   6 0   p r o j ec tio n   v ie w s   o f   ea ch   3 m o d el  u s in g   li g h t   f ield   d escr ip to r s   [ 2 2 ] .   I n   ad d itio n ,   w u t ilize  2 s k etc h - 3 m o d el  ali g n m e n al g o r it h m   to   s elec s o m e   ca n d id ate  v ie w s   f r o m   t h 2 p r o j ec tio n   v ie w s   f o r   ef f icien tl y   co m p ar in g   t h s i m ilar it y .     Ou r   lig h t   f ield s   ar e   d is tr ib u te d   u n i f o r m l y   a n d   p o s itio n ed   on   v er tice s   of   a   r eg u lar   d o d ec ah ed r o n .   Fo r   r eg u lar   d o d ec ah ed r o n ,   each   of   th e   20   v er tice s   is   co n n ec ted   by   3   ed g es,   w h ich   r e s u l ts   in   60   d if f er e nt   r o tatio n s   ( 3 edg e 20 s ve r t i ce s )   f o r   o u r   p r o j ec tio n s ,   so   th at   we   n ee d   r o tate   th e   ca m er a   s y s te m   60   ti m e s .   W h en   th e   ca m er as   s w itch   o n to   d if f er en t   v er tices   [ 2 3 ]   we   m ea s u r e   th e   s i m ilar it y   b et w ee n   3D   m o d el   a nd   s k e tch .   Her e   is   a   t y p ical   ex a m p le   to   ex p lai n   o u r   ap p r o ac h .   As   s h o w n   in   Fi g u r e   2,   in   t h e   le f t   is   a   p ig   3D   m o d el,   in   t h e   r ig h t   d is p la y   60   p r o j ec tio n   v ie w s   wh ich   ar e   r en d er ed   f r o m   v er tice s   of   a   d o d ec ah ed r o n   f o r   th e   p ig   3D   m o d el.           Fig u r e   2 .   T h e   lig h t   fi eld   d escr ip to r s   of   3D   m o d el   p r o j ec tio n       To   en h an ce   t h e   r etr iev a l   ac cu r ac y   a n d   p er f o r m an ce ,   we   ad o p t   2D   s k etch - 3D   m o d el   alig n m e n t   alg o r ith m   [ 2 4 ]   to   ch o o s e   th e   ca n d id ate   v ie w s   in   th e   s k etc h - b ased   3D   m o d el   r etr iev al.   We   ch o o s e   ca n d id ate   v ie w s   [ 2 5 ]   by   k ee p in g   a   ce r tain   p er ce n ta g e   T   w it h   to p   s i m ilar ities   b et w ee n   t h e   s k et ch   an d   all   th e   2D   p r o j ec tio n   v ie w s ,   e. g .   20% T   m ea n s   t h at   th e   n u m b er   of   o u r   ca n d id a te   v ie w s   is 6 0 * 2 0 % = 1 2 .       2 . 2 .     Adv a nced   s k elet o n   s t re ng t h   m a p   ( A SS M )   T h e   alg o r ith m   of   s k eleto n   e x tr ac tio n   by   A S SM   is   d escr ib ed   as   f o llo w s :   1.   Step   1.   E x tr ac tio n   of   e x ter n al   b o u n d ar y .   Fo r   each   q u er y   s k et ch   an d   2D   v ie w s   of   3D   m o d el s ,   th e   e x ter n a l   b o u n d ar y   is   e x tr ac ted   f ir s t l y ,   w h ic h   p r o v id es   m u c h   of   th e   i m ag e   v i s u al   i n f o r m atio n   f o r   th e   SSM   v al u e.   2.   Step   2 .   C o m p u tat io n   o f   SS v alu [ 2 6 ] .   W p er f o r m   d is tan ce   tr an s f o r m   o n   b o u n d ar y   a n d   th en   co m p u t e   th SS v al u b y   is o tr o p ic  d if f u s io n   o n   th g r ad ien v ec to r   f ield .   3.   Step   3.   R e f in ed   SSM   v al u e.   We   ad o p t   th e   n o n - m a x i m al   s u p p r ess io n   al g o r ith m   [ 2 7 ]   f o r   t h e   r ef in ed   SSM   v alu e.   4.   Step   4.   Selectio n   of   cr itical   p o in ts .   We   s elec t   t h e   cr itical   p o in ts   f r o m   t h e   r ef i n ed   SSM   v al u e.   5.   Step   5.   Sk ele to n   tr ac e.   T h e   f i n al   s k ele to n   is   o b tain ed   by   c o n n ec ti n g   t h e   cr itical   p o in t s .   We   p r o p o s e   a   co n n ec ti n g   cr itical   p o in ts   m et h o d   w h ic h   u s es   th e   Kr u s k al 's   al g o r ith m   to   d ec id e   t h e   o r d er   of   th e   co n n ec ti n g   p ath .   2 . 2 . 1.   Co m pu t a t io n   of   SSM   v a lue   We   d ef in e   a   f u n c tio n   () fr to   g et   th 9 e   ac cu r ate   s k eleto n   [ 2 6 ]   :     ( ) 1 ( ) ( ) f r G r d t r   ( 1 )     w h er e   () Gr r ep r esen ts   a   Ga u s s ian   k er n el   f u n ct io n ,   () d t r   r ep r esen ts   d is ta n ce   tr a n s f o r m   w h ic h   is   t h e   d is tan ce   f r o m   an   i n ter io r   p o in t   r   to   th e   n ea r est   b o u n d ar y   p o i n t,     is   its   s tan d ar d   co v ar ian ce ,   an d     is   th e   co n v o lu tio n   o p er ato r .   We   co m p u te   t h e   g r ad ien t   of   () fr as   f o llo w :       00 ( , ) ( , ) ff u v f xy     ( 2 )   Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   2252 - 8776   IJ - I C T   Vo l.   8 ,   No .   1 ,   A p r il   2 0 1 9   :   1 12   4   T h e   is o tr o p ic   d if f u s io n   of   () fr   is   p er f o r m ed :     2 2 2 2 2 2 ( ) ( ) ( ) ( ) x x y y x y du u u u f f f dt dv u u v f f f dt   ( 3)     w h er e   , uv ar e   t w o   co m p o n e n ts   of   th e   d if f u s ed   g r ad ien t   v ec to r   f ield .   x f   an d   y f   ar e   th e   t w o   co m p o n en t s   of () fr .   I n itializi n g   , uv w i th   00 , uv in   ( 2 ) ,   th e   p ar tial   d if f er en tia l   ( 3 )   can   be   s o lv ed   iter ati v el y   by   f in ite   d if f er e n ce   tech n iq u e.   T h e   is o tr o p ic   d if f u s io n   m a k es   th e   v ec to r s   of   () fr p r o p ag ate   to w ar d s   to   th e   o b j ec t   ce n tr e,   an d   th e   in ter s ec tio n s   of   v ec to r s   d eter m i n e   th e   ac t u al   lo ca tio n   of   th e   s k eleto n   p o in ts .     T h en ,   we   co n s id er   th e   i n itial   g r ad ien t   v ec to r   f ield () g v f r :     ( ) ( ( ) ( )) rr g vf r I r I r rr   ( 4 )     w h er e   () Ir   is   t h e   in te n s it y   v al u e   at   r ,   an d   r   r ep r esen ts   o n e   of   th e   ei g h t   i m m ed iate   n eig h b o r s   of   r .   T h e   SSM   v al u e   at   ea c h   p o in t   i n d icate s   t h e   p r o b ab ilit y   of   b ei n g   a   s k eleto n   p o i n t.   T h e   h i g h e r   v alu e   at   a   p o in t,   th e   m o r e   p r o b ab le   th is   p o in t   is   a   s k ele to n   p o in t.   We   co m p u te   t h e   SSM   v al u e   b y :     ( ( ) ) ( ) ( ) ( ) m ax ( 0 , ) r N r g vf r r r S S M r rr    ( 5 )     w h er e   () Nr is   t h e   s et   of   t h e   ei g h t   i m m ed iate   n ei g h b o u r s   of   r .     2 . 2 . 2.   Ref ined   SSM   v a lue   W h en   we   h a v e   b ee n   co m p u te d   th e   v al u e   of   SS M,   u s e   n o n - m ax i m a l   s u p p r ess io n   [ 2 7 ]   alg o r ith m   to   o b tain   SSM   r ef i n ed   ed g e.   T h e   n o n - m ax i m al   s u p p r ess io n   alg o r ith m   is   d escr ib ed   as   f o llo w s :   Fig u r e   3 ( a)   s h o w s   th e   e ig h t   d i r ec tio n s   of   p o i n t   ( , ) P x y   w it h i n   t h e   3 ×3   r eg io n .   In   F ig u r e   3 ( b ) ,   th e   q u ad r an g le   is   f o r m ed   by   co n n ec ti n g   th e   e ig h t   d ir ec tio n s   of   p o in t ( , ) P x y .   T h en ,   we   u s e   t h e   d ir ec tio n   of   () g vf P   to   m a k e   a   s tr ai g h t   lin e,   w h ic h   in ter s ec t   w it h   t h e   q u ad r an g le   at   p o in t   ( , ) xy  an d ( , ) xy .     If   ( , ) ( , ) & ( , ) ( , ) S S M x y S S M x y S S M x y S S M x y  ,   th en   t h e   p o in t   ( , ) P x y   w il l   be   r etain ed .   If   n o t,   th e   p o i n t   ( , ) P x y w il l   be   d elete d .   W h en   all   p o in ts   h av e   b ee n   u tili ze d   t h e   n o n - m ax i m a l   s u p p r ess io n   alg o r it h m ,   we   w o u ld   g et   t h e   r ef i n ed   SSM   v al u e.       3 2 1 4 P 8 7 6 5   ( a)   P = ( x , y ) ( x ' , y ' ) ( x " , y " )   ( b )       Fig u r e   3.   ( a)   T he   eig h t   d ir ec ti o n s   of   p o in t ,   ( b )   T h e   q u ad r an g le   f o r m ed   by   co n n ec ti n g   t h e   ei g h t     d ir ec tio n s   of   p o in t     Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - I C T     I SS N:   2252 - 8776       A   n o ve l   s ke tch - b a s ed   3D   mo d el   r etri ev a l   a p p r o a ch   b a s ed   on   s ke leto n   ( Jin g   Zh a n g )   5   2 . 2 . 3.   Select io n   of   cr it ica l   po i nts   Fo r   th e   r ef i n ed   SSM   v al u e,   we   se lect   t h e   cr itical   p o in t s   w it h   t h e   lo w es t   v al u e   of   th e   g r ad ien t   m ag n it u d e ( ) ( ) G r d t r  .     Ou r   cr itical   p o in ts   co r r esp o n d   to   s ig n i f ican t   v is u al   p ar ts   of   th e   o b j ec t.   T h er ef o r e,   th e   o b tain ed   s k eleto n   co n tai n s   b r an c h es   r e p r esen tin g   all   s ig n i f ica n t   v i s u al   p ar ts .   No tice   th at   in   th e   d e f i n itio n   of   th e   cr itical   p o in t,   we   a ls o   in c lu d e   t h e   en d p o in ts ,   b ec au s e   th o s e   p o in ts   u s u all y   do   n o t   h av e   m i n i m u m   g r ad ien t   m a g n i tu d e.   If   th e y   ar e   n o t   s elec ted ,   th e   s k eleto n   b r an ch e s   m a y   be   s h o r te n ed .     2 . 2 . 4.   Sk elet o n   t ra ce   W co n s id er   th cr itical   p o in ts   E u clid ea n   d i s ta n ce   m a tr ix   to   r ep r esen a n   u n d ir ec ted   w ei g h ted   g r ap h .   E ac h   cr itical  p o in t   ch o o s es  t h to p   3   m i n i m u m   E u cl i d ea n   d is ta n ce   w it h   o t h er   p o in t s   in   t h p r o c ess   o f   Kr u s k al ' s   al g o r ith m   [ 2 0 ] .   T h Kr u s k al ' s   al g o r ith m   ad d s   ed g e s   b y   w ei g h asce n d in g   o r d er ,   w h ic h   f o r m s   tr e e   th at  i n clu d es  e v er y   v er tex .   T h to tal  w ei g h o f   all  th ed g e s   in   th tr ee   is   m in i m ized .   B elo w   ar th s tep s   o f   co n n ec ti n g   cr itical  p o in ts   u s i n g   Kr u s k al s   alg o r it h m .     Ass u m e   ( , ) G V E r ep r esen t   g r ap h   w h ic h   f o r m ed   by   cr itical   p o in t s   E u clid ea n   d i s tan ce .   W h er e   V   is   t h e   cr itica l   p o in t s   s e t   of   th e   g r ap h G ,   an d E   is   th e   ed g e   s et   of   t h e   cr itical   p o in ts   E u clid ea n   d is tan ce .   W e   s et   th e   n u m b er   of   cr itica l   p o in ts   is N ,   an d   s o r t   all   th e   ed g e s   by   w eig h t   a s ce n d i n g   o r d er .     1.   Step 1 .   We   d ef in e   a   s et   of   N   i n d ep en d en t   v er tices.   Si n ce   N   cr itical   p o in ts   n ee d   be   co n n e ct ed ,   we   co n s id er   th e   N cr itical   p o in ts   s ep ar atel y .   2.   Step 2 .   We   ch o o s e   t he   ed g e   by   w ei g h t   a s ce n d i n g   o r d er .   If   t h e   ed g e   of   t w o   v er tices   s at is f ies   in   d i f f er en t   v er tex   s e ts ,   we   ad d   th is   ed g e   to   th e   m in i m u m   s p an n i n g   tr ee ’s   ed g e   s et,   a n d   m er g e   t h e   t w o   d if f er en t   v er tex   s e ts   i n to   o n e   v er te x   s et.   If   n o t,   we   w o u ld   co n s id er   t h e   v er tices   of   n e x t   ed g e.     3.   Step 3 .   R ep ea t   s tep 2   u n til   all   t h e   v er tic es   ar e   in   t h e   s a m e   v er t ex   s et.   As   s h o w n   in   Fi g u r e   4   ( a) ,   it   is   an   ex a m p le   to   e x p lai n   o u r   ap p r o ac h   w h ic h   i n cl u d es   7   cr itica l   p o in ts   to   u s e   th e   Kr u s k a l’ s   al g o r ith m .   In   F ig u r e   4   ( b ) ,   th e   E u cl id ea n   d is tan ce   b et w ee n   7   cr itical   p o in ts   r ep r ese n ts   an   u n d ir ec ted   co m p le te   g r ap h .   In   Fi g u r e   4 ( c) ,   it s   th e   m in i m u m   s p an n in g   tr ee   of   7   cr itical   p o in ts   w h ic h   u s e   th e   Kr u s k al ' s   al g o r ith m   to   cr ea te.         A B C D E F G   ( a)   5 9 1 1 8 8 5 6 7 7 1 2 A B C D E F G 1 2 9 1 0   ( b )   5 9 5 6 7 7 A B C D E F G   ( c)         Fig u r e   4 .   ( a)   An   ex a m p le   i n cl u d in g   7   cr itical   p o in ts ,   ( b )   T he   E u clid ea n   d is ta n ce   b et w ee n   7   cr itical   p o in ts ,   ( c)   T h e   m in i m u m   s p an n i n g   tr ee   of   Kr u s k al ' s   al g o r ith m       2 . 3 .     H is t o g ra m   F ea t ure   Co m pa r is on   Ou r   h is to g r a m   f ea t u r e   co m p ar is o n   alg o r ith m   co n s is t s   of   h i s to g r a m   f ea t u r e   ex tr ac tio n   an d   s k eleto n   d is tan ce   co m p u tatio n   al g o r ith m .   T h e   h is to g r a m   f ea t u r e   ex t r ac tio n   alg o r ith m   ad o p ts   th e   r ad ii   of   th e   d is k s   at   s k eleto n   p o in ts   a n d   th e   len g t h s   of   s k ele to n   b r an ch es   to   ex tr ac t   th e   h i s to g r a m   f ea t u r e.   T h e   r ad ii   of   th e   d is k s   an d   len g t h s   of   s k eleto n   b r an c h es   ar e   in v ar ia n t   u n d er   th e   e n v ir o n m en t   of   n o n - r i g id   tr an s f o r m at io n   [ 2 8 ]   w h ic h   w o u ld   h elp   to   g et   h ig h - p r ec is io n   r etr iev a l   r esu lt.   A d d itio n a ll y ,   th e   s k eleto n   d is tan ce   co m p u tatio n   al g o r ith m   co m p ar es   t h e   s i m ilar it y   b et w e en   t w o   s k eleto n s   u s i n g   th e   h is to g r a m   f ea tu r e   m atr ix   of   s k ele to n   en d p o in ts ,   w it h   r elativ el y   les s   q u an tit y   t h a n   s k eleto n   p o in ts   w h ic h   lead s   to   a   lo w er   co m p u tatio n al   co m p le x i t y .     2 . 3 . 1.   H is t o g ra m   F ea t ure   E x t ra ct io n   We   d ef in e   a   2D   d ataset { ( , ) 1 , 2 , . . . , } ii S a b i T  ,   an d   th e ( , ) H S X r ep r esen ts   th e   2D   h is to g r a m   m atr i x   of S ,   w h er e = { ( , ) 0 , 1 , . . . , ; 0 , 1 , . . . , } ij X x y i m j n  is   t h e   h is to g r a m   p ar a m et er ,   w it h   co n s tr ain ts - 1 - 1 , i i i i x x y y  , 1 [ , ] im a x x , 1 [ , ] jn b y y .   Def in e   t h e   2D   h i s to g r a m   m atr ix   ( , ) H S X as   f o llo w :     Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   2252 - 8776   IJ - I C T   Vo l.   8 ,   No .   1 ,   A p r il   2 0 1 9   :   1 12   6   11 12 1 21 22 2 12 ( , ) = n n m m mn h h h h h h H S X h h h         ( 6 )     w h er e   ij h r ep r esen ts   t h e   n u m b e r   of   S d ataset   ele m e n ts   d is tr ib u ti n g   in   t h e   r ec tan g u lar   ar e a   ( 1 , ii xx , 1 , jj yy   ) ,   , ij xy u s u all y   is   ar ith m etic   s eq u e n ce   or   g eo m etr ic   s eq u e n ce .     As   s h o w n   in   Fi g u r e   5,   th e   p o i n t   Q   r ep r esen ts   th e   s k eleto n   ce n tr e   w h ic h   is   th e   s k eleto n   p o in t   w it h   r ad iu s   of   t h e   m a x i m a l   d is k ,   a n d ( 1 , 2 , . . , ) i v i T is   th e   s et   of   s k eleto n   p o in t s .   T h en   we   u s e   f ea tu r e   d ata s et   Q P   to   r ep lace   th e   ab o v e   2D   d atase t S :       { ( ) ( ) ( ( , ) , ( ) ) } ( 1 , 2 , . . . , ) Q Q i Q i i i P p v p v s k e Q v R v i T   ( 7 )     w h er e ( , ) i s k e Q v   is   th e   s h o r tes t   p ath   f r o m   s k eleto n   ce n tr e   Q   to   s k eleto n   p o in t i v .   () i Rv r ep r esen ts   t h e   r ad i i   of   d is k s   of   s k ele to n   p o in t i v .   i v   is   th e   co r r esp o n d in g   p o in t   of   i v at   th e   co n to u r . () Qi pv r ep r esen ts   th e   r elat iv e   d is tan ce   f r o m   s k eleto n   ce n tr e Q   to   co n to u r   p o in t   i v .           Fig u r e   5.   T h e   r ad iu s   of   th e   m a x i m al   d is k   an d   co n to u r   p o in t       Fo r   th e   2D   h is to g r a m   f ea t u r e   m atr i x ( , ) Q H P X ,   X is   th e   co r r esp o n d in g   h i s to g r a m   p ar a m eter .       { ( , ) , } ( 0 , 1 , . . . , ; 0 , 1 , . . . , ) i i j i j X x y x l y r j i m j n   ( 8 )     T h e   d eter m i n atio n s   of   p ar a m e ter s   , , , l r m n ar e   u n d er   th e   co n s tr ai nt   of   r ad ii   of   d is k s   an d   t h e   len g t h s   of   s k e leto n   b r an c h es.     As   s h o w n   in   Fi g u r e   6,   we   co n s id er   th e   en d p o in t   A   as   th e   b a s e   r esear ch   p o in t,   t h e   d ef i n itio n   of   A P is   s i m ilar   to Q P .   T h e   ( , ) A H P X   r ep r esen ts   t h e   h is to g r a m   f ea t u r e   m atr i x .           Fig u r e   6.   T h e   s h o r test   p ath   of   s k eleto n   en d p o in t s   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - I C T     I SS N:   2252 - 8776       A   n o ve l   s ke tch - b a s ed   3D   mo d el   r etri ev a l   a p p r o a ch   b a s ed   on   s ke leto n   ( Jin g   Zh a n g )   7   T h e   Fig u r e   7   s h o w s   th e   2D   h i s to g r a m   of   s k eleto n   en d p o in t A   g en er ated   by   t h e   le n g th   of   a ll   cu r v e s   d is tr ib u ti n g   in   ea c h   r ec ta n g u l ar   ar ea .   T h e   ( , ) i s k e A v   is   th e   ab s cis s a   wh ich   r ep r esen t s   t h e   s h o r tes t   p a th   f r o m   th e   e n d p o in t   A   to   s k e leto n   p o i n t i v . T h e   () i Rv is   th e   o r d in ate   w h ic h   r ep r esen ts   t h e   r ad iu s   of   d i s k   of   s k e leto n   p o in t i v .           Fig u r e   7 .   T h e   2D   h is to g r a m   of   s k eleto n   en d p o in t A       2 . 3 . 2.   Sk elet o n   Di s t a nce   Co m p uta t io n   We   d ef in e   t w o   s k eleto n s   12 = ( v , v , . . . , v ) m G an d 12 = ( v , v , . . . , v ) n G ,   w h er e   v i an d v j   r ep r esen t   en d p o in ts   f r o m   d i f f er en t   s k eleto n s .   W it h   t h e   h is to g r a m   f ea t u r e   m a tr ix   () i Hk an d   () j Hk of   s k el eto n   en d p o in ts v i an d v j ,   we   g et   t h e   d is ta n ce   b et w ee n   2D   h i s to g r a m   of   t w o   s k eleto n   en d p o in ts :       1 ( v , v ) ( ) ( ) mn i j k i j k d w H k H k     ( 9 )     w h er e       1 ( ) + ( ) co s ( ) 2 = ( ) + ( ) co s ( ) 2 ij k mn ij k H k H k Z w H k H k Z   ( 1 0 )     2 m ax ( ( ) + ( )) ij k Z H k H k   ( 1 1 )     s atis f y in g ( ) + ( ) 1 ij H k H k Z .   W h en   we   co m p ar e   t h e   s i m ilar it y   b et w ee n   t wo   s k e leto n s ,   ch o o s e   o n e   of   th e   s k e l eto n s   as   a   b en ch m ar k ,   a n d   co m p u te   all   t h e   d is ta n ce   w it h   th e   o t h er   s k el eto n   en d p o in ts .     1 1 1 2 1 2 1 2 2 2 12 ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) n n m m m n d v v d v v d v v d v v d v v d v v D G G d v v d v v d v v         ( 1 2 )     Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   2252 - 8776   IJ - I C T   Vo l.   8 ,   No .   1 ,   A p r il   2 0 1 9   :   1 12   8   In   th e   all   e n d p o in ts   d is tan c e   m atr i x   ( , ) D G G ,   we   s elec t   t h e   m in i m u m   v al u e   of   each   lin e   12 m i n ( , ) m i n ( , ) m i n ( , ) ( 1 , 2 , . . . , ) j j m j d v v d v v d v v j n to   co m p u te   t h e   d is ta n ce   b et w ee n   t w o   s k eleto n s .   T h en   t h e   d is ta n ce   of   t w o   s k eleto n s   is   e x p r ess ed   as :     1 d i s ( , ) m i n ( , ) , 1 , 2 , . . . , m ij j i G G d v v j n     ( 1 3 )       3.   RE SU L T S   AND   AN AL Y SI S   We   i m p le m e n t   o u r   s k etc h - b as ed   3D   m o d el   r etr iev al   m et h o d   in   C ++   u n d er   W in d o w s .   As   s h o w n   in   Fig u r e   8,   T h e   lef t   s id e   of   t h e   i n ter f ac e   is   a   ca n v a s   f o r   s k e tch in g   t h e   m o d el.   T h e   u s er   ca n   e r ase   an d   m o d if y   if   th e y   do   n o t   s ati s f y   w i th   t h e   d r a w n   s k etc h .   T h e   r ig h t   s id e   is   d is p la y i n g   p ag e   f o r   th e   r etr iev ed   3D   m o d els   w it h   a   r elev an t   J P E G   i m ag e.   T h e   u s er   can   click   t h e   b lu e   b u tto n   to   d o w n lo ad   th e   co r r esp o n d in g   3D   m o d el.       T h e   s y s te m   co n s is ts   of   o f f - li n e   f ea t u r e   ex tr ac tio n   a n d   on - lin e   r etr iev al   p r o ce s s es.   In   th e   o f f - li n e   p r o ce s s ,   th e   f ea t u r es   ar e   e x tr a cted   in   a   PC   w it h   a   P en ti u m   III   8 0 0 MH z   C P U   an d   GeFo r ce 2   MX   v id eo   ca r d .   In   th e   on - l in e   p r o ce s s ,   t h e   r etr ie v al   s y s te m   co n s is ts   by   a   PC   w it h   an   I n tel   Xeo n   C P U   E 5 5 2 0 @ 2 . 2 7   GHz   an d   1 2 . 0   GB   of   R A M.   Ou r   s k etc h - b a s ed   3D   m o d el   r etr iev al   b en ch m ar k   is   b u ilt   on   th e   well - k n o w n   Natio n al   T aiw a n   U n iv er s it y ( NT U)   [ 2 9 ]   d atab ase   an d   th e   latest   co llect io n   of   h u m an   s k etc h e s .             Fig u r e   8.   Ou r   s k etc h - b ased   3D   m o d el   r etr iev al   s y s te m       3. 1 .     Sk elet o n   E x t ra ct io n   by   ASSM   T h e   p r o p o s ed   A SS M   m et h o d   is   ab le   to   co m p u te   s k ele to n   b r a n ch es   in   all   s i g n i f ica n t   v is u al   p ar ts .   Fig u r e   9   s h o w s   lea f   s k eleto n   e x tr ac tio n   p r o ce s s   by   ASSM   ap p r o ac h .   As   s h o w n   in   Fi g u r e   9 ( a) ,   it’ s   t h e   o r ig i n al   leaf   i m a g e.   In   Fi g u r e   9 ( b ) ,   s h o w s   t h e   co m p u tatio n   of   th e   S SM   v alu e   a f ter   is o tr o p ic   d if f u s io n   on   th e   g r ad ie n t   v ec to r   f ield .   In   Fig u r e   9 ( c) ,   t h e   SSM   v a lu e   is   r ef in ed   by   t h e   n o n - m a x i m al   s u p p r ess io n   alg o r ith m .   In   Fi g u r e   9 ( d ) ,   th e   cr itical   p o in t s   s et   e x tr ac ted   f r o m   th e   SS M   r ef in ed   v al u e.   In   Fi g u r e   9 ( e) ,   s h o w s   th e   f in al   s k eleto n   co n n ec ted   by   Kr u s k al ' s   al g o r ith m .         ( a)     ( b )     ( c)     ( d )     ( e)             Fig u r e   9 .   I llu s tr atio n   of   leaf   s k eleto n   ex tr ac tio n   p r o ce s s   by   ASSM   ap p r o ac h   ( a)   th e   o r ig in al   lea f   i m ag e ,   ( b )   s h o w s   t h e   SS M   v al u e,   ( c)   th e   SSM   v al u e   is   r ef i n ed   by   th e   non - m a x i m al   s u p p r ess io n   alg o r it h m ,   ( d )   th e   cr itical   p o in t   s et   ex tr ac ted   f r o m   ( c) ,   ( e)   th e   f in a l   s k e leto n   co n n ec ted   by   Kr u s k al ' s   al g o r ith m   Evaluation Warning : The document was created with Spire.PDF for Python.
IJ - I C T     I SS N:   2252 - 8776       A   n o ve l   s ke tch - b a s ed   3D   mo d el   r etri ev a l   a p p r o a ch   b a s ed   on   s ke leto n   ( Jin g   Zh a n g )   9   3. 2 .     Sk elet o n   M a t ching   B a s e d   on   H is t o g ra m   F ea t ure   In   o r d er   to   s h o w   t h e   ef f ec ti v en es s   of   t h e   p r o p o s ed   h is to g r a m   f ea t u r e   co m p ar is o n   alg o r ith m ,   we   test ed   th r ee   s k e leto n   m atc h i ng   e x p er i m e n ts   b et w ee n   s k e tch   an d   2D   v ie w   of   3D   m o d el.   F ig u r e   1 0   s h o w s   th e   co r r esp o n d en ce   b et w ee n   a   cat   an d   a n o th er   d e f o r m ed   cat . I t   d e m o n s tr ates   t h at   o u r   h i s to g r a m   f ea t u r e   co m p ar is o n   alg o r it h m   ca n   r ea lize   th e   s k e leto n   m atch in g   of   d ef o r m ed   o b j ec t .   Fig u r e   1 1   s h o w s   th e   co r r esp o n d en ce   b et w ee n   t h e   p er s o n s   w i th   d if f er e n t   n u m b er s   of   ar m s .   It   ill u s tr ate s   t h at   o u r   h i s to g r a m   f ea t u r e   co m p ar is o n   al g o r ith m   w o r k s   co r r ec tl y   if   o b j ec t   p ar ts   a r e   s ig n i f ica n tl y   al ter ed .   Fig u r e   1 2   s h o w s   th e   co r r esp o n d en ce   b et w ee n   an   e lep h an t   a nd   an o t h er   elep h a n t   w it h   a   s tick .   It   d e m o n s tr ates   th at   o u r   m atc h in g   p r o ce s s   h as   s tr o n g   p er f o r m a n c e   w h en   t h e   co m p ar ed   o b j ec ts   h av e   t h e   r ed u n d an t   p ar ts .                   Fig u r e   1 0.   T h e   co r r esp o n d en ce   b et w ee n   a   cat   an d   an o t h er   d ef o r m ed   cat   Fig u r e   1 1.   T h e   co r r esp o n d en ce   b et w ee n   th e   p er s o n s   w it h   d if f er e n t   n u m b er s   of   ar m s   Fig u r e   12.   T h e   co r r esp o n d en ce   b et w ee n   an   elep h a n t   a n d   an o t h er   elep h an t   w i th   a   s tick       3. 3 .     Co m pa ri s o n   w it h   o t her   a pp ro a ches     We   co n s id er ed   class ical   P r ec i s io n   an d   R ec all   m etr ics   av er a g ed   o v er   th e   s et   of   p r o ce s s ed   q u er ies [ 3 0 ]   to   m ea s u r e   th e   r etr ie v al   e f f ec t i v en e s s .   R ec all   m ea s u r es   t h e   a b ilit y   of   th e   s y s te m   to   r etr iev e   all   m o d els   t h at   ar e   r elev an t.   P r ec is io n   m ea s u r es   t h at   t h e   ab ilit y   of   t h e   s y s te m   to   r etr i ev e   o n l y   m o d els   t h at   ar e   r elev an t.   T h e y   ar e   d ef in ed   as:       ( 1 4 )       ( 1 5 )     T o   h av co m p r eh e n s iv e v alu atio n   o f   o u r   al g o r ith m ,   we  f u r t h er   p r o v id th r es u lt s   f o r   o th er   p er f o r m a n ce   m etr ic s   i n clu d i n g   Nea r est   Nei g h b o u r   ( NN) ,   F ir s T ier   ( FT) ,   Seco n d   T ier   ( S T ) ,   E - m ea s u r ( E ) ,   Dis co u n ted   C u m u lati v Gain   ( DC G)   an d   Av er ag P r ec is io n   ( A P ) .   T h m ea n i n g   o f   th ab o v p er f o r m a n ce   m etr ics   is   a s   f o llo w s   [ 3 0 ] .   N m ea s u r e s   t h p er ce n ta g o f   th c lo s est  m atc h e s   t h at  ar r elev an m o d el s .   FT   r ep r esen ts   h o w   m u ch   p er ce n ta g o f   clas s   h a s   b ee n   r etr iev e d   am o n g   t h to p   C   lis t,  w h er C   is   t h ca r d in alit y   o f   th r elev a n t c la s s   o f   t h q u e r y   s k e tch .   I t d ef i n es a s :     ( 1 ) r e l e v a n t c o r r e c t l y r e t r i e v e d FT t o p C r e t r i e v e d   (1 6 )     ST   r e p r esen ts   h o w   m u c h   p er ce n tag e   of   a   class   h as   b ee n   r etr iev ed   a m o n g   th e   to p   2 ( 1 ) C   lis t ,   w h er e   C   h as   t h e   s a m e   m ea n i n g   w it h   FT   m e tr ic .     2 ( 1 ) r e l e v a n t c o r r e c t l y r e t r i e v e d ST t o p C r e t r i e v e d   (1 7 )     E   is   u s ed   to   m ea s u r e   t h e   p er f o r m a n ce   of   t h e   r etr ie v al   r es u l ts   w it h   a   f ix ed   le n g t h ,   e. g .   t h e   f ir s t   32   m o d el s .   It   co m b in e s   b o th   th e   P r ec is io n   P   an d   R ec all   R :   r e l e v a n t c o r r e c t l y r e t r i e v e d R e c a l l a l l r e l e v a n t r e l e v a n t c o r r e c t l y r e t r i e v e d P r e c i e s a l l r e t r i e v e d Evaluation Warning : The document was created with Spire.PDF for Python.
            I SS N :   2252 - 8776   IJ - I C T   Vo l.   8 ,   No .   1 ,   A p r il   2 0 1 9   :   1 12   10   2 11 E PR      ( 1 8 )     DC G   is   d e f in ed   as   t h e   s u m m e d   w ei g h ted   v a lu e   r elate d   to   th e   p o s itio n s   of   t h e   r elev a n t   m o d els.       1 2 2 lo g P k k w D CG w k    ( 1 9 )     w h er e k w d en o te   w ei g h ted   v al ue   of   each   r etr iev al   r es u lt ,   a n d   k d en o tes   t h e   in d e x   of   r etr iev a l   r esu lt .   P is   th e   n u m b er   of   r etr iev al   r es u lt.   A P   ca n   b co m p u ted   b y   co u n t in g   t h to tal  ar ea   u n d er   t h P r ec is io n - R ec a ll  c u r v e.   T h h ig h er   P r ec is io n - R ec all  c u r v w o u ld   g et  a   b etter   A P   v al u e.   W co m p ar o u r   ap p r o ac h   w i th   o th er   f o u r   lead in g   s k etc h - b ased   3 m o d el  r etr iev al  alg o r it h m s ,   w h ich   u til ize  s k eleto n   c h ar ac ter is tic s   as  t h f ea tu r es  to   d escr ib th o b j ec s h ap e.   S u n d ar   et  al.   [ 3 1 ]   ar th m o s t   r ep r esen tat iv e   in   t h f ield   o f   s k eleto n   b ased   s h ap e   m atc h in g   a n d   r etr ie v al.   T h e y   u tili ze d   t h th i n n i n g   alg o r it h m   a n d   cl u s ter i n g   al g o r ith m   wh ich   h e lp   les s en   th e   ef f ec o f   m an y   s m a ll  p er tu r b atio n s   o n   t h s u r f ac a n d   r ed u ce   t h n u m b er   o f   n o d es   n ec ess ar y   f o r   s k ele tal   g r ap h   co n s tr u ctio n .   L ei   H   e al.   [ 3 2 ]   u s ed   th i n n i n g   al g o r ith m   o n   th e   s il h o u e tte  i m ag es   to   ex tr ac t h co r r esp o n d in g   s k eleto n s   an d   u tili ze d   s k ele to n   p r u n in g   m et h o d .   L in   et  al.   [ 3 3 ]   g o th s k e leto n   o f   3 m o d el   th r o u g h   s k e leto n   e x tr ac tio n   al g o r ith m   b ased   o n   m e s h   s i m p li f icatio n   an d   m es h   co n tr ac tio n .   Sirin   Y   et  al.   [ 3 4 ]   s tar ted   b y   d r a w i n g   cir cles   o f   i n cr ea s i n g   r ad iu s   ar o u n d   s k elet o n s ,   w h ic h   lead   to   ea ch   s k elet o n   co r r esp o n d ed   to   th ce n tr o f   m ax i m a ll y   i n s c r ib ed   cir cle. W illu s tr ate  3 m o d el s   o f   ca r ,   la m p ,   p la n a n d   ch air   i n   t h F ig u r e   1 3   an d   th av er ag co m p ar is o n   r esu lt is   s h o w n   in   T ab le  1 .           Fig u r e   13.   E x a m p les   of   s k etc h - b ased   r etr iev al   r es u lts       T ab le   1.   Me tr ics   f o r   th e   P er f o r m an ce   C o m p ar is o n   b et w ee n   Ou r   A p p r o ac h   a nd   Oth er   A p p r o ac h es   A p p r o a c h e s   NN   FT   ST   E   D C G   AP   O u r   A p p r o a c h   0 . 3 8 7   0 . 3 1 6   0 . 3 8 3   0 . 3 7 4   0 . 5 8 9   0 . 3 9 4   L e i   H’ s   A p p r o a c h   0 . 3 6 5   0 . 2 6 8   0 . 3 3 1   0 . 3 5 2   0 . 5 4 1   0 . 3 3 5   S u n d a r   H’s   A p p r o a c h   0 . 3 4 7   0 . 2 5 1   0 . 3 2 7   0 . 3 2 1   0 . 5 3 3   0 . 3 2 6   L i n   S’s   A p p r o a c h   0 . 2 8 5   0 . 2 3 6   0 . 2 9 4   0 . 2 6 8   0 . 4 9 1   0 . 2 7 8   S i r i n   Y’s   A p p r o a c h   0 . 2 1 1   0 . 2 0 8   0 . 2 4 3   0 . 2 0 2   0 . 4 6 6   0 . 2 0 4       It   is   o b v io u s   th at   o u r   ap p r o ac h   o u tp er f o r m s   o th er   lea d in g   s k etc h - b a s ed   3D   m o d e l   r etr iev al   ap p r o ac h es.   T h e   ap p r o ac h es   of   S u n d ar   H   et   al   [ 3 1 ]     an d   L ei   H   et   al   [ 3 2 ]     u tili ze d   t h e   th in n i n g   a lg o r it h m   w h ic h   is   q u ite   s e n s iti v e   to   n o is e   an d   can   ac h ie v e   lar g e   a m o u n t   of   ca lcu latio n .   L i n   S   et   al   [ 3 3 ]   u s e d   th e   f r o n t   v ie w   of   Evaluation Warning : The document was created with Spire.PDF for Python.