Bilder in Tweets kodieren (Extreme Image Compression Edition) [closed]

59

Basierend auf der sehr erfolgreichen Twitter Image Encoding Challenge bei Stack Overflow.

Wenn ein Bild 1000 Wörter wert ist, wie viel von einem Bild können Sie in 114,97 Bytes passen?

Ich fordere Sie auf, eine allgemeine Methode zum Komprimieren von Bildern in einen Twitter-Standardkommentar zu entwickeln, der nur druckbaren ASCII-Text enthält .

Regeln:

  1. Sie müssen ein Programm schreiben, das ein Bild aufnehmen und den codierten Text ausgeben kann.
  2. Der vom Programm erstellte Text darf höchstens 140 Zeichen lang sein und darf nur Zeichen enthalten, deren Codepunkte im Bereich von 32 bis einschließlich 126 liegen.
  3. Sie müssen ein Programm (möglicherweise dasselbe Programm) schreiben, das den codierten Text aufnimmt und eine decodierte Version des Fotos ausgibt.
  4. Ihr Programm kann externe Bibliotheken und Dateien verwenden, jedoch keine Internetverbindung oder Verbindung zu anderen Computern erfordern.
  5. Der Dekodierungsprozess kann in keiner Weise auf die Originalbilder zugreifen oder diese enthalten.
  6. Ihr Programm muss Bilder in mindestens einem der folgenden Formate (nicht unbedingt mehr) akzeptieren: Bitmap, JPEG, GIF, TIFF, PNG. Wenn einige oder alle Beispielbilder nicht im richtigen Format vorliegen, können Sie sie vor der Komprimierung durch Ihr Programm selbst konvertieren.

Bewertung:

Dies ist eine etwas subjektive Herausforderung, daher wird der Gewinner (irgendwann) von mir beurteilt. Ich werde mich auf einige wichtige Faktoren konzentrieren, die im Folgenden in abnehmender Wichtigkeit aufgeführt sind:

  1. Möglichkeit, eine Vielzahl von Bildern sinnvoll zu komprimieren, auch solche, die nicht als Beispielbild aufgeführt sind
  2. Fähigkeit, die Umrisse der Hauptelemente in einem Bild beizubehalten
  3. Möglichkeit, die Farben der Hauptelemente in einem Bild zu komprimieren
  4. Fähigkeit, Konturen und Farben der kleinen Details in einem Bild beizubehalten
  5. Kompressionszeit. Obwohl es nicht so wichtig ist, wie gut ein Bild komprimiert ist, sind schnellere Programme besser als langsamere Programme, die dasselbe tun.

Ihre Einreichung sollte die resultierenden Bilder nach der Dekomprimierung zusammen mit dem generierten Twitter-Kommentar enthalten. Wenn möglich, können Sie auch einen Link zum Quellcode angeben.

Beispielbilder:

Die Hindenburg , Berglandschaft , Mona Lisa , 2D-Formen

PhiNotPi
quelle
U + 007F (127) und U + 0080 (128) sind Steuerzeichen. Ich würde vorschlagen, diese ebenfalls zu verbieten.
PleaseStand
Gute Beobachtung. Ich werde das reparieren.
PhiNotPi
Lässt Twitter Unicode nicht zu?
marinus
4
Ich habe das Gefühl, dass ich eine Lösung dafür patentieren möchte.
Shmiddty
2
"Gebirgslandschaften" 1024x768 - Holen Sie es, bevor es weg ist! -> i.imgur.com/VaCzpRL.jpg <-
jdstankosky

Antworten:

58

Ich habe meine Methode durch Hinzufügen der eigentlichen Komprimierung verbessert. Es funktioniert jetzt iterativ wie folgt:

  1. Konvertieren Sie das Bild in YUV
  2. Verkleinern Sie das Bild unter Beibehaltung des Seitenverhältnisses (wenn das Bild farbig ist, wird die Farbsättigung mit 1/3 der Breite und Höhe der Luminanz abgetastet).

  3. Reduzieren Sie die Bittiefe auf 4 Bits pro Sample

  4. Wenden Sie die Medianvorhersage auf das Bild an, um die Probenverteilung gleichmäßiger zu gestalten

  5. Wenden Sie die adaptive Bereichskomprimierung auf das Bild an.

  6. Überprüfen Sie, ob die Größe des komprimierten Bildes <= 112 ist

Das größte Bild, das in die 112 Bytes passt, wird dann als endgültiges Bild verwendet, wobei die verbleibenden zwei Bytes zum Speichern der Breite und Höhe des komprimierten Bildes sowie eines Flags verwendet werden, das angibt, ob das Bild farbig ist. Bei der Dekodierung wird der Vorgang umgekehrt und das Bild so skaliert, dass die kleinere Abmessung 128 beträgt.

Es gibt einiges an Verbesserungspotenzial, da normalerweise nicht alle verfügbaren Bytes verwendet werden. Ich bin jedoch im Begriff, die Renditen für das Downsampling und die verlustfreie Komprimierung erheblich zu verringern.

Schnelle und schmutzige C ++ - Quelle

Windows exe

Mona Lisa (13x20 Luminanz, 4x6 Chroma)

&Jhmi8(,x6})Y"f!JC1jTzRh}$A7ca%/B~jZ?[_I17+91j;0q';|58yvX}YN426@"97W8qob?VB'_Ps`x%VR=H&3h8K=],4Bp=$K=#"v{thTV8^~lm vMVnTYT3rw N%I           

Mona Lisa Mona Lisa Twitter verschlüsselt

Hindenburg (21x13 Luminanz)

