[twitter] 트위터 이미지 인코딩 챌린지 [닫기]

그림의 단어가 1000 단어 인 경우 140 자에 얼마나 많은 그림을 넣을 수 있습니까?

참고 : 그것은 사람들입니다! 바운티 마감일이 다가 왔고, 약간의 심의를 거쳐 Boojum의 입국이 Sam Hocevar의 출전 을 거의 끝내지 못했다고 결정했습니다 . 글을 쓸 기회가 생기면 더 자세한 메모를 게시 할 것입니다. 물론 모든 사람은 계속해서 솔루션을 제출하고 사람들이 투표 할 수있는 솔루션을 개선해야합니다. 제출하고 참가한 모든 사람에게 감사합니다. 나는 그들 모두를 즐겼다. 이것은 내가 달리는 데 많은 재미가 있었고, 참가자와 관중 모두에게 재미 있기를 바랍니다.

나는 우연히 이 흥미로운 게시물 트위터 코멘트로 압축 이미지에 노력에 대해, 그 스레드 (그리고 사람들의 많은 레딧에 스레드는 ) 당신이 그것을 할 수있는 다른 방법에 대한 제안을했다. 그래서 나는 그것이 좋은 코딩 도전을 만들 것이라고 생각합니다. 사람들이 입에 돈을 넣을 수있게하고, 인코딩에 대한 그들의 아이디어가 당신이 이용할 수있는 제한된 공간에서 어떻게 더 자세하게 이끌어 낼 수 있는지 보여줍니다.

140 개의 문자 Twitter 메시지로 이미지를 인코딩하고 다시 이미지로 디코딩하는 범용 시스템을 제안합니다. 유니 코드 문자를 사용할 수 있으므로 문자 당 8 비트 이상을 얻을 수 있습니다. 그러나 유니 코드 문자를 허용하더라도 이미지를 아주 작은 공간으로 압축해야합니다. 이것은 확실히 압축 손실이 될 것이므로 각 결과가 얼마나 잘 보이는지에 대한 주관적인 판단이 필요합니다.

다음은 원작자 인 Quasimondo 가 자신의 인코딩에서 얻은 결과입니다 (이미지는 Creative Commons Attribution-Noncommercial 라이센스에 따라 라이센스가 부여됨 ).
모나리자

더 잘할 수 있습니까?

규칙

  1. 프로그램에는 인코딩디코딩의 두 가지 모드가 있어야합니다 .
  2. 인코딩 할 때 :
    1. 프로그램은 선택한 합리적인 래스터 그래픽 형식의 그래픽을 입력으로 가져와야 합니다. ImageMagick이 지원하는 모든 래스터 형식 은 합리적이라고 간주합니다.
    2. 프로그램은 140 개 이하의 유니 코드 코드 포인트로 표시 될 수있는 메시지를 출력해야합니다. 범위 (140) 코드 포인트 U+0000U+10FFFF(비 문자를 제외한 U+FFFE, U+FFFF, U+NFFFE , U+NFFFF 여기서 N110진수 및 범위 U+FDD0U+FDEF ) 및 대리 코드 포인트 ( U+D800U+DFFF). 선택한 적절한 인코딩으로 출력 될 수 있습니다. GNU에서iconv 지원하는 모든 인코딩 은 합리적이며 플랫폼 기본 인코딩 또는 로캘 인코딩이 적합 할 것입니다. 자세한 내용 아래의 유니 코드 노트 를 참조하십시오.
  3. 디코딩 할 때 :
    1. 프로그램은 인코딩 모드 의 출력을 입력으로 가져와야 합니다.
    2. 출력 벡터 형식도 정상이지만 프로그램은 위에서 정의한대로 적절한 형식으로 이미지를 출력해야합니다.
    3. 이미지 출력은 입력 이미지의 근사값이어야합니다. 입력 이미지에 가까울수록 좋습니다.
    4. 디코딩 프로세스는 상기 지정된 출력 이외의 다른 인코딩 프로세스의 다른 출력에 액세스 할 수 없으며; 즉, 이미지를 어딘가에 업로드하고 디코딩 프로세스에서 다운로드 할 URL 또는 이와 유사한 것을 출력 할 수 없습니다.
  4. 사용자 인터페이스의 일관성을 유지하려면 프로그램이 다음과 같이 작동해야합니다.

    1. 프로그램은 적절한 인터프리터가있는 플랫폼에서 실행 파일로 설정 될 수있는 스크립트이거나 실행 파일로 컴파일 될 수있는 프로그램이어야합니다.
    2. 프로그램은 첫 번째 인수로 encode또는 decode모드를 설정해야합니다.
    3. 프로그램은 다음 방법 중 하나 이상을 입력해야합니다 (파일 이름을 사용하는 방법을 구현하는 경우 파일 이름이 누락 된 경우 stdin 및 stdout에서 읽고 쓸 수도 있음).

      1. 표준 입력에서 입력을 가져 와서 표준 출력에서 ​​출력을 생성합니다.

        my-program encode <input.png >output.txt
        my-program decode <output.txt >output.png
        
      2. 두 번째 인수로 명명 된 파일에서 입력을 받고 세 번째로 명명 된 파일에서 출력을 생성하십시오.

        my-program encode input.png output.txt
        my-program decode output.txt output.png
        
  5. 솔루션을 위해 다음을 게시하십시오.
    1. 전체 코드 및 / 또는 다른 곳에서 호스팅 된 링크 (매우 길거나 컴파일하는 데 많은 파일이 필요한 경우 등)
    2. 코드에서 즉시 명확하지 않거나 코드가 길고 사람들이 요약에 관심이있는 경우 작동 방식에 대한 설명.
    3. 원본 이미지와 함께 압축되는 텍스트 및 디코딩 된 이미지의 예제 이미지입니다.
    4. 다른 사람이 가지고있는 아이디어를 기반으로하는 경우 해당 속성을 지정하십시오. 다른 사람의 아이디어를 구체화하려고해도 괜찮지 만, 그 특성을 귀속 해야 합니다.

지침

