Glitched Block Matching Algorithm

391zuf.gif


Glitched Block matching algorithm. Usually used in video compression

  PImage img1;
  PImage img2;
  ArrayList mv;
  
void setup(){
  size(1280,720);
  img1 = loadImage("video\\thumb0087.jpg");
  img2 = loadImage("video\\thumb0088.jpg");
  
  mv = blockMatch(img1,img2,4);
}


ArrayList blockMatch(PImage img1, PImage img2, int N) {
  ArrayList moveVectors3 = new ArrayList();
  for (int oi = 0; oi < 1280; oi +=N) {
    for (int oj = 0; oj < 720; oj +=N) {
        PImage searchImage = img1.get(oi - N, oj - N, N*3, N*3);
        PImage R = img2.get(oi, oj, N, N);
        float mad = MeanDifference(searchImage, R, N, N, N);
        PVector sp = new PVector(oi, oj);
        PVector ep = null;
        int step = N;
        while (step!=1) {
          for (int i = 0; i < N*3; i+=N) {
              for (int j = 0; j < N*3; j+=N) {
                  float nmad = MeanDifference(searchImage, R, N, i, j);
                  if (nmad < mad) {
                      mad = nmad;
                      ep = new PVector(i + oi- N, j + oj- N);
                  }
              }
          }
          step/=2;
        }
        if (ep != null){
          //moveVectors.add(img1.get((int)ep.x, (int)ep.y,N,N));
          //moveVectors2.add(sp);
          moveVectors3.add(new PVector[]{sp,ep});
          //println(oi + "  " + oj);
        }
    }
  }
  return moveVectors3;
}

void printFromVec(PImage img, PVector[] moveVectors, int N) {
    image(img.get((int)moveVectors[1].x, (int)moveVectors[1].y, N,N), (int)moveVectors[0].x, (int)moveVectors[0].y);
}

void printAllFVec(PImage img, ArrayList moveVectors, int N) {
  for (int i = 0; i <  moveVectors.size(); i++) {
    printFromVec(img, moveVectors.get(i), N);
  }
}

void drawToGrap(PImage img, PImage base, PGraphics grap, ArrayList moveVectors, int N) {
  grap.beginDraw();
  grap.background(0);
  grap.image(base,0,0);
  for (int i = 0; i <  moveVectors.size(); i++) {
    grap.image(img.get((int)moveVectors.get(i)[1].x, (int)moveVectors.get(i)[1].y, N,N), (int)moveVectors.get(i)[0].x, (int)moveVectors.get(i)[0].y);
  }
  grap.endDraw();
}
  

float MeanDifference(PImage C, PImage R, int N, int x, int y) {
  float MAD = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (j + y >= N*3 || i + x >= N*3) continue;
      MAD += Math.abs(hue(C.get(i + x, j + y)) - hue(R.get(i,j)));
    }
  }
  return MAD /= (N*N);
}



void draw() {
  image(img1,0,0);
    noFill();
    stroke(255);
  PGraphics g1 = createGraphics(width, height);
  drawToGrap(img2, img1, g1, mv, 4);
  image(g1,  0,0);
}

Wiki: here