Target Identification Module

[benjaminwinger]

This issue is for more detailed information on the Target Identification module as well as for discussion of its implementation and assignment of duties.

Description

Module for analyzing frames using OpenCV tools, locating objects of interest and gathering information about the objects such as target colour, pixel area, perimeter and shape.

Implementation Ideas

This module can largely be based off of the code that I wrote for the 2015 competition which is currently stored in the 2015-attempt branch.
The above-mentioned code uses the OpenCV function kmeans to create a new image that contains only the n most common colours in the image. This image is then subtracted from the original image to isolate all of the uncommon coloured areas and shapes are identified by applying OpenCV's contour detection on the final image.
It is worth noting that kmeans is a very resource intensive function, and will be more costly than any other single part of this project.

It may also be useful to look at Isaac and Rees's target identification when looking at implementation improvements. (no clue where the code is)

Notes

While it is probably a good idea to start with the implementation that we already have, another possibility that we can look into is using machine learning for target identification. Unless there is someone who already has experience with machine learning who would be willing to implement it, other parts of the project should take precedence. But once the rest of the project is on track to being completed if there is someone eager to spend the time to learn (which I may eventually do myself, having the time being the key issue here) it may be well worth the time and effort.

Useful Links

Here's a link to the OpenCV 3.0 Documentation which includes tutorials.
OpenCV Doc
Histogram Based Image Segmentation Article

Assignees

@benjaminwinger
@Rich143
@francisli91

[benjaminwinger]

I've been reading up a bit on clustering and image segmentation. I think that we could get better results by re-implementing the opencv kmeans function to as a k-harmonic means function (see this document for details on the comparison between between k-means and similar clustering algorithms) and we could also remove some of the redundant code so that it outputs the subtracted image rather than making us do the colour subtraction in post.

A much faster alternative though may be to use histogram analysis for clustering as we would only have to perform a single pass over the image to generate the histogram, then do whatever calculations we need to find the clusters using the histograms (which is just identifying peaks and valleys, might get a bit complicated but it should be much faster to find clusters using the histogram than using the original image with k-means or the like) and then a single pass (though multiple operations on each pixel rather than a single assignment) to generate the final image by subtracting the value of the closest cluster from each pixel in the image.

Another thing we may have to think about is that we may want to use a completely different algorithm (such as the histogram based clustering mentioned above) for the target identification when running in real time than when running in post, where we have much more time and could use a slower but more accurate algorithm for the clustering such as k-harmonic means.

I also just noticed that for some reason you can only have one person assigned to an issue at a time. Maybe we should just include a list on the first comment.

[Rich143]

The histogram idea sounds like it might work well, have you found any documents that explain how we could use the histogram to identify the clusters?
I've also found that open cv has a function that does "Haar Feature-based Cascade Classifier for Object Detection". Haven't read much about it yet, but it looks like a machine learning algorithm. Seems to be mostly for facial recognition though so not sure how well it would work for us. Here's the open cv documentation on it: http://docs.opencv.org/3.0.0/d5/d54/group__objdetect.html

[francisli91]

I've briefly used the Haar Feature-based Cascade Classifier for facial detection - it is a standard way to do facial detection and works rather well. Perhaps we can train it for other objects.

If we're doing clustering, perhaps we can look into doing mean-shift clustering as a pre-process step. It is kind of like an averaging filter and makes the image look kind of 'cartoony' e.g. http://www.mathworks.com/matlabcentral/fileexchange/screenshots/9672/original.jpg
Though I wouldn't recommend it for real-time usage.

[benjaminwinger]

Mean shift clustering is essentially accomplishing what k-means clustering is, though the algorithm is different. Wikipedia says that mean shift is generally slower than kmeans, the advantage of mean shift being that you don't have to choose the number of clusters like with kmeans. It may not be bad in our case, since if we have the cluster number set too high with k-means it may end up choosing a target as a cluster if it is large enough or if the rest of the image is largely uniform.

Haar cascade classifiers are generalizable using OpenCV. There's a tutorial on training a classifier here.

What we should probably do is implement all of the possible methods of target identification and once we've set up a testing framework do a detailed comparison of their speed and accuracy.