{'fraction_non_alphanumeric': 0.026645669291338582, 'fraction_numerical': 0.010078740157480314, 'mean_word_length': 4.690322580645161, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Implementation of Text Hiding in Medical Images based on Graph Coloring for Android Devices

Medical images are representations of highly vulnerable digital images and useful objects that help diagnose a patient. However, it is not easy to maintain the authenticity of a medical image because there are many ways that it can be manipulated. Therefore, several methods have been developed to protect the authenticity of medical images. One way is to add a watermark onto the medical images. However, digital image watermarking techniques are usually widely implemented using software running on a computer. In this paper, the authors built a system to hide the text on medical images using an Android device. The system consists of an embedding and extracting process. In the embedding process, the method used is vector quantization and graph coloring based on a Genetic Algorithm. The test result shows that the scheme has good imperceptibility and a fast enough time consumption to be implemented on an Android device.


Introduction
The digital image has many uses in life, one of which is in the field of medicine. Medical images are representations of highly vulnerable digital images and useful objects that help diagnose a patient's condition. Medical devices can be used to obtain these medical images, one of which is the Ultrasound image or via Ultrasonography (USG) [1] . The authenticity of the medical image is very important because it will have an impact on the diagnosis of a patient's disease. However, it is not easy to retain the authenticity of the medical image because it can be easily manipulated in many ways, one of which is with the help of software [1] . Therefore, medical images must have copyright information embedded on it.
To maintain the authenticity of medical images, the researchers developed a method for entering information onto images known as image watermarking. Digital image watermarking is a technique of inserting certain information onto a digital image. This inserted information is called a watermark. This watermark can take the form of text, image, audio, or even video [2]. At present, digital image watermarking techniques have been widely implemented using software running on a computer. With the growing development of mobile technology nowadays, especially Android OS, it is possible that digital watermarking be done using an Android device. This is because Android devices can easily be used at any time or place.
In this paper, the authors built a system to hide the text on medical images using an Android device. The system consists of an embedding and extracting process. In the embedding process, the method used is vector quantization and graph coloring based on a Genetic Algorithm (GA). The testing was done to determine the value of Peak Signal to Noise Ratio (PSNR) between the watermarked medical images and original medical images. In addition to testing imperceptibility, the watermarked medical images were also tested for robustness via determination of the  [3] . The author also tested the accuracy of the extracted text before the watermarked medical image was manipulated.

. Related works
Many studies have developed methods for digital image watermarking. Adiwijaya et al. [4] implemented steganography to embed medical records onto medical images. The research itself provided a method that leveraged on a data hiding scheme using Vector Quantization and graph coloring based on evolutionary algorithms, i.e. the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO). The result of the research showed that GA provided better performance than PSO in terms of computational time, but both algorithms yielded approximately the same performance in terms of hiding capacity.
Adiwijaya et al. [1] discussed a scheme for a reversible watermark using a modified LSB and Huffman compression to detect and recover a manipulated medical image. The testing results showed that the system was capable of detecting an attack with up to 100% accuracy and could also perform recovery with recovery rate of up to 98% accuracy for some attacks.
Ari Muzakir [5] implemented watermarking using a Least Significant Bit (LSB) technique on an Android device. The research utilized an existing RGB channel in the image and then converted each channel to 8 bits. After that, every character of the existing message was converted into 8 bits based on ASCII code. The results of the simulations carried out using an Android smartphone showed that the LSB watermarking technique was not able to be seen by the naked human eye, meaning that there was no significant difference in the image of the original files with the images that had been watermarked.
Mohammad Farukh Hashmi et al. [6] proposed real-time copyright protection and implementation of image and video processing on Android and embedded platforms. In the system, pre-specified copyright information was embedded directly on pictures as they were taken. The system also implemented real-time video processing such as Canny Edge Detection, Dilation, and Successive frame subtraction on Android and embedded platforms. The results showed that the quality of the watermarked image had a PSNR value exceeding the minimum standard of PSNR.
Raffaele Pizzolante et al. [7] developed a tool for portable devices based on Android OS, that permits the addition of a visible or invisible watermark to images. The implemented algorithm for the visible watermark converted the string of the watermark into a bitmap image, and then merged the bitmap obtained with the input image in a random position. Meanwhile, the algorithm used for the invisible watermark was a modified version of labeling techniques. Testing was done to determine the robustness of the watermarked image under JPEG compression. The testing result showed that there was a percentage error obtained from the extraction process when the compression factor of the JPEG algorithm was low (i.e. 50% and 30%); however, it was still possible to easily distinguish the string of the watermark.

