A bit of fun with bloc matching

I’ve added a new filter in the G’MIC-Qt, plug-in, located at Degradations / Rebuild From Similar Blocs :

I wanted to try something weird (most of the things that go through my brain are weird anyway :slight_smile:). The initial algorithm is :

  1. Decompose the input image into a set of blocs, each being N\times N pixels.
  2. For each bloc, find the most similar bloc in this set, excluding itself.
  3. Rebuild the image by arranging the blocs determined at step 2.

I’ve done a slight modification to the initial algorithm, so that finding the most similar bloc is not done in the RGB space, but in a smoothed/scaled YCbCr space (this way, I can tune the importance of the luminance against the chromas, for the bloc matching measure).

The filter is entirely implemented with the following G’MIC code:

#@gui Rebuild From Similar Blocs : fx_rebuild_from_similar_blocs, fx_rebuild_from_similar_blocs
#@gui : Bloc Size (%) = float(5,2,50)
#@gui : sep = separator()
#@gui : Regularization factor = float(0,0,2)
#@gui : Luminance factor = float(0.75,0,3)
#@gui : Norm type = choice(1,"L1","L2")
#@gui : sep = separator()
#@gui : note = note{"This filter subdivides the image into blocs, and replace each bloc by the most similar bloc found in the other blocs.
#@gui : "}
#@gui : sep = separator()
#@gui : note = note("<small>Author: <i>David Tschumperlé</i>.      Latest Update: <i>2020/09/17</i>.</small>")
fx_rebuild_from_similar_blocs :
  repeat $! l[$>] split_opacity l[0] to_rgb
    w0,h0,S={[w,h,round(min(w,h)*$1%)]} # S: Bloc size

    # Split image into regular blocs.
    r {ceil([w,h]/$S)*$S},1,100%,0,3,0.5,0.5
    +l. b. $2% rgb2ycbcr sh. 0 *. $3 rm. s yx,-$S a z endl

    # For each bloc, find most similar bloc.
    f. ":
        ind = x + y*w;
        kmin = 0;
        dmin = inf;
        for (k = 0, k<wh, ++k, k!=ind?(
          d = norm"{1+$4}"(S - crop(#1,0,0,k,w#1,h#1,1));
          d<dmin?(dmin = d; kmin = k);
        xt = kmin%w;
        yt = int(kmin/w);
        i(xt,yt) = ind;

    # Reconstruct image.
    eval.. "
      ind = i;
      xs = (ind%"$M")*"$S";
      ys = int(ind/"$M")*"$S";
      xt = x*"$S";
      yt = y*"$S";
    k. r $w0,$h0,1,100%,0,0,0.5,0.5
  endl a c endl done

The bloc matching step is done in parallel, to speed up the process when multiple cores are available. Also, when a best-match between bloc B1 and B2 is found, the result is set for these two blocs at the same time, avoiding the recompute the matching between B2 and B1.

Here is another result:

Yes that looks weird and is probably useless, but I know some people are interested in glitch art, and this is an easy way of scrambling your image while still being able to recognize its content.
Well that’s it, it took one hour to set up, and it gave me some fun, so I guess it wasn’t completely useless.


Hmm, this seem to go well with my interactive tiler tool. Basically, draw out a map design, run this tool, then patch it up with the interactive tool. I should try that.

Was thinking this could be rejiggered into a quick and dirty inpaint tool.