CSCI 135 Online |
In this assignment, you will re-affirm the atomic nature of matter by tracking the motion of particles undergoing Brownian motion, fitting this data to Einstein's model, and estimating Avogadro's number. In the process you will use a variety of the things you've learned in the course including: object-oriented programming, recursion, and performance analysis.
Historical perspective. The atom played a central role in 20th century physics and chemistry, but prior to 1908 the reality of atoms and molecules was not universally accepted. In 1827, the botanist Robert Brown observed the random erratic motion of wildflower pollen grains immersed in water using a microscope. This motion would later become known as Brownian motion. Einstein hypothesized that this Brownian motion was the result of millions of tiny water molecules colliding with the larger pollen grain particles.
In one of his "miraculous year" (1905) papers, Einstein formulated a quantitative theory of Brownian motion in an attempt to justify the "existence of atoms of definite finite size." His theory provided experimentalists with a method to count molecules with an ordinary microscope by observing their collective effect on a larger immersed particle. In 1908 Jean Baptiste Perrin used the recently invented ultramicroscope to experimentally validate Einstein's kinetic theory of Brownian motion, thereby providing the first direct evidence supporting the atomic nature of matter. His experiment also provided one of the earliest estimates of Avogadro's number. For this work, Perrin won the 1926 Nobel Prize in physics.
The problem. In this assignment, you will redo a version of Perrin's experiment. Your job is greatly simplified because with modern video and computer technology (in conjunction with your programming skills), it is possible to accurately measure and track the motion of an immersed particle undergoing Brownian motion. We supply video microscopy data of polystyrene spheres ("beads") suspended in water, undergoing Brownian motion. Your task is to write a program to analyze this data, determine how much each bead moves between observations, fit this data to Einstein's model, and estimate Avogadro's number.
The data. Start by downloading this single zip file. We provide ten datasets obtained by William Ryu using fluorescent imaging. Each run contains a sequence of two hundred 640-by-480 color JPEG images, frame00000.jpg through frame00199.jpg and is stored in a subdirectory run_1 through run_10.
Here is a movie of several beads undergoing Brownian motion. Below is a typical raw image (left) and a cleaned up version (right) using thresholding, as described below.
Each image shows a two-dimensional cross section of a microscope slide. The beads move in and out of the microscope's field of view (the x- and y-directions). Beads also move in the z-direction, so they can move in and out of the microscope's depth of focus; this results in halos, and it can also result in beads completely disappearing from the image.
Particle identification. The first challenge is to identify the beads amidst the noisy data. Each image is 640-by-480 pixels, and each pixel is represented by a Color object which needs to be converted to a luminance value ranging from 0.0 (black) to 255.0 (white). Whiter pixels correspond to beads (foreground) and blacker pixels to water (background). We break the problem into three pieces: (i) read in the picture, (ii) classify the pixels as foreground or background, and (iii) find the disc-shaped clumps of foreground pixels that constitute each bead.
Create a helper data type Blob that has the following API.
public class Blob ------------------------------------------------------------------------------------------------ public Blob() // construct an empty blob public void add(int i, int j) // add a pixel (i, j) to the blob public int mass() // return number of pixels added = its mass public double distanceTo(Blob b) // return distance between centers of masses of this blob and b public String toString() // return string containing this blob's mass and center of mass // format center-of-mass coordinates with 4 digits to right // of decimal point
Next, write a data type BlobFinder that has the following API. Use depth-first search to efficiently identify the blobs.
Write a main() method in BlobFinder.java that takes an integer P, a double value tau, and the name of a JPEG file as command-line arguments. It then creates a BlobFinder object using a luminance threshold of tau. Next, it prints out all of the beads with at least P pixels; finally, it prints out all of the blobs (beads with at least 1 pixel).public class BlobFinder ------------------------------------------------------------------------------------------------ // find all blobs in the picture using the luminance threshold tau public BlobFinder(Picture picture, double tau) // return the number of beads with >= P pixels public int countBeads(int P) // return all beads with >= P pixels public Blob[] getBeads(int P)
The program identifies 15 blobs in the sample frame, 13 of which are beads. Our string representation of a blob specifies its mass (number of pixels) and its center of mass (in the 640-by-480 picture). By convention, pixels are measured from left-to-right, and from top-to-bottom (instead of bottom-to-top).% java BlobFinder 25 180.0 run_1/frame00001.jpg 13 Beads: 29 (214.7241, 82.8276) 36 (223.6111, 116.6667) 42 (260.2381, 234.8571) 35 (266.0286, 315.7143) 31 (286.5806, 355.4516) 37 (299.0541, 399.1351) 35 (310.5143, 214.6000) 31 (370.9355, 365.4194) 28 (393.5000, 144.2143) 27 (431.2593, 380.4074) 36 (477.8611, 49.3889) 38 (521.7105, 445.8421) 35 (588.5714, 402.1143) 15 Blobs: 29 (214.7241, 82.8276) 36 (223.6111, 116.6667) 1 (254.0000, 223.0000) 42 (260.2381, 234.8571) 35 (266.0286, 315.7143) 31 (286.5806, 355.4516) 37 (299.0541, 399.1351) 35 (310.5143, 214.6000) 31 (370.9355, 365.4194) 28 (393.5000, 144.2143) 27 (431.2593, 380.4074) 36 (477.8611, 49.3889) 38 (521.7105, 445.8421) 35 (588.5714, 402.1143) 13 (638.1538, 155.0000)
Particle tracking. The next step is to determine how far a bead moved from one time step t to the next t + Δt. For our data, Δ t = 0.5 seconds per frame. We assume the data is such that each bead moves a relatively small amount, and that two beads do not collide. (However, we must account for the possibility that the bead disappears from the frame, either by departing the microscope's field of view in the x- or y- direction, or moving out of the microscope's depth of focus in the z-direction.) Thus, for each bead at time t + Δt, we calculate the closest bead at time t (in Euclidean distance) and identify these two as the same beads. However, if the distance is too large (greater than delta pixels) we assume that one of the beads has either just begun or ended its journey. We record the displacement that each bead travels in the Δt units of time.
Write a main() method in BeadTracker.java that takes an integer P, a double value tau, a double value delta, and a sequence of JPEG filenames as command-line arguments, identifies the beads (using the specified values of P and tau) in each JPEG image (using BlobFinder), and prints out (one per line, formatted with 4 decimal places to the right of decimal point) the radial displacement that each bead moves from one frame to the next (assuming it is no more than delta). Note that it is not necessary to explicitly track a bead through a sequence of frames—you only need to worry about identifying the same bead in two consecutive frames.
% java BeadTracker 25 180.0 25.0 run_1/*.jpg 7.1833 4.7932 2.1693 5.5287 5.4292 4.3962 ...
Data analysis. Einstein's theory of Brownian motion connects microscopic properties (e.g., radius, diffusivity) of the beads to macroscopic properties (e.g., temperature, viscosity) of the fluid in which the beads are immersed. This amazing theory enables us to estimate Avogadro's number with an ordinary microscope by observing the collective effect of millions of water molecules on the beads.
For our data, Δt = 0.5 so this is an estimate for D as well. The radial displacements ri are measured in pixels: to convert to meters, multiply by 0.175 * 10-6 (meters per pixel).
and k is the Boltzmann constant. All parameters are given in SI units. The Boltzmann constant is a fundamental physical constant that relates the average kinetic energy of a molecule to its temperature. We estimate k by measuring all of the parameters in the Stokes-Einstein equation, and solving for k.
For the final part, write a main() method in Avogadro.java that reads in the displacements from standard input and computes an estimate of Boltzmann's constant and Avogadro's number using the formulas described above.
% more displacements-run_1.txt % java BeadTracker 25 180.0 25.0 run_1/*.jpg | java Avogadro 7.1833 Boltzmann = 1.2535e-23 4.7932 Avogadro = 6.6330e+23 2.1693 5.5287 5.4292 4.3962 ... % java Avogadro < displacements-run_1.txt Boltzmann = 1.2535e-23 Avogadro = 6.6330e+23
Output formats. Use four digits to the right of the decimal place for all of your floating point outputs whether they are in floating point format or exponential format.
Running time analysis. Formulate a hypothesis for the running time (in seconds) of BeadTracker as a function of the input size N (total number of pixels read in across all frames being processed). Use the double hypothesis as described in the lecture on Performance. Include in you submission a readme.txt file containing details of your performance experiments as well as your hypothesis about the order of growth and constant term of the function.
Are the slides from the video available? Here they are.
Do I need to follow the prescribed API? Yes, we will be testing the methods in the API directly. If your method has a different signature or does not behave as specified, you will lose a substantial number of points. You may not add public methods to the API; however, you may add private methods (which are only accessible in the class in which they are declared).
Are diagonal pixels considered adjacent? No, use only the 4 ordinal neighbors (N, E, S, and W).
Do I have to output the blobs, beads and displacements in the same order as shown on the assignment web page? No, although keeping it in the same order makes it easier for you (and us) to check. However, you must follow the instructions for the BlobFinder.main() which says to print out the list of beads with size at least P before printing out the list of all the blobs.
What should I do if several of the beads in frame t+1 have the same bead in frame t as their closest bead? That happens from time to time, but don't worry about it. For our purposes, it is fine to ignore this case since the beads aren't supposed to get too close. If they do get close, there's no good way to track them anyway. Our posted solutions do not check for that rare case and we just let the same bead in frame t get paired a second time.
I am able to find beads and blobs correctly, but my BeadTracker gives a few errors, despite that it is mostly working. Why could this be? Make sure you exactly follow the given instructions: for each bead in each frame, you should be finding the closest bead to it in the previous frame. Doing the reverse gives slightly different results. (See also the next question.)
Why do I have to compare each bead in frame t+1 to each bead in frame t? Why can't I do it the other way around? It's an arbitrary choice. We require you do it this way to make it easier to check your answer.
My physics is a bit rusty. Do I need to worry about converting units? No, we have provided all of the constants in SI units. The only conversion you should need to do is to convert from distances measured in pixels (the radial displacements) to distances measured in meters using the conversion factor of 0.175 × 10-6 meters per pixel.
Can I assume that all of the frames be 640-by-480 and that all of the runs will consist of 200 frames? No, do not hardwire any of these constants into your program. Use picture.width() and picture.height() for the width and height, and use args.length for the number of command-line arguments.
Is there a way to make the toString() method format numbers in a nice way? Yes. String.format() works like System.out.printf(), but returns the resulting string instead of printing it. Here is our toString() method in Blob.
See p. 125 of the textbook to learn more about formatted printing.public String toString() { return String.format("%2d (%8.4f, %8.4f)", mass, cx, cy); }
How do I specify the 200 image names on the command line? One way is to type them all in.
An easier alternative is to use the wildcard capability of your command line: for example, the following specifies (in alphabetical order) all .jpg files in the run_1 directory.% java BeadTracker 25 180.0 25.0 run_1/frame00000.jpg run_1/frame00001.jpg run_1/frame00002.jpg ...
% java BeadTracker 25 180.0 25.0 run_1/*.jpg
How can I estimate the running time of my BeadTracker program? Use the Stopwatch object from Section 4.1. Remember to remove it and any additional print statements from your submitted version of BeadTracker.java. Alternatively, you may use the java command-line option -Xprof. Either way, when you execute BeadTracker, redirect the output to a file to avoid measuring the time to print the output to the terminal. Run BeadTracker with a variety of input sizes which allow you to get good timing data and form a doubling hypothesis.
How do I run BeadTracker with a variety of input sizes? Don't all the runs have 200 frames? They do, but when you are investigating the timing, you don't care about the actual displacements, only how long it takes to compute them.
On OS X or Linux, you can use the wildcard capability of the command-line to run 10 frames, 20 frames, 40 frames, 80 frames, and 160 frames:
% java BeadTracker 25 180.0 25.0 run_1/frame000[0]*.jpg > temp.txt % java BeadTracker 25 180.0 25.0 run_1/frame000[0-1]*.jpg > temp.txt % java BeadTracker 25 180.0 25.0 run_1/frame000[0-3]*.jpg > temp.txt % java BeadTracker 25 180.0 25.0 run_1/frame000[0-7]*.jpg > temp.txt % java BeadTracker 25 180.0 25.0 run_1/frame000*.jpg run_1/frame001[0-5]*.jpg > temp.txt
On Windows, one simple way is to create several subdirectories with the desired number of frames. Another way is to use the limited wildcard capability of command prompt to run 100, 200 and 400 frames.
> java BeadTracker 25 180.0 25.0 run_1\frame000*.jpg > temp.txt > java BeadTracker 25 180.0 25.0 run_1\*.jpg > temp.txt > java BeadTracker 25 180.0 25.0 run_1\*.jpg run_1\*.jpg > temp.txt
How long should my program take? It depends on the speed of your computer, but probably between a few seconds and 30 seconds for 200 frames.
How much memory should my program use? Ours uses less than 5 MB. You will receive a deduction if you use substantially more. The most common way to waste memory is to hold references to an array of Picture objects in BeadTracker instead of only two at a time. You can use the -Xmx option to limit how much memory Java uses: for example, the following command limits the memory available to Java to 5 MB.
% java -Xmx5m BeadTracker 25 180.0 25.0 run_1/*.jpg
How accurate of an estimate should I get? You should get within 10% or so of the exact value for Avogadro's number (6.022142 × 1023). The standard deviation of the radius of the beads is about 10%, so you shouldn't expect results more accurate than this.
However, your estimates for a given run should agree exactly with ours. Our output from Avogadro for run_1 is given on the assignment page. Our output from Avogadro for run_2 is given below in the Testing section. Here is our output from run_6.
% java BeadTracker 25 180.0 25.0 run_6/*.jpg | java Avogadro Boltzmann = 1.3482e-23 Avogadro = 6.1670e+23
Possible Progress Steps. These are purely suggestions for how you might make progress. You do not have to follow these steps.
Be sure to thoroughly test your data type before proceeding.
Page last updated: January 21, 2015