[sac-user] SaC syntax for array boundaries

Robert Bernecky bernecky at snakeisland.com
Mon Feb 15 20:54:14 CET 2016


Hi, Rob,

As I mentioned in my earlier message to you, the term
"nearest" is vague, particularly at the corners.
I find that being precise in the statement of the problem
often leads to insights into approaches to solving the problem.

Let's back up a bit: What problem are you trying to solve?
I.e., is this an image filtering problem, perhaps?

Your problem is, essentially, a convolution on each row
of a matrix. Depending on the application, a few common ways of
dealing with the edge values are:

  - clamp the edge result values to the input edge values.
    I.e., the result values for the edges match the input values for
    the edges.

  - compute the edge result values as if they were interior values
    on a larger input array, padded on all sides with:

       - zero or other useful constant
      or
       - the element(s) from the opposite end of the matrix,
         as if it were toroidal in shape. [Note that this does not
         define how to treat the corner values.]
      or
       - copies of the edge values.
      or
       ...

I have found that an APLish approach often works quite well
in SAC: construct a Boolean mask, b, that matches the input array, M,
in shape, with zeros at the edges, and ones at the interior points.
Then, the result is merely:

     z = (tod( b) * filterkernel(M)) +
         (tod(!b) * edgekernelfilter(M));

With any luck, the above computations will all WL-fold into
a WL with one partition for the interior, and one or more partitions
for the edges.

I have attached the Bernecky-Scholz PLDI2015 paper that shows a
one-dimensional version of this at work.

Bob


On 16-02-15 12:19 PM, Rob Stewart wrote:
> Thanks Bodo,
> 
> That's slightly more involved than I was anticipating.
> 
> The function I'd like to implement is:
> 
>> blur_x(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3;
> 
> At each position. How, by using your shiftRight and shiftLeft functions
> below, could I implement:
> 
> int[*] blurX(int[*] array)
> 
> The the boundary condition of mirroring the nearest element.
> 
> Moreover for the definition:
> 
> blur_y(x, y) = (input(x, y-1) + input(x, y) + input(x, y+1))/3;
> 
> How, using shiftRight and shiftLeft, could I implement:
> 
> int[*] blurY(int[*] array)
> 
> Such that I could compose them easily, e.g.
> 
> b = blurX ( blurY ( blurX ( a ) ) );
> 
> ?
> 
> --
> Rob
> 
> On 15/02/2016 at 16:44 Scholz, Sven-Bodo writes:
> 
>> You would have to define your own generic mechanism, e.g.:
>>
>>
>> use Array: all;
>> use StdIO: all;
>>
>>
>> inline
>> int[*] shiftRight( int dimension, int[*] hyperplane, int[*] array)
>> {
>>   dim_cut = modarray( 0*shape(array), dimension, 1);
>>   res = with {
>>          (0*shape( array) <= iv < dim_cut) : hyperplane[drop([dimension+1], iv)];
>>          (dim_cut <= iv < shape(array) ) : array[modarray( iv, dimension, iv[dimension]-1)];
>>         } : modarray( array);
>>   return res;
>> }
>>
>> inline
>> int[*] shiftLeft( int dimension, int[*] hyperplane, int[*] array)
>> {
>>   dim_cut = modarray( shape(array), dimension, shape(array)[dimension]-1);
>>   res = with {
>>          (0*shape( array) <= iv < dim_cut) : array[modarray( iv, dimension, iv[dimension]+1)];
>>          (dim_cut <= iv < shape(array) ) : hyperplane[drop([dimension+1], iv)];
>>         } : modarray( array);
>>   return res;
>> }
>>
>> int main() {
>>
>>   int[10,10] a;
>>
>>   a = reshape([10,10], iota( 100));
>>
>>   print(a);
>>
>>   d = shiftRight( 0, a[0], a) + a + shiftLeft( 0, a[9], a) ;
>>
>>   print(d);
>>
>>   return 0;
>> }
>>
>>
>> One could envision arbitrary versions of shift that perform the insertion you want.
>>
>>
>> Alternatively, you could use a[ max( [o,o], iv-1) ]    for the selection and then define all elements that way…..
>> most likely with some performance penalty though….
>>
>> Bodo
>>
>>
>>> On 15 Feb 2016, at 15:46, Stewart, Robert <R.Stewart at hw.ac.uk> wrote:
>>>
>>> Hi Bodo, Artem,
>>>
>>> Say I wanted to implemented blur_x in SaC, which at each pixel does:
>>>
>>> blur_x(x, y) = (input(x-1, y) + input(x, y) + input(x+1, y))/3;
>>>
>>> The important bit: at the edges of the array I want to mirror the
>>> nearest array element.
>>>
>>> On a 10x10 array. I could do this for the sub region between (1,1) and
>>> (8,8):
>>>
>>> b = with {
>>>      ( [1,0] <= [x,y] < [9,10]) : a[x-1,y] + a[x,y] + a[x+1,y] ;
>>>    } : modarray(a);
>>>
>>> Then:
>>>
>>> c = with {
>>>      ( [0,0] <= [x,y] < [0,10]) : a[x,y] + a[x,y] + a[x+1,y] ;
>>>    } : modarray(b);
>>>
>>> d = with {
>>>      ( [9,0] <= [x,y] < [10,10]) : a[x-1,y] + a[x,y] + a[x,y] ;
>>>    } : modarray(c);
>>>
>>> Is there shorthand in SaC for clamping nearest pixel elements at the
>>> border of a 2D array, to apply stencils that fall beyond array
>>> boundaries?
>>>
>>> Thanks,
>>>
>>> --
>>> Rob
> _______________________________________________
> sac-user mailing list
> sac-user at sac-home.org
> http://lists.sac-home.org/mailman/listinfo/sac-user
> 


-- 
Robert Bernecky
Snake Island Research Inc
18 Fifth Street
Ward's Island
Toronto, Ontario M5J 2B9

bernecky at snakeisland.com
tel: +1 416 203 0854

-------------- next part --------------
A non-text attachment was scrubbed...
Name: paper.pdf
Type: application/pdf
Size: 81030 bytes
Desc: not available
URL: <http://lists.sac-home.org/pipermail/sac-user/attachments/20160215/26ffaa19/attachment.pdf>


More information about the sac-user mailing list