Facebook Fingerprint Study

[Pyohwan]

• https://github.com/facebook/ThreatExchange/tree/master/hashing/tmk

• 학습자료

  • 12/5일 1차 15page까지 학습하기
  • https://github.com/facebook/ThreatExchange/blob/master/hashing/hashing.pdf

[Pyohwan]

Summary

TMK (for Temporal Match Kernel) 은 Facebook API Research ('FAIR') 와 함께 만든 비디오 유사성 감지(video-similarity-detection) 알고리즘이다.

Status

• 회사간 공유를 위해 exports 위해선, 늘어선 비디오 목록을 해시한 다음, 해당 데이터를 공개해야 한다. (ex. ThreatExchange) -- 이것은 작은 노력이며, imports 하기 위해선 모든 비디오 해시하고 해시 목록과 비교해야 한다 -- 이것은 대규모 노력이다. 현재 (2019-01-18) 이 코드는 single-machine-only 이다 : 아직 DB 나 RPC 에 연결 된건 없다
• FAISS와의 통합이 성공적으로 프로토 타입되었습니다. 이에 대한 정보를 곧 게시 할 예정입니다.

  Goals

• 정확하게 동일한 샘플 비디오를 해시하고 얻음
• 파일 포맷 이슈를 알려달라
• 초기 match-threshold 값을 사용해서 matching 컨텐츠를 찾는지 확인해 달라
• 알고리즘 추가 원하면 pull request 해라
• 특히 PDQ의 자바 포트를 선호하는데 TMK 도 마찬가지다

이후 내용들은 사용법 설정 등의 내용이라 안 읽음

[Pyohwan]

THE TMK+PDQF VIDEO-HASHING ALGORITHM AND THE PDQ IMAGE- HASHING ALGORITHM

우리는 copy-detection 문제 공간을 위한 한쌍의 기술을 제시한다.

• PDQ, 범용적인 photo-hashing 알고리즘. 해시는 256 bits의 해밍 distance, 0~100 품질 메트릭으로 quantifles 레벨을 정량화 한다 e.g. 흐릿하거나 기능 없는 이미지를 식별한다. Hash-computation 시간은 이미지 파일의 디스크 읽기와 동일한 크기이다.
• TMK+PDQF, 범용 video-hashing 알고리즘. PDQ 에서 최종 binary-quantization 단계를 빼고, TMK 알고리즘으로 frames 의 시간 정보를 수집한다. 해시는 256KB 지만 첫번째 1KB 가 모든 비디오를 구별한다. Hash-computation 시간은 video-playback 시간보다 높은 배수다 : 저장 밀도에 따라 최대 30배
• Facebook 의 abuse-detction 패턴에서 배운 large-scale 교훈을 활용하도록 디자인 함

  OVERVIEW

  DESIGN GOALS

  TMK+PDQF and PDQ 는 의미(semantic) 보다는 구문(syntactic) hasher 이다. semantic 알고리즘은 이미지에서 나무를 찾는것 처럼 기능(features)를 감지한다. 얼굴 특징을 식별하여 다른 사진에서 개인의 사진을 감지한다. 모델 트레이닝 시간과 인식할 세트를 사전 선택하는 비용이 발생한다. 반대로 copy-detection 사례의 경우, 사전 정보나 컨텍스트가 없는 두 이미지가, 본질적으로 동일한지 확인한다.

Semantic hasher 는 Facebook 의 다양한 머신러닝 기술을 포함한다. syntactic hashers 는 PDQ와 함께 pHash , aHash, dHash, and GIST이 포함되며 이문서에서는 논외한다.

다른 동급 알고리즘과 마찬가지로 PDQ는 disk reads 속도와 거의 같게끔 실행해서 빠르다. 마찬가지로 TMK+PDQF는 몇배의 비디오 재생(playback) 속도로 실행됩니다 -- 저장 밀도에 따라 아마 30배

