University of Twente Student Theses


Graph cuts for fast optimization in Markov Random Field based Remote Sensing image analysis

Karimov, Abdulmain (2010) Graph cuts for fast optimization in Markov Random Field based Remote Sensing image analysis.

[img] PDF
Abstract:Optimization of energy is a challenging issue in Markov Random Field (MRF) based remote sensing image analysis. Traditional energy minimization methods such as Iterated Conditional Modes (ICM) and Simulated Annealing (SA) are widely used to deal with this problem. ICM does not provide a globally best estimation but it concentrates on local area and it does not provide optimal solution. SA is used to find globally optimal solutions for MRF based image analysis problems which allow approximating the global minimum of energy function that produces better quality of solutions, but at it takes long computational time to approximate the global minimum. Therefore, in order to address this problem faster energy minimization methods from vision are proposed. The applicability of graph based methods such as swap-move and expansion-move algorithms in MRF based remotely sensed images have been proposed and studied in this research. A number of methods are proposed that address multi label (class) image classification problem, which make use of class separability measures. Based on these measures classification trees are constructed. Each level of tree nodes represents a particular class. These methods show how the sequence (order) of tree nodes can have an impact on classification result. The most appropriate method among them is selected that best represents the reality. In addition, a method is proposed that used to optimize the smoothness values based on “trial and error” method. Its main issue is to identify the optimal smoothness value, i.e. the value that is most suitable for specific spectral classes. The results show that these smoothness values are more sensitive to spectral classes that are least separated, and less sensitive to those that most separated. The “least” and “most” separated issues are based on divergence - class separability measures. The results of swap-move and expansion-move algorithms are compared with MLC, ICM and SA. Different smoothness parameters are chosen and tested for each energy minimization method. The results of swap-move and expansion-move algorithms are similar to SA annealing with logarithmic cooling schedule, which is considered able to approximate the global optimal solution. In terms of computation, these algorithms outperformed the SA algorithms and in some cases ICM also. In comparison with MLC, the swap-move and expansion-move algorithms produce better results. In conclusion, swap-move and expansion-move algorithms show that they are applicable in MRF based remote sensing image classification. Their performances, both in terms of computation and classification accuracy are considered sufficient to address the research problems. Although in some cases they are not able to fully detect trees, mainly due to similarity in spectral properties of trees and grassland classes. In addition, the proposed methods for construction of classification tree and optimising smoothness value showed their significant importance in addressing a multi label image classification problem. Key words: Markov Random Field, local optimization, global optimization, graph cuts, swap-move, expansion-move, performance evaluation, computational time, Simulated Annealing (SA), logarithmic cooling schedule, exponential cooling schedule, classification tree, tree nodes, optimizing of smoothness value, least separated class, most separated class .
Item Type:Essay (Master)
Faculty:ITC: Faculty of Geo-information Science and Earth Observation
Programme:Geoinformation Science and Earth Observation MSc (75014)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page