22
$\begingroup$

Two months ago, I asked a question here

And @nikie give me a solution:

The intuitive way to understand ListCorrelate is that the kernel is "moved" to every position in the array, and the sum of the products between the kernel values and the array values at that position is stored in the output array:

I make a graphic to show this process as shown below:

the process

However, I cannot understand this built-in function (contain $\{K_L,K_R\}$) when it works for 2-dimensional data.

For example,

$\{K_L,K_R\}=\{2,2\}$

ListCorrelate[
  {{x, y, z}, {u, v, w}}, 
  {{a, b, c, d}, {e, f, g, h}, {i,j, k, l}},
  {2, 2}]

result

$\{K_L,K_R\}=\{2,3\}$ or $\{K_L,K_R\}=\{1,3\}$ or $\{K_L,K_R\}=\{-1,3\}$

According this result, I figure the picture:

diagram

However, I cannot find the regulation, namely, how does ListCorrelate pad?

Update

Thanks for @DumpsterDoofus's solution, I know how the ListCorrelate work in 1-dimensional data when it contains ${k_L,k_R}$ (as shown below)

the ListCorrelate work in 1-dimensional data when it contains $\{k_L,k_R\}$

one-dimensional case

And now my main confusion is ListCorrelate works in 2-dimensional data.

Is there a analogous graphic to show the process in 2-dimensional data?

$\endgroup$
  • $\begingroup$ Why did you get rid of your reputation? Are you going to wind up your account? $\endgroup$ – Artes Mar 10 at 12:33
  • $\begingroup$ @Artes I just wanna share the points to people that ever help me. $\endgroup$ – xyz Mar 10 at 12:34
  • $\begingroup$ It's all right, but a bit original to offer nine or so of the highest bounties in three days. This is why I'm curious. $\endgroup$ – Artes Mar 10 at 12:41
  • $\begingroup$ @Artes I have not use Mathematica for 3 years. And very happy to learn much from here. $\endgroup$ – xyz Mar 10 at 12:43
21
+600
$\begingroup$

$K_L$ and $K_R$ represent positions in the kernel, specifically the positions of the kernel elements that overlap the first and last array elements. Here's an example showing the correlation of a 5×5 array with a 2×3 kernel, with each element of the result showing the overlapping kernel position. The array is in red and the kernel in grey. Here we are using the default "no-overhang" values KL={1,1} and KR={-1,-1} (note that the positions are lists of length 2, as we are specifying a position in a 2D kernel. When we use KL=1 that's just a shorthand for KL={1,1})

enter image description here

Referring to the image above, we can see that in the top left corner, the kernel element {1,1} (KL) overlaps the top left element of the array. And in the bottom right corner the kernel element {-1,-1} (KR) overlaps the bottom right element of the array.

Now suppose we want a 2D correlation where the kernel overhangs by one element on the left hand side. Like this:

enter image description here

What should KL and KR be to get this? Look at the top left corner - the kernel element {1,2} is overlapping the top left element of the array, so we need KL={1,2}. And in the bottom right corner kernel element {-1,-1} overlaps the bottom right array element so we still have KR={-1,-1}.

Hopefully it will be no surprise that KL=-1, KR=1 gives "maximal overhang" on all sides. This is shorthand for KL={-1,-1} and KR={1,1}, so the kernel element {-1,-1} overlaps in the top left and element {1,1} overlaps in the bottom right:

enter image description here

The padding option just determines how to deal with the parts of the kernel that hang outside of the array. You can imagine the array surrounded by zeros or by copies of itself (the default "periodic" padding) or whatever other values you specify. But for understanding KL and KR forget the padding and just look at which kernel elements overlap the first and last array elements.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wow,+2, this solution is what I have been looking for.Thanks a lot! :-) $\endgroup$ – xyz Nov 8 '14 at 2:12
5
$\begingroup$

It becomes slightly easier if you look at 1-dimensional data first. Here's an example:

KER = Table[k[i], {i, 5}];
LIST = Table[l[i], {i, 8}];
ListCorrelate[KER, LIST, {2, 4}]

