کاهش رنگ تصویر با خوشه بندی | پیاده سازی در R

«خوشه بندی» (Clustering) از تکنیک‌های معروف در زمینه «یادگیری ماشین» (Machine Learning) از نوع «بدون نظارت» (Unsupervised) یا غیرنظارتی است. بوسیله روش‌های خوشه‌بندی، بسیاری از تکنیک‌های تصویربرداری پزشکی مثل MRI، متحول شده است. به طوری که با استفاده از خوشه‌بندی، شناسایی تومورها و نواحی مربوط به جراحی تومر تعیین شده و آسیب کمتری به نواحی دیگر اعضای بدن می‌رسد. در این نوشتار از فرادرس می‌خواهیم به کمک خوشه بندی یک تصویر را تجزیه و تحلیل کرده و تعداد رنگ‌های آن را کاهش دهیم. این موضوع می‌تواند به نوعی، باعث کاهش کیفیت شده ولی در عوض، حجم فایل تصویری را هم کاهش می‌دهد. اغلب در فشرده‌سازی تصویر از خوشه‌بندی نیز استفاده می‌شود. به این ترتیب موضوع کاهش رنگ تصویر با خوشه بندی را با استفاده از کدهای زبان برنامه‌نویسی R پیاده‌سازی کرده و به کمک یک مثال گام‌های لازم برای نحوه انجام کار را فرا می‌گیریم.

برای آشنایی بیشتر با موضوع پردازش تصویر رایانه‌ای بهتر است ابتدا نوشتارهای بینایی کامپیوتر چیست؟ — به زبان ساده و آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن را مطالعه کنید. همچنین خواندن پردازش تصویر با پایتون — راهنمای کاربردی و JPEG بهتر است یا PNG؟ نیز خالی از لطف نیست.

کاهش رنگ تصویر با خوشه بندی

همانطور که اشاره شد، تکنیک خوشه‌بندی قادر است نقاط همسان یا شبیه را تعیین کرده و برای آن‌ها یک نماینده ایجاد کند. در اغلب حالت‌ها، روش به کار رفته در خوشه‌بندی، «خوشه‌بندی تفکیکی» یا «خوشه‌بندی افرازی» (Partitional Clustering) و از الگوریتم خاصی به نام k-means یا k-میانگین استفاده می‌شود. به این ترتیب به عنوان «معرف» (Profile) برای هر خوشه، از میانگین مقادیر یا ویژگی‌ها در هر خوشه استفاده شده  و به همین علت نیز نام این الگوریتم را k-میانگین گذاشته‌اند.

فیلم آموزش خوشه بندی تفکیکی با نرم افزار آر R در فرادرس

کلیک کنید

این الگوریتم اولین بار توسط «جیمز مکوئین» (MacQueen) در سال 1967 به منظور معرفی خوشه‌بندی تفکیکی طی مقاله‌ای، معرفی شد. بعدها الگوریتم پیشنهادی وی، توسط «استوارت لوید» (Stuart Lloyd)، مورد بازبینی قرار گرفت و برای تبدیل پالس به کد در «آزمایشگاه‌های بل» (Bell Laboratory) به کار رفت. این الگوریتم به طور مستقل توسط فرد دیگری به نام «ادوارد فورجی» (Edward W. Forgy) نیز ابداع شد و به همین علت گاهی این الگوریتم را به نام «لوید-فورجی» (Lloyd- Forgy) می‌شناسند.

در این نوشتار می‌خواهیم به کمک این الگوریتم، عمل کاهش رنگ تصویر با خوشه بندی را انجام دهیم. در حقیقت با این کار رنگ‌های موجود در یک تصویر کمتر از حالت عادی خواهند شد. در این بین از زبان برنامه‌نویسی و محاسبات آماری R و بعضی از کتابخانه‌های آن بهره خواهیم برد. برای انجام این کار، مراحل یا گام‌های زیر را طی خواهیم کرد.

1. دریافت اطلاعات رنگ‌های به کار رفته در یک تصویر فرضی (در اینجا از یک تصویر درونی در R استفاده خواهیم کرد).
2. خوشه‌بندی رنگ‌ها با توجه به تعداد رنگ درخواستی برای کاهش رنگ (مثلا ۵ رنگ اصلی)
3. محاسبه مراکز خوشه‌ها به عنوان رنگ‌های جایگزین برای طیف رنگ‌های اصلی
4. جایگزین کردن طیف رنگ‌ها با رنگ‌های حاصل از خوشه‌بندی در تصویر و نمایش تصویر جدید

