[WIP] Add distance transform function #4051

leGIT-bot · 2019-07-24T23:21:56Z

Description

New distance transform function
#904
http://www.cs.cornell.edu/~dph/papers/dt.pdf

pull request was recreated due to an 'unknown repository' problem


peakmem_reference                                         172M
peakmem_scipy_2d                                          312M
peakmem_skimage_2d                                     256M
time_scipy_2d                                                   814±0ms
time_skimage_2d                                              925±0ms


peakmem_reference                                         2.9G
peakmem_scipy_3d                                           7.73G
peakmem_skimage_3d                                      9.31G
time_scipy_3d                                                    1.68±0m
time_skimage_3d                                               54.6±0s

Checklist

Docstrings for all functions
Gallery example in ./doc/examples (new features only)
Benchmark in ./benchmarks, if your changes aren't covered by an
existing benchmark
Unit tests
Clean style in the spirit of PEP8

For reviewers

Check that the PR title is short, concise, and will make sense 1 year
later.
Check that new functions are imported in corresponding __init__.py.
Check that new features, API changes, and deprecations are mentioned in
doc/release/release_dev.rst.
Consider backporting the PR with @meeseeksdev backport to v0.14.x

add a modified version of numpy.applyalongaxis as well as a simple test; optional variables can only be set to defult value for now until an input method is decided upon

remove debug warnings

Make the 1D optional inputs compulsary since it will be inaccessible. It works by converting the 1D function to a patial function with the optional upper function inputs filled

Split 1d func into three for speed. Moved auxilary funcs into cython

hmaarrfk · 2019-07-29T01:08:13Z

skimage/transform/_distance_transform.pyx

+            out = INFINITY
+    return out
+
+cdef double manhattan_dist(Py_ssize_t a, double b, double c) nogil:


why is b a double here, while in other cases it is Py_ssize_t

mahattan meet is used by manhattan_dist which can pass an inf value which is a double

euclidean meet does not use euclidean dist

hmaarrfk · 2019-07-29T01:12:00Z

skimage/transform/_distance_transform.pyx

+            out[i] = euclidean_dist(i,centers[current_domain],cost_arr[<Py_ssize_t>centers[current_domain]])
+    return out
+
+def _generalized_distance_transform_1d_manhattan(double[:] arr, double[:] cost_arr,


Is this the same as the code above? maybe look at
https://github.com/scikit-image/scikit-image/blob/master/skimage/transform/_warps_cy.pyx#L156
to see how you can combine the two codes

one of the manhattan functions has a different signature
other than that the code is the same

the code used to be different though

the code used to be different though

funny how that evolves.

Well, I might just do all the meet and distance computation in floats and call it a day. Your benchmarks might be able to show you that it makes no difference.
Generally, when things are the same, they are easier to maintain.

changed it, did the benchmarking and checked
it does make a difference
from mid 40s to about a minute

no. unless you want to write it for arm, ppc64le, arm32bit, arm64bit, x86, x86 64bit

but I admire the enthusiasm.

What would you like to optimize?

I thought that euclidean_dist, euclidean_meet... are very short and called often

What does the Cython look like? The generated C that is?

Vectorization might be better than you think. You might want to try numba or pythran.

I think first cython needs to be merged and then worry about whether others are more efficient

hmaarrfk · 2019-07-29T01:47:14Z

@leGIT-bot i don't want you to do busy work, so I think the big thing that is left to figure out is why your code doesn't perform well small image size case.

You can parametrize your benchamrk (which I recommend) and start profiling your code.

I think you got the GIL release right. so for now, I don't think I can help on that front anymore.

leGIT-bot · 2019-07-29T02:26:56Z

@leGIT-bot i don't want you to do busy work, so I think the big thing that is left to figure out is why your code doesn't perform well small image size case.

You can parametrize your benchamrk (which I recommend) and start profiling your code.

I think you got the GIL release right. so for now, I don't think I can help on that front anymore.

it uses a different algorithm and C
thanks for the help with the gil

SebastienEske · 2019-09-13T08:20:58Z

Hello, just a little comment: does it produce the same (rotated) output if the image is rotated? With this for example?

It's worth testing by rotation increments of 5 degree between 0 and 90 degrees.

I know opencv's distance transform has this issue. So even if this algorithm has it, you can just mention it as a limitation.

imagesc-bot · 2023-11-11T03:26:38Z

This pull request has been mentioned on Image.sc Forum. There might be relevant details there:

https://forum.image.sc/t/expanding-cell-label-boundaries-adaptively/60131/6

leGIT-bot and others added 30 commits February 22, 2019 14:44

added dst tfrm

30057cb

added test

23f1822

get test ready for testing

403e52e

fixed typo

c99698e

changed func name

22d3745

changed func name

2906b35

changed func name

0ca8b42

updated test file

58309e0

removed md alias

915b5ef

testing for manhattan

8bc008d

added distance function flexibility

0cc6439

add func advice

0434bf6

Improve structure. Add tests. Make more efficient

130cb55

start conversion to test_along_axis

bb0d97d

add a modified version of numpy.applyalongaxis as well as a simple test; optional variables can only be set to defult value for now until an input method is decided upon

Update distance_transform.py

a64c6af

remove debug warnings

Allow optional inputs generealised_distance_transform

d288561

Make the 1D optional inputs compulsary since it will be inaccessible. It works by converting the 1D function to a patial function with the optional upper function inputs filled

Update distance_transform.py

aea3268

change all lists to arrays

5c7ed65

improve variable naming

7fd5901

Add cython code

69e8f11

Split 1d func into three for speed. Moved auxilary funcs into cython

prettify code

a508ca5

test code

48f2795

Added some type and other stuff

7a81523

Fix cython

f5c1a52

Semi fix code

b04efe2

Remove bugs. Remove fake inf. Remove new bugs.

5751ae8

Optimised

f1343e1

Remove useless allocation of of loop

4f0ee78

Add test for euc

d030aed

Add benchmarks. Change time limit for benchmarks.

e39dce8

hmaarrfk reviewed Jul 29, 2019

View reviewed changes

leGIT-bot added 3 commits July 29, 2019 11:18

remove comments

b4d5219

nogil the whole thing

a40a927

remove debugging line

604ee03

leGIT-bot added 7 commits July 29, 2019 15:49

fix cython. de-randomise benchmarks

12d2bbb

chnage samplesize

34b3795

Fix sphere error

2002a48

refix sphere error

345267b

generalised function

5da93d6

reduce test time. add implementation choice comments

a65e1c2

regress to old code

9c2e6b0

leGIT-bot added 9 commits November 9, 2019 15:21

some changes

d3befd3

Merge branch 'master' into distance-transform

15b10b3

do type placement. logic is still the same

038f980

fix inf types

1d8b7c8

allow more types

888893f

not working, fused types cotinue

1c85bc6

now there is a different bug

10b85a0

no errors

cc4b605

commit for branch swap

7cd3767

sciunto removed this from the 0.17 milestone Apr 8, 2020

emmanuelle mentioned this pull request Apr 12, 2020

2020's calendar of community management #4486

Closed

Base automatically changed from master to main February 18, 2021 18:23

mkcor mentioned this pull request Feb 22, 2021

2021's calendar of community management #5169

Closed

lagru added the 👶 type: New feature label Feb 29, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

[WIP] Add distance transform function #4051

[WIP] Add distance transform function #4051

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

This comment was marked as off-topic.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

[WIP] Add distance transform function #4051

Are you sure you want to change the base?

[WIP] Add distance transform function #4051

Uh oh!

Conversation

Uh oh!

Description

Checklist

For reviewers

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

This comment was marked as off-topic.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!