with recent advances in telemedicine technology , it is now possible to perform closed - abdomen surgery on a moving organ of a remote patient using robotic instrument to minimize patient trauma and certain side effects . for robotic assisted surgery ,
dexterity is enhanced by microprocessor controlled mechanical wrists , which allow motion scaling for reducing gross hand movements and the performance of microscale tasks that are otherwise not possible .
so far , two commercially available master - slave manipulator devices are specifically designed for robotic cardiac surgery .
both systems improve the ergonomics of laparoscopic surgery and provide high dexterity , precision , and 3d visualization of the operating field .
one of the significant challenges of the in - vivo surgery is the destabilization introduced by respiratory motion , thus severely affecting precise instrument - tissue interactions and the execution of complex grafts .
the other one is the precise localization of the tumor boundary , while most of the automatic image - guided algorithms yield incomplete , discontinuous , imprecise detection results . and the two above challenges always trigger each other and form a chick - egg problem .
thus in this paper , we intend to solve this problem by a novel high - level entities formation method .
many existing methods have been developed to extract structural features [ 24 ] but , at the same time , included some errors ( incomplete detection leading to discontinuities , imprecise localization of contours ) that increased the difficulties of the further processing like tracking or 3d reconstruction .
one way to overcome these difficulties has been , these last years , to incorporate some interactivity .
the contour detection makes use of an interactive procedure for the first image , and is then used as initial model of a snake to extract the contours in the other images of the sequence .
thus in , for each model curve , control points were interactively defined as the anchor points of an active contour modeling .
initial control points were interactively selected and the 2d contours represented as a b - spline .
the active contour model was then applied to fit each curves of the selected contours . in , the segmentation of the first image made use of an interactive tool based on the mouse moving .
the operator selected an initial point inside the image , and uncoiled a thread with the mouse , roughly following the boundary .
an optimal path research procedure based on a dynamic programming algorithm and using a maximum multiscale response map for constraining the path search was performed between the initial point and the current position of the mouse .
the contour was thus piecewise built , by successively moving the mouse along the boundary .  
we look for improving the automatic segmentation result in each image of the sequence by reconstituting high level entities , that is , the shape of tumors , in order to facilitate the tracking and localization of the tumor .
a first intraimage analysis was previously performed to detect contours in each image of the sequence .
it aimed at forming correspondences from previously extracted contours by using a string matching process .
these correspondences will then be used to spatially prolong the segments in order to reconstitute the boundaries and get a symbolic description of the structures in the 2d space .  
we present in this paper the temporal matching method , which is based on an attributed string matching technique .
attributed string matching techniques have been broadly applied in pattern recognition with the aim to look for specific shapes , comparing unknown figures occurring in the input image with a set of prototypic models in a classification purpose or emphasizing  landmarks  subsets common to a set of features .
more recently , interest was found in image analysis in particular in shape recognition [ 79 ] and registration in the frame , for instance , of the 3d reconstruction from stereo views .
let sn   be an arbitrary string of length ln = |sn| defined on a discrete alphabet .   we denote   sn the ith symbol of sn for i  { 1  |sn| }  such as sn = snsn  sn  sn .
an edit distance , based on edit operations ( insertion , deletion , and substitution of symbols ) , is then defined as the minimum cost operation sequence over all possible sequences of operations   o   ( o = o1o2  om ) with ok equals to one of the three above cited edit operations .
it makes use of a cost matrix , which specifies the costs (ok ) of individual elementary operations for all combination of symbols .
the total cost of the transformation is then calculated by summing up the elementary costs applied to each operation in the sequence .
the distance associated with the minimum cost operation sequence is given by the relation:(1)(snln , splp)={mino(sn , sp(o))o : snlnsplp},with sn , sp(o ) = v = 1(ov ) .
the classical dynamic programming , initially designed by wagner & fisher , has largely been used to calculate the edit distance .  
the process goes through the edit matrix computation d(i , j ) ,   1  i  ln ,   1  j  lp using the following recursive relation:(2)d(i , j)=min  { ( d(i1,j1)+(snispj ) ) ,  ( d(i1,j)+(sni ) ) ,  ( d(i , j1)+(spj))},where  denote the empty symbol and (sn      sp ) ,   (  sp ) ,   (sn   ) , respectively , characterize the substitution , insertion , and deletion costs .
the least cost operation sequence is obtained through a search of a least cost path in the graph .
the result is a sequence of ordered pairs of positions in sn and sp corresponding to substitutions .   with a least - cost trace from sn to sp ,   t(sn , sp )
is hence defined as the set of ordered pairs of integer ( i , j ) corresponding to the indices of the paired symbols between the two strings .
let lt , n and lt+d , m two lines to be matched with ( t , t + d ) characterizing the image number in the sequence and ( n , m ) the line numbers in each image
. elements of lt , n and lt+d , m were , respectively , noted pt , n and pt + d , m , i and j being the element indexes for each line .
four attributes were associated to each pixel pt , n : the intensity i(pt , n ) , the euclidean location dt , ni , the tangent tt , ni , and the local curvature t , n . each line was thus expressed as a sequence st , n of symbols ( ln being the length of the string ) , each symbol corresponding to a set of attributes , we formalized as a vector st , ni=(i(pt , ni),dt , ni , tt , ni,t , ni ) . we designed a multiparametric cost function between sets of two vectors ( st , n , st + d , m ) based on perceptual criteria :   parallelism , proximity , curvature , and intensity similarity .
deletion and insertion costs were set to 0.5 , while the substitution cost , defined by the function f ( st , n , st + d , m ) , was expressed on the [ 0 , 1 ] interval :  
 ( 3)f(st , ni , st+d , mj)=fi(i(pt , ni),i(pt+d , mj))+fp(tt , ni , tt+d , mj )  + f(t , ni,t+d , mj)+fd(pt , ni , pt+d , mj),where  ,  ,  ,  were weighting coefficients such that  +  +  +  = 1 .  
