scikit-learn/scikit-learn — pull request #1419 by eickenberg (2012-11-27 15:44:42+00:00)
Title: Faster patch extraction

This is a very small contribution to the patch extraction method implemented in sklearn.feature_extraction.image:

Using stride tricks, a numpy array of dimension n is augmented to a "patch indexer" array of dimension 2n, where the first n indices indicate the location of the patch and the last n dimensions index the patch itself.

Up until there nothing changes in memory (except for shape and strides).

If one then calls a reshape on this array, ravelling the first n dimensions into 1 dimension, numpy proceeds to copy the data, effectively extracting patches and placing them in a list. Since this happens inside numpy, it is a lot faster than extraction using a for loop.

A benchmark on the patch extraction for the MiniBatchDictionaryLearning example shows a speed up of factor 16-17:

100x extract_patches_2d (old) ~ 20 seconds
100x extract_patches_2d (new) ~ 1.3 seconds

My only concern/question is: Will numpy always handle reshaping of strided arrays by copying? If not, this whole thing may be slightly unstable.

Otherwise, the extractor extends to any dimension, permits easy views on arrays and seems to me to have a rather general use, actually.

Thanks in advance for your time!