text:
% mainfile: ../../../../master.tex
\subsection{Python 3 and Windows Compatibility}
% The part of the label after the colon must match the file name. Otherwise,
% conditional compilation based on task labels does NOT work.
\label{task:20140903_jkn0}
\tags{development}
\authors{jkn}
\files{newBuild.py,addTask.py,changeAuthor.py,changeTag.py}
%\persons{}
I have discovered that many of the problems that I observed with cross-platform compatibility were causes by different encoding of files. Therefore, I have decided to store and read all files with the UTF-8 encoding using the {\tt io} module. In addition to updating the Python scripts with this, I have also updated the preamble and the user guide with a warning about changing the encoding.

max_stars_repo_name: jkjaer/latexResearchDiary

max_issues_repo_name: jkjaer/latexResearchDiary

max_forks_repo_name: jkjaer/latexResearchDiary


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  BIO-SPECTRAL IMAGING REVIEW
%%	Onur Ozcelik, Sabri Bolkar
%%
%%	Summer 2015
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%% STARTING %%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[a4paper]{article}

%%%%%%%%%% PACKAGES USED %%%%%%%%%%%%%%%%%%%%

    \usepackage[english]{babel}
    \usepackage[utf8x]{inputenc}

    % package for including graphics with figure-environment
    \usepackage{graphicx}
    \usepackage{hyperref}
    \usepackage{mathtools}
    % colors for hyperlinks
    % colored borders (false) colored text (true)
 \hypersetup{colorlinks=true,citecolor=black,filecolor=black,linkcolor=black,urlcolor=black}

    % package for bibliography .... BIBTEX
  %  \usepackage[authoryear,round]{natbib}

    % package for page header
    \usepackage[automark]{scrpage2}
    \pagestyle{scrheadings}
    \ihead[]{Bio-Spectral Imaging: A Review} %%%%% Head writings
    \ohead[]{\date}                 %%% date ?????????
    \cfoot[]{\pagemark}
    \setheadsepline[122mm]{0.3mm}

    \usepackage[nottoc,numbib]{tocbibind} %%%% references appear in contents
