了解和實現Viola-Jones圖像分類算法
本文章翻譯自 Anmol Parande
在過去的十年中，圖像分類（Image classification）一直是一個快速增長的領域，並且神經網絡（CNN）和其他深度學習技術的使用正在迅速增長。但是，在CNN成為主流之前，另一種技術已被廣泛使用並繼續使用：Viola-Jones。
CNN是單個分類器，它查看完整圖像並應用矩陣運算來進行分類，而 Viola-Jones 採用整體方法。這意味著 Viola-Jones 使用許多不同的分類器，每個分類器查看圖像的不同部分。每個單獨的分類器都比最終分類器弱（準確度低，產生更多的誤報等），因為它吸收的信息較少。但是，將每個分類器的結果合併後，它們會產生一個強大的分類器。
由於算法的性質，Viola-Jones方法僅限於二進制分類任務（例如 Object Detection），並且訓練週期非常長。但是，由於每個弱分類器僅需要少量參數，並且具有足夠數量的弱分類器，因此誤分類率很低，因此可以對圖像進行快速分類。
功能和整體形象
在介紹Viola-Jones的論文中做出的第一個主要貢獻是在圖像識別中使用了一組簡單的功能。在大多數任務中，像素值是輸入到算法中的特徵。但是，Viola和Jones引入了以下新功能。
從陰影矩形中的像素總和中減去未陰影矩形中的像素總和。很容易看出，即使是小圖像，也有很多功能（24 x 24圖像超過160,000）。由於算法要求迭代所有特徵，因此必須非常有效地計算它們。為了做到這一點，Viola 和 Jones 介紹了完整的形象。積分圖像由以下遞歸關係定義。
s（x，y）是點（x，y）處的累積行總和，ii（x，y）是同一點處的積分圖像值，而i（x，y）是該點處的像素值。這種關係表示的是，在點（x，y）處的積分圖像是當前像素上方和左側所有像素的總和。如下所示，這使得計算矩形區域中的像素總和變得容易。
區域D中的像素之和為 ii(4)+ ii(1) - ii(2)- ii(3)，僅是四個陣列參考。讓我們通過創建一個輔助函數來開始實現該算法，該函數在給定圖像（表示為2D numpy數組）的情況下計算積分圖像。
import numpy as np #Don't forget to import numpydef integral_image(image):
ii = np.zeros(image.shape)
s = np.zeros(image.shape)
for y in range(len(image)):
for x in range(len(image[y])):
s[y][x] = s[y-1][x] + image[y][x] if y-1 >= 0 else image[y][x]
ii[y][x] = ii[y][x-1]+s[y][x] if x-1 >= 0 else s[y][x]
return ii此函數僅實現上面的遞歸關係。因為 s(x，-1)= 0，所以當 y-1 <0時，s(x，y) 就是 i(x，y)，同樣對於 ii(-1，y) 也是如此。接下來，讓我們定義一個幫助器類來存儲矩形區域，以便以後輕鬆計算要素的值。
class RectangleRegion:
def __init__(self, x, y, width, height):
self.x = x
self.y = y
self.width = width
self.height = heightdef compute_feature(self, ii):
return ii[self.y+self.height][self.x+self.width] + ii[self.y][self.x] - (ii[self.y+self.height][self.x]+ii[self.y][self.x+self.width])Viola-Jones
現在我們已經建立了幫助程序類和函數，我們可以開始創建Viola-Jones算法。讓我們從定義ViolaJones類開始。我們的算法將使用的唯一超參數是特徵的數量（即弱分類器的數量）
class ViolaJones:
def __init__(self, T = 10):
self.T = T為了進行培訓，Viola-Jones使用了Adaboost的變體。提升的一般思路是讓每個後續的弱分類器更正先前分類器的錯誤。為此，它將權重分配給每個訓練示例，訓練分類器，選擇最佳分類器，並根據分類器的誤差更新權重。標註不正確的示例將獲得更大的權重，因此它們將被選擇的下一個分類器正確分類。
視覺助推。（請參閱源文章）
這給出了算法的以下概述：
- 初始化權重
- 標準化權重
- 選擇最佳弱分類器（基於加權誤差）
- 根據所選分類器錯誤更新權重
- 重複步驟2–4 T次，其中T是所需的弱分類器數量
train在ViolaJones類中添加一個方法，我們可以在其中實現培訓。
def train(self, training):
training_data = []
for x in range(len(training)):
training_data.append((integral_image(training[x][0]), training[x][1]))現在，train將採用單個參數training_data，它是一個元組數組。元組中的第一個元素將是代表圖像的2D numpy數組，第二個元素將是其分類（正數為1，負數為0）。該循環會將所有圖像轉換成其完整的圖像格式。我們將積分圖像添加到新數組中以保留原始數據集。
初始化權重
在算法開始時，我們沒有任何錯誤可作為權重的基礎，因此，同一類別的每個訓練示例的權重都相同（即，所有積極示例與所有消極示例均被加權）。這意味著第i個圖像
其中p是肯定示例的數量，n是否定示例的數量。假設我們事先知道正例和負例的數量，因此train將它們作為參數
def train(self, training, pos_num, neg_num):
weights = np.zeros(len(training))
training_data = []
for x in range(len(training)):
training_data.append((integral_image(training[x][0]), training[x][1]))
if training[x][1] == 1:
weights[x] = 1.0 / (2 * pos_num)
else:
weights[x] = 1.0 / (2 * neg_num)構建功能
訓練的主要循環需要選擇最佳的弱分類器，但是每種可能的特徵都有一個弱分類器。因此，在開始實施培訓的主要循環之前，我們必須構建所有功能。回想一下，這些功能如下所示。
讓我們將其實現build_features為ViolaJones類的一部分，以返回所有功能的數組。
def build_features(self, image_shape):
height, width = image_shape
features = []
for w in range(1, width+1):
for h in range(1, height+1):
i = 0
while i + w < width:
j = 0
while j + h < height:
#2 rectangle features
immediate = RectangleRegion(i, j, w, h)
right = RectangleRegion(i+w, j, w, h)
if i + 2 * w < width: #Horizontally Adjacent
features.append(([right], [immediate]))
bottom = RectangleRegion(i, j+h, w, h)
if j + 2 * h < height: #Vertically Adjacent
features.append(([immediate], [bottom]))
right_2 = RectangleRegion(i+2*w, j, w, h)
#3 rectangle features
if i + 3 * w < width: #Horizontally Adjacent
features.append(([right], [right_2, immediate]))
bottom_2 = RectangleRegion(i, j+2*h, w, h)
if j + 3 * h < height: #Vertically Adjacent
features.append(([bottom], [bottom_2, immediate]))
#4 rectangle features
bottom_right = RectangleRegion(i+w, j+h, w, h)
if i + 2 * w < width and j + 2 * h < height:
features.append(([right, bottom], [immediate, bottom_right]))
j += 1
i += 1
return features所述image_shape參數是以下形式的元組(height, width)。其餘算法將循環遍歷圖像中的所有矩形，並檢查是否有可能使用該特徵。我們對特徵的表示是一個包含兩個數組的元組。第一個數組是對特徵有正面貢獻的RectangleRegions，第二個數組是對特徵有負面貢獻的RectangleRegions。這種表示形式使我們以後可以輕鬆保存分類器。
應用功能
當我們找到最佳弱分類器以在算法中稍後使用時，將需要評估每個訓練示例的每個特徵。為了節省計算量，我們將在開始訓練分類器之前執行此操作。這是更有效的方法，因為每次我們選擇一個新的分類器時，都需要對其進行重新訓練。如果我們將特徵應用於訓練循環中的訓練示例，我們將重複進行工作，因為圖像的每個特徵的值永遠不會改變。在訓練之前應用功能也將使我們能夠在以後預選功能，以加快訓練速度。保留每個訓練示例標籤的單獨數組將簡化我們的代碼，因此我們也將在此步驟中創建該數組。將apply_features方法添加到ViolaJones類。
def apply_features(self, features, training_data):
X = np.zeros((len(features), len(training_data)))
y = np.array(map(lambda data: data[1], training_data))
i = 0
for positive_regions, negative_regions in features:
feature = lambda ii: sum([pos.compute_feature(ii) for pos in positive_regions]) - sum([neg.compute_feature(ii) for neg in negative_regions])
X[i] = list(map(lambda data: feature(data[0]), training_data))
i += 1
return X, y該train方法現在應如下所示
def train(self, training, pos_num, neg_num):
weights = np.zeros(len(training))
training_data = []
for x in range(len(training)):
training_data.append((integral_image(training[x][0]), training[x][1]))
if training[x][1] == 1:
weights[x] = 1.0 / (2 * pos_num)
else:
weights[x] = 1.0 / (2 * neg_num) features = self.build_features(training_data[0][0].shape)
X, y = self.apply_features(features, training_data)弱分類器
我們終於有了所有的內容來開始構建和訓練弱分類器。回想一下，Viola-Jones使用一系列弱分類器並將它們的結果加權在一起以產生最終分類。每個弱分類器都是“弱”分類器，因為它本身不能準確地完成分類任務。每個弱分類器都查看單個特徵（f）。它具有閾值（θ）和極性（p）來確定訓練示例的分類。
極性可以是-1或1。當p = 1時，當f（x）<θ或特徵值小於 threshold 時，弱分類器輸出正結果。當p = -1時，當f（x）>θ時，弱分類器輸出正結果。現在，讓我們定義一個類來封裝弱分類器功能。
class WeakClassifier:
def __init__(self, positive_regions, negative_regions, threshold, polarity):
self.positive_regions = positive_regions
self.negative_regions = negative_regions
self.threshold = threshold
self.polarity = polaritydef classify(self, x):
feature = lambda ii: sum([pos.compute_feature(ii) for pos in self.positive_regions]) - sum([neg.compute_feature(ii) for neg in self.negative_regions])
return 1 if self.polarity * feature(x) < self.polarity * self.threshold else 0注意，每個特徵是正矩形區域的總和，從中減去負矩形區域的總和。回想一下，算法的下一步是選擇最佳的弱分類器。為此，我們需要找到每個 threshold 的最佳 threshold 和極性(polarity)。
訓練弱分類器
訓練弱分類器是該算法中計算量最大的部分，因為每次選擇新的弱分類器作為最佳分類器時，由於訓練示例的權重不同，因此必須重新訓練所有分類器。但是，存在一種使用權重為單個弱分類器找到最佳閾值和極性的有效方法。首先，根據權重對應的特徵值對權重進行排序。現在，遍歷權重數組，如果選擇閾值作為該特徵，則計算誤差。找到誤差最小的閾值和極性。閾值的可能值是每個訓練示例上特徵的值。誤差可以通過
T表示權重的總和，S表示到目前為止所看到的所有示例的權重之和。上標“ +”和“-”表示總和屬於哪一類。從概念上講，此錯誤比較瞭如果將當前位置以下的所有示例都標記為否，則有多少示例將被錯誤分類；如果將當前位置下方的所有示例都標記為正，則將有多少示例將被錯誤分類（考慮到每個示例的加權方式） 。
這樣，我們可以評估恆定時間（O（1））中每個可能閾值的誤差和線性時間（O（n））中所有閾值的誤差。閾值設置為誤差最小的特徵值。極性由位於閾值左側（小於）和右側（大於）的正例和負例數確定。如果閾值還剩下更多正面示例，則p = 1。否則，p = -1。這就是我剛剛在代碼中描述的內容（ViolaJones類的一部分）。此方法將訓練所有弱分類器，並將它們返回到數組中。
def train_weak(self, X, y, features, weights):
total_pos, total_neg = 0, 0
for w, label in zip(weights, y):
if label == 1:
total_pos += w
else:
total_neg += w classifiers = []
total_features = X.shape[0]
for index, feature in enumerate(X):
if len(classifiers) % 1000 == 0 and len(classifiers) != 0:
print("Trained %d classifiers out of %d" % (len(classifiers), total_features))
applied_feature = sorted(zip(weights, feature, y), key=lambda x: x[1])
pos_seen, neg_seen = 0, 0
pos_weights, neg_weights = 0, 0
min_error, best_feature, best_threshold, best_polarity = float('inf'), None, None, None
for w, f, label in applied_feature:
error = min(neg_weights + total_pos - pos_weights, pos_weights + total_neg - neg_weights)
if error < min_error:
min_error = error
best_feature = features[index]
best_threshold = f
best_polarity = 1 if pos_seen > neg_seen else -1
if label == 1:
pos_seen += 1
pos_weights += w
else:
neg_seen += 1
neg_weights += w
clf = WeakClassifier(best_feature[0], best_feature[1], best_threshold, best_polarity)
classifiers.append(clf)
return classifiers選擇最佳弱分類器
訓練完所有弱分類器後，我們現在可以找到最佳分類器。這就像遍歷所有分類器併計算每個分類器的平均加權誤差一樣簡單。將select_best方法添加到ViolaJones類
def select_best(self, classifiers, weights, training_data):
best_clf, best_error, best_accuracy = None, float('inf'), None
for clf in classifiers:
error, accuracy = 0, []
for data, w in zip(training_data, weights):
correctness = abs(clf.classify(data[0]) - data[1])
accuracy.append(correctness)
error += w * correctness
error = error / len(training_data)
if error < best_error:
best_clf, best_error, best_accuracy = clf, error, accuracy
return best_clf, best_error, best_accuracy請注意，我們返回了訓練數據的原始表示形式（元組數組）。這是因為我們需要積分圖像傳遞給弱分類器，而不是要素的值。另外，請注意，我們一直在跟踪準確性。這將在下一步算法中更新權重時發揮作用。總之，train_weak和select_best彌補我之前提到的高級算法的第三步。更新train以使用這兩種方法。
def train(self, training, pos_num, neg_num):
...
for t in range(self.T):
weak_classifiers = self.train_weak(X, y, features, weights)
clf, error, accuracy = self.select_best(weak_classifiers, weights, training_data)這些函數屬於循環，因為最佳弱分類器取決於每個訓練示例的權重，並且請記住，在選擇每個新的弱分類器之後，每個訓練示例的權重都會變化。
更新權重
Viola-Jones的大部分工作都用於構建功能，訓練分類器以及在每次迭代中選擇最佳的弱分類器。其餘的火車方法相對簡單。在選擇最佳分類器之前，我們應該對權重進行歸一化。選擇最佳弱分類器後，我們必須使用所選弱分類器的誤差來更新權重。正確分類的訓練樣本權重較小，錯誤分類的樣本權重不變。
Epsilon代表最佳分類器的誤差，w是第i個示例的權重（weight），而beta是更改權重的原因。beta的指數為1-e，如果正確分類了訓練示例，則e為0；如果分類不正確，則e為1（這就是為什麼我們在選擇最佳弱分類器時返回精度數組的原因）。
def train（self，training，pos_num，neg_num）：
...
對於範圍（self.T）中的t：
權重=權重/ np.linalg.norm（權重）
weak_classifiers = self.train_weak（X，y，特徵，權重）
clf，誤差，準確性= self.select_best（弱分類器，權重，訓練數據）
beta =誤差/（1.0- 誤差）
對於範圍（len（accuracy））中的
i ：weights [i] = weights [i] *（beta * *（1-精度[i]）強分類器
最後，我們必須從弱分類器中編譯強分類器。強分類器定義為
係數α是每個弱分類器在最終決策中所佔的權重，它取決於誤差，因為它是β倒數的自然對數。將弱分類器決策的加權總和與alpha值總和的一半進行比較，因為這類似於說“至少一半的弱分類器同意肯定的分類。”
我們需要存儲所有分類器及其對應的Alpha，因此請將兩個新的實例變量添加到init方法中。
def __init __（self，T = 10）：
self.T = T
self.alphas = []
self.clfs = []接下來，更新訓練方法的循環以計算Alpha並存儲它們以及分類器
def train(self, training, pos_num, neg_num):
...
for t in range(self.T):
weights = weights / np.linalg.norm(weights)
weak_classifiers = self.train_weak(X, y, features, weights)
clf, error, accuracy = self.select_best(weak_classifiers, weights, training_data)
beta = error / (1.0 - error)
for i in range(len(accuracy)):
weights[i] = weights[i] * (beta ** (1 - accuracy[i]))
alpha = math.log(1.0/beta)
self.alphas.append(alpha)
self.clfs.append(clf)最終的訓練方法如下所示
def train(self, training, pos_num, neg_num):
weights = np.zeros(len(training))
training_data = []
for x in range(len(training)):
training_data.append((integral_image(training[x][0]), training[x][1]))
if training[x][1] == 1:
weights[x] = 1.0 / (2 * pos_num)
else:
weights[x] = 1.0 / (2 * neg_num) features = self.build_features(training_data[0][0].shape)
X, y = self.apply_features(features, training_data)
for t in range(self.T):
weights = weights / np.linalg.norm(weights)
weak_classifiers = self.train_weak(X, y, features, weights)
clf, error, accuracy = self.select_best(weak_classifiers, weights, training_data)
beta = error / (1.0 - error)
for i in range(len(accuracy)):
weights[i] = weights[i] * (beta ** (1 - accuracy[i]))
alpha = math.log(1.0/beta)
self.alphas.append(alpha)
self.clfs.append(clf)確保添加import math到文件頂部。最後，實現強分類器的分類方法。
def classify(self, image):
total = 0
ii = integral_image(image)
for alpha, clf in zip(self.alphas, self.clfs):
total += alpha * clf.classify(ii)
return 1 if total >= 0.5 * sum(self.alphas) else 0改善
功能的數量以驚人的速度增長。對於24x24的圖像，有超過160,000個功能，而對於28x28的圖像，則有超過250,000。此外，這些功能中的許多功能都無法提供太多的分類功能，並且幾乎沒有用。刪除盡可能多的功能將很有用，因此我們可以訓練更少的WeakClassifier。幸運的是，SciKit-Learn軟件包可以通過其SelectPercentile類幫助我們縮小功能空間。要利用此優勢，請將以下內容添加到train方法中並導入所需的類。
from sklearn.feature_selection import SelectPercentile, f_classif
def train(self, training_data, pos_num, neg_num):
...
X, y = self.apply_features(features, training_data)
indices = SelectPercentile(f_classif, percentile=10).fit(X.T, y).get_support(indices=True)
X = X[indices]
features = features[indices]
...擬合SelectPercentile類將找到最佳的k％特徵（我在這裡選擇10％）。get_support然後，該方法返回那些特徵的索引。在擬合SelectPercentile時，請注意，傳入的XT不僅僅是X。這是因為SelectPercentile希望每一行都是一個訓練示例，而每一列都希望是特徵值，但是X數組已對此進行了切換。
保存和加載
由於ViolaJones需要花費很長時間進行訓練，因此能夠從文件中保存和加載模型將非常有用。使用 Pickle Model 很容易。將以下內容添加到ViolaJones類
def save(self, filename):
with open(filename+".pkl", 'wb') as f:
pickle.dump(self, f)@staticmethod
def load(filename):
with open(filename+".pkl", 'rb') as f:
return pickle.load(f)測試中
ViolaJones是為人臉偵測（Face Detection）任務創建的，因此有什麼更好的方法可以在同一任務上測試我們的代碼。麻省理工學院的生物與計算學習中心創建的CBCL人臉數據庫就是一個很好的測試數據。數據集包含訓練集，其中包含2000多個面部圖像和4500多個非面部圖像。每個圖像均為19x19灰度。原始數據集的每個圖像都是.pgm格式，因此我創建了兩個Pickle文件，一個用於訓練，一個用於測試，這使我們可以將它們直接加載到ViolaJones類中。你可以下載他們在這裡 GitHub上。
def train(t):
with open("training.pkl", 'rb') as f:
training = pickle.load(f)
clf = ViolaJones(T=t)
clf.train(training, 2429, 4548)
evaluate(clf, training)
clf.save(str(t))def test(filename):
with open("test.pkl", 'rb') as f:
test = pickle.load(f)
clf = ViolaJones.load(filename)
evaluate(clf, test)def evaluate(clf, data):
correct = 0
for x, y in data:
correct += 1 if clf.classify(x) == y else 0
print("Classified %d out of %d test examples" % (correct, len(data)))train(10)
test("10")在T = 10的情況下，該算法花了一個小時來訓練，並且在訓練集上獲得了85.5％的準確度，在測試集上獲得了78％的準確度。在T = 50的情況下，該算法花了五個小時進行訓練，並且在訓練和測試集上均獲得了93％的準確性。
結束語
Viola-Jones實施了對機器學習和人工智能很重要的幾個概念。首先，這是一種合奏方法。其次，它利用Adaboost算法的一種變體進行特徵選擇。這些特性使它成為過去使用並繼續使用的強大的圖像分類方法。原始論文還介紹了“注意級聯”的思想，以大大減少否定示例的分類時間。在本教程的第二部分中了解有關此內容的更多信息。
希望本教程對Viola-Jones算法有一個很好的了解。您可以在此處查看所有代碼。謝謝閱讀！
