奇异值分解(SVD)和简单图像压缩

SVD(Singular Value Decomposition,奇异值分解)

算法优缺点:

  • 优点:简化数据,去除噪声,提高算法结果
  • 缺点:数据的转换可能难于理解
  • 适用数据类型:数值型数据

算法思想:

很多情况下,数据的一小部分包含了数据的绝大部分信息,线性代数中有很多矩阵的分解技术可以将矩阵表示成新的易于处理的形式,不同的方法使用与不同的情况。最常见的就是SVD,SVD将数据分成三个矩阵U(mm),sigma(mn),VT(nn),这里得到的sigma是一个对角阵,其中对角元素为奇异值,并且它告诉了我们重要的特征。
这里的实现用的也是numpy种的函数linalg.svd()

实例:用SVD进行图像压缩

这里的数据集是前面用于手写识别的一个数据,大小为32*32=1024像素,因为进行svd之后我们的数据变成一堆浮点数,所以输出函数要改进一下,设置一个阀值(这个值的设置会影响显示效果)。可以看出完成压缩之后我们只需要两个奇异值和U、VT两个矩阵,共计64+64+2=130个像素,达到了近十倍压缩比,而且还原出来的图像基本不变

数据如下:

奇异值分解(SVD)和简单图像压缩

执行结果:
  1. *********orignal matrix**************
  2. 00000000000000110000000000000000
  3. 00000000000011111100000000000000
  4. 00000000000111111110000000000000
  5. 00000000001111111111000000000000
  6. 00000000111111111111100000000000
  7. 00000001111111111111110000000000
  8. 00000000111111111111111000000000
  9. 00000000111111100001111100000000
  10. 00000001111111000001111100000000
  11. 00000011111100000000111100000000
  12. 00000011111100000000111110000000
  13. 00000011111100000000011110000000
  14. 00000011111100000000011110000000
  15. 00000001111110000000001111000000
  16. 00000011111110000000001111000000
  17. 00000011111100000000001111000000
  18. 00000001111100000000001111000000
  19. 00000011111100000000001111000000
  20. 00000001111100000000001111000000
  21. 00000001111100000000011111000000
  22. 00000000111110000000001111100000
  23. 00000000111110000000001111100000
  24. 00000000111110000000001111100000
  25. 00000000111110000000011111000000
  26. 00000000111110000000111111000000
  27. 00000000111111000001111110000000
  28. 00000000011111111111111110000000
  29. 00000000001111111111111110000000
  30. 00000000001111111111111110000000
  31. 00000000000111111111111000000000
  32. 00000000000011111111110000000000
  33. 00000000000000111111000000000000
  34. ****reconstructed matrix using 3 singular values******
  35. 00000000000000000000000000000000
  36. 00000000000000000000000000000000
  37. 00000000000010111110000000000000
  38. 00000000000011111110000000000000
  39. 00000000000111111111000000000000
  40. 00000000001111111111110000000000
  41. 00000000001111111111110000000000
  42. 00000000011100000000111000000000
  43. 00000000111100000000111100000000
  44. 00000001111100000000111100000000
  45. 00000001111100000000011100000000
  46. 00000001111100000000011100000000
  47. 00000001111100000000011100000000
  48. 00000000111100000000001111000000
  49. 00000000111100000000001111000000
  50. 00000000111100000000001111000000
  51. 00000000111100000000001111000000
  52. 00000000111100000000001111000000
  53. 00000000111100000000001111000000
  54. 00000000111100000000001110000000
  55. 00000000111100000000001111000000
  56. 00000000111100000000001111000000
  57. 00000000111100000000001111000000
  58. 00000000111100000000001111000000
  59. 00000000111100000000001110000000
  60. 00000000111100000000111100000000
  61. 00000000001111111111111000000000
  62. 00000000001111111111110000000000
  63. 00000000001111111111110000000000
  64. 00000000000011111111110000000000
  65. 00000000000011111111100000000000
  66. 00000000000000000000000000000000
 #coding=utf-8
from numpy import *
def printMat(inMat, thresh=0.8):
for i in range(32):
for j in range(32):
if float(inMat[i,j]) > thresh:
print 1,
else:
print 0,
print ' ' def imgCompress(numSV=3, thresh=0.8):
myl = []
for line in open('0_5.txt').readlines():
newRow = []
for i in range(32):
newRow.append(int(line[i]))
myl.append(newRow)
myMat = mat(myl)
print '*********orignal matrix**************'
printMat(myMat,thresh)
U, sigmal, VT = linalg.svd(myMat)
SigRecon =mat(zeros((numSV,numSV)))
for k in range(numSV):
SigRecon[k,k] = sigmal[k]
reconMat = U[:,:numSV] * SigRecon * VT[:numSV,:]
print "****reconstructed matrix using %d singular values******" % numSV
printMat(reconMat, thresh) def main():
imgCompress() if __name__ == '__main__':
main()

机器学习笔记索引

上一篇:数值分析之奇异值分解(SVD)篇


下一篇:SVD的几何意义,以及在去噪,推荐系统中的应用