http:^^www.cs.cornell.edu^info^people^barber^potrivl^potrivl.html
来自「This data set contains WWW-pages collect」· HTML 代码 · 共 677 行 · 第 1/3 页
HTML
677 行
MIME-Version: 1.0
Server: CERN/3.0
Date: Sunday, 01-Dec-96 18:54:03 GMT
Content-Type: text/html
Content-Length: 34844
Last-Modified: Saturday, 18-May-96 02:22:04 GMT
<html><head><title>An Improved-Version of a Parallel Object-Tracker in RivL</title><center><h1>An Improved-Version of a Parallel Object-Tracker in RivL</h1><p>http://www.cs.cornell.edu/Info/People/barber/potrivl/potrivl.html<p><b>Sicco Tans (<!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><a href=mailto:stans@cs.cornell.edu>stans@cs.cornell.edu</a><br><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><a href="http://www.cs.cornell.edu/Info/People/barber">Jonathan Barber</a> (<!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><a href=mailto:barber@cs.cornell.edu>barber@cs.cornell.edu</a>)<br></b><p><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><a href="http://www.cs.cornell.edu/Info/Courses/Spring-96/CS664/CS664.html">CS664 Final Project</a><br><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><a href="http://www.cs.cornell.edu/Info/People/rdz/rdz.html">Professor Ramin Zabih</a><br><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><a href="http://www.cs.cornell.edu/">Department of Computer Science</a><br><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><a href="http://www.cornell.edu">Cornell University</a></h2></center><p></head><body><a name = "home"><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p><h2>0.0 Table of Contents</h2><ul><li><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><a href="#1.0">1.0 Abstract</a><li><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><a href="#2.0">2.0 Introduction</a><li><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><a href="#3.0">3.0 RivL and the Generic Parallel Paradigm</a><ul><li><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><a href="#3.1">3.1 The RivL Graph</a> <li><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><a href="#3.2">3.2 Generic Parallel RivL</a></ul><li><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><a href="#4.0">4.0 RivL's Object Tracker</a><ul><li><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><a href="#4.1">4.1 The Object Tracker Script</a> <li><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><a href="#4.2">4.2 The Algorithm behind <i>im_search</i></a> <li><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><a href="#4.3">4.3 Parallelizing <i>im_search</i></a> <li><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><a href="#4.4">4.4 Problems with <i>im_search</i> and Generic Parallel RivL</a></ul><li><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><a href="#5.0">5.0 Parallelizing <i>im_search</i> in RivL</a><ul><li><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><a href="#5.1">5.1 A Course-Grain Parallelization Scheme</a> <li><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><a href="#5.2">5.2 Implementation #1: An Inefficient Parallel <i>im_search</i></a></ul><li><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><a href="#6.0">6.0 Implementation #2: Persisent Parallel Object Tracker</a><ul><li><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><a href="#6.1">6.1 Passing Sequence Information</a> <li><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><a href="#6.2">6.2 The Contents of Shared Memory</a> <li><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><a href="#6.3">6.3 Setting up Shared Memory</a> <li><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><a href="#6.4">6.4 Updating Shared Memory</a> <li><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><a href="#6.5">6.5 A New Semaphore</a> <li><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><a href="#6.6">6.6 Implementation Issues</a></ul><li><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><a href="#7.0">7.0 Performance Results</a><li><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><a href="#8.0">8.0 Extensions & Improvements</a><li><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><a href="#9.0">9.0 Conclusions</a><li><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><a href="#10.0">10.0 References</a></ul><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p><a name="1.0"><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><a href="#home">Go Back</a><h2>1.0 Abstract</h2>The fields of multimedia image processing and Computer Vision are converging. At the same time, a lot of work is being spent on making image/vision processing algorithms more efficient, accessible, and usable to programmers. A strong example of this merging of technologies exists in RivL's Object Tracker, which has been the focus of our work. In this paper, we detail the inception and development of an efficient [parallel] Object Tracker that is available with RivL.<p><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><!WA34><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p> <a name="2.0"><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><!WA35><a href="#home">Go Back</a><h2>2.0 Introduction</h2>There are many similarities between the fields of multimedia image processing and Computer Vision. In many instances it is hard distinguish one from the other. Both fields involve operating on a single or a continuous stream of images. These operations typically incur a very large computational expense. Object Tracking is an example of such a multimedia/vision application.<p>In recent years, a lot of effort has been spent in attempting to make image-processing and vision-related algorithms easier to program, by adding many layers of abstraction between the image data, the image operations themselves, and the interface to the programmer/user. At the same time, these higher levels of abstraction should not add to the computational complexity of the operation.<p> This left researchers and developers with the extraordinarily difficult problem of making multimedia/vision operations fast, efficient, and easy-to-use. The effort manifested itself with the construction of RivL (<i>A Resolution Independent Video Language</i>) [<!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><!WA36><a href="#1ref">1</a>]. RivL is a multimedia software processing package that, given a set of images (or a set of a sequence of images), can efficiently process these multimedia streams and generate an outgoing image (or a sequence of images). RivL is implemented as a tcl extension that is capable of performing common image operations such as overlay, smoothing, clipping, cropping, etc. It also includes more complex vision-related image processing operations, such as objecttracking, which has been the focus of our work. The tcl interface simplifies the process of coding an image/vision processing script.<p>In recent months, several developers have improved RivL performance measures via a fine-grained parallelization scheme using a shared memory machine and an a distributed computing environment [<!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><!WA37><a href="#2ref">2</a>]. The parallelization is independent of most of the image operations resident in the RivL library (e.g. im_clip, im_smooth, im_canny). Unfortunately, this scheme does not lend itself to more complicated computer vision applications. In particular, the scheme does not work for Object Tracking.<p> <b>Bearing this in mind, we established the project goal to develop a backwards-compatible parallel implementation of Object Tracking tailored for RivL.</b><p> In Section 3.0, we introduce RivL, and describe the generic parallelization scheme.In Section 4.0, we describe the Hausdorff-based Object-Tracking algorithm implemented in RivL. In Section 5.0, we introduce the scheme for parallelizing RivL's Object Tracking operation. In Section 6.0, we describe our implementation of a parallel Object-Tracking RivL operation. In Section 7.0 we present our performance results. In Section 8.0, we present some extensions for future work and improvements in the current implementation. In Section 9.0, we draw some conclusions.<p><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><!WA38><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p> <a name="3.0"><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><!WA39><a href="#home">Go Back</a><h2>3.0 RivL and the Generic Parallel Paradigm</h2><a name="3.1"><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><!WA40><a href="#home">Go Back</a><h3>3.1 The RivL Graph</h3>We begin our discussion of RivL by introducing the RivL Evaluation Graph.<p><center><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><!WA41><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sld001.gif"></center><p>In order for RivL to execute, it requires a set of multimedia input data, and a control RivL script. The RivL script is a sequence of tcl-RivL commands that specify what image processing operations should occur on the input data. Once RivL is invoked, the RivL script is translated into the RivL graph, as pictured above. Each node corresponds to some image operator (e.g. <i>im_smooth</i>, <i>im_canny</i>, etc.), and each edge or signal corresponds to the actual image data. Those nodes lying inside of the illustrated rectangle above correspond to true image operators. Those nodes lying outside of the rectangle are the RivL I/O nodes. The nodes outside and to the left of the rectangle correspond to read nodes (i.e. one read/node per image [or stream]), and the node to right of the rectangle corresponds to the write node.<p>We want to emphasize that construction of the RivL graph does not compute on any multimedia data. The RivL graph is merely the control-flow structure through which each inputted sequence of data must propagate to generate the outputted, processed image.<p>There are two phases in processing data using the RivL graph once it has been constructed. The first phase manifests itself in a graph traversal from right-to-left. This is what makes RivL an efficient image processing mechanism. The first node that is evaluated is the Write node (the right-most node). By traversing the graph in reverse-order, RivL decides at each node exactly how much data the output signal requires from the input signal. The evaluation is reverse-propagated from the write node, through the graph, and back to every read node. Once the reverse-propagation completes, every node in the graph knows exactly how much data from each input signal is required to compute the node's corresponding output signal. The multimedia data is then processed on the second traversal, which conforms to a left-to-right traversal of the RivL graph, propagating the input data forwards through the graph, only operating on data that is relevant to the final output image.<p><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><!WA42><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p><a name="3.2"><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><!WA43><a href="#home">Go Back</a><h2>3.2 Generic Parallel RivL</h2>We can summarize the preceding section into the statement that, the amount of data that is fetched from each Read node is exactly a function of the output of the Write node. Combining this notion with the fact that most of the image processing operations in RivL do not create dependencies from one pixel to another in a given input image, we can derive a simple for mechanism for "dividing up the work", and parallelizing RivL.<p> Instead of running RivL on a single processor, RivL spawns multiple processes on different processors, and has each process work towards computing a different segment of the output data. We define the notion of a single master RivL process, and multiple slave RivL processes. Each slave process should run on a different processor. Once started, the slave process sits idle, listening for instructions from the master. During the initial setup period, the master sends each slave process a logical ID#. In addition, each slave is aware of the total number of processes "available for work".<p>Following the control-setup period, the master sends each slave a copy of the RivL script. Once each slave (and the master) receives the RivL script, they each generate a copy of the RivL graph, and perform the right-to-left traversal independently.<p>The difference between the right-to-left traversal now, is that the logical ID# for the current processor and the total number of processes becomes a factor in determining how much computation gets done for each process.<p><center><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><!WA44><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sld002.gif"></center><p>According the figure above, the amount of data fetched from each read node is no longer a function of the output of the write node, but is now a function of:<p><ul><li>the process's Logical ID# <li>the total number of processes <li>and, is a function of the write node's output</ul>That is, each RivL process is responsible for computing a different, independent portion of the final output data, which is based on the above parameters. The approach is fine-grained in that each RivL process performs the same set of computations, on different data.<p> Actual data computation (the left-to-right graph traversal) occurs when the master says "go". Each slave and the master process computes their appropriated portion of the output image.<p><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><!WA45><img src="http://www.cs.cornell.edu/Info/People/barber/potrivl/pict/sepbar-6.gif"><p><a name="4.0"><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><!WA46><a href="#home">Go Back</a><h2>4.0 RivL's Object-Tracker</h2> <a name="4.1"><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><!WA47><a href="#home">Go Back</a><h3>4.1 The Object-Tracker Script</h3>The RivL Object Tracker is implemented as a tcl script which executes a set of RivL ⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?