ফ্লাড ফিল অ্যালগরিদমঃ গ্রাফিক্স প্রোগ্রামিং এর জন্য যা জানতেই হবে

Post updated on 27th January, 2020 at 01:51 pm

Flood fill algorithm হচ্ছে কোন একটা গ্রাফ (graph) বা মাল্টি ডাইমেনশনাল এরের (Multi-dimensional array) মধ্যকার connected component-গুলো বের করার একটা কার্যকরি এলগোরিদম। ফ্লাড ফিলকে সিড ফিলও (Seed fill) বলা হয়ে থাকে। Flood মানে তো বন্যা। বন্যার পানি যেভাবে আসেপাশের এলাকাকে প্লাবিত করে এই এলগোরিদমটাও একই ধরণের কাজ করে।

Computer Graphics কোর্সের graphics programming এর জন্য এই এলগরিদমটা দরকার হয়। ধর তুমি উইন্ডোজের Paint এর মত একটা সফটওয়্যার বা টুলস বানাতে চাচ্ছ। ওয়েবের জন্য বা মোবাইল এপের জন্য এমন একটা এপ বানাতে চাচ্ছ যেখানে বিভিন্ন shape দেয়া থাকবে। ত্রিভুজ, চতুর্ভুজ, বৃত্ত ইত্যাদি। এগুলো দিয়ে shape draw করার পর color bucket এর মাধ্যমে এক ক্লিকে পুরো shape এর রং পরিবর্তন করে দিতে চাও। এটা করতে হলে এই এলগরিদমটা জানতে হবে। অথবা selected color এর area-কে অন্য একটা color দিয়ে fill করার ফাংশনালিটিটা তুমি তোমার সফটওয়্যারে ইমপ্লিমেন্ট করতে চাচ্ছ। তখনও এই এলগো লাগবে।

Definition এর কানেক্টেড কম্পোনেন্ট বলতে বুঝানো হচ্ছে কোন একটা নোডের সাথে অন্যান্য যে নোডগুলো কানেক্টেড আছে সেগুলোকে। উদাহরণ দেয়া যায় কোন একটা ছবি দেখে। ধরি ছবিটা হচ্ছে বাংলাদেশের পতাকা। লাল-সবুজের এই পতাকাটি যদি সাদা কাগজে না এঁকে একটা গ্রাফ পেপারে আঁকি তাহলে কেমন হবে? দেখা যাবে অসংখ্য ক্ষুদ্র ক্ষুদ্র বর্গের সমন্বয়ে পতাকাটি তৈরি হয়েছে। বেশির ভাগ বর্গের রং সবুজ। আর মাঝের অংশে থাকা বর্গগুলোর রং লাল। পুরো ছবিটিতে তাহলে কয় ধরণের বা কয়টি রঙ্গের কানেক্টেড কম্পোনেন্ট রয়েছে? দুই ধরণের তাই না? একটা region এর রং সবুজ, আরেকটা রিজিয়ন হচ্ছে লাল বর্ণের। তাহলে তুমি কিন্তু চাইলে বের করতে পারবা সবুজ রঙ্গের কানেক্টেড কম্পোনেন্ট বা কানেক্টেড বর্গ বা connected pixel কতগুলো। যদিও ম্যানুয়াল্যি এটা গুণে বের করা কঠিন। কিন্তু তুমি চাইলে একটা প্রোগ্রাম করে বের করে ফেলতে পারো একটা ইমেজের কোন একটা নির্দিষ্ট রঙ্গের কানেক্টেড পিক্সেলের সংখ্যা। আর এ জন্যেই দরকার হয় আমাদের এই ফ্লাড ফিল এলগোরিদম।

ধরো, তোমার কাছে একটা ডিজিটাল ইমেজ আছে। ডিজিটাল ইমেজগুলো কিন্তু স্রেফ একটা 2D array. যার প্রতিটা index এ নির্দিষ্ট কিছু intensity এর মান দেয়া থাকে। এই ডেটাগুলো ধারণ করে ঐ পিক্সেলের brightness, color, amplitude ইত্যাদি। কাজের সুবিধার্তে আমরা এমন একটা ছবির কথা (আসলে char টাইপের 2D array) কল্পনা করি যেই ছবির প্রতিটা পিক্সেলে একটা করে character থাকবে। ক্যারেক্টারগুলো হতে পারে @, . (dot), * (asterisk) অথবা স্পেস। নিচের ছবিটা দেখঃ

