格雷碼編碼+解碼+實現(Python)
作者:曹博
原文:
格雷碼編碼+解碼+實現(Python)
01 二值碼
02 格雷碼編碼
2。1 編碼優點
2。2 編碼生成
2。3 遞迴生成
2。4 二值碼轉換
2。5 編碼圖
03 格雷碼投影
3。1 投影圖案生成
3。2 DLP投影影象
04 格雷碼解碼
4。1 全域性/區域性灰度閾值法
4。2 多幅影象閾值法
4。3 特殊情況
05 參考文獻
01 二值碼
先來說結構光中最簡單的情況,時域上的編碼,由於極線約束的關係,我們只需要在單方向上進行編碼即可,我們以最簡單的兩灰度級三位二進位制碼為例,這裡有個區域,其中
亮區域
對應編碼1,
暗區域
對應編碼0,假設現在我們向被測物順序投射三幅二進位制編碼圖案,如下所示:
圖1 二進位制碼的編碼與解碼原理
現在,對於這些區域,對應的編碼如下:
這些區域都被我們編碼起來了,沒毛病!但是這樣的編碼雖然很簡單,但是存在問題!如果和格雷碼一比,你一定一眼就可以發現。
02 格雷碼編碼
2.1 編碼優點
二進位制編碼缺點:相鄰區域的編碼的位數變化太多了!
那這會帶來什麼問題?當然,在相機拍照清晰的情況下,這種編碼方式當然不會出現任何問題。但問題就出現在,
相機拍攝到的黑白相間的邊界點往往是一個過渡灰度,很容易導致解碼錯誤(0->1 or 1->0)
,這是自然二進位制編碼解碼最容易出錯的點。而
格雷碼最大的特定是相鄰數字編碼只相差一位
,它們的對比如下所示:
這有什麼優點呢?格雷碼出錯的機率更小,因為相鄰區域的編碼只有一位差異,有兩種情況,假設編碼只有一位差異,這一位錯誤編碼出現在:
非差異位
:對這類編碼錯誤,我們完全可以進行補救,因為相鄰兩個畫素的編碼應該是大部分相同的,我們可以對相鄰兩個畫素的編碼進行糾正,而二進位制碼可沒有這個編碼糾正機制;
差異位
:那無非是差一個畫素而已,這時候我們無法區分這兩塊區域;
舉個例子,對001(1)區域,它最容易出現錯誤的區域是黑白相間的邊界處,錯誤的編碼:011:
二值碼:3區域,差2個畫素;
格雷碼:2區域,差1個畫素,
另外,在編碼的最後一幅影象裡,條紋都是非常細的,以上面3位編碼為例,檢視編碼最後位,如果是:
二值碼:01010101
格雷碼:01100110
由於漫反射的原因,通常容易出錯的地方是黑白交錯的區域解碼,當條紋在最後一幅很細的時候,明顯格雷碼編碼條紋更粗,可能出錯的地方更少。
不論你是否理解,格雷碼的主要優點就在於可以減小解碼過程中的錯誤率,當然它依然有二值碼一樣的缺點,主要在於在選取位數較多的時候,最後幾幅圖的格雷碼條紋會非常細,不容易分辨,因而我們通常只選取4位格雷碼進行編碼。這樣的處理精度並不高,這也是後面我們結合相移法來進行編碼、解碼的主要原因。
補充:格雷碼的其他應用
格雷碼在傳統二進位制控制系統中也有廣泛應用,例如數字3的表示法為011,要切換為鄰近的數字4,也就是 100時,裝置中的三個位元都得要轉換,因此於未完全轉換的過程時裝置會經歷短暫的,010、001、101、110、111等其中數種狀態,也就是代表著2、1、5、6、7,因此此種數字編碼方法於鄰近數字轉換時有比較大的誤差可能範圍。但這樣的轉換,對於一些追求硬體效能極限的嵌入式應用,比如說飛機的電傳系統中,這樣的翻轉來不及轉換很正常!這就很尷尬!相反,格雷碼只需要一位翻轉即可!
2.2 編碼生成
改變最右邊的為值;
改變右邊第一個為1的位元,其左邊位元值;
重複1、2步;
來解釋下,以3位格雷碼為例,從原始的值 0(000):
步驟1,改變最右邊值:001
步驟2,改變右邊第一個為1的位元,其左邊的位元:011
步驟1,改變最右邊值:010
步驟2,改變右邊第一個為1的位元,其左邊的位元:110
步驟1,改變最右邊值:111
步驟2,改變右邊第一個為1的位元,其左邊的位元:101
如果按照這個步驟來生成格雷碼,對計算機來說,每次要去找右邊第一個1,然後去翻轉,其實是很麻煩的,而且這裡其實有些操作是冗餘的。
2.3 遞迴生成
我們來看格雷碼其它的特點:
除了最高位(左邊第一位),格雷碼的位元完全對稱
第一個00,和最後個00;
第二個01,和最後個01;
…
而最高位的規律就更容易了,前面的格雷碼為0,後面的為1
所以,格雷碼的生成步驟:
產生0,1兩個字串;0、1
在第一步基礎上:
每個字串前都+0->0+0、0+1
翻轉首個元素,其餘對稱:1+1、1+0
最終:00、01、11、10
在上一步基礎上:
每個字串前都+0->0+00、0+01、0+11、0+10
翻轉首字元,其餘對稱:1+10、1+11、1+01、1+00
最終:000、001、011、010、110、111、101、100
之後遞迴即可!我們用C++程式碼來實現一下,採用遞迴的形式:
/*==================================================
@Project:GrayCode
@File : main
@Desc :生成格雷碼
——————————————————————————
@Author :Jianbin Cao
@Email : fly_cjb@163。com
@Date :2020/11/10 20:40
==================================================*/
#include
#include
#include
using namespace std;
vector
if (n < 1) {
cout << “格雷碼數量必須大於0” << endl;
assert(0);
} else if (n == 1) {
vector
code。emplace_back(“0”);
code。emplace_back(“1”);
return code;
} else {
vector
vector
for (int idx = 0; idx < code_pre。size(); ++idx) {
code。push_back(“0” + code_pre[idx]);
}
for (int idx = int(code_pre。size() - 1); idx >= 0; ——idx) {
code。push_back(“1” + code_pre[idx]);
}
return code;
}
}
int main()
{
int n = 4;
vector
for (auto &g : gray_code){
cout << g << endl;
}
}
2.4 二值碼轉換
三步:
最高位保留
格雷碼的次高位:二進位制碼最高位與次高位的亦或操作;
其餘位的格雷碼依次類推
vector
int count = 1 << n;
vector
for(int i = 1 ; i < count; i ++)
{
int bin = i,cur = bin >> (n - 1);
for(int k = n - 1;k > 0;k ——)
cur = (cur << 1) + (((bin >> k) & 1) ^ ((bin >>(k - 1)) & 1));
res[i] = cur;
}
return res;
}
vector
for (auto &g : gray_code2){
cout << (bitset
}
2.5 編碼圖
圖2 相移+格雷碼編碼圖(檢視格雷碼部分)[3]
注:
03 格雷碼投影
3.1 投影圖案生成
結合格雷碼生成和編碼圖,這段程式碼就很好寫了,我們來寫一下,這回我們用Python來寫(人生苦短!):
import cv2
import numpy as np
class GrayCode:
codes = np。array([])
k2code = {}
k2v = {}
v2k = {}
def __init__(self, n:int=3):
self。n = n
self。codes = self。__creatCode(self。n)
# 從k(idx)轉換到格雷碼
for k in range(2**n):
self。k2code[k] = self。__k2code(k)
# 從格雷碼轉換到v
for k in range(2 ** n):
self。k2v[k] = self。__k2v(k)
# 從v轉換到k(idx)
for k, v in self。k2v。items():
self。v2k[v] = k
def toPattern(self, idx:int, cols:int = 1280, rows:int = 800):
assert (idx >= 0)
row = self。codes[idx, :]
one_row = np。zeros([cols], np。uint8)
assert (cols % len(row) == 0)
per_col = int(cols / len(row))
for i in range(len(row)):
one_row[i * per_col : (i + 1) * per_col] = row[i]
pattern = np。tile(one_row, (rows, 1)) * 255
return pattern
def __creatCode(self, n:int):
code_temp = GrayCode。__createGrayCode(n)
codes = []
for row in range(len(code_temp[0])):
c = []
for idx in range(len(code_temp)):
c。append(int(code_temp[idx][row]))
codes。append(c)
return np。array(codes, np。uint8)
def __k2code(self, k):
col = self。codes[:, k]
code = “”
for i in col:
code += str(i)
return code
def __k2v(self, k):
col = list(self。codes[:, k])
col = [str(i) for i in col]
code = “”。join(col)
return int(code, 2)
@staticmethod
def __createGrayCode(n:int):
if n < 1:
print(“輸入數字必須大於0”)
assert (0);
elif n == 1:
code = [“0”, “1”]
return code
else:
code = []
code_pre = GrayCode。__createGrayCode(n - 1)
for idx in range(len(code_pre)):
code。append(“0” + code_pre[idx])
for idx in range(len(code_pre) - 1, -1, -1):
code。append(“1” + code_pre[idx])
return code
if __name__ == ‘__main__’:
n = 8
g = GrayCode(n)
print(“code”)
print(g。codes)
print(“\nk -> code”)
print(g。k2code)
print(“\nk -> v”)
print(g。k2v)
print(“\nv -> k”)
print(g。v2k)
for i in range(n):
pattern = g。toPattern(i)
title = str(i) + “-img”
cv2。imshow(title, pattern)
cv2。waitKey(0)
cv2。destroyWindow(title)
3.2 DLP投影影象
參考連結:DLP LightCrafter4500投影影象步驟整理(一)
04 格雷碼解碼
格雷碼的解碼很簡單,只需要把投影的結構光還原回十進位制數字,我們就能知道相機中畫素點 對應於投影圖片的哪一列。但現在問題的關鍵是,我們相機捕獲回來的編碼圖案,
由於物體材料表面反光等因素,可能暗的地方不是那麼暗,亮的地方不是那麼亮,
這將會給正確解碼工作帶來一定難度!換句話說,如何對相機捕獲到的結構光進行
準確的二值化操作
?
4.1 全域性/區域性灰度閾值法
最簡單的方法是設定一個全域性灰度閾值,對於灰度值:高於閾值的畫素點:1、低於閾值的畫素點:0。或者利用區域性自適應閾值對圖片進行二值化操作,比如:
利用每個畫素點周邊的灰度資訊進行二值化
,但這類方法,由於使用結構光的環境往往是複雜的,比如說,
同樣的結構光,打在黑色物體表面的亮度,它就會比白色物體表面的亮度要低
,這意味著同樣的光條紋在不同物體上獲取的灰度值不同,所以往往不能夠滿足格雷碼解碼的二值化需求!舉個例子,光部分打在高反射區域(亮度高),部分打在漫反射區域(亮度暗),這類區域性自適應閾值法就不能很好適應這種場景。
4.2 多幅影象閾值法
雖然由於環境光、以及物體表面材料原因,一副影象中畫素的灰度值通常是不均勻的,我們無法直接利用一張影象中呈現的灰度資訊對結構光進行解碼,但是我們可以利用結構光一連串圖片來幫助獲取畫素點當前是亮條紋還是暗條紋。
以5位的格雷碼為例,其需要投影5張結構光圖案:
圖3 五位格雷碼投影圖案
假設有一個編碼為11011的格雷碼條紋打在物體表面上,在連續投影的5張格雷碼圖案中,物體表面被編碼照射區域,其既經歷暗條紋(編碼0),又經歷亮條紋(1),下面這條結論式確定無疑的:
對於同一位置,其被亮條紋照射到的亮度總是高於其被暗條紋照射的亮度!
那麼對於一個畫素點在一張圖片中的二值化,我們可以這樣操作:首先,找到畫素點在一連串格雷碼圖片中的最大灰度值,記為,最小灰度值,記為 ,對於每張影象,我們計算下面這個值:
圖4 格雷碼全暗/全亮區域[3]
因為這些點不會經歷明暗變化,所以你真的不好判斷是亮條紋還是暗條紋。我們有很多辦法去避免這個現象,比如說:
避開這個編碼(避開了意味著要多編碼)
跟其他畫素點亮度做比較(但是正如之前所說,由於物體表面材料屬性不同,這個方法缺乏魯棒性)
其中,有一種魯棒性比較好的解決方法是,額外讓所有編碼編碼位置都能經歷全0或者全1的過程,這也是傳統格雷碼結合相移技術需要額外投射兩幅全黑和全白圖案的原因,如圖4所示。
另外一個方法,我們額外投射一條更細的編碼,如圖5所示,互補格雷碼結合相移。當然,實際情況當然不是不簡單的多投射一條更細的格雷碼這麼簡單,但總的來說,我們總歸是有辦法解決的。
圖5 互補格雷碼結合相移的編碼圖 [3]
4.3 特殊情況
但上述方法奏效的前提是,假設被亮條紋照射到的亮度總是高於該位置被暗條紋照射到的亮度。但滿足這個條件的前提是:
物體間沒有漫反射,以及投影投射的光之間不會發生互相干擾
,這在大多數情況下是成立的。但是有一些特殊的位置,有可能
物體表面在亮條紋時,其亮度反而比經歷暗條紋時要暗
!對於這類問題,可以參考論文[1]來解決!
05 參考文獻
[1]: Robust Pixel Classification for 3D Modeling with Structured Light
[2]: High-accuracy, high-speed 3D structured light imaging techniques and potential applications to intelligent robotics
[3]: 第十三公開課:基於格雷碼結合相移技術的高魯棒性高效率動態三維面形測量,四川大學,吳周杰
[4]: 系列篇|結構光——格雷碼解碼方法,書涵