public
Created — forked from garyburd/unshred.go

Go solution to the Instagram Engineering Challenge (http://goo.gl/B92t0).

  • Download Gist
main.go
Go
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
// A solution to the Instagram Engineering Challenge (http://goo.gl/B92t0)
package main
 
import (
"fmt"
"image"
"image/draw"
"image/jpeg"
"image/png"
"io"
"math"
"os"
"path"
"sort"
)
 
const shredWidth = 32
 
func fatal(s string, args ...interface{}) {
fmt.Fprintf(os.Stderr, s, args...)
os.Exit(2)
}
 
func readImage(fname string) image.Image {
f, err := os.Open(fname)
if err != nil {
fatal("Error opening input: %v\n", err)
}
defer f.Close()
m, _, err := image.Decode(f)
if err != nil {
fatal("Error reading input: %v\n", err)
}
return m
}
 
func writeImage(fname string, m image.Image) {
var encode func(io.Writer, image.Image) error
switch path.Ext(fname) {
case ".jpg":
encode = func(w io.Writer, m image.Image) error {
return jpeg.Encode(w, m, nil)
}
case ".png":
encode = png.Encode
default:
fatal("Unknown output type")
}
 
f, err := os.Create(fname)
if err != nil {
fatal("Error creating output: %v\n", err)
}
defer f.Close()
 
if err := encode(f, m); err != nil {
fatal("Error encoding output: %v\n", err)
}
}
 
// shuffleImage returns an image with shreds in m reordered by shuffle.
func shuffleImage(m image.Image, shuffle []int) image.Image {
b := m.Bounds()
result := image.NewRGBA(image.Rect(0, 0, b.Max.X-b.Min.X, b.Max.Y-b.Min.Y))
for dst, src := range shuffle {
draw.Draw(result,
image.Rect(dst*shredWidth, 0, dst*shredWidth+shredWidth, b.Max.Y-b.Min.Y),
m,
image.Pt(src*shredWidth, 0),
draw.Src)
}
return result
}
 
// edge represents a possible connection between two shreds.
type edge struct {
// Index of shreds to left and right of this edge.
left, right int
// Measure of difference between shreds at this edge.
diff float64
}
 
// shred represents a shred.
type shred struct {
// Index of shred joined to the left and right of this shred or -1 to
// indicate that no shred is joined.
left, right int
}
 
// byDiff sorts shreds by the diff field.
type byDiff []edge
 
func (edges byDiff) Len() int { return len(edges) }
func (edges byDiff) Less(i, j int) bool { return edges[i].diff < edges[j].diff }
func (edges byDiff) Swap(i, j int) { edges[i], edges[j] = edges[j], edges[i] }
 
func chanDiffSqr(c1, c2 uint32) float64 {
d := math.Log10(float64(c1+1)/65535.0) - math.Log10(float64(c2+1)/65535.0)
return d * d
}
 
// computeShuffle returns a slice that maps source shred index to destination
// shred index.
func computeShuffle(m image.Image) []int {
b := m.Bounds()
n := (b.Max.X - b.Min.X) / shredWidth
 
// Create an edge for all shred combinations.
edges := make([]edge, 0, n*n-n)
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i == j {
continue
}
x0 := b.Min.X + i*shredWidth + shredWidth - 1
x1 := b.Min.X + j*shredWidth
// Compute difference between edges as sum of euclidian distance
// between adjacent pixels in RGB space.
var diff float64
for y := b.Min.Y; y < b.Max.X; y++ {
r0, g0, b0, _ := m.At(x0, y).RGBA()
r1, g1, b1, _ := m.At(x1, y).RGBA()
diff += math.Sqrt(chanDiffSqr(r0, r1) + chanDiffSqr(g0, g1) + chanDiffSqr(b0, b1))
}
edges = append(edges, edge{i, j, diff})
}
}
 
sort.Sort(byDiff(edges))
 
// Initialize shreds with left and right set to -1
shreds := make([]shred, n)
for i := range shreds {
shreds[i] = shred{-1, -1}
}
 
// Join shreds in edge quality order.
joins := 0
for _, e := range edges {
if shreds[e.left].right >= 0 || shreds[e.right].left >= 0 {
// One or both shreds for this edge are connected.
continue
}
shreds[e.left].right = e.right
shreds[e.right].left = e.left
joins += 1
if joins == n-1 {
// Exit to avoid joining shreds in a loop.
break
}
}
 
// Find shred on the left edge of output.
i := 0
for ; i < n; i++ {
if shreds[i].left < 0 {
break
}
}
 
// Compute shuffle by iterating from left to right through shreds.
shuffle := make([]int, 0, n)
for ; i >= 0; i = shreds[i].right {
shuffle = append(shuffle, i)
}
 
return shuffle
}
 
func main() {
if len(os.Args) != 3 {
fatal("usage: unshred input output")
}
m := readImage(os.Args[1])
shuffle := computeShuffle(m)
m = shuffleImage(m, shuffle)
writeImage(os.Args[2], m)
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.