如何製作 QR Code #10：從照片中提取 QR Code
事先聲明，本篇文章的內容，為 Yeecy 在影像處理課程的期末專題中，最後得到的成果。在對 QR Code 有更多了解後，現在看來總覺當時的方法有些拙劣，不過我認為至少能提供個方向讓有興趣的讀者知道，自己也能從照片中辨識出 QR Code，並將其提取出來，希望讀者能從中受益。
獲取圖片
首先，我們要拍一張照片，舉下圖為例，可以注意到圖中的 QR Code 並非正立的，而是向左轉動了約 90 度。
灰階轉換
因為圖片的色彩對 QR Code 的提取沒有幫助（至少我這麼認為），所以先將其轉換成灰階。
二值化（binarization）
由於 QR Code 僅有黑白兩色，並不需要考慮非白色和黑色的剩餘顏色，我們使用灰階度切割（gray-level slicing），把比較黑的灰色變成黑色，把比較白的灰色變成白色，這個過程也可稱為二值化。
讀者可以使用其他方法來進行二值化，只要不會破壞 QR Code 的完整性，都是好方法。
邊緣提取
為了找到 QR Code 的三個定位圖案，我想了很久才想出了個能用但不實用的方法，這個方法的第一步要先進行邊緣提取。
Yeecy 使用索伯算子（Sobel operator）與二值化過的圖進行捲積，來取得只剩邊緣的圖片。
以上三張公式皆使用 latex2image 產生。
由於捲積運算與 QR Code 本身較無關係，Yeecy 在此附上自己用 Python 編寫的捲積函式，此函式僅接受二維矩陣配上二維的捲積核。
做完捲積後，我們可以得到只剩邊緣的圖片。
尋找封閉圖形
從上面的圖片可以發現，定位圖案包含了三個封閉的四邊形，第二步就是把所有的封閉圖形找出來。
由於之前自己寫過一個機器學習的演算法 DBSCAN，此處我使用相同的思路來實現尋找封閉圖形，不過這也是本文中最耗時的步驟，例如上圖需要耗費約五分鐘才能計算完所有封閉圖形，如果要優化的話，大概就是別用 Python 實現。
由於自己覺得變數命名沒命名的很好，改了又懶得測試結果正不正確，就不貼出程式碼來獻醜了。
找出定位圖案
找出所有封閉圖形後，計算每個封閉圖形的中心點，上面提到定位圖形包含三個封閉的四邊形，而且這三個四邊形相當相似，可以預期它們的中心點也會相當接近。
經過上面的推論，我們把尋找一個可能的定位圖案，轉變成為尋找一組擁有三個相當接近的中心點的封閉圖形。
當然，取決於先前處理步驟的程度，很有可能找不到三組或超過三組可能的定位圖案，如果找不到三組，那麼有可能是前面的處理步驟有些不妥，例如二值化的閾值選擇不恰當，如果找到三組以上，可以透過像是計算距離的方式，來排除一些不可能的存在。
不過有些時候也可能是圖片本身不好處理，像是 Yeecy 之前處理過一張投影在投影幕上的 QR Code 照片，那張照片不管使用哪個閾值來進行二值化，QR Code 都沒有辦法完整的呈現出來，可能會有一部分直接變白，或是一部分直接變黑，就算經過直方圖等化（histogram equalization），效果也沒好到哪裡去，這大概也是沒有手機能夠在現場辨識出 QR Code 的原因，只能說人眼真強大。
在找到吻合的中心點後，就可以反推出其最外圍的封閉圖案，下面畫出尋找到的中心點和包含該中心點的最外圍封閉圖案。
不難看出這三個正是我們想要的定位圖案，把它畫在原本的圖上可以看得更加清楚。
推斷 QR Code 的四個頂點
有了三個中心點和它們相應的定位圖案外圍，現在要來推斷 QR Code 的範圍了，因為 QR Code 原本是個正方形，所以只要知道四個頂點，就相當於得到 QR Code 的範圍了。
中心點關係
我們首先要知道三個點之間的關係，因為此時只知道三個點，並不知道哪個點代表 QR Code 的哪個定位圖案的中心。
為了找到三個點的關係，可以使用三角形的特性，也就是兩股必不長於斜邊，只要知道斜邊位置，就可以推斷出位於左上角的定位圖案中心點。
接下來要判斷哪個點位於右上，哪個點位於左下，如果搞混這兩個點的話，會導致最後提取出來的 QR Code 變成對於左上到右下的鏡像圖片，雖然鏡像可能不成問題，因為 iPhone 是能辨識出來的，不過還是追求正確比較好。
要判斷剩下的兩個點，大概就只能針對所有可能的排列情況，寫出相應的程式邏輯，Yeecy 想不到除去暴力判斷以外的方法。
推斷頂點
此處就用 Yeecy 當時報告的投影片來說明，相信讀者可以很容易看懂，需要提醒的是投影片中的圖片和本文使用的圖片是完全不一樣的。
至於為何要採用這樣的方法來得到三個頂點，理由很簡單，那就是人眼可以很輕鬆的看出頂點位置，但是電腦知道的只是一堆座標，除非讀者想用暴力判斷的方式來得到頂點，不然這個方法是萬用且無誤的。
推斷未知的第四點
上面說到知道四點就能知道 QR Code 的範圍，從上一步我們已經知道三個頂點了，現在要做的是估計第四點，同樣用 Yeecy 報告的投影片說明。
要想知道第四點，我們可以從解兩直線交點著手，因為兩點決定一線，所以要找出另外的兩點來找出兩線。上圖中的方法會在拍攝角度相當歪斜的時候失效，至於在如何的情況下會失效就留待讀者思考，Yeecy 只能說這個情況相當不符合正常人掃描 QR Code 的情況。
求出兩條直線後，計算這兩條直線的交點就是我們所要的第四點囉。
因為是拍照的關係，QR Code 並不一定會是個平行四邊形，所以不要天真的覺得 A+C = B+D 會恆成立喔。
回到本文的範例，經過上面的運算後，可以得到四個頂點的座標。
我們把這四個點放回原本的灰階圖看看。
看起來效果還不錯呢！
透視變換（perspective transformation）
這一部份牽涉到幾何學，Yeecy 因為懶得自己手刻，又剛好拿來讀圖片的函式庫提供了透視變換，所以我就不客氣的直接使用了。
進行透視變換需要使用者傳入四個頂點，必須注意到要傳入的可能是符合數學習慣的 (x, y)，也就是要傳入 (c, r)，而不是程式上習慣的 (r, c)，不然會像 Yeecy 除錯除半天，搞不懂到底哪裡有問題。
經過函式庫的處理後，QR Code 就被提取出來了。
不難發現這個 QR Code 有些歪斜，並且方格的邊邊有奇怪的突起，需要進一步的處理。
重新採樣（resampling）
現在我們要重新採樣上面提取出來的 QR Code，上面的一個碼元實際上是用許多像素（pixel）組合而成的，由於之前在編碼的時候，假設使用版本 1 且不包含靜默區域的 QR Code 時，我們實際處理的是一個 21×21 的二維陣列，而上圖計算一下可以知道是個 29×29 的 QR Code，但讀進電腦裡肯定不會只是 29×29 的二維陣列，要我猜，上圖應該也有個 400×400 吧。
估計碼元大小
在重新採樣之前，要先估計一個碼元的邊長大約是多少像素。
估計的方法有很多，Yeecy 自己就試了約莫六種，而前幾種都不是很理想，讀者也可以試試看自己想到的方法，很有趣的喔。
估計版本
有了碼元邊長所佔的像素估計值後，要做的是估計 QR Code 的版本，要先估計出版本，我們才能知道總共需要切出多少個碼元，基本上有了前面的工作，這個步驟是不難的。
開始採樣
接下來要做的事情有點像是畫網格，就如同下圖所示，不過實際操作不用真的畫出線條。
要如何決定網格又是另一個大學問了，不過基本思路是利用前面估計的碼元長度，每隔該長度就切一格，但是通常來說，只有在提取出來的 QR Code 不歪斜時才有用，至於要怎麼改進，就留待讀者細品箇中的奧妙了。
畫好格子後，我們要用一個顏色來代表每一格中包含的許多像素，Yeecy 是採用相對多數決，也就是只要哪個顏色的像素多，就用那個顏色來代表那一格。
到了這一步，我們就把 QR Code 從原先的照片中提取出來了，雖然採樣時所畫的網格好像不怎麼正確，導致左下的定位圖案都變形了，不過沒關係，因為解碼時也用不到它，至於其他部分如果有錯誤，我們還能透過錯誤校正碼來復原原始的訊息。
上圖經過 Yeecy 自己寫的解碼器處理後得到：
https://en.wikipedia.org/wiki/QR_code
讀者可以試著解碼，看結果跟上面寫是否一樣。
結語
根據我查到的資料，要達到實時偵測 QR Code，會使用到一些機器學習的方法，如維奧拉-瓊斯目標檢測框架，更甚者還會使用一些基於深度學習的目標檢測框架來達成，像是 YOLO，這些框架相當強大，不過實際上要怎麼運用，就留給有需要的讀者參考了。
感謝你的閱讀，我是 Yeecy，我們有緣再見。
