태그 보관물: code-challenge

code-challenge

이미지를 트윗으로 인코딩 (Extreme Image Compression Edition) [닫기] 허용해야합니다. 샘플

Stack Overflow에서 매우 성공적인 Twitter 이미지 인코딩 문제 를 기반으로합니다 .

이미지가 1000 단어의 가치가 있다면 114.97 바이트에 얼마나 많은 이미지를 넣을 수 있습니까?

인쇄 가능한 ASCII 텍스트 만 포함 된 표준 Twitter 주석으로 이미지를 압축하는 범용 방법을 제안 합니다 .

규칙 :

  1. 이미지를 찍고 인코딩 된 텍스트를 출력 할 수있는 프로그램을 작성해야합니다.
  2. 프로그램에 의해 작성된 텍스트는 최대 140 자 여야하며 코드 포인트가 32-126 범위에있는 문자 만 포함해야합니다.
  3. 인코딩 된 텍스트를 가져 와서 디코딩 된 버전의 사진을 출력 할 수있는 프로그램 (아마도 동일한 프로그램)을 작성해야합니다.
  4. 프로그램은 외부 라이브러리와 파일을 사용할 수 있지만 인터넷 연결이나 다른 컴퓨터에 연결하지 않아도됩니다.
  5. 디코딩 프로세스는 어떤 방식으로도 원본 이미지에 액세스하거나 원본 이미지를 포함 할 수 없습니다.
  6. 프로그램은 비트 맵, JPEG, GIF, TIFF, PNG 형식 중 하나 이상의 이미지를 허용해야합니다. 샘플 이미지의 일부 또는 전부가 올바른 형식이 아닌 경우 프로그램에서 압축하기 전에 직접 변환 할 수 있습니다.

심사 :

이것은 다소 주관적인 도전이므로 승자는 (결국) 나에게 판단됩니다. 나는 중요성을 감소시키는 아래에 열거 된 몇 가지 중요한 요소에 대해 판단 할 것이다.

  1. 샘플 이미지로 표시되지 않은 이미지를 포함하여 다양한 이미지를 압축하는 합리적인 작업 수행 기능
  2. 이미지에서 주요 요소의 외곽선을 유지하는 기능
  3. 이미지에서 주요 요소의 색상을 압축하는 기능
  4. 이미지에서 작은 세부 묘사의 윤곽과 색상을 유지하는 기능
  5. 압축 시간. 이미지가 얼마나 잘 압축되는지만큼 중요하지는 않지만 동일한 프로그램을 수행하는 느린 프로그램보다 빠른 프로그램이 더 좋습니다.

제출에는 압축 해제 후 생성 된 이미지와 생성 된 Twitter 주석이 포함되어야합니다. 가능하면 소스 코드에 대한 링크를 제공 할 수도 있습니다.

샘플 이미지 :

Hindenburg ,
산악 풍경 ,
모나리자 ,
2D 도형



답변

실제 압축을 추가하여 방법을 개선했습니다. 이제 다음을 반복적으로 수행하여 작동합니다.

  1. 이미지를 YUV로 변환
  2. 종횡비를 유지하면서 이미지 크기를 줄입니다 (이미지가 컬러 인 경우 크로마는 광도의 폭 및 높이의 1/3로 샘플링 됨)

  3. 샘플 당 비트 심도를 4 비트로 줄입니다.

  4. 중앙값 예측을 이미지에 적용하여 샘플 분포를 더 균일하게 만듭니다.

  5. 이미지에 적응 범위 압축을 적용합니다.

  6. 압축 이미지의 크기가 <= 112인지 확인하십시오.

그런 다음 112 바이트에 맞는 가장 큰 이미지가 최종 이미지로 사용되고 나머지 2 바이트는 압축 된 이미지의 너비와 높이를 저장하는 데 사용되며 이미지가 컬러인지 여부를 나타내는 플래그가 사용됩니다. 디코딩의 경우, 프로세스가 역전되고 이미지가 확대되어 더 작은 치수는 128입니다.

개선의 여지가 있습니다. 즉 사용 가능한 모든 바이트가 일반적으로 사용되는 것은 아니지만 다운 샘플링 + 무손실 압축에 대한 수익이 크게 감소하는 시점에 있다고 생각합니다.

