Kodowanie zdjęć w tweety (edycja Extreme Image Compression) [zamknięte]

59

Na podstawie bardzo udanego wyzwania kodowania obrazów na Twitterze w Stack Overflow.

Jeśli obraz jest wart 1000 słów, ile obrazu można zmieścić w 114,97 bajtach?

Rzucam ci wyzwanie, abyś zaproponował metodę ogólnego zastosowania do kompresji obrazów w standardowy komentarz na Twitterze, który zawiera tylko tekst ASCII do wydrukowania .

Zasady:

  1. Musisz napisać program, który może zrobić zdjęcie i wyprowadzić zakodowany tekst.
  2. Tekst utworzony przez program musi mieć maksymalnie 140 znaków i może zawierać tylko znaki, których punkty kodowe mieszczą się w zakresie od 32 do 126 włącznie.
  3. Musisz napisać program (prawdopodobnie ten sam program), który może pobrać zakodowany tekst i wydrukować zdekodowaną wersję zdjęcia.
  4. Twój program może korzystać z zewnętrznych bibliotek i plików, ale nie może wymagać połączenia z Internetem ani połączenia z innymi komputerami.
  5. Proces dekodowania nie może w żaden sposób uzyskać dostępu ani zawierać oryginalnych obrazów.
  6. Twój program musi akceptować obrazy w co najmniej jednym z tych formatów (niekoniecznie więcej): Bitmapa, JPEG, GIF, TIFF, PNG. Jeśli niektóre lub wszystkie przykładowe obrazy nie mają prawidłowego formatu, możesz je przekonwertować przed kompresją w programie.

Oceniając:

Jest to dość subiektywne wyzwanie, więc zwycięzca zostanie (ostatecznie) oceniony przeze mnie. Skoncentruję swoją ocenę na kilku ważnych czynnikach, wymienionych poniżej w malejącym znaczeniu:

  1. Zdolność do wykonania rozsądnej pracy polegającej na kompresji szerokiej gamy obrazów, w tym obrazów niewymienionych jako przykładowe
  2. Zdolność do zachowania konturów głównych elementów obrazu
  3. Możliwość kompresji kolorów głównych elementów obrazu
  4. Możliwość zachowania konturów i kolorów drobnych szczegółów na obrazie
  5. Czas kompresji. Chociaż nie tak ważne, jak dobrze obraz jest skompresowany, szybsze programy są lepsze niż wolniejsze programy, które robią to samo.

Twoje zgłoszenie powinno zawierać powstałe obrazy po dekompresji, wraz z wygenerowanym komentarzem na Twitterze. Jeśli to możliwe, możesz również podać link do kodu źródłowego.

Przykładowe obrazy:

Hindenburg , górzysty krajobraz , Mona Lisa , kształty 2D

PhiNotPi
źródło
U + 007F (127) i U + 0080 (128) są znakami kontrolnymi. Sugerowałbym również ich zakazanie.
PleaseStand
Dobra obserwacja. Naprawię to.
PhiNotPi
Czy Twitter nie dopuszcza do pewnego stopnia Unicode?
marinus
4
Czuję, że chciałbym opatentować rozwiązanie tego problemu.
Shmiddty
2
„Górzyste krajobrazy” 1024x768 - Zdobądź zanim zniknie! -> i.imgur.com/VaCzpRL.jpg <-
jdstankosky

Odpowiedzi:

58

Udoskonaliłem moją metodę, dodając rzeczywistą kompresję. Teraz działa iteracyjnie, wykonując następujące czynności:

  1. Konwertuj obraz na YUV
  2. Zmniejsz rozmiar obrazu zachowując proporcje (jeśli obraz jest kolorowy, próbkowanie barwy odbywa się w 1/3 szerokości i wysokości luminancji)

  3. Zmniejsz głębokość bitów do 4 bitów na próbkę

  4. Zastosuj prognozę mediany do obrazu, dzięki czemu rozkład próbki będzie bardziej jednolity

  5. Zastosuj kompresję zakresu adaptacyjnego do obrazu.

  6. Sprawdź, czy rozmiar skompresowanego obrazu wynosi <= 112

