Stack Overflow에서 매우 성공적인 Twitter 이미지 인코딩 문제 를 기반으로합니다 .
이미지가 1000 단어의 가치가 있다면 114.97 바이트에 얼마나 많은 이미지를 넣을 수 있습니까?
인쇄 가능한 ASCII 텍스트 만 포함 된 표준 Twitter 주석으로 이미지를 압축하는 범용 방법을 제안 합니다 .
규칙 :
- 이미지를 찍고 인코딩 된 텍스트를 출력 할 수있는 프로그램을 작성해야합니다.
- 프로그램에 의해 작성된 텍스트는 최대 140 자 여야하며 코드 포인트가 32-126 범위에있는 문자 만 포함해야합니다.
- 인코딩 된 텍스트를 가져 와서 디코딩 된 버전의 사진을 출력 할 수있는 프로그램 (아마도 동일한 프로그램)을 작성해야합니다.
- 프로그램은 외부 라이브러리와 파일을 사용할 수 있지만 인터넷 연결이나 다른 컴퓨터에 연결하지 않아도됩니다.
- 디코딩 프로세스는 어떤 방식으로도 원본 이미지에 액세스하거나 원본 이미지를 포함 할 수 없습니다.
- 프로그램은 비트 맵, JPEG, GIF, TIFF, PNG 형식 중 하나 이상의 이미지를 허용해야합니다. 샘플 이미지의 일부 또는 전부가 올바른 형식이 아닌 경우 프로그램에서 압축하기 전에 직접 변환 할 수 있습니다.
심사 :
이것은 다소 주관적인 도전이므로 승자는 (결국) 나에게 판단됩니다. 나는 중요성을 감소시키는 아래에 열거 된 몇 가지 중요한 요소에 대해 판단 할 것이다.
- 샘플 이미지로 표시되지 않은 이미지를 포함하여 다양한 이미지를 압축하는 합리적인 작업 수행 기능
- 이미지에서 주요 요소의 외곽선을 유지하는 기능
- 이미지에서 주요 요소의 색상을 압축하는 기능
- 이미지에서 작은 세부 묘사의 윤곽과 색상을 유지하는 기능
- 압축 시간. 이미지가 얼마나 잘 압축되는지만큼 중요하지는 않지만 동일한 프로그램을 수행하는 느린 프로그램보다 빠른 프로그램이 더 좋습니다.
제출에는 압축 해제 후 생성 된 이미지와 생성 된 Twitter 주석이 포함되어야합니다. 가능하면 소스 코드에 대한 링크를 제공 할 수도 있습니다.
샘플 이미지 :
Hindenburg ,
산악 풍경 ,
모나리자 ,
2D 도형
답변
실제 압축을 추가하여 방법을 개선했습니다. 이제 다음을 반복적으로 수행하여 작동합니다.
- 이미지를 YUV로 변환
-
종횡비를 유지하면서 이미지 크기를 줄입니다 (이미지가 컬러 인 경우 크로마는 광도의 폭 및 높이의 1/3로 샘플링 됨)
-
샘플 당 비트 심도를 4 비트로 줄입니다.
-
중앙값 예측을 이미지에 적용하여 샘플 분포를 더 균일하게 만듭니다.
-
이미지에 적응 범위 압축을 적용합니다.
-
압축 이미지의 크기가 <= 112인지 확인하십시오.
그런 다음 112 바이트에 맞는 가장 큰 이미지가 최종 이미지로 사용되고 나머지 2 바이트는 압축 된 이미지의 너비와 높이를 저장하는 데 사용되며 이미지가 컬러인지 여부를 나타내는 플래그가 사용됩니다. 디코딩의 경우, 프로세스가 역전되고 이미지가 확대되어 더 작은 치수는 128입니다.
개선의 여지가 있습니다. 즉 사용 가능한 모든 바이트가 일반적으로 사용되는 것은 아니지만 다운 샘플링 + 무손실 압축에 대한 수익이 크게 감소하는 시점에 있다고 생각합니다.
모나리자 (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 , SciPy 및 scikit-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:21과 21 : 1 사이에 있다고 가정하여 고정 가정이라고 생각합니다.Hindenburg는 많이 개선 될 수있었습니다. 내가 사용하는 색상 팔레트에는 6 가지 회색 음영 만 있습니다. 그레이 스케일 전용 모드를 도입 한 경우 추가 정보를 사용하여 색상 심도, 영역 수, 래스터 점 수 또는 세 가지의 조합을 증가시킬 수 있습니다.인코더에 옵션을 추가했는데--greyscale
,이 세 가지를 모두 수행합니다.블렌딩을 끄면 2D 모양이 더 좋아 보일 것입니다. 아마도 그 플래그를 추가 할 것입니다.분할 비율을 제어하기위한 인코더 옵션과 블렌딩을 끄는 디코더 옵션을 추가했습니다.- 조합으로 더 재미 있습니다. 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.png
stdin에서 트윗을 가져 와서 이미지를에 저장합니다 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"