빠르고 더러운 C ++ 소스

Windows exe

모나리자 (13×20 휘도, 4×6 크로마)

&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

힌덴부르크 (21×13 휘도)

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'

(19×14 휘도, 6×4 크로마)

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

2D 도형 (21×15 휘도, 7×5 크로마)

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!


답변

가다

이미지를 재귀 적으로 영역으로 나누어 작동합니다. 정보 내용이 많은 영역을 나누고 분할 선을 선택하여 두 영역 간의 색상 차이를 최대화하려고합니다.

각각의 분할은 분할 라인을 인코딩하기 위해 몇 비트를 사용하여 인코딩된다. 각 리프 영역은 단일 색상으로 인코딩됩니다.

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

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

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&

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

Hindenburg 사진은 꽤 엉망이지만, 다른 사람들은 내가 좋아합니다.

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()
    }
}

답변

파이썬

인코딩에는 numpy , SciPyscikit-image 가 필요합니다 .
디코딩에는 PIL 만 필요합니다 .

수퍼 픽셀 보간에 기반한 방법입니다. 시작하기 위해 각 이미지는 비슷한 색상의 70 개의 비슷한 크기 영역으로 나뉩니다 . 예를 들어, 가로 그림은 다음과 같이 나뉩니다.

각 영역의 중심은 402 개의 점을 포함하는 그리드에서 가장 가까운 래스터 점에 위치하며, 평균 색상 (216 색 팔레트에서)이며 이러한 각 영역은 0 부터 숫자로 인코딩됩니다. ~ 86832 , 2.5 인쇄 가능한 ASCII 문자 로 저장 가능 (실제로 2.497 , 그레이 스케일 비트를 인코딩하기에 충분한 공간 만 남음 ).

당신이 세심한 경우, 당신은 눈치 챘을 수 140 / 2.5 = 56 지역, 그리고 70 앞에서 언급 한 바와 같이. 그러나 이러한 각 영역은 고유하고 비교 가능한 개체이며 순서에 상관없이 나열 될 수 있습니다. 이 때문에 첫 번째 56 개 영역 의 순열 을 사용하여 다른 14 개를 인코딩 하고 가로 세로 비율을 저장하기 위해 약간의 비트를 남길 수 있습니다.

보다 구체적으로, 추가의 14 개의 영역 각각은 숫자로 변환 된 다음, 이들 숫자 각각이 함께 연결된다 (현재 값에 86832를 곱하고 다음 을 더함 ). 그런 다음이 거대한 숫자는 56 개의 개체 에 대한 순열로 변환됩니다 .

예를 들면 다음과 같습니다.

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)

출력합니다 :