Największy obraz, który mieści się w 112 bajtach, jest następnie używany jako obraz końcowy, a pozostałe dwa bajty służą do przechowywania szerokości i wysokości skompresowanego obrazu, plus flaga wskazująca, czy obraz jest kolorowy. W przypadku dekodowania proces jest odwracany, a obraz skalowany w górę, aby mniejszy wymiar wynosił 128.

Jest trochę miejsca na ulepszenia, mianowicie nie wszystkie dostępne bajty są zwykle używane, ale wydaje mi się, że jestem na etapie znacznie zmniejszających się zwrotów za próbkowanie w dół + kompresję bezstratną.

Szybkie i brudne źródło C ++

Exe systemu Windows

Mona Lisa (luminancja 13x20, barwa 4x6)

&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 zakodowana na Twitterze

Hindenburg (luminancja 21x13)

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 Twitter zakodowany w Hindenburgu

Góry (luminancja 19x14, barwa 6x4)

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           

Góra Mountain twitter zakodowane

Kształty 2D (luminancja 21x15, barwa 7x5)

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!    

Kształty 2D Twitter zakodowane w 2D Shapes

Sir_Lagsalot
źródło
7
To sprawia, że ​​mam wrażenie, że rozwijam zaćmę lub coś takiego. Haha, świetna robota!
jdstankosky
Niezłe ulepszenia!
jdstankosky
37

Iść

Działa poprzez rekurencyjne dzielenie obrazu na regiony. Staram się dzielić regiony z dużą zawartością informacji i wybieram linię podziału, aby zmaksymalizować różnicę kolorów między dwoma regionami.

Każdy podział jest kodowany za pomocą kilku bitów do kodowania linii podziału. Każdy region liścia jest kodowany jako jeden kolor.

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

<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>

wprowadź opis zdjęcia tutaj

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&

wprowadź opis zdjęcia tutaj

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.,(

Zdjęcie Hindenburga wygląda dość kiepsko, ale inne lubię.

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
źródło
3
Koleś, wyglądają świetnie.
MrZander
2
O Boże, to jest niesamowite.
jdstankosky
4
Zaraz, gdzie są twoje sznurki?
jdstankosky
1
To jak dotąd mój ulubiony.
primo
4
+1 za wygląd kubisty .
Ilmari Karonen,
36

Pyton

Kodowanie wymaga numpy , SciPy i scikit-image .
Dekodowanie wymaga tylko PIL .

Jest to metoda oparta na interpolacji superpikseli. Na początek każdy obraz jest podzielony na 70 podobnej wielkości regionów o podobnym kolorze. Na przykład obraz krajobrazu jest podzielony w następujący sposób:

wprowadź opis zdjęcia tutaj

Środek ciężkości każdego regionu znajduje się (do najbliższego punktu rastrowego na siatce zawierającej nie więcej niż 402 punkty), a także jego średni kolor (z palety 216 kolorów), a każdy z tych regionów jest zakodowany jako liczba od 0 do 86832 , który można zapisać w postaci 2,5 znaków ascii do wydrukowania (w rzeczywistości 2,497 , pozostawiając wystarczająco dużo miejsca do zakodowania dla bitu w skali szarości).

Jeśli jesteś uważny, być może zauważyłeś, że 140 / 2,5 = 56 regionów, a nie 70, jak powiedziałem wcześniej. Zauważ jednak, że każdy z tych regionów jest unikalnym, porównywalnym obiektem, który może być wymieniony w dowolnej kolejności. Z tego powodu możemy użyć permutacji pierwszych 56 regionów, aby zakodować pozostałe 14 , a także mieć kilka bitów pozostałych do przechowywania współczynnika kształtu.

Mówiąc dokładniej, każdy z dodatkowych 14 regionów jest przekształcany na liczbę, a następnie każda z tych liczb jest łączona razem (mnożąc bieżącą wartość przez 86832 i dodając następny). Ta (gigantyczna) liczba jest następnie przekształcana w permutację na 56 obiektach.

Na przykład:

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)