گام اول: دریافت اطلاعات یک فایل تصویری

ابتدا کتابخانه‌های مورد لزوم برای انجام این کار را معرفی می‌کنیم. کد زیر برای نصب کتابخانه‌های مورد نظر، نوشته شده است. به این ترتیب بسیاری از محاسبات توسط توابع درون کتابخانه‌ها صورت گرفته و کار برایمان بسیار ساده‌تر خواهد شد.

1###########################
2#      Install packages   #
3#      Run Once           #
4###########################
5
6install.packages("ggplot2")
7install.packages("scales")
8install.packages("jpeg")

البته به یاد داشته باشید که اجرای این بخش فقط یکبار صورت پذیرد، زیرا پس از اجرای این کد، این کتابخانه‌ها روی رایانه شخصی و در نرم‌افزار R ثبت و کپی شده‌اند. به منظور راه‌اندازی و بهره‌گیری از این کتابخانه‌ها نیز از دستورات زیر کمک بگیرد. به این ترتیب، کتابخانه‌های نصب شده، در حافظه قرار گرفته و توابع مربوط به آن‌ها، در دسترس خواهند بود.

1###########################
2#      Load packages      #
3#                         #
4###########################
5
6library(ggplot2)
7library(scales)
8library(jpeg)

همانطور که می‌دانید، کتابخانه ggplot2 مربوط به ترسیم نمودارها است. با دستورات مربوط به این کتابخانه، تصویر فراخوانی شده را در دو حالت عادی و کاهش رنگ، ترسیم خواهیم کرد. کتابخانه scales نیز به منظور استفاده از تابع show_col به کار رفته است که «پالت رنگ‌های» (Color Palette) «قرمز-سبز-آبی» (RGB) را نمایش می‌دهد. کتابخانه JPEG نیز برای خواندن و نوشتن فایل‌های تصویری با پسوند jpg مناسب است.

قطعه کد زیر، برای خواندن فایل تصویری و استخراج رنگ‌های آن مورد استفاده قرار گرفته است. هر یک از رنگ‌های RGB در یک بردار به نام R ,G و B ذخیره شده‌اند. قرار است این بردارها در خوشه‌بندی با الگوریتم kmeans نقش داشته باشند.

1###########################
2#      Reading JPG File   #
3#      Extract its Colors #
4###########################
5painting <- readJPEG(system.file("img", "Rlogo.jpg", package="jpeg"))
6
7dimension    <- dim(painting)
8painting_rgb <- data.frame(
9  x = rep(1:dimension[2], each = dimension[1]),
10  y = rep(dimension[1]:1, dimension[2]),
11  #slicing our array into three RGB colors 
12  R = as.vector(painting[,,1]), 
13  G = as.vector(painting[,,2]),
14  B = as.vector(painting[,,3])
15)

قبل از هر چیز بهتر است تصویر و پالت رنگی این فایل را مشاهده کنیم. دستورات زیر به این منظور نوشته شده‌اند.

فیلم آموزش برنامه نویسی R و نرم افزار RStudio – مقدماتی در فرادرس

کلیک کنید

تصویر مورد نظر در این متن همان لوگوی نرم‌افزار R است که به صورت یک فایل سیستمی و تصویری به نام Rlogo.jpg ثبت و در حافظه ذخیره شده است.

1###########################
2#      Plot the image     #
3#      and colors palette #
4###########################
5
6ggplot(data = painting_rgb, aes(x = painting_rgb$x, y = painting_rgb$y)) + 
7  geom_point(colour = rgb(painting_rgb$R,painting_rgb$G,painting_rgb$B)) +
8  labs(title = paste("Original Image")) +
9  xlab("x") +
10  ylab("y") 
11
12
13show_col(rgb(painting_rgb$R,painting_rgb$G,painting_rgb$B),labels = FALSE)

نتیجه اجرای این کد، تصویرهایی است که در ادامه قابل مشاهده‌ است. در تصویر ۱، نمایشی از فایل JPG در مختصات دکارتی را می‌بینید که قرار است کاهش رنگ تصویر با خوشه بندی روی آن اتفاق بیافتد.