আমরা যদি বের করতে চাই এই ছবির কতগুলো dot region আছে তাহলে কিভাবে করব? ডট রিজিওন বলতে বুঝাচ্ছি কত জায়গায় ডট কাছে যারা নিজেদের মধ্যে কানেক্টেড বা সিঙ্গেল ভাবে আছে। অর্থাৎ পাশাপাশি বা উপরে-নিচে যদি ডটগুলো কানেক্টেড থাকে তাহলে সেটাকে একটা রিজিয়ন বলছি। [6, 2] coordinate এ একটা মাত্র ডট আছে। এটাকে একটা রিজিয়ন ধরা হচ্ছে। আবার একদম নিচের দুই লাইনে নিজেদের মধ্যে কানেক্টেড মোট ১০টা ডট আছে, এই পুরোটা একটা রিজিয়ন। ছবি দেখে বুঝে গেছ এতক্ষণে এখানে ডট রিজিয়ন আছে মোট ৫টা। এটা বের করার বুদ্ধি কী? বুদ্ধি হচ্ছে ফ্লাড ফিল! চল দেখে নিইঃ

Algorithm:

আমাদের কাজ হচ্ছে প্রথমত দেখব কোন একটা পিক্সেলে (এই ক্ষেত্রে index) ডট আছে কিনা। যদি থাকে তাহলে এর সাথে কানেক্টেড সবগুলো ডটের অবস্থান নিশ্চিত হয়ে কাউন্টের মান এক বাড়াবো। যেই রিজিয়নের জন্য একবার কাউন্টের মান এক বাড়ানো হয়েছে সেই রিজিয়নের সবগুলো কানেক্টেড ডটের জন্যেই মূলত এক বাড়বে। এটা হ্যান্ডেল করতে হবে যেন প্রতি ডটের জন্য এক করে বাড়িয়ে দেয়া না হয়। এভাবে পুরো 2D array তে লুপ ঘুরিয়ে রিজিয়ন বের করতে হবে।

কোন একটা ইন্ডেক্সে ডট পাওয়া গেলে সেখান থেকে একটা DFS চালাতে হবে। ডিএফএসের নাম শুনে ভয় পাওয়ার কিছু নাই। ফ্লাড ফিল আসলে DFS-ই। প্রথমে 2D array তে traverse করার জন্য nested loop লিখতে পারি এরকম ভাবেঃ

for(i=0; i<row; i++) {

    for(j=0; j<column; j++)
     {
        if(grid[i][j]=='.' && flag[i][j]==0)
        {
            cnt++;
            floodfill(i,j);
        }

     }

}

grid একটি character type 2D array আর flag হচ্ছে integer type 2D array. একটু আগে বললাম না যে কোন একটা রিজিয়নের সব ডটের জন্য একবার মান বাড়বে? এটা করার জন্য ফ্ল্যাগ এরেটা রাখা (যার সব ইন্ডেক্সের মান ০ করে রাখা হয়েছে)। যেই ইন্ডেক্সে ডট পাওয়া যাবে সেই ইন্ডেক্স থেকে তার কানেক্টেড ডট ইন্ডেক্সগুলো খুঁজব। যখন ডট পাওয়া যাবে তখনই ফ্ল্যাগের ঐ ইন্ডেক্সের মান ১ করে দিব। এই জন্যেই দ্বিতীয় লুপের ভিতর কন্ডিশন চেক করা হয়েছে যে ইন্ডেক্সটায় ডট আছে কিনা এবং একই সাথে ফ্ল্যাগের ঐ ইন্ডেক্সের মান শূণ্য কিনা। কারণ এই ফ্ল্যাগের মান ১ হবার অর্থ হচ্ছে এই ডট already কোন একটা রিজিয়নের মধ্যে পড়ে গেছে। যদি দুইটাই সত্য হয় তার মানে এই ডটের রিজিয়নটা এখনো কাউন্ট করা হয় নি। তাই IF এর true block এর ভিতরে প্রথমে cnt বা কাউন্টের মান এক বাড়ানো হল, অর্থাৎ নতুন একটা ডট রিজিয়নের অস্তিত্ব পাওয়া গেছে। ডট পাওয়া গেল, কিন্তু ফ্ল্যাগের ঐ ইন্ডেক্সের মান ১ তাহলে কিন্তু কাউন্ট করব না। এরপরের লাইনে একটা ফাংশন কল করা হয়েছে। ডটের ইন্ডেক্সের row, column এর মান দুটি প্যারামিটার হিসেবে পাঠানো হয়েছে।

ফাংশনের বডিটা দেখি এইবারঃ

