Distance transform on image using NumPy
up vote
3
down vote
favorite
I would like to find the find the distance transform of a binary image in the fastest way possible without using the scipy function distance_transform_edt(). The image is 256 by 256. The reason I don't want to use scipy is because using it is difficult in Tensorflow. Every time I want to use this package I need to start a new session and this takes a lot of time. So I would like to make a custom function that only utilizes NumPy.
My approach is as follows: Find the coordinated for all the ones and all the zeros in the image. Find the euclidian distance between each of the zero pixels (a) and the one pixels (b) and then the value at each (a) position is the minimum distance to a (b) pixel. I do this for each 0 pixel. The resultant image has the same dimensions as the original binary map. My attempt at doing this is shown below.
I tried to do this as fast as possible using no loops and only vectorization. But my function still can't work as fast as the scipy package can. When I timed the code it looks like the assignment to the variable "a" is taking the longest time. But I do not know if there is a way to speed this up.
If anyone has any other suggestions for different algorithms to solve this problem of distance transforms or can direct me to other implementations in python, it would be very appreciated.
def get_dst_transform_img(og): #og is a numpy array of original image
ones_loc = np.where(og == 1)
ones = np.asarray(ones_loc).T # coords of all ones in og
zeros_loc = np.where(og == 0)
zeros = np.asarray(zeros_loc).T # coords of all zeros in og
a = -2 * np.dot(zeros, ones.T)
b = np.sum(np.square(ones), axis=1)
c = np.sum(np.square(zeros), axis=1)[:,np.newaxis]
dists = a + b + c
dists = np.sqrt(dists.min(axis=1)) # min dist of each zero pixel to one pixel
x = og.shape[0]
y = og.shape[1]
dist_transform = np.zeros((x,y))
dist_transform[zeros[:,0], zeros[:,1]] = dists
plt.figure()
plt.imshow(dist_transform)
python performance algorithm image numpy
edited Dec 11 at 19:29
200_success
128k15149412
asked Dec 11 at 19:19
user186901
161
add a comment |
up vote
3
down vote
favorite
I would like to find the find the distance transform of a binary image in the fastest way possible without using the scipy function distance_transform_edt(). The image is 256 by 256. The reason I don't want to use scipy is because using it is difficult in Tensorflow. Every time I want to use this package I need to start a new session and this takes a lot of time. So I would like to make a custom function that only utilizes NumPy.
My approach is as follows: Find the coordinated for all the ones and all the zeros in the image. Find the euclidian distance between each of the zero pixels (a) and the one pixels (b) and then the value at each (a) position is the minimum distance to a (b) pixel. I do this for each 0 pixel. The resultant image has the same dimensions as the original binary map. My attempt at doing this is shown below.
I tried to do this as fast as possible using no loops and only vectorization. But my function still can't work as fast as the scipy package can. When I timed the code it looks like the assignment to the variable "a" is taking the longest time. But I do not know if there is a way to speed this up.
If anyone has any other suggestions for different algorithms to solve this problem of distance transforms or can direct me to other implementations in python, it would be very appreciated.
def get_dst_transform_img(og): #og is a numpy array of original image
ones_loc = np.where(og == 1)
ones = np.asarray(ones_loc).T # coords of all ones in og
zeros_loc = np.where(og == 0)
zeros = np.asarray(zeros_loc).T # coords of all zeros in og
a = -2 * np.dot(zeros, ones.T)
b = np.sum(np.square(ones), axis=1)
c = np.sum(np.square(zeros), axis=1)[:,np.newaxis]
dists = a + b + c
dists = np.sqrt(dists.min(axis=1)) # min dist of each zero pixel to one pixel
x = og.shape[0]
y = og.shape[1]
dist_transform = np.zeros((x,y))
dist_transform[zeros[:,0], zeros[:,1]] = dists
plt.figure()
plt.imshow(dist_transform)
python performance algorithm image numpy
edited Dec 11 at 19:29
200_success
128k15149412
asked Dec 11 at 19:19
user186901
161
1
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
You could just try to copy the code from thescipyfunction. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.
– Graipher
Dec 12 at 10:45
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I would like to find the find the distance transform of a binary image in the fastest way possible without using the scipy function distance_transform_edt(). The image is 256 by 256. The reason I don't want to use scipy is because using it is difficult in Tensorflow. Every time I want to use this package I need to start a new session and this takes a lot of time. So I would like to make a custom function that only utilizes NumPy.
My approach is as follows: Find the coordinated for all the ones and all the zeros in the image. Find the euclidian distance between each of the zero pixels (a) and the one pixels (b) and then the value at each (a) position is the minimum distance to a (b) pixel. I do this for each 0 pixel. The resultant image has the same dimensions as the original binary map. My attempt at doing this is shown below.
I tried to do this as fast as possible using no loops and only vectorization. But my function still can't work as fast as the scipy package can. When I timed the code it looks like the assignment to the variable "a" is taking the longest time. But I do not know if there is a way to speed this up.
If anyone has any other suggestions for different algorithms to solve this problem of distance transforms or can direct me to other implementations in python, it would be very appreciated.
def get_dst_transform_img(og): #og is a numpy array of original image
ones_loc = np.where(og == 1)
ones = np.asarray(ones_loc).T # coords of all ones in og
zeros_loc = np.where(og == 0)
zeros = np.asarray(zeros_loc).T # coords of all zeros in og
a = -2 * np.dot(zeros, ones.T)
b = np.sum(np.square(ones), axis=1)
c = np.sum(np.square(zeros), axis=1)[:,np.newaxis]
dists = a + b + c
dists = np.sqrt(dists.min(axis=1)) # min dist of each zero pixel to one pixel
x = og.shape[0]
y = og.shape[1]
dist_transform = np.zeros((x,y))
dist_transform[zeros[:,0], zeros[:,1]] = dists
plt.figure()
plt.imshow(dist_transform)
python performance algorithm image numpy
edited Dec 11 at 19:29
200_success
128k15149412
asked Dec 11 at 19:19
user186901
161
I would like to find the find the distance transform of a binary image in the fastest way possible without using the scipy function distance_transform_edt(). The image is 256 by 256. The reason I don't want to use scipy is because using it is difficult in Tensorflow. Every time I want to use this package I need to start a new session and this takes a lot of time. So I would like to make a custom function that only utilizes NumPy.
My approach is as follows: Find the coordinated for all the ones and all the zeros in the image. Find the euclidian distance between each of the zero pixels (a) and the one pixels (b) and then the value at each (a) position is the minimum distance to a (b) pixel. I do this for each 0 pixel. The resultant image has the same dimensions as the original binary map. My attempt at doing this is shown below.
I tried to do this as fast as possible using no loops and only vectorization. But my function still can't work as fast as the scipy package can. When I timed the code it looks like the assignment to the variable "a" is taking the longest time. But I do not know if there is a way to speed this up.
If anyone has any other suggestions for different algorithms to solve this problem of distance transforms or can direct me to other implementations in python, it would be very appreciated.
def get_dst_transform_img(og): #og is a numpy array of original image
ones_loc = np.where(og == 1)
ones = np.asarray(ones_loc).T # coords of all ones in og
zeros_loc = np.where(og == 0)
zeros = np.asarray(zeros_loc).T # coords of all zeros in og
a = -2 * np.dot(zeros, ones.T)
b = np.sum(np.square(ones), axis=1)
c = np.sum(np.square(zeros), axis=1)[:,np.newaxis]
dists = a + b + c
dists = np.sqrt(dists.min(axis=1)) # min dist of each zero pixel to one pixel
x = og.shape[0]
y = og.shape[1]
dist_transform = np.zeros((x,y))
dist_transform[zeros[:,0], zeros[:,1]] = dists
plt.figure()
plt.imshow(dist_transform)
python performance algorithm image numpy
python performance algorithm image numpy
edited Dec 11 at 19:29
200_success
128k15149412
asked Dec 11 at 19:19
user186901
161
edited Dec 11 at 19:29
200_success
128k15149412
asked Dec 11 at 19:19
user186901
161
edited Dec 11 at 19:29
200_success
128k15149412
edited Dec 11 at 19:29
200_success
128k15149412
edited Dec 11 at 19:29
200_success
128k15149412
128k15149412
asked Dec 11 at 19:19
user186901
161
asked Dec 11 at 19:19
user186901
161
asked Dec 11 at 19:19
user186901
161
161
1
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
You could just try to copy the code from thescipyfunction. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.
– Graipher
Dec 12 at 10:45
add a comment |
1
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
You could just try to copy the code from thescipyfunction. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.
– Graipher
Dec 12 at 10:45
1
1
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
You could just try to copy the code from the
scipy function. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.– Graipher
Dec 12 at 10:45
You could just try to copy the code from the
scipy function. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.– Graipher
Dec 12 at 10:45
add a comment |
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209466%2fdistance-transform-on-image-using-numpy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209466%2fdistance-transform-on-image-using-numpy%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
This post is double-posted on SO, and answered there.
– Cris Luengo
Dec 12 at 5:55
You could just try to copy the code from the
scipyfunction. There are two imports used as far as I can tell, one is a normal Python file in the same folder, the other one is written in C and needs to be compiled, though.– Graipher
Dec 12 at 10:45