离散小波转换之影像压缩法 SPIHT

第十章

離散小波轉換之影像壓縮法

–SPIHT

(SetPartitioningInHierarchicalTrees)1Outlines介紹SPIHT影像壓縮程序2介紹SPIHT由Said與Pearlman學者提出(1996)一種離散小波影像壓縮方法，其壓縮效果比EZW還好一種位元平面(BitPlane)編碼法3SPIHT影像壓縮程序n: 離散小波較換結果中最大係數所佔的位元個數H: 存放DWT轉換結果中最重要係數的集合LSP: Significantpixels(重要點)串列LIP: Insignificantpixels(不重要點)串列LIS: 未處理係數的串列型A:包含此係數的子樹及係數本身的集合型B:包含此係數的子樹，但未包含係數本身的集合4Output:n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)LIS:LSP:SPIHT影像壓縮程序

(cont.)5Output:63–34–312310(+)11(-)00n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)

XXRRLIS:A(0,1)→A(1,0)→A(1,1)LSP:(0,0)(0,1)SPIHT影像壓縮程序

(cont.)6Output:63–34–3123A(0,1)491014–13

10(+)11(-)00110000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)

XXRRXRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)

XLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)7Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7

10(+)11(-)0011000010000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)XXRRXRRRRRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)

XXLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)8Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)

10(+)11(-)00110000100000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)XXRRXRRRRRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)XXRLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)9Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)0

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)XXRRXRRRRRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)XXRRLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)10Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)B(1,0)01

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)XXRRXRRRRRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)→A(2,0)→A(2,1)→A(3,0)→A(3,1)XXRRRLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)11Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)B(1,0)A(2,0)010

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)XXRRXRRRRRRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)→A(2,0)→A(2,1)→A(3,0)→A(3,1)XXRRRRLSP:(0,0)(0,1)(0,2)SPIHT影像壓縮程序

(cont.)12Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)B(1,0)A(2,0)A(2,1)–147–3–2010101000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)→XXRRXRRRRRRR

(4,2)→(4,3)→(5,2)→(5,3)RXRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)→A(2,0)→A(2,1)→A(3,0)→A(3,1)XXRRRRXLSP:(0,0)(0,1)(0,2)(4,3)XSPIHT影像壓縮程序

(cont.)13Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)B(1,0)A(2,0)A(2,1)–147–3–2A(3,0)0101010000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftrees)LIP:(0,0)→(0,1)→(1,0)→(1,1)→(0,2)→(0,3)→(1,2)→(1,3)→(2,0)→(2,1)→(3,0)→(3,1)→XXRRXRRRRRRR(4,2)→(4,3)→(5,2)→(5,3)RXRRLIS:A(0,1)→A(1,0)→A(1,1)→B(0,1)→B(1,0)→A(2,0)→A(2,1)→A(3,0)→A(3,1)XXRRRRXRLSP:(0,0)(0,1)(0,2)(4,3)SPIHT影像壓縮程序

(cont.)14Output:63–34–3123A(0,1)491014–13A(1,0)1514–9-7A(1,1)10(+)11(-)00110000100000B(0,1)B(1,0)A(2,0)A(2,1)–147–3–2A(3,0)A(3,1)01010100000

n=5 //25=32(n--)H=(0,0),(1,0),(0,1),(1,1) //head(rootsoftre