void floodfill(int i, int j) {

    if(i<0 || j<0 || i>=row || j>=column) //base case
    return;

   //if found dot and it's already not visited
   if(grid[i][j]=='.' && flag[i][j]==0){

      flag[i][j]=1; //mark this [i,j] dot as VISITED

      //DFS Call for adjacent indices
      floodfill(i+1,j);
      floodfill(i-1,j);
      floodfill(i,j+1);
      floodfill(i,j-1);
      floodfill(i+1,j+1);
      floodfill(i+1,j-1);
      floodfill(i-1,j+1);
      floodfill(i-1,j-1);

   }

}

এটা একটা recursive function. রিকার্সনের ব্যাপারে ধারণা না থাকলে আমার ব্লগের এই পোস্টগুলো পড়তে পার। এছাড়াও  ফাহিম ভাইয়ের এই লেখাটি এবং রোমিওর এই লেখাটিও দেখে নিতে পার।

ফাংশনের প্রথমেই base case টা লেখা হয়েছে। IF এর ভিতরে চেক করা হচ্ছে i,j এর মান শূণ্যের চেয়ে ছোট কিনা। মানে 2D array এর lower bound ক্রস করে কিনা। যেহেতু 2D array এর শুরুর ইন্ডেক্স [0, 0] তাই যখন এই ফাংশনের ভিতরে [-1, -1] টাইপের মান আসবে তখন তা আর কাজ করবে না। বেজ কেসে আটকে যাবে। একই ভাবে চেক করা হয়েছে মানগুলো কখনো row বা column এর সংখ্যার চেয়ে বড় হয়ে গেলে তখনও তা বেজ কেসে আটকে যাবে। যদি ইন্ডেক্সের মানগুলো এরের ইন্ডেক্সের চেয়ে ছোট বা বড় না হয়, অর্থাৎ এরের ভিতরেই অবস্থান করে তাহলেই শুধুমাত্র ফাংশনের পরের অংশের কাজ হবে।

main function থেকে চেক হয়ে আসার পরেও if(grid[i][j]==’.’ && flag[i][j]==0) এর চেকটি রাখা হয়েছে floodfill function এর ভিতরে। কারণ, কোন একটা রিজিয়নের প্রথম যেই ডটের জন্য মেইন ফাংশন থেকে ফ্লাড ফিল ফাংশন কল হবে সেটা ছাড়া অন্যান্য ডটের জন্য এই চেকিংটা কাজ করবে। যেহেতু এই ফাংশনটা নিজেই নিজেকে কল করতে থাকবে তাই এখানেও প্রতিবার চেক করা দরকার হচ্ছে যে কোনো ইন্ডেক্সে ডট পাওয়া গেছে কিনা এবং একই সাথে চেক করা যে এই ডটটি already visited কিনা?

যদি IF এর কন্ডিশন সত্য হয় তাহলে ভিতরে ঢুকে ফ্ল্যাগের ঐ ইন্ডেক্সের মান 1 করে দেয়া হচ্ছে। এর দ্বারা বুঝানো হচ্ছে এই ইন্ডেক্সটা অলরেডি ভিজিটেড। কোডের এই পর্যায়ে এসে ডটের corresponding index এর flag এরের ইন্ডেক্সটা 1 করে দেয়ার মাধ্যমে বুঝানো হচ্ছে “এই ইন্ডেক্স অলরেডি ট্রাভার্স করা শেষ। জিন্দেগীতেও আর এই ডটের উপর কাজ করা লাগবে না!”

এরপর হচ্ছে রিকার্সিভের আসল সৌন্দর্য শুরু!

একেকটা ইন্ডেক্সের সাথে সর্বোচ্চ ৮টা adjacent index থাকতে পারে। কোন একটা ইন্ডেক্স যদি হয় [i, j] তাহলে এর সাথে কানেক্টেড ইন্ডেক্সগুলো হবে [i+1, j], [i-1, j], [i, j+1], [i, j-1]… যেগুলো দিয়ে মোট আটবার floodfill() ফাংশনটি কল করা হয়েছে। এর ফলে একটা ডটের সাথে কানেক্টেড সবগুলো ডটের ইন্ডেক্সেই ভিজিট করা হবে। আর ভিজিট করা হয়েছে এই track টা রাখা হবে flag[][] এরের মধ্যে। এই ফাংশনটা সম্পূর্ণ ভাবে শেষ হবে তখনই যখন কোন একটা রিজিয়নের সবগুলো ডট ভিজিট করা হয়ে যাবে।

উপরের কোডটুকুই নিচের মত direction array ব্যবহার করে লেখা যায়। একই কাজ হবে। কিন্তু কোড হবে আরেকটু ছোট। ডিরেকশন এরে নিয়ে বিস্তারিত জানা যাবে ‘শাফায়েতের ব্লগ’ থেকে।

