NearestNeighborField Class Reference

Inheritance diagram for NearestNeighborField:

Public Member Functions
int	distance (int x, int y, int xp, int yp)
void	EM_Step (MaskedImageSP source, MaskedImageSP target, int R, bool upscaled)
void	initialize (const NearestNeighborField &nnf)
void	minimize (int pass)
void	minimizeLink (int x, int y, int dir)
	NearestNeighborField (const MaskedImageSP _input, MaskedImageSP _output, int _patchsize)
void	randomize (void)
Public Member Functions inherited from KisShared
bool	deref ()
bool	ref ()
int	refCount ()
QAtomicInt *	sharedWeakReference ()

Static Public Member Functions
static MaskedImageSP	ExpectationMaximization (KisSharedPtr< NearestNeighborField > TargetToSource, int level, int radius, QList< MaskedImageSP > &pyramid)
static void	ExpectationStep (KisSharedPtr< NearestNeighborField > nnf, MaskedImageSP source, MaskedImageSP target, bool upscale)

Public Attributes
QList< KoChannelInfo * >	channels
NNArray_type	field
QRect	imSize
MaskedImageSP	input
quint32	nColors
MaskedImageSP	output
std::vector< float >	similarity

Private Member Functions
void	init_similarity_curve (void)
void	initialize (void)
template<typename T >
T	randomInt (T range)

Private Attributes
int	patchSize

Additional Inherited Members
Protected Member Functions inherited from KisShared
	KisShared ()
	~KisShared ()

Detailed Description

Definition at line 516 of file kis_inpaint.cpp.

Constructor & Destructor Documentation

NearestNeighborField()

NearestNeighborField::NearestNeighborField ( const MaskedImageSP _input, MaskedImageSP _output, int _patchsize )

inline

Definition at line 574 of file kis_inpaint.cpp.

                                                                                            : patchSize(_patchsize), input(_input), output(_output)
    {
        imSize = input->size();
        field.resize(boost::extents[imSize.width()][imSize.height()]);
        init_similarity_curve();
 
        nColors = input->channelCount(); //only color count, doesn't include alpha channels
    }

References MaskedImage::channelCount(), field, imSize, init_similarity_curve(), input, nColors, and MaskedImage::size().

Member Function Documentation

distance()

int NearestNeighborField::distance ( int x, int y, int xp, int yp )

inline

Definition at line 686 of file kis_inpaint.cpp.

    {
        qint64 distance = 0;
        qint64 wsum = 0;
        const qint64 ssdmax = nColors * 255 * (qint64)255;
 
        //for each pixel in the source patch
        for (int dy = -patchSize; dy <= patchSize; dy++) {
            for (int dx = -patchSize; dx <= patchSize; dx++) {
                wsum += ssdmax;
                int xks = x + dx;
                int yks = y + dy;
 
                if (xks < 0 || xks >= input->size().width()) {
                    distance += ssdmax;
                    continue;
                }
 
                if (yks < 0 || yks >= input->size().height()) {
                    distance += ssdmax;
                    continue;
                }
 
                //cannot use masked pixels as a valid source of information
                if (input->isMasked(xks, yks)) {
                    distance += ssdmax;
                    continue;
                }
 
                //corresponding pixel in target patch
                int xkt = xp + dx;
                int ykt = yp + dy;
                if (xkt < 0 || xkt >= output->size().width()) {
                    distance += ssdmax;
                    continue;
                }
                if (ykt < 0 || ykt >= output->size().height()) {
                    distance += ssdmax;
                    continue;
                }
 
                //cannot use masked pixels as a valid source of information
                if (output->isMasked(xkt, ykt)) {
                    distance += ssdmax;
                    continue;
                }
 
                //SSD distance between pixels
                float ssd = input->distance(*input, xks, yks, *output, xkt, ykt);
                distance += qRound(ssd);
 
            }
        }
 
        if (wsum == 0) {
            return 0; // sanity check, to avoid undefined behaviour in code below
        }
        return qFloor(MAX_DIST * (qreal(distance) / wsum));
    }

References distance(), MaskedImage::distance, input, MaskedImage::isMasked(), MAX_DIST, nColors, output, patchSize, and MaskedImage::size().