. System design
Before proceeding with the discussion on system design, the following section describes the characteristics of the data used in this paper. The data used was 8-bit grayscale ultrasound images with 1024×1024 pixel resolution in JPEG format, making up to as many as 15 images. The data was obtained from Dr. Wahidin Sudiro Husodo hospital. Figure 1 shows an example of the data used in this paper. The text data used is a string.  Figure 1. Text data used in this study. Overall, the system was designed as part of two schemes; the first is the embedding scheme, which aims to insert messages into medical images. In this scheme, there are two inputs, which are the medical records of the patient and the medical images with the resulting output of medical images that contain secret data. To increase hiding capacity, secret text data was compressed using a Huffman Algorithm [4] . The flowchart of the embedding scheme is described in figure 2.

Embedding process
The embedding process includes processes such as ROI and RONI separation, codebook generation, graph construction, graph coloring, graph refining, and quantization. Figure 3 illustrates the embedding process.
The first step in the embedding process is ROI and RONI separation. To avoid misdiagnosis, medical images were divided into two parts: Region of Interest (ROI) and Region of Non-Interest (RONI). ROI is a sensitive part in a medical image, therefore the text cannot be inserted into the ROI section because it can change the shape of the original medical image [8] . To divide the ROI and RONI in a medical image, cropping was performed. Figures 4-6 below show the division of RONI and ROI in a medical image.
After ROI and RONI separation, a process called codebook generation was performed. The codebook is a set of codewords [9]. To build a codebook, the image was divided into several blocks, where each block is called a training vector. The training vectors then undergo a clustering process [8] . In this paper, the algorithm used to build the codebook is the Linde Buzo Gray (LBG) algorithm [10] .
The next stage is graph construction. A graph was constructed by adding a vertex v for each codeword cw in the codebook.  [4] .      After the graph is created, the next process is graph coloring. The graph was colored with a number of colors called color_number. In this paper, each color was represented by an integer, such that the colors = {0,1, 2, …, color_number-1} [8] . The value of the color_number must satisfy 2 x where x is the natural number. Each color corresponds with a x-bits secret message. For example, if color_number = 8, then color = {0,1,2,3,4,5,6,7} = {000,001,010,011,100,101,110,111}. Since graph coloring is a NP-complete problem and the Genetic Algorithm provides better performance than Particle Swarm Optimization [4] , this paper utilized the Genetic Algorithm [11] to color the graph.
The next process is refining the graph. This was done to reduce any failure during the quantization process [4] . The step for refining the graph was done for every vertex v present in the graph, utilizing a Breadth First Search to determine whether it was within a certain range from v or bfs_tresh from v in which all colors could be found [4] . If there is a color that cannot be found, v is removed from the graph.
The last step in the embedding process is final quantization. In the first step, RONI was divided into 4×4 blocks; the quantization process started from the first block. Next, in the iteration step, the most similar codeword cw to the current block was determined using Euclidean Distance. Then, the vertex v from the graph that corresponds to codeword cw was determined. If v was found, from secret bit data, b bit was taken as x, where 2 = color_number. If v was not found, the codeword cw that corresponds with v would be the output. In the next step, Breadth First Search was used for vertex v', which is connected with v and a satisfactory color (v') = x and the scheme search codeword cw' corresponding with vertex v', where state cw' is the output. If the current block is the last block, the quantization process is ended. If the current block is not the last block, the next block is moved as the current block and the iteration step is initiated.