Syntactic hashers 는 최소한의 adversarial(적대적) 미디어를 찾는데 탁월하다 -- 이미지 품질이 떨어지고, JPEG가 PNG로 변환되고, 예를들어 의도적인 공격/난독을 탐지하는데에는 적합하지 않다. 보다 적대적인 이미지 변환의 감지는 semantic/machine-learning 방법의 영역 내에 있습니다.

보다 강력한 알고리즘은 고도로 조작 된 미디어 변형을 감지합니다; lower-level syntactic hashers 는 탐지 된 변형에 대한 정보를 전달할 수 있습니다.

요약하면 TMK+PDQF 및 PDQ는 서비스 제공 업체의 content-matching 도구 상자에 적합한 항목입니다. 처리량이 많은 온라인 해싱 기술로 제안한다. Facebook과 다른 기술 회사는 이미 다양한 사용 사례에 적합한 여러 독점 기술을 사용하고 있습니다. 내부적으로 주요 기술 회사는 다른 매칭 알고리즘이 필요하지 않습니다. 그러나 부족한 것은 공유 해시 알고리즘을 회사간 공유를 방해하는것. 이것이 TMK+PDQF 및 PDQ가 채우도록 설계된 틈새 시장입니다.

FEATURES OF TMK

TMK(for Temporal Match Kernel)는 Facebook AI Research (FAIR)와 함께 제작 된 비디오 유사성 탐지 알고리즘입니다. 256KB 정도의 고정 길이로 비디오 해시를 제한한다.

MATCHING PERFORMANCE

TMK는 frame rates, 파일 형식 및 / 또는 픽셀 해상도가 변경 되더라도 두 비디오가 시각적으로 동일한 지 여부를 감지합니다. 또한 사소한 편집도 감지한다 : 가벼운 워터 마킹, 작은 헤더 / 트레일러 시퀀스 삽입 / 삭제 등

적대적으로 수정 된 비디오는 감지 못한다. (예 : 자르기, 테두리 추가, 더 무거운 로고 / 오버레이 등) copy-detection 공간에서 사각형으로 있어야 한다.

TMK+PDQF는 전체 비디오에서, 시간별 작은 편집을 감지합니다 : 2분 동영상에서 2분 5초로 변형된 것은 감지 가능한데, 1시간 영상에 추가된 2분 영상은 감지 못함. 차후 버전의 TMK에서 scene/subsequence 감지를 포함한 적극적인 편집을 감지 할 수 있습니다. TMK+PDQF 은 강력한 semantid-matching 알고리즘이다 -- TMK+PDQF는 조직의 dontent-matching 툴킷에서 하나의 구성 요소 (해시 공유 구성 요소)입니다. 구체적으로, 원본 동영상의 모든 변형에 대한 복잡한 video-matcher가 발견 한 결과를 전달하려면 TMK 해시가 두 개 이상 필요할 수 있습니다. - TMK+PDQF 사용을 의도한것으로 본다.

HASH LENGTH

TMK + PDQF의 비디오 디스크립터 크기는 비디오 길이에 의존하지 않습니다. 해시 파일의 크기는 256KB이지만 1KB 벡터는 거의 모든 비디오를 구별하기에 충분합니다. (PDQF와 다른 프레임 단위 알고리즘을 사용하면 해시 크기가 달라집니다 - PDQF 프레임 단위 기능은 256 개의 부동 소수점 숫자이므로 SomethingElse가 프레임 당 512 개의 부동 소수점 숫자를 생성하면 TMK + SomethingElse의 해시 파일 크기는 512KB입니다.)

FEATURES OF PDQ

MATCHING PERFORMANCE

PDQ는 유사한 이미지를 매칭 (리콜)하고 이종 이미지를 분리 (정밀)하는데 효과적이다. 가볍게 (non-adversarially) 수정 된 이미지를 위해 설계되었습니다. JPEG <-> PNG 변환, JPEG 품질 감소 등을 잘 수행합니다. 많은 알고리즘과 마찬가지로 적대적을 활성화로 이 탐지를 피하기 위해 이미지를 수정할 수 있습니다. 마지막으로, PDQ는 가벼운 워터 마킹 / 로고 배치에 내성이 있다.