EM_Step()

void NearestNeighborField::EM_Step	(	MaskedImageSP	source,
		MaskedImageSP	target,
		int	R,
		bool	upscaled )

ExpectationMaximization()

MaskedImageSP NearestNeighborField::ExpectationMaximization ( KisSharedPtr< NearestNeighborField > TargetToSource, int level, int radius, QList< MaskedImageSP > & pyramid )

static

Definition at line 830 of file kis_inpaint.cpp.

{
    int iterEM = std::min(2 * level, 4);
    int iterNNF = std::min(5, 1 + level);
 
    MaskedImageSP source = nnf_TargetToSource->output;
    MaskedImageSP target = nnf_TargetToSource->input;
    MaskedImageSP newtarget = nullptr;
 
    //EM loop
    for (int emloop = 1; emloop <= iterEM; emloop++) {
        //set the new target as current target
        if (!newtarget.isNull()) {
            nnf_TargetToSource->input = newtarget;
            target = newtarget;
            newtarget = nullptr;
        }
 
        for (int x = 0; x < target->size().width(); ++x) {
            for (int y = 0; y < target->size().height(); ++y) {
                if (!source->containsMasked(x, y, radius)) {
                    nnf_TargetToSource->field[x][y].x = x;
                    nnf_TargetToSource->field[x][y].y = y;
                    nnf_TargetToSource->field[x][y].distance = 0;
                }
            }
        }
 
        //minimize the NNF
        nnf_TargetToSource->minimize(iterNNF);
 
        //Now we rebuild the target using best patches from source
        MaskedImageSP newsource = nullptr;
        bool upscaled = false;
 
        // Instead of upsizing the final target, we build the last target from the next level source image
        // So the final target is less blurry (see "Space-Time Video Completion" - page 5)
        if (level >= 1 && (emloop == iterEM)) {
            newsource = pyramid.at(level - 1);
            QRect sz = newsource->size();
            newtarget = target->copy();
            newtarget->upscale(sz.width(), sz.height());
            upscaled = true;
        } else {
            newsource = pyramid.at(level);
            newtarget = target->copy();
            upscaled = false;
        }
        //EM Step
 
        //EM_Step(newsource, newtarget, radius, upscaled);
        ExpectationStep(nnf_TargetToSource, newsource, newtarget, upscaled);
    }
 
    return newtarget;
}

References ExpectationStep(), field, input, KisSharedPtr< T >::isNull(), minimize(), output, MaskedImage::size(), source(), target(), and MaskedImage::upscale().

ExpectationStep()

void NearestNeighborField::ExpectationStep ( KisSharedPtr< NearestNeighborField > nnf, MaskedImageSP source, MaskedImageSP target, bool upscale )

static

Definition at line 888 of file kis_inpaint.cpp.

