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 . 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 in the plane in time 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 , or, equivalently, minimizing . Calculating 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 at . 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 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 . 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 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 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 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 .