http:^^www.cs.cornell.edu^info^people^barber^potrivl^potrivl.html

来自「This data set contains WWW-pages collect」· HTML 代码 · 共 677 行 · 第 1/3 页

image operations.  Given an image sequence and a model to look for, the job of the RivL 
Object Tracker is to determine where an object model resides in a given image, for each 
frame in a sequence of images.  The image sequence can be represented by any RivL 
datatype (e.g. MPEG, continuous JPEG).  The model is a string of points, which is a 
bounding-box specifying the location of the object in a given image.<p>  

The Tracker operates as follows:  it looks at adjacent images in a sequence, which I will 
define here as <b>Prev</b> (for previous) and <b>Next</b>.  
We want to determine where the object 
model went from <i>Prev</i> to Next.  For every adjacent set of images, the Tracker performs the 
following sequence of operations:  it first smooths (using the RivL <i>im_smooth</i> operation) 
and then edge-detects (using the <i>im_canny</i> operator, which is a Canny Edge-Detector 
[<!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><!WA48><a href="#3ref">3</a>]) 
<i>Next</i>.  <i>Prev</i> was smoothed and edge-detected in the previous iteration.   
The <i>im_search</i> 
command is then invoked, which actually performs the object tracking.  The <i>im_search</i> 
command extracts the actual "object to be tracked" from <i>Prev</i> specified by model.  
<i>im_search</i> then searches for an instance of the object in <i>Next</i>.  
When <i>im_search</i> 
completes, it returns a new bounding-box model, which corresponds to the location of the 
tracked object in <i>Next</i>.   By modifying the RivL script, we can generate an output 
sequence of images that illustrates the object being tracked.<p>  

<center><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><!WA49><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/t1.jpg"><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><!WA50><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/t2.jpg"><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><!WA51><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/t3.jpg"></center>
<p>

The sequence of images above illustrates the output of RivL's Object Tracker.  
The tracked object appears highlighted, while rest of the image is dimmed.<p>

<a name="4.2">
<!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><!WA52><a href="#home">Go Back</a>
<h3>4.2  The Algorithm behind <i>im_search</i></h3>

The search itself is based on the Hausdorff distance [<!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><!WA53><a href="#4ref">4</a>], 
which is a measure of the 
similarity between two different sets of points.  The <i>im_search</i> command compares the 
object with different locations inside Next.  If we find a Hausdorff distance D, and it is 
within some threshold value V, then a match is found.  If more than one D is found within 
V, then we pick the match with the smallest Di, corresponding to the best possible match.<p>

The search utilizes a multi-resolution approach [<!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><!WA54><a href="#5ref">5</a>].
  The image <i>Next</i> is evenly divided into 
separate regions.  Each region is then pre-searched, to determine if there is "anything 
interesting" in that region.  By interesting, we mean that there is a substantial clustering of 
edges, again within some other threshold U.  For each region that was determined 
interesting, it is then recursively sub-divided and pre-searched.<p>  

<center><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><!WA55><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sld003.gif"></center>
<p>

By recursively dividing up the image and locating only "interesting" regions, the overall 
search space is decreased   The Hausdorff distance comparisons between the model and 
the region of interests can then proceed only on the reduced search space.<p>

<a name="4.3">
<!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><!WA56><a href="#home">Go Back</a>
<h3>4.3  Parallelizing <i>im_search</i></h3>

The multi-resolution approach lends itself to parallelization.  At each level of the 
resolution, separate independent regions must be pre-searched.  These pre-searches can be 
processed in parallel in a hungry-puppy fashion.  When the pre-search recursively moves 
down to a lower level, each region is again sub-divided and pre-searched.  These searches 
can also be done in parallel.  And so forth.<p>     

<a name="4.4">
<!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><!WA57><a href="#home">Go Back</a>
<h3>4.4  Problems with <i>im_search</i> and Generic Parallel RivL</h3>

