IMAGE PROCESSING

" Two roads diverged in a wood, and I,
I took the one less traveled by,
And that has made all the difference "-Robert Frost

The first technique that we are going to learn during our exploration of Machine Learning techniques is Decision tree, a supervised learning method. For all the machine learning techniques, I will follow ‘Machine Learning in Action’ by Peter Harrington and will update the readers with the other recommended books when we encounter different concepts. Simple but effective and also the most used classification technique. When we have the dataset in the hand, it is important to learn about it and classify it in a most optimal way. Decision tree takes decision at each point and splits the dataset. It is a top down traversal and each split should provide the maximum information. The key advantage of this technique is when the dataset is huge and the number of features is also quite high then it is important to find the best features to split the dataset in order to perform efficient and optimal classification.

Let’s suppose that we have the following dataset.

 Channel Variance Image Type Monochrome low BW RGB low BW RGB High Color

We may try to split the dataset without evaluating the performance of each split,as shown below.

MATLAB CODE:

%Read and display the dataset and the Features
dataSet=[{'Mono',   'low''BW'},
{'RGB', 'low''BW'},
{'RGB', 'High', 'Color'}];

Features={'Channel','Variance'};

display(cell2table(dataSet,'VariableNames',[Features,'ImageType']));

Now let’s try to split the dataset by measuring the information. Measuring the information before the split and after the split provides the ‘Information Gain’
Measure the information by means of Entropy. Entropy is the expected value of the information.

Calculate the Entropy Before the Split

The final decision can be ‘BW’ that represents Black and White image or the Color Image.

MATLAB CODE:

function Entropy = Calculate_Entropy(dataSet)

Rlabel = {dataSet{:,size(dataSet,2)}}'; %Extract the last column (i.e) Assuming that the last column is the Final decision or Outcome
uqlabel = unique(Rlabel);    %Find all the labels and eliminate the duplicates
Entropy = 0; %Initialize the Entropy
for k=1:size(uqlabel,1)
ProbC = sum(ismember(Rlabel,uqlabel{k}))/size(dataSet,1); %Probability of the unique value occuring in the whole feature's column
Entropy = Entropy-(ProbC*log2(ProbC)); %Shanon Entropy Estimation
end

end

Calculate the Entropy After the Split

Now to find the best feature to make the split, do the following:
·         Initialize Best Feature as NULL or zero
·         Initialize Best Information Gain =0;
·
Extract the values of the first feature (i.e) Channel

·         Find its Entropy with respect to the feature ‘Channel’ for all the unique values
Create Subsets based on the unique values in the feature ‘Channel’ is ‘Mono’ and ‘RGB’
Subset Mono,
 Image Type BW

Subset RGB,
 Image Type BW Color

·         Compare the Entropy Before the split and Entropy of the first feature.
If the difference between the Before_Entropy and Entropy of the first feature > Information Gain then Best Information Gain = Information Gain and Best Feature is the first feature.
Information Gain= Before Entropy – Entropy of the first feature
= 0.9183– 0.666
= 0.2516
Information Gain (0.2516) > Best Information Gain(0)
 Best Information Gain 0.2516 Best Feature Channel

·
Now extract the values of the Second feature(i.e) Variance

·         Find its Entropy with respect to the feature ‘Variance’ for all the unique values
Create Subsets based on the unique values in the feature ‘Variance’ is ‘low’ and ‘High’
Subset low,
 Image Type BW BW

Subset High,
 Image Type Color

·         Note that Entropy is zero  denotes the best split.
·         Compare the Entropy Before the split and Entropy of the second feature
If the difference between the Before_Entropy and Entropy of the Second feature > Information Gain then Best Information Gain = Information Gain and Best Feature is the Second feature
Information Gain=0.9183(Before_Entropy) – 0(Entropy of the first feature) = 0.9183
Information Gain (0.9183) > Best Information Gain(0.2516)

 Best Information Gain 0.9183 Best Feature Variance

MATLAB CODE:
function Best_Feature = find_Best_feature(dataSet,Base_Entropy)
Best_Info = 0; %Initialize the Best Information Gain
Best_Feature = 0; %Initialize the Best Feature
for ind = 1:size(dataSet,2)-1
%Traverse through all the columns in the dataSet
Rlabel = {dataSet{:,ind}}';
uqlabel = unique(Rlabel); %Find the unique values in each column
New_Entropy = 0;

