Next: Error Estimates and Optimal Up: Five Stages of Colloidal Previous: Noise Discrimination and Tracking

Linking Locations into Trajectories

Having located colloidal particles in a sequence of video images, we match up locations in each image with corresponding locations in later images to produce the trajectories in tex2html_wrap_inline859 . This requires determining which particle in a given image most likely corresponds to one in the preceding image. Tracking more than one particle requires care since any particle can be identified with only one particle in each of the successive and preceding frames. Thus, we seek the most probable set of N identifications between N locations in two consecutive images. If the particles are indistinguishable, as for monodisperse colloidal spheres, this likelihood can be estimated only by proximity in the two images.

The probability that a single Brownian particle will diffuse a distance tex2html_wrap_inline823 in the plane in time tex2html_wrap_inline987 is


where D is the particle's self-diffusion coefficient. For an ensemble of N noninteracting identical particles, the corresponding probability distribution is the product of single particle results:


The most likely assignment of particle labels from one image to the next is the one which maximizes tex2html_wrap_inline993 , or, equivalently, minimizing tex2html_wrap_inline995 . Calculating tex2html_wrap_inline993 for all possible combinations of label assignments, however, would require O(N!) computations, which is impractical for all but the most trivial distributions.

Each label assignment can be thought of as a bond drawn between a pair of particles in consecutive frames. The set of all possible label assignments forms a network in the plane. To reduce the complexity of assigning labels, we select only those bonds shorter than a characteristic length scale L to be possible candidates for the assignment of particle labels between two frames. This is equivalent to truncating the single-particle probability distribution tex2html_wrap_inline1003 at tex2html_wrap_inline1005 . If L is somewhat smaller than the typical interparticle spacing in a snapshot, the remaining network usually is reduced to a collection of disconnected subnetworks. We then can solve for the optimal set of identifications within each of these subnetworks separately. For small enough values of L, most subnetworks contain only single bonds for which the assignment of labels is trivial. Trajectory linking proceeds in tex2html_wrap_inline1011 time for such trivial cases.

The least difficult nontrivial subnetworks to resolve consist of bonds linking M particles in one frame to M in the next, with tex2html_wrap_inline1017 . The assignment of labels in this case proceeds according to eqn. (10) with no more than O(M!) operations and often much fewer. Subnetworks connecting unequal numbers of sites in two frames pose more of a problem since some labeling assignments then cannot be resolved. Such subnetworks are not unusual because particles often wander into and out of the observable sample volume, particularly near the edges. To proceed with labeling, we add as many ``missing'' bonds as are needed to complete trial labeling assignments. These missing bonds are assigned the length tex2html_wrap_inline1021 for the purpose of evaluating eqn. (10). The most probable set of identifications therefore requires labeling some particles as ``missing'' in individual time steps. The last known locations of missing particles are retained in case unassigned particles reappear sufficiently nearby to resume the trajectory. This process is repeated for the particle locations in each frame until tex2html_wrap_inline859 is completely determined. Trajectories for monodisperse colloidal spheres at a crystal-fluid interface appear in Fig. 3.

Linking particle distributions into trajectories is only feasible if the typical single particle displacement tex2html_wrap_inline823 in one time step is sufficiently smaller than the typical interparticle spacing, a. Otherwise, particle positions will become inextricably confused between snapshots. The optimal cutoff parameter falls in the range tex2html_wrap_inline1029 .

Next: Error Estimates and Optimal Up: Five Stages of Colloidal Previous: Noise Discrimination and Tracking

David G. Grier
Mon Mar 11 23:01:27 CST 1996