• 論壇上求出處的請求
• 知道是哪套動畫，但忘了哪一集
• 猜動畫出處的遊戲

• Google Image - 只找到著名的畫面
• TinEye - 沒有涵蓋動漫
• iqdb - 只針對靜態畫作(如 Pixiv)，沒有索引動畫
• SauceNAO - 涵蓋 IQDB 及遊戲 CG，當年還沒有加入動畫 （現在有了）

https://trace.moe

trace.moe 是一種基於內容的圖像搜尋引擎

• Content-based image retrieval (CBIR)
• 圖像處理程式
• 大數據

跟 AI, Machine Learning 完全沒有關係

• Color Layout, Edge Histogram, Opponent Histogram, ScalableColor, 等等.

• 硬體需求比較低
• 對於動畫來說，顏色是一個顯著特徵，色調普遍比較鮮明
• Color Layout 能刪除更多的重覆的畫面，減少資料庫大小

• 是一個既定標準 MPEG-7 standard
• 原圖 -> 分成 8x8 格 -> 計算每格顏色平均值 -> 換算成 YCbCr 色域 -> DCT 變換 -> 量化 (quantize) -> Zigzag 排列成線性
• 
• 提取出來的圖像特徵 (image hash): FQYLBAQRFgoYFBANEBIQDw0QCw0PDxAeEhEQDhAfDQ8PEA8=

• Cryptographic hash (如 MD5, SHA) => 對原資料改動很敏感
• Image Hash (如 Color layout) => 對原資料改動有抵抗性

LIRE 本身已經實現了多種 Image Hash，可以批量分析圖檔

原影片 -> 用ffmpeg以 24 幀提取畫面 -> 用LIRE計算圖像特徵 -> 除去重覆的 Hash -> 補上時間軸 -> 加載到 solr 資料庫

圖像相似度 = 兩個HASH的相似度 (1 - Edit Distance)

• 40,000 小時動畫大約有 ~3,456,000,000 幀
• 使用 24 幀的 running window 去除重覆 Hash
• 仍需要比對約 ~977,000,000 個 hash
• 使用Locality Sensitive Hashing減少搜尋空間
• 只需要比對 1~2 百萬個 hash

• LSH 是用來加速近似搜尋的另一層 Hash (可想像為 hash tag)
• 分佈並不平均, 有些群集比較大 (小至幾萬，大至幾億)
• 從最小的群集開始找 (因為最快)，找到滿意的結果就停
• LIRE作者把這種方法命名為 IDF 並加到新版的 liresolr (ref: semanticmetadata.net)

• liresolr 是單線程的
• 把 1 個大資料庫分成 32 小份 (solr cores)
• 把 hash 寫入當時體積最小的，讓每小份的大小相若
• 32 個資料庫仍然運行在在同一台伺服器

• 資料庫體積目前是 183GB
• 關掉記憶體分頁 (SWAP)
• 使用 vmtouch 把檔案鎖在 RAM (OS Cache)

• 更多 CPU, 更多 RAM!!
• 降低搜尋準確度 (cutoff)
• 用 NVMe SSD 取代 SATA SSD

• 使用 OpenCV 的 findContours 來裁剪黑邊

若要取得這搜尋結果的預覽 Shelter, episode 1, timecode: 00:00:51.83

固定前 N 秒後 M 秒	從那一個鏡頭開始到完結
00:50.93 (-0.9) to 00:53.93 (+2.1)	00:49.22 to 00:51.30 (dynamic)

固定前後幾秒的做法，使用者能用下一個鏡頭的畫面再搜尋，進而看到更多的預覽部份

• 把每幀所有像素的數值加起來，變成一個數字
• 從中間開始找向前後找，直到數值突變超過某(固定)閾值
• 準確度可達 87%(不能再高了
• 目前只用在 Telegram Bot，沒用在 Web

• https://github.com/soruly/trace.moe
• https://github.com/soruly/trace.moe-WebExtension
• https://github.com/soruly/trace.moe-telegram-bot
• https://github.com/soruly/trace.moe-media
• https://github.com/soruly/anilist-crawler
• https://github.com/soruly/anilist-chinese
• https://github.com/soruly/liresolr
• https://github.com/soruly/sola

https://soruly.github.io/trace.moe

• 自動索引 Youtube 上的影片
• 移除重覆的影片
• 支持其他 Image Hash , 例如 FCTH (Fuzzy Color and Texture Histogram)
• Cloud Native(?)

• 開發 LIRE 及 liresolr 的 Dr. Mathias Lux
• 提供的 Anilist API 的 Josh
• 一群持續支助項目的 Patrons
• 開發 4chan-x 的 ccd0
• SauceNAO 作者 Xamayon
• 開發 docute 的 egoist
• 給我回報了 CVE-2017-6390 XSS 報告 的 bestshow
• 在 discord 上替我協助其他人的粉絲
• 那些曾分享過、批評過、給過我建議的人
• 把動畫到這世界的人 ❤

• Patrons
• Discord Channel
• Telegram Channel
• Facebook Page

• https://about.me/soruly
• https://twitter.com/soruly
• https://telegram.me/soruly
• https://www.plurk.com/soruly
• https://www.instagram.com/soruly