Computing over image windows

14 views
Skip to first unread message

C Gosch

unread,
Nov 9, 2018, 12:44:12 PM11/9/18
to Accelerate
Hello everybody,

I am trying to write a function using Accelerate that is mapping over 2D arrays (like images) and
that for each of a number of grid points, computes a value using a window around that point (or any other array elements).
So far, I could only come up with a function that resulted in nested parallelism; is there a canonical way to do these kind of things?

I know about stencils, but I would need more freedom as to how large the windows are (that should be dynamic) and as to the shape of the windows.

Any help is appreciated, best regards
Christian

Trevor McDonell

unread,
Nov 9, 2018, 1:02:22 PM11/9/18
to accelerat...@googlegroups.com

Hi Christian!

Can you provide a bit more information about what you are trying to do, or link to some code? gist.github.com is good for posting snippets.

How large are the windows you are interested in?

In stencil, the shape of the window is just set by the dimensionality of the input array. Note that you are not required to use all of the elements within the stencil region; it just specifies the local neighbourhood you have access to. (I’m not sure if that is what you meant by the shape of the window?)

Maybe you can write a small scalar loop using while to do what you want at each point of interest? (Mind you I’m not sure if that is a good approach in the context of your actual application, since I don’t have any details there and am just guessing…)

All the best,
-Trev


--
You received this message because you are subscribed to the Google Groups "Accelerate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to accelerate-hask...@googlegroups.com.
Visit this group at https://groups.google.com/group/accelerate-haskell.
For more options, visit https://groups.google.com/d/optout.

Henning Thielemann

unread,
Nov 9, 2018, 1:59:42 PM11/9/18
to 'C Gosch' via Accelerate

On Fri, 9 Nov 2018, 'C Gosch' via Accelerate wrote:

> Hello everybody,
> I am trying to write a function using Accelerate that is mapping over 2D arrays (like images) and
> that for each of a number of grid points, computes a value using a window around that point (or any other array
> elements).
> So far, I could only come up with a function that resulted in nested parallelism; is there a canonical way to do
> these kind of things?

How about adding two dimensions to the array for the coordinates within
the window? That is, if your window is m times n then add two inner
dimensions of size m and n and mirror the window pixels into these
dimensions.

b ! (Z :. y :. x :. yw :. xw) = a ! (Z :. y+yw :. x+xw)

Then (slice b (Z:.y:.x:.All:.All)) gives you the window around the pixel
at (y,x). You may encode a convolution as a fold over the two inner
dimensions.

C Gosch

unread,
Nov 11, 2018, 2:41:48 PM11/11/18
to accelerat...@googlegroups.com
Thanks Henning -- that sounds like it may work for connected windows.


C Gosch

unread,
Nov 11, 2018, 2:57:53 PM11/11/18
to accelerat...@googlegroups.com
Hi Trevor,

I have some code on my other laptop; essentially there are two things I would like to be able to do:
One is to run convolution with larger windows (which may arguably be done in Fourier space), I think Henning's response is geared toward that. I am aware of Stencil, and that works perfectly for smaller windows.

Secondly, I would like to be able to compute on rectangular windows in an image around each pixel
from a sparse set of pixels. This is in the context of computing a matching score for points in image pairs,
using something very simple, such as cross correlation.

The third thing I would like to be able to do is this:
For each point in an array (or a sparse set of points), compute a function that uses arbitrary samples from the image. That means,
the function itself should be able to sample from the image at indices that it generates itself.
I know the latter is possible when I write a kernel e.g. in Metal, but is there a way in Accelerate?
A while ago I was playing with Repa, and I think there was a way to do that there by giving the function that is mapped over an array, as an argument a function to access other points in the array.

Sorry if that sounds a bit convoluted (no pun intended) :)
Christian

C Gosch

unread,
Nov 13, 2018, 1:27:54 AM11/13/18
to Accelerate
Hm, I tried to find a way to do what you proposed in Accelerate; maybe I'm just to inexperienced with
this library, but I was not able to find an obvious way to do this.
Can you explain how that is done using Accelerate?

Thanks a lot again,
Christian

Henning Thielemann

unread,
Nov 13, 2018, 3:33:24 AM11/13/18
to 'C Gosch' via Accelerate

On Mon, 12 Nov 2018, 'C Gosch' via Accelerate wrote:

> Hm, I tried to find a way to do what you proposed in Accelerate; maybe
> I'm just to inexperienced with this library, but I was not able to find
> an obvious way to do this. Can you explain how that is done using
> Accelerate?

You should be able to create the extended array b from a using
'backpermute'.

C Gosch

unread,
Nov 18, 2018, 6:45:41 PM11/18/18
to Accelerate
Hi Henning,

ah .. stupid me. This seems to work fine for me for now, thanks a lot again for your suggestions!
By the way, I realized we have met before, at HaL in Halle I think in 2011 (don't quote me on it).
Nice chatting with you again.

Best,
Christian
Reply all
Reply to author
Forward
0 new messages