//Global array
int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};

void floodfill(int i, int j) {

    if(i<0 || j<0 || i>=row || j>=column) //base case
    return;

    //if found dot and it's already not visited
    if(grid[i][j]=='.' && flag[i][j]==0){

        flag[i][j]=1; //mark this [i,j] dot as VISITED

        //DFS Call for adjacent indices
        for(int m = 0; m < 8; m++){

            int x = i + fx[m];
            int y = j + fy[m];
            floodfill(x, y);
        }

    }

}

Input-Output সহ পুরো কোডটা দেখতে পারো এখান থেকে। এই কোডে ডট ইন্ডেক্সগুলোর মানকে পরিবর্তন করা হয়েছে ‘+’ দ্বারা। এরপর সেটা প্রিন্ট করে দেখানো হয়েছে।

 

উপরের প্রবলেম আর কোড যদি বুঝে থাকো তাহলে তোমার জন্য একটা প্রবলেম দিচ্ছি। এটা নিজে নিজে সলভ করে ফেল। চাইলে এর সাথে আরো ডাল-লতা-পাতা দিয়ে বড় প্রবলেম বানিয়েও সলভ করতে পারো।

Problem:
তুমি একটা হার্ডওয়্যার প্রস্তুতকারক কোম্পানীর প্রোগ্রামার। নতুন এক ধরনের প্রিন্টার বানানো হবে যেটা কালারফুল ছবি প্রিন্ট করবে। সাধারণত প্রিন্টার ছবি প্রিন্ট করতে থাকলে কালি শর্ট পড়লে বুঝতে পারে না। প্রিন্ট করা শুরু করে দেয়, কালি শেষ হয়ে গেলে অপূর্ণ ছবি প্রিন্ট হয়। তোমার কোম্পানী চিন্তা করল এতে কাগজ-কালির অপচয় হয়। তাই প্রিন্ট করার আগেই ছবিটা প্রিন্ট করতে কতটুকু কালি দরকার সেটা হিসাব করে প্রিন্টারে থাকা কালির সাথে compare করা হবে। যদি পর্যাপ্ত কালি থাকে তাহলে প্রিন্ট হবে, অন্যথায় ইউজারকে বলে দিবে কালি রিফিল করার জন্য।

ধরে নাও, ছবিতে শুধু red, green, blue-ই থাকবে। আর একই রঙ্গের প্রতিটা পিক্সেল প্রিন্ট করার জন্য সংশ্লিষ্ট কালির ১ একক পরিমাণ কালি প্রয়োজন হবে। একেকটা ছবি প্রিন্ট করার জন্য প্রিন্টারটা তার হেডকে ৩ বার মুভ করায়। সবগুলো লাল রং একবারে, সবগুলো সবুজ একবারে একই ভাবে সবগুলো নীল রং একবারে প্রিন্ট করা হয়। প্রতিটা রং এর কতটা রিজিয়ন আছে সেটাও প্রিন্টারকে কমান্ড দিয়ে জানাতে হয়।

অনেক বড় প্রোজেক্ট। তোমাকে একটা ছোট পার্টের দায়িত্ব দেয়া হল। তোমার কাজ হচ্ছে ছবিটা থেকে বের করা কোন কালি কতটুকু প্রয়োজন। আর কোন কালির কতগুলো রিজিয়ন আছে?

Input:

RRGGGGGRBBBB
GRBGGGRGGGRR
BBRBGBRRRBGR
GBBRBGRRGRGR
RRRRRRRRRRRR

Output:

R – 1 region – 29 pixel
G – 4 region – 18 pixel
B – 3 region – 13 pixel

দেখো তো কোড করে এটা সল্ভ করতে পারো কিনা?

 

আজ এ পর্যন্তই। দেখা হবে আবার কোন এলগরিদমের আলোচনা নিয়ে। সে পর্যন্ত সবার জন্য শুভ কামনা। 🙂

[কারো চোখে কোথাও কোন ভুল ধরা পড়লে অনুগ্রহ করে জানাবেন। যারা আগে এই এলগোর সাথে পরিচিত ছিলেন না তাদেরকে বিশেষ ভাবে অনুরোধ করব ফিডব্যাক দিতে। আমি বুঝাতে পেরেছি কিনা বা আমার বুঝানোর স্টাইলটা ঠিক আছে কিনা। আর যারা পরিচিত তারা পরামর্শ দিতে পারেন লেখার ভঙ্গির ব্যাপারে। অগ্রীম ধন্যবাদ। 🙂 ]