{
    //int*** field = nnf->field;
    int R = nnf->patchSize;
    if (upscale)
        R *= 2;
 
    int H_nnf = nnf->input->size().height();
    int W_nnf = nnf->input->size().width();
    int H_target = target->size().height();
    int W_target = target->size().width();
    int H_source = source->size().height();
    int W_source = source->size().width();
 
    std::vector< quint8* > pixels;
    std::vector< float > weights;
    pixels.reserve(R * R);
    weights.reserve(R * R);
    for (int x = 0 ; x < W_target ; ++x) {
        for (int y = 0 ; y < H_target; ++y) {
            float wsum = 0;
            pixels.clear();
            weights.clear();
 
 
            if (!source->containsMasked(x, y, R + 4) /*&& upscale*/) {
                //speedup computation by copying parts that are not masked.
                pixels.push_back(source->getImagePixel(x, y));
                weights.push_back(1.f);
                target->mixColors(pixels, weights, 1.f, target->getImagePixel(x, y));
            } else {
                for (int dx = -R ; dx <= R; ++dx) {
                    for (int dy = -R ; dy <= R ; ++dy) {
                        // xpt,ypt = center pixel of the target patch
                        int xpt = x + dx;
                        int ypt = y + dy;
 
                        int xst, yst;
                        float w;
 
                        if (!upscale) {
                            if (xpt < 0 || xpt >= W_nnf || ypt < 0 || ypt >= H_nnf)
                                continue;
 
                            xst = nnf->field[xpt][ypt].x;
                            yst = nnf->field[xpt][ypt].y;
                            int dp = nnf->field[xpt][ypt].distance;
                            // similarity measure between the two patches
                            w = nnf->similarity[dp];
 
                        } else {
                            if (xpt < 0 || (xpt / 2) >= W_nnf || ypt < 0 || (ypt / 2) >= H_nnf)
                                continue;
                            xst = 2 * nnf->field[xpt / 2][ypt / 2].x + (xpt % 2);
                            yst = 2 * nnf->field[xpt / 2][ypt / 2].y + (ypt % 2);
                            int dp = nnf->field[xpt / 2][ypt / 2].distance;
                            // similarity measure between the two patches
                            w = nnf->similarity[dp];
                        }
 
                        int xs = xst - dx;
                        int ys = yst - dy;
 
                        if (xs < 0 || xs >= W_source || ys < 0 || ys >= H_source)
                            continue;
 
                        if (source->isMasked(xs, ys))
                            continue;
 
                        pixels.push_back(source->getImagePixel(xs, ys));
                        weights.push_back(w);
                        wsum += w;
                    }
                }
 
                if (wsum < 1)
                    continue;
 
                target->mixColors(pixels, weights, wsum, target->getImagePixel(x, y));
            }
        }
    }
}

References field, input, patchSize, R, similarity, MaskedImage::size(), source(), target(), and upscale.

init_similarity_curve()

void NearestNeighborField::init_similarity_curve ( void )

inlineprivate

Definition at line 545 of file kis_inpaint.cpp.

    {
        float s_zero = 0.999;
        float t_halfmax = 0.10;
 
        float x  = (s_zero - 0.5) * 2;
        float invtanh = 0.5 * std::log((1. + x) / (1. - x));
        float coef = invtanh / t_halfmax;
 
        similarity.resize(MAX_DIST + 1);
        for (int i = 0; i < (int)similarity.size(); i++) {
            float t = (float)i / similarity.size();
            similarity[i] = 0.5 - 0.5 * std::tanh(coef * (t - t_halfmax));
        }
    }

References MAX_DIST, and similarity.

initialize() [1/2]

void NearestNeighborField::initialize ( const NearestNeighborField & nnf )

inline

Definition at line 596 of file kis_inpaint.cpp.

    {
        float xscale = qreal(imSize.width()) / nnf.imSize.width();
        float yscale = qreal(imSize.height()) / nnf.imSize.height();
 
        for (int y = 0; y < imSize.height(); y++) {
            for (int x = 0; x < imSize.width(); x++) {
                int xlow = std::min((int)(x / xscale), nnf.imSize.width() - 1);
                int ylow = std::min((int)(y / yscale), nnf.imSize.height() - 1);
 
                field[x][y].x = nnf.field[xlow][ylow].x * xscale;
                field[x][y].y = nnf.field[xlow][ylow].y * yscale;
                field[x][y].distance = MAX_DIST;
            }
        }
        initialize();
    }

References field, imSize, initialize(), and MAX_DIST.

initialize() [2/2]

void NearestNeighborField::initialize ( void )

inlineprivate

Definition at line 526 of file kis_inpaint.cpp.

    {
        for (int y = 0; y < imSize.height(); y++) {
            for (int x = 0; x < imSize.width(); x++) {
                field[x][y].distance = distance(x, y, field[x][y].x, field[x][y].y);
 
                //if the distance is "infinity", try to find a better link
                int iter = 0;
                const int maxretry = 20;
                while (field[x][y].distance == MAX_DIST && iter < maxretry) {
                    field[x][y].x = randomInt(imSize.width() + 1);
                    field[x][y].y = randomInt(imSize.height() + 1);
                    field[x][y].distance = distance(x, y, field[x][y].x, field[x][y].y);
                    iter++;
                }
            }
        }
    }

References distance(), field, imSize, MAX_DIST, and randomInt().

minimize()

void NearestNeighborField::minimize ( int pass )

inline

