Image Filter and Recover

• 2020 年 5 月 3 日
• 筆記
• Algorithm, Computer Science

這是CS50的第四次大作業，順便學習了圖像的入門知識。

基礎

黑白圖(bitmap)的每個像素點只能取值0/1，1代表白色，0代表黑色。
常見的圖片格式有JPEG/PNG/BMP，這些格式都支持RGB，每個像素點可以用多個bit表示，常見的是24-bit，紅、綠、藍分別由8bit表示，範圍0~255。
BMP圖的開始位置有兩個header，第一個叫BITMAPFILEHEADER，14B；第二個叫BITMAPINFOHEADER，40B。接下來的每個像素點是按照BGR的順序存儲的。

過濾器

Image Filter就是對原圖的像素點的像素進行操作，得到一幅新圖。主要有下面幾種：

• Grayscale
  將RGB圖變為灰度圖。將每個像素點的R/G/B的值改為相同，值越大，亮度越大。一般取三色的平均值。
• Sepia
  比較像懷舊濾鏡，有很多算法可以做，主要就是對3種顏色乘一些係數，做一些加減運算。
• Reflection
  左右翻轉。
• Blur
  圖像模糊，對每個像素點的每種顏色，取其周圍3*3格子的平均值。
• Edges
  邊緣檢測，可以用Sobel Operator去做：
  Blur是對周圍的格子取平均，Sobel是求一個加權和，對於x和y方向，有兩個kernel：
  
  對每個像素點的每種顏色，用周圍3*3格子的對應顏色分別去乘Gx/Gy，得到加權和sumx/sumy。
  以x為例，如果左右兩邊差不多，那麼加權和接近0，否則得到一個大正數/負數，說明很有可能是兩個物體的分界。
  綜合考慮x和y方向，取\(\sqrt{sumx^2+sumy^2}\)，再四捨五入到0~255之間。
  對於邊緣的格子，可以做padding，圍一圈全黑(0)的格子，相當於不用計算。

圖片恢復

JPEG的前三個位元組分別是0xff, 0xd8, 0xff，第四個位元組的前四位是1110，這些可以唯一標識JPEG文件。
記憶卡上所有圖片是連續存儲的，最小單位每塊512B，不到一塊的後面補0，不影響顯示，每張圖片可能占若干塊。
可以每次讀512B扔到buffer里，如果是jpeg，就將其寫入新文件、繼續讀512B，直到遇到下一個jpeg。