有關利用K MEANS演算法來壓縮BMP

學校老師出了一題將全彩的BMP檔壓縮成256色的問題

也提供我們一些有關BMP可能所需的資料

https://drive.google.com/file/d/0B_F56pVthAZUSmg2Y...

目前還搞不清楚KEANS的步驟@@"

更不知道該如何下手 有人能幫幫我嗎

已更新項目:

@Chen

Could you teach me the steps ?

I am still not understand . T_T

2 個已更新項目:

請問我要怎麼把每個位數的顏色(紅綠藍)存到資料結構裡面@@?

要使用三維陣列還是link list @@?

3 個已更新項目:

把圖片的每個點抓出來使用

4 個已更新項目:

我解決了邏輯問題

但是又出現一個問題 ..

我如果選擇256種顏色

然後長寬分別為 977 * 734

執行一次 K MEANS 要花掉 977*734*256 = 1億8千萬次迴圈

( 每個位數和每個K各比較一次 )

有辦法修正嗎 @@?

5 個已更新項目:

為什麼我的執行要好久好久

換算下來要好幾個小時QQ

6 個已更新項目:

Could I give you my code and please help me for checking what's wrong ? T_T

7 個已更新項目:

我知道原因了

我有output所以造成很慢 去掉output就快很多了

謝謝你喔^ ^

THANKS

1 個解答

評分
  • Chen
    Lv 6
    6 年前
    最佳解答

    Color processing is basic function for image processing.

    1. jpg file is converted into bmp file or Bmp file is converted into jpg file.

    2. 24bit colors file is converted into 16 bit colors file

    3 24bit colors file is converted into 12 bit colors file ( for tracking )

    4. 24bit colors file is converted into 8 bit colors file ( for example )

    5. 24bit colors file is converted into 8 bit grey level file

    6. 24bit colors file is converted into 4 bit grey level file

    7. 24bit colors file is converted into binary white & black file

    Processing data in 24bit colors being convert into 256 colors adopts

    distance process, It creates many aliasing ( like MSPAINTS package softare), I adopts tree method ( no aliasing ).

    for example:

    original lena.bmp (24 bit colors bmp file)

    圖片參考:https://s.yimg.com/rk/AC08187637/o/89161970.bmp

    after my program( octree.exe ) lena8.bmp( 256 colors bmp file )

    圖片參考:https://s.yimg.com/rk/AC08187637/o/800385413.jpg

    2014-03-09 11:02:02 補充:

    I tell you how to do it:

    1. at first finding the previous 256 showing many times colors to works as centroidK

    256 centroid colors work as colors palette

    2014-03-09 11:02:32 補充:

    2..k-means is cluster of classification

    centroid0 of C0

    -----> | k- means| --> output colors index works as data of 256 colors

    input colors | |

    .

    .

    centroidk of C256

    .

    2014-03-09 11:02:52 補充:

    every distance between input color and centroidK is mininum, output CK works as

    data of colors, It is very simple, but It create aliasing

    2014-03-09 11:25:12 補充:

    distance = sqrt( input color - centroid k ) * (input color-centroidK )),

    2014-03-09 20:34:53 補充:

    every pixel defines RGB,

    and you maybe use every pixel to store in your 2 dimension memory or 3 channel memory.

    2014-03-09 20:42:08 補充:

    attention 2thing:

    1. Your memory muste be 4 multiple boundary, or skew picture or can't read or write in virtual memory.

    2014-03-09 20:45:24 補充:

    2.data of BMP format is from down up to top approach, JPEG(other)

    format is from top to down approach. so processing data must do inverse

    of data of BMP format.

    2014-03-09 20:49:38 補充:

    I can provide you with outline solving problem, detail steps by yourself.

    2014-03-10 09:44:05 補充:

    how to find the previous 256 showing many times colors in picture ?

    24bit colors need 16M byte array for histogram, It is too big, so You must reduce colors.

    2014-03-10 09:44:42 補充:

    reduce colors:

    2 method:

    1. 24bit colors is converted into 16 bit colors, You need 64K byte array.

    2. 24 colors in converted into 12 bit colors, You need 4K byte array

    dependent on your determination.

    2014-03-10 09:45:28 補充:

    God bless you !!

    2014-03-10 21:55:02 補充:

    yes, A 977 x 734 picture takes 977*734*256 times, about 10 ~ 20 second.

    , when You adopt distance method, It is slow and create aliasing.

    2014-03-10 21:58:09 補充:

    soory, modify it, about 5 - 10 second

    2014-03-10 23:44:41 補充:

    I have gived you 2 above attention statement, and At first you select small

    picture to test it ( 100x100 picture is 4 multiple boundary, andI think It take time about 1 second )

    2014-03-10 23:50:29 補充:

    by the way, I suggest you should adopt OPENMP to process loop data, It save

    many time.

還有問題?馬上發問,尋求解答。