wyświetli:

[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

Otrzymana permutacja jest następnie stosowana do oryginalnych 56 regionów. Pierwotny numer (a zatem dodatkowe 14 regionów) można również wyodrębnić, przekształcając permutację 56 zakodowanych regionów w jego reprezentację liczbową.

Gdy --greyscaleopcja jest używana z koderem, zamiast tego używane są 94 regiony (oddzielone 70 , 24 ), z 558 punktami rastrowymi i 16 odcieniami szarości.

Podczas dekodowania każdy z tych obszarów jest traktowany jako stożek 3D rozciągnięty do nieskończoności, którego wierzchołek znajduje się w środku ciężkości regionu, patrząc od góry (aka diagram Voronoi). Obramowania są następnie mieszane, aby utworzyć produkt końcowy.

Przyszłe ulepszenia

  1. Wymiary Mona Lisa są nieco inne, ze względu na sposób przechowywania proporcji. Będę musiał użyć innego systemu. Naprawiono, zakładając, że oryginalny współczynnik kształtu mieści się w przedziale od 1:21 do 21: 1, co uważam za rozsądne założenie.
  2. Hindenburg można znacznie poprawić. Paleta kolorów, której używam, ma tylko 6 odcieni szarości. Gdybym wprowadził tryb tylko w skali szarości, mógłbym użyć dodatkowych informacji, aby zwiększyć głębię kolorów, liczbę regionów, liczbę punktów rastrowych lub dowolną kombinację tych trzech. Dodałem --greyscaleopcję do enkodera, która wykonuje wszystkie trzy.
  3. Kształty 2d prawdopodobnie wyglądałyby lepiej przy wyłączonym mieszaniu. Prawdopodobnie dodam do tego flagę. Dodano opcję enkodera do kontroli współczynnika segmentacji oraz opcję dekodera, aby wyłączyć mieszanie.
  4. Więcej zabawy z kombinatoryką. 56! jest wystarczająco duży, aby pomieścić 15 dodatkowych regionów i 15! jest wystarczająco duży, aby pomieścić jeszcze 2, co daje łącznie 73 . Ale czekaj, jest więcej! Partycjonowanie tych 73 obiektów można również wykorzystać do przechowywania większej ilości informacji. Na przykład istnieje 73 do wyboru 56 sposobów, aby wybrać początkowe 56 regionów, a następnie 17 wybrać 15 sposobów, aby wybrać kolejne 15 . Ogółem 2403922132944423072 partycji, wystarczająco dużych, aby pomieścić 3 kolejne regiony w sumie 76. Musiałbym wymyślić sprytny sposób, aby jednoznacznie numerować wszystkie partycje 73 na grupy po 56 , 15 , 2 ... iz powrotem . Być może niepraktyczne, ale ciekawy problem do przemyślenia.

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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj


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

i

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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Drugi kodowany z --greyscaleopcją.


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(:%

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Zakodowane z --greyscaleopcją.


.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

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Kodowane --ratio 60i dekodowane z --no-blendingopcjami.


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
źródło
1
To nic niezwykłego
Lochok
Kolorowa wersja Mona Lisa wygląda, jakby pękło jedno z jej piersi. Jest to niesamowite.
jdstankosky
4
Używanie permutacji do kodowania dodatkowych danych jest dość sprytne.
Sir_Lagsalot
Naprawdę niesamowite. Czy potrafisz zrobić sens z tymi 3 plikami? gist.github.com
rubik
2
@rubik jest niesamowicie stratny, podobnie jak wszystkie rozwiązania tego wyzwania;)
primo
17

PHP

OK, zajęło mi to trochę czasu, ale oto jest. Wszystkie obrazy w skali szarości. Kolory zajęły zbyt wiele bitów do zakodowania dla mojej metody: P


Ciąg Mona Lisa
47 kolorów Monochrome
101 bajtów.

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

Mona Lisa


Kształty 2D
36 kolorów Monochromatyczny Ciąg
105 bajtów.

oAAAAAAABMIDUAAEBAyoAAAAAgAwAAAAADYBtsAAAJIDbYAAAAA22AGwAAAAAGwAAAAAAAAAAKgAAAAAqgAAAACoAAAAAAAAAAAAAAAAA

2d 2dc


Hindenburg
62 kolory Monochromatyczny
112 znaków.

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

zdjęcia tutaj wprowadź opis zdjęcia tutaj


Góry
63 kolory Monochromatyczne
122 znaki.

qAE3VTkaIAKgqSFigAKoABgQEqAABuAgUQAGenRIBoUh2eqhABCee/2qSSAQntt/s2kJCQbf/bbaJgbWebzqsPZ7bZttwABTc3VAUFDbKqqpzY5uqpudnp5vZg

picshere wprowadź opis zdjęcia tutaj


Moja metoda

Koduję mój strumień bitów przy użyciu rodzaju kodowania base64. Zanim zostanie zakodowany w czytelnym tekście, oto co się stanie.

Ładuję obraz źródłowy i zmieniam jego rozmiar do maksymalnej wysokości lub szerokości (w zależności od orientacji, pionowej / poziomej) wynoszącej 20 pikseli.

Następnie ponownie koloruję każdy piksel nowego obrazu do jego najbliższego dopasowania na palecie 6 kolorów w skali szarości.

Po tym utworzę ciąg z każdym kolorem piksela reprezentowanym przez litery [AF].

Następnie obliczam rozkład 6 różnych liter w ciągu i wybieram najbardziej zoptymalizowane drzewo binarne do kodowania na podstawie częstotliwości liter. Istnieje 15 możliwych drzew binarnych.

Strumień bitów zaczynam od jednego bitu, w [1|0]zależności od tego, czy obraz jest wysoki czy szeroki. Następnie używam 4 kolejnych bitów w strumieniu, aby poinformować dekoder, którego drzewa binarnego należy użyć do zdekodowania obrazu.

Poniżej znajduje się strumień bitów reprezentujących obraz. Każdy piksel i jego kolor są reprezentowane przez 2 lub 3 bity. To pozwala mi przechowywać informacje o wartości od 2 do 3 pikseli dla każdej drukowanej postaci ascii. Oto próbka drzewa binarnego 1110, z którego korzysta Mona Lisa:

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

Litery E 00i F 10są najczęstszymi kolorami w Mona Lisa. A 010, B 011, C 110i D 111są najmniej częste.

Drzewa binarne działają w następujący sposób: przechodzenie z jednego kawałka na drugi 0oznacza przejście w lewo, 1oznacza przejście w prawo. Idź dalej, dopóki nie trafisz w liść na drzewo lub ślepy zaułek. Liść, na którym kończysz, to postać, którą chcesz.

W każdym razie koduję binarne żądło na znaki base64. Podczas dekodowania łańcucha proces odbywa się w odwrotnej kolejności, przypisując wszystkie piksele do odpowiedniego koloru, a następnie obraz jest skalowany dwukrotnie w stosunku do zakodowanego rozmiaru (maksymalnie 40 pikseli X lub Y, w zależności od tego, który jest większy), a następnie matryca splotowa jest zastosowane do całości, aby wygładzić kolory.

Tak czy inaczej, oto obecny kod: „ link do pastebin

To brzydkie, ale jeśli widzisz miejsce na ulepszenia, daj mi znać. Zhakowałem go razem, jak chcę. Dowiedziałem WIELE Z tym wyzwaniem. Dziękujemy OP za opublikowanie go!

jdstankosky
źródło
2
Wyglądają niesamowicie dobrze, biorąc pod uwagę, ile masz niewykorzystanego miejsca do przechowywania (Mona Lisa używa tylko 606 bitów z 920 dostępnych!).
primo,
Dziękuję, primo, naprawdę to doceniam. Zawsze podziwiam twoją pracę, więc słyszę, jak mówisz, że to bardzo pochlebia!
jdstankosky
13

Moja pierwsza próba. To daje pole do poprawy. Myślę, że sam format faktycznie działa, problem tkwi w koderze. I brakuje mi pojedynczych bitów z mojego wyjścia ... mój (nieco wyższej jakości niż tutaj) plik skończył się na 144 znakach, kiedy powinno być trochę. (i naprawdę żałuję, że nie było - zauważalne są różnice między nimi a tymi). Nauczyłem się jednak, nigdy nie przeceniaj, jak duże jest 140 znaków ...

Sprowadzam to do zmodyfikowanej wersji palety RISC-OS - w zasadzie, ponieważ potrzebowałem palety 32 kolorów, i wydawało się, że to wystarczająco dobre miejsce do rozpoczęcia. Myślę, że przydałoby się to też trochę zmienić. Paleta

Rozbijam go na następujące kształty: Kształty i dzielę obraz na bloki palety (w tym przypadku 2x2 piksele) koloru przedniego i tylnego.

Wyniki:

Poniżej znajdują się tweety, oryginały i sposób ich dekodowania

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

Hindeberg Mój 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

Góra Moja góra

)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]?