많은 글로벌 디스크립터 알고리즘과 마찬가지로 PDQ는 사진을 페어링하는 데 적합하지 않습니다.

이미지의 해시를 생성하는 동안 PDQ는 rotated/flipped 사진의 해시가 계산 비용을 거의 들이지 않고 계산할 수 있습니다.

QUALITY METRIC

PDQ는 사진의 해시를 생성하는 것 외에도, 상대적으로 특징이없는 이미지를 표시하는 0-100 품질 메트릭을 가지고 있습니다.

[Pyohwan]

ALGORITHMS

TMK ALGORITHM

TMK에 대한 중요한 알고리즘 세부 사항은 Poullot 등의 논문에 포함되어 있으며 중요한 구현 세부 사항은 GitHub 리포지토리에 있으므로이 섹션은 PDQ의 해당 섹션보다 짧습니다.

TMK ALGORITHM SKETCH

COMPUTING HASHES

Given a video:

• 일반적인 frame-rate로 time-resample : 초당 15 프레임
• 일부 "frame descriptor"또는 "frame feature"또는 "embedding" 계산 : 이미지에서 floating-point 벡터로의 매핑. 이 문서의 목적 상 PDQF를 사용합니다. : 이 문서의 PDQ 알고리즘 섹션에서와 같이 단순히 PDQ에서 최종 이진 양자화(binary-quantization) 단계를 뺀 것입니다. (The F is for floating- point.)
  • 다양한 기간으로 요소 별 평균 cos / sin 가중치를 계산합니다.
  • PDQF는 각 프레임에 대해 256 요소 벡터를 생성하므로 각 임시 피처도 256 요소 벡터입니다. 예를 들어, 슬롯 37은 비디오의 모든 프레임에서 슬롯 37의 시간 가중 평균입니다.
• Output:
  • 모든 프레임 기능에 대한 부담이 없는 평균을 level-1 feature 이라고합니다.
  • 코사인과 사인을 사용하여 가중 평균을 수집하고 다양한주기와 다양한 fourier 가중치를 통칭하여 level-2 feature 라고합니다.
  • 모든 프레임이 처리 된 후 모든 기능이 L2-normalized 된다; 그런 다음 level-2 feature 는 선택된 fourier 가중치에 의해 가중치가 부여됩니다.
• File format : 생략

1. 일반적인 frame-rate 로 Time-resample
2. 일부 프레임 디스크립터 계산 : 이미지에서 256-element 벡터로 임베딩 된 일부
3. 요소별 평균 cos / sin 무게는 다양한 기간으로 측정되었습니다. 해시는 모든 삼각 가중 평균입니다.
   • Lookups: 일부 삼각법.

COMPARING HASHES

• 한 쌍의 .tmk 파일이 주어지면 코사인 유사성이 level-1 feature 사이에서 계산됩니다. 이것을 level-1 pair score라고합니다. 이 값이 원하는 임계 값 0.7 (완벽 일치 1.0, 최소 가능 -1.0)보다 작 으면 비디오가 일치하지 않는 것으로 간주됩니다. 이 코사인 유사성은 빠르며 FAISS와 같은 인덱싱 시스템에 적합합니다.
• level-1 pair score 가 임계 값 내에있는 경우에만 Poullot et al.의 논문에서 자세히 설명 된 것처럼 두 .tmk 파일의 level- 2 features 에 대한보다 자세한 기능을 계산합니다. 이것을 level-2 pair score 라고합니다. 완전 일치는 1.0이고 최소값은 0.0입니다. 권장 임계 값은 0.7입니다. level-2 pair score 는 FAISS에서 색인을 생성 할 수 없지만 level-1 match 에서만 계산해야합니다. - FAISS 색인 가능한

PDQ ALGORITHM

PDQ is:

• P : 지각의(perceptual) hasher : 사람들이 비슷한 것으로 인식하는 사진을 일치 시키려고 시도합니다.
• D : 스펙트럼 해싱 알고리즘입니다. 즉, 이산 코사인 변환(Discrete Cosine Transform) (DCT)을 사용합니다.
• Q : 출력 중 하나는 quality 메트릭으로, 시스템에서 처리 중 junky/featureless 프레임을 필터링 할 수 있습니다.

또한 꽤 빠릅니다 - low-level 최적화 기회가 있지만 참조 디자인은 디스크에서 이미지 파일을 읽는 데 걸리는 시간과 같거나 작은 시간으로 이미지를 해시 할 수 있습니다.

PDQ ALGORITHM SKETCH

PDQ는 pHash에 대한 우려를 다루면서 아래에 자세히 설명 된 것처럼 pHash (Zauner, 2010)에서 영감을 얻었으며 이와 관련되어 있습니다. PDQ의 알고리즘 단계는 다음과 같습니다.

• 그레이 스케일이 아닌 RGB에서 휘도(luminance)로 변환합니다.
• 이하 생략

이러한 모든 단계 중 핵심 개념은 DCT에서 제공하는 spectral-hashing 속성입니다 : PDQ는 중간에서 낮은 공간 주파수 성분이 이미지에 어느 정도 기여하는지 식별합니다.

PDQ HASH PROPERTIES AND DISTANCE THRESHOLDS

위의 알고리즘 스케치의 사실을 고려할 때 PDQ 해시에 대해 다음과 같은 속성이 있습니다:

• 해밍 거리가 0이면 두 개의 해시가 동일합니다. 최대 해밍 거리는 256입니다.
• 이하 생략

  PDQ ALGORITHM DETAILS

  JAROSZ FILTERS AND DOWNSAMPLING

  PDQ는 가벼운 crops or shifts 와 관련하여 견고해야합니다. 이러한 이유로 64x64로 다운 샘플링하는 것은 full-resolution의 휘도 이미지에서 픽셀의 cherry-pick 이 아니라, 각 이미지 블록 내의 픽셀에 대한 평균보다 중요합니다. 이하 생략..

Pixels within each block are sliding-window averaged twice in each direction, producing a 'tent' filter peaked on the center of the block which is selected for downsample 각 블록 내의 픽셀은 슬라이딩 윈도우를 각 방향으로 평균 두 번 평균화하여, 다운 샘플링을 위해 선택된 블록 중심에 피크가 붙은 '텐트' 필터를 생성합니다.

Full-resolution luminance image is divided into 16x16 blocks 최대 해상도 휘도 이미지는 16x16 블록으로 나뉩니다

Fixed-point optimization (not helpful) : 참조 구현을 개발하는 동안 Jarosz 필터 단계는 고정 소수점으로 공동 구현되었습니다 : 위에서 언급 한대로 12 개의 소수 비트를 가진 휘도 바이트 값, 즉 스케일 팩터가 4096 인 정수를 취한 다음 정수 산술로 패스를 수행하십시오. 성능은 통계적으로 샘플링 오류 막대 내에서 부동 소수점 버전과 동등한 수준으로 유지되었으므로 단순성을 위해 부동 소수점 버전 만 유지되었습니다.

Sample images: 왼쪽은 full-resolution 컬러 입력입니다; 중앙에는 full-resolution의 휘도가 있습니다; 오른쪽은 64x64 다운 샘플입니다 (편의를 위해 확대하여 표시).

특히, 다운 샘플로 시작하는 image-hashing 알고리즘과 마찬가지로, full-resolution 이미지에서 읽을 수있는 작은 텍스트는 PDQ 다운 샘플 내에서 읽을 수 없습니다. 이는 소량의 텍스트를 기반으로 콘텐츠를 제방쌓는데 주의를 기울여야한다는 것을 의미합니다 (텍스트가 특히 불쾌한 것을 말하더라도).