As we mentioned in the introduction, the generic parallel scheme described earlier works 
for the majority of the image operations in RivL.  Unfortunately, this is not the case for 
<i>im_search</i>.<p>  

In generic parallel RivL, the output write region is sub-divided based on the process's 
logical ID#, and the total number of processes willing to work.  In this paradigm, each 
process is responsible for its own portion of the output region.  Computation of each 
output region does not rely upon the output of any other regions. In generic RivL, there is 
no communication between different processes for a given traversal of the RivL graph.  
Each process is independent of one another.<p>

Unlike the more general operations, the output region of <i>im_search</i> cannot simply be 
sub-divided into different regions and computed independently of one another.  This is true for 
the reason that an object being tracked may overlap several write regions.  Since there is 
no communication between processes for a given traversal of the RivL graph, <i>im_search</i> 
will not work using Generic RivL.<p>
<!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><!WA58><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p>

<a name="5.0">
<!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><!WA59><a href="#home">Go Back</a>
<h2>5.0  Parallelizing <i>im_search</i> in RivL</h2>

<a name="5.1">
<!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><!WA60><a href="#home">Go Back</a>
<h3>5.1  A Course-Grain Parallelization Scheme</h3>

In Section 4.3 we introduced a method for parallelizing <i>im_search</i> based on the 
multi-resolution approach for object tracking.  This is exactly the scheme that has been 
implemented in RivL.  Unfortunately, this scheme is currently incompatible with fine-grain 
generic parallel RivL for the reasons described above.  Rather, parallel <i>im_search</i> 
was implemented over the original sequential version of RivL.<p>  

The alternative parallelization scheme works as follows:  RivL is initially invoked on only 
one process, the master Process.  The master constructs the RivL graph, and performs the 
right-to-left traversal, all by itself. <i>im_search</i>, like any other image operation, is 
constructed as a RivL node.  When the image sequence to be tracked is loaded and ready, 
each image makes its left-to-right traversal through the RivL graph.  When the data 
encounters the <i>im_search</i> node, the following sequence of events happens:<p>

<ul>
<li>RivL spawns n slave processes as an extension of <i>im_search</i><p> 
<li>The master process organizes the multi-resolution pre-searches.  It maintains a high 
priority queue, and a low priority queue.  The high-priority queue contains a list of 
pre-searches "to-do" on the sub-divided image.  
Each slave process pulls these jobs from the queue, 
and performs the pre-search on each job.  If an interesting region is found, the Slave 
process will further sub-divide that region into smaller regions, and place each 
sub-divided region as a job "to-do" onto the low priority queue.<p>  

<center><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><!WA61><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sld004.gif"></center>
<p><p>

<ul>
<li>The master can only write to the high-priority queue, and read from the low-priority 
queue.<p>
<li>The slave can only read from the high-priority queue, and write to the low-priority
queue.<p>
</ul>
</ul>
<p>

Essentially, each slave process performs the pre-searches in a hungry-puppy fashion, to 
narrow down the scope of the overall search region.  The master process is responsible for 
maintaining the queues.  It initially places work onto the high-priority queue for the slaves 
to fetch.  It then clears new pre-search jobs specified by each slave process from 
the low-priority queue, and places them back onto the high-priority queue for the next 
level of recursion.<p>

Once the pre-searches have concluded, the slaves have fulfilled their tasks for the current 
iteration.  The master then computes the Hausdorff distances between the object and the 
"interesting regions", and looks for the best possible match, if any.  If one is found, it 
outputs the new bounding-box of the object, based on the current image, <i>Next</i>.<p>

<a name="5.2">
<!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><!WA62><a href="#home">Go Back</a>
<h3>5.2  Implementation #1:  An Inefficient Parallel <i>im_search</i></h3>

We discovered an implementation of the parallelized <i>im_search</i> RivL node.  
Unfortunately, we are unable to give credit to the developer(s) of the implementation 
because it is completely un-documented. The implementation utilizes the parallelization 
scheme described in the previous section.  The design is meant to run over a shared 
memory machine.<p>

