Digital Media Computing
Assignment 1: Video Segmentation

-------------------------------------------------

HAND IN DATE: 31st October 2010
WEIGHTAGE: 25 Marks
-------------------------------------------------

Student Name Name | Student ID | Robert Johnson | 102122913 |

Table of Contents User Guide 2 Video Selection 2 Video Playback and Segmentation Execution 2 First Implementation 2 Second Implementation 3 Third Implementation 4 First Implementation 6 Part A: 50% Split 6 Part B: Custom User Percentile 7 Second Implementation 7 Part A: Uniform N-Splits 7 Part B: Histogram Equalization 8 Part C: Average Frames 8 Third Implementation 9 Order of processing 10 Problems Encountered 10

User Guide
All three implementations can be accessed by opening the index.html page.
The implementations have been tested to be work on Firefox 15 with any resolution above 1024x768. Due to the extensive use of HTML5 canvas, several legacy browsers may not be able to run the web page successfully.
Video Selection
Once the page has been loaded, the user has an option to select from 3 different videos. Two of which are stored locally. Please ensure to place both file ‘tracker.ogg’ and ‘video.ogg’ in the same folder as the index page. The user can click on either button 1, 2, or 3 to swap between different videos to experiment on. The video can be seen when user clicks on the play/pause button.
Video Playback and Segmentation Execution
It is important to note that the user may not see any changes on screen for each button press as long as the video is not being played. Each button acts as a toggle to switch between various implementations and modes. The top half of the screen occupies the area for the set of buttons and the status indicator.
From here the user may see what modes are toggled and which implementation he/she is currently on.

In order to observe the results, the user must first click on the play/pause button located near to the Original video header.
First Implementation
The first implementation contains 2 parts, 50% Split and Custom Percentile. The result can be observed on the right hand side with the title Segmented and it can be compared with the original image on the left hand side with the title Original. If the user has toggled the histogram to Shown then each image will be accompanied with a histogram of that image. This is displayed just underneath the image. If the user wishes to restore the results back to an empty state then the user can press the button Clear located just next to the Segmented title. Do note however that if the video is still playing then this action is overridden. There are two modes where the user can choose from; HSV and RGB. By default, HSV is already selected. This represents the type of color segmentation the user would like to apply to the image. The inputs entered for Frames and Splits in the third row are only applicable in the second and third implementation in accordance with the assignment question.
The first part can be executed by pressing the button labeled 50% Split.
The second part can be executed by first entering the desired threshold within the range of 0 to 100 and proceeding to press the button labeled % Split to observe the desired result.
Second Implementation
The second implementation comprises of a single part which is Histogram Equalisation. This button can be clicked on without having to clear the results produced from the first implementation. While the video is still playing, the user is free to switch back and forth between the two implementations to see real time changes to the output. The user does not need to pause, stop, or refresh the video to swap between different modes and implementations.
Before playing the video, please ensure that all parameters have been selected, primarily the Frames and Splits.
The frames indicate how many frames to base the average LUT on.
The splits indicate the number of uniform splits to be made on individual RGB channels.
The part can be executed by pressing the button labeled Histogram Equalisation.

Third Implementation
The third implementation varies very little from the previous implementation. It also is made up of a single part which is ROI (Region of Interest) Histogram Equalisation. Likewise, this button can be clicked on without having to clear the results produced from the first implementation. While the video is still playing, the user is free to switch back and forth between the two implementations to see real time changes to the output. The user does not need to pause, stop, or refresh the video to swap between different modes and implementations.
In addition to the second part, the user can define rectangular-shaped ROIs on the original video on the left hand side to specify the region on which the LUT will be based on. This can be achieved by holding the cursor down from the desired starting point and releasing the cursor at the desired end point. The ROI will be automatically replaced upon each subsequent region selection to reflect the changes.
The part can be executed by pressing the button labeled Histogram Equalisation.

