1## Copyright (C) 2000 Dave Cogdell <cogdelld@asme.org>
2## Copyright (C) 2000 Paul Kienzle <pkienzle@users.sf.net>
3## Copyright (C) 2012 Carnë Draug <carandraug+dev@gmail.com>
4##
5## This program is free software: you can redistribute it and/or modify
6## it under the terms of the GNU General Public License as published by
7## the Free Software Foundation, either version 3 of the License, or
8## (at your option) any later version.
9##
10## This program is distributed in the hope that it will be useful,
11## but WITHOUT ANY WARRANTY; without even the implied warranty of
12## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13## GNU General Public License for more details.
14##
15## You should have received a copy of the GNU General Public License
16## along with this program; see the file COPYING. If not, see
17## <https://www.gnu.org/licenses/>.
18
19## -*- texinfo -*-
20## @deftypefn  {Function File} {} xcorr2 (@var{a})
21## @deftypefnx {Function File} {} xcorr2 (@var{a}, @var{b})
22## @deftypefnx {Function File} {} xcorr2 (@dots{}, @var{scale})
23## Compute the 2D cross-correlation of matrices @var{a} and @var{b}.
24##
25## If @var{b} is not specified, computes autocorrelation of @var{a}, i.e.,
26## same as @code{xcorr (@var{a}, @var{a})}.
27##
28## The optional argument @var{scale}, defines the type of scaling applied to the
29## cross-correlation matrix. Possible values are:
30##
31## @table @asis
32## @item "none" (default)
33## No scaling.
34##
35## @item "biased"
36## Scales the raw cross-correlation by the maximum number of elements of @var{a}
37## and @var{b} involved in the generation of any element of @var{c}.
38##
39## @item "unbiased"
40## Scales the raw correlation by dividing each element in the cross-correlation
41## matrix by the number of products @var{a} and @var{b} used to generate that
42## element.
43##
44## @item "coeff"
45## Scales the normalized cross-correlation on the range of [0 1] so that a value
46## of 1 corresponds to a correlation coefficient of 1.
47## @end table
48##
49## @seealso{conv2, corr2, xcorr}
50## @end deftypefn
51
52function c = xcorr2 (a, b, biasflag = "none")
53
54  if (nargin < 1 || nargin > 3)
55    print_usage;
56  elseif (nargin == 2 && ischar (b))
57    biasflag = b;
58    b        = a;
59  elseif (nargin == 1)
60    ## we have to set this case here instead of the function line, because if
61    ## someone calls the function with zero argument, since a is never set, we
62    ## will fail with "`a' undefined" error rather that print_usage
63    b = a;
64  endif
65  if (ndims (a) != 2 || ndims (b) != 2)
66    error ("xcorr2: input matrices must must have only 2 dimensions");
67  endif
68
69  ## compute correlation
70  [ma,na] = size(a);
71  [mb,nb] = size(b);
72  c = conv2 (a, conj (b (mb:-1:1, nb:-1:1)));
73
74  ## bias routines by Dave Cogdell (cogdelld@asme.org)
75  ## optimized by Paul Kienzle (pkienzle@users.sf.net)
76  ## coeff routine by Carnë Draug (carandraug+dev@gmail.com)
77  switch lower (biasflag)
78    case {"none"}
79      ## do nothing, it's all done
80    case {"biased"}
81      c = c / ( min ([ma, mb]) * min ([na, nb]) );
82    case {"unbiased"}
83      lo   = min ([na,nb]);
84      hi   = max ([na, nb]);
85      row  = [ 1:(lo-1), lo*ones(1,hi-lo+1), (lo-1):-1:1 ];
86
87      lo   = min ([ma,mb]);
88      hi   = max ([ma, mb]);
89      col  = [ 1:(lo-1), lo*ones(1,hi-lo+1), (lo-1):-1:1 ]';
90
91      bias = col*row;
92      c    = c./bias;
93
94    case {"coeff"}
95      a = double (a);
96      b = double (b);
97      a = conv2 (a.^2, ones (size (b)));
98      b = sumsq (b(:));
99      c(:,:) = c(:,:) ./ sqrt (a(:,:) * b);
100
101    otherwise
102      error ("xcorr2: invalid type of scale %s", biasflag);
103  endswitch
104
105endfunction
106
107%!test  # basic usage
108%! a = magic (5);
109%! b = [6 13 22; 10 18 23; 8 15 23];
110%! c = [391  807  519  391  473  289 120
111%!      920 1318 1045  909 1133  702 278
112%!      995 1476 1338 1534 2040 1161 426
113%!      828 1045 1501 2047 2108 1101 340
114%!      571 1219 2074 2155 1896  821 234
115%!      473 1006 1643 1457  946  347 108
116%!      242  539  850  477  374  129  54];
117%! assert (xcorr2 (a, b), c);
118
119%!shared a, b, c, row_shift, col_shift
120%! row_shift = 18;
121%! col_shift = 20;
122%! a = randi (255, 30, 30);
123%! b = a(row_shift-10:row_shift, col_shift-7:col_shift);
124%! c = xcorr2 (a, b, "coeff");
125%!assert (nthargout ([1 2], @find, c == max (c(:))), {row_shift, col_shift});   # should return exact coordinates
126%! m = rand (size (b)) > 0.5;
127%! b(m)  = b(m)  * 0.95;
128%! b(!m) = b(!m) * 1.05;
129%! c = xcorr2 (a, b, "coeff");
130%!assert (nthargout ([1 2], @find, c == max (c(:))), {row_shift, col_shift});   # even with some small noise, should return exact coordinates
131
132%!test  # coeff of autocorrelation must be same as negative of correlation by additive inverse
133%! a = 10 * randn (100, 100);
134%! auto    = xcorr2 (a, "coeff");
135%! add_in  = xcorr2 (a, -a, "coeff");
136%! assert ([min(auto(:)), max(auto(:))], -[max(add_in(:)), min(add_in(:))]);
137