Instadeshred

gistfile1.txt

# instachallenge
# http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

from PIL import image

PIXEL_DIFF_CONSTANT = 2
IMAGE_HEIGHT = 369
IMAGE_WIDTH = 640
SHRED_WIDTH = 32
PIXEL_IN_COL_TO_SAMPLE= [2,29,40,210,123,122,111,123,190,304,504] # Automate
NUMBER_OF_COLUMNS = IMAGE_WIDTH/SHRED_WIDTH

# Unshred a shredded image
def unshred(shredded_file):
    image = Image.open(shredded_file)
    sections = sourceToSelections(image)
    unshredded = getOrderedImage(sections)
    unshredded.save(“unshredded.jpg”, “JPEG”)

# Class to keep track of unshredded images, right_most_pix_col and left_most_pix_col
class Sections(object):
    image = Image()
    right_most_pixel_col = []
    left_most_pixel_col = []

# Creates a list of section objects from the source image
def sourceToSections(image):
    createPixelSampleIndex():
    sections = []
    return sections

# Returns a list of ordered image columns from a list of sections
def getOrderedImage(sections):
    while(sections.length()>1):
        sections = mergeSections(sections)
    return sections.pop().image
    
# Returns a list of sections that are merged as much as possible in one pass
def mergeSections(sections):
    merged_list = sections.pop(0)
    for section in sections:
        merged_list = addSection(section, merged_list)
    return merged_list

# Adds a section into the appropriate part of a list or append to end if no match
# Note: could improve to deal with a simultaneous successful right and left match
# currently only handles one match for a given pass through the list
def addSection(section_to_add, merged_list):
    has_match = False
    new_merged_list = []
    for section in merged_list:
        match_type = isSectionMatch(section, section_to_add)
        if(match_type and not has_match): 
            section = mergeSections(section, section_to_add, match_type)    
            has_match = True
        new_merged_list.append(section)
    if not (has_match):
        new_merged_list.append(section_to_add)
    return new_merged_list

# Merge an item on the left or right side of a section and return the adjusted section
def mergeSections(section, item, match_type):
    if(match_type==1):
        destination_point(section.image.width,0)
        section.image = section.image.paste(item.image, destination_point)
        section.right_most_pixel_col = item.right_most_pixel_col
    if(match_type==2):
        destination_point(0,0)
        section.image = section.image.paste(item.image, destination_point)
        section.left_most_pixel_col = item.left_most_pixel_col
    return section

# Determine if two sections match and return if right or left match
def isSectionMatch(section_1, section_2):
    if isColumnMatch(section_1.right_most_pixel_col, section_2.left_most_pixel_col):
        return 1
    if isColumnMatch(section_1.left_most_pixel_col, section_1.right_most_pixel_col):
        return 2
    else:
        return 0
        
# Determine if two columns match returns true iff all pixels meet match criteria
def isColumnMatch(col_1, col_2):
    match = True
    for i in PIXEL_IN_COL_TO_SAMPLE:
        match = (isPixelMatch(col_1[i], col_2[i]) & match)
    return match

# Determine if two pixels match
def isPixelMatch(pixel_1, pixel_2):
    if ((abs(pixel_1[0] - pixel_2[0]) < PIXEL_DIFF_CONSTANT) 
    and (abs(pixel_1[1] - pixel_2[1]) < PIXEL_DIFF_CONSTANT)
    and (abs(pixel_1[2] - pixel_2[2]) < PIXEL_DIFF_CONSTANT)
    and (abs(pixel_1[3] - pixel_2[3]) < PIXEL_DIFF_CONSTANT)):
        return true
    else:
        return false