Simple Try for the Instagram Engineering Challenge

visionfans posted @ 2011年11月13日 02:25 in Articles , 1481 阅读

Introduction

在@Teaonly的微博中看到这个转帖：

Instagram公司给了一张把图像切片、打乱、组合成的图像。[1]

原图是：

要的是自动对乱序的图像切片进行重新排列，组成原始图片：

雷锋网有介绍。[2]

Instagram给出了图像尺寸，356×640，切片的宽度是32。对于如何自动找width的问题，Teaonly提出了方案。这里简单用32。

图片质量很好，只是简单的切割，没有任何degradation操作，于是使用了一个工程性的方法搞定：

 

Motivation

在切片相接处，两侧像素值差异很小，依次来判别是否相接。

Method

根据差异值进行统计，排序，就可以得到一个切片的左边可能是谁，右边可能是谁的hypothesis；排序的时候，取最相近的前两名。对左侧的判定结果，使用右侧排序结果进行hypothesis vertification。最后，可以得出最右侧元素，依次向前track出所有的图像切片，拼接即得原始图。

两列像素值差异计算公式简单用：

d = \sum_{i=1}^{n}\left|x_i-y_i \right|

在计算的时候，我只用了灰度信息，即把原图转化为灰度图，这样计算简便。也可以计算color的3维欧氏距离。不过，对这张图片grayscale就足够应付了。

Implementation

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
% The Image Unshredder script
%
% write by visionfans @ 2011.11.14
 
clear;clc;close all
 
% load image
imgOri = imread('http://instagram-static.s3.amazonaws.com/images/TokyoPanoramaShredded.png');
 
% get image size
nClip = 20;
[nrows ncols nCh] = size(imgOri);
widClip = ncols / nClip;
xAxis = linspace(0, ncols, nClip+1) + 1;
 
% show every clip, format
lSide = zeros(nrows, nClip);
rSide = zeros(nrows, nClip);
 
imgColClip  = uint8(zeros([nrows widClip nCh nClip]));
 
imgGray = rgb2gray(imgOri);
figure;
for i = 1:nClip
    % crop image patch
    rectArea = [xAxis(i) 1 31 nrows];
    imgClip = imcrop(imgGray, rectArea);
    imgColClip(:,:,:,i) = imcrop(imgOri, rectArea);  % for show
     
    subplot(2, nClip/2, i); imshow(imgColClip(:,:,:,i));title(num2str(i));
     
    % statics side line
    lSide(:, i) = imgClip(1:end, 1);
    rSide(:, i) = imgClip(1:end, end);
end
 
% calculate coloum pixel diversity
distMat = zeros(nClip, nClip);
for i = 1:nClip
    for j = 1:nClip
        if i==j
            distMat(i, j) = Inf;
        else
            distMat(i, j) = sum(abs(lSide(:, i) - rSide(:,j)));
        end
    end
end
 
% find candidate matchings
[~, lMatch] = sort(distMat');
[~, rMatch] = sort(distMat);
 
candsAll = zeros(2, nClip);
for i = 1:nClip
    lcands = lMatch(1:2,i);
    for j = 1:2
        rcands = rMatch(1:2, lcands(j));
         
        if ismember(i, rcands)
            candsAll(j,i) = lcands(j);
        end
    end
end
 
% filter repetition
rightElement = setdiff(1:nClip, unique(candsAll(1,:)));
 
if numel(rightElement)~=1, error('Need more elaborate check.'); end
 
% get result
imgOrder = zeros(1,nClip);
idxNext = rightElement;
for i = 1:nClip
    imgOrder(i) = idxNext;
    idxNext = candsAll(1, idxNext);
end
imgOrder = fliplr(imgOrder);
 
outImg = [];
for i = 1:nClip
    outImg = [outImg imgColClip(:,:,:,imgOrder(i))];
end
 
figure;imshow(outImg);title('Unshreded Image');

 

Result

Segmentation of image strips，每条宽32个pixels:

Sort result:

imgOrder = [  9    11    15    17    19    14     8     4     3    12     5    20    18    13     7    16     2     6     1    10 ]

Unshreded Image:

Discuss

更多需要考虑的情况：

1. 如何自动检测切片的分割位置，其实，这里给了基本假设是直线切割，如果不是直线怎么办。

2. 对于低质图像，本文中简单的边界差异比较算法就无效了，要考虑切片内部内容。'

3. 对于非直线切割的情况，如何利用边界特征去进行匹配。

3. 当前算法，难以处理通用的拼接。更多问题，有兴趣的同学可以继续挖下去。

Just for fun! ^-^

 

References

[1] Instagram Engineering Challenge: The Unshredder，http://instagram-engineering.tumblr.com/

[2] 复原这张图片，你就有机会加入Instagram, http://www.leiphone.com/join-instagram.html?jtss=tsina

Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter