bitmap 压缩-BitMap原理与实现

关于opencv如何压缩bitmap相关资料如下

安装 opencv

首先安装 python ,建议 python3 ,然后执行

:

pip install opencv-python

1.2 读取图片

首先引入 opencv 包:

importcv2ascv

而后读取图片:

image=(path)

其中 path 为图片路径, image 为图片数据,是一个 对象,其实就是一个多维数组。目前 opencv 支持几乎所有格式的图片(参考

)。

比较经典的问题是: 在只能够使用2G的内存中,如何完成以下操作:

①:对10亿个不重复的整数进行排序。

②:找出10亿个数字中重复的数字。

无论是排序还是找重复的数字都需要将这10亿个数字加入到内存中在去进行操作,很明显,题目给出的2G内存限制说明了在这样的场景下是不能够将所有数都加入到内存中的

1000000000* 4/(1024* 1024* 1024) = 3.725G

那么这时候就需要用到 BitMap结构了

bitMap使用一个bit为0/1作为map的value来标记一个数字是否存在,而map的key值正是这个数字本身。

相比于一般的数据结构需要用4个byte去存储数值本身,相当于是节省了 4*8:1 = 32倍的内存空间

bitMap不一定要用bit数组,可以使用 int,long等等的基本数据类型实现,因为其实质都是在bit位上存数据,用哪种类型只是决定了最终实现出来的BitMap的内置数组中单个元素存放数据的多少

例如:java中的BitSet使用Long数组

BitMap的实现当然少不了位运算,先来明确几个常见位运算,这是实现BitMap的基础:

set(bitIndex): 添加操作

1 .确定该数处于数组中的哪个元素的位上

int wordIndex = bitIndex >> 5;

因为我用的是int[]实现,所以这里右移 5 位(2^5 = 32)

2 .确定相对于该元素中的位置偏移

int bitPosition = bitIndex & ((1 << 5) - 1);

这里相当于是 bitIndex % (1<<5)的取模运算,因为当取模运算的除数是2的次幂,所以可以使用以下的位运算来计算,提升效率(对比HashMap的容量为什么总是2的幂次方的问题,HashMap求下标时也是使用 hash&(n-1))

tips: 位运算的优先级是低于+,-等等的,所以要加上括号,防止发生不可描述的错误

3 .将该位置1

bits[wordIndex] |= 1 << bitPosition;

相当于是将指定位置处的bit值置1,其他位置保持不变,也就是将以这个bitIndex为key的位置为1

tips: 这里是参考了网上的各位大佬的文章,取余 + 按位或,又对比了下BitSet的源码:

words[wordIndex] |= (1L << bitIndex);

没有取余操作,直接|,这两个一样吗?答案当然是一样的

举个栗子:

1 << 148 == 1<< 20

1L << 125 ==1L<< 61

即对于int和long型数据,直接左移其位数相当于是附带了对其的取模操作

总结

:使用Bit-map的思想,我们可以将存储空间进行压缩,而且可以对数字进行快速排序、去重和查询的操作。

Bloom Fliter是Bit-map思想的一种扩展,它可以在允许低错误率的场景下,大大地进行空间压缩,是一种拿错误率换取空间的数据结构

当一个元素加入布隆过滤器中的时候,会进行哪些操作:

当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行哪些操作:

然后,一定会出现这样一种情况:

不同的字符串可能哈希出来的位置相同

(可以适当增加位数组大小或者调整我们的哈希函数来降低概率),因此:

布隆过滤器可能会存在误判的情况

总结来说就是:

布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在

。

Bloom Filter的应用: 常用于解决缓存穿透等场景。

1、等比压缩,等比压缩是保持原图长宽比例的压缩,只是图片变小,展示的还是原图的所有内容(区别于第二种通过Matrix压缩,可以选取图片的一部分,类似于上传头像时,让你在图上选一块zoom的形式)。等比压缩用的的主要是,通过options缩放比例的设置,来生成缩略图:

2、通过Matrix进行更加灵活的缩放:这种方式主要是通过构建缩放矩阵和方法来实现灵活缩放,宽和高缩放的比例可以不一致,而且通过方法创建出来的是新的位图,这个位图可以是选取原图的一部分,而不是对原图进行整体缩放!类似于上传头像时,让你在原图上扣下来一块的效果,控制非常灵活。

3、无损压缩,无损压缩是说图片大小和清晰度看上去和原图没有什么差别,但是确实size缩小了,这里缩小的原理是牺牲了分辨率等其他直观看不到的东西,看起来和原图一样,但是一放大就立马失真了,不会和原图一样放大很多才会逐渐变得不清晰。无损压缩后的图片像素并不会减少,而Bitmap占用内存的定义就是像素点占的内存,所以以Bitmap的方式加载到内存中时,和压缩前占用的内存是同样大的,原来会oom的图片,质量压缩后同样会oom;但是,质量压缩后将流输出到文件中,文件的size会大幅度减小,所以质量压缩特别适合在 Android 端进行图片上传的时候进行图片压缩,既能保持上传后的清晰度,又能减小size。另外质量压缩不是可以无限缩小的,降低到一定程度,就算把quality设置的再小,size也不会再降低了。另外这种方式最好返回保存压缩后的图片保存的文件路径,而不要直接返回Bitmap,示例就懒得改了。

一张图片处理过程,建议先进行等比压缩或者Matrix压缩后,再进行质量压缩,这样组合使用,不管是生成缩略图还是图片上传,效果都不错