First Implementation
The purpose of the first implementation is to segment a video with 256-bit colors into that with just 2-bit (8) colors by dividing each RGB channel into two. This was achieved by setting each channel to either 0 or 255 depending on its original value. The value can be determined by comparing whether the original value is larger or equal to the threshold or less. It is set to 255 if the value is larger or 0 if it is lesser. By reducing the range of colors to just 8, the resulting video frame will allow the user to see the grouping of colors more clearly.
In addition to RGB splitting, this implementation allowed for an additional processing to filter video frames based on a separate color space, HSL (Hue Saturation Value). Since objects in a video do not change hue but rather their saturation and level of intensity due to lighting conditions and shadow formations. The added advantage of using HSL is that the resulting image will not lose essential color information by segmenting individual RGB channels separately allowing the color to be preserved. This in turn will result with a better grouping of colors to distinguish various objects within the frame. The Value in HSV will be used to split and reassign the pixel data. This will segment the frame into two parts, pixels with vibrant colors and pixels with dull colors. Instead of reassigning the Value, the Saturation is readjusted to either 0 or 100. This is done to increase the richness of interesting colors while lowering the intensity of dull colors to improve the results when the frame is later processed further.
Part A: 50% Split
If the mode selected is HSV then the frame will first be segmented according to its HSV value before being segmented based on its RGB value. Otherwise it will be segmented only via RGB value while ignoring its HSV value.
The hue ranges from 0 – 360, saturation from 0 – 100, and the value from 0 – 100. Therefore, the two values to be the reassigning values for Saturation are the two extremes 0 and 100. The comparison is carried out based on the value of Value at 50% which corresponds to 50. Any pixels with value greater or equal 50 will have its saturation reassigned to 100 while anything lower will have the value of 0.
The first part of the first implementation divided the channel equally to 50%. This meant that the threshold for deciding which value to assign is set at 50%, if values were lower than 127 will get a new value of 0 whereas anything above 127 or equal will be assigned a new value of 255. The resulting image will show a balanced division of colors because each pixel will change to the nearest 8 color it is most similar to.
Part B: Custom User Percentile
Part B differs slightly than the previous part in that the user is allowed to choose any threshold he so wishes. Presented with an input box and a button, the user can choose from a range of 0 to 100 the desired threshold. The larger the threshold, the darker the range of colors will be. This is because anything larger than the threshold will be assigned the value 255 whereas anything lower will be assigned the value of 0. Since the value represents the intensity of the color, a large threshold will cause an overall of low color intensity i.e. darker image. The opposite is also true for a lower threshold will cause the image to be much lighter.
The point where the HSL Value is split will also use this threshold value. A lower threshold would mean a higher percentage of dull colors being included with interesting colors and vice versa. Depending on the source image, readjusting the percentile to go higher or lower can result in a better segmentation.
Second Implementation
The second implementation involves converting the original image of 256-bit colors to that of any N-bit colors the user specifies from a range of 2 to 10 bits. The higher the bit the color has, the larger the amount of color variants there can be. With a larger number of colors, there will be more details retained relative to only 8 colors in the first implementation. Each channel will be split into N parts. A custom function had to be made to cater for the dynamic number of parts to split the color channels by. This function allows for greater flexibility and reusability at the cost of added computational time and resources as opposed to the rudimentary and hard coded if else statement used in the first implementation. One of the reasons for the added cost is because a preprocessing function is also required before this function can be used. Two arrays are filled with points to split the channel at and the value for each of the N parts of the channel. This information will be accessed in a for loop for each pixel to determine the new value to be designated to it.
Part A: Uniform N-Splits
The first part was interpreted as a dynamic number of splits that will cause each channel to have thresholds that will cause fair distribution for each part among all range of a particular channel. Since there are N parts to be split out of 100%, the threshold increment has been calculated to be at (100%/N) and the new value to be assigned would be (100%/N-1). Since N is fixed to be from 2 and above, the program will not encounter division by zero error. However for good measure, appropriate error handling has been applied. An example of this is when user would like to split the channels into 4 uniform splits. By applying the formula stated earlier, it can be determined that the splitting interval and the part increment is at 64 and ~85 respectively.
From this data, the splitting array is populated with the values [256,192,128,64,0] and the reassigning values [256,171,86,0]. For each parts as i, the upper limit will be split[i], the lower limit at split[i+1]. The new value is accessed in the second assign array at assign[i]. These values are used as parameters in a comparison to find the new value for that channel. If original value is within the limit bound, replace with value from assign array otherwise leave the original value as it is.
Part B: Histogram Equalization
The second and final part of the second implementation involves an additional step before it is segmented into 2N colors. In accordance with the question, the intensity of each color channel must be equalized such that each color intensity range will receive equal amount of colors. An image with a bland contrast will be converted to have a larger dynamic range with high contrast. A lookup table is first generated by assigning a value for each color intensity, store the value of cumulative sum of the color intensities thus far multiplied with the ratio of maximum value of 255 divided with the number of pixels (width x height).
The same method also holds true for the case of HSV histogram equalizations albeit minor variable changes. As opposed to RGB histograms, only the histogram of V from HSV will need to be equalized to provide accurate automated contrast adjustments. The maximum value also differs to 100 instead of 255 to reflect the maximum value of V.
Once the iteration is complete, there will be a new lookup table generated which can map the old pixels to its new pixels that will result with even histogram distribution. Once the frame is equalized, it goes through the function mentioned in part A to map the equalized pixels into their corresponding color groups.
Part C: Average Frames
This implementation also allows for the selection of average N frames to base the equalized histogram on. As opposed to calculating a new lookup table for each pixel, a new lookup table will only be calculated for every Nth frames with the combined histogram of these frames averaged before it is equalized. By adopting this approach, it is possible to save on computational costs and from personal observation, the frames produce less noise and are less prone to flickers and random stutters which means the data produced is of higher quality. The difference between equalizing an average of N frames and averaging of N equalized frames is in the ordering of the two functions; average and equalisation.
From my understanding, these two statements can yield distinct results from one another. Equalising an average of N frames signifies that the mean average of these frames is first calculated to form an average frame which will later have its histogram equalized. On the other hand however, averaging of N equalized frames will have the actions in reverse order. Each N frames will have its histogram equalized and later on these frames can be combined and averaged to find the average of these frames.
Taking into consideration the complexity of equalization function relative to average operand, it would be more expensive to compute average of N equalized frames rather than equalizing average of N frames. The former will require N function calls to equalization whereas the latter would require just one.
Third Implementation
The third implementation builds upon the use of histogram equalisations from the second implementation with added functionality that allows for dynamic allocation of ROI (Region of Interest) to formulate the equalization lookup table to be applied to the entire frame.
The user can define the ROI by dragging the cursor from one point to another to form a bounding box which will be the region in which its pixels are the values that will determine the contrast level for the entire image.
The use of ROI is particularly useful when the background colors outnumbers the foreground colors which causes the use of histogram equalization function without an ROI to produce a result that will ensure the background image has good dynamic range while compromising the visibility of the foreground object. This is because the way histogram equalization works is it tries to even the amount of intensities of the entire range to form a cumulative histogram that is relatively linear. The foreground object may only belong to a small subset of the entire range thus the algorithm will equalize irrelevant background colors. By using an ROI, the user can select the region where he/she wants more contrast. A case in point is for video 1, by selecting the region primarily occupied by the face, the outcome will cause a result that will produce more contrast and details within that region.
Order of processing
From the results of my experiments, it can be seen that applying the process of ROI histogram equalization on a video frame after it has been segmented would be better in the sense of performance. Since the input frame contains limited colors, it will be more affordable to compute which will lead to improved performance. On the other hand, the output frame after process will not be as accurate because much of the information that is beneficial for ROI histogram equalization has been lost due to the reduction in colors and simplification of image. The result produced is not that is initially desired which defeats the purpose of using ROI histogram equalization of specifying regions to extract more dynamic range of contrast. Thus it can be said that applying the opposite to the former, process ROI histogram equalization before the frame is segmented is much better.
Problems Encountered
This assignment was not without its hurdles and roadblocks which hindered progression in exchange for locating, debugging and fixing errors. Due to the nature of the JavaScript language and HTML5, errors are not displayed and the remainder of the page will still continue to function as though the errors are non-existent. The errors are only spotted when testing functionalities to check for compliance to the assignment question. Placing alert() functions at key positions were extensively used to pinpoint root of the problem.
Most errors that occurred are mostly common mistakes such as wrong variable names used, variables being re-declared, wrong values and wrong data flow. These errors are subsequently fixed when pinpointed. Another issue that is much more evident now as opposed to the first assignment was in performance. Due to the use of a video as opposed to a stationary image, there can be hundreds of frames for a single video. Each of these frames will have to be processed individually and iteratively. The initial code did not have optimized code and some calculations were unnecessarily executed during each frame. This caused the frames per second (FPS) to drop significantly to the point that the entire browser locks up. This highlighted the importance of code and query optimization and encourages reuse of data not needed for each frame.
When reallocating the 256-bit colors into their respective color groups, it used to make a function call for each frame to the function that contained a nested loop to determine the output value of the input value. Since the boundaries and split points for part N remains constant so long as variable N is not changed then it is unnecessary to keep calling this function. The solution to this was found by constructing a look up table only when the variable N changes. The difference it made to the performance was night and day. Similar optimizations were also made throughout the code to reuse variables that aren’t changed as often.
There are however performance issues unavoidable as of yet. Performance severely drops when the histogram is set to be displayed. Since histograms have to be calculated on a per frame basis, data reuse is no longer an option. Considerations were made to improve the performance of HSV to RGB to HSV translations but it turned out, creating a LUT of size 256 * 256 * 256 would seem to be a much costlier option than converting back and forth between the two types.
An issue still unresolved despite various attempts at finding a solution is the ability to access pixel data of video / image elements that reside on a different website. Although the video loads up just fine on both the Original and Segmented sections, the canvas that supposed to display segmented frames only mirrors the original video. As it turns out, for security reasons it has been decided by HTML5’s governing body W3C that video / image elements originating from locations other than your domain will have its canvas labeled ‘tainted’ and access to the pixel data is subsequently denied.