TL;DR

Debian/UbuntuのVLFeatは特許を取られているSIFT関連コードが削除されたものがパッケージ化されている
VLFeatのpythonバインディングであるcyvlfeatはSIFT関連コードの存在を期待しているためpipではインストールに失敗する
- SIFT関連コードだけを除外することで使えるようになる

VLFeatについて

OpenCV以外の画像処理OSSとして、VLFeatがあります(2-clause BSDライセンス)。
OpenCVがサポートしていない、PHOW, LIOP特徴を扱うことが出来ます。

基本的にはC++用ライブラリですが、Python bindingも存在しています。

pyvlfeat
- 新しめのpython, gccの組み合わせでビルドできない
cyvlfeat
- Cythonベースのwrapper

メンテナンスに関してはcyvlfeatの方が状態は良さそうだったのでこちらを使おうとしたのですが、Debian/Ubuntuパッケージのバイナリと組み合わせた時に問題があったので、その対応方法を示します。

libvlfeat-dev

Debian 9, Ubuntu 16ともにlibvlfeat-devのパッケージバージョンは0.9.20+dfsg0-1となっています。0.9.20がupstreamのバージョン、+dfsg0はDFSGに適合するよう修正したことを示すバージョン、-1がパッケージのバージョンとなっています。
DFSGとはDebian Free Software Guidelinesの略で、Debian/Ubuntuにおいて公式にパッケージ化するためには、このガイドラインを満たしたライセンスである必要があります。

全体としてはDFSGに適合しないけれども、適合ない部分を外して再配布可能な場合にこのようなバージョン番号をつけ、適合しない部分を削除した状態でパッケージ化しています。

参考: Debian Wiki What does “dfsg” or “ds” in the version string mean?

VLFeatの場合、SIFT特徴に関するコードを削除してパッケージ化しています。

cyvlfeat

cyvlfeatはそういった事情をまったく考慮していないので、pip等でインストールを試みる場合、vl/sift.h自体が存在していないため、失敗してしまいます。
対応方法としては

VLFeatをオリジナルのソースコードからビルド、インストールしてSIFTを使えるようにする
cyvlfeatの方を修正して、SIFTを使わないようにする

の2通りが考えられます。ここでは後者について説明します。

ソースコードの取得

githubより取得します。

$ git clone https://github.com/menpo/cyvlfeat
$ git checkout v0.4.6 # この記事を書いている時点の最新リリースタグ

setup.py, cyvlfeat/init.pyの修正

以下のパッチを適用します。

diff --git a/cyvlfeat/__init__.py b/cyvlfeat/\_\_init\_\_.py
index d18842c..f327cdc 100644
--- a/cyvlfeat/__init__.py
+++ b/cyvlfeat/__init__.py
@@ -3,7 +3,7 @@ import cyvlfeat.generic
 import cyvlfeat.gmm
 import cyvlfeat.hog
 import cyvlfeat.kmeans
-import cyvlfeat.sift
+#import cyvlfeat.sift


 from ._version import get_versions
diff --git a/setup.py b/setup.py
index 7775538..85e49d7 100644
--- a/setup.py
+++ b/setup.py
@@ -57,8 +57,8 @@ if IS_WIN and IS_CONDA:
     LIBRARY_DIRS.append(conda_bin_dir)

 vl_extensions = [
-    gen_extension('cyvlfeat.sift.cysift',
-                  [op.join('cyvlfeat', 'sift', 'cysift.pyx')]),
+#    gen_extension('cyvlfeat.sift.cysift',
+#                  [op.join('cyvlfeat', 'sift', 'cysift.pyx')]),
     gen_extension('cyvlfeat.fisher.cyfisher',
                   [op.join('cyvlfeat', 'fisher', 'cyfisher.pyx')]),
     gen_extension('cyvlfeat.hog.cyhog',

インストール

ソースコードからのインストールを行います。

$ python setup.py install

PythonからVLFeatを使う(cyvlfeat)