در تصویر شماره ۲، پالت رنگی (الگوی رنگ‌های به کار رفته در تصویر) را ملاحظه می‌کنید. مشخص است که تعداد رنگ‌ها بسیار زیاد هستند. توجه داشته باشید که شاید این رنگ‌ها تکراری به نظر برسند ولی اگر کدهای رنگ آن‌ها را نیز به جدول اضافه کنید، متوجه خواهید شد که با یکدیگر حداقل از لحاظ کد رنگ، تفاوت دارند. به این منظور کافی است در تابع show_col، پارامتر labels=FALSE را به صورت labels=TRUE درآورید. این کار را در پالت رنگی که حاصل از نتایج خوشه‌بندی است در تصویر 3، انجام داده‌ایم.

گام دوم: خوشه‌بندی رنگ‌ها

برای خوشه‌بندی مقادیر حاصل از چندین مشاهده (یا در اینجا نقطه‌های تصویر)، از تابع kmeans در R استفاده می‌کنیم. این تابع در کتابخانه Base قرار گرفته و احتیاج به بارگذاری ندارد. نتایج حاصل از اجرای کاهش رنگ تصویر با خوشه بندی توسط این تابع، می‌تواند اثر مناسبی در کاهش حجم تصویر داشته باشد. ابتدا مراکز خوشه‌ها (Centers) و همچنین برچسب مشاهدات (cluster) و تعلق به هر خوشه را مشخص می‌کنیم. در کد زیر این عمل اجرا شده و نتایج مربوط به مراکز و برچسب‌ها در کلاسی به نام k_means ذخیره می‌شود. توجه داشته باشید که تعداد خوشه‌ها یا تعداد مراکز توسط پارامتر centers=5 برابر با پنج در نظر گرفته شده است پس انتظار داریم از این مرحله، پنج رنگ استخراج شده و تصویر نهایی براساس این تعداد رنگ ساخته شود.

1###########################
2#      Clustering Colors  #
3#    with kmeans function #
4###########################
5
6k_means <- kmeans(painting_rgb[,c("R","G","B")], centers = 5, iter.max = 30)
7
8str(k_means)

نتیجه را به کمک تابع str به صورت زیر مشاهده خواهید کرد. مشخص است که پنج مرکز با سه مولفه یعنی کدهای R و G همچنین B ذخیره شده است. تعداد نقاط این تصویر نیز ۷۶۰۰ پیکسل است.

1List of 9
2 $ cluster     : int [1:7600] 3 3 3 3 3 3 3 3 3 3 ...
3 $ centers     : num [1:5, 1:3] 0.404 0.546 0.993 0.743 0.184 ...
4  ..- attr(*, "dimnames")=List of 2
5  .. ..$ : chr [1:5] "1" "2" "3" "4" ...
6  .. ..$ : chr [1:3] "R" "G" "B"
7 $ totss       : num 1709
8 $ withinss    : num [1:5] 17.1 21.23 2.97 9.46 10.78
9 $ tot.withinss: num 61.5
10 $ betweenss   : num 1647
11 $ size        : int [1:5] 1397 1889 3020 656 638
12 $ iter        : int 4
13 $ ifault      : int 0
14 - attr(*, "class")= chr "kmeans"

در خروجی بالا مشخص است که این الگوریتم پس از ۴ بار تکرار همگرا شده و نتیجه حاصل از خوشه‌بندی، بدست آمده است. این مقدار در بخش iter مشخص شده. حال کافی است که مراکز خوشه‌ها و همچنین برچسب‌ها را از متغیر k_means استخراج کنیم.

نکته: یکی از ویژگی‌های الگوریتم خوشه‌بندی kmeans، سرعت در همگرایی است. به همین منظور در اکثر مواردی که احتیاج به خوشه‌بندی سریع و از نوع تفکیکی یا افرازی داریم، از این الگوریتم بهره می‌بریم.

گام سوم: استخراج مراکز خوشه‌ها و برچسب گذاری مشاهدات

محاسبه مراکز خوشه‌ها به ما کمک می‌کند که برآیند یا نماینده‌ای برای هر طیف از رنگ‌ها ایجاد کنیم. به این ترتیب در گام سوم از کاهش رنگ تصویر با خوشه بندی که مرحله استخراج مراکز خوشه‌ها است، عمل جایگزین کردن طیف‌ها با رنگ جدید به عنوان نماینده هر خوشه را انجام داده و تعداد رنگ‌ها را کاهش می‌دهیم.

فیلم آموزش خوشه بندی با الگوریتم های تکاملی و فراابتکاری در فرادرس

کلیک کنید

