(1) Sampling points

The shape of a fish is captured by a finite subset of points sampled from the external (and sometimes internal contours) on the object. Using an edge detector such as the Canny edge operator, a binary image is obtained. From this binary image, N points are sampled such that the final subset is distributed sufficiently uniform along the edges. The number of points to sample, N , affects the accuracy of the shape representation, and we shall discuss that effect in the Results & Discussion section. For most of the fish images we're using, 100 - 300 points are sufficient.

Shown below are two fish images sampled with 150 points:

Original	Sampled

(2) Shape Context

First we define the problem: given two fish images F1 and F2, we've extracted a representative point subset P and Q, respectively. For each point p_i on the first shape, we want to find the "best" matching point q_j. How do we define a descriptor for the shape content for each point? What is the "goodness" metric of matching one point against the other?

The descriptor proposed by Belongie et al., is shape context , a feature vector that expresses the configuration of the entire shape relative to the reference point. To reduce the complexity of the feature vector, a coarse histogram is used. For each point p_i in a shape, the corresponding feature vector is computed by a histogram h_i of the relative coordinates of the remaining N-1 points:

Bins are uniform in log-polar space, making the descriptor more sensitive to positions of nearby sample points than to those of points farther away.

The cost of matching (p_i, q_j) thus can be defined using the C² text statistic:

The shape context is essentially translation invariant. To achieve scale invariance, all radial distances are normalized by mean distance between all point pairs. We ignore the handling of outliers and noise, assuming that our fish images are clean. To achieve rotation invariance, however, we took a more user-interactive approach. Instead of the approach proposed by the paper, which is treating the tangent vector at each point as the positive x-axis, we let users help pinpoint the outline of the fish and orient the input image to a fixed orientation (see Image Pre-Processing section).

(3) Bipartite Graph Matching

Given the parwise cost matrix, we want a one-to-one matching such that the total matching cost is minimized. This is simply the min-cost bipartite matching problem. The Kuhn-Munkres algorithm (also known as the Hungarian method) solves matching problem in O(n³). When implementing the bipartite matching, we tested running time and optimality on three methods: the Hungarian, a near-optimal heuristic approach, and the greedy approach. Performance comparison is given in the Results & Discussion section, and an outline of the heuristic and greedy approach is described in the Appendix. We decided to use the heuristic approach since it gives a sufficiently good solution within reasonable running time.

The Belongie paper used "dummy" nodes to handle outliers. Since our fish images are assumed to be clean, dummy nodes are generally not used. However, if we are to use variable sample points (dependent on the shape size or complexity), dummy nodes may be added with a threshold set to rule out bad matches. A few hand-tuned tests indicate that a threshold of 40 performs pretty well when sample points vary between 100 and 400.

Shown below is a good vs bad matching example. The left one is matching two fish shapes that are extracted from two different images containing the same species of fish (but probably not the same fish...). So this should have a "good" matching. The red dots are the sampled shape points for the query image, and the green dots are those of the correct database match image.

Right Answer	Wrong Answer
Just aligning the two shapes points to get a view before the matching...

Right Answer	Wrong Answer

The blue lines indicate point-to-point corresspondence. It's obvious that the left one has a more coherent and believable matching.

(4) Modeling Transformation

Given one-to-one correspondences between two pointsets, we can estimate a plane transformation using Thin Plate Splicing. Given a set of data points, a weighted combination of thin plate splines centered about each data point gives the interpolation function that passes through the points exactly while minimizing the "bending energy" - defined as

Since we don't expect corresponding point locations to be perfect, the interpolation is relaxed by means of regularization. By adding a regularization parameter l. We set l equal to a²l₀, where a is again the mean distance, and l₀ = 1.

We do TPS transformation individually for x and y. In the original paper, they did a matching-TPS reiteration to recover from errorneous correspondences. We consider this as unncessary, so we run bipartite matching only once, then use the bending energy as an indicator for goodness of matching.

(5) Shape Distance

Here comes to fun part: we have the query image of a fish whose identity is unknown, and a database of annotated fish images. We compute the matching cost and bending energy for all database images. Then, what should the scoring theme be? Belongie et al., used a combined distance cost of (1) symmetric sum of shape context matching cost over best matching points + (2) sum of squared brightness differences in Gaussian windows around sample points + (3) bending energy. And they weighted the three distance costs when it was applied to different image sets.

After experimenting with a few image matches, we decided to discard this scoring theme and come up with our own. Instead of using the real costs and weigh them differently, we use a weighted ranking system. Each database image would different rankings for different features, we can then weigh them in whatever way we like without worrying about different features having different cost ranges - for example, a bipartite matching cost could range from 9000 to 50000, depending on sample point size, while bending energy is usually less than 100.

In addition to matching cost and bending energy, we substituted texture for brightness differences. We used the texture feature from Manjunath et al.,, which uses a Gabor wavelet feature vector. We used the Matlab code provided by the author. The difficulty arises however, in deciding the "texture" of a fish. Unlike a grassy plane or cloth, the shape of a fish varies and it's not entirely clear which part of it should be considered as texture. If we include the entire fish image, it would take into account too much of the silhouette outline. Instead we sampled only the middle (supposedly the torso) part of the fish, where stripes, spots, and color patterns are most distinguishable.

A few texture patch example is shown below. We're showing it in color because it's prettier, but in reality the texture patch is converted to grayscale. This makes sense since illumination changes too much over different fish images.

