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

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

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

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

評(píng)估已識(shí)別的 SET 卡 (SetEvaluator.py)

向用戶(hù)顯示 SET (set_utils.display_sets)

我們?yōu)榍叭齻€(gè)任務(wù)中的每一個(gè)創(chuàng)建了一個(gè)專(zhuān)用類(lèi)，我們可以在下面的類(lèi)型提示 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（開(kāi)源數(shù)組和矩陣操作庫(kù)）之后，定位卡片的第一步是應(yīng)用圖像預(yù)處理技術(shù)來(lái)突出卡片的邊界。具體來(lái)說(shuō)，這種方法涉及將圖像轉(zhuǎn)換為灰度，應(yīng)用高斯模糊并對(duì)圖像進(jìn)行閾值處理。簡(jiǎn)要地：

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

OpenCV 使這三個(gè)步驟變得很簡(jiǎn)單：

# 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. 查找卡片輪廓

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

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

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

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

識(shí)別輪廓后，必須重構(gòu)卡片的邊界以標(biāo)準(zhǔn)化原始圖像中卡片的角度和方向。這可以通過(guò)仿射扭曲變換來(lái)完成，仿射扭曲變換是一種幾何變換，可以保留圖像上線(xiàn)條之間的共線(xiàn)點(diǎ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è)重構(gòu)的卡片圖像及其坐標(biāo)作為參數(shù)傳遞給 Card 類(lèi)構(gòu)造函數(shù)。這是構(gòu)造函數(shù)的簡(jiǎn)化版本：

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()

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

膨脹是其中像素 P 的值變成像素 P 的 “鄰域” 中最大像素的值的操作。腐蝕則相反：像素 P 的值變成像素 P 的 “鄰域” 中最小像素的值。
該鄰域的大小和形狀（或“內(nèi)核”）可以作為輸入傳遞給 OpenCV（默認(rèn)為 3x3 方陣）。
對(duì)于二值圖像，腐蝕和膨脹的組合（也稱(chēng)為打開(kāi)和關(guān)閉）用于通過(guò)消除落在相關(guān)像素 “范圍” 之外的任何像素來(lái)去除噪聲。在下面的例子中可以看到這一點(diǎ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ù)處理后的圖像 → 膨脹腐蝕的“閉合”圖像，注意噪聲消除我獲取了生成的圖像，并使用不同的方法從處理后的卡片中提取每個(gè)屬性——形狀、陰影、顏色和計(jì)數(shù)。我使用了 Github 上@piratefsh 的 set-solver 存儲(chǔ)庫(kù)中的代碼來(lái)識(shí)別卡片顏色和陰影，并設(shè)計(jì)了我自己的形狀和計(jì)數(shù)方法。

形狀

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

陰影

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

顏色

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

計(jì)數(shù)

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

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

方法一：所有可能的組合

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

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

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

但是有一個(gè)更好的方法......

方法 2：驗(yàn)證 SET Key

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

向用戶(hù)顯示 SETS

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

# 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)

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

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

引文和資源

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.