基于樣例的影像修補演算法在移除較大的內容，修補大塊范圍的應用上，比基于像素的傳統影像修補方法要適用得多，其基本思想和基于像素的方法還是一致的，只是基于像素的方法是一個像素一個像素地填充待修補區域，而基于樣例的方法是一片一片樣例地填充，大致的步驟是：
- 確定待修補的邊界
- 計算邊界的優先級，確定優先修補的patch
- 從周圍已知區域選擇和待修補patch最相似的patch，并填充待修補patch
- 如果待修補區域已經全部填充，結束，否則回到2，
這里有論文的中英文版，從原理上來說比較容易理解，就不贅述了，直接上代碼，然后上實體，
using ElementType = struct {
int flag;
float confidence;
};
static float compute_confidence(const long x, const long y, const int radius, const unique_ptr<ElementType[]>& sET, const long Width, const long Height)
{
float confidence = 0;
long hstart = max(0, y - radius), hend = min(Height, y + radius + 1);
long wstart = max(0, x - radius), wend = min(Width, x + radius + 1);
long offset = hstart * Width;
for (long m = hstart; m < hend; ++m)
{
for (long n = wstart; n < wend; ++n)
{
if (sET[offset + n].confidence != 0.0f)
{
confidence += sET[offset + n].confidence;
}
}
offset += Width;
}
confidence /= (hend - hstart) * (wend - wstart);
return confidence;
}
static float compute_dataterm(const long x, const long y, const unique_ptr<BYTE[]>& sY, const unique_ptr<ElementType[]>& sET, const long Width, const long Height)
{
float gradIx = 0, gradIy = 0;
long coff = y * Width + x;
float gradNx = 0.0f, gradNy = 0.0f;
long hstart = max(0, y - 1), hend = min(Height, y + 2);
long wstart = max(0, x - 1), wend = min(Width, x + 2);
long offset = hstart * Width;
for (long m = hstart; m < hend; ++m)
{
int dy = m - y;
for (long n = wstart; n < wend; ++n)
{
int dx = n - x;
if (sET[offset + n].flag != INSIDE)
{
int dl = sY[offset + n] - sY[coff];
if (dx && dy) {
gradIx += (0.5f * sqrtf(2) * dl) / dx;
gradIy += (0.5f * sqrtf(2) * dl) / dy;
}
else if (dx) {
gradIx += dl / dx;
}
else if (dy) {
gradIy += dl / dy;
}
}
else {
gradNx += dx;
gradNy += dy;
}
}
offset += Width;
}
// rotate (gradIx, gradIy) 90 degree
{
float temp = -gradIy;
gradIy = gradIx;
gradIx = temp;
}
// normalize gradN
if (gradNx != 0.0f || gradNy != 0.0f)
{
float mag = sqrtf(gradNx * gradNx + gradNy * gradNy);
gradNx /= mag;
gradNy /= mag;
}
float dataterm = abs(gradIx * gradNx + gradIy * gradNy) / 255.0f;
return dataterm;
}
#define LAB_DISTANCE
BOOL CDibProcess::ExemplarInpaint(CDibMask* pDibMask, const int radius, const int search_radius)
{
CRect* pRect = nullptr;
CRect Mask;
unique_ptr<BYTE[]> sMask;
if (pDibMask)
{
pDibMask->GetMaskCircumRect(Mask);
pDibMask->GetMask(sMask);
pRect = &Mask;
}
else
return FALSE;
long i, j;
const long Width = GetWidth();
const long Height = GetHeight();
long Hstart, Hend, Wstart, Wend;
long len;
pRect->NormalizeRect();
if (pRect->top < 0) pRect->top = 0;
if (pRect->left < 0) pRect->left = 0;
if (pRect->bottom > Height) pRect->bottom = Height;
if (pRect->right > Width) pRect->right = Width;
Hstart = pRect->top;
Hend = pRect->bottom;
Wstart = pRect->left;
Wend = pRect->right;
ASSERT(Hstart >= 0 && Hstart <= Hend && Hend <= Height);
ASSERT(Wstart >= 0 && Wstart <= Wend && Wend <= Width);
unique_ptr<BYTE[]> sRed, sGreen, sBlue;
if (GetRGB(sRed, sGreen, sBlue, &len) == FALSE) return FALSE;
unique_ptr<BYTE[]> sLum(new BYTE[len]);
for (i = 0; i < len; ++i) {
sLum[i] = RGB2Y(sRed[i], sGreen[i], sBlue[i]);
}
#ifdef LAB_DISTANCE
unique_ptr<BYTE[]> sL(new BYTE[len]), sA(new BYTE[len]), sB(new BYTE[len]);
for (i = 0; i < len; ++i) {
RGB2LAB(sRed[i], sGreen[i], sBlue[i], sL[i], sA[i], sB[i]);
}
#endif
// initialize
unique_ptr<ElementType[]> sET(new ElementType[len]);
BYTE* pm = sMask.get();
for (i = 0; i < len; ++i)
{
if (*pm++ == 0)
{
sET[i].flag = KNOWN;
sET[i].confidence = 1.0f;
}
else
{
sET[i].flag = INSIDE;
sET[i].confidence = 0.0f;
}
}
// initialize fill front
multimap<float, CPoint, greater<float>> fill_front; // <priority, position>
long hstart = max(0, Hstart - 1), hend = min(Height, Hend + 1);
long wstart = max(0, Wstart - 1), wend = min(Width, Wend + 1);
BYTE *start_off = sMask.get() + hstart * Width + wstart;
for (i = hstart; i < hend; ++i)
{
pm = start_off;
for (j = wstart; j < wend; ++j)
{
if (*pm == 0) {
// check 4 connected pixels
if (i - 1 >= 0 && *(pm - Width)
|| j - 1 >= 0 && *(pm - 1)
|| j + 1 < Width && *(pm + 1)
|| i + 1 < Height && *(pm + Width))
{
// fill front, compute priority = confidence * dataterm
float confidence = compute_confidence(j, i, radius, sET, Width, Height);
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(confidence * dataterm, CPoint(j, i));
++pm;
}
else {
// known
++pm;
}
}
else {
// inside
++pm;
}
}
start_off += Width;
}
if (fill_front.size() == 0) return FALSE;
while (fill_front.size())
{
auto it = fill_front.begin(); // point to the highest priority
CPoint point = it->second;
fill_front.erase(it);
// determine the patch rect certered by point
CRect patch_rect(point.x - radius, point.y - radius, point.x + radius + 1, point.y + radius + 1);
patch_rect.IntersectRect(patch_rect, CRect(0, 0, Width, Height));
// serach the exemplar that minimizes distance to patch_rect
float min_distance = 1e20f;
CRect min_rect;
const long patch_width = patch_rect.Width(), patch_height = patch_rect.Height();
bool valid_fill_front_pixel = true;
long search_hstart = max(0, point.y - search_radius), search_hend = min(Height, point.y + search_radius + 1) - patch_height;
long search_wstart = max(0, point.x - search_radius), search_wend = min(Width, point.x + search_radius + 1) - patch_width;
for (i = search_hstart; i < search_hend; ++i)
{
for (j = search_wstart; j < search_wend; ++j)
{
long offset = i * Width + j;
long patch_offset = patch_rect.top * Width + patch_rect.left;
float d_sum = 0;
long total = 0;
bool valid = true;
for (long m = 0; m < patch_height; ++m)
{
for (long n = 0; n < patch_width; ++n)
{
if (sET[offset + n].flag != INSIDE)
{
if (sET[patch_offset + n].flag != INSIDE)
{
#ifdef LAB_DISTANCE
int dx = sL[offset + n] - sL[patch_offset + n];
int dy = sA[offset + n] - sA[patch_offset + n];
int dz = sB[offset + n] - sB[patch_offset + n];
#else
int dx = sRed[offset + n] - sRed[patch_offset + n];
int dy = sGreen[offset + n] - sGreen[patch_offset + n];
int dz = sBlue[offset + n] - sBlue[patch_offset + n];
#endif
d_sum += sqrtf(float(dx * dx + dy * dy + dz * dz));
++total;
}
}
else
{
// jump out of the double loop
m = patch_height;
valid = false;
break;
}
}
offset += Width;
patch_offset += Width;
}
if (valid)
{
if (total == patch_height * patch_width)
{
// the point is not a fill front point
valid_fill_front_pixel = false;
i = Height - patch_height;
break;
}
float distance = d_sum / (float)total;
if (distance < min_distance)
{
min_distance = distance;
min_rect.SetRect(j, i, j + patch_width, i + patch_height);
}
else if (distance == min_distance) {
float ph_distance = sqrtf(float((patch_rect.top - i) * (patch_rect.top - i) + (patch_rect.left - j) * (patch_rect.left - j)));
float min_rect_ph_distance = sqrtf(float((patch_rect.top - min_rect.top) * (patch_rect.top - min_rect.top) + (patch_rect.left - min_rect.left) * (patch_rect.left - min_rect.left)));
if (ph_distance < min_rect_ph_distance) {
min_distance = distance;
min_rect.SetRect(j, i, j + patch_width, i + patch_height);
}
}
}
}
}
if (!valid_fill_front_pixel) continue; // directly go to next fill front pixel
if (min_distance == 1e20f) // in case the search radius is too small to find a match patch
return FALSE;
// found the rect with minimum distance, then copy
{
long offset = min_rect.top * Width + min_rect.left;
long patch_offset = patch_rect.top * Width + patch_rect.left;
TRACE(TEXT("fill front (%d, %d), copy [%d, %d, %d, %d] -> [%d, %d, %d, %d], offset %d -> %d\n"), point.x, point.y,
min_rect.left, min_rect.top, min_rect.right, min_rect.bottom,
patch_rect.left, patch_rect.top, patch_rect.right, patch_rect.bottom, offset, patch_offset);
for (i = 0; i < patch_height; ++i)
{
for (j = 0; j < patch_width; ++j)
{
if (sET[patch_offset + j].flag == INSIDE)
{
sRed[patch_offset + j] = sRed[offset + j];
sGreen[patch_offset + j] = sGreen[offset + j];
sBlue[patch_offset + j] = sBlue[offset + j];
#ifdef LAB_DISTANCE
sL[patch_offset + j] = sL[offset + j];
sA[patch_offset + j] = sA[offset + j];
sB[patch_offset + j] = sB[offset + j];
#endif
sLum[patch_offset + j] = sLum[offset + j];
sET[patch_offset + j].flag = KNOWN;
}
}
offset += Width;
patch_offset += Width;
}
// use the updated confidence at point to update the each pixel confidence in the patch
float confidence = compute_confidence(point.x, point.y, radius, sET, Width, Height);
patch_offset = patch_rect.top * Width + patch_rect.left;
for (i = 0; i < patch_height; ++i)
{
for (j = 0; j < patch_width; ++j)
{
if (sET[patch_offset + j].confidence == 0.0f)
sET[patch_offset + j].confidence = confidence;
}
patch_offset += Width;
}
}
// update fill front priorities
{
// first remove the fill front pixels inside the patch
for (it = fill_front.begin(); it != fill_front.end(); ++it)
{
point = it->second;
if (patch_rect.PtInRect(point))
{
it = fill_front.erase(it);
if (it == fill_front.end()) break;
}
}
// then add new pixels to fill front from possible 4 sides of the patch
i = patch_rect.top;
j = patch_rect.left + 1;
long patch_offset = i * Width + j;
if (i - 1 >= 0) {
for (; j < patch_rect.right - 1; ++j)
{
if (sET[patch_offset - Width].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
++patch_offset;
}
}
i = patch_rect.bottom - 1;
j = patch_rect.left + 1;
patch_offset = i * Width + j;
if (i + 1 < Height) {
for (; j < patch_rect.right - 1; ++j)
{
if (sET[patch_offset + Width].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
++patch_offset;
}
}
i = patch_rect.top + 1;
j = patch_rect.left;
patch_offset = i * Width + j;
if (j - 1 >= 0) {
for (; i < patch_rect.bottom - 1; ++i)
{
if (sET[patch_offset - 1].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
patch_offset += Width;
}
}
i = patch_rect.top + 1;
j = patch_rect.right - 1;
patch_offset = i * Width + j;
if (j + 1 < Width) {
for (; i < patch_rect.bottom - 1; ++i)
{
if (sET[patch_offset + 1].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
patch_offset += Width;
}
}
// then 4 corner pixels
i = patch_rect.top;
j = patch_rect.left;
patch_offset = i * Width + j;
if (i - 1 >= 0 && sET[patch_offset - Width].flag == INSIDE
|| j - 1 >= 0 && sET[patch_offset - 1].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
//i = patch_rect.top;
j = patch_rect.right - 1;
patch_offset = i * Width + j;
if (i - 1 >= 0 && sET[patch_offset - Width].flag == INSIDE
|| j + 1 < Width && sET[patch_offset + 1].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
i = patch_rect.bottom - 1;
j = patch_rect.left;
patch_offset = i * Width + j;
if (j - 1 >= 0 && sET[patch_offset - 1].flag == INSIDE
|| i + 1 < Height && sET[patch_offset + Width].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
//i = patch_rect.bottom - 1;
j = patch_rect.right - 1;
patch_offset = i * Width + j;
if (j + 1 < Width && sET[patch_offset + 1].flag == INSIDE
|| i + 1 < Height && sET[patch_offset + Width].flag == INSIDE)
{
float dataterm = compute_dataterm(j, i, sLum, sET, Width, Height);
fill_front.emplace(sET[patch_offset].confidence * dataterm, CPoint(j, i));
}
}
}
PutRGB(pRect, sRed, sGreen, sBlue);
return TRUE;
}
Impaint
在計算兩片樣例之間的距離時，顏色空間的選擇還是挺重要的，我試過幾個不同的顏色空間，按照論文中使用的CIE Lab應該效果是最好的，
先看論文里那個簡單的三單色圖案，和基于像素的方法比較，效果要更好一些，沒有了邊緣的模糊，
原圖（640x480） 樣例半徑3，搜索半徑50
再看幾個在基于像素的方法中用過的影像，總的來說，相對于基于像素的方法，沒有了模糊的效果，在待修補的范圍較大，背景比較復雜的情況，一般要比基于像素的方法要好一些，雖然基于樣例的方法是從周圍已知的影像中選擇最接近的樣例，會向待修補區域里面延伸已知區域的紋理和明顯的梯度，但同樣的周圍已知的樣例，和待修補區域原始的內容肯定有差異，填補了以后銜接的地方就會出現一些不自然，不連貫，而且隨著向待修補區域中心推進，置信度會逐漸降低，這些不自然不連貫的地方也會不斷延伸，甚至擴大，
待修補圖 樣例半徑1，搜索半徑10
原圖（698x319） inpaint模板
樣例半徑3，搜索半徑50 樣例半徑4，搜索半徑80
原圖（2048x1269） inpaint模板
樣例半徑3，搜索半徑50 樣例半徑5，搜索半徑100
再看這樣一個例子，去除影像中的白塔，背景相對來說更復雜一些，不同的樣例半徑和搜索半徑，得出的結果可能很不相同，樣例半徑決定了一次填補的區域大小，陽歷半徑太小，可能容易選擇錯誤的匹配樣例，導致后面匹配也都跑偏了，樣例半徑太大了，可能銜接的地方過渡不自然，如果比較確定用來填補的區域比較近，搜索半徑就小一些，否則就大一些，
原圖 inpaint模板
樣例半徑3，搜索半徑80 樣例半徑3，搜索半徑100
樣例半徑5，搜索半徑100 樣例半徑5，搜索半徑150
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296166.html
標籤：其他