In general, shape & texture feature extraction take a reasonable constant amount of time, and they're computed once-and-for-all and then stored in *.mat format. The greatest dragdown of matching speed is caused by the bipartite matching.

Below is a comparison table of running time(secs) on 3 methods: Hungarian, Heuristic, and Greedy.

As can be observed, the heuristic method is a better choice since it runs faster than the optimal Hungarian method while still achieving a near-optimal solution.

First of all we need to define the criteria for a "correct match". If the correct corresponding fish shows up as first place, it is undoubtedly a correct answer. But what if it goes second? third? The combination of weights on the different feature rankings could also lead to mismatches, especially when the query fish has the same shape with the correct database fish but has a different texture/color pattern, which is common. For example, if one googles up for images for Betta Splendens (fighter fish), then the following images show up:

Even when one ignores the orientation, the texture pattern is still very different. One might be tempted to say that all the fighter fishes have the same outline shape. That is only partially true: the fighter fishes all have similar head and torso outline, but the tails vary greatly. To make matters worse, some of the fish tails are transparent, which will cause great trouble in gettin a clean cut. Even when the query images is near noise-free, insufficient sample points may cause the details of the tail to be ignored, and the shape context descriptor would only represent it as a huge blob of tail fin.

We'll present examples on good and bad matches following subsections.

This is our query:

We try to match it against a 36-image database, which contains the right answer:

But when we match it, ths best match appeared to be something seemingly very different. The best match turns out to be Melichthys Niger!

First we look at bipartite shape matching. The highest ranking fish is Colisa Lalia. We compare the contour of the query, Colisa Lalia, and the right answer.

The query actually looks more similar to the shape of C. Lalia - a lenghtier body with the eye area captured. M. Niger ranks No.6 in shape matching.

M. Niger ranks No.1 in TPS bending energy and No.3 in texture, while the right answer ranks 15 and 23, correspondingly. It's not surprising that the texture ranking turned out this way, since by the way we sampled the texture it includes partial outline shapes, especially when the fish is round.

This leads to the thought that we should come up with a better way of sampling texture patches. Unfortunately, we didn't have enough time....

The matching of Abudefduf Saxatilis matches perfectly - without surprise, since the two input images were extremely similar. The query fish shape was:

The right answer ranks 1 on shape, 3 on bending, and 10 on texture. The reason for the slightly lower rank on texture can be speculated: the texture patch is actually not that similar around the torso center, since the right answer had straight vertical black stripes with yellow taint, and the query image didn't have yellow taint and had more curved stripes. Still, the overall good ranking across 3 categories yielded the correct answer.

This experiment was done with lavishness: Hungarian method for optimal min-cost bipartite matching, variable sample points (100, 200, 300, or 400 points based on image size).

And this match was done out of a database 86 fish images, with image size up to 600x600. It was encouraging to get this result, given the fact that the input had only 100 sample points (a 206x130 image), and the query had 300 (a 650x400 image). The matching took at least 40 minutes, which is why we didn't venture future in using Hungarian method + large database.

The running time of the matching system is heavily dependent on two factors: database size and sample point size. The sample point size increases the matching time for each single matching cubically. Since the matching is done sequentially (although they could be done concurrently under parallel implementation), the running time goes up linearly. In a word,

Part I: GrabCut (AutoCutRefine.m)

This program is developed by Rohit Gupta and Krishnan Ramnath from Carnegie Mellon University, with our modification in the user interface.

• First click File>Open to specifiy the image. (screen shot)
• Then, click on the diagonal bounding box of the fish (click1, click2)
• The program will run and try to find best segmentation.
• After the segmentation is done, it will be shown by green edge.
• Refine the segmentation by specifying foreground and background
  • Foreground -- (use your mouse to) click once to start your stroke, move your mouse around on the foreground, and click again to end the stroke. This will give you red dots on the image.
  • Background -- (use your mouse to) click once to start your stroke, move your mouse around on the background, and click again to end the stroke. This will give you blue dots on the image.
  • ForegroundRec -- click two spots to form a rectangle that is fully in the foregroung image. This will give you a red rectangle.
  • BackgroundRec -- click two spots to form a rectangle that is fully in the background image. This will give you a blue rectangle.
  • AutoRefine -- click to redo the autocut. This will show the effects of all your specified foreground/background points.
• "Save File" -- will save the segmented image to "segmented_image.ppm"

Part II: Fish Orientation (gui_rotate.m)

This function is called by passing the image filename. It will show the image on the screen.

• First click on the fish's mouth
• Then click on the fish's tail. This point will be at the same horizontal level as the fish in the result image.
• The result image will be shown on the screen and saved to "saved-(original filename)"

fishGUI

which will start up the GUI that looks like this:

You can load a raw image (accepted formats are BMP, PPM, and JPG) by clicking Load Image, or use Load Record to load a .mat file that already has the query image's features extracted and stored. A image Record contains its original image, a thumbnail, coordinates of sampled points, shape context descriptor (histogram), texture feature vector, and most important of one, the fish's venerable latin name. (NOTE: we understand that nobody knows the scientific name of a fish besides biologists, but common names have too many aliases and confusion).

Once you have a image/record loaded, you can match it against a compiled database by clicking Do Query!. You can select any existing database, or you can first use Add image to DB to compile your own database.

When the matching is done it will be displayed (up to top 15 matches can be displayed). You can save the matching record for future reference.