Kształty Moje kształty

%\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 Kopalnia Mona Lisa

Wiem, że kolory są niewłaściwe, ale tak naprawdę podoba mi się Monalisa. Jeśli usunę rozmycie (co nie byłoby zbyt trudne), jest to rozsądne kubistyczne wrażenie: str

Muszę popracować

  • Dodawanie wykrywania kształtu
  • Lepszy algorytm „różnicy” kolorów
  • Odkrywanie, gdzie poszły moje brakujące części

Dam później trochę pracy, aby spróbować je naprawić i ulepszyłem koder. Te dodatkowe 20 lub więcej postaci stanowią ogromną różnicę. Chciałbym je z powrotem.

Źródło i paleta kolorów C # znajdują się na https://dl.dropboxusercontent.com/u/46145976/Base96.zip - chociaż z perspektywy czasu może nie działać idealnie, gdy są uruchamiane osobno (ponieważ spacje w argumentach programów nie idą tak dobrze).

Enkoder zajmuje mniej niż kilka sekund na mojej dość przeciętnej maszynie.

Lochok
źródło
11
Koleś. Wyglądają lepiej niż jakakolwiek sztuka współczesna, którą widziałem w galerii ... Powinieneś zrobić z nich ogromne odbitki i je sprzedać!
jdstankosky
1
Wygląda na to, że muszę wyjąć kasetę z mojego Atari i podłączyć ją z powrotem. Podoba mi się.
metro
13