Extracting process
The second scheme is extraction. In this scheme, the required inputs are codebooks and the colored graph, which was created during the embedding process. In the first step, RONI was divided into 4x4 blocks. The extracting process starts from the first block. Next, in the iteration step, the most similar codeword cw to the current block was found using Euclidean Distance. Then, vertex v from the graph that corresponds to codeword cw was determined. If v is found, color(v) will be the secret bit data [12] . If the current block is the last block, the extracting process is ended. If the current block is not the last block, the next block is moved as the current block and the iteration step is initiated.

Result and discussion
In this paper, the author conducted 3 tests to determine the quality of imperceptibility, accuracy of the extracted text, and robustness. The system was made in the form of an application that runs on an Android platform. The device used for testing ran on an Android 7.0 (Nougat) operating system, with 3GB RAM capacity, and Octa-core 1.6 GHz Cortex-A53 CPU. The parameters used in this test are a codebook with size 128, color_number with 8 colors, adj_tresh with range value from 20-60, and bfs_tresh with a value of 150. The metric used to test robustness was BER. First, the watermarked RONI was extracted without attack, to determine the accuracy of the extracted text. Then, the watermarked RONI was attacked using sharpening, Gaussian noise, median filter, and salt and pepper noise attacks, to determine its robustness. All types of attacks were implemented using OpenCV for Android libraries [13] . Based on table 1, the average PSNR value of all medical images was found to exceed the standard PSNR of 30 dB [3] . The value of PSNR exceeded the minimum standard because of the embedding scheme was based on vector quantization. Vector quantization is an image compression method that manipulates the fact that, in a large block of similar images [12] , the watermarked medical image will not be very different from the original medical image. In addition to imperceptibility testing, the author also included the running time of each complicated process. From the codebook-generating process, the average running time was 20.83 seconds; this time will increase with an increase in codebook size. For graph coloring, average running time was 35.52 seconds. However, when testing the sample_8 image, the time required for coloring the graph was 137,98 seconds, while the time for graph coloring sample_15 was only 0.62 seconds. This is because the GA algorithm sometimes showed very good performance, so the initialization of color on the graph and the color created from the initialization would be directly valid. Then, the last step was determining the running time during the process of quantization, where average running time was found to be 0.79 seconds. The time required was short because during the quantization process, all secret data bits had been inserted into the picture. However, if the current image block is not the last image block, then the quantization process will be stopped. The running time will then increase with increased length of secret bit data. Based on table 2, the average accuracy was found to be 100%. This indicates that the text extracted from all the watermarked medical images is the same as the original text. This can be obtained when the watermarked RONI has not been manipulated. Since the codebook and graph used during the extraction process were the same as those used during the embedding process, the extracted text was able to achieve 100% accuracy. The average extracting time was 3.57 seconds. This average time is fast because, during extraction, when the length of secret bit data that had been extracted is the same as the length of original secret bit data, the extraction process will be stopped. The extracting time will increase with increased length of secret bit data. Based on table 3, all the executed attacks resulted in average BER values of above 50%. This is because all types of attacks were done to manipulate the image, and this would change the pixel values that exist in the image. Therefore, during the extraction process, an error will emerge in the second step when the search process codeword is most similar to the block of image to be extracted.

Conclusions
According to the results and discussion, it can be concluded that the embedding scheme has good imperceptibility because all the watermarked medical images yielded an average PSNR value above the minimum standard. This embedding scheme also showed good accuracy with the  8 extracted text given that the watermarked medical images had not been manipulated. However, if the watermarked medical images have been manipulated, this embedding scheme would produce an average BER value of above 50%. This indicates that the embedding scheme has weak robustness. In terms of security, the text hidden in the watermarked medical images using this embedding scheme could not be retrieved without first having knowledge of the colored graph. Based on the contributions of this study, the author has shown that the embedding scheme is suitable to implement on Android devices because it has good imperceptibility and a fast enough time consumption. In future work, the author will improve the data insertion method into images that have good imperceptibility and robustness as well as that can be implemented in mobile devices.