Definition at line 615 of file kis_inpaint.cpp.

    {
        int min_x = 0;
        int min_y = 0;
        int max_x = imSize.width() - 1;
        int max_y = imSize.height() - 1;
 
        for (int i = 0; i < pass; i++) {
            //scanline order
            for (int y = min_y; y < max_y; y++)
                for (int x = min_x; x <= max_x; x++)
                    if (field[x][y].distance > 0)
                        minimizeLink(x, y, 1);
 
            //reverse scanline order
            for (int y = max_y; y >= min_y; y--)
                for (int x = max_x; x >= min_x; x--)
                    if (field[x][y].distance > 0)
                        minimizeLink(x, y, -1);
        }
    }

References distance(), field, imSize, and minimizeLink().

minimizeLink()

void NearestNeighborField::minimizeLink ( int x, int y, int dir )

inline

Definition at line 637 of file kis_inpaint.cpp.

    {
        int xp, yp, dp;
 
        //Propagation Left/Right
        if (x - dir > 0 && x - dir < imSize.width()) {
            xp = field[x - dir][y].x + dir;
            yp = field[x - dir][y].y;
            dp = distance(x, y, xp, yp);
            if (dp < field[x][y].distance) {
                field[x][y].x = xp;
                field[x][y].y = yp;
                field[x][y].distance = dp;
            }
        }
 
        //Propagation Up/Down
        if (y - dir > 0 && y - dir < imSize.height()) {
            xp = field[x][y - dir].x;
            yp = field[x][y - dir].y + dir;
            dp = distance(x, y, xp, yp);
            if (dp < field[x][y].distance) {
                field[x][y].x = xp;
                field[x][y].y = yp;
                field[x][y].distance = dp;
            }
        }
 
        //Random search
        int wi = std::max(output->size().width(), output->size().height());
        int xpi = field[x][y].x;
        int ypi = field[x][y].y;
        while (wi > 0) {
            xp = xpi + randomInt(2 * wi) - wi;
            yp = ypi + randomInt(2 * wi) - wi;
            xp = std::max(0, std::min(output->size().width() - 1, xp));
            yp = std::max(0, std::min(output->size().height() - 1, yp));
 
            dp = distance(x, y, xp, yp);
            if (dp < field[x][y].distance) {
                field[x][y].x = xp;
                field[x][y].y = yp;
                field[x][y].distance = dp;
            }
            wi /= 2;
        }
    }

References distance(), field, imSize, output, randomInt(), and MaskedImage::size().

randomInt()

template<typename T >

T NearestNeighborField::randomInt ( T range )

inlineprivate

Definition at line 520 of file kis_inpaint.cpp.

    {
        return rand() % range;
    }

randomize()

void NearestNeighborField::randomize ( void )

inline

Definition at line 583 of file kis_inpaint.cpp.

    {
        for (int y = 0; y < imSize.height(); y++) {
            for (int x = 0; x < imSize.width(); x++) {
                field[x][y].x = randomInt(imSize.width() + 1);
                field[x][y].y = randomInt(imSize.height() + 1);
                field[x][y].distance = MAX_DIST;
            }
        }
        initialize();
    }

References field, imSize, initialize(), MAX_DIST, and randomInt().

Member Data Documentation

channels

QList<KoChannelInfo *> NearestNeighborField::channels

Definition at line 571 of file kis_inpaint.cpp.

field

NNArray_type NearestNeighborField::field

Definition at line 568 of file kis_inpaint.cpp.

imSize

QRect NearestNeighborField::imSize

Definition at line 567 of file kis_inpaint.cpp.

input

MaskedImageSP NearestNeighborField::input

Definition at line 565 of file kis_inpaint.cpp.

nColors

quint32 NearestNeighborField::nColors

Definition at line 570 of file kis_inpaint.cpp.

output

MaskedImageSP NearestNeighborField::output

Definition at line 566 of file kis_inpaint.cpp.

patchSize

int NearestNeighborField::patchSize

private

Definition at line 563 of file kis_inpaint.cpp.

similarity

std::vector<float> NearestNeighborField::similarity

Definition at line 569 of file kis_inpaint.cpp.

---

The documentation for this class was generated from the following file:

• plugins/tools/tool_smart_patch/kis_inpaint.cpp