Zrezygnowałem z prób utrzymania koloru i zrobiłem się czarno-biały, ponieważ wszystko, czego próbowałem z kolorem, było nierozpoznawalne.

Zasadniczo dzieli tylko piksele na 3 w przybliżeniu równe części: czarny, szary i biały. Nie zachowuje również rozmiaru.

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 HindenburgCompressed

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

MonaLisa MonaLisaCompressed

Góry

+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

Góry MountainsCompressed

Kształty

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:

Kształty ShapesCompressed

Oto program. python compress.py -c img.pngkompresuje img.pngi drukuje tweet.

python compress.py -d img.pngpobiera tweet ze standardowego wejścia i zapisuje obraz w folderze 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')
pudełko kartonowe
źródło
Lol, +1 dla nieograniczonych współczynników kształtu.
jdstankosky
7

Mój skromny wkład w 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()
    }

Pomysł polega po prostu na zmniejszeniu rastra (plik musi być w png) do macierzy, której liczba komórek jest mniejsza niż 140, tweety to seria kolorów (w 64 kolorach) poprzedzona dwoma znakami wskazującymi liczbę wierszy i kolumny rastra.

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

plannapus
źródło
4

Nie jest to kompletne rozwiązanie, wystarczy wprowadzić tę metodę. (Matlab)

