Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Techniques for in-memory acceleration of scikit-image functions #10

Open
mrocklin opened this issue May 21, 2018 · 6 comments
Open

Techniques for in-memory acceleration of scikit-image functions #10

mrocklin opened this issue May 21, 2018 · 6 comments

Comments

@mrocklin
Copy link
Member

mrocklin commented May 21, 2018 •
edited
Loading

In https://github.com/scikit-image/scikit-image/wiki/UC-Berkeley-(BIDS)-sprint,-May-28-Jun-2-2018 scikit-image devs write the following objective:

work on the parallelization of some algorithms to improve performance, focusing maybe first on the case of machines with several cores

There are probably a few ways to achieve this:

  1. Parallel programming mechanisms within Cython

  2. Parallelizing operations with overlapping domains with functions like da.map_overlap

    http://dask.pydata.org/en/latest/array-ghost.html

  3. Embarrassingly parallel operations over, for example, stacks of images

  4. Rewrite some algorithms to avoid excessive memory use

  5. Consider using Numba (see Investigate using Numba within Scikit-Image #9)

@stefanv @emmanuelle @jni @kne42 @jakirkham
@emmanuelle
Copy link

In order to get an idea of which functions take the longest time to execute, I've written a simple script to execute all functions of scikit-image (almost all of them, those with a single non-keyword argument) on 1000x1000 and 4000x4000 images. The script is https://github.com/emmanuelle/skimage-sprint/blob/master/benchmark_skimage.py

@emmanuelle
Copy link

And the output is here

function name  1000x1000 (s) 4000 x 4000 (s)
order_angles_golden_ratio 1.5820041880942881e-06 1.3740063877776265e-06
pyramid_laplacian 2.038999809883535e-06 2.049004251603037e-06
pyramid_gaussian 3.373002982698381e-06 2.7860005502589047e-06
img_as_ubyte 3.707995347213e-06 9.119998139794916e-06
invert 8.161900041159242e-05 0.0019422420009505004
hessian_matrix_eigvals 0.0001217419994645752 0.010738437005784363
img_as_bool 0.00017211600061273202 0.002036489997408353
dtype_limits 0.000177570000232663 7.536200428148732e-05
img_as_uint 0.0001946500051417388 0.004587891002302058
img_as_float32 0.0005660879978677258 0.028035934003128204
moments_hu 0.0006392470022547059 0.04105230799905257
threshold_mean 0.0006504839984700084 0.010182017002080102
unique_rows 0.0009700149967102334 0.025093265998293646
img_as_float64 0.0011418929934734479 0.05300714600161882
img_as_float 0.0012039230059599504 0.05176752900297288
is_low_contrast 0.0019830750024993904 0.03078262700000778
moments 0.0021918849961366504 0.06323738799983403
img_as_int 0.002340591003303416 0.039925568002217915
centroid 0.0027759529984905384 0.05770436300372239
threshold_yen 0.00308390300051542 0.07896760300354799
threshold_isodata 0.0031663679983466864 0.08060623300116276
regionprops 0.003312683002150152 0.05274687599739991
moments_central 0.0035911910017603077 0.11994485199829796
inertia_tensor_eigvals 0.004306473005271982 0.12313450299552642
inertia_tensor 0.004435836999618914 0.11800956200022483
cumulative_distribution 0.004628459995728917 0.07664868199935881
threshold_triangle 0.004814849999092985 0.07862083500367589
histogram 0.005222961000981741 0.07671320399822434
remove_small_objects 0.00564464800118003 0.10340420799911954
threshold_otsu 0.005656451001414098 0.09468782500334783
adjust_gamma 0.005796907003968954 0.08713734699995257
binary_erosion 0.006340839005133603 0.10116303100221558
roberts_pos_diag 0.006819407004513778 0.16811347799375653
rescale_intensity 0.007098617003066465 0.13121031199989375
threshold_li 0.0076990099987597205 0.130684645002475
binary_dilation 0.008432052003627177 0.13217282199912006
label 0.00852108999970369 0.18191857099736808
dilation 0.008548391997464933 0.13689996099856216
scharr_v 0.008617122999567073 0.20457357700070133
prewitt_v 0.008636899998236913 0.20390668300387915
relabel_sequential 0.008781475000432692 0.17905225599679397
shannon_entropy 0.008863214003213216 0.16472001900547184
sobel_v 0.009289729001466185 0.1983102379963384
laplace 0.009692168001492973 0.2109651020000456
integral_image 0.00993309400655562 0.4099128989983001
erosion 0.010141922000912018 0.16486640800576424
remove_small_holes 0.010388347996922676 0.20070177200250328
roberts_neg_diag 0.010667030001059175 0.16767271300341235
equalize_hist 0.010949996998533607 0.19283514600101626
scharr_h 0.011591768001380842 0.20086948199605104
adjust_log 0.011799407999205869 0.21127869600604754
sobel_h 0.011800329994002823 0.20289843600039603
prewitt_h 0.012467783002648503 0.20232361699891044
peak_local_max 0.012902177004434634 0.6169858400025987
binary_opening 0.01438260599388741 0.2256378680031048
gaussian 0.014572945001418702 0.4035357009997824
binary_closing 0.014764310995815322 0.23084263900091173
clear_border 0.014840408999589272 0.23890565100009553
white_tophat 0.018658321001566947 0.36532218000502326
closing 0.018690986005822197 0.298772050999105
estimate_sigma 0.019138827999995556 0.5767053489980754
perimeter 0.019193760002963245 0.34547738400578965
roberts 0.01929068599565653 0.42091855999751715
opening 0.01952228500158526 0.28466637899691705
find_boundaries 0.01959003700176254 0.30622119899635436
rank_order 0.020321311996667646 0.4259337850016891
black_tophat 0.021625324996421114 0.2979806239964091
pyramid_reduce 0.021672442999260966 0.5187376629983191
prewitt 0.02306484199652914 0.4878450860051089
median 0.023534564999863505 0.3854890369984787
scharr 0.02386966100311838 0.48736922499665525
adjust_sigmoid 0.0240844450017903 0.41007384000113234
sobel 0.02445847100170795 0.4877438399998937
corner_fast 0.024688117002369836 0.39655747499637073
corner_moravec 0.03714942999795312 0.6685943539996515
hessian_matrix_det 0.03941447000397602 0.716864127003646
corner_kitchen_rosenfeld 0.04089961200224934 1.2105924540010164
hessian_matrix 0.0426930009998614 1.1756715160008753
random_noise 0.05140691000269726 0.8992877540003974
equalize_adapthist 0.05178537100437097 0.739087408001069
denoise_wavelet 0.05607400900044013 1.4170424129988533
shape_index 0.06344841700047255 1.7304453139950056
structure_tensor 0.06410771799710346 1.799445274999016
convex_hull_image 0.06760330100223655 1.416709417993843
threshold_niblack 0.06874862300173845 1.5447136430011597
corner_shi_tomasi 0.0704145050040097 1.9788300119980704
corner_harris 0.07319289400038542 1.948151467993739
threshold_sauvola 0.07328394999785814 1.5270891500040307
corner_foerstner 0.076296082996123 1.9690196290030144
inverse_gaussian_gradient 0.08535292600572575 1.731628206995083
canny 0.10476821399788605 2.1550492129972554
skeletonize 0.10783256000286201 7.3660553180015995
hough_line 0.13461809400178026 3.683965532996808
swirl 0.137581949995365 2.9712439970026026
local_maxima 0.14133706600114238 2.8922174730032566
unwrap_phase 0.1498056389973499 2.4318994929999462
local_minima 0.16337000900239218 3.2404415550045087
skeletonize_3d 0.1770735350000905 8.405797448998783
pyramid_expand 0.1774391039944021 3.8492587030050345
hog 0.19873329900292447 3.4330161370016867
medial_axis 0.24623131300177192 9.650262839000789
corner_peaks 0.3557854530008626 6.070875867997529
slic 0.3907627309963573 6.815546577003261
denoise_tv_chambolle 0.44250795799598563 9.765179585003352
blob_doh 0.5569545350008411 11.360353389994998
hessian 0.6042380700018839 13.89035327199963
frangi 0.6053614679985913 13.7607722190005
felzenszwalb 0.9909110170046915 50.248761565002496
convex_hull_object 1.382232694006234 57.99437347300409
thin 1.5165445329985232 137.09647026900348
blob_dog 1.7475284499960253 30.783051873004297
daisy 2.5314105299985385 58.24184620199958
denoise_nl_means 3.3063822820040514 67.17348862299696
blob_log 4.322434088993759 75.12872078899818
iradon 4.79451753700414 512.5343781369957
probabilistic_hough_line 5.272198466998816
radon 7.824015924001287
frt2 11.070842119996087
chan_vese 68.08258557799854

@mrocklin
Copy link
Member Author

mrocklin commented May 27, 2018 via email

@emmanuelle
Copy link

I think the answer will depend on users. Actually, I would love to have data about which functions of scikit-image are used the most, I don't know if some packages have tried to get such data (like having a repo with image processing scripts contributed by users and parsing them fir usage stats).

As for me, denoise_nl_means would be very useful, and daisy as well (I'm using daisy to compute local features for segmenting images). Maybe feature.daisy can be accelerated with prange over orientations.

I think your list is very useful, maybe we could start considering if algorithms could be changed / accelerated (for example do we really need tv_chambolle since tv_bregman is faster? Or is it faster just before the accuracy is not the same? I don't know.) And then look for possible prange and embarrassingly parralel loops. And then consider chunking for functions in which the result would be unchanged (functions using local kernels).

@emmanuelle
Copy link

I also wrote a script to save logs of the line profiler, so that we can see where the time is mostly spent. It's https://github.com/emmanuelle/skimage-sprint/blob/master/profile_skimage.py

@emmanuelle
Copy link

The above script should be improved to look also at the cython functions called by python functions, but it's a first start :-).

@jni jni mentioned this issue Jun 19, 2018
Closed
9 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@emmanuelle @mrocklin