Skip to content

Instantly share code, notes, and snippets.

@hpbuniat
Created December 4, 2011 10:48
Show Gist options
  • Save hpbuniat/1429873 to your computer and use it in GitHub Desktop.
Save hpbuniat/1429873 to your computer and use it in GitHub Desktop.
<?php
error_reporting(E_ALL);
ini_set('display_errors', '1');
ini_set('max_execution_time', 0);
ini_set('memory_limit', '256M');
/**
* Test for http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder
*
* @author Hans-Peter Buniat
*/
class Instagram {
/**
* The image to work on
*
* @var Imagick
*/
private $_image;
/**
* The result image
*
* @var ressource
*/
private $_result;
/**
* The image-height
*
* @var int
*/
private $_iImageHeight;
/**
* The image-width
*
* @var int
*/
private $_iImageWidth;
/**
* The image as vertical iterator
*
* @var array
*/
private $_aIterator = array();
/**
* The detected shreds
*
* @var array
*/
private $_aShreds = array(
0
);
/**
* Read the image to work on
*
* @param string $sImage
*
* @return Instagram
*/
public function read($sImage) {
$this->_image = new Imagick($sImage);
$this->_iImageHeight = $this->_image->getImageHeight();
$this->_iImageWidth = $this->_image->getImageWidth();
$this->_result = imagecreatefrompng($sImage);
return $this;
}
/**
* Get the resulting image
*
* @return void
*/
public function get() {
imagepng($this->_result);
}
/**
* Detect the shreds and find the correct order
*
* @return Instagram
*/
public function find() {
$oIterator = $this->_image->getPixelIterator();
// create a vertical iterator
$aDistance = array();
foreach ($oIterator as $iRow => $oPixels) {
foreach ($oPixels as $iColumn => $oPixel) {
$this->_aIterator[$iColumn][$iRow] = $oPixel->getHSL();
}
$oIterator->syncIterator();
}
unset($oIterator);
// find the shred-edges - they have a much higher distance than normal pixel-columns
$aDistance = $this->_getColumnDistance($this->_aIterator, false);
$aIgnore = array(
0,
$this->_iImageWidth - 2,
$this->_iImageWidth - 1
);
foreach ($aDistance as $iColumn => $fDistance) {
if (in_array($iColumn, $aIgnore) === true) {
continue;
}
// find the shreds .. this needs re-thinking ;)
if ($fDistance > (0.775 * ($aDistance[$iColumn - 1] + $aDistance[$iColumn + 1])) or $fDistance > ($aDistance[$iColumn - 1] * 2)
or ($fDistance > $aDistance[$iColumn - 1] and $fDistance > (0.825 * ($aDistance[$iColumn + 1] + $aDistance[$iColumn + 2])))) {
$this->_aShreds[] = $iColumn;
}
}
// get the first shred
$fMax = $iFirst = 0;
foreach ($aDistance as $iKey => $mValue) {
if ($mValue > $fMax) {
$fMax = $mValue;
$iFirst = $iKey;
}
}
$aFinal = array(
$iFirst
);
// re-structure the shreds, to determine the length of a specifc shred
$this->_aShreds = array_flip($this->_aShreds);
ksort($this->_aShreds);
$aDistance = $this->_aShreds;
unset($aDistance[$iFirst]);
// find every next shred to the first, second, .. shred
while (count($aDistance) > 0) {
$iCompare = end($aFinal);
$iCompare = $this->_getNextShred($iCompare) - 1;
$aColumnDistance = $this->_getColumnDistance($aDistance, $iCompare);
asort($aColumnDistance);
$iNext = key($aColumnDistance);
$aFinal[] = $iNext;
unset($aDistance[$iNext], $aColumnDistance);
}
// create the resulting image
$iDestX = $iSrcX = $iDestY = $iSrcY = 0;
$rResult = imagecreatetruecolor($this->_iImageWidth, $this->_iImageHeight);
foreach ($aFinal as $iShred) {
$iSrcWidth = $this->_getNextShred($iShred) - $iShred;
imagecopy($rResult, $this->_result, $iDestX, $iDestY, $iShred, $iSrcY, $iSrcWidth, $this->_iImageHeight);
$iDestX += $iSrcWidth;
}
$this->_result = $rResult;
return $this;
}
/**
* Get the next shred
*
* @param int $iCurrent
*
* @return int
*/
private function _getNextShred($iCurrent) {
reset($this->_aShreds);
foreach ($this->_aShreds as $iShred => $iKey) {
if ($iShred === $iCurrent) {
$iNext = key($this->_aShreds);
if ($iNext === 0) {
$iNext = $this->_iImageWidth;
}
return $iNext;
}
}
return 0;
}
/**
* Compare columns to other columns
*
* @param array $aIterator
* @param mixed $mCompare
*
* @return array
*/
private function _getColumnDistance($aIterator, $mCompare) {
$aResult = array();
foreach ($aIterator as $iColumn => $mTemp) {
$aResult[$iColumn] = 0;
$iCompare = ($mCompare === false) ? ((($iColumn === 0) ? $this->_iImageWidth : $iColumn) -1) : $mCompare;
foreach ($this->_aIterator[$iColumn] as $iRow => $aColors) {
$aResult[$iColumn] += $this->_getEdgeDistance($aColors, $iCompare, $iRow);
}
}
return $aResult;
}
/**
* Get the edge-distance by using the: https://en.wikipedia.org/wiki/Sobel_operator with a simplified matrix
*
* @param array $aColors
* @param array $iCompare
* @param array $iRow
*
* @return float
*/
private function _getEdgeDistance($aColors, $iCompare, $iRow) {
// create a distance value for the edge, using the: https://en.wikipedia.org/wiki/Sobel_operator
$fUpLeft = $fDownLeft = 0;
$fLeft = 2 * $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow]);
if ($iRow > 0) {
$fUpLeft = $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow - 1]);
}
if ($iRow < ($this->_iImageHeight - 1)) {
$fDownLeft = $this->_getColorDistance($aColors, $this->_aIterator[$iCompare][$iRow + 1]);
}
// calculating the distance
return sqrt(pow((0 - ($fUpLeft + ($fLeft * 2) + $fDownLeft)), 2) + pow($fUpLeft - $fDownLeft, 2));
}
/**
* Get the absolute distance between the color values of 2 pixel
*
* @param array $aColorA
* @param array $aColorB
*
* @return float
*/
private function _getColorDistance(array $aColorA, array $aColorB) {
return pow($aColorA['hue'] - $aColorB['hue'], 2) + pow($aColorA['saturation'] - $aColorB['saturation'], 2) + pow($aColorA['luminosity'] - $aColorB['luminosity'], 2);
}
}
$aOpts = getopt('i:');
if (empty($aOpts['i']) === true and empty($_GET['i']) !== true) {
$aOpts['i'] = $_GET['i'];
}
try {
if (empty($aOpts['i']) === true) {
throw new Exception('IMAGE_IS_NEEDED');
}
$o = new Instagram();
$o->read($aOpts['i'])->find();
header('Content-type: image/png');
$o->get();
}
catch (Exception $e) {
var_dump($e);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment