
媒体数据管理上机实验
这门课的上机题目还都挺有意思,尤其是第三个 LSH 索引耗费了不少精力,故记录下来。
编程语言为 Python 3
1. LZW 编码算法.
如果字典数超过 10 可能会出 bug,因为编码是 1 位的(可通过增加编码位数解决)
算法流程:
- 对输入字符串初始化生成单字符的字典,设P为空字符串;
- 遍历字符串每一位C,判断P+C是否在字典中,若是则将P+C赋予P,否则在字典中添加P+C,在结果添加P对应的值,并将C赋予P;
- 最后一位字符在结果添加P的值;
- 输出编码结果与字典;
- 解码程序拿到编码结果与初始化的单字符字典;
- 将字典键值翻转,对编码的每一位求得对应字符前缀,保存到字典;
- 除第一次,将前缀添加到上一条的末尾,并更新前缀,记录;
- 输出记录下的字符。
1 | def init(s): |
测试:
1 | input a string: abababcabcab |
2. k-l 变换与矢量量化.
在 ColorHistogram.asc
数据集上实现 k-l 变换
算法流程:
- 将输入数据预处理(中心化);
- 求得协方差矩阵C;
- 求C的特征值和特征向量;
- 取最大特征值的特征向量,求得最佳投影矩阵P;
- 对原始样本矩阵投影,得到降维后的新样本矩阵。
1 | import numpy as np |
通过 scipy.cluster.vq
实现对图片的矢量量化
算法流程
- 读取输入图片并转化为 (height * width, channel)
- 计算 kmeans
- 矢量量化
- 输出图像
1 | from scipy.cluster.vq import kmeans, vq |
3. LSH索引实现近似最近邻搜索.
查找 corel数据集
前 1000 行每个点的最近邻点,使用原始汉明编码,计算汉明距离,使用 LSH 索引,实现近似最近邻搜索。输入:corel数据集,汉明码长度K,建表数量L,哈希桶最大容量B;
算法流程:
- 对数据集预处理:乘100取整,获得最大值C与数据维数n;
- 在n*C的范围内生成k个随机数,存入表H,为要取到的汉明码位数。新建哈希索引表;
- 将数据点的坐标转化为0与1的汉明编码,取2中生成的随机数位,组成字符串pi;
- 若哈希索引表pi桶的数量大于B则不记录,否则在pi桶记录该数据点;
- 重复操作2,3,4,生成L张H表与哈希索引表;
- 对前1000行的点进行最邻近搜索,即对数据点求它的汉明编码,对每张H表和每张哈希索引表,根据H表的位数生成字符串,将哈希索引表的该字符串编码处的点作为候选项,将所有的候选项排序选择频次最高的前十个作为结果;
- 计算召回率 Recall、准确率 Accuracy、所用时间 timecost
自己写的代码:
1 | import numpy as np |
4. SIFT特征提取与图像匹配.
算法描述:
输入:原始图像、train图像集;
输出:最相似的图片;
算法流程:
- 使用SIFT提取原图的特征,得到关键点 kp 及描述符 des;
- 获取train中图片,使用SIFT提取特征,得到关键点 kp1 及描述符 des1;
- 初始化flann匹配器;
- knnMatch 返回原图每个特征点的两个匹配;
- 若第一个匹配点的距离小于第二个的0.7倍,则该对特征匹配成功,计入匹配成功列表;
- 若匹配成功的数量大于最大匹配成功数量 ,则替换;
- 重复2到6的操作,直到train中图片搜索完毕。
- 输出最大匹配的图片名。
注意:cv2.xfeatures2d.SIFT_create()
在新版 opencv-python
中删除,我的解决方案是通过 pip uninstall opencv-python
卸载原有的 opencv-python
,再通过 pip install opencv-contrib-python==3.4.2.16
安装旧版本的 opencv-contrib-python
,可以运行。
1 | import cv2 |
感谢您的阅读,本文由 夏月秋风 版权所有。如若转载,请注明出处:夏月秋风(http://yoursite.com/2020/07/07/Mediadataexp/)