기본적으로 위반 될 수있는 규칙, 제안 또는 점수 기준입니다.

  1. 미학이 중요합니다. 나는 다음을 근거로 판단하고 다른 사람들이 판단 할 것을 제안 할 것이다.
    1. 출력 이미지의 모양 및 원본의 모양
    2. 텍스트가 멋지다. 당신이 정말로 영리한 압축 체계를 가지고 있다면 완전히 임의의 gobbledigook는 괜찮습니다. 원래 솔루션의 작성자는 한자 만 사용하기로 결정했습니다.
    3. 재미있는 코드와 영리한 알고리즘이 항상 좋습니다. 나는 짧고 요점을 밝히고 명확한 코드를 좋아하지만 좋은 결과를 낳는 한 정말 영리한 복잡한 알고리즘도 괜찮습니다.
  2. 작업이 이미지를 잘 압축하는 것만 큼 중요하지는 않지만 속도도 중요합니다. 차라리 며칠 동안 유전자 알고리즘을 실행하는 것보다 10 분의 1 초 안에 이미지를 변환 할 수있는 프로그램이 있습니다.
  3. 품질이 합리적으로 비교되는 한 더 긴 솔루션보다 더 짧은 솔루션을 선호합니다. 간결함은 미덕입니다.
  4. 프로그램은 Mac OS X, Linux 또는 Windows에서 무료로 구현 가능한 언어로 구현해야합니다. 프로그램을 실행할 수 있기를 원하지만 MATLAB 또는 다른 제품 에서만 실행되는 훌륭한 솔루션이 있다면 괜찮습니다.
  5. 프로그램은 가능한 한 일반적이어야합니다. 일부 이미지는 다른 이미지보다 더 나은 결과를 얻을 수 있지만 가능한 한 많은 이미지에서 작동해야합니다. 특히:
    1. 프로그램에 내장되고 참조를 작성하고 디코딩 할 때 일치하는 이미지를 생성하는 몇 개의 이미지가 프로그램에 내장되어있는 것은 상당히 불충분하며 일부 이미지 만 포함합니다.
    2. 단순하고 평평한 기하학적 모양의 이미지를 가져 와서 벡터 프리미티브로 분해 할 수있는 프로그램은 꽤 근사하지만, 특정 복잡성을 넘어서 이미지에 실패하면 불충분하게 일반적 일 것입니다.
    3. 특정 고정 종횡비의 이미지 만 찍을 수 있지만 잘 작동하는 프로그램도 괜찮지 만 이상적이지는 않습니다.
    4. 흑백 이미지는 컬러 이미지보다 작은 공간에 더 많은 정보를 얻을 수 있습니다. 반면에 적용 가능한 이미지 유형이 제한 될 수 있습니다. 얼굴은 흑백으로 잘 나오지만 추상적 인 디자인은 그다지 좋지 않을 수 있습니다.
    5. 출력 이미지가 입력보다 작 으면 대략 동일한 비율이면 완벽하게 괜찮습니다. 원본과 비교하기 위해 이미지를 확대해야하는 경우에도 괜찮습니다. 중요한 것은 그것이 어떻게 보이는지입니다.
  6. 당신의 프로그램은 실제로 트위터를 통과하고 상처없이 나올 수있는 결과물을 생산해야합니다. 지원되는 정확한 문자 세트에 대한 문서를 찾을 수 없기 때문에 이것은 규칙이 아니라 지침 일뿐입니다. 그러나 제어 문자, 보이지 않는 결합 문자, 개인용 문자 등은 피해야합니다.

채점 루 브릭

