CODEWITHSUNDEEP
sortingimage-processinglanguage-agnostic
tigrou
tigrou

Reputation: 4516

How to sort image blocks by to minimize the differences between them?

I have a list of small image blocks. All of them are the same size (eg : 16x16). They are black and white, with pixel values between 0-255. I would like to sort those images to minimize the the difference between them.

What I have in mind is to compute the mean absolute difference (MAD) of pixels between adjacent blocks (eg : block N vs block N+1, block N+1 vs block N+2, ...). From this I can calculate the sum of those MAD values (eg : sum = mad1 + mad2 + ...). What I would like is to find the ordering that minimize that sum.

Before :

enter image description here

After : (this was done by hand only to provide an example, there is probably a better ordering for those blocks, especially the ones with vertical stripes)

enter image description here

Upvotes: 0

Views: 182

Answers (1)

tigrou
tigrou

Reputation: 4516

Based on RaymoAisla comment which pointed out this is similar to Travelling salesman problem, I have decided to implement a solution using Nearest neighbour algorithm. While not perfect, it gives great results :

enter image description here

Here is code :

from PIL import Image
import numpy as np

def sortImages(images):  #Nearest neighbour algorithm
    result = []
    tovisit = range(len(images)) 

    best = max(tovisit, key=lambda x: images[x].sum()) #brightest block as first
    tovisit.remove(best)
    result.append(best)

    while tovisit: 
        best = min(tovisit, key=lambda x: MAD(images[x], images[best])) #nearest neighbour
        tovisit.remove(best)
        result.append(best)
    return result  #indices of sorted image blocks

def MAD(a, b): #mean absolute distance
    return np.absolute(a - b).sum()

images = ... #should contains b&w images only (eg : from PIL Image)
arrays = [np.array(x).astype(int) for x in images] #convert images to np arrays
result = sortImages(arrays)

Upvotes: 0

Related Questions