for k = 1:size(uqlabel,1)
ProbC = sum(ismember(Rlabel,uqlabel{k}))/size(dataSet,1); %Find the occurance of the unique value
SubSet = [dataSet(ismember(Rlabel,uqlabel(k)),size(dataSet,2))]; %Find the subset that corresponds to the unique values of that particular column
New_Entropy = New_Entropy + (ProbC.*Calculate_Entropy(SubSet)); %Calculate the entropy with respect to the particular column or the Feature
end

%Information Gain obtained from the difference between the before and after split
Info_Gain = Base_Entropy-New_Entropy;

if(Info_Gain>Best_Info)
Best_Info = Info_Gain;
Best_Feature = ind;
end

end
end

Traverse through the dataset until the leaf node is reached
The First feature that will be used to split the dataset is ‘Variance’ and now the other features are traversed to either reach the final result or split further with respect to the other feature.
·         Select the best feature column
·         Find the unique values, ‘low’ and ‘High’
·         Obtain the subset based on the unique values,
·         For the value ‘low’
 Variance Image Type low BW low BW
Since the result is homogenous as it is evident from the above table, it can be stated as
If variance is low then Image Type = ‘BW’
For the value ‘High’
 Variance Image Type High Color

If variance is High then Image Type = ‘Color’
·         If the result is not homogeneous, then we can further proceed with finding the best feature until we obtain homogeneous results.

Finally, the decision tree with the best split is constructed as shown below.

MATLAB CODE:
function tree=Traverse_tree(dataSet,Best_Feature,Features,Ranges,tree)
%Find the best features and the nodes
Rangeval=Ranges(Ranges~=Best_Feature);
Rlabel={dataSet{:,Best_Feature}}';
uqlabel=unique(Rlabel);

sz=size(tree,2);
Prev=tree{sz}.Prev+1;
for k=1:size(uqlabel,1)
Uprev=Prev;
SubSet = [dataSet(ismember(Rlabel,uqlabel(k)),Rangeval)];
Tlabel=unique({SubSet{:,end}}');
if(numel(Tlabel)==1) %Homogeneous or same result
%To store the conditions and then correspoding leaf nodes
sz=sz+1;
tree{sz}.node=char(uqlabel(k));%Condition Example: 'Low', 'Yes'
tree{sz}.Prev=Uprev;
sz=sz+1;

tree{sz}.node=char(Tlabel); %Final Decision Example:'BW,'Color'
tree{sz}.Prev=Uprev+1;

else
%Not Homogeneous then Calculate Entropy and Find the best
%Feature for the Subset and repeat the procedure
Base_Entropy=Calculate_Entropy(SubSet);
Best_Feature=find_Best_feature(SubSet,Base_Entropy);
%To store the conditions and then correspoding leaf nodes
sz=sz+1;
tree{sz}.node=char(uqlabel(k));
tree{sz}.Prev=Uprev;
sz=sz+1;
tree{sz}.node=char(Features(Best_Feature));
tree{sz}.Prev=Uprev+1;

Features1={Features{~ismember(Features,Features{Best_Feature})}};
%Find the homogeneous result for the Subset
tree= Traverse_tree(SubSet,Best_Feature,Features1,[1:numel(Rangeval)],tree);
sz=size(tree,2);
end

end
end

Here is an example with the real data sets to examine the decision tree that we created using the information gain. ‘Classification of Black and White Image and Color Image

Here’s another Example with somewhat messed up dataset and let’s see how to decide on the splits. Instead of determining whether the image is BW(Black and White) or Color, the dominating Color in the image will also be taken into account. Here, it is clear that the number of features and the values in each feature has increased. The ‘DominantB’ feature indicates the amount of black or gray pixels in the image. It can be high, low or medium.

 Channel Variance DominantB ImageType Monochrome low High Black Monochrome low low White Monochrome low Medium BW RGB low High Black RGB low low White RGB low Medium BW RGB High High Color RGB High low Color

MATLAB CODE:

display(cell2table(dataSet,'VariableNames',[Features,'ImageType']));

Base_Entropy = Calculate_Entropy(dataSet); %Base Entropy = 2
Best_Feature = find_Best_feature(dataSet,Base_Entropy); %Best Feature=3
%To store the nodes and Features
tree={};
tree{1}.node = char(Features{Best_Feature});
tree{1}.Prev = 0;
Features = {Features{~ismember(Features,Features{Best_Feature})}};
tree = Traverse_tree(dataSet,Best_Feature,Features,[1:4],tree);
draw_tree(tree);

To conclude, we have seen a supervised method that works on nominal values. The main disadvantage of this method is that it cannot handle continuous values. Let’s see in the upcoming posts on how decision tree can be altered to suit the data  sets with continuous values.
Like "IMAGE PROCESSING" page