%%%%%%%% BODY STARTS %%%%%%%%%%%%%%%%%%%%%%%

    \begin{document}
        \title{
        \begin{figure}[!ht]
            \flushleft
                \includegraphics[width=1\textwidth]{metu_logo.jpg}
        \end{figure}
        \vspace{1cm}
        \Huge Bio-Spectral Imaging: A Review
        }

        \vspace{1cm}

        % if you are the only author, you might use the following
        % \author{Name of student}

        % Insert here your name and correct mail address
        \author{\Large \href{mailto:first.student@smail.fh-koeln.de}{
        Onur {\"O}z{\c{c}}elik} \and \Large \href{mailto:second.student@smail.fh-koeln.de}{Sabri Bolkar} %%%% ADD MAILS
        \vspace{1cm}}

        % name of the course and module
        \date{
       %% \large Module: Modulename \\ Course: Coursename \\
        \vspace{0.8cm}
        \large Supervisor: Asst.
        Prof. Sevin{\c{c}} Figen {\"O}ktem \\
        \vspace{1cm}
        \large %%% DATE ?
        }

        \maketitle
        \setlength{\parindent}{0pt}

    \vspace{2cm}

%%%%%%%%%%%%%%%%%% ABSTRACT %%%%%%%%%%%%%%%%

    \begin{abstract}
	 Spectral Imaging is a promising optical technique that combines advantages of both spectroscopy and imaging in an unique way. It offers a noninvasive diagnostic method for numerous diseases especially for the ones that originates from epithelial tissues. Herein, this report gives an introductory overview of bio-spectral imaging and its main medical applications. It also briefly describes system hardware and main instruments that constitute bio-spectral imaging devices.
    \end{abstract}

%%%%%%%%%%%%%%%%%%%%% INTRODUCTION %%%%%%%%%

        \newpage
        \tableofcontents
        \vspace{3cm}
        \listoffigures
        \newpage

    \section{Introduction} % (fold)
    \label{sec:Introduction}
	$\hspace{5mm}$ Spectral Imaging is a very special imaging method which extracts characteristic spectral information of elements covering the imagined area. Unlike other optical imaging methods (e.g., optical coherence tomography, optical diffuse tomography) which are monochromatic in their nature, spectral imaging utilizes different band gaps of electromagnetic spectrum and combines them to acquire all the available chemical fingerprints of ingredients as much as the current technology allows. Because of this reason, data in SI systems is stored as 3D cubes (x, y, $\lambda$) rather than mere 2d monochromatic images. As put by Qin, It can also be described as a very special multidimensional spectroscopy device that applies spectroscopic measurement for each point in imagined area: "If conventional imaging tries to answer the question \emph{where} and conventional spectroscopy tries to answer the question \emph{what}, then hyperspectral imaging tries to answer the question \emph{where} is \emph{what}" \cite{sifir}.
    \medskip
    \begin{figure}[h]
		\includegraphics[width=0.5\textwidth]{3dcube.jpg}
			\centering
         \caption{3d Data Cube (Source: Zeiss-Campus)}
	\end{figure}

     $\hspace{5mm}$ In the scientific literature, spectral imaging modality (i.e., imaging spectroscopy, once it was called) is divided into four main groups according to amount of spectral bands scanned. Names of research groups also indicate number of wavelengths utilized (i.e., Multispectral, hyperspectral and ultraspectral imaging). The term multispectral imaging is used to express the method that utilize only a few wavelengths to extract information. Hyperspectral imaging, Unlike multispectral imaging, includes hundreds of overlapping contagious bands, and ensures no spectral bands are skipped. And, ultraspectral imaging is much more advanced technique that includes thousands of contagious bands.

\medskip
    $\hspace{5mm}$If conventional color cameras are to be compared with spectral imaging cameras, huge differences can be observed. Traditional cameras usually uses a single imaging chip which consists of color filters covering every pixel of a sensor. Each pixel of the sensor can detect only one of the three primary colors. Therefore, three pixels are required to detect the color of the area. Color cameras record three spectral bands simultaneously to obtain the color image and represent the image with three parameters: Red-Green-Blue, or RGB (figure 2). This cameras emulates the human vision and easy to interpret. However, similar to human vision, they have limitations. They misses spectral information outside of the three bands which is important for identifying a material. Therefore, color imaging systems cannot distinguish between different materials with the same color. This significantly limits diagnostic capabilities of color cameras and unveils the need for a more advanced system. This problem can be pointed as the main motivation behind spectral imaging architecture. Since, they obtain images at many wavelengths which are not recognizable by human vision and carries unique information about many materials which are not available with RGB cameras.
    \medskip
    \begin{figure}[h]
		\includegraphics[width=0.8\textwidth]{rgb.jpg}
			\centering
         \caption{Spectral Scanning - comparison of RGB, multispectral and hyperspectral imaging methods}
	\end{figure}

    \section{Origins of Bio-Spectral Imaging}
    \label{sub:origins_of_Bio-Spectral_Imaging}

    $\hspace{5mm}$ The idea to use several spectral signatures of elements dates back to 1970's when a detailed analysis was needed for remote sensing applications (i.e., NASA  Landsat-1 in 1972 transferred intense spectral data). As put by Alexander Goetz, who is the main figure behind this miraculous method, it was the enormous noisy data that led this great invention: "No single material requires hundreds of spectral bands spread over several octaves of the electromagnetic spectrum to be identified uniquely. However, when mixed with many other materials on the Earth's surface and viewed through a hostile and changing atmosphere, there is security in numbers." But, at that time the problem was the limited technology to analyze collected data since improvements in the field was highly stick to the advances in computational power. It was 90's when spectral imaging technique fully exploited \cite{bir}. A timeline for spectral imaging airborne and satellite cameras can be viewed in figure 3.
    \medskip
    \begin{figure}[h]
		\includegraphics[width=0.9\textwidth]{timeline.jpg}
			\centering
         \caption{Timeline of three different categories of spectral imaging, along with synthetic aperture radar (SAR) imaging \cite{iki}}
	\end{figure}

    $\hspace{5mm}$ Before 90's, remote sensing SI devices were not suitable for laboratory use and for bio-applications because of their high cost, large size and complexity. However, after late 80's, advances in computational power and increase in availability of low cost sensors (e.g., CCD detectors) enabled biomedical implementation of spectral imaging technique \cite{uc}. One of the early successful application of the technique came with the name SpectraCube\texttrademark 1000, developed in 1994 by a team from Bar Ilan University and Spectral-Diagnostics\texttrademark \cite{dort}. It stands as the first successful implementation of the idea. Although the system's spatial resolution was quite low (just 170$\times$170), it was able to observe subcellular characteristics of cells (i.e., visualization of chromatin packing, determination of porphyrin level and distribution of cytoplasmic organelles). Later, spectral imaging had become more common in biomedical society. Institutions started to create their own spectral imaging devices for many other diagnosis and research purposes. More detailed analysis of these different spectral imaging systems will be given in the following sections of the article.

%%%%%%%%%%%%%%%%%  HARDWARE OVERVIEW %%%%%%%%%%%%

	\section{Hardware of Bio-Spectral Imaging Devices: Instruments}
    \label{sec:Hardware_of_Bio-Spectral_Imaging_Devices}
    \hspace{5mm} A typical bio-spectral imaging system consists of five main instruments: \emph{Light source} to create information carrier signal interacting with matter, \emph{wavelength dispersion device} to read spectral information from white light, \emph{imaging detector} such as CCD and CMOS area detectors, \emph{data analysis element} (e.g., computer) and \emph{calibration module} for spectral and spatial calibration (figure 4), for most of the modern systems calibration module and other peripherals are embedded to the main computer to ease the control of the information flow.
    \medskip
    \begin{figure}[h]
		\includegraphics[width=0.9\textwidth]{system.jpg}
			\centering
         \caption{SI system overview}
	\end{figure}

    \hspace{5mm} The core part of the bio-spectral imaging architecture is the light source. Unlike its predecessor remote sensing hyperspectral imaging systems, bio-spectral imaging devices uses active light to acquire knowledge from the sample (i.e., if natural light sources are used, the system is called passive imaging system as in the case of most of the remote sensing applications). The main aim of the light source is to create the means of interaction with material to be scanned. Instruments utilized as imaging light sources are: Halogen lamps, light emitting diodes (LED), lasers. There exist also another type of sources which are called tunable sources. Systems using this approach are rather different with respect to system architecture. They reverse the order and place dispersion element before sample, so that matter interacting light become dispersed \cite{sifir}.

    \medskip
    \hspace{5mm} The system element dispersing broadband light to its monochromatic constituents is called wavelength dispersion device. Because imaging sensors are physically color blind (i.e., they are only sensible to specific photon energy levels, only specific monochromatic light), broadband light has to be dispersed to be able to measure intensity level for each wavelength. Main instruments utilized for this purpose are: Interferometers (e.g., Michelson Interferometer, Sagnac Interferometer), imaging spectrographs, filter wheels, Acousto-optic tunable filters (AOTF), liquid crystal tunable filters (LCTF) and specialized dispersion devices used in snapshot imaging methods \cite{bes} \cite{sifir}.

    \medskip
    \hspace{5mm} Third major component of bio-spectral imaging systems are area detectors. After dispersion of spectral information carrier light, components of light are directed to CCD and CMOS image sensors. They differ from traditional spectroscopy detectors and are able image an configured area (i.e., in spectroscopy, point detectors are used).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \section{Fundamentals of Bio-Spectral Imaging} % (fold)
    \label{sec:Fundamentals_of_Bio-Spectral_Imaging}
    \hspace{5mm} Interaction of light with targeted tissue is the most important research topic in bio-spectral imaging. As the information carrying medium, light should be able to penetrate the tissue to reach the target, interrogate with cells and it also should be recaptured by sensors to acquire related information \cite{bes.1}. In each of these processes, there exist deep bio-physical interaction models and theories which are above the scope of this article. But, it is essential to delve into fundamental ideas about tissue optics and discussions why spectral imaging is a great choice of diagnosis technique.

    \medskip
     \hspace{5mm} There exist four main interactions of light photons with matter: Absorption, refraction, scattering and transmission, all of which occur at atomic scale and alter the state of light according to characteristic differences of interacted cells. In addition to these fundamental processes, there are also some additional optical parameters that can be used to characterize tissues such as anisotropy (i.e., directional dependency of interacting materials) and reduced scattering \cite{bes.1}. The first process light undergoes is absorption, the later processes are possible when energy level of light photon is not suitable for absorption, and photon escapes from first danger. After interacting with matter (e.g., scattered, refracted) photon's energy level is lowered and probability of absorption increases. In all of these interactions light carries embedded fingerprints of the chemical structure even in absorption. Since, after absorption increase in the energy of the material may lead to re-emission or heat generation (even chemical reactions) that makes materials observable \cite{bes.2}.
       \medskip
    \begin{figure}[h]
		\includegraphics[width=0.7\textwidth]{light_tissue.jpg}
			\centering
         \caption{Light Tissue Interaction \cite{onbir}}
	\end{figure}

    \hspace{5mm} Most tissues in human body are heterogeneous; therefore, spatial variations can be seen in their optical properties. Because of spatial variations, most of light photons are scattered within human tissues \cite{alti}. The penetration depth of light into tissues depends on how strongly light is absorbed by these tissues. Most tissues cannot absorb enough light to permit it to penetrate significantly in the spectral range from 600 to 1300 nanometer, known as diagnostic window. Within this window, the propagating light becomes diffuse because scattering is dominant over absorption \cite{alti} \cite{yedi}. In tissues, absorption is a function of molecular composition, whose changes at specific wavelengths could provide a spectral fingerprint of the molecule for diagnosis \cite{alti} \cite{sekiz}. Light absorbed by tissues could be radiated as fluorescence. Ultraviolet and visible light usually excite the molecules of the tissues and causes fluorescence emission. Different fluorescence emission spectra could be observed in different cells which are in different disease states. Therefore, fluorescence imaging can be used to inspect tissues for medical diagnosis \cite{yedi}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \section{Classification of Imaging Systems} % (fold)
    \label{sec:Classification_of_Imaging_Systems}

    \subsection{According to Spatial Scanning Methods} % (fold)
    \label{sub:According_to_Spatial_Scanning_Methods}

    \hspace{5mm} Monochrome sensors used in spectral imaging systems can capture only two of three spectral dimensions (x, y, $\lambda$) of the spectral cube at a time. Spatial or spectral scanning methods are used to capture the third dimension \cite{dokuz}. The whiskbroom, pushbroom, staring and snapshot (single exposure) methods are commonly used in bio-spectral imaging applications \cite{bes}.

     \medskip
	 \hspace{5mm} In Whiskbroom method, spectrum ($\lambda$) of a single point is obtained by sensor arrays at a time and the point is scanned along two spatial dimensions (x and y). In Pushbroom method, one spatial dimension (x) and spectrum ($\lambda$) is obtained with a 2D detector array and the other spatial dimension (y) is captured with line scanning. Whiskbroom and Pushbroom methods require a lot time to acquire spectral cube because they do spatial scanning and intense data processing is required. Another disadvantage of these methods is that they usually require complex hardware configurations. In Whiskbroom and Pushbroom methods, light is divided by a dispersive element (prism or grating), which makes them efficient and low-cost \cite{bes}.

	 \medskip
	 \hspace{5mm} Pushbroom method is suitable for searching an object with specific spectra, because line-scan provides the entire spectrum of each pixel in real time. With Pushbroom method, the entire spectral cube does not have to be collected. For a known spectrum, a classified image can be assembled by identifying the spectrum in each spectral line scan \cite{on}

	\medskip
	 \hspace{5mm} In Staring method, full spatial image (x and y) is obtained at once with a 2D sensor array while the spectrum ($\lambda$) is scanned. Instead of the dispersive element used in Whiskbroom and Pushbroom methods, tunable filters are used in this method and because of that, the spectral cube can be acquired in a simpler way without any relative motion of the scene and the imager \cite{oniki}. In staring method, the number of spectral bands scanned can be determined by the user and a dynamic range can be maintained \cite{bes}. Also, in clinical applications, staring spectral imagining devices become more suitable when imagined area is exposed to wide field (broadband) illumination \cite{dokuz}.

	\medskip
	 \hspace{5mm} In Snapshot method, the spatial image (x and y) and the spectrum ($\lambda$) is obtained in a single exposure. One of the advantages of the snapshot method is that spectral image can be captured faster than other methods. Therefore, it can be used in studies in endoscopy detection, fluorescent probes analysis and retinal oxygen saturation measurement. Another advantage of this method is high reliability and robustness since snapshot imagers has no moving parts. It also provide high throughput because there are no multiplex losses. The disadvantage of the snapshot method is low spatial resolution because the size of the spectral cube depends on the size of the CCD sensor used in the imager \cite{alti}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \subsection{According to Spectroscopic Measurement Types} % (fold)
    \label{sub:According_to_Spectroscopic_Measurement_Types}

            \medskip
            \hspace{5mm}The other type of classification is based on measurement methods. To collect spectral data from different type of tissues, several techniques have been developed. All of the methods will be discussed have various advantages over others, especially when analyzing different tissues having unique optical characteristics. Therefore, considerations related with optical properties of tissues are crucial when choosing the optimal imaging modality.

            \medskip
           \subsubsection{Near-infrared Spectral Imaging (NIR-SI)}
           \hspace{5mm} NIR spectroscopy has already been used in some applications such as measurement hemoglobin concentration and blood oxygen saturation \cite{onuc}. Near-infrared imaging can be used as a complementary method for tissue characterization and diagnosis of cancer because of its ability to distinguishing normal tissue from diseased tissue. NIR light between 700 and 900 nm is mostly scattered in tissues and it can reach deep tissues. Unlike the other imaging methods such as X-ray and MRI, extra harmful radiation or radioactive materials are not used in NIR imaging \cite{ondort}.

           \subsubsection{Reflectance SI}
           \hspace{5mm} Diseased tissues interact with light in some ways like elastic scattering and absorption. When light interacts with a diseased tissue, the effect of the disease on the tissue causes some changes in the patterns in the light. These changes can be seen on the light reflected from the tissue. There are several studies investigating the applications of reflectance spectroscopy for tissues in cervix, breast, oral cavity, lungs, esophagus and gastrointestinal tract. There are also applications of reflectance spectroscopy for brain tumors, ovarian cancer, bladder cancer and skin cancer \cite{onbes}.

            \subsubsection{Fluorescence SI}
            \hspace{5mm} Fluorescence is used in a wide range of applications such as fluorescence microscopy, DNA sequencing, flow cytometry and fluorescence-based immunoassays. In biomedical applications, fluorescence spectroscopy has been being investigated for applications such as characterizing cardiac tissue, analyzing blood and early detection of cancer, particularly those in the cervix, oral cavity, breast, brain, skin, esophagus and bronchus \cite{onalti}.

            \subsubsection{Light Scattering SI}
            \hspace{5mm} Light scattering spectroscopy (LSS) allows investigating the structure of epithelial cells without removing them. With the use of LSS, Images of some histological properties (e.g., nuclear enlargement, pleomorphism and increased chromatin content) can be obtained. LSS imaging shows promising results for investigation of nuclear changes resulting from cancer and other diseases, particularly cancer in cervix and oral cavity \cite{onalti.1}. Light scattering spectroscopy also shows promise for the precise classification of invisible dysplasia in real time \cite{onalti.2}.

            \subsubsection{Raman Scattering SI}
            \hspace{5mm} Raman spectroscopy can provide information about chemical and molecular properties of tissues without destructive effects and external contrast-enhancing substances. Most of the reported studies about Raman spectroscopy examined its applications in skin, although there are studies investigating its  applications in bone, brain, gastrointestinal tract, artery, breast, urinary tract, uterus, lung, and eye \cite{onalti.3}. Since it consists of a lot of components (e.g., lasers, filters, microscope objectives), Raman spectroscopy is compatible with other methods of biomedical optics such as confocal laser-scanning, optical coherence tomography and angularly resolved elastic scattering \cite{onalti.4}.

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%

\section{Spectral Imaging Data Analysis} % (fold)
    \label{sec:Spectral_Imaging_Data_Analysis}

    \hspace{5mm} It can be stated that diagnosis process and medical treatment cannot be possible without processing of acquired spectral data. Complexity and noisiness of raw data makes it cumbersome  to comprehend even for expert physicians. Therefore, to extract relevant feature, data is processed. General procedure for processing can be viewed in figure 6.

    \begin{figure}[h]
		\includegraphics[width=0.7\textwidth]{dataAnaly.jpg}
			\centering
         \caption{Data Processing Steps}
	\end{figure}

	\subsection{Preprocessing}

    \hspace{5mm} The first step in data processing is preprocessing. As the name implies preprocessing is preparation step before real analysis is done. The data acquired by SI devices include thousands of pixels and wavelengths. Processing of high dimensional data is harder and inefficient (i.e., classification algorithms check unneeded data), therefore various preprocessing methods have been developed by engineers. In addition to its main aim easing the way to extract features, preprocessing also serves for another purpose that is decreasing so-called curse of dimensionality \cite{dokuz}.

    \medskip
    \hspace{5mm} Curse of dimensionality is accepted as one of the most important issues in machine learning field. The term was coined in 1961 by Richard Bellman while he was working of dynamic optimization \cite{onyedi}. This infamous term has been popularized because of its counter-intuitive results. Increasing data dimension may lead to expectation of more accurate results, but in contrast it is the high dimensional data itself scrambles the classifier. This strange outcome is the main reason for necessity of a preprocessor to lower data dimension.
It should be stated that preprocessing algorithms are optimized not to lose any information while decreasing dimension of data \cite{onsekiz}. Principal component analysis is one of the main methods for preprocessing applications, there exists also an advanced form of PCA called independent component analysis (ICA) which can also be used as preprocessor, but it's mainly used as classifier especially for brain signal analysis. A detailed and simplified information about PCA can be found in Shlen's famous tutorial \cite{ondokuz}.

    \subsection{Classification}

    \hspace{5mm} After removal of redundancy in data by preprocessing algorithms, remaining data space is fed to classifier. Classifier is the main part in machine learning systems where data is separated according to their feature components each having unique characteristics. There are various ways to do that job, but classifiers are generally divided into two groups: Supervised Clustering and Unsupervised Clustering.

     \begin{figure}[h]
		\includegraphics[width=0.6\textwidth]{Class.png}
			\centering
         \caption{Main classifier algorithms}
	\end{figure}

    \newpage

    \hspace{5mm} Both supervised and unsupervised methods depends upon statistical resemblance mapping in which data points are selected and classified to maximize (or minimize) targeted statistical parameter. Discussion related with classification algorithms is out of the scope of this paper because of intense research done on machine learning algorithms. But, some of the most used algorithms can be viewed in Figure 7.

    \subsection{Spectral Unmixing}

    \hspace{5mm} Distribution of materials in spectral data cube is generally heterogeneous; and a single pixel does not contain just one type of material. Therefore, there is a need for sub-pixel analysis. The method to extract sub-pixel features is called \emph{Spectral Unmixing}. It is used to approximate material ingredients using known spectral of materials and pixel's spectra. In other words, it is in a way a sub-pixel spectral decomposer for spectral imaging systems \cite{yirmi}.

     \begin{figure}[h]
		\includegraphics[width=1\textwidth]{unmix.png}
			\centering
         \caption{Taxonomy of Unmixing Algorithms \cite{yirmi}}
	\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
	\newpage
    \section{Conclusion} % (fold)
    \label{sec:conclusion}

    \hspace{5mm} We have presented mainstream spectral imaging applications in medical diagnosis and treatment. The article is aimed to be an introductory text for explaining general concepts without going into too much detail. In addition to medical applications and spectral imaging methods, SI instruments, brief history of hyperspectral imaging and data analysis techniques are also discussed. We also referenced most cited and inclusive articles that fit best for beginners in the bio-spectral imaging research field, therefore further investigation can be easily done through reading sources referenced.

    \medskip
    \hspace{5mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%	\section{Glossary}
  %%  \label{sec:Glossary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% REFERANCES

   %% \bibliographystyle{natdin}  .... BIBTEX
     %%   \bibliography{references} % expects file "references.bib"

\begin{thebibliography}{9}

\bibitem{sifir} Qin, J. (2010). Hyperspectral Imaging Instruments. Da-Wen, S.(ed.) in \emph{Hyperspectral Imaging for Food Quality Analysis and Control}. Elsevier. http://doi.org/10.1016/B978-0-12-374753-2.10005-X

\bibitem{bir} Goetz, A. F. H. (2009). Three decades of hyperspectral remote sensing of the Earth: A personal view. \emph{Remote Sensing of Environment}, 113(SUPPL. 1), 5–16. http://doi.org/10.1016/j.rse.2007.12.014

\bibitem{iki} Shaw, G. Burke, H. (2003). Spectral Imaging for Remote Sensing. \emph{Lincoln Lab. Journal}, 14(1).

\bibitem{uc} Garini, Y., Katzir, N., Cabib, D., Buckwald, R. a, Soenksen, D. G., Malik, Z. (1996). Spectral Bio-Imaging. \emph{Fluorescence Imaging Spectroscopy and Microscopy.}

\bibitem{dort} Zvi Malik ; Dario Cabib ; Robert A. Buckwald ; Yuval Garini and Dirk G. Soenksen "Novel spectral imaging system combining spectroscopy with imaging applications for biology", Proc. SPIE 2329, \emph{Optical and Imaging Techniques in Biomedicine}, 180 (February 1, 1995)

\bibitem{bes} Li, Q., He, X., Wang, Y., Liu, H., Xu, D., and Guo, F. (2013). Review of spectral imaging technology in biomedical engineering: achievements and challenges. \emph{Journal of Biomedical Optics}, 18(10), 100901. http://doi.org/10.1117/1.JBO.18.10.100901

\bibitem{bes.1} Jacques, S. L. (2013). Optical Properties of Biological Tissues: A Review. \emph{Physics in Medicine and Biology}, 58(11), R37–61.

\bibitem{bes.2} Walsh, J. (2011).Basic Interactions of Light with Tissue. Welch, A. J.,  Van Gemert, M. J. C.(ed.) In \emph{Optical-thermal response of laser-irradiated tissue}, 1–958. http://doi.org/10.1007/978-90-481-8831-4

\bibitem{alti} Joel, M. (2003). Optical Properties of Tissues. Vo-Dinh (ed.) In \emph{Biomedical Photonics Handbook}. CRC Press.

\bibitem{yedi} Lu, G., and Fei, B. (2014). Medical hyperspectral imaging: a review. \emph{Journal of Biomedical Optics}, 19(1), 10901.

\bibitem{sekiz} Zhang, Y., Chen, Y., Yu, Y., Xue, X., Tuchin, V. V, and Zhu, D. (2013). Visible and near-infrared spectroscopy for distinguishing malignant tumor tissue from benign tumor and normal breast tissues in vitro. \emph{Journal of Biomedical Optics}, 18(7), 077003.

\bibitem{dokuz} Balas, C. et al. (2011). Multi/Hyper-spectral Imaging. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{on} Bearman, G. and Levenson, L.(2003). Biological Imaging Spectroscopy. Vo-Dinh (ed.) In \emph{Biomedical Photonics Handbook}. CRC Press.

\bibitem{onbir} Elavarasu S, Naveen D, Thangavelu A. Lasers in periodontics. J Pharm Bioall Sci [serial online] 2012 [cited 2015 Aug 30];4, Suppl S2:260-3. Available from: http://www.jpbsonline.org/text.asp?2012/4/6/260/100245

\bibitem{oniki} N. Gupta, “Development of staring hyperspectral imagers,” in 2011 IEEE Applied Imagery Pattern Recognition Workshop, Washington, DC, pp. 1–8, Institute of Electrical and Electronics Engineers Inc. (2011).

\bibitem{onuc} Yu, G. et al. (2011). Near-Infrared Diffuse Correlation Spectroscopy for Assessment of Tissue Blood Flow. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{ondort} Erickson, S. J., \& Godavarty, A. (2009). Hand-held based near-infrared optical imaging devices: A review. Medical Engineering and Physics, 31(5), 495–509. http://doi.org/10.1016/j.medengphy.2008.10.004

\bibitem{onbes} McGee, S. et al. (2011). Reflectance Spectroscopy. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{onalti} Roblyer, D. et al. (2011). Fluorescence Spectroscopy. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{onalti.1} Gurjar, R.S., Backman, V., Perelman, L.T., Georgakoudi, I., Badizadegan, K.,
Itzkan, I., Dasari, R.R., Feld, M.S. (2001). Imaging human epithelial
properties with polarized light-scattering spectroscopy. \emph{Nature Med.}, 7(11),
1245–1248.

\bibitem{onalti.2} Qiu, L. et al. (2011). Light Scattering Spectroscopy. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{onalti.3} Krafft, C., \& Sergo, V. (2006). Biomedical applications of Raman and infrared spectroscopy to diagnose tissues. \emph{Spectroscopy}, 20(5-6), 195–218.

\bibitem{onalti.4} Berger, A.J. (2011). Raman, SERS, and FTIR Spectroscopy. Boas, D. A. et al (ed.) in \emph{Handbook of biomedical optics}. Boca Raton : CRC Press, c2011.

\bibitem{onyedi} Bellman, R. E (1961). \emph{Adaptive control processes: a guided tour.} Princeton University Press

\bibitem{onsekiz} Domingos, P. (2012). A few useful things to know about machine learning. Communications of the ACM, 55(10), 78.

\bibitem{ondokuz} Shlens, J. (2014). A Tutorial on Principal Component Analysis. Retrieved from http://arxiv.org/abs/1404.1100

\bibitem{yirmi} Keshava, N. (2003). A Survey of Spectral Unmixing Algorithms. Lincoln Laboratory Journal, 14(1), 55–78.

\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

ext: tex

max_stars_repo_path: latex source/Bio-Spectral Imaging.tex

max_stars_repo_name: delamine/Bio-Spectral-Imaging

max_issues_repo_path: latex source/Bio-Spectral Imaging.tex

max_issues_repo_name: delamine/Bio-Spectral-Imaging

max_forks_repo_path: latex source/Bio-Spectral Imaging.tex

max_forks_repo_name: delamine/Bio-Spectral-Imaging


text:
\documentclass[10pt,letterpaper,oneside,onecolumn]{article}
\usepackage[]{fontenc}
\usepackage[dvips]{epsfig}
\usepackage{fullpage}
\usepackage{html}

\pagestyle{plain}
\setcounter{secnumdepth}{5}
\setcounter{tocdepth}{5}

\title{A Brief Overview of Shimple}
\author{Navindra Umanee
(\htmladdnormallink{navindra@cs.mcgill.ca}{mailto:navindra@cs.mcgill.ca})}
\date{June 6, 2003}

\begin{document}
\maketitle

This document briefly describes Shimple, an SSA variant of Soot's
Jimple internal representation.  It assumes general knowledge of Soot,
Jimple and SSA form. You may wish to jump directly to the walk-through
section for a demonstration of why you might be interested in using
Shimple either by implementing analyses or by applying existing
optimizations.

\section{Why Shimple?}

Static Single Assignment (SSA) form guarantees a single static
definition point for every variable used in a program, thereby
significantly simplifying as well as enabling certain analyses.

Shimple provides you with an IR in SSA form that is almost entirely
identical to Jimple except for the introduction of Phi nodes.  The
idea is that Shimple can be treated almost identically to Jimple with
the added benefits of SSA.

For example, the additional variable splitting due to SSA form may
turn a previously flow-insensitive analysis into a flow-sensitive one
with little or no additional work.

\section{Hacking Overview}

The public API of Shimple is fully described in the
\htmladdnormallink{Soot API
documentation}{http://www.sable.mcgill.ca/soot/doc/}.  In particular,
in the \htmladdnormallink{soot.shimple
package}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/package-summary.html},
the
\htmladdnormallink{Shimple}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/Shimple.html}
class provides the Shimple grammar constructors and various utility
functions, the
\htmladdnormallink{ShimpleBody}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/ShimpleBody.html}
class describes Shimple bodies and
\htmladdnormallink{PhiExpr}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/PhiExpr.html}
provides the interface to Phi expressions.

Use/Definition and Definition/Use chains for Shimple bodies can be
obtained with
\htmladdnormallink{ShimpleLocalDefs}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/toolkits/scalar/ShimpleLocalDefs.html}
or
\htmladdnormallink{ShimpleLocalUses}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/toolkits/scalar/ShimpleLocalUses.html}
available in package soot.shimple.toolkits.scalar.

