Closed Bug 1004208 Opened 10 years ago Closed 10 years ago

Explore using canny edge detection before calculating entropy

Categories

(Testing Graveyard :: Eideticker, defect)

x86_64
Linux
defect
Not set
normal

Tracking

(Not tracked)

RESOLVED FIXED

People

(Reporter: wlach, Assigned: ffledgling)

References

Details

Attachments

(3 files, 2 obsolete files)

Background: http://wrla.ch/blog/2014/03/its-all-about-the-entropy/

Currently in eideticker we run sobel edge detection (http://en.wikipedia.org/wiki/Sobel_operator) on the frames of the capture before measuring entropy. Code here: 

https://github.com/mozilla/eideticker/blob/master/src/videocapture/videocapture/entropy.py#L12

Canny edge detection (http://en.wikipedia.org/wiki/Canny_edge_detector) generally seems to give better results according to research literature, and would let us probably measure entropy in each frame more accurately, leading to more stable results. 

This bug is about exploring that option. There are a number of existing implementations of the canny edge detector in scikit-imaging and opencv. We should experiment with integrating those into Eideticker, or maybe writing our own?

To play with this, you'll probably want to try applying the algorithm to existing frames in eideticker and visualizing the results. ipython notebooks would be a useful tool for this, here's an example of one I used to debug a problem earlier this week:

http://nbviewer.ipython.org/url/people.mozilla.com/~wlachance/square-diff.ipynb

CC'ing ffledgling, because he seemed interested in exploring eideticker image processing. Feel free to needinfo me in this bug or contacting me on irc #ateam (wlach) if you have more questions. :)
Here's an example capture you can manipulate and run tests on. See the above ipython notebook for code examples:

http://people.mozilla.org/~wlachance/b2g-contacts-scrolling-capture.zip
Attached image edge_comparison.png
So this is from the first round of experiments, in general as wlach said, canny is much better than sobel at detecting edges, but there is variation among the results based on the implementation we use.

Here's an ipython notebook with code snippets and some comments: http://nbviewer.ipython.org/url/web.iiit.ac.in/~anhadjai.singh/eideticker.ipynb


In general OpenCV's implementation yields cleaner results vis-a-vis SciKit-Image's results, but SciKit-Image seems to be able to extract more "elements" from the image.
For example we see the alphabets to the side of the screen in the SciKit version but not in the OpenCV version. There's a noise vs. edge-clarity trade off.


In terms of performance Canny should be slower than the sobel based method because it is slightly more sophisticated in what it does and also because Sobel is typically a substep of the Canny process.

OpenCV seems to be much faster because of the C/C++ implementation behind the scenes.
The SciKit versions fall in line with our prediction regarding the speed, i.e Canny slower than Sobel, but I suspect some of the slowness in the SciKit methods we're using may atleast in part be attributed to the numpy manipulations that we're doing in memory.

Stats:

In [3]: timeit _cannyOpenCV(I)                                                                 
100 loops, best of 3: 11.5 ms per loop

In [4]: timeit _cannySciKit(I)
1 loops, best of 3: 644 ms per loop

In [5]: timeit _sobel(I)
1 loops, best of 3: 525 ms per loop

Although at this point in time OpenCV's Canny implementation sounds appealing, we might want to run the analysis for more frames and compare the results manually to decide which one is better.
My main concern at the moment is that Canny (especially the OpenCV version) might remove valid elements in it's quest for noise removal.


Compatibility Update on OpenCV (requested by wlach):

OpenCV is available for Ubuntu 12.04 (Precise) as per [1] 
The version available in the repos is 2.3.1-7, although I've been writing code against 2.4.7-2, API docs[2] tell me that the functions we need are available in 2.3.* as well, so it should not be a problem.


[1] http://packages.ubuntu.com/search?keywords=opencv&searchon=names&suite=precise&section=all

[2] http://docs.opencv.org/2.3/modules/imgproc/doc/feature_detection.html?highlight=canny#cv2.Canny
Ok, I think the OpenCV one looks very promising. So the next step is to experiment with the entropy values per-frame when we replace our existing sobel algorithm with the canny edge detector.

I think the way I'd like to do this would be to change the code to optionally apply a canny filter to the input data instead of a sobel one. The code that does this is mostly here:

https://github.com/mozilla/eideticker/blob/master/src/videocapture/videocapture/entropy.py#L10

Running: "git grep sobel" will show you where the sobel filter is called -- change this to reference canny stuff instead, then rerun get_frame_entropies on the capture I gave and let me know what the results are. :)
This is a comparison of the entropy graphs generated by Sobel and Canny edge detectors.
Here's an iPython notebook demonstrating the code: http://nbviewer.ipython.org/url/web.iiit.ac.in/~anhadjai.singh/eideticker2.ipynb

On the whole as expected the Canny edge-detector yeilds less noisy and cleaner entropy plots.
Patch to add Canny edge detection for entropy calculations in eideticker.
Please take a look and let me know what you think!
Attachment #8417741 - Flags: review?(wlachance)
Assignee: nobody → ffledgling
Comment on attachment 8417741 [details] [diff] [review]
0001-Added-Canny-edge-for-entropy-calculations-Bug-100420.patch

Review of attachment 8417741 [details] [diff] [review]:
-----------------------------------------------------------------

Ok, good stuff. We need to add a few things before this can land:

1. Update the README.md to install whatever opencv packages are required https://github.com/mozilla/eideticker/blob/master/README.md#requirements
2. Add opencv python package to: https://github.com/mozilla/eideticker/blob/master/src/videocapture/setup.py
3. Update the get_stable_frame method to use canny edge detection instead of sobel edge detection: https://github.com/mozilla/eideticker/blob/master/src/videocapture/videocapture/stableframe.py
4. Update the metrics defaults to use canny detection (I think your code actually breaks that, as it stands): https://github.com/mozilla/eideticker/blob/master/src/eideticker/eideticker/metrics.py
5. Update the metrics metadata to store "framecannyentropies" (we can just drop "framesobelentropies") https://github.com/mozilla/eideticker/blob/master/src/eideticker/eideticker/metrics.py#L82
6. Update the dashboard detail view to understand framecannyentropies (I think this just means you need to add a new dictionary element here: https://github.com/mozilla/eideticker/blob/master/src/dashboard/js/common.js#L45)

::: src/videocapture/videocapture/entropy.py
@@ +22,3 @@
>          frame = numpy.hypot(dx, dy)  # magnitude
>          frame *= 255.0 / numpy.max(frame)  # normalize (Q&D)
>  

Delete two spaces here

@@ +62,2 @@
>  
> +def get_entropy_diffs(capture, num_samples=5, edge_detection=None):

Just remove this function, it's not used for anything anymore so it's not worth updating.
Attachment #8417741 - Flags: review?(wlachance) → review-
Updated Patch, please let me know if this needs any further changes.

Re: packages listed in readme, I've added the packages I think should be needed, but you might want to actually install and check once anyway.
Attachment #8417741 - Attachment is obsolete: true
Attachment #8418288 - Flags: review?(wlachance)
Comment on attachment 8418288 [details] [diff] [review]
0002-Added-Canny-edge-for-entropy-calculations-Bug-100420.patch

Review of attachment 8418288 [details] [diff] [review]:
-----------------------------------------------------------------

Looks pretty good, tested it with decent results as well! r+ with review comments addressed, please upload another patch.

(I will need to coordinate landing it with updating the eideticker machines accordingly)

::: README.md
@@ +9,5 @@
>    installed. You can get this by running:
>  
> +    `sudo apt-get install -y zip ffmpeg g++ python-scipy python2.7-dev \
> +    python-virtualenv ntp python-opencv libopencv-core2.3 libopencv-dev \
> +    libopencv-imgproc2.3 libopencv-imgproc-dev libopencv-core-dev python-opencv`

I think you should only need to add python-opencv here. The other deps should be pulled in automatically.

::: src/dashboard/js/common.js
@@ +73,4 @@
>  // default value for detail view: usually frame diff sums, unless we're
>  // looking at entropy, in which case we'll look at the entropy values
>  function getDefaultDetailParameter(measureName, metadata) {
> +  if (measureName === "overallentropy" && metadata.framecannyentropies) {

We should keep the old check for "framesobelentropies", as we'll still have data in the dashboard with this in it after the patch lands. Just separate out this clause as a seperate else if..

::: src/eideticker/eideticker/metrics.py
@@ +57,4 @@
>      if 'overallentropy' in analysis_props['valid_measures']:
>          metrics['overallentropy'] = \
>                                      videocapture.get_overall_entropy(capture,
> +                                         edge_detection=analysis_props['edge_detection'])

Could you align this better?

::: src/videocapture/videocapture/entropy.py
@@ +22,3 @@
>          frame = numpy.hypot(dx, dy)  # magnitude
>          frame *= 255.0 / numpy.max(frame)  # normalize (Q&D)
>  

Remove these two blank lines.
Attachment #8418288 - Flags: review?(wlachance) → review+
New patch with nits fixed. Carrying over r+, but you might want to take a look to make sure everything is okay anyway. Please let me know if anything needs changing.
Attachment #8418288 - Attachment is obsolete: true
Attachment #8418700 - Flags: review+
Looks good, will commit once we've sorted out our Ubuntu situation (bug 1007233).
We probably don't want to land this before bug 1007054, as I don't think we can really install opencv inside the virtualenv.
Depends on: 1007054
Landed this: https://github.com/mozilla/eideticker/commit/7b16e6a35ec9bc58eefa068f072a4de66abd2ba0
Needed one small followup fix: https://github.com/mozilla/eideticker/commit/b9a0f5c39daf4de5ebb5451a8340dbdcb459188e
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Product: Testing → Testing Graveyard
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: