點(diǎn)擊上方“小白學(xué)視覺(jué)”，選擇加"星標(biāo)"或“置頂”

重磅干貨，第一時(shí)間送達(dá)

小伙伴們玩過(guò) SET 嗎？SET 是一種游戲，玩家在指定的時(shí)間競(jìng)相識(shí)別出十二張獨(dú)特紙牌中的三張紙牌（或 SET）的模式。每張 SET 卡都有四個(gè)屬性：形狀、陰影/填充、顏色和計(jì)數(shù)。下面是一個(gè)帶有一些卡片描述的十二張卡片布局示例。

請(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è)，要么全部共享相同的變量，要么都具有不同的變量。為了直觀地演示，以下是三個(gè)有效 SET 示例：

構(gòu)建一個(gè) SET 求解器：一個(gè)計(jì)算機(jī)程序，該程序獲取 SET 卡的圖像并返回所有有效的 SET，我們使用 OpenCV（一個(gè)開(kāi)源計(jì)算機(jī)視覺(jué)庫(kù)）和 Python。為了時(shí)自己熟悉，我們可以瀏覽圖書館的文檔并和觀看一系列教程。此外，我們還可以閱讀一些類似項(xiàng)目的博客文章和 GitHub 存儲(chǔ)庫(kù)。1?我們將項(xiàng)目分解為四項(xiàng)任務(wù)：

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

   
   

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

   
   

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

   
   

4. 向用戶顯示 SET (set_utils.display_sets)

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

import cv2
# main method takes path to input image of cards and displays SETsdef 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 binarizationdef 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)（沿邊界）的曲線。”2 第一步是對(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ì)多邊形曲線。以下是一些已識(shí)別的卡片輪廓，它們疊加在原始圖像上。

輪廓以繪制為紅色

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

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

# Performs an affine transformation and crop to a set of card verticesdef 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

然后我們將每個(gè)重構(gòu)的卡片圖像及其坐標(biāo)作為參數(shù)傳遞給 Card 類構(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()

作為第一步，一種名為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ì)于二值圖像，腐蝕和膨脹的組合（也稱為打開(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)

我獲取了生成的圖像，并使用不同的方法從處理后的卡片中提取每個(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è)輪廓中）。

另外：識(shí)別卡片屬性的另一種方法可能是將有監(jiān)督的 ML 分類模型應(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！

為了檢查已識(shí)別卡片中的集合，將卡片對(duì)象數(shù)組傳遞給 SetEvaluator 類。

方法一：所有可能的組合

至少有兩種方法可以評(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ù)定義，所得總和可被三整除。類似地，如果所有三個(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@staticmethoddef 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，我們稱這第三張卡為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ú)立的集合。

向用戶顯示 SETS

最后，我們跟隨 piratefsh 和 Nicolas Hahn 的引導(dǎo)，通過(guò)在原始圖像上用獨(dú)特的顏色圈出各自 SET 的卡片，向用戶展示 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ù)及其一些用途。

1. 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!

2. 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.

3. You can find a more detailed description of morphological transformations on the OpenCV site?here.

4. Some?interesting probabilities?related to the game SET.

交流群

歡迎加入公眾號(hào)讀者群一起和同行交流，目前有SLAM、三維視覺(jué)、傳感器、自動(dòng)駕駛、計(jì)算攝影、檢測(cè)、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競(jìng)賽等微信群（以后會(huì)逐漸細(xì)分），請(qǐng)掃描下面微信號(hào)加群，備注：”昵稱+學(xué)校/公司+研究方向“，例如：”張三?+?上海交大?+?視覺(jué)SLAM“。請(qǐng)按照格式備注，否則不予通過(guò)。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~