[導(dǎo)讀]SET 是一種游戲，玩家在指定的時間競相識別出十二張獨特紙牌中的三張紙牌（或 SET）的模式。每張 SET 卡都有四個屬性：形狀、陰影/填充、顏色和計數(shù)。下面是一個帶有一些卡片描述的十二張卡片布局示例。帶有一些卡片描述的標(biāo)準(zhǔn)十二張卡片布局請注意，卡片的四個屬性中的每一個都可以通過三個變體之一來表達(dá)。因為沒有兩張牌是重復(fù)的，所以一副套牌包含 3? = 81 張牌（每個屬性 3 個變體，4 個屬性）。一個有效的 SET 由三張卡片組成，對于四個屬性中的每一個，要么全部共享相同的變量，要么都具有不同的變量。為了直觀地演示，以下是三個有效 SET 示例：(1) 形狀：全部不同 (2) 陰影：全部不同 (3) 顏色：全部不同 (4) 計數(shù)：全部相同(1) 形狀：全部不同 (2) 陰影：全部相同 (3) 顏色：全部不同 (4) 計數(shù)：全部相同(1) 形狀：全部相同 (2) 陰影：全部不同 (3) 顏色：全部相同 (4) 計數(shù)：全部不同構(gòu)建一個 SET 求解器：一個計算機程序，該程序獲取 SET 卡的圖像并返回所有有效的 SET，我們使用 OpenCV（一個開源計算機視覺庫）和 Python。為了使自己?熟悉，我們可以瀏覽圖書館的文檔并和觀看一系列教程。

SET 是一種游戲，玩家在指定的時間競相識別出十二張獨特紙牌中的三張紙牌（或 SET）的模式。每張 SET 卡都有四個屬性：形狀、陰影/填充、顏色和計數(shù)。下面是一個帶有一些卡片描述的十二張卡片布局示例。帶有一些卡片描述的標(biāo)準(zhǔn)十二張卡片布局請注意，卡片的四個屬性中的每一個都可以通過三個變體之一來表達(dá)。因為沒有兩張牌是重復(fù)的，所以一副套牌包含 3? = 81 張牌（每個屬性 3 個變體，4 個屬性）。一個有效的 SET 由三張卡片組成，對于四個屬性中的每一個，要么全部共享相同的變量，要么都具有不同的變量。為了直觀地演示，以下是三個有效 SET 示例：(1) 形狀：全部不同 (2) 陰影：全部不同 (3) 顏色：全部不同 (4) 計數(shù)：全部相同(1) 形狀：全部不同 (2) 陰影：全部相同 (3) 顏色：全部不同 (4) 計數(shù)：全部相同(1) 形狀：全部相同 (2) 陰影：全部不同 (3) 顏色：全部相同 (4) 計數(shù)：全部不同構(gòu)建一個 SET 求解器：一個計算機程序，該程序獲取 SET 卡的圖像并返回所有有效的 SET，我們使用 OpenCV（一個開源計算機視覺庫）和 Python。為了使自己熟悉，我們可以瀏覽圖書館的文檔并和觀看一系列教程。此外，我們還可以閱讀一些類似項目的博客文章和 GitHub 存儲庫。我們將項目分解為四項任務(wù)：

在輸入圖像中定位卡片 (CardExtractor.py)

識別每張卡片的唯一屬性 (Card.py)

評估已識別的 SET 卡 (SetEvaluator.py)

向用戶顯示 SET (set_utils.display_sets)

我們?yōu)榍叭齻€任務(wù)中的每一個創(chuàng)建了一個專用類，我們可以在下面的類型提示 main 方法中看到。

import cv2
# main method takes path to input image of cards and displays SETs
def main():
input_image = 'PATH_TO_IMAGE'
original_image = cv2.imread(input_image)
extractor: CardExtractor = CardExtractor(original_image)
cards: List[Card] = extractor.get_cards()
evaluator: SetEvaluator = SetEvaluator(cards)
sets: List[List[Card]] = evaluator.get_sets()
display_sets(sets, original_image)
cv2.destroyAllWindows()

在輸入圖像中定位卡片

1. 圖像預(yù)處理

