hybridsynthesizerec.m

histogram based code for image retrival

function error = hybridsynthesizerec(data,overlap,patchlist)
%
% |----------------------------------------------------------|
% | 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.        |
% |----------------------------------------------------------|
%
% HYBRIDSYTHESIZEREC adaptive patch quilting with 'overlap resynthesis' 
%                    patch lapping improvement strategy. this is the recursive 
%                    part, thus the use of suffix REC.
%                    this is also the heart of the implementation
%
%   error = hybridsynthesizerec(data,overlap,patchlist)
%
%   This subroutine will synthesize a texture from an input
%   sample data.T, and use patches defined in patchlist.F and patchlist.V 
%   (faces and vertices) in the order they occur in the facelist F.
%   it extends image quilting to using a technique which we title
%   'image completion', 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 patch-lapping error is above data.patch_delta_max
%
%   INPUT:
%   data      - the input 'data' as described in gen_input.m
%   overlap   - the number of overlap pixels
%   patchlist - an indexed face set structure with vertices V, faces F
%               and bounding box data BB (see gentoroidalquadmeshoffset.m
%               and genquadmeshoffset.m)
%
%   OUTPUT:
%   mse - the lapping-error for the patch encountered in this call
%

% 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;

% k-nearest neighbors for each pixel in T (flattened, scanline-order)
% see hybridsynthesize.m and especially build_knn.m. here, we only need it to
% decide whether to use overlap_resynthesis_knn.m or overlap_resynthesis_exh.m
global knn;

% some global magic (pixelvalue) numbers, defined in hybridsynthesize.m
global NOT_YET_SYNTHESIZED;
global PER_FRAGMENT_SYNTH;

% the error, accumulated for each patch (in this call)
error_accum = 0;

% -----------------------------------------------------------------------------------------
% ALGORITHM STEP: iterate through all patches
% -----------------------------------------------------------------------------------------
% iterate through all output patches in order given by face list F
% note: the ordering has major impact on the synthesis results! we need
% causal neighborhoods as much as possible.
for posval=1:length(patchlist.F),

    % pos = patch number, for shifting start patch
    pos = posval;
   
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: compute 'shift'
    % -------------------------------------------------------------------------------------
    % shift patch vertices (tmp data stored in 'patch') so that BB min of 
    % F(pos) is in position(1,1), toroidally
    % BB(pos,1) and BB(pos,2) are upper left BB corner row and col index
    % values in 'shift' will be <= 0 as the BB coords are positive integers >= 1
    % 'original_patch' is a list of patch vertices in clockwise ordering
    original_patch = [patchlist.V(patchlist.F(pos,:),1) patchlist.V(patchlist.F(pos,:),2)];
    shift = [1 1] - [patchlist.BB(pos,1) patchlist.BB(pos,2)];
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: 'shift' patch so min bounding box coord is in (1 1)
    % -------------------------------------------------------------------------------------
    patch = circshiftpatch(original_patch,data.rows,data.cols,shift);

    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: compute binary support for ungrown patch
    % -------------------------------------------------------------------------------------
    % compute binary patch support PS (of size 'out') for the ungrown patch
    % note -> on 'patch-1': subtract 1 from patch coords (making them 0-based) to 
    % compensate for matlab's ROIPOLY fill conventions
    trnpatch = transpose(patch-1);
    PS = roipoly(out, [trnpatch(2,:)], [trnpatch(1,:)]);
    
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: now shift patch and grow by dilation using user-defined 'overlap'
    %                 GPS stands for 'grown patch support' (binary)
    % -------------------------------------------------------------------------------------
    psize = max(patch) - 1;
    deltashift = [overlap overlap];
    GPS = circshift(PS, deltashift);
    GPS = imdilate(GPS, strel('square', 2*overlap+1));
    grownpatchsize = psize + 2*overlap;
    
    % some important error output. if the grown patch is larger than the 
    % input texture T, we must abort...
    if (grownpatchsize(1) > data.rows_t | grownpatchsize(2) > data.cols_t),
        disp('ERROR: grown patch is larger than input texture. aborting...');
        return;
    end
    
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: 'deltashift' ungrown patch support 'PS' as well
    % -------------------------------------------------------------------------------------
    % also, shift PS by deltashift (so the ungrown patches in both PS and GPS are congruent)
    PS = circshift(PS,deltashift);
    
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: shift copy of 'pre' and build binary support J and image mask I
    % -------------------------------------------------------------------------------------
    % circularly shift temporary copy of (globally defined) 'pre' by (shift + deltashift)
    % note: pre is partially synthesized result with values of 
    % (NOT_YET_SYNTHESIZED 0 0) in pixels that are yet to be synthesized
    pre_shift = circshift(pre, shift+deltashift);
    [I,J] = buildimagemask(size(data.T), grownpatchsize, GPS, pre_shift);
    
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: compute error image from I,J, fftS, fftST and fftSTs
    % -------------------------------------------------------------------------------------
    % now we have I, J and all other data (in 'data') and can generate error image for 
    % the image mask to locate the best match (remember, reference point is upper left 
    % corner of support function area and image mask bounding box)
        
    % switch on 'metric' string in 'data' (see gen_input.m)
    switch data.metric
    case 'src'
        errorimg = errorimage_src(data, I, J);
    case 'dst'
        errorimg = errorimage_dst(data, I, J);
    case 'sum'
        errorimg = errorimage_sum(data, I, J);
    case 'sqdiff'
        errorimg = errorimage_sqdiff(data, I, J);
    otherwise
        % this is equivalent to setting metric to 'simple'
        errorimg = errorimage(data, I, J);
    end

    % NOTE: value in max(errorimage) (bottom right corner) is error for picking patch with 
    % BB_grown_min at (1,1) (no shift)

    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: trim errorimg if input T doesn't wrap 
    % -------------------------------------------------------------------------------------
    % trim bottom and right strip of err (if T doesn't wrap) -> (NOTE: 'wrap' CAN 
    % cause excessive verbatim copying if we do not introduce countermeasures)
    if (strcmp('nowrap',data.mode)),
        errorimg = errorimg(1:size(errorimg,1)-grownpatchsize(1)+1,...
            1:size(errorimg,2)-grownpatchsize(2)+1);
    end
        
    % -------------------------------------------------------------------------------------
    % ALGORITHM STEP: find some candidates for picking with low error, but diverse
    % -------------------------------------------------------------------------------------
    % find some candidates depending on user defined 'errtol' and choose one at random
    % must use abs() because rounding errors (can) lead to negative, close-to-zero numbers. 
    min_error = min(errorimg(:));
    minimumerror = abs(min_error);
    error_tolerance = (1 - minimumerror) * data.errtol;
    [jbest, ibest] = find(errorimg <= (error_tolerance+minimumerror));
    
    % choose one at randindex
    randindex = ceil(rand * length(jbest));
    % bestpos is the upper left bounding box corner of best GROWN patch
    bestpos = [jbest(randindex) ibest(randindex)];
    
    % uncomment the following 4 lines to hardcode placement of the first (seed)
    % patch. setting data.errtol to 0 and hardcoding the first patch yields