Currently, the only Shimple optimization available is the powerful,
control flow aware, SConstantPropagatorAndFolder.  The latter as well
as some simple Shimple analyses are available in package
\htmladdnormallink{soot.shimple.toolkits.scalar}{http://www.sable.mcgill.ca/soot/doc/soot/shimple/toolkits/scalar/package-summary.html}.
Please consult the Soot source for details.

\section{Usage Options}

For a full description of the options and phases pertaining to
Shimple, please consult the
\htmladdnormallink{primary}{http://www.sable.mcgill.ca/soot/\#documentation}
Soot option and phase documentation.

\section{Command Line Walk Through}

For fun, you may wish to run Shimple from the command-line and study
its output.  Consider the following (compiled) Java code of the
{\tt ShimpleTest} class:

\begin{verbatim}
public int test()
{
    int x = 100;

    while(doIt){
        if(x < 200)
            x = 100;
        else
            x = 200;
    }

    return x;
}
\end{verbatim}

\subsection{Producing Jimple}

If you produce Jimple with `{\tt soot.Main -f jimple ShimpleTest}' you
obtain the following code for the {\tt test()} method:

\begin{verbatim}
        i0 = 100;
        goto label2;

     label0:
        if i0 >= 200 goto label1;

        i0 = 100;
        goto label2;

     label1:
        i0 = 200;

     label2:
        if $z0 != 0 goto label0;

        return i0;
\end{verbatim}

\subsection{Producing Shimple}

To produce Shimple instead, use `{\tt soot.Main -f shimple ShimpleTest}':

\begin{verbatim}
        i0 = 100;
(0)     goto label2;

     label0:
        if i0_1 >= 200 goto label1;

        i0_2 = 100;
(1)     goto label2;

     label1:
(2)     i0_3 = 200;

     label2:
        i0_1 = Phi(i0 #0, i0_3 #2, i0_2 #1);
        if $z0 != 0 goto label0;

        return i0_1;
\end{verbatim}

The difference between the Jimple and Shimple output is that the
latter guarantees unique local definition points in the program (for
scalars).  Notice here that the variable {\tt i0} has been split into
the four variables {\tt i0}, {\tt i0\_1}, {\tt i0\_2} and {\tt i0\_3},
each with a unique definition point.

We have also introduced a Phi node.  You can read `{\tt i0\_1 = Phi(i0
\#0, i0\_3 \#2, i0\_2 \#1)}' as saying that {\tt i0\_1} will be assigned
value {\tt i0} if control flow comes from unit {\tt \#0} {\em or} it
will be assigned {\tt i0\_3} if control flow comes from unit {\tt
\#2} {\em or}... and so on.

If you have a prejudice against variable names with underscores, you
may use `{\tt soot.Main -f shimple -p shimple standard-local-names
ShimpleTest}' instead so that Shimple applies the Local Name
Standardizer each time new locals are introduced.

Feel free to skip the following digression and move on to the next
subsection.

\subsubsection{A Digression on Shimple Pointers}

Because Soot represents the body of a method internally as a Unit
chain, we need to store explicit pointers (such as {\tt \#0} and {\tt
\#1} in the above example) to keep track of the control flow
predecessors of the Phi statements.

Shimple's internal implementation of PatchingChain attempts to move
and maintain these pointers in a manner that will be as transparent as
possible to the user.  For example, in the simplest case, if a
statement is appended to block:

\begin{verbatim}
     label0:
(1)     i0_1 = 1000;
\end{verbatim}

to obtain:

\begin{verbatim}
     label0:
        i0_1 = 1000;
(1)     new_stmt;
\end{verbatim}

Shimple will automatically move the {\tt \#1} pointer down to the new
statement since it is in the same basic block.

The intent is to provide maximum flexibility for code motion
optimizations as well as other transformations.  In this case, {\tt
i0\_1 = 1000} is free to move up or down the Unit chain as long as the
new location dominates the original CFG block it was in.

\subsection{Producing Jimple, Again}

Since we eventually have to get rid of those pesky Phi nodes, you
may wish to see what the code looks like after going from Jimple to
Shimple and back again to Jimple.  Do this with `{\tt java soot.Main -f
jimple --via-shimple ShimpleTest}':

\begin{verbatim}
        i0_1 = 100;
        goto label2;

     label0:
        if i0_1 >= 200 goto label1;

        i0_1 = 100;
        goto label2;

     label1:
        i0_1 = 200;

     label2:
        if $z0 != 0 goto label0;

        return i0_1;
\end{verbatim}

Happily, in this case, the Jimple produced looks exactly like the
original Jimple code.  As usual you may specify `{\tt -p shimple
standard-local-names}' if the underscores hurt your eyes; they are
otherwise quite harmless.

To understand what's really going on when Shimple eliminates Phi
nodes, you can tell it to eliminate them naively with `{\tt soot.Main
-f jimple --via-shimple -p shimple phi-elim-opt:none ShimpleTest}':

\begin{verbatim}
        i0 = 100;
        i0_1 = i0;
        goto label2;

     label0:
        if i0_1 >= 200 goto label1;

        i0_2 = 100;
        i0_1 = i0_2;
        goto label2;

     label1:
        i0_3 = 200;
        i0_1 = i0_3;

     label2:
        if $z0 != 0 goto label0;

        return i0_1;
\end{verbatim}

Now you can see that all Shimple did was to replace the Phi node
with equivalent copy statements.

\subsection{Applying Shimple Optimizations}

So, what good is Shimple?

If you were paying attention, you may have noticed that despite the
control flow and different assignments to {\tt x}, {\tt x} is in fact
a constant 100 and is only ever used by a single return statement.  In
other words, all the computations are quite useless and need to be
optimized away.

Let's try to apply Jimple's Constant Propagator and Folder.  In fact,
to be fair, let's try all the available  Jimple optimizations activated
with `{\tt soot.Main -f jimple -O ShimpleTest}':

\begin{verbatim}

        i0 = 100;
        goto label2;

     label0:
        if i0 >= 200 goto label1;

        i0 = 100;
        goto label2;

     label1:
        i0 = 200;

     label2:
        if $z0 != 0 goto label0;

        return i0;
\end{verbatim}

As you can see in this case, the Jimple optimizations failed to deduce
that {\tt x} is a constant.  Jimple may be forgiven for this since
reasoning about control flow is not always an easy task to automate.
Shimple, on the other hand, encodes control flow information
explicitly in the Phi nodes thereby allowing optimizations to make use
of the information.

Currently, the only optimization we have implemented specifically for
Shimple is a version of the powerful constant propagation algorithm
sketched by the Cytron et el.  The implementation can reason about
control flow and can currently handle the conditional branching
statements {\tt IfStmt}, {\tt TableSwitchStmt} and {\tt
LookupSwitchStmt}.

Let's apply it with `{\tt soot.Main -f jimple --via-shimple -O
ShimpleTest}':

\begin{verbatim}
     label0:
        if $z0 != 0 goto label0;

        return 100;
\end{verbatim}

Et voila, Shimple optimized out the {\tt x} variable completely. What
happened is that the optimization propagated reachable definitions to
the Phi node and then noticed that the Phi node was useless (because
it made a selection from identical values) and therefore trimmed it
out.  In the process, dead code was exposed which was ultimately
eliminated.

To understand what is really going on, you can look at the output from
`{\tt soot.Main -f shimple -p sop on}', `{\tt soot.Main -f shimple -p sop
on -p sop.cpf prune-cfg:false}' and `{\tt soot.Main -f jimple
--via-shimple -p shimple phi-elim-opt:none -p sop on -p sop.cpf
prune-cfg:false}' on this and other examples:

\begin{verbatim}
public int test2()
{
    int i = 1000;
    int j = 1000;

    while(doIt){
        if(i == j){
            if(anotherIt)
                i = j;
            else
                j = i;
        }
        else{
            i = 5;
            j = 6;
        }
    }

    return i + j;
}
\end{verbatim}

\section{Thanks and Credits}

Thanks and credits go alphabetically to Laurie Hendren, John
Jorgensen, Patrick Lam and Ondrej Lhotak for helping with the design
of Shimple and general implementation issues.  I am most grateful for
their help and advice.

\section{Future Work}

Much more work on Shimple is planned as the project is likely to morph
into a Master's thesis.  Some thoughts currently include investigating
the various scalar SSA variants as well as heap, array and possibly
concurrent forms of SSA.  The Shimple architecture and implementation
will therefore evolve quite a bit internally, but as far as possible
we will try to maintain backwards-compatibility for the public
interfaces.

Suggestions, improvements and bug reports/fixes welcome!  Please send
these either to the Soot mailing list at
\htmladdnormallink{soot-list@sable.mcgill.ca}{mailto:soot-list@sable.mcgill.ca}, or directly to myself
at
\htmladdnormallink{navindra@cs.mcgill.ca}{mailto:navindra@cs.mcgill.ca}.

\subsection{Partial To-Do List}

\begin{itemize}
\item Implement more SSA-based analyses.
\item Add timers and profiling code.
\item Make internal analyses more useful and generic for external use.
\item Adopt an Strategy-type pattern for SSA builder modules, etc.
\item Implement a Shimple parser.
\item Provide an interface for CFG manipulations that intelligently
updates Phi nodes.
\item Implement a Control Dependence Graph?  Any interest in that?
\end{itemize}

\subsection{Known Issues}

A vague description of a couple of known issues follows.  You may
ignore this section completely since regular usage of Shimple should
not be affected in general.

\subsubsection{Issue 1}

One issue is related to Phi nodes inserted at the beginning of try
blocks which are subsequently used by Phi nodes in the corresponding
handler block.  Fortunately, although the code produced looks strange
it is not incorrect.  Example:

\begin{verbatim}
    label1:
        i0_2 = Phi(i0 #0, i0_1 #1);
(2)     i1 = 4 / 0;
(3)     i0_3 = i0_2 / 0;
        i2 = i0_3;

     label2:
        goto label4;

     label3:
        $r0 := @caughtexception;
        i0_4 = Phi(i0_1 #1, i0 #0, i0_2 #2, i0_3 #3);

        catch java.lang.Exception from label1 to label2 with label3;
\end{verbatim}

The {\tt \#2} pointer of the second Phi node really should be pointing
directly at the first Phi node instead of at the statement following
it (since the latter may throw an exception and branch to the handler
block).  Fortunately, in these cases the second Phi node will always
be pointing directly at the predecessors of the first Phi node as well
({\tt \#0} and {\tt \#1} in this example), rendering the matter moot.
This glitch will be eliminated in a future release.

\subsubsection{Issue 2}

Another issue is related to the Shimple patching algorithm.  In the
rare case that control flow falls through from an if statement to a
try block and the if statement has a pointer to it:

\begin{verbatim}
       value = 1000;
(1)    if (whatever) goto label100;

label1:
       first_trap_statement;
       ...
       goto label100;
label2:
       $r0 := @caughtexception;
       i0 = Phi(value #1, ...);
\end{verbatim}

In the above, it may be desirable to move the \#1 pointer down if a
Unit happens to be inserted after the if statement.  Although Shimple
is smart enough to do this in most known cases, it currently misses
the one case where control flows from an if statement in a
non-exceptional context to an exceptional context.

This is not a big problem for most people unless an exotic code motion
algorithm (currently non-existent in Soot) attempts to move the
definition of {\tt value} below the if statement for some reason.

\section*{History}
\begin{itemize}
\item June 6, 2003: Initial version.
\item June 17, 2003: Updated for Soot 2.0.1.
\end{itemize}

\end{document}


text:
\documentclass[a4paper,12pt]{article}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{geometry}
\usepackage{times}
\geometry{legalpaper, portrait, margin=.75in}

\begin{document}

\begin{flushright}

\vspace{1.1cm}

{\bf\Huge Lab 1}

\rule{0.25\linewidth}{0.5pt}

\vspace{0.5cm}
%Put Authors
Justin Ely
\linebreak
\newline
%Put Author's affiliations
\footnotesize{615.202.81.FA15 Data Structures \\}
\vspace{0.5cm}
% Date here below
06 October, 2015
\end{flushright}

\noindent\rule{\linewidth}{1.0pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Comments}
A stack-based implementation make sense for translating postfix expressions largely because stacks are a well-understood
and robust way to evaluate postfix expressions, and a topic of previous course modules.  This ties into the current assignment, as to translate an expression into machine
language you first need to determine each individual operation in order.

From each expression, the translation requires evaluating the postfix expression in the abstract: iterating through the input string and selecting out each operation individually.  However, instead of evaluating, the final step is to print out the machine instructions that would evaluate the operation.  The machine code is straight-forward: load argument 2, perform operation on arg2 and arg1, store result.

Providing adequate tests for the translator was integral to the final robust version of the code.  With the initial version, there had been no
accounting for things like blank strings, spaces, numbers, or unused variables.  Putting in many different test-cases with strange edge-cases caused
new errors (or lack there of) which lead to new handling of the expressions.

\subsection{Recursion}
While a recursive solution would be possible, it's not the standard way to solve postfix expressions.  The iterative technique
is straightforward and naturally works with a stack, making it the better algorithm for this project.  Though it is likely that the recursive
solution is more costly for computation and memory usage, the small size of this project likely means this is not an appreciable
concern.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Design}
For my stack, I chose to implement an array based stack of fixed size (50 elements) and type (String).  The String type seems
like a natural choice given the design requirements.  It allows each element to be of different lengths, which would not be possible
with a char array, and is thus able to store the "TEMPX" strings needed in the problem.  The fixed type was motivated more from
simplicity than anything else.  Dynamic typing was not needed for this problem, and so implementing it would cause additional tests
to be run and additional failures to be possible.  A set length of 50 elements was chosen because memory is cheap, and a 50
variable stack is unlikely to happen in a typical postfix expression - though this is a known limitation of the design.

I chose to implement a custom exception for when an invalid expression is supplied: BadPostfixExpression.  This was done both for clarity to the user and specificity when error handling.
Providing clearer output to the user is a definite advantage; constraining the error as much as possible and pointing right to what went
wrong reduces the amount of time spent debugging.  The added specificity when handling errors is particularly good practice
so as to not accidentally handle an unanticipated error simply because the thrown error classes were the same.

\subsection{Enhancements}
While the requirements were to read expressions from named files, I felt that it is cumbersome to need to write a text
file just to feed a single command into the translator.  Because of this, I allow both named files and explicit postfix expressions to be
supplied as input.  This does have some trade-offs: namely if an input argument is the name of a file on the disk, then it
will be read line-by-line, otherwise it will be treated as a single postfix expression.  This means that an incorrectly spelled file
will be read as postfix and will generate the same error as would an invalid expression, and may lead to some minor confusion.

Another enhancement is the support of exponentiation.  The design requirements state that only +,-,*,/ need to be supported,
but it was simple to implement exponentiation (\$) as well.  The machine command corresponding to \$ is PW, short for power.

The last enhancement made is an additional convenience function that returns the current size of the stack.  While not needed
for this problem, for an array-based stack of fixed size such a method could be useful to avoid overflow and so was included.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Efficiency}
The efficiency of the module is tied to the stack implementation.  Since insertions and deletions can happen only at one end,
the cost of either operation is O(1).  With constant-time operations to pop and push from the stack, the complexity of the
entire translation process is O(n) - since to evaluate a postfix expression, a single pass over the statement is sufficient.

There will be differences in the constant factor for the complexity in each run however.  As an example, translating the simple expression
AB+ requires two pushes and two pops.  For a longer expression with nested operations, the results of previous computations will
be pushed back onto the stack for evaluation later, slightly increasing the time time required from simply scaling as N.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{What I learned}
This project was my first serious experience with Java, and as such I learned quite a lot about the language and how language
semantics can enforce a particular design.  The very structure of splitting each class into separate files enforces a high
amount of modularity.  While I appreciate this to an extent, such aggressive splitting is a distinct departure from the logical
groupings I'm used to.  As a particular example, I would have liked to include my custom exception, BadPostfixExpression, in
with the code for parsing and translating the expressions.  This particular exception is custom-designed for this application, and it
would make sense to contain it within the other postfix specific code.

In addition, throwing exceptions was a major learning experience.  Beyond simply needing to declare the thrown exception in
the function definition,  the two distinct exception types was a stumbling block for a time.  The fact that some errors {\bf must} be caught by
their calling functions is a good example of the language enforcing particular behavior.  By throwing an error that requires catching upon
compilation, I'm forced to write code that is less-prone to unintended failure.  However, I was able to get around this by subclassing an
Error rather than an Exception, which only raises an error if encountered during runtime.  Depending on the specific bit of code, checked
or unchecked errors can be more appropriate.

\subsection{Complaints}
This wouldn't be a learning experience without some complaints, so to round out the experience I might as well detail them.
Declaring types of functions and variables is a pain.  I do understand why they are there, but they simply make programming
less fun!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Next time}
The main thing I would change would be generic typing of the Stack data structure.  Although restricting the type to
Strings is fine for the current designs of this project, creating stacks of different types would be beneficial both as a learning experience
and to allow more features to the Postfix translator.

I would also either use a dynamically allocated stack, or have the maximum size of the stack be set upon initialization.  Although my
imposed limitation of 50 elements seems generous for the current application, allowing the stack size to be set based upon
the length of the input expression would be much safer and generalizable.

Exploring the available unit-testing frameworks is another aspect that I would work towards.  Although my test-cases work fine,
the amount of work required to test them up without the benefit of a unit-test environment was burdensome and unnecessary.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}

max_stars_repo_name: justincely/classwork

max_issues_repo_name: justincely/classwork

max_forks_repo_name: justincely/classwork


text:
\documentclass[a4paper,titlepage]{article}
\usepackage[utf8]{inputenc}
\usepackage{fullpage}
\usepackage{indentfirst}
\usepackage[per-mode=symbol]{siunitx}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath}
\usepackage{array}
\usepackage[hidelinks]{hyperref}
\usepackage[format=plain,font=it]{caption}
\usepackage{subcaption}
\usepackage{standalone}
\usepackage[nottoc]{tocbibind}
\usepackage[noabbrev,capitalize,nameinlink]{cleveref}
\usepackage{listings}
\usepackage{titlesec}
\usepackage{minted}
\usepackage{booktabs}
\usepackage{csvsimple}
\usepackage{siunitx}
\usepackage[super]{nth}
\usepackage[titletoc]{appendix}

% Custom commands
\newcommand\numberthis{\addtocounter{equation}{1}\tag{\theequation}}
\newcommand{\code}[1]{\mintinline{python}{#1}}
\newcolumntype{P}[1]{>{\centering\arraybackslash}p{#1}}

\setminted{linenos,breaklines,fontsize=auto}

%\titleformat*{\section}{\normalsize\bfseries}
%\titleformat*{\subsection}{\small\bfseries}
\renewcommand{\thesubsection}{\thesection.\alph{subsection}}
\providecommand*{\listingautorefname}{Listing}
\newcommand*{\Appendixautorefname}{Appendix}
%\crefname{appendix}{Appendix}{Appendices}
%\def\appendixname{Appendix}

%opening
\title{\textbf{ECSE 543 \\ Assignment 2}}
\author{Sean Stappas \\ 260639512}
\date{November \nth{20}, 2017}

\begin{document}
	\sloppy
	\maketitle

	\tableofcontents

	\twocolumn

	\section*{Introduction}

	The code for this assignment was created in Python 2.7 and can be seen in \autoref{appendix:code}. To perform the required tasks in this assignment, the \mintinline{python}{Matrix} class from Assignment 1 was used, with useful methods such as add, multiply, transpose, etc. This package can be seen in the \mintinline{python}{matrices.py} file shown in \autoref{lst:matrices}. The only packages used that are not built-in are those for creating the plots for this report, i.e., \mintinline{python}{matplotlib} for plotting. The structure of the rest of the code will be discussed as appropriate for each question. Output logs of the program are provided in \autoref{appendix:logs}. The \mintinline{python}{SIMPLE2D} input and output files can be seen in \autoref{appendix:simple2d}.

	\section{FE Triangles}

	The source code for the Question 1 program can be seen in the \mintinline{python}{q1.py} file shown in \cref{lst:q1}, with output shown in \cref{lst:q1_log}.

	\subsection{Local S-Matrix}

	The equation for the $\alpha$ parameter for a general vertex $i$ of a finite element triangle can be seen in \cref{eq:alpha}, where $i+1$ and $i+2$ implicitly wrap around when exceeding 3, the total number of vertices in a triangle. $A$ is the area of the triangle.

	\begin{equation} \label{eq:alpha}
		\begin{split}
			\alpha_i(x, y) = \frac{1}{2A} \big[
			& (x_{i+1}y_{i+2} - x_{i+2}y_{i+1}) \\
			& + (y_{i+1} - y_{i+2})x \\
			& + (x_{i+2} - x_{i+1})y \big]
		\end{split}
	\end{equation}

	Using \cref{eq:alpha}, we can solve for the entries of the local $S$-matrix, as shown in \cref{eq:local_s}. This was used in the \code{finite_element_triangles.py} script shown in \cref{lst:finite_element_triangles} to compute every entry for both example triangles.

	\begin{equation} \label{eq:local_s}
		\begin{split}
			S_{ij}
			= &\int\displaylimits_{\Delta_e}\nabla\alpha_i\cdot\nabla\alpha_j ds \\
			= &\frac{1}{4A} \big[ (y_{i+1} - y_{i+2})(y_{j+1} - y_{j+2}) \\
			&+ (x_{i+2} - x_{i+1})(x_{j+2} - x_{j+1})
			\big]
		\end{split}
	\end{equation}

	The local $S$-matrices, $S_1$ and $S_2$, for the two triangles can be seen in \cref{eq:local_s1,eq:local_s2}, as well as in the output of the \code{q1.py} program shown in \cref{lst:q1_log}.

	\begin{equation} \label{eq:local_s1}
		S_1 =
			\begin{bmatrix}
				\input{matrices/S1.txt}
			\end{bmatrix}
	\end{equation}

	\begin{equation} \label{eq:local_s2}
		S_2 =
			\begin{bmatrix}
				\input{matrices/S2.txt}
			\end{bmatrix}
	\end{equation}

	\subsection{Global S-Matrix}

	The disjoint $S$-matrix is then given by the following:

	\begin{equation*}
		\begin{split}
			&S_{dis} = \begin{bmatrix}
				S_1 & \textbf{0} \\
				\textbf{0} & S_2
			  \end{bmatrix} \\
			&= \begin{bmatrix}
			\input{matrices/S_dis.txt}
			\end{bmatrix}
		\end{split}
	\end{equation*}

	The connectivity matrix $C$ is given by \cref{eq:connectivity}.

	\begin{equation} \label{eq:connectivity}
		C =
			\begin{bmatrix}
				\input{matrices/C.txt}
			\end{bmatrix}
	\end{equation}

	The global $S$-matrix is then given by \cref{eq:global_s}.

	\begin{equation} \label{eq:global_s}
		S = C^T S_{dis} C^T
	\end{equation}

	Using \cref{eq:connectivity,eq:global_s}, we can compute the global $S$-matrix, giving the value shown in \cref{eq:global_s_solution}, which is computed by the \mintinline{python}{finite_element_triangles.py} script shown in \cref{lst:finite_element_triangles}.

	\begin{equation} \label{eq:global_s_solution}
		S =
			\begin{bmatrix}
				\input{matrices/S.txt}
			\end{bmatrix}
	\end{equation}

	\section{FE Coaxial Cable}

	The source code for the Question 2 program can be seen in the \mintinline{python}{q2.py} file shown in \cref{lst:q2}, with output shown in \cref{lst:q2_log}.

	\subsection{Mesh}
	The mesh to be used by the \mintinline{python}{SIMPLE2D} program can be seen in \cref{fig:finite_element_mesh}. The (0.06, 0.04) node is labeled in blue.

	\begin{figure}[!htb]
		\centering
		\includegraphics[width=\columnwidth]{plots/finite_element_mesh.pdf}
		\caption
		{Finite element mesh with labeled nodes. The (0.06, 0.04) node is labeled in blue.}
		\label{fig:finite_element_mesh}
	\end{figure}

	The mesh to be used by the \mintinline{python}{SIMPLE2D} program is generated by the \mintinline{python}{finite_element_mesh_generator.py} script shown in \cref{lst:finite_element_mesh_generator}. This generates the node positions, triangle coordinates and initial potentials for the mesh, and saves them in a \code{mesh.dat} file to be used as input for the \code{SIMPLE2D} program. This input file can be seen in \cref{lst:mesh}. The resulting output file generated by the \code{SIMPLE2D} program can be seen in \cref{lst:result}.

	\subsection{Electrostatic Potential}

	Based on the results from the \mintinline{python}{SIMPLE2D} program, the potential at (0.06, 0.04) is \SI{5.5263}{\volt}. This corresponds to node 16 in the mesh arrangement we created.

	\subsection{Capacitance}

	The finite element functional equation for two conjoint finite element triangles forming a square $i$ can be seen in \cref{eq:functional}.

	\begin{equation} \label{eq:functional}
		W_i = \frac{1}{2} U_{con_i}^T S U_{con_i}
	\end{equation}
	where $S$ is given in \cref{eq:global_s_solution} and $U_{con_i}$ is the conjoint potential vector for square $i$, giving the potential at the four corners of the square defining the combination of two finite element triangles. This can be seen in \cref{eq:u}.

	\begin{equation} \label{eq:u}
		U_{con} =
			\begin{bmatrix}
				U_{i_1} \\
				U_{i_2} \\
				U_{i_3} \\
				U_{i_4}
			\end{bmatrix}
	\end{equation}

	To find the total energy function $W$ of the mesh, we must add the contributions from each square and multiply by 4, since our mesh is one quarter of the entire coaxial cable. This yields \cref{eq:total_functional}.

	\begin{equation} \label{eq:total_functional}
		W = 4 \sum_{i}^{N}{W_i} = 2 \sum_{i}^{N}{U_{con_i}^T S U_{con_i}}
	\end{equation}
	where $N$ is the number of finite difference squares in the mesh.

	Note that $W$ is not equal to the energy. The relation between the energy per unit length $E$ and $W$ is shown in \cref{eq:energy}.

	\begin{equation} \label{eq:energy}
		E = \epsilon_0 W
	\end{equation}

	We then know that the energy per unit length $E$ is related to the capacitance per unit length $C$ as shown in \cref{eq:energy_capacitor}.

	\begin{equation} \label{eq:energy_capacitor}
		E = \frac{1}{2} C V^2
	\end{equation}
	where $V$ is the voltage across the coaxial cable.

	Combining \cref{eq:functional,eq:total_functional,eq:energy,eq:energy_capacitor}, we obtain an expression for the capacitance per unit length which can be easily calculated, as shown in \autoref{eq:capacitance}.

	\begin{equation} \label{eq:capacitance}
		C = \frac{2E}{V^2} = \frac{4 \epsilon_0}{V^2} \sum_{i}^{N}{U_{con_i}^T S U_{con_i}}
	\end{equation}

	The capacitance per unit length is computed as \SI{5.2137E-11}{\farad\per\meter} by the \mintinline{python}{finite_element_capacitance.py} script shown in \cref{lst:finite_element_capacitance} with output shown in \cref{lst:q2_log}.

	\section{CG Coaxial Cable}

	The source code for the Question 3 program can be seen in the \mintinline{python}{q3.py} file shown in \cref{lst:q3}, with output shown in \cref{lst:q3_log}.

	\subsection{Positive Definite Test}

	To form the $A$ matrix, we must consider all the free nodes in the mesh. There are 19 free nodes in our quarter-conductor mesh, as shown in \cref{fig:finite_difference_mesh}.

	\begin{figure}[!htb]
		\centering
		\includegraphics[width=\columnwidth]{plots/finite_difference_mesh.pdf}
		\caption
		{Finite difference mesh with labeled free nodes. The (0.06, 0.04) node is labeled in blue. The boundary free nodes are labeled in orange.}
		\label{fig:finite_difference_mesh}
	\end{figure}

	The potential at the non-boundary free nodes is given by \cref{eq:free_node}.

	\begin{equation} \label{eq:free_node}
		-4\phi_{i, j} + \phi_{i + 1, j}  + \phi_{i - 1, j}  + \phi_{i, j + 1}  + \phi_{i, j - 1} = 0
	\end{equation}

	The free nodes along a boundary must satisfy the Neumann boundary condition for symmetry. These boundary free nodes are labeled in orange in \cref{fig:finite_difference_mesh}. Since our quarter-mesh is the bottom left corner of the overall mesh, these boundary nodes defining planes of symmetry are along the top and the right. The Neumann boundary condition for the top nodes is given by \cref{eq:neumann_top} and that for the right nodes is given by \cref{eq:neumann_right}.

	\begin{equation} \label{eq:neumann_top}
		\phi_{i, j + 1} - \phi_{i, j - 1} = 0
	\end{equation}

	\begin{equation} \label{eq:neumann_right}
		\phi_{i + 1, j} - \phi_{i - 1, j} = 0
	\end{equation}

	Now, the simplified potential for boundary free nodes can be calculated, as seen in \cref{eq:top_potential,eq:right_potential}.

	\begin{equation} \label{eq:top_potential}
		-4\phi_{i, j} + \phi_{i + 1, j}  + \phi_{i - 1, j}  + 2\phi_{i, j - 1} = 0
	\end{equation}

	\begin{equation} \label{eq:right_potential}
		-4\phi_{i, j} + 2\phi_{i - 1, j} + \phi_{i, j + 1}  + \phi_{i, j - 1} = 0
	\end{equation}

	The non-free nodes are fixed by the potentials of the conductors, i.e., \SI{15}{\volt} and \SI{0}{\volt}.

	With \cref{eq:free_node,eq:top_potential,eq:right_potential}, we can form the $A$ matrix from every mesh node. This is done in \mintinline{python}{finite_difference_mesh_generator.py}, as shown in \cref{lst:finite_difference_mesh_generator}. The output $A$ matrix can be seen in \cref{lst:q3_log}.

	Using the \code{choleski.py} program from Assignment 1 shown in \cref{lst:choleski}, we can see that the matrix $A$ is indeed not positive definite.	To make $A$ positive definite, one can simply multiply both sides of the $Ax = b$ equation by $A^T$, forming a new equation $A^TAx = A^Tb$. This is equivalent to $A'x = b'$, where $b' = A^Tb$ and $A' = A^TA$. Here, $A'$ is now positive definite. The verification and multiplication of $A$ is done by the \code{q3.py} program shown in \cref{lst:q3}, with output shown in \cref{lst:q3_log}

	\subsection{Matrix Solution}

	The matrix equation to be solved can be seen in \cref{eq:fd}, where $A'$ and $b'$ are the matrices generated previously and $\phi_c$ is the unknown potential vector.

	\begin{equation} \label{eq:fd}
		A'\phi_c = b'
	\end{equation}

	The matrix equation is solved first by the Choleski method from Assignment 1, as found in the \mintinline{python}{choleski.py} shown in \cref{lst:choleski}. Then, the conjugate gradient method defined by \mintinline{python}{conjugate_gradient_solve} of the \mintinline{python}{conjugate_gradient.py} file shown in \cref{lst:conjugate_gradient} was applied. The solved $\phi_c$ vector from both methods can be seen in \cref{lst:q3_log}.

	\subsection{Residual Norm}

	Consider a vector $\textbf{v} = \{v_1, \ldots, v_n\}$. The infinity norm $\|\textbf{v}\|_\infty$ of $\textbf{v}$ is given by the maximum absolute element of $\textbf{v}$, as shown in \cref{eq:infinity_norm}.

	\begin{equation} \label{eq:infinity_norm}
		\|\textbf{v}\|_\infty = \max\{|v_1|, \ldots, |v_n|\}
	\end{equation}

	Similarly, the 2-norm $\|\textbf{v}\|_2$ of $\textbf{v}$ is given by \cref{eq:2_norm}.

	\begin{equation} \label{eq:2_norm}
		\|\textbf{v}\|_2 = \sqrt{\sum_{i = 1}^{n} v_i^2}
	\end{equation}

	The infinity norm of the residual vector versus conjugate gradient iterations can be seen in \cref{fig:q3c_infinity}. The 2-norm versus iterations can be seen in \cref{fig:q3c_2}. Both norms converge to 0 after $n = 19$ iterations, as expected.

	\begin{figure}[!htb]
		\centering
		\includegraphics[width=\columnwidth]{plots/q3c_infinity.pdf}
		\caption
		{Value of the infinity norm $\|\textbf{r}\|_\infty$ of the residual vector versus iterations of the conjugate gradient algorithm.}
		\label{fig:q3c_infinity}
	\end{figure}

	\begin{figure}[!htb]
		\centering
		\includegraphics[width=\columnwidth]{plots/q3c_2.pdf}
		\caption
		{Value of the 2-norm $\|\textbf{r}\|_2$ of the residual vector versus iterations of the conjugate gradient algorithm.}
		\label{fig:q3c_2}
	\end{figure}

	\subsection{Potential Comparison}

	A comparison of the potential at (0.06, 0.04) to three decimal places for various numerical methods can be seen in \cref{table:potential_comparison}. It can be seen that the potential found with all the methods is the same to three decimal places.

	\begin{table}[!htb]
		\centering
		\caption{Comparison of potential at (0.06, 0.04) to three decimal places for various numerical methods.}
		\begin{tabular}{r | l}
			\textbf{Method} & \textbf{Potential (V)} \\ \hline
			Choleski & 5.526 \\
			Conjugate gradient & 5.526 \\
			Finite element & 5.526 \\
			Finite difference (SOR) & 5.526
		\end{tabular}
		\label{table:potential_comparison}
	\end{table}

	\subsection{Capacitance Computation}

	Once the potential values are known from the finite difference solution, the capacitance can be calculated in the same way as in Question 2(c), i.e., with \cref{eq:capacitance}. The mesh must simply be converted to the finite element version to compute the $U_{con}$ and $S$ matrices. In this way, the \code{SIMPLE2D} is not needed.

%	\begin{figure}[!htb]
%		\centering
%		\includegraphics[width=0.5\columnwidth]{plots/q1_circuit_1.pdf}
%		\caption
%		{Test circuit 1 with labeled nodes.}
%		\label{fig:q1_circuit_1}
%	\end{figure}
%
%	\begin{table}[!htb]
%		\centering
%		\caption{Voltage at labeled nodes of circuit 1.}
%		\csvautobooktabular{csv/q1_circuit_1.csv}
%		\label{table:q1_circuit_1}
%	\end{table}

	\onecolumn

	\begin{appendices}

		\section{Code Listings} \label{appendix:code}

		\setminted{linenos,breaklines,fontsize=\footnotesize}

		\begin{center}
			\captionof{listing}{Custom matrix package (\texttt{matrices.py}).}
			\inputminted{python}{../matrices.py}
			\label{lst:matrices}
		\end{center}

		\begin{center}
			\captionof{listing}{Question 1 (\texttt{q1.py}).}
			\inputminted{python}{../q1.py}
			\label{lst:q1}
		\end{center}

		\begin{center}
			\captionof{listing}{Finite element triangles (\texttt{finite\_element\_triangles.py}).}
			\inputminted{python}{../finite_element_triangles.py}
			\label{lst:finite_element_triangles}
		\end{center}

		\begin{center}
			\captionof{listing}{Question 2 (\texttt{q2.py}).}
			\inputminted{python}{../q2.py}
			\label{lst:q2}
		\end{center}

		\begin{center}
			\captionof{listing}{Finite element mesh generator (\texttt{finite\_element\_mesh\_generator.py}).}
			\inputminted{python}{../finite_element_mesh_generator.py}
			\label{lst:finite_element_mesh_generator}
		\end{center}

		\begin{center}
			\captionof{listing}{Finite element capacitance (\texttt{finite\_element\_capacitance.py}).}
			\inputminted{python}{../finite_element_capacitance.py}
			\label{lst:finite_element_capacitance}
		\end{center}

		\begin{center}
			\captionof{listing}{Question 3 (\texttt{q3.py}).}
			\inputminted{python}{../q3.py}
			\label{lst:q3}
		\end{center}

		\begin{center}
			\captionof{listing}{Finite difference mesh generator (\texttt{finite\_difference\_mesh\_generator.py}).}
			\inputminted{python}{../finite_difference_mesh_generator.py}
			\label{lst:finite_difference_mesh_generator}
		\end{center}

		\begin{center}
			\captionof{listing}{Choleski decomposition (\texttt{choleski.py}).}
			\inputminted{python}{../choleski.py}
			\label{lst:choleski}
		\end{center}

		\begin{center}
			\captionof{listing}{Conjugate gradient (\texttt{conjugate\_gradient.py}).}
			\inputminted{python}{../conjugate_gradient.py}
			\label{lst:conjugate_gradient}
		\end{center}

		\section{Output Logs} \label{appendix:logs}

		\begin{center}
			\captionof{listing}{Output of Question 1 program (\texttt{q1.txt}).}
			\inputminted{pycon}{logs/q1.txt}
			\label{lst:q1_log}
		\end{center}

		\begin{center}
			\captionof{listing}{Output of Question 2 program (\texttt{q2.txt}).}
			\inputminted{pycon}{logs/q2.txt}
			\label{lst:q2_log}
		\end{center}

		\begin{center}
			\captionof{listing}{Output of Question 3 program (\texttt{q3.txt}).}
			\inputminted{pycon}{logs/q3.txt}
			\label{lst:q3_log}
		\end{center}

		\section{Simple2D Data Files} \label{appendix:simple2d}
		\begin{center}
			\captionof{listing}{Input mesh for the \texttt{SIMPLE2D} program (\texttt{mesh.dat}).}
			\inputminted{pycon}{../simple2d/mesh.dat}
			\label{lst:mesh}
		\end{center}

		\begin{center}
			\captionof{listing}{Resulting potentials generated by the \texttt{SIMPLE2D} program (\texttt{result.dat}).}
			\inputminted{pycon}{../simple2d/result.dat}
			\label{lst:result}
		\end{center}

	\end{appendices}

\end{document}


text:
%
% API Documentation for QSTK
% Package QSTK.qstklearn
%
% Generated by epydoc 3.0.1
% [Mon Mar  5 00:49:20 2012]
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                          Module Description                           %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    \index{QSTK \textit{(package)}!QSTK.qstklearn \textit{(package)}|(}
\section{Package QSTK.qstklearn}

    \label{QSTK:qstklearn}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                Modules                                %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{Modules}

\begin{itemize}
\setlength{\parskip}{0ex}
\item \textbf{fastknn}: This package is an implementation of a novel improvement to KNN which
speeds up query times

  \textit{(Section \ref{QSTK:qstklearn:fastknn}, p.~\pageref{QSTK:qstklearn:fastknn})}

\item \textbf{gendata}
  \textit{(Section \ref{QSTK:qstklearn:gendata}, p.~\pageref{QSTK:qstklearn:gendata})}

\item \textbf{hmm}: This package includes code for representing and learning HMM's.

  \textit{(Section \ref{QSTK:qstklearn:hmm}, p.~\pageref{QSTK:qstklearn:hmm})}

\item \textbf{kdtknn}: A simple wrapper for scipy.spatial.kdtree.KDTree for doing KNN

  \textit{(Section \ref{QSTK:qstklearn:kdtknn}, p.~\pageref{QSTK:qstklearn:kdtknn})}

\item \textbf{mldiagnostics}
  \textit{(Section \ref{QSTK:qstklearn:mldiagnostics}, p.~\pageref{QSTK:qstklearn:mldiagnostics})}

\item \textbf{parallelknn}: This is an implementation of the K nearest neighbor learning algorithm. The
implementation is trivial in that the near neighbors are calculated
naively- without any smart tricks. Euclidean distance is used to calculate
the distance between two points. The implementation also provides some
coarse parallelism. If the par\_query function is used then the query
points are split up equally amongst threads and their near neighbors are
calculated in parallel. If the number of threads to use is not specified
then no of threads  = no of cores as returned by the cpu\_count function.
This may not be ideal.

  \textit{(Section \ref{QSTK:qstklearn:parallelknn}, p.~\pageref{QSTK:qstklearn:parallelknn})}

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                               Variables                               %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  \subsection{Variables}

    \vspace{-1cm}
\hspace{\varindent}\begin{longtable}{|p{\varnamewidth}|p{\vardescrwidth}|l}
\cline{1-2}
\cline{1-2} \centering \textbf{Name} & \centering \textbf{Description}& \\
\cline{1-2}
\endhead\cline{1-2}\multicolumn{3}{r}{\small\textit{continued on next page}}\\\endfoot\cline{1-2}
\endlastfoot\raggedright \_\-\_\-p\-a\-c\-k\-a\-g\-e\-\_\-\_\- & \raggedright \textbf{Value:}
{\tt None}&\\
\cline{1-2}
\end{longtable}

    \index{QSTK \textit{(package)}!QSTK.qstklearn \textit{(package)}|)}

max_stars_repo_name: elxavicio/QSTK

max_issues_repo_name: jenniyanjie/QuantSoftwareToolkit

max_forks_repo_name: jenniyanjie/QuantSoftwareToolkit


text:
\documentclass[conference,compsoc]{IEEEtran}
\usepackage{hyperref}

\usepackage[justification=raggedright,format=hang]{caption}

\usepackage{url}
\makeatletter
\g@addto@macro{\UrlBreaks}{\UrlOrds}
\makeatother

\usepackage{cite}
\usepackage{amsmath,amssymb,amsfonts}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{textcomp}
\usepackage{float}
\usepackage{xcolor}
\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}

\usepackage{epigraph}
\usepackage{listings}
\usepackage{adjustbox}
\usepackage{multirow}
\usepackage{array}
\usepackage{authblk}
\usepackage[ruled,vlined]{algorithm2e}

\newcommand{\myparagraph}[1]{\smallskip\noindent{\bf #1.}}
\newcommand{\myfirstparagraph}[1]{\noindent{\bf #1.}}
\newcommand{\scedit}[1]{{\color{black} #1}} % blue

\begin{document}

\title{FuzzSplore: Visualizing Feedback-Driven Fuzzing Techniques}

\iffalse
\author{\IEEEauthorblockN{Andrea Fioraldi}
\IEEEauthorblockA{\textit{1692419}}
\and
\IEEEauthorblockN{Luigi Paolo Pileggi}
\IEEEauthorblockA{\textit{1691249}}
}

\author{\IEEEauthorblockN{Andrea Fioraldi\IEEEauthorrefmark{1}\IEEEauthorrefmark{2},
Luigi Paolo Pileggi\IEEEauthorrefmark{1}}
\IEEEauthorblockA{andreafioraldi@gmail.com,
gigimail@gigi.com\\
\IEEEauthorrefmark{1} Sapienza University of Rome,
\IEEEauthorrefmark{2} EURECOM}}
\fi

\author[1]{Andrea Fioraldi}
\author[1]{Luigi Paolo Pileggi}
\affil[1]{Sapienza University, Rome, Italy \authorcr {\tt \{fioraldi.1692419, pileggi.1691249\}@studenti.uniroma1.it}\vspace{1.5ex}}

\maketitle

\begin{figure*}[t]
\centering
\includegraphics[width=1.0\textwidth]{img/full}
\caption{Complete view of the {\sc FuzzSplore} visual panel.}
\label{fig:full}
\end{figure*}

\begin{abstract}
Fuzz Testing techniques are the state of the art in software testing for security issues nowadays.
Their great effectiveness attracted the attention of researchers and hackers and involved them in developing a lot of new techniques to improve Fuzz Testing.
The evaluation and the cross-comparison of these techniques is an almost open problem. In this paper, we propose a human-driven approach to this problem based on information visualization.
We developed a prototype upon the {\sc AFL++} fuzzing framework, {\sc FuzzSplore}, that an analyst can use to get useful insights about different fuzzing configurations applied to a specific target in order to choose or tune the best technique during a fuzzing campaign.
\end{abstract}

\section{Introduction}

{\em Fuzz Testing} or {\em Fuzzing} is a family of techniques to automatically uncovers bugs in software.

Due to its effectiveness, much more efficient than other software testing techniques like {\it Symbolic Execution} \cite{redqueen} \cite{sebastian}, the research in this field is flourishing and several different techniques were developed to improve fuzz testing, both from academia and industry.

The evaluation and the comparison of these techniques, however, is a debatable matter \cite{fuzzeval}.

A common proxy is the comparison of the code coverage reached over time by each fuzzer, due to the fact that a fuzzer cannot find a bug if it does not explore at least the vulnerable code segment.
Another widely used metric is found bugs over time, but a bug can be found just thanks to randomism or by specific target-dependant actions taken by the fuzzer and this makes the evaluations very prone to overfitting.

The data collected using these metrics are often representable using a simple time-based graph that shows the evolution of the fuzzing algorithm.

This approach is useful for immediate basic comparison between two or more techniques, an analyst has to just see which technique reaches more coverage in less time but does not reveal the properties of a fuzzer regards specific types of program states.

For instance, a technique can be better than another in exploring some types of program states and at the same time reaching less code coverage.
The technique will not cover the bugs in the unexplored code of course, but it may uncover bugs in the program points that it can better explore.
An example of such technique is the directed fuzzer towards sanitizers violations by \"Osterlund et al. \cite{parmesan}.

The problem of the evaluation of fuzzing techniques is important not only when the aim is to generally states which fuzzer is best, but also when an analyst wants to select the best fuzzers for a single target. It is common that fuzzers that are considered generally better than others on some targets perform worst than the others \cite{aflplusplus}.

We propose {\sc FuzzSplore}, a tool that allows an analyst to manually explore the evolution of different fuzzing techniques regards a single target program.

The main insight that a user can get using the tool are:

\begin{enumerate}
\item The ability of a fuzzer to generate clusters of inputs that are correlated in terms of covered program points;
\item The ability of a fuzzer in generating diversified inputs with its mutational algorithm;
\item The ability of a fuzzer to reach program points exploring intermediate inputs that are not an improvement in terms of coverage \cite{besensitive}.
\end{enumerate}

These insights can drive the user to choose the best technique to use for the selected program under test (PUT).

\section{Background}
\label{sec:back}

The simplest description of Feedback-driven Fuzzing is an algorithm that provides apparently random data to a computer program and then it watches for crashes or unexpected states and also saves the generated input for later processing if they cover interesting new states in terms of the chosen feedback \cite{fuzzing-book}.

Typically, the property of the program used as feedback is the set of the edges in the program Control Flow Graph \cite{compilerbook} in what is the so-called {\it Coverage-guided Fuzzing} (CGF).

The inputs are mutations of previously saved inputs in the fuzzing loop in Mutational Fuzzing (Figure \ref{fig:cfg}) or generated from scratch from a model in Generational Fuzzing.

We base our implementation on {\sc AFL++} \cite{aflplusplus}, a widely used fuzzer in recent times, that is a Mutational Coverage Guided Fuzzer.

\begin{figure}[H]
\includegraphics[scale=0.2]{img/cgf}
\centering
\caption{Basic representation of the Mutational Coverage Guided Fuzzing algorithm}
\label{fig:cfg}
\end{figure}

State of the art Coverage-Guided Fuzzers encodes the approximate executed path in a representation that is easy and fast to process.
{\sc AFL++} uses a vector of 65536 entries by default, the {\it hitcounts} vector.

Each coordinate is associated with an edge and each value represents how many times the edge is executed modulo 256.

When a value greater than the previous one is registered in this vector, the fuzzer considers the input interesting and saves it.

Some extensions of CGF save also intermediate inputs that are a superset of the coverage reported in the hitcounts vector, like \cite{lafintel} \cite{ijon} \cite{besensitive}.

In general, when an input is saved, we can associate it to the testcases that generated it by mutation, the {\it parent} testcases. In this way, is easy to construct a graph of generated inputs that represents the progress of the hill-climbing algorithm of the fuzzer, the {\it Generations} Graph.

% Looking for parents in this tree, we can evaluate if the intermediate inputs generated by the specific technique is effective.

\section{Methodology}

A {\em fuzzing campaign} is the process of running one or more fuzzers for a long period of time or even continuously like in OSS-Fuzz \cite{serebryany2017oss}.

Security researchers typically start fuzzing using naive configurations and off-the-shelf fuzzers, then, meanwhile, the campaign runs, observe the evolution and tune the fuzzers.

Our proposed approach aims to insert in the observation-tuning feedback loop a visual component to help the researcher better understand insights about the fuzzers testing a particular target.

The data processed by {\em FuzzSplore} comes from the execution of the corpus of testcases that each fuzzer saved so far. The execution is instrumented and various properties are observed.

Then we visualize these collected properties and the user can relate them to better understand what is going. After that, the user can choose to drop some fuzzers if less effective and assign more resources (typically CPUs) to the most effective fuzzers or tune each individual fuzzer.

The fuzzing campaign can then continue. When it saturates, the analyst can collect insights using our tool and restart the visual analytics feedback-loop.

Saturation of fuzzers, when no more additional state is explored or the number of states explodes, is a problem that was rarely addressed in academic literature but that affects each type of Feedback-driven Fuzzer \cite{saturation},  and a tool that can guide towards the selection of techniques that avoid saturation can help a lot the campaign.

\subsection{Data Retrieval}

% We developed a script to extract the data from the execution of the various instrumented programs used by each fuzzer.

We denote each fuzzer $F_i$ where $i$ is the index that identifies it.
With $PUT_i$ we denote the version of the PUT preprocessed and instrumented in order to be used by $F_i$.
$PUT_e$ is the version of the PUT that logs the edge coverage using the hitcounts vector. It has to be provided independently if it is used or not by some fuzzer $F_i$.
With $T_i(t)$ we denote the set of the saved testcases, the queue, by $F_i$ until time $t$ (seconds).

Given $t$ as the time chosen by the user to observe the progress of the fuzzers, the Algorithm \ref{alg:data} computes the following sets:

\begin{itemize}
\item the set $C$ of all the functions $C_i \colon Time \longrightarrow NumEdges$ that relates, for the fuzzer $F_i$, a time unit to the number of discovered edges so far;
\item the set $I$ of all the functions $I_i \colon Testcase \longrightarrow \{F_j, ...\}$ that associates, for the fuzzer $F_i$, each testcase in $T_i(t)$ to the set of fuzzers that consider the testcase as interesting;
\item the set $X$ of the sets $X_i$, that maintains, for each fuzzer, the hitcounts vectors associated with the execution of each testcase in $T_i(t)$;
\end{itemize}

\begin{algorithm}[h]
\DontPrintSemicolon
%\KwResult{The set $C$ of all the functions $C_i \colon Time \longrightarrow NumEdges$ that associates, for the fuzzer $F_i$, a time unit to the number of discovered edges so far. The set of all the functions $I_i \colon Testcase \longrightarrow \{F_j...\}$ that associates, for the fuzzer $F_i$, each testcase of $T_i(t)$ to the set of fuzzers that consider the testcase as interesting.}

  \For {$F_i$ \textbf{ in } $Fuzzers$}{
    $V_{acc} \gets (0_0 ... 0_{65536}) $\;

    \For {$T$ \textbf{ in } $T_i(t)$}{
      $V \gets Execute(PUT_e, T)$\;
      $X_i \gets X_i \cup \{V\}$\;
      $V, IsInteresting \gets MergeCoverage(V_{acc}, V)$\;
      \If {$IsInteresting$}{
        $C_i(Time(T)) \gets CountNotZeros(V_i)$\;
      }
    }

    \For {$F_j$ \textbf{ in } $Fuzzers \setminus F_i$}{

     $V_{acc} \gets (0_0 ... 0_{65536}) $\;

      \For {$T$ \textbf{ in } $T_i(t)$}{
        $V \gets Execute(PUT_j, T)$\;
        $V_{acc}, IsInteresting \gets MergeCoverage(V_{acc}, V)$\;
        \If {$IsInteresting$}{
          $I_i(T) \gets I_i(T) \cup \{F_j\}$\;
        }
      }

    }

  }

 \Return{$C, I, X$}\;
 \caption{Compute $C$, $I$, and $X$}
 \label{alg:data}
\end{algorithm}

The next item that has to be retrieved, in addition to $C$, $I$ and $X$, is the set $G$ of all the graphs $G_i$ that describes the evolution of each $T_i(t)$, the levels graph introduced in Sec. \ref{sec:back}.

We assume that each fuzzer encodes the information about the parent testcases into the metadata of each testcase. In this way, it is trivial to construct the graph just by reading all the metadata in $T_i(t)$.

\subsection{Visualization}

We visualize the computed data $C$, $I$, $X$, $G$, and some other properties that can be directly collected in four different views.

You can see these views with some example data in the screenshot of our implementation, in Figure \ref{fig:full}.

A time bar is used to select $t' \in [0, t]$ to ignore data outside the selected time range and, for instance, visualize the data related to the queue $T_I(t')$ without the need to run again Algorithm \ref{alg:data}.

\subsubsection{Testcases Scatterplot}

Each $X_i$ is a matric of $|T_i(t)|$ rows in which each row is a vector of 65536 entries.

These raw numbers are raw to visualize. To handle this problem, we reduce the dimensionality of each vector $X_{i,j}$ from 65536 to 2, in order to be easily visualized in a scatterplot.

To do that, we chosen an algorithm that optimizes the conservation of local distances after the dimensionality reduction, {\em t-SNE} \cite{maaten2008visualizing}. The nature of this algorithm is random, it needs to process $X$ entirely in order to get new vectors that are meaningfully comparable.

We experimentally observed on a test dataset that a perplexity of 30 is good enough.

The user can select groups of nodes interactively to highlight properties in the other visualizations.

\subsubsection{Coverage Growth Plot}

$C$ can be visualized simply using a line plot with the X axis representing the domain, the time, and the Y axis the number of edges.

When a testcase is selected in the scatterplot or in the generations graph a vertical line appears at position $x$ where $x$ is the time in which the testcase was discovered.

\subsubsection{Interesting Testcases Plot}

This plot is used to visualize the evolution of the fuzzing algorithm in finding new testcases. The X axis represents time in seconds, the Y axis the number of new interesting testcases saved by the fuzzer in that second.
This information is directly contained in $T_i(t)$.

Here too, when a testcase is selected in the scatterplot or in the generations graph a vertical line appears at position $x$ where $x$ is the time in which the testcase was discovered.

\subsubsection{Generations Graph}

We visualize each Generations Graph $G_i$ combined with $I$. Given a fuzzer $F_j$ from the user, we highlight in graph $G_i$ each node associated with each testcase $T$ if $F_j \in I_i(T)$. In this way, the user can know if the evolution of $T_i(t)$ associated with the fuzzer $F_i$ is compatible with the selected $F_j$.

When a testcase is selected in the scatterplot, the border of the corresponding node in the graph is highlighted. The user can select additional nodes or deselect nodes selected from the scatterplot. The scatterplot selection is synchronized in both ways with the graph.

\subsection{Analyst Feedback}

The insights that an analyst can retrieve in order to choose or tune the fuzzers using the visualization are, but not limited to, the following:

\begin{itemize}
\item Looking just at the scatterplot, the user can select a subset of fuzzers that explore different program points if the points related to each fuzzer in the graphs are clustered;
\item Looking at the scatterplot and the coverage graph, the user can select a cluster of testcases that are similar and see the ability of a fuzzer in generating similar testcases in a small range of time. A fuzzer that discovers few points at a time and have them distributed for all the X axis of the coverage plot should be deprioritized;
\item Looking at the coverage graph, when there is a huge increment of the number of edges, the user can see if an outlier in the scatterplot was generated. This allows to isolate interesting testcases that improves a lot the coverage;
\item Selecting testcases in the graph, the user can see if the testcases are similar in the scatterplot in order to understand the ability of the mutator to generate similar or different derived inputs;
\item Selecting testcases in the graph and a fuzzer to cross-compare, the user can know if the coverage metric of the other fuzzer is sensitive enough to cover the selected testcases.
\end{itemize}

With this information, the security researcher should be able to choose and tune the set of fuzzers to avoid the saturation of the fuzzing campaign. This methodology is a first step towards a fuzzers debugger that is highly demanded by the security research community.

%\subsection{Choosing and Tuning Fuzzers}

\section{Implementation}

We created an \textsc{html} page comprised of 4 views and a filtering panel and all the components were created using the \textsc{D3.js} library.

\subsection{Testcases Scatterplot}

The scatterplot (Fig. \ref{fig:scatterplot}) has, as both axes, a linear scale where the points are color-coded to represent a category to help the analyst distinguish the similarity in the clusters highlighted and the presence of outliers.\par
By brushing over the scatterplot a routine is called to update the other 3 views with the highlighted elements by selecting the corresponding nodes in the Generation graph and inserting lines in both plots.\par
The user can also zoom in and out and both axes are scaled appropriately.

\begin{figure}[h]
  \includegraphics[scale=0.25]{img/scatterplot}
  \centering
  \caption{Testcases scatterplot}
  \label{fig:scatterplot}
\end{figure}

\subsection{Coverage Growth and Interesting Testcases Plots}

The Coverage graph (Fig. \ref{fig:coverage}) plots the growth over time of the number of covered edges, the Interesting Testcase graph (Fig. \ref{fig:inputs}) plots the number of new interesting test cases over time instead, for both the bottom axis is implemented as a linear scale, for the first graph the left axis is implemented as a logarithmic scale, for the latter a linear scale is used instead.\par
When data is selected on the scatterplot or graph vertical lines appear in both plots at the corresponding time having the stroke color matching the fuzzing technique.\par
We also implemented a pan and zoom functionality that keeps the lowest value pinned at the bottom.

\begin{figure}[h]
  \includegraphics[scale=0.25]{img/coverage}
  \centering
  \caption{Coverage growth plot}
  \label{fig:coverage}
  \includegraphics[scale=0.25]{img/inputs}
  \centering
  \caption{Interesting Testcases plot}
  \label{fig:inputs}
\end{figure}

\subsection{Generation Graph}
The Generation Graph (Fig. \ref{fig:tree})  is created as a hierarchical layout where each data point's value is displayed as a node label.\par
The user can zoom as well as pan over the entire view to have a better understanding of the data and when a node is selected in the other a routine is called to highlights the corresponding points in the scatterplot and insert lines in the other plots.
A mouseover on node lowlights all the nodes except the hovered nodes and their neighbor nodes and edges.

\begin{figure}[H]
  \includegraphics[scale=0.25]{img/tree}
  \centering
  \caption{Generation graph}
  \label{fig:tree}
\end{figure}

\subsection{Filtering Panel}
The user can filter the data shown an all the 4 views by time, with a range slider (Fig. \ref{fig:panel}) located at the bottom right of the page, and by category, by clicking on the category names directly on top of the slider, the filtering works by updating the existing graphs without redrawing.

\begin{figure}[h]
  \includegraphics[scale=0.25]{img/panel}
  \centering
  \caption{Filtering panel}
  \label{fig:panel}
\end{figure}

\section{Concluding Remarks}

{\sc FuzzSplore} brings a useful visualization-based method to retrieve insights from running fuzzers in a campaign.

It defines a long-term visual analytics feedback loop applied to fuzzing with a set of data retrieval and visualization techniques that can be easily extended in future works.

The information that a security researcher can collect using our approach can help in understanding the problem of saturation in fuzzing campaigns, a widely spread problem that is rarely addressed in academic literature.

We share {\sc FuzzSplore} as Free and Open Source Software at \url{https://github.com/andreafioraldi/FuzzSplore}.

\vspace{10mm}

\bibliographystyle{IEEEtran}
\bibliography{bibliography}

\end{document}

max_stars_repo_name: andreafioraldi/FuzzSplore

max_issues_repo_name: andreafioraldi/FuzzSplore

max_forks_repo_name: andreafioraldi/FuzzSplore


text:
\subsection{Gradient theorem}

In a scalar field, the line integral of the gradient field is the difference between the value of the scalar field at the start and end points.

This generalises the fundamental theorem of calclulus.

max_stars_repo_name: adamdboult/nodeHomePage

max_issues_repo_name: adamdboult/nodeHomePage

max_forks_repo_name: adamdboult/nodeHomePage