Webサービス・アプリを色から検索できる機能をリリースした話（色差・近似色）

## はじめに

最近、話題のWebサービス・アプリが見つかる「 [Apppla(アプラ)](https://www.appp.la) 」を開発・運営しています。その中で、サービスをカテゴリや紹介文といったテキストからの一般的な検索だけでなく、サービスカラーから検索する機能を実装した話をします。
コードの話というよりは考え方やアルゴリズム?の話です。

- Appplaとは?
- 色差アルゴリズム
- 色検索のアプローチ

## Appplaとは?
<img width="1440" alt="スクリーンショット 2018-03-13 18.14.57.png" src="https://qiita-image-store.s3.amazonaws.com/0/85665/9cb0b776-7697-8734-0c04-e9b00bc0ca48.png">

話題のWebサービス・アプリが見つかるサイトです。Techable, THE BRIDGE, Tech Crunch, PR TIMES, ProductHuntなど約50のメディアから最新のWebサービス・アプリ情報をApppla公認のキュレーターによって毎日お届けします。

見ていただけると嬉しいです＼(^o^)／
URL: https://www.appp.la

色からWebサービス・アプリを探す機能は以下から確認できます。
https://www.appp.la/colors

## 色差計算アルゴリズム

2つの色の知覚的な差を定量化するアルゴリズムはいくつかあり、いくつかの手法を紹介します。

- RGB
- CIE76
- CIE94

### RGB
色は16進数(`#ffffff`)で表記できますが、これはR(Red), G(Green), B(Blue)の3つの要素で構成されており、それらの要素に対してユークリッド距離を求めて、[この距離が小さい = 色が近い]とする方法。

色1(`R1, G1, B1`)と色2(`R2, G2, B2`)の差は

> ![RGBのユークリッド距離](https://camo.qiitausercontent.com/bcf23c61b06e4fc52ee08319e67240b275040d4c/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f66393539383032633363373335326462653961653936343638666231383865393364653639656637)
> （「[Color difference](https://en.wikipedia.org/wiki/Color_difference#Euclidean)」『ウィキペディア』より引用）

### CIE76

前述のRGBは馴染み深いと思うのですが、この方法ではLabというものが使われています。

Lab色空間は明度を意味する次元 L と補色次元の a および b を持ち、CIE XYZ 色空間の座標を非線形に圧縮したものに基づいた補色空間です。RGB出力機器の都合が優先されていますが、Lab色空間は人間の視覚を近似するよう設計されているのが特徴です。

一般的なRGBからLab色空間に変換を行う必要がありますが、その変換作業は下で説明するOSS(Ruby gems, .NET Library)があるので割愛します。

変換を行った後は、色1(`L1, a1, b1`)と色2(`L2, a2, b2`)の差は

> ![CIE76のユークリッド距離](
https://camo.qiitausercontent.com/0a7c9d9d00c05943af755d0f8a70a2b88dbc91d7/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f39343532646331383732626666636333363036363332343565323263613332643561383466336331)
> （「[Color difference](https://en.wikipedia.org/wiki/Color_difference#CIE76)」『ウィキペディア』より引用）

で求められます。この値が小さい色が似ている色ということになります。

### CIE94

CIE94は、塗料やコーディング業界で利用されている色の表現方法です。Lab色空間を維持しながら、知覚的な不均一に対応するように拡張されている。

色1(`L1, a1, b1`)と色2(`L2, a2, b2`)の差は

> ![CIE96](https://camo.qiitausercontent.com/1413a2f0214dac661eb8411b36121a7df98727eb/68747470733a2f2f77696b696d656469612e6f72672f6170692f726573745f76312f6d656469612f6d6174682f72656e6465722f7376672f33643231316533323339323936376565323365393262316533636463306665326530656634303631)
> （「[Color difference](https://en.wikipedia.org/wiki/Color_difference#CIE94)」『ウィキペディア』より引用）

で求められます。この数式で使用している数式の説明は上記のWikiより参照してください。

---

色差の計算方法は他にもいろいろあってRGB to Labなどは既にOSSなどが公開されているので、そういったものを利用することをおすすめします。

- [.NETライブラリのColorMine](http://colormine.org/)
- [Color tools for Ruby.](https://github.com/halostatue/color)

## 色検索のアプローチ

今回の実装では、RGBでの色差計算を採用しました。色をRGB形式で保存していたこともあり、楽そうだったというだけの理由です。
ただ、毎回上記のアルゴリズムで色の近似を計算していては一般的なデータベースは色検索には特化していないし、最適化も難しいので、色検索のフローを簡素化することで解決しました(多分これが一般的な解決方法な気がします)。

<img width="1440" alt="スクリーンショット 2018-04-17 15.53.32.png" src="https://qiita-image-store.s3.amazonaws.com/0/85665/991416c4-8dd9-d492-0711-31cf3a430d82.png">

あらかじめ、基本となる色を決めます。Appplaでは上記の20色を選定しています(この色の選定はマテリアルカラー表を参考にしたのですが今になってミスったなと思っています)。
近似色を保存するカラムをあらかじめ作成しておき、データベースに色を登録する際に、上記のアルゴリズムで基本色の中で一番近い色を近似色カラムに保存します。そして、あるrgbに近い色を検索する時は、rgbと基本色2０色から近い色を近似色に持つモデルを引っ張って来れば完了です。

### 実装した色検索のフロー
1. データベースにrgb値を保存する際に、あらかじめ決めた基本色に近い色を近似色として保存します。
2. 検索したい色(rgb)を受け取る
3. 受け取ったrgbと近い基本色を求める
4. 3で求めた基本色を近似色とするモデルを取得

色情報の取得は、Appplaで紹介されたサービス全体のキャプチャー画像を撮り、Rubyの`MiniMagick`を使用してその画像から支配色を抽出してカラーコードを生成しています。

```ruby
def take_colors(image_url, quantity: 10, threshold: 1)
  return [] if image_url.nil?
  image = MiniMagick::Image.open(image_url)
  result = image.run_command('convert', image_url, '-format', '%c', '-colors', quantity, '-depth', 8, 'histogram:info')
  
  # Extract colors and frequencies from result
  frequencies = result.scan(/([0-9]+)\:/).flatten.map { |m| m.to_f }
  hex_values = result.scan(/(\#[0-9ABCDEF]{6})/).flatten

  total_frequencies = colors.reduce(0.0) { |sum, (_, freq)| sum += freq }.to_f
  colors.
    map { |(hex, freq)| [hex, (freq * 100 / total_frequencies).to_i] }.
    reject { |(hex, freq)| freq < threshold }.
    sort_by { |(hex, freq)| freq }.reverse
end

```

### 参考サイト
- [色差アルゴリズムの違いをビジュアル化してみた](https://qiita.com/hachisukansw/items/98c218bc5616eaaba9a0)
- [色差を求める](http://yaamaa-memo.hatenablog.com/entry/2017/02/05/044208)
- [PHP を用いた色検出アルゴリズム – ランサーズポートフォリオを支える技術](https://engineer.blog.lancers.jp/2013/11/php-collor-mapping-algorithm/)