在導(dǎo)入OpenCV和Numpy（開源數(shù)組和矩陣操作庫）之后，定位卡片的第一步是應(yīng)用圖像預(yù)處理技術(shù)來突出卡片的邊界。具體來說，這種方法涉及將圖像轉(zhuǎn)換為灰度，應(yīng)用高斯模糊并對圖像進行閾值處理。簡要地：

轉(zhuǎn)換為灰度可通過僅保留每個像素的強度或亮度（RGB 色彩通道的加權(quán)總和）來消除圖像的著色。
對圖像應(yīng)用高斯模糊會將每個像素的強度值轉(zhuǎn)換為該像素鄰域的加權(quán)平均值，權(quán)重由以當(dāng)前像素為中心的高斯分布確定。這樣可以消除噪聲并 “平滑” 圖像。經(jīng)過實驗后，我們決定高斯核大小設(shè)定 (3,3) 。
閾值化將灰度圖像轉(zhuǎn)換為二值圖像——一種新矩陣，其中每個像素具有兩個值（通常是黑色或白色）之一。為此，使用恒定值閾值來分割像素。因為我們預(yù)計輸入圖像具有不同的光照條件，所以我們使用 cv2.THRESH_OTSU 標(biāo)志來估計運行時的最佳閾值常數(shù)。

OpenCV 使這三個步驟變得很簡單：

# Convert input image to greyscale, blurs, and thresholds using Otsu's binarization
def preprocess_image(image):
greyscale_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blurred_image = cv2.GaussianBlur(greyscale_image, (3, 3), 0)
_, thresh = cv2.threshold(blurred_image, 0, 255, cv2.THRESH_OTSU)
return thresh 原始 → 灰度和模糊 → 閾

2. 查找卡片輪廓

接下來，我使用 OpenCV 的 findContours() 和 approxPolyDP() 方法來定位卡片。利用圖像的二進制值屬性，findContours() 方法可以找到 “ 連接所有具有相同顏色或強度的連續(xù)點（沿邊界）的曲線。”2 第一步是對預(yù)處理圖像使用以下函數(shù)調(diào)用：

contours, hierarchy = cv2.findContours(processed_image, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)

cv2.RETR_TREE 標(biāo)志檢索所有找到的輪廓以及描述給定輪廓嵌套或嵌入其他輪廓的級別的層次結(jié)構(gòu)。cv2.CHAIN_APPROX_SIMPLE 標(biāo)志僅通過編碼輪廓端點來壓縮輪廓信息。在進行了一些錯誤檢查以排除非卡片之后，我們使用approxPolyDP ()方法使用輪廓端點來估計多邊形曲線。以下是一些已識別的卡片輪廓，它們疊加在原始圖像上。輪廓以繪制為紅色

3. 重構(gòu)卡片圖像

識別輪廓后，必須重構(gòu)卡片的邊界以標(biāo)準(zhǔn)化原始圖像中卡片的角度和方向。這可以通過仿射扭曲變換來完成，仿射扭曲變換是一種幾何變換，可以保留圖像上線條之間的共線點和平行度。我們可以在示例圖像中看到下面的代碼片段。

# Performs an affine transformation and crop to a set of card vertices
def refactor_card(self, bounding_box, width, height):
bounding_box = cv2.UMat(np.array(bounding_box, dtype=np.float32))
frame = [[449, 449], [0, 449], [0, 0], [449, 0]]
if height > width:
frame = [[0, 0], [0, 449], [449, 449], [449, 0]]
affine_frame = np.array(frame, np.float32)
affine_transform = cv2.getPerspectiveTransform(bounding_box, affine_frame)
refactored_card = cv2.warpPerspective(self.original_image, affine_transform, (450, 450))
cropped_card = refactored_card[15:435, 15:435]
return cropped_card

仿射變換疊加在原始圖像上以展示標(biāo)準(zhǔn)化的角度和方向然后我們將每個重構(gòu)的卡片圖像及其坐標(biāo)作為參數(shù)傳遞給 Card 類構(gòu)造函數(shù)。這是構(gòu)造函數(shù)的簡化版本：

class Card:
def __init__(self, card_image, original_coord):
self.image = card_image
self.processed_image = self.process_card(card_image)
self.processed_contours = self.processed_contours()
self.original_coord = reorient_coordinates(original_coord) #standardize coordinate orientation
self.count = self.get_count()
self.shape = self.get_shape()
self.shade = self.get_shade()
self.color = self.get_color()

