function outcell = wordcat( rects, fun )
% WORDCAT Determine word collinearity using an iterative greedy algorithm
%
%   OUTCELL = WORDCAT( RECTS ) where RECTS is the Nx4
%   matrix, where N is the number of words in the image, representing
%   the word rectangles. Each row is of the form [ x y width height ].
%   OUTCELL is a cell with the connected words.  Each entry in the
%   cell is a vector representing a connected component, containing
%   indices into RECTS representing the collinear words in order. 
%
%   For example, if the first line of connected words used the third,
%   fourth, and eigth rectangles of the boxdata, then OUTCELL{1} =
%   [3,4,8].
%
%   WORDCAT( RECTS, FUN) where FUN is the scoring
%   function the sortedcat algorithm will use to determine how well
%   two rectangles will work as a predecessor, successsor pair. This
%   function should take the 1X4 [x y width height] vector for the two
%   rectangles to be compared, and output the score.  
%
%   WORDCAT uses the method described in Section 3 of the following article:
%
%     J. Weinman, Z. Butler, D. Knoll, and J. Feild, Toward Integrated Scene Text
%     Reading. IEEE TPAMI 36(2):375--387, 2014.doi:10.1109/TPAMI.2013.126
%     
%   This algorithm locates best possible successors for each rectangle
%   in order to determine which are connected by sorting the scores
%   from best to worst and assigning pairs with the best scores first,
%   preventing any particular rectangle from becoming too "greedy" and
%   taking a rectangle that should belong to another.
%
%   See also DISTFXN

% $Id$
 
% Jerod Weinman, Zach Butler, Dugan Knoll, Alexander Turner, Yirong Jing
% jerod@acm.org
% Copyright 2011, 2012, 2013, 2014
 
%    This file is part of PIONEER WordNorm.
%
%    PIONEER WordNorm is free software: you can redistribute it and/or modify
%    it under the terms of the GNU General Public License as published by
%    the Free Software Foundation, either version 3 of the License, or
%    (at your option) any later version.
%
%    PIONEER WordNorm is distributed in the hope that it will be useful,
%    but WITHOUT ANY WARRANTY; without even the implied warranty of
%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%    GNU General Public License for more details.
%
%    You should have received a copy of the GNU General Public License
%    along with PIONEER WordNorm.  If not, see <http://www.gnu.org/licenses/>.

% Copyright (c) 2012-2014
% Jerod Weinman
% jerod@acm.org

if nargin<2
  fun = @distfxn;
end;

% Set number of words so we don't have to compute it later
n = size(rects,1);

% Check for the case of no text
if(n == 0)
    outcell = cell(0);
    return;
end;

% The vectors of successors and predecessors
successors = zeros(1, n);
predecessors = zeros(1, n);

% The vector of scores
scores = -Inf * ones(n);


% Assign scores -- this should be done with a mapping (like bintprogcat)
for k=1:n;
    for m=1:n;
        if(k ~= m)
           scores(k,m) = fun(rects(k,:), rects(m,:));
        end;
    end;
end;

% Sort the scores (this should use the 'descend' option)
valids = sort(-1 .* mkvector(scores(scores ~= -Inf)));

% Assign successors
for k=1:size(valids);
    % Find the rows and columns of candidate pairs with this score
    [preds,succs] = find(scores == -1*valids(k));
    for m=1:size(preds)
        % If either has already been assigned, don't assign again
        if(predecessors(preds(m)) || successors(succs(m)))
            continue;
        end;
        % Assign the predecessors and the successors
        successors(succs(m)) = preds(m);
        predecessors(preds(m)) = succs(m);
    end;
end;

% Form connected component matrices and put them in outcell
cellcount = 1;
% For every rectangle that has no predecessor (ie is head of a chain of
% neighbors)
for s=find(predecessors == 0)
    t = s;
    outmtx = [];
    % Start forming the matrix that will determine this connected component
    while(t)
        outmtx(end+1) = t;
        t = successors(t);
    end;
    outcell{cellcount} = outmtx;
    cellcount = cellcount + 1;
end;


