run-length 編碼和解碼

來自專欄 Algo. & Data

Contact me:

Blog : https://cugtyt.github.io/blog/index

Email: cugtyt#qq.com, cugtyt#http://gmail.com

本文的代碼來自於Run-Length Encode and Decode paulorzp。

這個run-length是一個數值只取0和1的二維矩陣，一般的用途是描述圖像的mask，比如：

看一下簡單的內容和圖像的對應：

這裡先貼出編碼和解碼的代碼，代碼來源：

def rle_encode(img): img: numpy array, 1 - mask, 0 - background Returns run length as string formated pixels = img.flatten() pixels = np.concatenate([[0], pixels, [0]]) runs = np.where(pixels[1:] != pixels[:-1])[0] + 1 runs[1::2] -= runs[::2] return .join(str(x) for x in runs) def rle_decode(mask_rle, shape): mask_rle: run-length as string formated (start length) shape: (height,width) of array to return Returns numpy array, 1 - mask, 0 - background s = mask_rle.split() starts, lengths = [np.asarray(x, dtype=int) for x in (s[0:][::2], s[1:][::2])] starts -= 1 ends = starts + lengths img = np.zeros(shape[0]*shape[1], dtype=np.uint8) for lo, hi in zip(starts, ends): img[lo:hi] = 1 return img.reshape(shape)

我們用上面的簡單例子來一步步分析編碼和解碼的過程：

編碼

• 定義mask：

mask = np.array([ [0, 1, 1, 0], [1, 1, 1, 1], [1, 0, 0, 1] ])

mask的圖像就是上方那個簡單的圖像。

• 扁平化

python mask.flatten()> array([0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1])

• 首尾加0

np.concatenate([[0], mask, [0]]) > array([0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0])

• 每個元素與前一個元素比較，找到不同的位置

runs = np.where(mask[1:] != mask[:-1])[0] + 1 > array([ 2, 4, 5, 10, 12, 13])

• 作差，找到所有連續1的起始位置和個數

runs[1::2] -= runs[::2] > array([ 2, 2, 5, 5, 12, 1])

至此，編碼就完成了。

code = .join(str(x) for x in runs)

注意到它這裡的起始位置是從1開始算的

解碼

• 從字元串中分割code成list

code = code.split() > [2, 2, 5, 5, 12, 1]

• 解出起始位置和個數

starts, lengths = [np.asarray(x, dtype=int) for x in (code[0:][::2], code[1:][::2])] > (array([ 2, 5, 12]), array([2, 5, 1]))

• 因為python本身是從0開始計算的，所以減1取真實的起始位置和終點位置

starts -= 1 ends = starts + lengths starts, ends > (array([ 1, 4, 11]), array([ 3, 9, 12]))

• 最後一步，恢復原數據

decode_mask = np.zeros(3*4, dtype=np.uint8) for lo, hi in zip(starts, ends): decode_mask[lo:hi] = 1 > array([0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1], dtype=uint8)

結果圖：

總結起來就是記錄所有連續1的起始位置和長度作為編碼，解碼依據這個記錄恢復就好。

推薦閱讀：