از طرفی باید مشخص شود که هر «پیکسل» (Pixel) از تصویر متعلق به کدام طیف رنگی است. اینجا است که برچسب‌ها یا متغیر cluster نقش ایفا کرده و نقاط مربوط به هر خوشه را مشخص می‌کنند. قطعه کدی که در ادامه می‌بینید برای استخراج مراکز و همچنین نسبت دادن برچسب‌ها نوشته شده است.

1###########################
2#      Calculate Centers  #
3#      and recolor        #
4###########################
5
6kcenters = as.data.frame(k_means$centers)
7show_col(rgb(kcenters$R,kcenters$G,kcenters$B),labels = FALSE)

همچنین نمایش پالت رنگ‌های جدید (طیف رنگ‌های حاصل از خوشه‌بندی) نیز در تصویر ۳ ظاهر شده است. جایگذاری هر رنگ با رنگ حاصل از خوشه‌بندی نیز در انتهای کد دیده می‌شود. رنگ‌های اصلی به نظر خاکستری تیره، آبی فیلی، سفید، دلفینی و خاکستری تیره است. خانه آخری که در تصویر ۳، شامل رنگ نیست و برای تبدیل پالت رنگ‌ها به یک ماتریس کامل ایجاد شده است. به همین دلیل در تصویر آن را به صورت هاشور زده نمایش داده‌ایم.

گام چهارم: جایگزین کردن رنگ‌ها و نمایش تصویر جدید

در آخرین گام لازم است که رنگ‌های تصویر اصلی با رنگ‌های حاصل از خوشه‌بندی جایگزین شود. تصویر نهایی نیز به این ترتیب ساخته و به کمک تابع ggplot ترسیم خواهد شد. نکته مهم در این گام کد زیر است.

1kcolors = rgb(k_means$centers[k_means$cluster,])

این تساوی، قادر است رنگ هر یک از نقاط را که بوسیله k_mean$cluster اندیس‌گذاری شده‌اند را با رنگ‌های مربوط به مراکز خوشه‌ها، جایگزین کند. تابع rgb باعث می‌شود که کد رنگ‌های RGB در متغیر kcolors قرار گیرد تا هنگام ترسیم تصویر، از پالت RGB استفاده شود.

1###########################
2#      Calculate Centers  #
3#      and recolor        #
4###########################
5
6kcenters = as.data.frame(k_means$centers)
7show_col(rgb(kcenters$R,kcenters$G,kcenters$B),labels = TRUE)
8kcolors = rgb(k_means$centers[k_means$cluster,])

در ادامه، برنامه و کدهای مربوط به رسم شکل مورد نظر آورده شده است. باز هم از تابع ggplot برای ترسیم تصویر جدید استفاده کرده‌ایم.

فیلم آموزش خوشه بندی سلسله مراتبی در آر R در فرادرس

کلیک کنید

توجه داشته باشید که پارامترهای دیگری که در این قسمت آورده شده، مربوط به تعیین رنگ نقاط (geom_point) با پارامتر colour و همچنین عنوان‌ها و برچسب‌های محورهای نمایش داده شده (xlab , ylab) در تصویر است.

1###########################
2#      plot the image     #
3#   with reduced colors   #
4###########################
5
6ggplot(data = painting_rgb, aes(x = x, y = y)) + 
7  geom_point(colour = kcolors) +
8  labs(title = paste("k-Means Clustering of", k_means$Clusters, "Colours")) +
9  xlab("x") +
10  ylab("y") 

در تصویر ۴ می‌توانید شکل جدید را مشاهده کنید. مشخص است که تعداد رنگ‌ها در طیف رنگی، باعث شده است که کیفیت تصویر کاهش یابد ولی در عوض فضای ذخیره سازی برای تعداد رنگ‌ها نیز کاهش خواهد داشت.

خلاصه و جمع‌بندی

همانطور که در این متن خواندید، کاهش رنگ تصویر با خوشه بندی، امری ساده و برنامه نویسی آن با امکانات زبان برنامه‌نویسی R به راحتی صورت می‌گیرد. ولی آنچه مهم است، تعیین تعداد رنگ‌های مناسب است که کاربران متوجه کاهش کیفیت تصویر ساخته شده نسبت به تصویر اصلی نباشند. بنابراین پارامتر $$k$$ که در این نوشتار به طور ثابت اختیار شد، خود جای بحث و بررسی بیشتر دارد. در بیشتر مواقع تکنیک‌های دیگری نیز برای فشرده سازی تصویر و کاهش رنگ‌ها به کار می‌برند که در قالب‌های معروف تصویری مثل JPEG دیده می‌شود.