which produces:

{k[2] l[1] + k[3] l[2] + k[4] l[3] + k[5] l[4] + k[1] l[8], 
 k[1] l[1] + k[2] l[2] + k[3] l[3] + k[4] l[4] + k[5] l[5], 
 k[1] l[2] + k[2] l[3] + k[3] l[4] + k[4] l[5] + k[5] l[6], 
 k[1] l[3] + k[2] l[4] + k[3] l[5] + k[4] l[6] + k[5] l[7], 
 k[1] l[4] + k[2] l[5] + k[3] l[6] + k[4] l[7] + k[5] l[8], 
 k[5] l[1] + k[1] l[5] + k[2] l[6] + k[3] l[7] + k[4] l[8]}

To understand this output it helps to introduce some notation: given a list $l$ and a kernel $k$ of length $M$, define

$$F(j)=\sum_{\ell=1}^M k_{\ell}l_{\ell+j}$$

where the subscripts are interpreted modulo the length of the corresponding list. We then have

$$\text{ListCorrelate}\left[k,l,\{K_L,K_R\}\right]=\{F(-K_L+1),F(-K_L+2),...,F(K_R)\}.$$

In short, it is a partial cyclic correlation; $K_L$ determines how far to the left the correlation hangs, $K_R$ determines how far right the correlation hangs, and the resulting list has $K_L+K_R$ elements.

In particular, we have the following identity:

$$\text{ListCorrelate}\left[k,l\right]=\text{ListCorrelate}\left[k,l,\{1,M\}\right]$$

which relates the default behavior of ListCorrelate with the behavior with overhang lengths specified.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Firstly ,thanks for your solution, I know how the ListCorrelate work in 1-dimensional when it contains $\{k_L,k_R\}$, and now my mainly confusion is ListCorrelate works in 2-dimensional . $\endgroup$ – xyz Nov 6 '14 at 3:17
  • $\begingroup$ @ShutaoTang: See Simon Wood's answer for an explanation of the 2D case. $\endgroup$ – DumpsterDoofus Nov 8 '14 at 0:14
  • $\begingroup$ OK, @DumpsterDoofus I got it.:) $\endgroup$ – xyz Nov 8 '14 at 2:13
4
$\begingroup$

If you want to understand the built-in function when it contains $\{K_L,K_R\}$

For the example you mention,

$\{K_L,K_R\}=\{2,2\}$

ListCorrelate[
  {{x, y, z}, {u, v, w}}, 
  {{a, b, c, d}, {e, f, g, h}, {i,j, k, l}},
  {2, 2}]

The best way is to split it up in simpler ListCorrelate functions.

ker = {{x, y, z}, {u, v, w}}
list = {{a, b, c, d}, {e, f, g, h}, {i, j, k, l}}

first row of the outcome is generated by starting with $K_L$ which means to start with ker[[2]] , at the position in list after skipping the first correlation of ker[[1]] (in case of a kernel with length 3, this means to start at list position 4). This can easily be shown with:

Total@
   (Flatten@      
      {
       ListCorrelate[ker[[2]], list[[1, {4, 1, 2}]]], 
       ListCorrelate[ker[[1]], list[[3, {4, 1, 2}]]]
      })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]], list[[1, {1, 2, 3}]]], 
       ListCorrelate[ker[[1]], list[[3, {1, 2, 3}]]]
       })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]],list[[1, {2, 3, 4}]]], 
       ListCorrelate[ker[[1]],list[[3, {2, 3, 4}]]]
      })

Total@
   (Flatten@
      {
       ListCorrelate[ker[[2]], list[[1, {3, 4, 1}]]], 
       ListCorrelate[ker[[1]], list[[3, {3, 4, 1}]]]
      })

(* OUT *)

d u + a v + b w + l x + i y + j z

a u + b v + c w + i x + j y + k z

b u + c v + d w + j x + k y + l z

c u + d v + a w + k x + l y + i z

In this way you I hope can see how the 'list' and 'kernel' are rotated and can expand the example up until the last row which uses $K_R$ = 2, or again ker[[2]].

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.