Użyłem 16 palety kolorów i 40 pozycji, aby stworzyć ważony diagram voronoi . Zastosowano algorytm genetyczny i prosty algorytm wspinaczki, aby dopasować obraz.

Album z oryginalnym obrazem, a także mam 16-bajtową wersję z 4 kolorami i ustalonymi pozycjami. :)

wprowadź opis zdjęcia tutaj

(Czy mogę tutaj zmienić rozmiar obrazu?)

randomra
źródło
1
Czy możesz opublikować pozostałe zdjęcia? Chcę zobaczyć, jak wyglądają dzięki tej kompresji!
jdstankosky
@jdstankosky Przepraszamy, nie mogę tego teraz zrobić. Może jakiś czas później ...
randomra 17.04.13
4

DO#

Aktualizacja - wersja 2


Podjąłem kolejną próbę, teraz używając MagickImage.NET ( https://magick.codeplex.com/ ) do kodowania danych JPEG, napisałem również podstawowy kod do lepszego przetwarzania danych nagłówka JPEG (jak sugerował primo), ja również użyłem GuassianBlur na wyjściu, co pomaga złagodzić część kompresji JPEG. Ponieważ nowa wersja działa lepiej, zaktualizowałem swój post, aby odzwierciedlić nową metodę.


metoda


Próbowałem czegoś wyjątkowego (mam nadzieję), zamiast próbować manipulować głębią kolorów lub identyfikacją krawędzi, lub próbować samodzielnie użyć innych sposobów zmniejszenia rozmiaru obrazu. Użyłem algorytmu JPEG przy maksymalnej kompresji w zmniejszonych wersjach zdjęcia, a następnie eliminując wszystko oprócz „StartOfScan” ( http://en.wikipedia.org/wiki/JPEG#Syntax_and_structure ) i kilku kluczowych elementów nagłówka, jestem w stanie sprowadzić rozmiar do dopuszczalnej wielkości. Wyniki są naprawdę imponujące dla 140 znaków, daje mi nowy szacunek dla plików JPEG:

Hindenburg

Hindenburg Oryginał

,$`"(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-- 

Góry

Góry Oryginał

,$  (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 Oryginał

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 %%%% !

Kształty

Kształty Oryginał

(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 % '!


Kod


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

Naprawdę zaczynam tęsknić za ReSharper +. Mam wiele rzeczy do poprawienia, wciąż mam tu sporo twardego kodowania, choć interesuje mnie bałagan (pamiętaj, że potrzebujesz dll MagickImage, aby uruchomić to w VS)


Oryginał (przestarzałe) - http://pastebin.com/BDPT0BKT

Nadal trochę bałaganu.

David Rogers
źródło
„Teraz jest naprawdę bałagan”. Zgadzam się z tym - na pewno musi być lepszy sposób na wygenerowanie tego nagłówka? Ale przypuszczam, że najważniejsze są wyniki. +1
primo
1

Python 3

metoda

To, co program najpierw robi, to zmniejszenie obrazu, znacznie zmniejszając jego rozmiar.

Po drugie, konwertuje wartości rgb na binarne i odcina ostatnie kilka cyfr.

Następnie konwertuje dane bazy 2 na bazę 10, gdzie dodaje wymiary obrazu.

Następnie konwertuje dane z bazy 10 na bazę 95, używając wszystkich ascii, jakie udało mi się znaleźć. Nie mogłem jednak użyć / x01 i tym podobnych z powodu jego zdolności do zanegowania funkcji, która zapisała plik tekstowy.

I (dla dodatkowej niejednoznaczności) funkcja dekodowania robi to w odwrotnej kolejności.

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')

Krzyk

Krzyk 1 Krzyk 2

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)

Kule

Kulki 1 Kule 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
źródło