{"id":1063,"date":"2019-10-06T16:44:58","date_gmt":"2019-10-06T16:44:58","guid":{"rendered":"https:\/\/muthu.co\/?p=1063"},"modified":"2021-05-24T02:50:13","modified_gmt":"2021-05-24T02:50:13","slug":"reducing-the-number-of-colors-of-an-image-using-median-cut-algorithm","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/reducing-the-number-of-colors-of-an-image-using-median-cut-algorithm\/","title":{"rendered":"Reducing the number of colors of an image using Median Cut algorithm"},"content":{"rendered":"\n

In my previous post, I talked about the <\/span><\/span>Uniform Quantization algorithm, <\/span><\/a>which was a simple way of reducing the colors in the image<\/span><\/span>. <\/span>Though it’s easy to <\/span><\/span>implement<\/span><\/span>, it doesn’t always yield good results when there are many colors belonging to the same region<\/span><\/span>. Also, a lot of color regions will not have any colors mapped to them resulting in color map entries get wasted.<\/span><\/p>\n\n\n\n

In this post, I will talk about the Median Cut algorithm for color quantization. The main idea is to recursively<\/span> sort the pixels by color space and divide it along the median. The implementation can be found here.<\/a><\/span><\/p>\n\n\n\n

Algorithm<\/h2>\n\n\n\n
  1. Move all pixels into a single large bucket.<\/li>
  2. Find the color channel (red, green, or blue) in the image with the greatest range.<\/li>
  3. Sort the pixels by that channel values.<\/li>
  4. Find the median and cut the region by that pixel.<\/li>
  5. Repeat the process for both buckets until you have the desired number of colors.<\/li><\/ol>\n\n\n\n

    For example, In your image, if the blue channel has the greatest range, then a pixel with an RGB value of (32, 8, 16) is less than a pixel with an RGB value of (1, 2, 24), because 16 < 24. Sort the pixels along blue channel. After the bucket has been sorted, move the upper half of the pixels into a new bucket. Repeat the process on both buckets, giving you 4 buckets, then repeat on all 4 buckets, giving you 8 buckets, then repeat on all 8, giving you 16 buckets. Average the pixels in each bucket and you have a palette of 16 colors.<\/p>\n\n\n\n

    Since the number of buckets doubles with each iteration, this algorithm can only generate a palette with a number of colors that is a power of two.<\/p>\n\n\n\n

    Implementation<\/h2>\n\n\n\n

    The code below implements the Median Cut Color quantization algorithm. You can reduce the colors only in the multiple of 2 because in each recursion you are dividing the block into two. The complete notebook is <\/span>here<\/span><\/a>.<\/span><\/p>\n\n\n\n

    import matplotlib.pyplot as plt\nimport numpy as np\nfrom skimage.io import imread\n        \nsample_img = imread('resource\/girl.jpg')\n\ndef median_cut_quantize(img, img_arr):\n    # when it reaches the end, color quantize\n    print(\"to quantize: \", len(img_arr))\n    r_average = np.mean(img_arr[:,0])\n    g_average = np.mean(img_arr[:,1])\n    b_average = np.mean(img_arr[:,2])\n    \n    for data in img_arr:\n        sample_img[data[3]][data[4]] = [r_average, g_average, b_average]\n    \ndef split_into_buckets(img, img_arr, depth):\n    \n    if len(img_arr) == 0:\n        return \n        \n    if depth == 0:\n        median_cut_quantize(img, img_arr)\n        return\n    \n    r_range = np.max(img_arr[:,0]) - np.min(img_arr[:,0])\n    g_range = np.max(img_arr[:,1]) - np.min(img_arr[:,1])\n    b_range = np.max(img_arr[:,2]) - np.min(img_arr[:,2])\n    \n    space_with_highest_range = 0\n\n    if g_range >= r_range and g_range >= b_range:\n        space_with_highest_range = 1\n    elif b_range >= r_range and b_range >= g_range:\n        space_with_highest_range = 2\n    elif r_range >= b_range and r_range >= g_range:\n        space_with_highest_range = 0\n\n    print(\"space_with_highest_range:\",space_with_highest_range)\n\n    # sort the image pixels by color space with highest range \n    # and find the median and divide the array.\n    img_arr = img_arr[img_arr[:,space_with_highest_range].argsort()]\n    median_index = int((len(img_arr)+1)\/2)\n    print(\"median_index:\", median_index)\n\n    \n    #split the array into two buckets along the median\n    split_into_buckets(img, img_arr[0:median_index], depth-1)\n    split_into_buckets(img, img_arr[median_index:], depth-1)\n    \nflattened_img_array = []\nfor rindex, rows in enumerate(sample_img):\n    for cindex, color in enumerate(rows):\n        flattened_img_array.append([color[0],color[1],color[2],rindex, cindex]) \n        \nflattened_img_array = np.array(flattened_img_array)\n\n# the 3rd parameter represents how many colors are needed in the power of 2. If the parameter \n# passed is 4 its means 2^4 = 16 colors\nsplit_into_buckets(sample_img, flattened_img_array, 4)<\/code><\/pre>\n\n\n\n
    The output of the above program after execution:<\/p>\n\n\n\n
    \"\"<\/a>
    Original Image<\/strong><\/figcaption><\/figure><\/div>\n\n\n\n
    \"reduced<\/a>
    8 colors<\/strong><\/figcaption><\/figure><\/div>\n\n\n\n
    \"\"<\/a>
    32 Colors<\/strong><\/figcaption><\/figure><\/div>\n\n\n\n
    \"\"<\/a>
    128 colors<\/strong><\/figcaption><\/figure><\/div>\n\n\n\n
    References:<\/h2>\n\n\n\n