When the left-to-right traversal of the RivL graph hits the <i>im_search</i> node, RivL attaches 
the high and low priority job queue data structure to shared memory, and generates UNIX-
IPC semaphores to govern access to this shared object to prevent race conditions, and to 
synchronize the parallelization.  Once the shared-memory and semaphores are set up, 
RivL then forks n slave processes.<p>

We want to emphasize that this implementation is SPMD.  The only shared data  is the job 
queue, which is simply a data structure that contains pointers to different portions of 
<i>Next</i>.  
The object-model and image data are completely replicated in each RivL process, and 
reside at exactly the same address in each process's address space.  The parallel 
computation proceeds as described above.  When the slave processes are done (i.e. all 
interesting regions have been found), the master kills each slave, and de-allocates 
the shared-memory segment.  The master then proceeds to finish the object tracking computation.  On the next traversal of the RivL graph, the above sequence of 
events are repeated   The master again sets up shared-memory and the 
semaphores, re-forks, and then re-kills the slaves.<p>

We believe that this is a very wasteful implementation of <i>im_search</i>.  At every iteration, 
expensive UNIX kernel system calls are generated to:<p>

<ol>
<li>setup shared-memory and the semaphores.  In doing so, expensive resources are wasted 
in re-allocating the same memory segment.<p> 
<li>fork n slave processes.  This involves replicating not only the <i>im_search</i> node, but the 
entire RivL address space.  This includes replicating the RivL graph, and all RivL data, 
including the model and image data.  We believe that the developers of this 
implementation forked new slaves every iteration to eliminate a lot of work and 
complications involved in establishing an efficient means of communication between the 
processes.  
</ol>
<p>

This wastefulness led us to develop a smarter implementation of <i>im_search</i> that re-uses 
resources, and improves performance of the object tracker.<p>
<!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><!WA63><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p>   

<a name="6.0">
<!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><!WA64><a href="#home">Go Back</a>
<h2>6.0  Implementation #2:  Persistent Parallel <i>im_search</i></h2>

An improved way of implementing the object tracking algorithm seeks to reduce the 
overhead of re-creating a shared memory segment and forking off a series of child 
processes for each frame in an object tracking sequence. With a little information about 
the position of the current frame in a larger tracking problem, the object tracker can keep 
the shared memory and the child processes alive while the same sequence of images 
continue to be tracked. This way, the master process can simply put the new image and 
model into shared memory and wake the children up to start work on the current tracking 
sub-problem. Only when a sequence has been completely tracked will the shared memory 
be cleaned up and the children killed in anticipation of a new sequence to be tracked.<p>

<a name="6.1">
<!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><!WA65><a href="#home">Go Back</a>
<h3>6.1  Passing Sequence Information</h3>

The first issue to be dealt with was the passing of sequence information into the object 
tracker. This required information from RivL's tcl interface into the C procedures. The 
basic idea was to figure out how many images were in the sequence being tracked and the 
index of the current frame being processed. If the frame was the first frame in its sequence, 
the object tracker ran the <i>mp_startup</i> procedure to set up a shared memory segment large 
enough for the current image sequence and forked off the child processes. If the current 
frame was the last frame in a sequence, the object tracker would run <i>mp_shutdown</i>, and 
remove the shared memory segment and clean up the child processes after completing the 
tracking algorithm. Any other frame position meant that the frame was somewhere in the 
middle of the sequence and required no special action.<p>

<a name="6.2">
<!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><!WA66><a href="#home">Go Back</a>
<h3>6.2  The Contents of Shared Memory</h3>

The master process is responsible for keeping the shared memory segment up to date with 
the current tracking task. Because the child processes no longer contain the most recent 
image and model information, these structures have to be explicitly maintained in shared 
memory. Basically, shared memory is extended from the rudimentary object tracker to 
contain a large body of additional data in addition to the basic jobs structure outlined 
above:<p>