識別卡片屬性作為第一步，一種名為process_card的靜態(tài)方法應(yīng)用了上述相同的預(yù)處理技術(shù)，以及對重構(gòu)后的卡片圖像進行二進制膨脹和腐蝕。簡要說明和示例：

膨脹是其中像素 P 的值變成像素 P 的 “鄰域” 中最大像素的值的操作。腐蝕則相反：像素 P 的值變成像素 P 的 “鄰域” 中最小像素的值。
該鄰域的大小和形狀（或“內(nèi)核”）可以作為輸入傳遞給 OpenCV（默認(rèn)為 3x3 方陣）。
對于二值圖像，腐蝕和膨脹的組合（也稱為打開和關(guān)閉）用于通過消除落在相關(guān)像素 “范圍” 之外的任何像素來去除噪聲。在下面的例子中可以看到這一點。
#Close card image (dilate then erode)
dilated_card = cv2.dilate(binary_card, kernel=(x,x), iterations=y)
eroded_card = cv2.erode(dilated_card, kernel=(x,x), iterations=y)

帶有噪聲的卡片 → 預(yù)處理后的圖像 → 膨脹腐蝕的“閉合”圖像，注意噪聲消除我獲取了生成的圖像，并使用不同的方法從處理后的卡片中提取每個屬性——形狀、陰影、顏色和計數(shù)。我使用了 Github 上@piratefsh 的 set-solver 存儲庫中的代碼來識別卡片顏色和陰影，并設(shè)計了我自己的形狀和計數(shù)方法。

形狀

為了識別卡片上顯示的符號的形狀，我們使用卡片最大輪廓的面積。這種方法假設(shè)最大的輪廓是卡片上的一個符號——這一假設(shè)在排除非極端照明的情況下幾乎總是正確的。

陰影

識別卡片陰影或 “填充” 的方法使用卡片最大輪廓內(nèi)的像素密度。

顏色

識別卡片顏色的方法包括評估三個顏色通道 (RGB) 的值并比較它們的比率。

計數(shù)

為了識別卡片上的符號數(shù)量，我們首先找到了四個最大的輪廓。盡管實際上計數(shù)從未超過三個，但我們選擇了四個，然后進行了錯誤檢查以排除非符號。在使用 cv2.drawContours 填充輪廓后，為了避免重復(fù)計算后，我們需要檢查一下輪廓區(qū)域的值以及層次結(jié)構(gòu)（以確保輪廓沒有嵌入到另一個輪廓中）。

填充原始符號以確保沒有內(nèi)部邊界被視為輪廓。另外：識別卡片屬性的另一種方法可能是將有監(jiān)督的 ML 分類模型應(yīng)用于卡片圖像。根據(jù)一些快速研究，似乎可以使用 Scikit 的 SVM 或 KNN 和 Keras ImageDataGenerator 來增強數(shù)據(jù)集。然后每個變體都被編碼為一個整數(shù)，這樣任何卡片都可以用四個整數(shù)的數(shù)組表示。例如，帶有兩個空菱形符號的紫色卡片可以表示為 [1,1,3,2]。現(xiàn)在卡片表示為數(shù)組，讓我們評估一下 SET！評估 SET為了檢查已識別卡片中的集合，將卡片對象數(shù)組傳遞給 SetEvaluator 類。

方法一：所有可能的組合

至少有兩種方法可以評估卡的數(shù)組表示形式是否為有效集。第一種方法需要評估所有可能的三張牌組合。例如，當(dāng)顯示 12 張牌時，有 ??C? =(12!)/(9!)(3!) = 660 種可能的三張牌組合。使用 Python 的 itertools 模塊，可以按如下方式計算

import itertools SET_combinations = list(combinations(cards: List[Card], 3))

請記住，對于每個屬性，SET 中的三張卡片的變化必須相同或不同。如果三個卡片陣列彼此堆疊，則給定列/屬性中的所有值必須顯示全部相同的值或全部不同的值?？梢酝ㄟ^對該列中的所有值求和來檢查此特性。如果所有三張卡片對于該屬性具有相同的值，則根據(jù)定義，所得總和可被三整除。類似地，如果所有三個值都不同（即等于 1、2 和 3 的排列），則所得的總和 6 也可以被 3 整除。如果沒有余數(shù)，這些值的任何其他總和都不能被3整除。我們將這種方法應(yīng)用于所有 660 種組合，保存了有效的組合?？炜?，我們有了我們的 SET！下面是一個簡單演示此方法的代碼片段（在可能的情況下不使用生成器盡早返回 False）：

