function out = hybridsynthesize(data,overlap,knn_in)
%
% |----------------------------------------------------------|
% | Hybrid Texture Synthesis MATLAB package                  |
% |                                                          |
% | Author: Andrew Nealen                                    |
% |         Discrete Geometric Modeling Group                |
% |         Technische Universitaet Darmstadt, Germany       |
% |                                                          |
% | Note:   This is part of the prototype implementation     |
% |         accompanying our paper/my thesis                 |
% |                                                          |
% |         Hybrid Texture Synthesis. A. Nealen and M. Alexa |
% |         Eurographics Symposium on Rendering 2003         |
% |                                                          |
% |         Hybrid Texture Synthesis. A. Nealen              |
% |         Diplomarbeit (MSc), TU Darmstadt, 2003           |
% |                                                          |
% |         See the paper/thesis for further details.        |
% |----------------------------------------------------------|
%
% HYBRIDSYTHESIZE adaptive patch sampling with 'overlap resynthesis' 
%                 improvement strategy (wrapper for hybridsynthesizerec.m)
%
%   [out] = hybridsynthesize(data,overlap,knn_in)
%
%   This subroutine will synthesize a texture from an input
%   sample T (stored in 'data'), and use patches of corner length 
%   psr/psc (in pixels, stored in 'data').
%   it extends image quilting to using a technique which we title
%   'overlap resynthesis', this is implemented to reduce aliasing 
%   artifacts due to insufficient neighborhood matching along patch edges. 
%   also, this algorithm implements 'adaptive patch sampling', where we 
%   split a patch into four patches when the smallest lapping error is above 
%   patch_delta_max (a value in [0,1] stored in 'data').
%
%   IMPORTANT:
%   generate input 'data' by using gen_input.m
%
%   INPUT:
%
%   'data' is an input structure with (among other settings) the following information:
%
%     T - the input texture (upper left is at coord (1,1) in matlab)
%     rows/cols - the number of pixel rows and columns in the final image
%     errtol - added to miniumum error. assures diversity at the cost of 
%              possible bad matches. set to 0 to choose only best match, 1 to pick random
%     feather - set to 1 to smoothly blend the valid overlap pixels. 
%               setting to 0 results in no feathering
%     mode - possible values are 'wrap' and 'nowrap' (defines the wrapping properties
%            of the input texture T). can cause excessive verbatim copying.
%     pixel_delta_max - sqaured error for which we validate pixels in the overlap region,
%          setting to 0 resynthesizes the entire overlap region on a per fragment
%          basis. increasing pixel_delta_max, in the interval of [0,1], trades off 
%          overlap feathering (see 'feather') for per-pixel resynthesis.
%          setting to 1 results in pure overlap feathering.
%     patch_delta_max - mamal allowed error for patch lapping. set to 1 for no 
%                       adaptive splitting.
%     psr/psc - initial patch size (ps) for rows (r) and cols (c).
%     metric - the metric used for lapping error computation. possible values are
%              'simple', 'src', 'dst', 'sum' and 'sqdiff'
%
%     see gen_input.m for more info on the input structure ('data')
%
%   furthermore:
%
%   overlap - the number of overlap pixels, determining overlap width (starting with psr/6 
%             or psc/6 is a reasonable value)
%
%   OPTIONAL:
%   knn_in  - a k-nearest neighbors structure for the input texture T of size N x k
%             with N = rows_t x cols_t (flattened indices, row major (see build_knn.m)
%             if this is passed in, the algorithm implicitly uses k-coherence search
%             (as opposed to exhaustive, fft-based search) for per-pixel synthesis.
%             NOTE: see build_knn.m
%
%   OUTPUT:
%   out - the final synthesized image
%
%   !!! IMPORTANT USAGE NOTES:
%   - the input 'data' can be generated by using function 'gen_input'
%   - the corner lengths (psr/psc) should be powers of 2 (2^r,2^c) for 
%     (recursive) splitting purposes
%   - 'psr' ('psc') should be an integer fraction of 'rows' ('cols')
%   - 'data' should always be initially generated by gen_input, after
%     which the user can modify the values in the datastructure
%

% make sure input is ok
if (size(overlap,1) ~= 1 | size(overlap,2) ~= 1),
    disp('the input value for overlap must be a single integer');
    out  = zeros(1);
    return;
end

% global figure handle
%global pos1;

% global result (out) and intermediate (pre) image
global out;
global pre;

% global source map (for ashikhmin/k-coherence search)
global source_map;

% global k-nearest neighbors for each pixel in T (flattened, scanline-order)
% see build_knn.m
global knn;
if (exist('knn_in')),
    % if knn-data exists, use ashikhmin/k-coherence search in overlap resynthesis ...
    nbhd = num2str(2*data.knn_overlap+1);
    disp(strcat('ashikhmin/k-coherence per-pixel search with k=',num2str(data.k),...
        ', and a box-shaped nbhd=',nbhd,'x',nbhd));
    knn = knn_in;
else
    % ... otherwise default to exhaustive, fft-based search
    nbhd = num2str(2*data.exh_overlap+1);
    disp(strcat('exhaustive, fft-based per-pixel search with a box-shaped nbhd=',...
        nbhd,'x',nbhd));
    knn = 0;
end

% some global magic (pixelvalue) numbers
global NOT_YET_SYNTHESIZED;
global PER_FRAGMENT_SYNTH;
NOT_YET_SYNTHESIZED = -1;
PER_FRAGMENT_SYNTH  = -2;

% -----------------------------------------------------------------------------------------
% ALGORITHM STEP: initialization
% -----------------------------------------------------------------------------------------
out  = zeros(data.rows, data.cols, 3); % used for final result (and for intermediate display)
pre  = zeros(data.rows, data.cols, 3); % used as initializer/computational image

% NOTE: after the algorithm completes, 'pre' and 'out' are identical. we only carry 'out'
%       along to display the algorithm progress, since the initializer values in
%       'pre' are outside the valid image range of [0,1] and cannot be displayed using
%       matlab's IMSHOW

% global source map (for ashikhmin acceleration)
% holds the (flattened, scanline-order) index for the selected pixel in 'out'
% initialize with random (flattened) indices in 1...N with N = RxC
% IMPORTANT!!! -> later, we will consider the sources of the box-shaped 
% neighborhood for the potential candidate list, but will only compare 
% to the valid (i.e. already synthesized) pixels in the output image for picking
% the best pixel
N = data.rows*data.cols;
source_map = zeros(data.rows,data.cols);
for r=1:data.rows,
    for c=1:data.cols,
        source_map(r,c) = ceil(rand*N);
    end
end

%  initialize processed image ('pre') to invalid value (NOT_YET_SYNTHESIZED)
%  pre(j,i,1) is NOT_YET_SYNTHESIZED where the final image (out) has no valid pixel 
%  values yet. we also hold 'out' as a valid image format, initialized to 'pure red' 
%  where no synthesis has taken place, so we can display the progress of the algorithm
for j=1:size(out,1),
    for i=1:size(out,2),
        pre(j,i,1) = NOT_YET_SYNTHESIZED;
        out(j,i,1) = 1;
    end
end

% figure positioning stuff
bdwidth = 30; topbdwidth = 90;
set(0, 'Units', 'pixels');
scnsize = get(0, 'ScreenSize');
pos1 = [bdwidth, 2/3*scnsize(4)+bdwidth,...
        scnsize(3)/3 - 2*bdwidth, scnsize(4)/3 - (topbdwidth + bdwidth)];
%figure(1); set(1, 'Position', pos1);

% -----------------------------------------------------------------------------------------
% ALGORITHM STEP: generate initial patch list
% -----------------------------------------------------------------------------------------
num_row_patches = data.rows/data.psr;
num_col_patches = data.cols/data.psc;
if((num_row_patches-fix(num_row_patches)) ~= 0 |...
        (num_col_patches-fix(num_col_patches)) ~= 0),
    disp('ERROR: check that psr/psc is integer fraction of rows/cols. aborting.');
    return;
end

% initialize the top level patch mesh. make it wrap. add offset if we want to start/end
% elsewhere than upper left corner.
[patchlist.V,patchlist.F,patchlist.BB] =...
    gentoroidalquadmeshoffset(data.psr,data.psc,num_row_patches,num_col_patches,0,0);

% -----------------------------------------------------------------------------------------
% ALGORITHM STEP: start recursive procedure. get result and mean square 
%                 error (mean square lapping error) of all patches
% -----------------------------------------------------------------------------------------
err = hybridsynthesizerec(data,overlap,patchlist);

disp(strcat('done. total error:',num2str(err)));
