ABSTRACT
Markov random fields is n-dimensional random process defined on a discrete lattice. Usually the lattice is a regular 2-dimensional grid in the plane, finite or infinite. Markov Random Field is a new branch of probability theory that promises to be important both in theory and application of probability. The existing literature on the subject is quite technical and often only understandable to the expert. This paper is an attempt to present the basic idea of the subject and its application in image denoising to the wider audience. In this paper, a novel approach for image denoising is introduced using the ICM (Iterated Conditional Modes) approach of Markov Random Fields model.
INTRODUCTION
Many problems in Signal Processing can be cast in the framework of state estimation, in which we have state variables whose values are not directly accessible and variables whose values are available. Variables of the latter kind are also referred to as observations in this context. Usually there exists a statistical relationship between the state variables and the observations such that we can infer estimates of the states from the observations. In many cases prior knowledge about the states is also available (usually in form of a probability distribution on the state variables) and we can use that knowledge to refine the state estimate. In a variety of interesting problems, however, neither the statistical relationship between the state variables and the observations nor the prior distribution are perfectly known and hence are modeled as parameterized distributions with unknown parameters. These parameters are then also subject to estimation. In the domain of physics and probability, a Markov random field (often abbreviated as MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. A Markov random field is similar to a Bayesian network in its representation of dependencies; the differences being that Bayesian networks are directed and acyclic, whereas Markov networks are undirected and may be cyclic. Thus, a Markov network can represent certain dependencies that a Bayesian network cannot (such as cyclic dependencies); on the other hand, it can’t represent certain dependencies that a Bayesian network can (such as induced dependencies).
OPTIMIZATION
An optimization problem is one that involves finding the extremum of a quantity or function. Such problems often arise as a result of a source of uncertainty that precludes the possibility of an exact solution. Optimization in an MRF problem involves finding the maximum of the joint probability over the graph, usually with some of the variables given by some observed data. Equivalently, as can be seen from the equations above, this can be done by minimizing the total energy, which in turn requires the simultaneous minimization of all the clique potentials. Techniques for minimization of the MRF potentials are plentiful. Many of them are also applicable to optimization problems other than MRF. For example, gradient descent methods are well-known techniques for finding local minima, while the closely-related method of simulated annealing attempts to find a global minimum.
MATLAB SOURCE CODE
Instructions to run the code
- Copy each of below codes in different M files.
- Place all the files in same folder
- Also note that these codes are not in a particular order. Copy them all and then run the program.
- Run the “MAIN_GUI.m” file
Code 1 – GUI Function File – MAIN_GUI.m
function varargout = MAIN_GUI(varargin) % MAIN_GUI MATLAB code for MAIN_GUI.fig % MAIN_GUI, by itself, creates a new MAIN_GUI or raises the existing % singleton*. % % H = MAIN_GUI returns the handle to a new MAIN_GUI or the handle to % the existing singleton*. % % MAIN_GUI('CALLBACK',hObject,eventData,handles,...) calls the local % function named CALLBACK in MAIN_GUI.M with the given input arguments. % % MAIN_GUI('Property','Value',...) creates a new MAIN_GUI or raises the % existing singleton*. Starting from the left, property value pairs are % applied to the GUI before MAIN_GUI_OpeningFcn gets called. An % unrecognized property name or invalid value makes property application % stop. All inputs are passed to MAIN_GUI_OpeningFcn via varargin. % % *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one % instance to run (singleton)". % % See also: GUIDE, GUIDATA, GUIHANDLES % Edit the above text to modify the response to help MAIN_GUI % Last Modified by GUIDE v2.5 07-Oct-2013 19:54:21 % Begin initialization code - DO NOT EDIT gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @MAIN_GUI_OpeningFcn, ... 'gui_OutputFcn', @MAIN_GUI_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end % End initialization code - DO NOT EDIT % --- Executes just before MAIN_GUI is made visible. function MAIN_GUI_OpeningFcn(hObject, eventdata, handles, varargin) % This function has no output args, see OutputFcn. % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % varargin command line arguments to MAIN_GUI (see VARARGIN) set(handles.pushbutton5,'Enable','off') set(handles.pushbutton2,'Enable','off') set(handles.pushbutton3,'Enable','off') set(handles.pushbutton4,'Enable','off') % Choose default command line output for MAIN_GUI handles.output = hObject; % Update handles structure guidata(hObject, handles); % UIWAIT makes MAIN_GUI wait for user response (see UIRESUME) % uiwait(handles.figure1); % --- Outputs from this function are returned to the command line. function varargout = MAIN_GUI_OutputFcn(hObject, eventdata, handles) % varargout cell array for returning output args (see VARARGOUT); % hObject handle to figure % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % Get default command line output from handles structure varargout{1} = handles.output; % --- Executes on button press in pushbutton1. function pushbutton1_Callback(hObject, eventdata, handles) % hObject handle to pushbutton1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) [file,path]=uigetfile('*.tif','SELECT THE INPUT IMAGE'); img=strcat(path,file); inputimage=imread(img); if length(size(inputimage))==3 inputimage=rgb2gray(inputimage); end handles.inputimage=inputimage; axes(handles.axes1) imshow(handles.inputimage) set(handles.pushbutton5,'Enable','on') guidata(hObject, handles); % --- Executes on selection change in listbox1. function listbox1_Callback(hObject, eventdata, handles) % hObject handle to listbox1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) % Hints: contents = cellstr(get(hObject,'String')) returns listbox1 contents as cell array % contents{get(hObject,'Value')} returns selected item from listbox1 str = get(hObject, 'String'); val = get(hObject,'Value'); switch str{val}; case 'Gaussian' handles.CH=1; case 'Salt and Pepper' handles.CH=2; case 'Poisson' handles.CH=3; case 'Speckle' handles.CH=4; end guidata(hObject, handles); % --- Executes during object creation, after setting all properties. function listbox1_CreateFcn(hObject, eventdata, handles) % hObject handle to listbox1 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles empty - handles not created until after all CreateFcns called % Hint: listbox controls usually have a white background on Windows. % See ISPC and COMPUTER. if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end % --- Executes on button press in pushbutton2. function pushbutton2_Callback(hObject, eventdata, handles) % hObject handle to pushbutton2 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) covar=100; max_diff = 200; weight_diff = 0.02; iterations = 10; dst=handles.noisyimage; denoised = restore_image(dst, covar, max_diff, weight_diff, iterations); handles.denoised=denoised; set(handles.pushbutton3,'Enable','on') guidata(hObject, handles); % --- Executes on button press in pushbutton3. function pushbutton3_Callback(hObject, eventdata, handles) % hObject handle to pushbutton3 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) axes(handles.axes3) imshow(uint8(handles.denoised)) set(handles.pushbutton4,'Enable','on') guidata(hObject, handles); % --- Executes on button press in pushbutton4. function pushbutton4_Callback(hObject, eventdata, handles) % hObject handle to pushbutton4 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) X=handles.inputimage; XAPP1=handles.noisyimage; XAPP2=handles.denoised; [PSNRorigVSnoisy,MSEorigVSnoisy,MAXERR,L2RAT]=measerr(X,XAPP1); [PSNRorigVSdenoised,MSEorigVSdenoised,MAXERR,L2RAT]=measerr(X,XAPP2); %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % NEW PARAMETERS TO BE CALCULATED xyz=6; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% set(handles.text9,'String',(MSEorigVSnoisy)); set(handles.text12,'String',(MSEorigVSdenoised)); set(handles.text11,'String',(PSNRorigVSnoisy)); set(handles.text10,'String',(PSNRorigVSdenoised)); set(handles.text14,'String',xyz); % --- Executes on button press in pushbutton5. function pushbutton5_Callback(hObject, eventdata, handles) % hObject handle to pushbutton5 (see GCBO) % eventdata reserved - to be defined in a future version of MATLAB % handles structure with handles and user data (see GUIDATA) set(handles.pushbutton2,'Enable','off') set(handles.pushbutton3,'Enable','off') set(handles.pushbutton4,'Enable','off') I=handles.inputimage; if handles.CH==1 noisy = imnoise(I,'gaussian',0,0.001); elseif handles.CH==2 noisy = imnoise(I,'salt & pepper'); elseif handles.CH==3 noisy = imnoise(I,'poisson') ; elseif handles.CH==4 noisy = imnoise(I,'speckle',0.01); end handles.noisyimage=noisy; axes(handles.axes2) imshow(handles.noisyimage) handles.noisyimage=double(handles.noisyimage); set(handles.pushbutton2,'Enable','on') guidata(hObject, handles);
Code 2 – Function M FIle – restore_image.m
function otptimage=restore_image(inptimage,covar,diffM,diffW,itr) % create two images. one will be the input image, the other output. [row,col]=size(inptimage); % get the row and col of input image buffer = zeros(row,col,2); % make 2 empty frames of 0 values buffer(:,:,1) = inptimage; % put the input image in first frame, 2nd frame will contain the output image (let it be empty for now) s = 2; d = 1; V_max=(row*col) * ((256)^2/(2*covar) + 4*diffW*diffM);% it is a value larger then potential of any pixel value for i=1:itr % Switch source and destination buffers. if s==1 s=2; d=1; else s=1; d=2; end % Vary each pixel individually to find the values that minimise the local potentials. for r=1:row % row count for c=1:col % column count V_local=V_max; % initializing local potential value with the highest potential value min_val=-1; for val=0:255 V_data=(val-inptimage(r,c))^2/(2*covar); % component due to known data V_diff=0; % component due to difference btw neighbouring pixel values if r>1 % 2--row V_diff=V_diff+min((val-buffer(r-1,c,s))^2,diffM); end if r<size(inptimage,1) % 1--(row-1) V_diff=V_diff+min((val-buffer(r+1,c,s))^2,diffM); end if c>1 % 2--col V_diff=V_diff+min((val-buffer(r,c-1,s))^2,diffM); end if c<size(inptimage,2) % 1--(col-1) V_diff=V_diff+min((val-buffer(r,c+1,s))^2,diffM); end V_current=V_data + diffW*V_diff; % new potential value if V_current<V_local % decision rule` % [r c val] min_val=val; V_local=V_current; end end buffer(r,c,d)=min_val; end end end otptimage=buffer(:,:,d); end