# Takes 3 card objects and returns Boolean: True if SET, False if not SET
@staticmethod
def is_set(trio):
count_sum = sum([card.count for card in trio])
shape_sum = sum([card.shape for card in trio])
shade_sum = sum([card.shade for card in trio])
color_sum = sum([card.color for card in trio])
set_values_mod3 = [count_sum % 3, shape_sum % 3, shade_sum % 3, color_sum % 3]
return set_values_mod3 == [0, 0, 0, 0]

但是有一個更好的方法......

方法 2：驗證 SET Key

請注意，對于一副牌中的任意兩張牌，只有一張牌（并且只有一張牌）可以完成 SET，我們稱這第三張卡為SET Key。方法 1 的一種更有效的替代方法是迭代地選擇兩張卡片，計算它們的 SET 密鑰，并檢查該密鑰是否出現(xiàn)在剩余的卡片中。在 Python 中檢查 Set() 結(jié)構(gòu)的成員資格的平均時間復(fù)雜度為 O (1)。這將算法的時間復(fù)雜度降低到 O( n2)，因為它減少了需要評估的組合數(shù)量?？紤]到只有少量 n 次輸入的事實（在游戲中有12 張牌在場的 SET 有 96.77% 的機會，15 張牌有 99.96% 的機會，16 張牌有 99.9996% 的機會?），效率并不是最重要的。使用第一種方法，我在我的中端筆記本電腦上對程序計時，發(fā)現(xiàn)它在我的測試輸入上平均運行 1.156 秒（渲染最終圖像）和 1.089 秒（不渲染）。在一個案例中，程序在 1.146 秒內(nèi)識別出七個獨立的集合。

向用戶顯示 SETS

最后，我們跟隨 piratefsh 和 Nicolas Hahn 的引導(dǎo)，通過在原始圖像上用獨特的顏色圈出各自 SET 的卡片，向用戶展示 SET。我們將每張卡片的原始坐標(biāo)列表存儲為一個實例變量，該變量用于繪制彩色輪廓。

# Takes List[List[Card]] and original image. Draws colored bounding boxes around sets.
def display_sets(sets, image, wait_key=True):
for index, set_ in enumerate(sets):
set_card_boxes = set_outline_colors.pop()
for card in set_:
card.boundary_count = 1
expanded_coordinates = np.array(expand_coordinates(card.original_coord, card.boundary_count), dtype=np.int64)
cv2.drawContours(image, [expanded_coordinates], 0, set_card_boxes, 20)

屬于多個 SET 的卡片需要多個輪廓。為了避免在彼此之上繪制輪廓，expanded_coordinates() 方法根據(jù)卡片出現(xiàn)的 SET 數(shù)量迭代擴展卡片的輪廓。這是使用 cv2.imshow() 的操作結(jié)果：就是這樣——一個使用 Python 和 OpenCV 的 SET 求解器！這個項目很好地介紹了 OpenCV 和計算機視覺基礎(chǔ)知識。特別是，我們了解到：

圖像處理、降噪和標(biāo)準(zhǔn)化技術(shù)，如高斯模糊、仿射變換和形態(tài)學(xué)運算。
Otsu 的自動二元閾值方法。
輪廓和 Canny 邊緣檢測。
OpenCV 庫及其一些用途。

引文和資源

Piratefsh’s set-solver on Github was particularly informative. After finding that her approach to color identification very accurate, I ended up simply copying the method. Arnab Nandi’s card game identification project was also a useful starting point, and Nicolas Hahn’s set-solver also proved useful. Thank you Sherr, Arnab, and Nicolas, if you are reading this!
Here’s a basic explanation of contours and how they work in OpenCV. I initially implement the program with Canny Edge Detection, but subsequently removed it because it did not improve card identification accuracy for test cases.
You can find a more detailed description of morphological transformations on the OpenCV site here.
Some interesting probabilities related to the game SET.