GmL<B&ep^m40dPs%V[4&"~F[Yt-sNceB6L>Cs#/bv`\4{TB_P Rr7Pjdk7}<*<{2=gssBkR$>!['ROG6Xs{AEtnP=OWDP6&h{^l+LbLr4%R{15Zc<D?J6<'#E.(W*?"d9wdJ'       

Hindenburg Hindenburg-Twitter verschlüsselt

Berge (19x14 Luminanz, 6x4 Chroma)

Y\Twg]~KC((s_P>,*cePOTM_X7ZNMHhI,WeN(m>"dVT{+cXc?8n,&m$TUT&g9%fXjy"A-fvc 3Y#Yl-P![lk~;.uX?a,pcU(7j?=HW2%i6fo@Po DtT't'(a@b;sC7"/J           

Berg Berg-Twitter verschlüsselt

2D-Formen (21 x 15 Luminanz, 7 x 5 Chroma)

n@|~c[#w<Fv8mD}2LL!g_(~CO&MG+u><-jT#{KXJy/``#S@m26CQ=[zejo,gFk0}A%i4kE]N ?R~^8!Ki*KM52u,M(his+BxqDCgU>ul*N9tNb\lfg}}n@HhX77S@TZf{k<CO69!    

2D-Formen 2D Shapes zwitschern verschlüsselt

Sir_Lagsalot
quelle
7
Dadurch habe ich das Gefühl, dass ich einen grauen Star oder so etwas bekomme. Haha, großartige Arbeit!
Jdstankosky
Schöne Verbesserungen!
Jdstankosky
37

Gehen

Arbeitet, indem das Bild rekursiv in Regionen unterteilt wird. Ich versuche, Regionen mit hohem Informationsgehalt zu unterteilen und die Trennlinie auszuwählen, um den Farbunterschied zwischen den beiden Regionen zu maximieren.

Jede Unterteilung wird unter Verwendung einiger Bits zum Codieren der Trennlinie codiert. Jeder Blattbereich ist als einzelne Farbe codiert.

Bildbeschreibung hier eingeben

4vN!IF$+fP0~\}:0d4a's%-~@[Q(qSd<<BDb}_s|qb&8Ys$U]t0mc]|! -FZO=PU=ln}TYLgh;{/"A6BIER|{lH1?ZW1VNwNL 6bOBFOm~P_pvhV)]&[p%GjJ ,+&!p"H4`Yae@:P

Bildbeschreibung hier eingeben

<uc}+jrsxi!_:GXM!'w5J)6]N)y5jy'9xBm8.A9LD/^]+t5#L-6?9 a=/f+-S*SZ^Ch07~s)P("(DAc+$[m-:^B{rQTa:/3`5Jy}AvH2p!4gYR>^sz*'U9(p.%Id9wf2Lc+u\&\5M>

Bildbeschreibung hier eingeben

lO6>v7z87n;XsmOW^3I-0'.M@J@CLL[4z-Xr:! VBjAT,##6[iSE.7+as8C.,7uleb=|y<t7sm$2z)k&dADF#uHXaZCLnhvLb.%+b(OyO$-2GuG~,y4NTWa=/LI3Q4w7%+Bm:!kpe&

Bildbeschreibung hier eingeben

ZoIMHa;v!]&j}wr@MGlX~F=(I[cs[N^M`=G=Avr*Z&Aq4V!c6>!m@~lJU:;cr"Xw!$OlzXD$Xi>_|*3t@qV?VR*It4gB;%>,e9W\1MeXy"wsA-V|rs$G4hY!G:%v?$uh-y~'Ltd.,(

Das Hindenburg-Bild sieht ziemlich beschissen aus, aber die anderen mag ich.

package main

import (
    "os"
    "image"
    "image/color"
    "image/png"
    _ "image/jpeg"
    "math"
    "math/big"
)

// we have 919 bits to play with: floor(log_2(95^140))

// encode_region(r):
//   0
//      color of region (12 bits, 4 bits each color)
// or
//   1
//      dividing line through region
//        2 bits - one of 4 anchor points
//        4 bits - one of 16 angles
//      encode_region(r1)
//      encode_region(r2)
//
// start with single region
// pick leaf region with most contrast, split it

type Region struct {
    points []image.Point
    anchor int  // 0-3
    angle int // 0-15
    children [2]*Region
}

// mean color of region
func (region *Region) meanColor(img image.Image) (float64, float64, float64) {
    red := 0.0
    green := 0.0
    blue := 0.0
    num := 0
    for _, p := range region.points {
        r, g, b, _ := img.At(p.X, p.Y).RGBA()
        red += float64(r)
        green += float64(g)
        blue += float64(b)
        num++
    }
    return red/float64(num), green/float64(num), blue/float64(num)
}

// total non-uniformity in region's color
func (region *Region) deviation(img image.Image) float64 {
    mr, mg, mb := region.meanColor(img)
    d := 0.0
    for _, p := range region.points {
        r, g, b, _ := img.At(p.X, p.Y).RGBA()
        fr, fg, fb := float64(r), float64(g), float64(b)
        d += (fr - mr) * (fr - mr) + (fg - mg) * (fg - mg) + (fb - mb) * (fb - mb)
    }
    return d
}

// centroid of region
func (region *Region) centroid() (float64, float64) {
    cx := 0
    cy := 0
    num := 0
    for _, p := range region.points {
        cx += p.X
        cy += p.Y
        num++
    }
    return float64(cx)/float64(num), float64(cy)/float64(num)
}

// a few points in (or near) the region.
func (region *Region) anchors() [4][2]float64 {
    cx, cy := region.centroid()

    xweight := [4]int{1,1,3,3}
    yweight := [4]int{1,3,1,3}
    var result [4][2]float64
    for i := 0; i < 4; i++ {
        dx := 0
        dy := 0
        numx := 0
        numy := 0
        for _, p := range region.points {
            if float64(p.X) > cx {
                dx += xweight[i] * p.X
                numx += xweight[i]
            } else {
                dx += (4 - xweight[i]) * p.X
                numx += 4 - xweight[i]
            }
            if float64(p.Y) > cy {
                dy += yweight[i] * p.Y
                numy += yweight[i]
            } else {
                dy += (4 - yweight[i]) * p.Y
                numy += 4 - yweight[i]
            }
        }
        result[i][0] = float64(dx) / float64(numx)
        result[i][1] = float64(dy) / float64(numy)
    }
    return result
}

func (region *Region) split(img image.Image) (*Region, *Region) {
    anchors := region.anchors()
    // maximize the difference between the average color on the two sides
    maxdiff := 0.0
    var maxa *Region = nil
    var maxb *Region = nil
    maxanchor := 0
    maxangle := 0
    for anchor := 0; anchor < 4; anchor++ {
        for angle := 0; angle < 16; angle++ {
            sin, cos := math.Sincos(float64(angle) * math.Pi / 16.0)
            a := new(Region)
            b := new(Region)
            for _, p := range region.points {
                dx := float64(p.X) - anchors[anchor][0]
                dy := float64(p.Y) - anchors[anchor][1]
                if dx * sin + dy * cos >= 0 {
                    a.points = append(a.points, p)
                } else {
                    b.points = append(b.points, p)
                }
            }
            if len(a.points) == 0 || len(b.points) == 0 {
                continue
            }
            a_red, a_green, a_blue := a.meanColor(img)
            b_red, b_green, b_blue := b.meanColor(img)
            diff := math.Abs(a_red - b_red) + math.Abs(a_green - b_green) + math.Abs(a_blue - b_blue)
            if diff >= maxdiff {
                maxdiff = diff
                maxa = a
                maxb = b
                maxanchor = anchor
                maxangle = angle
            }
        }
    }
    region.anchor = maxanchor
    region.angle = maxangle
    region.children[0] = maxa
    region.children[1] = maxb
    return maxa, maxb
}

// split regions take 7 bits plus their descendents
// unsplit regions take 13 bits
// so each split saves 13-7=6 bits on the parent region
// and costs 2*13 = 26 bits on the children, for a net of 20 bits/split
func (region *Region) encode(img image.Image) []int {
    bits := make([]int, 0)
    if region.children[0] != nil {
        bits = append(bits, 1)
        d := region.anchor
        a := region.angle
        bits = append(bits, d&1, d>>1&1)
        bits = append(bits, a&1, a>>1&1, a>>2&1, a>>3&1)
        bits = append(bits, region.children[0].encode(img)...)
        bits = append(bits, region.children[1].encode(img)...)
    } else {
        bits = append(bits, 0)
        r, g, b := region.meanColor(img)
        kr := int(r/256./16.)
        kg := int(g/256./16.)
        kb := int(b/256./16.)
        bits = append(bits, kr&1, kr>>1&1, kr>>2&1, kr>>3)
        bits = append(bits, kg&1, kg>>1&1, kg>>2&1, kg>>3)
        bits = append(bits, kb&1, kb>>1&1, kb>>2&1, kb>>3)
    }
    return bits
}

func encode(name string) []byte {
    file, _ := os.Open(name)
    img, _, _ := image.Decode(file)

    // encoding bit stream
    bits := make([]int, 0)

    // start by encoding the bounds
    bounds := img.Bounds()
    w := bounds.Max.X - bounds.Min.X
    for ; w > 3; w >>= 1 {
        bits = append(bits, 1, w & 1)
    }
    bits = append(bits, 0, w & 1)
    h := bounds.Max.Y - bounds.Min.Y
    for ; h > 3; h >>= 1 {
        bits = append(bits, 1, h & 1)
    }
    bits = append(bits, 0, h & 1)

    // make new region containing whole image
    region := new(Region)
    region.children[0] = nil
    region.children[1] = nil
    for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
        for x := bounds.Min.X; x < bounds.Max.X; x++ {
            region.points = append(region.points, image.Point{x, y})
        }
    }

    // split the region with the most contrast until we're out of bits.
    regions := make([]*Region, 1)
    regions[0] = region
    for bitcnt := len(bits) + 13; bitcnt <= 919-20; bitcnt += 20 {
        var best_reg *Region
        best_dev := -1.0
        for _, reg := range regions {
            if reg.children[0] != nil {
                continue
            }
            dev := reg.deviation(img)
            if dev > best_dev {
                best_reg = reg
                best_dev = dev
            }
        }
        a, b := best_reg.split(img)
        regions = append(regions, a, b)
    }

    // encode regions
    bits = append(bits, region.encode(img)...)

    // convert to tweet
    n := big.NewInt(0)
    for i := 0; i < len(bits); i++ {
        n.SetBit(n, i, uint(bits[i]))
    }
    s := make([]byte,0)
    r := new(big.Int)
    for i := 0; i < 140; i++ {
        n.DivMod(n, big.NewInt(95), r)
        s = append(s, byte(r.Int64() + 32))
    }
    return s
}

// decodes and fills in region.  returns number of bits used.
func (region *Region) decode(bits []int, img *image.RGBA) int {
    if bits[0] == 1 {
        anchors := region.anchors()
        anchor := bits[1] + bits[2]*2
        angle := bits[3] + bits[4]*2 + bits[5]*4 + bits[6]*8
        sin, cos := math.Sincos(float64(angle) * math.Pi / 16.)
        a := new(Region)
        b := new(Region)
        for _, p := range region.points {
            dx := float64(p.X) - anchors[anchor][0]
            dy := float64(p.Y) - anchors[anchor][1]
            if dx * sin + dy * cos >= 0 {
                a.points = append(a.points, p)
            } else {
                b.points = append(b.points, p)
            }
        }
        x := a.decode(bits[7:], img)
        y := b.decode(bits[7+x:], img)
        return 7 + x + y
    }
    r := bits[1] + bits[2]*2 + bits[3]*4 + bits[4]*8
    g := bits[5] + bits[6]*2 + bits[7]*4 + bits[8]*8
    b := bits[9] + bits[10]*2 + bits[11]*4 + bits[12]*8
    c := color.RGBA{uint8(r*16+8), uint8(g*16+8), uint8(b*16+8), 255}
    for _, p := range region.points {
        img.Set(p.X, p.Y, c)
    }
    return 13
}

func decode(name string) image.Image {
    file, _ := os.Open(name)
    length, _ := file.Seek(0, 2)
    file.Seek(0, 0)
    tweet := make([]byte, length)
    file.Read(tweet)

    // convert to bit string
    n := big.NewInt(0)
    m := big.NewInt(1)
    for _, c := range tweet {
        v := big.NewInt(int64(c - 32))
        v.Mul(v, m)
        n.Add(n, v)
        m.Mul(m, big.NewInt(95))
    }
    bits := make([]int, 0)
    for ; n.Sign() != 0; {
        bits = append(bits, int(n.Int64() & 1))
        n.Rsh(n, 1)
    }
    for ; len(bits) < 919; {
        bits = append(bits, 0)
    }

    // extract width and height
    w := 0
    k := 1
    for ; bits[0] == 1; {
        w += k * bits[1]
        k <<= 1
        bits = bits[2:]
    }
    w += k * (2 + bits[1])
    bits = bits[2:]
    h := 0
    k = 1
    for ; bits[0] == 1; {
        h += k * bits[1]
        k <<= 1
        bits = bits[2:]
    }
    h += k * (2 + bits[1])
    bits = bits[2:]

    // make new region containing whole image
    region := new(Region)
    region.children[0] = nil
    region.children[1] = nil
    for y := 0; y < h; y++ {
        for x := 0; x < w; x++ {
            region.points = append(region.points, image.Point{x, y})
        }
    }

    // new image
    img := image.NewRGBA(image.Rectangle{image.Point{0, 0}, image.Point{w, h}})

    // decode regions
    region.decode(bits, img)

    return img
}

func main() {
    if os.Args[1] == "encode" {
        s := encode(os.Args[2])
        file, _ := os.Create(os.Args[3])
        file.Write(s)
        file.Close()
    }
    if os.Args[1] == "decode" {
        img := decode(os.Args[2])
        file, _ := os.Create(os.Args[3])
        png.Encode(file, img)
        file.Close()
    }
}
Keith Randall
quelle
3
Alter, die sehen cool aus.
MrZander
2
Oh mein Gott, das ist super.
Jdstankosky
4
Warte, wo sind deine Saiten?
Jdstankosky
1
Das ist bisher mein Favorit.
Primo
4
+1 für den kubistischen Look.
Ilmari Karonen
36

Python

Für die Codierung sind Numpy , SciPy und Scikit-Image erforderlich .
Für die Dekodierung ist nur PIL erforderlich .

Dies ist eine Methode, die auf Superpixel-Interpolation basiert. Zu Beginn wird jedes Bild in 70 Bereiche mit ähnlicher Größe und ähnlicher Farbe unterteilt. Beispielsweise ist das Landschaftsbild folgendermaßen unterteilt:

Bildbeschreibung hier eingeben

Der Schwerpunkt jeder Region befindet sich (zum nächsten Rasterpunkt in einem Raster mit nicht mehr als 402 Punkten) sowie die durchschnittliche Farbe (aus einer 216-Farben-Palette), und jede dieser Regionen ist als Zahl von 0 codiert bis 86832 , in der Lage, in 2,5 druckbaren ASCII-Zeichen gespeichert zu werden (tatsächlich 2,497 , so dass gerade genug Platz für die Codierung eines Graustufenbits bleibt ).

Wenn Sie aufmerksam sind, haben Sie vielleicht bemerkt, dass 140 / 2,5 = 56 Regionen und nicht 70, wie ich zuvor angegeben habe. Beachten Sie jedoch, dass jede dieser Regionen ein eindeutiges, vergleichbares Objekt ist, das in beliebiger Reihenfolge aufgeführt werden kann. Aus diesem Grund können wir die Permutation der ersten 56 Regionen verwenden, um für die anderen 14 zu codieren , und wir können auch ein paar Bits übrig haben, um das Seitenverhältnis zu speichern.

Insbesondere wird jede der zusätzlichen 14 Regionen in eine Zahl umgewandelt und dann jede dieser Zahlen miteinander verkettet (der aktuelle Wert wird mit 86832 multipliziert und die nächste addiert). Diese (gigantische) Zahl wird dann in eine Permutation für 56 Objekte umgewandelt.

Zum Beispiel:

from my_geom import *

# this can be any value from 0 to 56!, and it will map unambiguously to a permutation
num = 595132299344106583056657556772129922314933943196204990085065194829854239
perm = num2perm(num, 56)
print perm
print perm2num(perm)

wird ausgeben:

[0, 3, 33, 13, 26, 22, 54, 12, 53, 47, 8, 39, 19, 51, 18, 27, 1, 41, 50, 20, 5, 29, 46, 9, 42, 23, 4, 37, 21, 49, 2, 6, 55, 52, 36, 7, 43, 11, 30, 10, 34, 44, 24, 45, 32, 28, 17, 35, 15, 25, 48, 40, 38, 31, 16, 14]
595132299344106583056657556772129922314933943196204990085065194829854239

Die resultierende Permutation wird dann auf die ursprünglichen 56 Regionen angewendet . Die ursprüngliche Nummer (und damit die zusätzlichen 14 Regionen) kann ebenfalls extrahiert werden, indem die Permutation der 56 codierten Regionen in ihre numerische Darstellung umgewandelt wird.

Wenn die --greyscaleOption mit dem Encoder verwendet wird, werden stattdessen 94 Regionen (getrennt 70 , 24 ) mit 558 Rasterpunkten und 16 Graustufen verwendet.

Bei der Dekodierung wird jede dieser Regionen als 3D-Kegel behandelt, der sich von oben betrachtet bis ins Unendliche erstreckt und dessen Scheitelpunkt sich im Schwerpunkt der Region befindet (auch als Voronoi-Diagramm bezeichnet). Die Ränder werden dann zusammengemischt, um das Endprodukt zu erzeugen.

Zukünftige Verbesserungen

  1. Die Abmessungen der Mona Lisa sind etwas unterschiedlich, da ich das Seitenverhältnis speichere. Ich muss ein anderes System verwenden. Behoben, indem angenommen wird, dass das ursprüngliche Seitenverhältnis irgendwo zwischen 1:21 und 21: 1 liegt, was ich für eine vernünftige Annahme halte.
  2. Die Hindenburg könnte stark verbessert werden. Die von mir verwendete Farbpalette enthält nur 6 Graustufen. Wenn ich einen Nur-Graustufen-Modus einführen würde, könnte ich die zusätzlichen Informationen verwenden, um die Farbtiefe, die Anzahl der Regionen, die Anzahl der Rasterpunkte oder eine beliebige Kombination der drei zu erhöhen. Ich habe --greyscaledem Encoder eine Option hinzugefügt , die alle drei unterstützt.
  3. 2d Shapes würden wahrscheinlich besser aussehen, wenn die Überblendung deaktiviert ist. Ich werde wahrscheinlich eine Flagge dafür hinzufügen. Es wurde eine Encoder-Option zur Steuerung des Segmentierungsverhältnisses und eine Decoder-Option zur Deaktivierung der Überblendung hinzugefügt.
  4. Mehr Spaß mit der Kombinatorik. 56! ist tatsächlich groß genug, um 15 zusätzliche Regionen und 15 zu speichern ! ist groß genug, um 2 weitere für insgesamt 73 zu speichern . Aber warte, es gibt noch mehr! Die Aufteilung dieses 73 - Objekt könnte auch mehr Informationen zu speichern , verwendet werden. Zum Beispiel gibt es 73 Auswahlmöglichkeiten 56 , um die ersten 56 Regionen auszuwählen , und dann 17 Auswahlmöglichkeiten 15 , um die nächsten 15 auszuwählen . Insgesamt 2403922132944423072 Partitionen, die groß genug sind, um 3 weitere Regionen für insgesamt 76 zu speichern. Ich würde müssen mit einer cleveren Art und Weise zu entwickeln, um eindeutig Anzahl aller Partitionen von 73 in Gruppen von 56 , 15 , 2 ... und zurück . Vielleicht nicht praktisch, aber ein interessantes Problem, über das man nachdenken sollte.

0VW*`Gnyq;c1JBY}tj#rOcKm)v_Ac\S.r[>,Xd_(qT6 >]!xOfU9~0jmIMG{hcg-'*a.s<X]6*%U5>/FOze?cPv@hI)PjpK9\iA7P ]a-7eC&ttS[]K>NwN-^$T1E.1OH^c0^"J 4V9X

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben


0Jc?NsbD#1WDuqT]AJFELu<!iE3d!BB>jOA'L|<j!lCWXkr:gCXuD=D\BL{gA\ 8#*RKQ*tv\\3V0j;_4|o7>{Xage-N85):Q/Hl4.t&'0pp)d|Ry+?|xrA6u&2E!Ls]i]T<~)58%RiA

und

4PV 9G7X|}>pC[Czd!5&rA5 Eo1Q\+m5t:r#;H65NIggfkw'h4*gs.:~<bt'VuVL7V8Ed5{`ft7e>HMHrVVUXc.{#7A|#PBm,i>1B781.K8>s(yUV?a<*!mC@9p+Rgd<twZ.wuFnN dp

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Das zweite ist mit der --greyscaleOption verschlüsselt .


3dVY3TY?9g+b7!5n`)l"Fg H$ 8n?[Q-4HE3.c:[pBBaH`5'MotAj%a4rIodYO.lp$h a94$n!M+Y?(eAR,@Y*LiKnz%s0rFpgnWy%!zV)?SuATmc~-ZQardp=?D5FWx;v=VA+]EJ(:%

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Kodiert mit der --greyscaleOption.


.9l% Ge<'_)3(`DTsH^eLn|l3.D_na,,sfcpnp{"|lSv<>}3b})%m2M)Ld{YUmf<Uill,*:QNGk,'f2; !2i88T:Yjqa8\Ktz4i@h2kHeC|9,P` v7Xzd Yp&z:'iLra&X&-b(g6vMq

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Codiert mit --ratio 60und decodiert mit --no-blendingOptionen.


encoder.py

from __future__ import division
import argparse, numpy
from skimage.io import imread
from skimage.transform import resize
from skimage.segmentation import slic
from skimage.measure import regionprops
from my_geom import *

def encode(filename, seg_ratio, greyscale):
  img = imread(filename)

  height = len(img)
  width = len(img[0])
  ratio = width/height

  if greyscale:
    raster_size = 558
    raster_ratio = 11
    num_segs = 94
    set1_len = 70
    max_num = 8928  # 558 * 16
  else:
    raster_size = 402
    raster_ratio = 13
    num_segs = 70
    set1_len = 56
    max_num = 86832 # 402 * 216

  raster_width = (raster_size*ratio)**0.5
  raster_height = int(raster_width/ratio)
  raster_width = int(raster_width)

  resize_height = raster_height * raster_ratio
  resize_width = raster_width * raster_ratio

  img = resize(img, (resize_height, resize_width))

  segs = slic(img, n_segments=num_segs-4, ratio=seg_ratio).astype('int16')

  max_label = segs.max()
  numpy.place(segs, segs==0, [max_label+1])
  regions = [None]*(max_label+2)

  for props in regionprops(segs):
    label = props['Label']
    props['Greyscale'] = greyscale
    regions[label] = Region(props)

  for i, a in enumerate(regions):
    for j, b in enumerate(regions):
      if a==None or b==None or a==b: continue
      if a.centroid == b.centroid:
        numpy.place(segs, segs==j, [i])
        regions[j] = None

  for y in range(resize_height):
    for x in range(resize_width):
      label = segs[y][x]
      regions[label].add_point(img[y][x])

  regions = [r for r in regions if r != None]

  if len(regions)>num_segs:
    regions = sorted(regions, key=lambda r: r.area)[-num_segs:]

  regions = sorted(regions, key=lambda r: r.to_num(raster_width))

  set1, set2 = regions[-set1_len:], regions[:-set1_len]

  set2_num = 0
  for s in set2:
    set2_num *= max_num
    set2_num += s.to_num(raster_width)

  set2_num = ((set2_num*85 + raster_width)*85 + raster_height)*25 + len(set2)
  perm = num2perm(set2_num, set1_len)
  set1 = permute(set1, perm)

  outnum = 0
  for r in set1:
    outnum *= max_num
    outnum += r.to_num(raster_width)

  outnum *= 2
  outnum += greyscale

  outstr = ''
  for i in range(140):
    outstr = chr(32 + outnum%95) + outstr
    outnum //= 95

  print outstr

parser = argparse.ArgumentParser(description='Encodes an image into a tweetable format.')
parser.add_argument('filename', type=str,
  help='The filename of the image to encode.')
parser.add_argument('--ratio', dest='seg_ratio', type=float, default=30,
  help='The segmentation ratio. Higher values (50+) will result in more regular shapes, lower values in more regular region color.')
parser.add_argument('--greyscale', dest='greyscale', action='store_true',
  help='Encode the image as greyscale.')
args = parser.parse_args()

encode(args.filename, args.seg_ratio, args.greyscale)

decoder.py

from __future__ import division
import argparse
from PIL import Image, ImageDraw, ImageChops, ImageFilter
from my_geom import *

def decode(instr, no_blending=False):
  innum = 0
  for c in instr:
    innum *= 95
    innum += ord(c) - 32

  greyscale = innum%2
  innum //= 2

  if greyscale:
    max_num = 8928
    set1_len = 70
    image_mode = 'L'
    default_color = 0
    raster_ratio = 11
  else:
    max_num = 86832
    set1_len = 56
    image_mode = 'RGB'
    default_color = (0, 0, 0)
    raster_ratio = 13

  nums = []
  for i in range(set1_len):
    nums = [innum%max_num] + nums
    innum //= max_num

  set2_num = perm2num(nums)

  set2_len = set2_num%25
  set2_num //= 25

  raster_height = set2_num%85
  set2_num //= 85
  raster_width = set2_num%85
  set2_num //= 85

  resize_width = raster_width*raster_ratio
  resize_height = raster_height*raster_ratio

  for i in range(set2_len):
    nums += set2_num%max_num,
    set2_num //= max_num

  regions = []
  for num in nums:
    r = Region()
    r.from_num(num, raster_width, greyscale)
    regions += r,

  masks = []

  outimage = Image.new(image_mode, (resize_width, resize_height), default_color)

  for a in regions:
    mask = Image.new('L', (resize_width, resize_height), 255)
    for b in regions:
      if a==b: continue
      submask = Image.new('L', (resize_width, resize_height), 0)
      poly = a.centroid.bisected_poly(b.centroid, resize_width, resize_height)
      ImageDraw.Draw(submask).polygon(poly, fill=255, outline=255)
      mask = ImageChops.multiply(mask, submask)
    outimage.paste(a.avg_color, mask=mask)

  if not no_blending:
    outimage = outimage.resize((raster_width, raster_height), Image.ANTIALIAS)
    outimage = outimage.resize((resize_width, resize_height), Image.BICUBIC)
    smooth = ImageFilter.Kernel((3,3),(1,2,1,2,4,2,1,2,1))
    for i in range(20):outimage = outimage.filter(smooth)
  outimage.show()

parser = argparse.ArgumentParser(description='Decodes a tweet into and image.')
parser.add_argument('--no-blending', dest='no_blending', action='store_true',
    help="Do not blend the borders in the final image.")
args = parser.parse_args()

instr = raw_input()
decode(instr, args.no_blending)

my_geom.py

from __future__ import division

class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y
    self.xy = (x, y)

  def __eq__(self, other):
    return self.x == other.x and self.y == other.y

  def __lt__(self, other):
    return self.y < other.y or (self.y == other.y and self.x < other.x)

  def inv_slope(self, other):
    return (other.x - self.x)/(self.y - other.y)

  def midpoint(self, other):
    return Point((self.x + other.x)/2, (self.y + other.y)/2)

  def dist2(self, other):
    dx = self.x - other.x
    dy = self.y - other.y
    return dx*dx + dy*dy

  def bisected_poly(self, other, resize_width, resize_height):
    midpoint = self.midpoint(other)
    points = []
    if self.y == other.y:
      points += (midpoint.x, 0), (midpoint.x, resize_height)
      if self.x < midpoint.x:
        points += (0, resize_height), (0, 0)
      else:
        points += (resize_width, resize_height), (resize_width, 0)
      return points
    elif self.x == other.x:
      points += (0, midpoint.y), (resize_width, midpoint.y)
      if self.y < midpoint.y:
        points += (resize_width, 0), (0, 0)
      else:
        points += (resize_width, resize_height), (0, resize_height)
      return points
    slope = self.inv_slope(other)
    y_intercept = midpoint.y - slope*midpoint.x
    if self.y > midpoint.y:
      points += ((resize_height - y_intercept)/slope, resize_height),
      if slope < 0:
        points += (resize_width, slope*resize_width + y_intercept), (resize_width, resize_height)
      else:
        points += (0, y_intercept), (0, resize_height)
    else:
      points += (-y_intercept/slope, 0),
      if slope < 0:
        points += (0, y_intercept), (0, 0)
      else:
        points += (resize_width, slope*resize_width + y_intercept), (resize_width, 0)
    return points

class Region:
  def __init__(self, props={}):
    if props:
      self.greyscale = props['Greyscale']
      self.area = props['Area']
      cy, cx = props['Centroid']
      if self.greyscale:
        self.centroid = Point(int(cx/11)*11+5, int(cy/11)*11+5)
      else:
        self.centroid = Point(int(cx/13)*13+6, int(cy/13)*13+6)
    self.num_pixels = 0
    self.r_total = 0
    self.g_total = 0
    self.b_total = 0

  def __lt__(self, other):
    return self.centroid < other.centroid

  def add_point(self, rgb):
    r, g, b = rgb
    self.r_total += r
    self.g_total += g
    self.b_total += b
    self.num_pixels += 1
    if self.greyscale:
      self.avg_color = int((3.2*self.r_total + 10.7*self.g_total + 1.1*self.b_total)/self.num_pixels + 0.5)*17
    else:
      self.avg_color = (
        int(5*self.r_total/self.num_pixels + 0.5)*51,
        int(5*self.g_total/self.num_pixels + 0.5)*51,
        int(5*self.b_total/self.num_pixels + 0.5)*51)

  def to_num(self, raster_width):
    if self.greyscale:
      raster_x = int((self.centroid.x - 5)/11)
      raster_y = int((self.centroid.y - 5)/11)
      return (raster_y*raster_width + raster_x)*16 + self.avg_color//17
    else:
      r, g, b = self.avg_color
      r //= 51
      g //= 51
      b //= 51
      raster_x = int((self.centroid.x - 6)/13)
      raster_y = int((self.centroid.y - 6)/13)
      return (raster_y*raster_width + raster_x)*216 + r*36 + g*6 + b

  def from_num(self, num, raster_width, greyscale):
    self.greyscale = greyscale
    if greyscale:
      self.avg_color = num%16*17
      num //= 16
      raster_x, raster_y = num%raster_width, num//raster_width
      self.centroid = Point(raster_x*11 + 5, raster_y*11+5)
    else:
      rgb = num%216
      r, g, b = rgb//36, rgb//6%6, rgb%6
      self.avg_color = (r*51, g*51, b*51)
      num //= 216
      raster_x, raster_y = num%raster_width, num//raster_width
      self.centroid = Point(raster_x*13 + 6, raster_y*13 + 6)

def perm2num(perm):
  num = 0
  size = len(perm)
  for i in range(size):
    num *= size-i
    for j in range(i, size): num += perm[j]<perm[i]
  return num

def num2perm(num, size):
  perm = [0]*size
  for i in range(size-1, -1, -1):
    perm[i] = int(num%(size-i))
    num //= size-i
    for j in range(i+1, size): perm[j] += perm[j] >= perm[i]
  return perm

def permute(arr, perm):
  size = len(arr)
  out = [0] * size
  for i in range(size):
    val = perm[i]
    out[i] = arr[val]
  return out
primo
quelle
1
Das ist nichts
weniger als
Die Farbversion der Mona Lisa sieht aus wie einer ihrer Brüste geknallt. Scherz beiseite, das ist unglaublich.
Jdstankosky
4
Die Verwendung der Permutationen zum Codieren zusätzlicher Daten ist ziemlich clever.
Sir_Lagsalot
Wirklich, wirklich großartig. Können Sie eine Zusammenfassung mit diesen 3 Dateien machen? gist.github.com
rubik
2
@ Rubik es ist unglaublich verlustreich, wie alle Lösungen für diese Herausforderung sind;)
Primo
17

PHP

OK, ich habe eine Weile gebraucht, aber hier ist es. Alle Bilder in Graustufen. Farben brauchten zu viele Bits, um sie für meine Methode zu codieren: P


Mona Lisa
47 Colors Monochrome
101- Byte-Zeichenfolge.

dt99vvv9t8G22+2eZbbf55v3+fAH9X+AD/0BAF6gIOX5QRy7xX8em9/UBAEVXKiiqKqqqiqqqqNqqqivtXqqMAFVUBVVVVVVVVVVU

mona Lisa


2D-Formen
36 Farben Monochrome
105- Byte-Zeichenfolge.

oAAAAAAABMIDUAAEBAyoAAAAAgAwAAAAADYBtsAAAJIDbYAAAAA22AGwAAAAAGwAAAAAAAAAAKgAAAAAqgAAAACoAAAAAAAAAAAAAAAAA

2d 2dc


Hindenburg
62 Colors Monochrome
112 Zeichen.

t///tCSuvv/99tmwBI3/21U5gCW/+2bdDMxLf+r6VsaHb/tt7TAodv+NhtbFVX/bGD1IVq/4MAHbKq/4AABbVX/AQAFN1f8BCBFntb/6ttYdWnfg

Bilder hier Bildbeschreibung hier eingeben


Berge
63 Farben Monochrom
122 Zeichen.

qAE3VTkaIAKgqSFigAKoABgQEqAABuAgUQAGenRIBoUh2eqhABCee/2qSSAQntt/s2kJCQbf/bbaJgbWebzqsPZ7bZttwABTc3VAUFDbKqqpzY5uqpudnp5vZg

Bilder hier Bildbeschreibung hier eingeben


Meine Methode

Ich codiere meinen Bitstream mit einer Art Base64-Codierung. Bevor es in lesbaren Text kodiert wird, geschieht Folgendes.

Ich lade das Quellbild und verändere es auf eine maximale Höhe oder Breite (je nach Ausrichtung, Hoch- / Querformat) von 20 Pixel.

Als nächstes färbe ich jedes Pixel des neuen Bildes auf einer 6-Farben-Graustufen-Palette neu ein, um die bestmögliche Übereinstimmung zu erzielen.

Danach erstelle ich eine Zeichenfolge mit jeder durch die Buchstaben [AF] dargestellten Pixelfarbe.

Ich berechne dann die Verteilung der 6 verschiedenen Buchstaben in der Zeichenfolge und wähle den optimierten Binärbaum für die Codierung basierend auf den Buchstabenhäufigkeiten aus. Es gibt 15 mögliche binäre Bäume.

Ich starte meinen Bitstream mit einem einzelnen Bit, [1|0]je nachdem, ob das Bild groß oder breit ist. Ich benutze dann die nächsten 4 Bits im Stream, um dem Decoder mitzuteilen, welcher Binärbaum zum Decodieren des Bildes verwendet werden soll.

Was folgt, ist der Bitstrom, der das Bild darstellt. Jedes Pixel und seine Farbe wird durch 2 oder 3 Bits dargestellt. Auf diese Weise kann ich für jedes gedruckte ASCII-Zeichen mindestens 2 bis 3 Pixel an Informationen speichern. Hier ist ein Beispiel eines Binärbaums 1110, der von der Mona Lisa verwendet wird:

    TREE
   /    \
  #      #
 / \    / \
E   #  F   #
   / \    / \
  A   B  C   D

Die Buchstaben E 00und F 10sind die häufigsten Farben in der Mona Lisa. A 010, B 011, C 110und D 111sind am seltensten.

Binäre Bäume funktionieren wie folgt: Von Bit zu Bit 0gehen , heißt nach links gehen, 1heißt nach rechts gehen. Fahren Sie fort, bis Sie ein Blatt am Baum oder eine Sackgasse treffen. Das Blatt, auf dem Sie landen, ist der Charakter, den Sie wollen.

Wie auch immer, ich codiere den Binärstich in base64-Zeichen. Beim Dekodieren der Zeichenfolge erfolgt der Vorgang in umgekehrter Reihenfolge, wobei alle Pixel der entsprechenden Farbe zugewiesen werden. Anschließend wird das Bild doppelt so groß wie die kodierte Größe skaliert (maximal 40 Pixel, entweder X oder Y, je nachdem, welcher Wert größer ist). Anschließend wird eine Faltungsmatrix erstellt auf das Ganze aufgetragen, um die Farben zu glätten.

Wie auch immer, hier ist der aktuelle Code: " Pastebin Link "

Es ist hässlich, aber wenn Sie Raum für Verbesserungen sehen, lassen Sie es mich wissen. Ich habe es zusammen gehackt, wie ich es will. I GELERNT VIEL VON DIESER CHALLENGE. Vielen Dank, dass Sie OP für die Veröffentlichung!

jdstankosky
quelle
2
Diese sehen unglaublich gut aus, wenn man bedenkt, wie viel ungenutzten Speicherplatz Sie haben (Mona Lisa verwendet nur 606 Bits von 920 verfügbaren!).
Primo
Danke, primo, das weiß ich wirklich zu schätzen. Ich bewundere Ihre Arbeit immer, also ist es ziemlich schmeichelhaft, wenn Sie das sagen!
Jdstankosky
13

Mein erster Versuch. Dies ist verbesserungswürdig. Ich denke, dass das Format selbst tatsächlich funktioniert, das Problem liegt im Encoder. Das, und ich vermisse einzelne Bits in meiner Ausgabe ... meine (etwas höhere Qualität als hier) Datei endete mit 144 Zeichen, wenn noch einige übrig sein sollten. (und ich wünschte wirklich, es gäbe - die Unterschiede zwischen diesen und diesen sind spürbar). Ich habe jedoch gelernt, niemals zu überschätzen, wie groß 140 Zeichen sind ...

Ich habe es auf eine modifizierte Version der RISC-OS-Palette gebracht - im Grunde genommen, weil ich eine 32-Farben-Palette brauchte, und das schien ein guter Anfang zu sein. Ich denke, das könnte sich auch ändern. Palette

Ich zerlege es in die folgenden Formen: Formen und teile das Bild in Palettenblöcke (in diesem Fall 2x2 Pixel) einer Vorder- und Rückseite.

Ergebnisse:

Es folgen die Tweets, die Originale und wie der Tweet dekodiert wird

*=If`$aX:=|"&brQ(EPZwxu4H";|-^;lhJCfQ(W!TqWTai),Qbd7CCtmoc(-hXt]/l87HQyaYTEZp{eI`/CtkHjkFh,HJWw%5[d}VhHAWR(@;M's$VDz]17E@6

Hindeberg Mein Hindenberg

"&7tpnqK%D5kr^u9B]^3?`%;@siWp-L@1g3p^*kQ=5a0tBsA':C0"*QHVDc=Z='Gc[gOpVcOj;_%>.aeg+JL4j-u[a$WWD^)\tEQUhR]HVD5_-e`TobI@T0dv_el\H1<1xw[|D

Berg Mein Berg

)ey`ymlgre[rzzfi"K>#^=z_Wi|@FWbo#V5|@F)uiH?plkRS#-5:Yi-9)S3:#3 Pa4*lf TBd@zxa0g;li<O1XJ)YTT77T1Dg1?[w;X"U}YnQE(NAMQa2QhTMYh..>90DpnYd]?

Formen Meine Formen

%\MaaX/VJNZX=Tq,M>2"AwQVR{(Xe L!zb6(EnPuEzB}Nk:U+LAB_-K6pYlue"5*q>yDFw)gSC*&,dA98`]$2{&;)[ 4pkX |M _B4t`pFQT8P&{InEh>JHYn*+._[b^s754K_

Mona Lisa Mona Lisa Mine

Ich weiß, dass die Farben falsch sind, aber ich mag die Monalisa. Wenn ich die Unschärfe entfernt hätte (was nicht zu schwer wäre), hätte ich einen vernünftigen kubistischen Eindruck: p

Ich muss daran arbeiten

  • Formerkennung hinzufügen
  • Ein besserer Algorithmus für Farbunterschiede
  • Herauszufinden, wo meine fehlenden Teile waren

Ich werde später versuchen, diese Probleme zu beheben und den Encoder zu verbessern. Diese zusätzlichen 20 Charaktere machen einen gewaltigen Unterschied. Ich würde sie gerne zurückhaben.

Die C # -Quelle und die Farbpalette befinden sich unter https://dl.dropboxusercontent.com/u/46145976/Base96.zip - obwohl dies im Nachhinein möglicherweise nicht einwandfrei funktioniert, wenn sie separat ausgeführt werden (da Leerzeichen in Argumenten für Programme nicht erforderlich sind) Gut).

Der Encoder benötigt auf meinem durchschnittlichen Rechner weniger als ein paar Sekunden.

Lochok
quelle
11
Kumpel. Diese sehen besser aus als jede zeitgenössische Kunst, die ich in einer Galerie gesehen habe ... Sie sollten riesige Abzüge davon machen und sie verkaufen!
Jdstankosky
1
Es sieht so aus, als müsste ich die Patrone aus meinem Atari nehmen und wieder einstecken. Ich mag es.
undergroundmonorail
13

Ich gab den Versuch auf, die Farbe zu behalten und wurde schwarz und weiß, da alles, was ich mit Farbe versuchte, nicht wiederzuerkennen war.

Im Grunde ist alles, was es tut, Pixel in 3 ungefähr gleiche Teile zu teilen: Schwarz, Grau und Weiß. Es hält auch nicht die Größe.

Hindenburg

~62RW.\7`?a9}A.jvCedPW0t)]g/e4 |+D%n9t^t>wO><",C''!!Oh!HQq:WF>\uEG?E=Mkj|!u}TC{7C7xU:bb`We;3T/2:Zw90["$R25uh0732USbz>Q;q"

Hindenburg HindenburgKomprimiert

Mona Lisa

=lyZ(i>P/z8]Wmfu>] T55vZB:/>xMz#Jqs6U3z,)n|VJw<{Mu2D{!uyl)b7B6x&I"G0Y<wdD/K4hfrd62_8C\W7ArNi6R\Xz%f U[);YTZFliUEu{m%[gw10rNY_`ICNN?_IB/C&=T

Mona Lisa MonaLisaCompressed

Berge

+L5#~i%X1aE?ugVCulSf*%-sgIg8hQ3j/df=xZv2v?'XoNdq=sb7e '=LWm\E$y?=:"#l7/P,H__W/v]@pwH#jI?sx|n@h\L %y(|Ry.+CvlN $Kf`5W(01l2j/sdEjc)J;Peopo)HJ

Berge BergeKomprimiert

Formen

3A"3yD4gpFtPeIImZ$g&2rsdQmj]}gEQM;e.ckbVtKE(U$r?{,S>tW5JzQZDzoTy^mc+bUV vTUG8GXs{HX'wYR[Af{1gKwY|BD]V1Z'J+76^H<K3Db>Ni/D}][n#uwll[s'c:bR56:

Formen ShapesCompressed

Hier ist das Programm. python compress.py -c img.pngkomprimiert img.pngund druckt den Tweet.

python compress.py -d img.pngNimmt den Tweet von stdin und speichert das Bild in img.png.

from PIL import Image
import sys
quanta  = 3
width   = 24
height  = 24

def compress(img):
    pix = img.load()
    psums = [0]*(256*3)
    for x in range(width):
        for y in range(height):
            r,g,b,a = pix[x,y]
            psums[r+g+b] += 1
    s = 0
    for i in range(256*3):
        s = psums[i] = psums[i]+s

    i = 0
    for x in range(width):
        for y in range(height):
            r,g,b,a = pix[x,y]
            t = psums[r+g+b]*quanta / (width*height)
            if t == quanta:
                t -= 1
            i *= quanta
            i += t
    s = []
    while i:
        s += chr(i%95 + 32)
        i /= 95
    return ''.join(s)

def decompress(s):
    i = 0
    for c in s[::-1]:
        i *= 95
        i += ord(c) - 32
    img = Image.new('RGB',(width,height))
    pix = img.load()
    for x in range(width)[::-1]:
        for y in range(height)[::-1]:
            t = i % quanta
            i /= quanta
            t *= 255/(quanta-1)
            pix[x,y] = (t,t,t)
    return img

if sys.argv[1] == '-c':
    img = Image.open(sys.argv[2]).resize((width,height))
    print compress(img)
elif sys.argv[1] == '-d':
    img = decompress(raw_input())
    img.resize((256,256)).save(sys.argv[2],'PNG')
Pappkarton
quelle
Lol, +1 für nicht beschränkte Seitenverhältnisse.
Jdstankosky
7

Mein bescheidener Beitrag in R:

encoder<-function(img_file){
    img0 <- as.raster(png::readPNG(img_file))
    d0 <- dim(img0)
    r <- d0[1]/d0[2]
    f <- floor(sqrt(140/r))
    d1 <- c(floor(f*r),f)
    dx <- floor(d0[2]/d1[2])
    dy <- floor(d0[1]/d1[1])
    img1 <- matrix("",ncol=d1[2],nrow=d1[1])
    x<-seq(1,d0[1],by=dy)
    y<-seq(1,d0[2],by=dx)
    for(i in seq_len(d1[1])){
        for (j in seq_len(d1[2])){
            img1[i,j]<-names(which.max(table(img0[x[i]:(x[i]+dy-1),y[j]:(y[j]+dx-1)])))
            }
        }
    img2 <- as.vector(img1)
    table1 <- array(sapply(seq(0,255,length=4),function(x)sapply(seq(0,255,length=4),function(y)sapply(seq(0,255,length=4),function(z)rgb(x/255,y/255,z/255)))),dim=c(4,4,4))
    table2 <- array(strsplit(rawToChar(as.raw(48:(48+63))),"")[[1]],dim=c(4,4,4))
    table3 <- cbind(1:95,sapply(32:126,function(x)rawToChar(as.raw(x))))
    a <- as.array(cut(colorspace::hex2RGB(img2)@coords,breaks=seq(0,1,length=5),include.lowest=TRUE))
    dim(a) <- c(length(img2),3)
    img3 <- apply(a,1,function(x)paste("#",c("00","55","AA","FF")[x[1]],c("00","55","AA","FF")[x[2]],c("00","55","AA","FF")[x[3]],sep=""))
    res<-paste(sapply(img3,function(x)table2[table1==x]),sep="",collapse="")
    paste(table3[table3[,1]==d1[1],2],table3[table3[,1]==d1[2],2],res,collapse="",sep="")
    }

decoder<-function(string){
    s <- unlist(strsplit(string,""))
    table1 <- array(sapply(seq(0,255,length=4),function(x)sapply(seq(0,255,length=4),function(y)sapply(seq(0,255,length=4),function(z)rgb(x/255,y/255,z/255)))),dim=c(4,4,4))
    table2 <- array(strsplit(rawToChar(as.raw(48:(48+63))),"")[[1]],dim=c(4,4,4))
    table3 <- cbind(1:95,sapply(32:126,function(x)rawToChar(as.raw(x))))
    nr<-as.integer(table3[table3[,2]==s[1],1])
    nc<-as.integer(table3[table3[,2]==s[2],1])
    img <- sapply(s[3:length(s)],function(x){table1[table2==x]})
    png(w=nc,h=nr,u="in",res=100)
    par(mar=rep(0,4))
    plot(c(1,nr),c(1,nc),type="n",axes=F,xaxs="i",yaxs="i")
    rasterImage(as.raster(matrix(img,nr,nc)),1,1,nr,nc)
    dev.off()
    }

Die Idee ist einfach, das Raster (Datei muss in png sein) auf eine Matrix zu reduzieren, deren Zellenzahl niedriger als 140 ist. Die Tweets sind dann eine Reihe von Farben (in 64 Farben), denen zwei Zeichen vorangestellt sind, die die Anzahl der Zeilen angeben und Spalten des Rasters.

encoder("Mona_Lisa.png")
[1] ",(XXX000@000000XYi@000000000TXi0000000000TX0000m000h00T0hT@hm000000T000000000000XX00000000000XXi0000000000TXX0000000000"

Bildbeschreibung hier eingeben

encoder("630x418.png") # Not a huge success for this one :)
[1] "(-00000000000000000000EEZZooo00E0ZZooo00Z00Zooo00Zo0oooooEZ0EEZoooooooEZo0oooooo000ooZ0Eo0000oooE0EE00oooEEEE0000000E00000000000"

Bildbeschreibung hier eingeben

encoder("2d shapes.png")
[1] "(,ooooooooooooooooooooo``ooooo0o``oooooooooo33ooooooo33oo0ooooooooooo>>oooo0oooooooo0ooooooooooooolloooo9oolooooooooooo"

Bildbeschreibung hier eingeben

encoder("mountains.png")
[1] "(,_K_K0005:_KKK0005:__OJJ006:_oKKK00O:;;_K[[4OD;;Kooo4_DOKK_o^D_4KKKJ_o5o4KK__oo4_0;K___o5JDo____o5Y0____440444040400D4"

Bildbeschreibung hier eingeben

Plannapus
quelle
4

Keine vollständige Lösung, sondern nur die Methode. (Matlab)

Ich habe eine 16-Farben-Palette und eine 40-Positionen-Palette verwendet, um ein gewichtetes Voronoi-Diagramm zu erstellen . Verwendet einen genetischen Algorithmus und einen einfachen Algorithmus zum Bergsteigen, um das Bild anzupassen.

Album mit Originalbild und ich habe auch eine 16 Byte Version mit 4 Farben und festen Positionen dort. :)

Bildbeschreibung hier eingeben

(Kann ich hier die Bildgröße ändern?)

randomra
quelle
1
Können Sie die anderen Bilder posten? Ich möchte sehen, wie sie mit dieser Komprimierung aussehen!
Jdstankosky
@jdstankosky Entschuldigung, ich kann es jetzt nicht tun. Vielleicht einige Zeit später ...
Randomra
4

C #

Update - Version 2


Ich habe einen weiteren Versuch unternommen und jetzt MagickImage.NET ( https://magick.codeplex.com/ ) zum Codieren der JPEG-Daten verwendet. Ich habe auch einige grundlegende Codes geschrieben, um JPEG-Header-Daten besser zu verarbeiten (wie von primo vorgeschlagen) hat GuassianBlur für die Ausgabe verwendet, um die JPEG-Komprimierung etwas abzumildern. Da die neue Version besser funktioniert, habe ich meinen Beitrag aktualisiert, um die neue Methode widerzuspiegeln.


Methode


Ich habe (hoffentlich) etwas Einzigartiges ausprobiert, anstatt zu versuchen, die Farbtiefe oder Kantenidentifikation zu manipulieren oder die Bildgröße auf unterschiedliche Weise zu reduzieren. Ich habe den JPEG-Algorithmus bei maximaler Komprimierung für verkleinerte Versionen von verwendet die Bilder, dann durch Eliminieren von allem, außer dem "StartOfScan" ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) und ein paar wichtigen Header-Elementen, kann ich die Größe auf einen akzeptablen Wert reduzieren. Die Ergebnisse sind für 140 Zeichen tatsächlich ziemlich beeindruckend, was mir neuen Respekt für JPEGs verschafft:

Hindenburg

Hindenburg Original

,$`"(b $!   _ &4j6k3Qg2ns2"::4]*;12T|4z*4n*4<T~a4- ZT_%-.13`YZT;??e#=*!Q033*5>z?1Ur;?2i2^j&r4TTuZe2444b*:>z7.:2m-*.z?|*-Pq|*,^Qs<m&?:e-- 

Berge

Berge Original

,$  (a`,!  (1 Q$ /P!U%%%,0b*2nr4 %)3t4 +3#UsZf3S2 7-+m1Yqis k2U'm/#"h q2T4#$s.]/)%1T &*,4Ze w$Q2Xqm&: %Q28qiqm Q,48Xq12 _

Mona Lisa

Mona Lisa Original

23  (a`,!  (1 Q$ /P q1Q2Tc$q0,$9--/!p Ze&:6`#*,Tj6l0qT%(:!m!%(84|TVk0(*2k24P)!e(U,q2x84|Tj*8a1a-%** $r4_--Xr&)12Tj8a2Tj* %r444 %%%% !

Formen

Formen Original

(ep 1# ,!  (1 Q$ /P"2`#=WTp $X[4 &[Vp p<T +0 cP* 0W=["jY5cZ9(4 (<]t  ]Z %ZT -P!18=V+UZ4" #% i6%r}#"l p QP>*r $!Yq(!]2 jo* zp!0 4 % !0 4 % '!


Code


Version 2 - http://pastebin.com/Tgr8XZUQ

Ich fange wirklich an, ReSharper zu verpassen + Ich habe eine Menge Dinge zu verbessern, immer noch viel hartes Programmieren, aber interessant, damit es in VS läuft.


Original (veraltet) - http://pastebin.com/BDPT0BKT

Immer noch ein bisschen chaotisch.

David Rogers
quelle
"Das ist im Moment wirklich ein Durcheinander", stimme ich dem zu - es muss doch einen besseren Weg geben, um diesen Header zu generieren? Aber ich nehme an, dass die Ergebnisse am wichtigsten sind. +1
Primo
1

Python 3

Methode

Zunächst verkleinert das Programm das Bild und verkleinert es erheblich.

Zweitens wandelt es die RGB-Werte in Binärwerte um und schneidet die letzten Ziffern ab.

Dann konvertiert es die Daten der Basis 2 in die Basis 10, wo es die Abmessungen des Bildes hinzufügt.

Dann konvertiert es die Daten in der Basis 10 in die Basis 95 und verwendet dabei alle gefundenen ASCII-Werte. Allerdings konnte ich / x01 und ähnliches nicht verwenden, da es die Funktion negieren konnte, mit der die Textdatei geschrieben wurde.

Und (aus Gründen der Mehrdeutigkeit) erfolgt die Dekodierung in umgekehrter Reihenfolge.

compress.py

    from PIL import Image
def FromBase(digits, b): #converts to base 10 from base b
    numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?`~\\ '''
    D=[]
    for d in range(0,len(digits)):
        D.append(numerals.index(digits[d]))
    s=0
    D=D[::-1]
    for x in range(0,len(D)):
        s+=D[x]*(b**x)
    return(str(s))
def ToBase(digits,b): #converts from base 10 to base b
    numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?`~\\ '''
    d=int(digits)
    D=''
    B=b
    while(B<=d):
        B*=b
    B//=b
    while(B>=1):
        D+=numerals[d//B]
        d-=((d//B)*B)
        B//=b
    return(D)
im=Image.open('1.png')
size=im.size
scale_factor=40
im=im.resize((int(size[0]/scale_factor),int(size[1]/scale_factor)), Image.ANTIALIAS)
a=list(im.getdata())
K=''
for x in a:
    for y in range(0,3):
        Y=bin(x[y])[2:]
        while(len(Y))<9:
            Y='0'+Y
        K+=str(Y)[:-5]
K='1'+K
print(len(K))
K=FromBase(K,2)
K+=str(size[0])
K+=str(size[1])
K=ToBase(K,95)
with open('1.txt', 'w') as outfile:
    outfile.write(K)

decode.py

    from random import randint, uniform
from PIL import Image, ImageFilter
import math
import json
def FromBase(digits, b): #str converts to base 10 from base b
    numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?`~\\ \x01\x02\x03\x04\x05\x06\x07'''
    D=[]
    for d in range(0,len(digits)):
        D.append(numerals.index(digits[d]))
    s=0
    D=D[::-1]
    for x in range(0,len(D)):
        s+=D[x]*(b**x)
    return(str(s))
def ToBase(digits,b): #str converts from base 10 to base b
    numerals='''0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!@#$%^&*()_-+={[}]|:;"',<.>/?`~\\ \x01\x02\x03\x04\x05\x06\x07'''
    d=int(digits)
    D=''
    B=b
    while(B<=d):
        B*=b
    B//=b
    while(B>=1):
        D+=numerals[d//B]
        d-=((d//B)*B)
        B//=b
    return(D)
scale_factor=40
K=open('1.txt', 'r').read()
K=FromBase(K,95)
size=[int(K[-6:][:-3])//scale_factor,int(K[-6:][-3:])//scale_factor]
K=K[:-6]
K=ToBase(K,2)
K=K[1:]
a=[]
bsize=4
for x in range(0,len(K),bsize*3):
    Y=''
    for y in range(0,bsize*3):
        Y+=K[x+y]
    y=[int(Y[0:bsize]+'0'*(9-bsize)),int(Y[bsize:bsize*2]+'0'*(9-bsize)),int(Y[bsize*2:bsize*3]+'0'*(9-bsize))]
    y[0]=int(FromBase(str(y[0]),2))
    y[1]=int(FromBase(str(y[1]),2))
    y[2]=int(FromBase(str(y[2]),2))
    a.append(tuple(y))
im=Image.new('RGB',size,'black')
im.putdata(a[:size[0]*size[1]])
im=im.resize((int(size[0]*scale_factor),int(size[1]*scale_factor)), Image.ANTIALIAS)
im.save('pic.png')

Der Schrei

Scream1 Scream2

hqgyXKInZo9-|A20A*53ljh[WFUYu\;eaf_&Y}V/@10zPkh5]6K!Ur:BDl'T/ZU+`xA4'\}z|8@AY/5<cw /8hQq[dR1S 2B~aC|4Ax"d,nX`!_Yyk8mv6Oo$+k>_L2HNN.#baA

Mona Lisa

Mona Lisa 1 Mona Lisa 2

f4*_!/J7L?,Nd\#q$[f}Z;'NB[vW%H<%#rL_v4l_K_ >gyLMKf; q9]T8r51it$/e~J{ul+9<*nX0!8-eJVB86gh|:4lsCumY4^y,c%e(e3>sv(.y>S8Ve.tu<v}Ww=AOLrWuQ)

Kugeln

Kugeln 1 Kugeln 2

})|VF/h2i\(D?Vgl4LF^0+zt$d}<M7E5pTA+=Hr}{VxNs m7Y~\NLc3Q"-<|;sSPyvB[?-B6~/ZHaveyH%|%xGi[Vd*SPJ>9)MKDOsz#zNS4$v?qM'XVe6z\
Magenta
quelle