허용되는 솔루션을 선택할 때 솔루션 순위를 매기는 방법에 대한 일반적인 지침으로 25 점 척도로 솔루션을 평가할 것이라고 가정 해 보겠습니다 (매우 거칠고 직접 사용하여 직접 점수를 매기 지 않을 것입니다). 이것은 기본 지침으로) :

  • 인코딩 체계가 광범위한 입력 이미지를 얼마나 잘 재현하는지 15 점 . 이것은 주관적이고 미학적 판단입니다
    • 0은 전혀 작동하지 않음을 의미하며 매번 같은 이미지를 다시 제공합니다.
    • 5는 디코딩 된 버전이보기에 좋지 않고 더 복잡한 이미지에서는 전혀 작동하지 않을 수 있지만 몇 개의 이미지를 인코딩 할 수 있음을 의미합니다.
    • 10은 광범위한 이미지에서 작동하며 때로는 눈에 잘 띄는 유쾌한 이미지를 생성 함을 의미합니다.
    • 15는 일부 이미지의 완벽한 복제본을 생성하고 더 크고 복잡한 이미지의 경우에도 인식 할 수있는 무언가를 제공함을 의미합니다. 또는 인식 할 수있는 이미지를 만들지 않지만 원본에서 명확하게 파생 된 아름다운 이미지를 생성 할 수 있습니다.
  • 3 점유니 코드 문자 집합을 영리하게 사용하기위한
    • 허용되는 전체 문자 집합을 간단히 사용하기위한 0 점
    • 트위터를 통해 또는보다 다양한 상황에서 안전하게 전송할 수있는 제한된 문자 집합을 사용하기위한 1 포인트
    • Han 표의 문자 만 또는 오른쪽에서 왼쪽으로 만 문자와 같은 주제별 하위 집합을 사용하기위한 2 점
    • 읽을 수있는 텍스트를 생성하거나 문제의 이미지처럼 보이는 문자를 사용하는 등 실제로 깔끔한 작업을 수행하기위한 3 가지 포인트
  • 영리한 알고리즘 접근법과 코드 스타일을위한

    3 가지 포인트

    • 이미지를 축소하고 픽셀 당 1 비트로 처리하고 base64로 인코딩하기 위해 1000 줄의 코드 만있는 0 포인트
    • 표준 인코딩 기술을 사용하고 잘 작성되고 간단한 무언가를위한 1 점
    • 비교적 새로운 인코딩 기술을 도입하거나 놀랍도록 짧고 깨끗한 것을 나타내는 2 포인트
    • 실제로 좋은 결과를 생성하는 하나의 라이너 또는 그래픽 인코딩의 새로운 지평을 여는 무언가에 대해 3 점 게다가)
  • 속도 2 점 다른 모든 것은 같고 빠를수록 좋습니다. 그러나 위의 기준은 속도보다 중요합니다.
  • 자유 소프트웨어를 선호하기 때문에 무료 (오픈 소스) 소프트웨어에서 1 포인트 실행 (C #은 Mono에서 실행되는 한이 포인트를 계속 사용할 수 있습니다. 마찬가지로 MATLAB 코드는 GNU Octave에서 실행되는 경우에도 마찬가지입니다)
  • 실제로 모든 규칙을 따르는 경우 1 점 . 이 규칙은 조금 크고 복잡해 졌으므로 작은 세부 사항이 잘못되어있는 좋은 대답을 받아 들일 것입니다. 그러나 실제로 모든 규칙을 따르는 솔루션에 대한 추가 포인트를 줄 것입니다.

참조 이미지

일부 사람들은 참조 이미지를 요청했습니다. 다음은 시도 할 수있는 몇 가지 참조 이미지입니다. 더 작은 버전은 여기에 포함되어 있으며 필요한 경우 더 큰 버전의 이미지로 연결됩니다.

레나
모나리자
코넬 박스
StackOverflow 로고

나는 제공하고 500 담당자 현상금 솔루션에 대한 (플러스 50 그 StackOverflow의 킥을) 그 I 위의 기준에 따라, 최고의있다. 물론 다른 모든 사람들도 여기에서 자신이 좋아하는 솔루션에 투표하도록 권장합니다.

마감 시한

이 콘테스트는 5 월 30 일 토요일 오후 6 시경에 현상금이 소진 될 때까지 진행됩니다. 나는 그것이 끝나는 정확한 시간을 말할 수 없습니다. 오후 5시에서 7시 사이에있을 수 있습니다. 오후 2 시까 지 제출 된 모든 출품작을 볼 것을 보장 할 것이며 오후 4 시까 지 제출 된 모든 출품작을 보도록 최선을 다하겠습니다. 그 이후에 솔루션을 제출하면 결정을 내리기 전에 공정한 모습을 보일 기회가 없을 수 있습니다. 또한 제출이 빠를수록 최적의 솔루션을 선택할 수 있도록 투표 할 수있는 기회가 많아 지므로 마감 시한이 아니라 빨리 제출하여 제출하십시오.

유니 코드 노트

정확히 어떤 유니 코드 문자가 허용되는지에 대한 혼동이있었습니다. 가능한 유니 코드 코드 포인트 범위는 U+0000U+10FFFF. 열린 데이터 교환에서 유니 코드 문자로 사용하기에는 결코 유효하지 않은 일부 코드 포인트가 있습니다. 이들은입니다 noncharacters대리 코드 포인트 . Noncharacters가 정의되어 Unidode 표준 섹션 5.1.0 1670 값으로 U+FFFE, U+FFFF, U+NFFFE , U+NFFFF 여기서 N 이다 1– . 이러한 값은 응용 프로그램 별 내부 용도로 사용되며 적합한 응용 프로그램은 이러한 문자를 처리 한 텍스트에서 제거 할 수 있습니다. 에 정의 된 대리 코드 포인트10 진수 및 범위 U+FDD0U+FDEF유니 코드 표준 5.1.0 3.8 으로는 U+D800U+DFFF, UTF-16에 기본 다국어 평면을 넘어 문자를 인코딩하는 데 사용된다 따라서 이러한 코드 포인트를 UTF-16 인코딩으로 직접 표현할 수 없으며 다른 인코딩으로 인코딩 할 수 없습니다. 따라서,이 대회의 목적을 위해, 전 범위 이상이면 140 유니 코드 코드 포인트들의 시퀀스로 영상을 부호화하는 프로그램을 수 U+0000U+10FFFF 상기 정의 된 바와 같은 모든 noncharacters 및 게이트 쌍을 제외한.

나는 것이다 선호 에만 할당 된 문자 및 할당 된 문자의 영리한 하위 집합을 사용하거나 그들이 사용하는 문자 집합으로 뭔가 재미있는을 더 나은 사람을 사용하는 솔루션을. 할당 된 문자 목록은 유니 코드 문자 데이터베이스를 참조하십시오 . 일부 문자는 직접 나열되고 일부 문자는 범위의 시작과 끝으로 만 나열됩니다. 또한 대리 코드 포인트는 데이터베이스에 나열되어 있지만 위에서 언급 한 바와 같이 금지되어 있습니다. 출력하는 텍스트를 더 흥미롭게 만들기 위해 특정 문자 속성을 활용하려면 명명 된 코드 블록 목록다양한 문자 속성 과 같은 다양한 문자 정보 데이터베이스를 사용할 수 있습니다..

트위터는 그들이 지원하는 정확한 문자 세트를 지정하지 않기 때문에 특정 문자가 추가되거나 특정 문자가 제거되기 때문에 실제로 트위터와 작동하지 않는 솔루션에 대해 관대합니다. 모든 인코딩 된 출력을 트위터 나 identi.ca 와 같은 다른 마이크로 블로깅 서비스를 통해 무해 하게 전송할 수 있어야하지만 바람직하지는 않습니다 . 트위터 엔터티가 <,> 및 &를 인코딩하여 각각 4, 4 및 5 문자로 계산한다는 내용의 문서를 보았지만 직접 테스트하지는 않았으며 JavaScript 문자 카운터가 보이지 않습니다. 그런 식으로 그들을 계산합니다.

팁 및 링크

  • 규칙에서 유효한 유니 코드 문자의 정의는 약간 복잡합니다. CJK Unified Ideographs (U + 4E00–U + 9FCF)와 같은 단일 문자 블록을 선택하는 것이 더 쉬울 수 있습니다.
  • 이미지 조작에 ImageMagick 또는 Python Imaging Library 와 같은 기존 이미지 라이브러리를 사용할 수 있습니다 .
  • 유니 코드 문자 집합 및 다양한 인코딩을 이해하는 데 도움이 필요한 경우이 빠른 안내서 또는 Linux 및 Unix의 UTF-8에 대한 자세한 FAQ를 참조하십시오 .
  • 솔루션을 일찍받을수록 더 많은 시간을 투표해야합니다. 개선하면 솔루션을 편집 할 수 있습니다. 솔루션을 마지막으로 살펴볼 때 최신 버전을 기반으로 현상금을 적용합니다.
  • 쉬운 이미지 형식을 구문 분석하고 쓰려면 (기존 형식 만 사용하고 싶지 않은 경우) PPM 형식을 사용하는 것이 좋습니다 . 작업하기 매우 쉬운 텍스트 기반 형식이며 ImageMagick 을 사용 하여 변환 할 수 있습니다 .


답변

자, 여기에 nanoakeunch.cppCMakeLists.txt 파일이 있습니다. 그것은에 의존 마법 (magick) ++ 의 이미지 처리의 대부분을 ImageMagick과의 API. 또한 문자열 인코딩을위한 bignum 산술을위한 GMP 라이브러리 가 필요합니다 .

나는 몇 가지 독특한 왜곡으로 프랙탈 이미지 압축을 기반으로 솔루션을 기반으로했습니다. 기본 아이디어는 이미지를 가져 와서 복사본을 50 %로 축소하고 원본 이미지의 겹치지 않는 블록과 비슷한 다양한 방향으로 조각을 찾는 것입니다. 이 검색에는 매우 무차별 한 접근 방식이 필요하지만 수정 사항을 쉽게 소개 할 수 있습니다.

첫 번째 수정은 90도 회전과 뒤집기를 보는 대신 45도 방향을 고려한다는 것입니다. 그것은 블록 당 하나 더 비트이지만 이미지 품질을 엄청나게 도와줍니다.

다른 한 가지는 각 블록의 각 색상 구성 요소에 대한 대비 / 밝기 조정을 저장하는 것이 너무 비싸다는 것입니다. 대신, 나는 약간의 비율로 혼합되는 심하게 양자화 된 색상 (팔레트에는 4 * 4 * 4 = 64 색상 만 있음)을 저장합니다. 수학적으로, 이것은 각 색상의 가변 밝기 및 일정한 대비 조정과 같습니다. 불행히도, 이는 색상을 뒤집는 부정적인 대조가 없다는 것을 의미합니다.

각 블록의 위치, 방향 및 색상이 계산되면이를 UTF-8 문자열로 인코딩합니다. 먼저 블록 테이블의 데이터와 이미지 크기를 나타내는 매우 큰 bignum을 생성합니다. 이것에 대한 접근 방식은 Sam Hocevar의 솔루션과 유사합니다. 위치에 따라 기수가 많은 수의 종류입니다.

그런 다음 사용 가능한 문자 집합의 크기에 관계없이 기본으로 변환합니다. 기본적으로 할당 된 유니 코드 문자 집합에서 앰퍼샌드, 제어, 결합 및 대리 문자 및 개인 문자를 뺀 값보다 작거나 큽니다. 예쁘지는 않지만 작동합니다. 기본 테이블을 주석 처리하고 대신 인쇄 가능한 7 비트 ASCII (<,> 및 & 문자 제외) 또는 CJK Unified Ideograph를 선택할 수도 있습니다. 사용 가능한 문자 코드 테이블에 유효하지 않은 유효한 문자가 번갈아 실행 된 길이가 저장됩니다.

어쨌든, 여기에 일부 이미지와 시간이 있습니다 (이전 3.0GHz P4에서 측정). 위에서 설명한 전체 할당 된 유니 코드 세트에서 140 자로 압축되었습니다. 전반적으로, 나는 그들이 모두 어떻게 밝혀 졌는지 상당히 기쁘게 생각합니다. 이것에 대해 더 많은 시간을 할애했다면 아마도 압축 해제 된 이미지의 방해를 줄이려고 할 것입니다. 그럼에도 불구하고 결과는 극단적 인 압축 비율에 매우 적합하다고 생각합니다. 압축 해제 된 이미지는 약간 인상적이지만 비트가 원본과 어떻게 일치하는지 쉽게 알 수 있습니다.

스택 오버플로 로고 (8.6 초 인코딩, 7.9 초 디코딩, 485 바이트) :
http://i44.tinypic.com/2w7lok1.png

Lena (32.8 초 인코딩, 13.0 초 디코딩, 477 바이트) :
http://i42.tinypic.com/2rr49wg.png http://i40.tinypic.com/2rhxxyu.png

모나리자 (43.2 초, 14.5 초, 490 바이트) :
http://i41.tinypic.com/ekgwp3.png http://i43.tinypic.com/ngsxep.png

편집 : CJK 통합 문자

Sam은 이것을 CJK와 함께 사용하는 것에 대한 의견을 물었습니다. CJK Unified 문자 세트에서 139 자로 압축 된 Mona Lisa 버전은 다음과 같습니다.

http://i43.tinypic.com/2yxgdfk.png
咏 璘 驞 凄 脒 鵚 据 蛥 鸂 拗 朐 朖 辿 韩 瀦 魷 歪 痫 栘 璯 緍 脲 蕜 抱 揎 頻 蓼 債 鑡 嗞 靊 寞 柮 嚛 嚵 籥 聚隤 慛 絖 銓 馿 渫 櫰 矍 昀 鰛 掾 撄 粂 敽 牙 稉 擎 蔍 螎 葙 峬 覧 絀 蹔 抆 惫 冧 笻 哜 搀 澐 芯 譶 辍 澮 垝 黟 偞 媄 童 竽 梀 韠 镰 猳 閺 狌 而 羶 喙伆 杇 婣 唆 鐤 諽 鷍 鴞 駫 搶 毤 埙 誖 萜 愿 旖 鞰 萗 勹 鈱 哳 垬 濅 鬒 秀 瞛 洆 认 気 狋 異 闥 籴 珵 仾 氙 熜 謋 繴 茴 晋 髭 杍 嚖 熥 勳 縿 餅 珝 爸擸 萿

내가 사용했던 프로그램 상단의 튜닝 매개 변수는 19, 19, 4, 4, 3, 10, 11, 1000, 1000입니다. 또한 number_assigned 및 코드의 첫 번째 정의를 주석 처리하고 주석 처리를 제거했습니다. CJK Unified 문자 세트를 선택하기위한 마지막 정의.


답변

이미지 파일 및 파이썬 소스 (버전 1 및 2)

버전 1
다음은 첫 번째 시도입니다. 가면서 업데이트하겠습니다.

나는 SO 로고를 거의 무손실로 300 자로 줄였습니다. 내 기술은 SVG 벡터 아트로의 변환을 사용하므로 라인 아트에서 가장 잘 작동합니다. 실제로는 SVG 압축기이며 여전히 원본 아트가 벡터화 단계를 거쳐야합니다.

첫 번째 시도 에서 PNG 추적에 온라인 서비스 를 사용 했지만 potrace (오픈 소스)를 포함하여이 부분을 처리 할 수있는 많은 무료 도구와 무료 도구가 있습니다 .

결과는 다음과 같습니다

원본 SO 로고 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo.png 원본
디코딩 된 SO 로고 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded.png 인코딩 후 및 디코딩

캐릭터 : 300

시간 : 측정되지 않았지만 실제로 즉각적 임 (벡터화 / 래스터 화 단계는 포함되지 않음)

다음 단계는 유니 코드 문자 당 4 개의 심볼 (SVG 경로 포인트 및 명령)을 포함하는 것입니다. 현재 내 파이썬 빌드에는 문자 당 해상도를 제한하는 UCS4가 지원되지 않습니다. 또한 최대 범위를 유니 코드 예약 범위 0xD800의 하단으로 제한했지만 허용되는 문자 목록과 필터를 피하기 위해 필요한 문자 수를 이론적으로 70-100까지 낮출 수 있습니다. 위의 로고.

현재이 방법의 한계는 출력 크기가 고정되어 있지 않다는 것입니다. 벡터화 후 벡터 노드 / 포인트 수에 따라 다릅니다. 이 제한을 자동화하려면 이미지를 픽셀 화 (벡터의 주요 이점 제거)하거나 원하는 노드 수에 도달 할 때까지 단순화 단계를 통해 경로를 반복 실행해야합니다 (현재 Inkscape에서 수동으로 수행 중임).

버전 2

업데이트 : v2는 이제 경쟁 할 자격이 있습니다. 변경 사항 :

  • 명령 줄 제어 입력 / 출력 및 디버깅
  • 정규식 대신 SVG를 처리하기 위해 XML 파서 (lxml)를 사용합니다.
  • 유니 코드 심볼 당 2 개의 경로 세그먼트 팩
  • 문서화 및 정리
  • style = “fill : color”및 fill = “color”지원
  • 단일 문자로 포장 된 문서 너비 / 높이
  • 단일 문자로 포장 된 경로 색상
  • 색상 당 4 비트의 색상 데이터를 버린 다음 16 진수 변환을 통해 문자로 압축하여 색상 압축을 수행합니다.

캐릭터 : 133

시간 : 몇 초

v2 디코딩 http://www.warriorhut.org/graphics/svg_to_unicode/so-logo-decoded-v2.png 인코딩 및 디코딩 후 (버전 2)

보시다시피 이번에는 몇 가지 아티팩트가 있습니다. 그것은 방법의 제한이 아니라 내 전환의 어딘가에 실수입니다. 아티팩트는 포인트가 0.0-127.0 범위를 벗어날 때 발생하며이를 제한하려는 시도가 혼합 된 성공을 거두었습니다. 해결책은 단순히 이미지를 축소하는 것이지만 대지 또는 그룹 매트릭스가 아닌 실제 지점의 크기를 조정하는 데 문제가있어서 걱정하기에 너무 피곤합니다. 요컨대, 포인트가 지원되는 범위에 있으면 일반적으로 작동합니다.

중간의 꼬임은 핸들이 연결된 핸들의 다른쪽으로 이동하기 때문이라고 생각합니다. 기본적으로 포인트는 처음에 너무 가깝습니다. 압축하기 전에 소스 이미지에 대해 단순 필터를 실행하면이를 수정하고 불필요한 문자를 제거해야합니다.

업데이트 :이 방법은 간단한 객체에 적합하므로 복잡한 경로를 단순화하고 노이즈를 줄이는 방법이 필요했습니다. 이 작업에 Inkscape 를 사용했습니다 . Inkscape를 사용하여 불필요한 경로를 정리하는 데 운이 있었지만 자동화 할 시간이 없었습니다. 경로 수를 줄이기 위해 Inkscape ‘Simplify’기능을 사용하여 샘플 svgs를 만들었습니다.

단순화는 정상적으로 작동하지만이 많은 경로로 인해 느릴 수 있습니다.

AUTOTRACE 예 http://www.warriorhut.org/graphics/svg_to_unicode/autotrace_16_color_manual_reduction.png 코넬 상자 http://www.warriorhut.com/graphics/svg_to_unicode/cornell_box_simplified.png 레나 http://www.warriorhut.com/graphics /svg_to_unicode/lena_std_washed_autotrace.png

추적 된 썸네일 http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_autotrace.png

다음은 초 저해상도입니다. 일부 영리한 경로 압축이 필요할 수도 있지만 140 자 제한에 가깝습니다.

손질 http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_groomed.png
단순화 및 얼룩 제거.


삼각 분할 http://www.warriorhut.org/graphics/svg_to_unicode/competition_thumbnails_triangulated.png 단순화, 얼룩 제거 및 삼각 분할.

autotrace --output-format svg --output-file cornell_box.svg --despeckle-level 20 --color-count 64 cornell_box.png

위 : autotrace를 사용하여 단순화 된 경로 .

불행히도 내 파서는 자동 추적 출력을 처리하지 않으므로 포인트가 어떻게 사용되는지 또는 얼마나 멀리 단순화 해야하는지 알지 못합니다. 슬프게도 마감 시간 전에 쓸 시간이 거의 없습니다. 그래도 inkscape 출력보다 구문 분석이 훨씬 쉽습니다.


답변

내 전체 솔루션은에서 찾을 수 있습니다 http://caca.zoy.org/wiki/img2twit . 다음과 같은 기능이 있습니다.

  • 합리적인 압축 시간 (고품질의 경우 약 1 분)
  • 빠른 감압 (1 분의 1)
  • 종횡비가 아닌 원본 이미지 크기를 유지합니다
  • 적절한 재구성 품질 (IMHO)
  • 메시지 길이 및 문자 세트 (ASCII, CJK, 기호)는 런타임에 선택할 수 있습니다
  • 압축 해제시 메시지 길이 및 문자 세트가 자동 감지됩니다.
  • 매우 효율적인 정보 포장

http://caca.zoy.org/raw-attachment/wiki/img2twit/so-logo.png
http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter4.png

蜥 秓 鋖 筷 聝 诿 缰 偺 腶 漷 庯 祩 皙 靊 谪 獜 岨 幻 寤 厎 趆 脘 搇 梄 踥 桻 理 戂 溥 欇 渹 裏 軱 骿 苸 髙 骟 市 簶 璨 粭 浧 鱉 捕 弫 潮 衍 蚙 瀹 岚玧 霫 鏓 蓕 戲 債 鼶 襋 躻 弯 袮 足 庭 侅 旍 凼 飙 驅 據 嘛 掔 倾 诗 籂 阉 嶹 婻 椿 糢 墤 渽 緛 赐 更 儅 棫 武 婩 縑 逡 荨 璙 杯 翉 珸 齸 陁 颗 鳣 憫擲 舥 攩 寉 鈶 兓 庭 璱 篂 鰀 乾 丕 耓 庁 錸 努 樀 肝 亖 弜 喆 蝞 躐 葌 熲 谎 蛪 曟 暙 刍 镶 媏 嘝 驌 慸 盂 氤 缰 殾 譑

인코딩 프로세스에 대한 대략적인 개요는 다음과 같습니다.

  • 사용 가능한 비트 수는 원하는 메시지 길이와 사용 가능한 문자 집합에서 계산됩니다.
  • 소스 이미지는 사용 가능한 비트가 허용하는 한 많은 정사각형 셀로 분할됩니다.
  • 고정 된 수의 포인트 (현재 2)가 초기 좌표 및 색상 값을 가진 각 셀에 영향을줍니다.
  • 품질 조건이 충족 될 때까지 다음이 반복됩니다.
    • 점은 무작위로 선택됩니다
    • 이 시점에서 임의로 작업이 수행됩니다 (셀 내부로 이동하여 색상 변경).
    • 결과 이미지 (아래 디코딩 프로세스 참조)가 소스 이미지에 더 가까운 경우 작업이 유지됩니다.
  • 이미지 크기와 포인트 목록은 UTF-8로 인코딩됩니다.

그리고 이것은 디코딩 과정입니다 :

  • UTF-8 스트림에서 이미지 크기 및 포인트를 읽습니다.
  • 대상 이미지의 각 픽셀에 대해 :
    • 자연 환경의 목록이 계산됩니다
    • 픽셀의 최종 색상은 자연스러운 이웃 색상의 가중 평균으로 설정됩니다.

내가 프로그램의 가장 독창적 인 부분이라고 생각하는 것은 비트 스트림입니다. 비트 정렬 값 ( stream <<= shift; stream |= value) 을 압축하는 대신 2의 제곱 범위 ( stream *= range; stream += value) 가 아닌 임의의 값을 압축합니다 . 이것은 큰 숫자 계산이 필요하고 물론 훨씬 느리지 만 20902 주요 CJK 문자를 사용할 때 1960 대신 2009.18 비트를 제공합니다 (데이터에 넣을 수있는 세 가지 포인트가 더 있습니다). 그리고 ASCII를 사용할 때 840 대신 917.64 비트를 제공합니다.

처음에는 실제로 도움이 될지 확신하지 못했기 때문에 무거운 무기 (코너 감지, 특징 추출, 색 정량화 …)가 필요한 초기 이미지 계산 방법에 대해 결정했습니다. 이제 수렴이 느리다는 것을 알고 있습니다 (1 분은 허용되지만 그럼에도 불구하고 느립니다).

주요 피팅 루프는 Direct Binary Seach 디더링 알고리즘에서 느슨하게 영감을 얻었습니다 (더 나은 하프 톤을 얻을 때까지 픽셀이 무작위로 스왑되거나 뒤집 힙니다). 에너지 계산은 간단한 제곱 평균 거리이지만 원래 이미지에서 5×5 중앙값 필터를 먼저 수행합니다. 가우시안 블러는 아마도 사람의 눈 동작을 더 잘 표현할 수 있지만 날카로운 모서리를 잃고 싶지 않았습니다. 또한 프로세스를 교정 할 개월이 없기 때문에 시뮬레이션 어닐링 또는 기타 조정하기 어려운 방법에 대해 결정했습니다. 따라서 “quality”플래그는 엔코더가 끝나기 전에 각 포인트에서 수행되는 반복 횟수를 나타냅니다.

http://caca.zoy.org/raw-attachment/wiki/img2twit/Mona_Lisa_scaled.jpg
http://caca.zoy.org/raw-attachment/wiki/img2twit/twitter2.png

苉 憗 揣 嶕 繠 剳 腏 篮 濕 茝 霮 墧 蒆 棌 杚 蓳 縳 樟 赒 肴 飗 噹 砃 燋 任 朓 峂 釰 靂 陴 貜 犟 掝 喗 讄 荛 砙 矺 敨 鷾 瓔 亨 髎 芟 氲 簵 鸬 嫤 鉸 俇激 躙 憮 鄴 甮 槺 骳 佛 愚 猪 駪 惾 嫥 綖 珏 矯 坼 堭 颽 箽 赭 飉 訥 偁 箝 窂 蹻 熛 漧 衆 橼 愀 航 玴 毡 裋 頢 羔 恺 墎 嬔 鑹 楄 瑥 鶼 呍 蕖 抲 鸝 秓苾 绒 酯 嵞 脔 婺 污 囉 酼 俵 菛 琪 棺 则 辩 曚 鸸 職 銛 蒝 礭 鱚 蟺 稿 纡 醾 陴 鳣 尥 蟀 惘 鋁 髚 忩 祤 脤 养 趯 沅 况

모든 이미지가 잘 압축되지는 않지만 결과에 놀랐고 이미지를 250 바이트로 압축 할 수있는 다른 방법이 무엇인지 궁금합니다.

또한 무작위 초기 상태“양호한”초기 상태 에서 인코더 상태의 진화에 대한 작은 영화를 볼 수 있습니다.

편집 : 압축 방법과 JPEG의 비교 방법은 다음과 같습니다. 왼쪽에서 jamoes는 536 바이트 이상의 그림입니다. 오른쪽에서 Mona Lisa는 여기에 설명 된 방법을 사용하여 534 바이트로 압축했습니다 (여기에서 언급 된 바이트는 데이터 바이트를 나타내므로 유니 코드 문자를 사용하여 낭비 된 비트는 무시 함).

http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona.jpg
http://caca.zoy.org/raw-attachment/wiki/img2twit/minimona2.png

편집 : CJK 텍스트를 최신 버전의 이미지로 대체했습니다.


답변

내 소프트웨어가 표시된 작업에 맞게 조정되지 않았으므로 다음은 공식 제출이 아닙니다. DLI 는 최적화 된 범용 손실 이미지 코덱으로 설명 될 수 있습니다. 이미지 압축을위한 PSNR 및 MS-SSIM 레코드 홀더이며,이 특정 작업에서 어떻게 작동하는지 보는 것이 흥미로울 것입니다. 제공된 참조 Mona Lisa 이미지를 사용하여 100×150으로 축소 한 다음 DLI를 사용하여 344 바이트로 압축했습니다.

모나리자 DLI http://i40.tinypic.com/2md5q4m.png

JPEG 및 IMG2TWIT 압축 샘플과 비교하기 위해 DLI를 사용하여 이미지를 534 바이트로 압축했습니다. JPEG는 536 바이트이고 IMG2TWIT는 534 바이트입니다. 쉽게 비교할 수 있도록 이미지의 크기가 대략 같은 크기로 조정되었습니다. JPEG는 왼쪽 이미지이고 IMG2TWIT는 중앙이며 DLI는 오른쪽 이미지입니다.

비교 http://i42.tinypic.com/302yjdg.png

DLI 이미지는 얼굴 특징 중 일부, 특히 유명한 미소를 보존합니다. 🙂


답변

내 솔루션의 일반적인 개요는 다음과 같습니다.

  1. 140 utf8 문자에 들어갈 수있는 최대 원시 데이터 양을 계산하는 것으로 시작합니다.
    • (나는 원래 웹 사이트 가 트위터가 메시지를 저장했다고 주장 하는 utf8을 가정 하고 있습니다. 이것은 위의 문제 설명과 다르며 utf16을 요청합니다.)
    • 사용 이 utf8 faq를 하여 단일 utf8 문자로 인코딩 할 수있는 최대 비트 수가 31 비트 인 것으로 계산합니다. 이를 위해 U-04000000 – U-7FFFFFFF 범위에있는 모든 문자를 사용합니다. (1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx, 31 x가 있으므로 최대 31 비트를 인코딩 할 수 있습니다).
    • 31 비트 x 140자는 4340 비트와 같습니다. 8로 나누면 524.5가되고 542 바이트 합니다 .
    • (자체를 utf16으로 제한하면 문자 당 2 바이트 만 저장할 수 있으며 이는 280 바이트와 같습니다).
  2. 표준 jpg 압축을 사용하여 이미지를 압축합니다.
    • 이미지의 크기를 약 50×50 픽셀로 조정 한 다음 이미지 크기가 최대 542 바이트에이를 때까지 여러 가지 압축 수준으로 압축하십시오.
    • 다음은 536 바이트로 압축 된 모나리자 의 예 입니다.
  3. 압축 된 이미지의 원시 비트를 UTF-8 문자로 인코딩하십시오.
    • 각 바이트를 이미지의 비트로 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 바이트로 바꿉니다.
    • 이 부분은 아마도 현재 존재하는 어떤 것도 없기 때문에 대부분의 코드를 작성해야 할 부분 일 것입니다.

나는 당신이 코드를 요구한다는 것을 알고 있지만 실제로 이것을 코딩하는 데 시간을 보내고 싶지 않습니다. 효율적인 디자인은 적어도 다른 사람이 이것을 코딩하도록 영감을 줄 수 있다고 생각했습니다.

제안 된 솔루션의 가장 큰 장점은 기존 기술을 최대한 재사용한다는 것입니다. 좋은 압축 알고리즘을 작성하는 것은 재미있을 수 있지만, 수학 수준이 높은 사람들이 작성한 더 나은 알고리즘이 보장됩니다.

다른 중요한 참고 사항은 utf16이 선호하는 인코딩으로 결정되면이 솔루션은 분리된다는 것입니다. jpeg는 280 바이트로 압축 될 때 실제로 작동하지 않습니다. 그러나이 특정 문제 설명에 대해 jpg보다 더 나은 압축 알고리즘이있을 수 있습니다.


답변

좋아, 나는 게임에 늦었지만 그럼에도 불구하고 나는 프로젝트를 만들었다.

반투명 다채로운 원을 사용하여 초기 이미지를 재현하는 완구 유전자 알고리즘입니다.

풍모:

  • 순수한 루아. Lua 인터프리터가 실행되는 곳에서 실행합니다.
  • netpbm P3 형식을 사용합니다
  • 포괄적 인 단위 테스트 세트가 제공됩니다
  • 원본 이미지 크기를 유지합니다

잘못된 사람들 :

  • 느린
  • 이 공간 제약 조건에서는 초기 이미지의 기본 색 구성과 몇 가지 특징에 대한 일반적인 개요 만 유지합니다.

다음은 Lena를 나타내는 예입니다. 犭 楊 谷 杌 蒝 螦 界 匘 玏 扝 匮 俄 归 晃 客 猘 摈 硰 划 刀 萕 码 摃 斢 嘁 蜁 嚎 耂 澹 簜 僨 砠 偑 婊 內 團 揕 忈 義 倨 襠 凁 梡岂 掂 戇 耔 攋 斘 眐 奡 萛 狂 昸 箆 亲 嬎 廙 栃 兡 塅 受 橯 恰 应 戞 优 猫 僘 瑩 吱 賾 卣 朸 杈 腠 綍 蝘 猕 屐 稱 悡 ​​詬 來 噩 压 罍 尕 熚 帤 厥 虤 嫐虲 兙 罨 縨 炘 排 叁 抠 堃 從 弅 慌 螎 熰 標 宑 簫 柢 橙 拃 丨 蜊 缩 昔 儻 舭 勵 癳 冂 囤 璟 彔 榕 兠 摈 侑 蒖 孂 埮 槃 姠 璐 哠 眛 嫡 琠 枀 訜 苄 暬厇 廩 焛 瀻 严 啘 刱 垫 仔

오리지널 레나 인코딩 된 레나

이 코드는 bitbucket.org의 Mercurial 저장소에 있습니다. http://bitbucket.org/tkadlubo/circles.lua를 확인하십시오


답변

다음은 문제에 대한 나의 접근 방식이며, 이것이 매우 흥미로운 프로젝트라는 것을 인정해야합니다. 그것은 분명히 정상적인 작업 영역을 벗어 났으며 나에게 새로운 것을 배울 수있는 것을주었습니다.

내 기본 아이디어는 다음과 같습니다.

  1. 총 16 가지 음영이 존재하도록 이미지 그레이 스케일을 다운 샘플링
  2. 이미지에서 RLE 프리폼
  3. 결과를 UTF-16 문자로 압축하십시오
  4. 압축 된 결과에서 RLE을 수행하여 문자 중복 제거

이것이 작동하지만 아래 샘플 이미지에서 볼 수 있듯이 제한된 범위에서만 작동합니다. 출력 측면에서 다음은 샘플 트윗, 특히 샘플에 표시된 Lena 이미지에 대한 샘플 트윗입니다.

乤 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 2 企 伂 8 企 伂 3 企 伂 5 企 倂 倃 伂 倁 3 企 儁 企 2 伂 倃 5 企 倁 3 企 倃 4 企 倂 企 倁 企伂 2 企 伂 5 企 倁 企 伂 쥹 皗 鞹 鐾 륶 䦽 阹 럆 䧜 椿 籫 릹 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 㞳 鞷 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 殞 焻 鍴 祳 㭾 뤶 殞 焻

보시다시피, 나는 문자 집합을 약간 제한하려고 시도했습니다. 그러나 이미지 색상 데이터를 저장할 때이 문제가 발생했습니다. 또한,이 인코딩 방식은 추가 이미지 정보에 사용될 수있는 많은 비트의 데이터를 낭비하는 경향이있다.

실행 시간 측면에서, 작은 이미지의 경우 코드는 제공된 샘플 이미지의 경우 약 55ms로 매우 빠르지 만 이미지가 클수록 시간이 증가합니다. 512×512 Lena 참조 이미지의 실행 시간은 1182ms입니다. 코드 자체가 성능에 대해 최적화되지 않았을 가능성이 높습니다 (예 : 모든 것이 비트 맵으로 작동 함) 므로 리팩토링 후 시간이 조금 줄어 듭니다.

내가 더 잘했을 수 있거나 코드에 잘못되었을 수있는 것에 대한 제안을 자유롭게 제공하십시오. 런타임 및 샘플 출력의 전체 목록은 다음 위치에서 찾을 수 있습니다. http://code-zen.info/twitterimage/

하나 업데이트

기본 문자열을 다시 확인하기 위해 트윗 문자열을 압축 할 때 사용되는 RLE 코드를 업데이트했습니다. 그렇다면 출력에 사용하십시오. 이것은 숫자 값 쌍에 대해서만 작동하지만 몇 문자의 데이터를 저장합니다. 실행 시간은 이미지 품질과 거의 동일하지만 트윗은 약간 작은 경향이 있습니다. 테스트를 완료하면 웹 사이트에서 차트를 업데이트하겠습니다. 다음은 Lena의 작은 버전에 대한 예제 트윗 문자열 중 하나입니다.

乤 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 5 企 倂 倃 伂 倁 グ 儁 企 2 伂 倃 ガ 倁 ジ 倃 4 企 倂 企 倁 企 伂 ツ 伂 ス 倁企 伂 쥹 皗 鞹 鐾 륶 䦽 阹 럆 䧜 椿 籫 릹 靭 욶 옷뎷 歩 㰷 歉 䴗 鑹 㞳 鞷 㬼 獴 鏙 돗 鍴 祳 㭾 뤶 殞 焻 乹 Ꮛ 靆 䍼

업데이트 2

또 다른 작은 업데이트이지만 4 가지가 아닌 3 가지 그룹으로 색상 음영을 포장하도록 코드를 수정했습니다. 여기에는 공간이 더 필요하지만 뭔가 빠지지 않으면 “홀수”문자가 더 이상 색상 위치에 나타나지 않습니다. 데이터입니다. 또한 압축을 조금 더 업데이트하여 색상 수 블록과 달리 전체 문자열에 적용 할 수 있습니다. 나는 여전히 런타임을 테스트하고 있지만 명목상 개선 된 것으로 보입니다. 그러나 이미지 품질은 여전히 ​​동일합니다. 다음은 Lena 트윗의 최신 버전입니다.

2 乤 万 乐 唂 伂 倂 倁 企 儂 2 企 倁 3 企 倁 ウ 伂 8 企 伂 エ 伂 5 企 倂 倃 伂 倁 グ 儁 企 2 伂 倃 ガ 倁 ジ 倃 4 企 倂 企 倁 企 伂 ツ 伂 ス 倁企 伂 坹 坼 坶 坻 刾 啩 容 力 吹 婩 媷 劝 圿 咶 坼 妛 啭 奩 嗆 婣 冷 咛 啫 凃 奉 佶 坍 均 喳 女 媗 决 兴宗 喓 夽 兴 唹 屹 冷 圶 埫 奫 唓 坤 喝 奎 似商 嗉 乃

StackOverflow 로고 http://code-zen.info/twitterimage/images/stackoverflow-logo.bmp Cornell Box http://code-zen.info/twitterimage/images/cornell-box.bmp Lena http : // code-zen .info / twitterimage / images / lena.bmp Mona Lisa http://code-zen.info/twitterimage/images/mona-lisa.bmp