[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

그런 다음 결과 순열은 원래 56 개의 영역에 적용됩니다 . 마찬가지로, 56 개의 인코딩 된 영역 의 순열 을 그것의 숫자 표현으로 변환 함으로써 원래의 숫자 (및 추가의 14 개의 영역)가 추출 될 수있다 .

--greyscale옵션을 인코더와 함께 사용 하면 558 개의 래스터 포인트와 16 개의 회색 음영이있는 94 개의 영역이 대신 사용됩니다 ( 70 , 24로 분리 ) .

디코딩 할 때, 이들 영역 각각은 위에서 본 바와 같이 영역의 중심에서 정점이있는 무한대로 확장 된 3D 콘 (일명 보로 노이 다이어그램)으로 취급됩니다. 그런 다음 테두리를 혼합하여 최종 제품을 만듭니다.

향후 개선

  1. 종횡비를 저장하는 방식으로 인해 모나리자의 치수가 약간 떨어졌습니다. 다른 시스템을 사용해야합니다. 원래 종횡비가 1:21과 21 : 1 사이에 있다고 가정하여 고정 가정이라고 생각합니다.
  2. Hindenburg는 많이 개선 될 수있었습니다. 내가 사용하는 색상 팔레트에는 6 가지 회색 음영 만 있습니다. 그레이 스케일 전용 모드를 도입 한 경우 추가 정보를 사용하여 색상 심도, 영역 수, 래스터 점 수 또는 세 가지의 조합을 증가시킬 수 있습니다. 인코더에 옵션을 추가했는데 --greyscale,이 세 가지를 모두 수행합니다.
  3. 블렌딩을 끄면 2D 모양이 더 좋아 보일 것입니다. 아마도 그 플래그를 추가 할 것입니다. 분할 비율을 제어하기위한 인코더 옵션과 블렌딩을 끄는 디코더 옵션을 추가했습니다.
  4. 조합으로 더 재미 있습니다. 56! 실제로 15 개의 추가 지역 을 저장할 수있을만큼 크고 15 개입니다! 73 개에 대해 2 개를 더 저장할 수있을만큼 큽니다 . 그러나 더 많은 것이 있습니다! 이 73 개의 객체를 분할하면 더 많은 정보를 저장할 수 있습니다. 예를 들어, 거기 (73)가 선택 (56) 은 초기 선택 방법 (56 개) 영역, 그리고 17 15 선택한 다음 선택하는 방법 (15) . 총 2403922132944423072 , 총 76 개의 영역을 3 개 더 저장할 수있을만큼 큰 총 분할. 73의 모든 파티션 을 56 , 15 , 2등의 그룹 으로 고유 번호를 매길 수있는 영리한 방법을 찾아야합니다 . 아마도 실용적이지는 않지만 생각해 볼 흥미로운 문제입니다.

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


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

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

두 번째는 --greyscale옵션으로 인코딩되었습니다 .


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

--greyscale옵션으로 인코딩되었습니다 .


.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

로 인코딩되고 옵션으로 --ratio 60디코딩됩니다 --no-blending.


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

답변

PHP

알았어, 시간이 좀 걸렸지 만 여기있어 그레이 스케일의 모든 이미지. 내 방법으로 인코딩하는 데 너무 많은 비트가 인코딩되었습니다 .P


모나리자
47 색 단색
101 바이트 문자열.

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


2D 도형
36 색 단색
105 바이트 문자열.

oAAAAAAABMIDUAAEBAyoAAAAAgAwAAAAADYBtsAAAJIDbYAAAAA22AGwAAAAAGwAAAAAAAAAAKgAAAAAqgAAAACoAAAAAAAAAAAAAAAAA


Hindenburg
62 색상 흑백
112 자.

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



63 색 단색
122 자.

qAE3VTkaIAKgqSFigAKoABgQEqAABuAgUQAGenRIBoUh2eqhABCee/2qSSAQntt/s2kJCQbf/bbaJgbWebzqsPZ7bZttwABTc3VAUFDbKqqpzY5uqpudnp5vZg


내 방법

비트 스트림을 base64 인코딩 유형으로 인코딩합니다. 읽을 수있는 텍스트로 인코딩하기 전에 다음과 같이됩니다.

소스 이미지를로드하고 20 픽셀의 최대 높이 또는 너비 (방향, 가로 / 세로에 따라)로 크기를 조정합니다.

다음으로 새 이미지의 각 픽셀을 6 색 그레이 스케일 팔레트에서 가장 가깝게 다시 채색합니다.

그 후에 문자 [AF]로 표시되는 각 픽셀 색상으로 문자열을 만듭니다.

그런 다음 문자열 내에서 6 개의 다른 문자의 분포를 계산하고 문자 빈도를 기준으로 인코딩을 위해 가장 최적화 된 이진 트리를 선택합니다. 15 개의 가능한 이진 트리가 있습니다.

[1|0]이미지가 크거나 넓은 지 여부에 따라 단일 비트로 비트 스트림을 시작 합니다. 그런 다음 스트림에서 다음 4 비트를 사용하여 이미지를 디코딩하는 데 어떤 이진 트리를 사용해야하는지 디코더에 알립니다.

다음은 이미지를 나타내는 비트 스트림입니다. 각 픽셀과 그 색상은 2 또는 3 비트로 표현됩니다. 이를 통해 인쇄 된 모든 ASCII 문자에 대해 최소 2 ~ 3 픽셀의 정보를 저장할 수 있습니다. 다음 1110은 Mona Lisa에서 사용하는 이진 트리 샘플입니다 .

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

문자 E 00와 F 10는 모나리자에서 가장 일반적인 색상입니다. A 010, B 011, C 110및 D 111가 가장 빈번하지 않습니다.

이진 트리는 다음과 같이 작동합니다. 비트 단위로 0이동하면 왼쪽으로 1이동하고 오른쪽으로 이동한다는 의미입니다. 나무의 잎이나 막 다른 길에 닿을 때까지 계속 가십시오. 당신이 끝내는 잎은 당신이 원하는 캐릭터입니다.

어쨌든 바이너리 스팅을 base64 문자로 인코딩합니다. 문자열을 디코딩 할 때 프로세스는 역으로 수행되어 모든 픽셀을 적절한 색상으로 할당 한 다음 이미지 크기를 인코딩 된 크기의 두 배 (X 또는 Y 중 최대 40 픽셀 중 더 큰 것)로 확대하고 컨벌루션 매트릭스는 색상을 부드럽게하기 위해 모든 것에 적용됩니다.

어쨌든, 현재 코드는 다음과 같습니다 : ” pastebin link

추악하지만 개선의 여지가 있다면 알려주십시오. 내가 원하는대로 해킹했다. 나는 이 도전으로부터 많은 것을 배웠다 . 게시 해 주셔서 감사합니다.


답변

나의 첫 번째 시도. 개선의 여지가 있습니다. 형식 자체가 실제로 작동한다고 생각합니다. 문제는 인코더에 있습니다. 즉, 출력에서 ​​개별 비트가 누락되었습니다 … 약간 품질이 높은 파일은 144 자로 끝났습니다. (그리고 나는 정말로 있었으면 좋겠다-이것들과 그것들의 차이점이 눈에 띄었다). 그래도 140 자의 문자가 얼마나 큰지 과대 평가하지는 않았습니다.

기본적으로 32 색 팔레트가 필요하기 때문에 RISC-OS 팔레트의 수정 된 버전으로 가져 왔습니다. 이것은 내가 생각하는 일부 변화와 관련이 있습니다.


이미지를 다음 모양으로
분류하고 이미지를 앞면과 뒷면의 팔레트 블록 (이 경우 2×2 픽셀)으로 분할합니다.

결과 :

다음은 트윗, 원본 및 트윗을 해독하는 방법입니다

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


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


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


%\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_


나는 색상이 잘못되었음을 알고 있지만 실제로는 모나리자를 좋아합니다. 블러를 제거하면 (너무 어렵지는 않을 것입니다), 합리적인 입체파 인상입니다 : p

나는 일해야한다

  • 모양 감지 추가
  • 더 나은 색상 “차이”알고리즘
  • 누락 된 비트가 어디로 갔는지 파악

나중에 문제를 해결하고 인코더를 개선하기 위해 더 많은 작업을하겠습니다. 20 개 정도의 캐릭터는 엄청난 차이를 만듭니다. 다시 돌려 드리고 싶습니다.

C # 소스 및 색상 팔레트는 https://dl.dropboxusercontent.com/u/46145976/Base96.zip있습니다 . 비록 후시에서는 프로그램에 대한 인수의 공백이 없어서 따로 실행하면 완벽하게 작동하지 않을 수 있습니다 잘).

상당히 평범한 기계에서 인코더는 몇 초도 걸리지 않습니다.


답변

나는 색상을 유지하려고 노력을 포기하고 흑백으로 갔다. 색상으로 시도한 모든 것이 인식되지 않기 때문이다.

기본적으로 픽셀, 검은 색, 회색 및 흰색의 대략 동일한 3 개 부분으로 픽셀을 나눕니다. 또한 크기를 유지하지 않습니다.

힌덴부르크

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

모나리자

=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

+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

모양

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:

프로그램은 다음과 같습니다. 트윗을 python compress.py -c img.png압축 img.png하고 인쇄합니다.

python compress.py -d img.pngstdin에서 트윗을 가져 와서 이미지를에 저장합니다 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')

답변

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()
    }

아이디어는 단순히 래스터 (파일은 png로 있어야 함)를 셀 수가 140보다 작은 행렬로 줄이는 것입니다. 트위트는 행 수를 나타내는 두 문자가 앞에 오는 일련의 색상 (64 색상)입니다. 래스터의 기둥.

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

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

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

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