each function was defined as an exponential of the form f ( , ) = e ,   where max characterized the maximum permitted deviation between two symbols for a given criterion and  , the difference measured between the two considered symbols .  
max definition depends on the limit , we set up for each parameter deviation so that   0  f ( , )  1 , value 0 depicting a good shape similarity .
this stage aimed at establishing the temporal correspondences between segments of contours along the sequence .
the attributed string matching was applied on sets of pairewise images , all possible temporal associations being taken into consideration .   for each contours lt , n   in image it ,   a contours neighborhood v(t , t+d),n was built in image it+d such as(4)v(t , t+d),n={lt+d , mm=1nn ,  distance(lt , n , lt+d , m)<dmax},where dmax sets the upper limit for the contour displacement between two instants t and t + d and nn denotes the cardinal of v(t , t+d),n .
all the possible combinations of contours , inside this neighborhood , were then considered for the pairing . with the segment running direction for the matching being
not prior known , each extremity of a segment was numbered and two runs were considered according to these extremities .
two associations were then considered among the four possible combinations { ( lt , n , lt + d , m ) , ( lt , n , lt + d , m ) } ,    exponent 1 and 2 representing the extremity number . attributed strings ( st , n , st + d , m ) were then assigned to each two lines ( lt , n , lt+d , m ) .
the attributed string matching process was applied for each two pairs of lines and the right running direction corresponded to the best association among the two , when choosing the minimal edit distance as selection criterion . because multiple assignments can occur in some situations ( when several contours are close to each other or when spurious segments are present ) , two criteria were thus defined in order to keep only the one - to - one matchinga threshold on the normalized edit distance aimed to remove all the inconsistent associations : matched lines whose edit distance was greater than this threshold were cancelled.an overlapping criterion was then considered to remove redundant associations .
these associations are considered as right if there is no overlapping between the matched sets .   on the contrary
thus when several candidate curves were associated to the same curve with some overlapping between these associations , the matched lines were sorted out on the edit distance value and the established trace between the paired symbols .
considering for each line lt , n , the matched line list by decreasing edit distance values , if the trace between the matched pixels intersected a curve , the pair of lines having the highest edit distance value was removed .
a threshold on the normalized edit distance aimed to remove all the inconsistent associations : matched lines whose edit distance was greater than this threshold were cancelled .
these associations are considered as right if there is no overlapping between the matched sets .  
thus when several candidate curves were associated to the same curve with some overlapping between these associations , the matched lines were sorted out on the edit distance value and the established trace between the paired symbols . considering for each line lt , n
, the matched line list by decreasing edit distance values , if the trace between the matched pixels intersected a curve , the pair of lines having the highest edit distance value was removed .
the matching procedure was applied to endoscopic images acquired from standard optical colonoscope ( from our collaborator : stanford university ) , and the preliminary results can be found in figure 1 .
whatever the detection operator and the decision rule , it must be accepted that no exact result can be derived .
this statement , which applies to edge detection too , was the first motivation of this work . in a first stage , edges were grouped using spatial properties to construct coherent pieces .
the next stage , that is , the temporal matching , takes advantage of the motion correspondence to solve spatial ambiguities and improve the segmentation results in presence of occlusion or discontinuities on the images .
it was pairewise applied on the contour and allows at the same time to get a first approximation of the motion between the structures .
the parameters setting resulted from a learning stage , which allowed studying the behavior of the algorithm according to the parameters choice and combination .  
this study showed that the results were not sensitive to the choice of the parameters .
the best result was obtained with the following setting :  = 20% ,    = 15% ,    = 30% ,    = 35% ,   imax = 20 ( maximum intensity difference ) ,   max = /4 ( angular difference between the tangents ) , max = 0.5 ( maximum curvature with || = |t , n  t + d , m|/8 ) , dmax = 30 ( maximum distance ) .  
for these parameters , we computed the mean cross - correlation , the mean distance , and the mean normalized edit distance over the set of matched lines .
the branches formation was then performed over the sequence , based on the matching process results .
in this paper , we made use of an attributed string matching technique for the formation of high - level entities like boundaries of tumors in endoscopic images for remote - controlled robotic surgery .
the advantage of the method is that few parameters have to be set to track the contours over time .
the established temporal relationships were exploited to spatially locate the contours and reconstitute the tumor boundaries .
these results will be further used to complete the tumor boundaries that were previously performed on each image of the sequence .
this work represents a contribution to the difficult problem of the tumor tracking and localization in robot - assisted minimal invasive surgery .
 temporal matching is applied in the frame of the formation of high - level entities in remote - controlled robotic surgery . 
 the objective is to track tumor boundaries over time to improve the segmentation stage in each image of the sequence to facilitate the tracking and localization of the tumor . 
 it makes use of an attributed string matching technique to find the correspondence between tumor boundaries over time . 
 relationships are then exploited to reconstitute the tumor boundaries and remove the inconsistencies coming from the detection errors . 
 input data are free form shapes of different length representing the tumor boundary , extracted at a previous stage . 
1. Introduction
2. Temporal Matching
3. Result and Discussion
4. Conclusion