Tuesday, August 30, 2011

Thursday, August 18, 2011

Why Opencv is so fast

Convolution is the basis of many computer visions algorithms and straightforward algorithm to implement in C, but in the comparison of various implementations Opencv clearly comes out as the winner.

For the convolution of a 5x5 kernel with a 1000x1000 image of type float32 (time in ms):

opencv 5.43189048767
nidimage 36.602973938

And this factor of performance is visible in the implementations of other libraries as well, e.g. leptonica, theano.

It has been a goal of scikits.image to operate without too many explicit dependencies, so pulling in a fast convolution algorithm has been stated as a very desired goal.

The reason why opencv performs so well, is because of its use of SSE operators. In convolution where we apply the same operation on multiple data items the gains in perfomance are considerable.

The following command for example,

__m128 t0 = _mm_loadu_ps(S);

loads 4 values from the S pointer into the 128 bit register t0, and all operations on on this register operate on these values in parallel.

s0 = _mm_add_ps(s0, s1);


I have implemented a SSE based float32 convolution routine and though a bit slower than opencv, it diminishes the performance gap considerably. Each type needs some additional work, including support for row and column separable convolutions. With this we will get a good foundation for a fast convolution implementation.

Benchmark of current results for the test case:

scikits.image 11.029958725
opencv 5.04112243652
scipy.ndimage 43.2901382446

Wednesday, July 20, 2011

Video work

I've added video reading support with Opencv and GStreamer backends.

camera =CvVideo("test.avi")
#or camera = GstVideo("test.avi")
image = camera.get()

Extending the backend system to support switching classes would be great, similar to the way we handle functions but in a Video("test.avi", backend="opencv") kind of way.
The Opencv video duration retrieval methods are currently broken in Linux, but I implemented it anyway for when they fix it in the future. Until then, the functionality is there in GStreamer. Both implementations also play IP camera streams, so between them you are pretty much set to handle most cameras/codecs.

Monday, July 4, 2011

Backend Testing

The following is a code snippet of our testing system for Python Nose tests:

class TestSobel(BackendTester):
def test_00_00_zeros(self):
"""Sobel on an array of all zeros"""
result = F.sobel(np.zeros((10, 10), dtype=np.float32))
assert (np.all(result == 0))


When we inherit from BackendTester, tests are generated for all the implemented backends. If you have a missing dependency, the test will be skipped.

Friday, June 17, 2011

Low barrier to entry

An emphasis for our backend system has been to offer a real low barrier to entry for adding new backend functions. Therefore we have tried to avoid unnecessary configuration files, just a module that you drop in each submodules backend directory with naming convention doing all the rest.

Documentation for each function is updated to indicate what backends are available. To do that though without importing a module, we have resorted to quick parsing of the function definitions of a module.

At the start of the execution, the source tree is scanned and scikits.image.backends is populated with all found backends. This can be used for backend exploration.

use_backend("opencv")
use_backend(scikits.image.backends.opencv)

Scikits.image already has a IO plugin system with very similar though slightly more complicated infrastructure, and in the future it may be wise to merge the two systems. This will require two tiers of backends one for visualization and one for processing.

Wednesday, June 8, 2011

Decorators

We have looked at a few variations on the backend decorator theme, one uses the keyword argument style while another uses import techniques (with no resulting overhead). The importing style proved to be a bit unpythonic though, so we are going with a more explicit backend manager.

How we will handle documentation of a function and its backend is also a topic of discussion. The backend function documentation should be made available if that backend is in use, or at least a good indication that this backend is the one at service.

I also started with some color conversion backends, and I've found that implementations differ to some extent. HSV for example is handled quite arbitrarily between frameworks and this will hamper comparative testing. Even gray scale conversion offers subtle differences.

Monday, May 30, 2011

Initial backend work

We have started with the backend system. To recap, it will enable us to provide implementation backings for functions from various frameworks.

I've started with the Sobel operation, and implemented it in both opencv and opencl. At the same time I've reworked the numpy version as well so that identical results can be obtained. With different implementations at your disposable a great benefit is the way that you can test and benchmark different algorithms.

The working idea for now is to make a decorator that one can add to functions:

@add_backends
def sobel(image):
    # numpy implementation
    ...

This will add an optional backend implementation parameter to the function that the function will try to use:

# use the opencv sobel implementation
sobel(image, backend="opencv")
# use the opencl implementation on an available gpu
sobel(image, backend="opencl")

If the specified implementation is not found, we fall back to the default numpy backend. For global backend selections we are thinking of something in the following line:

use_backend("opencl")

This will try to use opencl wherever possible.

An alternative thought to our current setup is to specify it more explicitly:

opencv.sobel(image)

The following week we will try to finalize this API and implement a few more functions.

Saturday, April 30, 2011

Accepted for the Google Summer of Code!

Our proposal was accepted for the Google Summer of Code 2011.
Now it is time to tool up and cover some groundwork before we begin!

Sunday, April 17, 2011

Edges

Edge detection has always played some part in my illumination invariant algorithms, so I thought it would be a good idea to try getting it into the Scikit. The CellProfiler project has released their algorithms, so I've ported it together with its well written tests. It is rudimentary but a good foundation for a start.

Interestingly the Sobel functions of opencv and ndimage gives different results, perhaps a good idea to look a bit into the source to see what differs.
My branch is hosted at the following location:
Pull request and commit for this patch:

Friday, April 8, 2011

GSOC2011

This is my proposal to improve scikits.image for the Google Summer of Code 2011.

Multiple computational backend support

While scikits.image is currently built on NumPy, leveraging the graphical processing unit (GPU) by using PyOpenCL (http://mathema.tician.de/software/pyopencl) would provide a significant speed increase for certain parallelizable algorithms.

Similarly, other libraries such as CorePy (http://www.corepy.org) and Theano (http://deeplearning.net/software/theano) provide benefits over NumPy under certain circumstances.

To leverage these libraries, a backend system will be implemented whereby algorithms can easily be run on different libraries or devices. For example, we could execute a color conversion on the GPU as:


from scikits.image import backend

rgb2hsv(x, backend=backend('opencl'))


Video Input and Output

The scikit has excellent input/output plugin facilities, but currently does not support video reading, writing or display. Existing open source video reader libraries will be wrapped using Cython (http://cython.org), whereafter the existing ImageCollection class can be modified to display them. The possibility of wrapping a camera acquisition library can be investigated.


Image Processing Algorithms

The number of algorithms provided by the library is currently limited. The addition of certain key algorithms would increase its usefulness dramatically. I propose adding the following algorithms, implemented in Cython:

  • Feature detection (probabilistic Hough transform, STAR, FAST)

  • Segmentation (graph cuts and watershed)

  • Geometrical transformations (distortion removal)

This goal seems ambitious, but for many algorithms existing wrappers exist which may be re-used, for example code from CellProfiler at MIT’s Broad Institute (released under a BSD license).


Documentation

To improve adoption of the project, I’d like to write an introductory tutorial and improve the existing documentation.