The linearization procedure of the input image was followed by the reflectance assignment and the segmentation processes. The former provided the image components with a characterizing triplet and the latter used that information to gather identical representatives into image regions. The following stage of the algorithm attempts to identify the reflectance triplets assigned to these regions with a reflectance triplet that is stored in the environment model. These color matches could then suggest correspondence between image regions and environment surfaces. During the implementation of this task several difficulties occurred. Besides eliminating the effect of varying lighting conditions, an appropriate measurement system had to be defined to produce comparable distance indicators in the whole volume of the reflectance cube. The operations of the color identification process can be followed on the diagram of Figure 21.

4.1 Color Identification Algorithms

After obtaining the reflectance triplets of a specified number of regions from the input image, these measures had to be classified. It had to be determined what existing color name would best describe the recovered surface information. The classification process worked with a very specific domain of color values. This collection merely contained reflectance values that were represented in any one of the locale descriptions of the environment model [Figure 20]. To find the matching category of a particular reflectance value, it was compared to the pool of model reflectance measures [Step 1, Figure 21] and was identified with its closest matching representative. It was assigned a color label accordingly. This step of the algorithm implicitly formulated a strong assumption. As each region was paired with a model reflectance triplet, it was supposed that all the regions on the input image formed part of the agent’s registered surrounding. In other words, it was assumed that the agent knew each input region and its characteristics were stored in the environment model. Although this assumption facilitated the search task considerably by reducing the size of the color-term pool that had to be investigated, it also introduced a serious weakness to the color identification procedure. An unknown surface could completely offset and modify the nature of color classification for the whole input and that could result in a set of false identifications. A more detailed description about the nature and the disadvantages of that assumption can be found at the end of the current chapter.

In the majority of the cases, the image measures did not match perfectly the values that are stored in the model collection. That was because the lighting conditions were purposely not controlled in the experiments. The linearization procedure, the very first procedure of the whole image analysis, applied intensity values that were obtained from a particular image containing the 3-step gray card [Figure 19]. There, the gray calibration surface was exposed to a particular combination of illumination effects. The image correction was carried out according to this setting. It attempted to eliminate distortions introduced by the color camera, but it was not responsible for nullifying the effects of varying lighting conditions. In this way, there usually remained some alterations on the input that had to be accounted for. That was the major task of the color identification transforms.

According to another implicit assumption used by the algorithm, there was only one light source illuminating each image scene. Therefore, locating the closest neighboring triplet of all the input reflectances in the model was not the correct method for classifying a scene. In case in the lighting settings were different on the input image and on the one including the gray card, it was an appropriate shift mechanism [Step 2, Figure 21], acting on all the image reflectance measures, that should well approximate the searched values. The goal of the color identification transformation analyzer was to find the function (multiplier triplet) whose outcome would best fit, simultaneously, all the reflectance values obtained for the image. Then it was the set of these matched constant reflectance values that the algorithm used for place localization purposes.

4.1.1 Guide to Evaluation Tables

Figure 22,23 and 24 provide a summary of several of the evaluation methods that are described below. The table entries state how many reflectance values were misjudged out of the total number of input measures. These numbers, though, do not demonstrate the complete nature of the operations. In case of failure, they do not show the rate of misjudgment. For example, there are entries in the table that have only 1/5 (one out of five) mismatch. Without any additional information this result could be evaluated as a fairly good one. However, that is not necessarily true. The indicated mistakes could either be very serious or acceptable. A "serious" mistake, for instance, would be naming the color of the wall (vanilla) as brown. A less serious error was often declared if the algorithm output a close guess and/or the impreciseness could be explained by factors that the algorithm did not account for. These unexpected phenomena could be, for instance, reflections or shadows. The most common fault of this type was the misidentification of shadowed wall regions and of door colors. To a human observer the color of the side doors and office doors on the 4^th floor of the Laboratory building seem to be well-distinguishable, however, the algorithm often mistook them for one of the other. To help the reader in evaluating the performance of the different methods, some of the entries are colored. Green numbers refer to severely false identifications; red ones refer to excellent and purple to very good ones.
 

4.2 Transformation Evaluator Options

What would be the best way to define a "good" transform? Several experiments were carried out to grasp the notion of the closest match following a shifting procedure. Different aspects/values relating to the transform were registered. It was tested which one would be the most reliable to predict the nature of the transform outcome. Some of these properties were Euclidean distance, normalized Euclidean distance, magnitude of the transform multipliers and the ratio of the pre- and post-transform distances.

4.2.1 Euclidean Distance

The first evaluator used was the Euclidean distance measurement. It simply evaluated how far away two three-dimensional points were from each other. After an initial region (it was selected to be either the largest of size or the "darkest" of color) was associated with one of the standard reflectance descriptors, the same transform that had been required in its case was applied to all the other indicators gained from the input image. Then the distances of the new values were calculated from their closest reflectance constants in the model and summed for the whole group of regions on the input image [Step 3, Figure 21]. This procedure was repeated several times with different initial reflectance value. Eventually, the transform with the smallest total sum of differences was selected to be the most adequate one [Step 4, Figure 21]. The first column of Figure 24 displays the results of one of the experiment series. Three of the images were analyzed correctly, but the rest of the results were not satisfactory, especially the outcomes for the Office2, Office3 and Main2 images.

4.2.2 Variance

Other experiments were carried out using the value of variances of the matches instead of just the Euclidean distances. Variance was considered as an evaluator because, in theory, a final match with lower variances in the distances would be preferred versus a match with higher ones. In other words, a match with consistently small differences should be more adequate than one with some perfect and some distant matches. Using this evaluator the average of distances was essential to be analyzed as well. Low variance for a far average match was just as bad as a highly varying one. For example, the transformation of a set of light reflectance values into a set of dark ones could be compared to a transform that matches only light values to the input. It should be the second transform that is selected even if there is an identification difference in its case that is greater than what would normally be accepted. That decision implies that no extremely drastic differences were expected in the lighting effects. All the input images were obtained under conditions that allowed for clear visibility, the surfaces were neither in complete darkness nor in blinding brightness. The obtained results are listed in [Figure 24, column 2 and 5]. Although in this specific case, the evaluator did not perform worse than the distance formula, in general, it could not produce better results than the distance operator. For this reason, in the more advanced transforms, the variance evaluator was not utilized.

4.2.3 "Ratio"

A third descriptor, which had been quite successful in the identification process, was one that made a comparison between the total sum of distances before and after the selected transform. After a set of constant reflectance values were identified from the model, based upon Euclidean distance measurements, the confidence of the matches was determined with respect to them. The absolute value of the ratio of the total sum of distances post and prior to the application of the shifting multipliers taken from the same set of selected environment model constants should be as close to unity as possible. This rule also assumed that the changes of illumination magnitudes on the inputs were not extreme. That is to say, it was preferred to have a transform that did not apply large multipliers to the input reflectance measures in order to find a match. Using too large multipliers would locate the corresponding constants of the input in the opposite end of the reflectance cube, which was not desired by the assumption. Column 3 and 6 on Figure 22 indicate that this evaluator managed to correctly analyze images that were mismatched by its predecessors. (E.g.: Po1.clr, Side3.clr, and Office2.clr)

4.3 Modifications to the Algorithm

4.3.1 Modifying the Number of Iterations (1)

While working with the above-described evaluators, it was discovered/ realized that simply measuring Euclidean distances in the reflectance cube could be decisive. In a set of experiments, an image containing mainly high reflectance values was consistently identified with dark characterizing triplets. Such a misidentification was especially common in case of evaluators that examined all the possible matches of the initial region into the environment model before selecting the best transform. See Figure 22, column 5, where the evaluator managed to produce only one perfect match. In this case, matching all the regions with darker triplets proved to be more "beneficial" than staying in the lighter, opposite corner of the reflectance cube. That phenomenon often happened when analyzing the different shades of vanilla-color on the "cans.clr" input image [Figure 22].

The reason for that dark preference could be found in the current nature of the reflectance space. When one closely analyzes the collection of constant reflectance values in the model [Figure 20], it is clearly visible that the space in the close vicinity of (0, 0, 0) is much more populated than around the value (1, 1, 1). Therefore, distances of the same numerical value in the darker end are more significant than those in the lighter corner. To reduce the probability of false matches of this nature, the algorithm put a constraint on the number of constant reflectance measures to which the initial region was compared and according to which multiplier triplets were generated. This iteration number was experimentally determined to be 4 out of 14.

4.3.2 Modifying the Number of Iterations (2)

Further experiments demonstrated that there could also be a difference between the identification accuracy depending on the lightness value of the initially examined region. That feature could be related to the one explained above. The same distance measured in the darker corner of the cube was more significant than towards the lighter corner. If this fact was not taken into consideration then the confidence values attached to the selected matches did not provide an intuitive indicator of the correctness of the operation. To eliminate that disabling factor from the algorithm, a new strategy further limited the number of iterations executed during the color identification procedure based upon the reflectance triplet initially analyzed. When the starting image region belonged to the "darker" corner of the reflectance cube, more transform options were to be considered as opposed to the case when the region was "lighter". The value of these iterations was determined to be 3 and 6 out of a collection of 14 measures.

Although the previously mentioned modifications increased the number of correct matches of the color-identification operators, they still could not eliminate a lot of false identifications. One explanation lied again in the distance measurements. Although the number of iterations became limited, so the initial matches did not fall too far away from each other, the distance measurements were still biased towards the darker matches. The following alteration attacked specifically that aspect of the algorithm.

4.3.3 Normalized Euclidean Distance

Instead of merely calculating the Euclidean distance between the examined reflectance triplets, it was the Euclidean distance divided by the norm of the reflectance measure residing in the model that was applied in the algorithm. This normalization modification improved the color identification procedure significantly. Compare Figure 24 column 3 to Figure 22 column 2 and Figure 24 column 1 to Figure 22 column 4. The most prominent progress appeared in case of the evaluator that used the largest image region as the initial one and measured Euclidean distances. From three perfect and three very good matches it improved to produce five perfect and two very good matches. The results of this transform are boldfaced on Figure 22, column 4.

Some of the above-mentioned modifications relied heavily on the current nature of the environment model. Hence, this strictly specific approach might not be very effective in general environmental scenarios. However, the analysis of the model played a very important role in improving the performance of the identification process of Susan B.

As the new distance measurement was introduced all the experiments were repeated. The idea of using a limited number of iterations still seemed to be essential. However, varying the iteration number according to the lightness of the initially analyzed region reduced in significance. In this way the normalized distance measure was incorporated in both of the main evaluators (Euclidean distance and ratio of distances) to determine the confidence level of an identification transform. Columns 1-4 in Figure 22 demonstrate the outcome of these experiments. The best performance on the test set of 14 images could be associated with the transform in boldface letters. That procedure applied a distance evaluator, the largest image region as a main base of comparison and four iterations to carry out its operations. In total, it achieved five perfect and two very good associations.

4.4 The Initially Analyzed Reflectance

As the evaluation sets demonstrate it on Figure 22 and 24, there were several experiments, from the beginning, that studied the importance of the initially analyzed image region. For these purposes, two main approaches were established. One version selected a particular image region out of the examined set. It was either the largest of size or the darkest of color. In the former case, it was assumed that the biggest surface would provide essential information about the location of the agent. In case of the latter, the accuracy of the color identification transforms was expected. It was proposed that the confidence measure for the operations could increase if the initial correct association was defined in the dark region (where the distances are more significant) of the reflectance cube.

The other option was more general. Instead of selecting a certain image region, it analyzed the transform with respect to all the members of the examined collection. This option eliminated all assumptions about the importance of individual regions and gave equal opportunity to all the examined regions to lead to the best-fitting collective match.

The general solution did not perform satisfactorily. No matter which evaluator (the distance or the ratio) was applied with it, it committed several mistakes. As it was mentioned earlier, its worst match occurred when it identified vanilla-colored light image regions with low reflectance ones (e.g.: Figure 22, Main.clr).

The experiments with the darkest region could produce good results mainly if the majority of the examined regions were dark. A precise match in the darker corner of the reflectance cube was more important than that in the lighter corner where only a few number of constants were located. In general, however, this selection did not perform better than the series selecting the largest region. (Compare columns 1-4, Figure 22) What is more, when the darkest region had the smallest size among the examined image regions, its application often led to serious failures. The explanation of this phenomenon is that relatively small dark areas could very often be associated with reflections, unknown objects or noise on the input images. Consequently, the identification based on its reflectance value could completely mislead the match.

The latter observation above resulted in some adjustments in the number of image regions originally obtained from the input image.

4.5 Number of Examined Regions

After the linearization and reflectance assignment processes, the region analysis algorithm grouped together neighboring pixels with identical/highly similar reflectance measures. In the following, only a few of them were selected from there to assist in the color identification and the place localization tasks. These representative regions were the largest ones on the image.

Originally, the number of examined regions was set for five. This value was selected as it still allowed for quite a reasonable computation speed and it also seemed to provide a sufficient amount of information about the main regions appearing on the image. However, because of frequent occurrence of noise and reflections on the inputs, whose size was relatively small compared to that of other main regions, some flexibility was introduced. Based upon the input image, the number of examined entities decreases if the size of a region falls below a threshold. The threshold value (T = 1500 pixels) was determined by pure experimentation. 

4.6 Identification of Confidence Measures

After running any of the above-described color identification algorithms, it was not possible to assign appropriate confidence measures to the outputs. This was because the first match in the transform was always assigned 100% confidence and the transform multiplier values were determined according to this first reflectance. If the initial match was not close enough, the whole assignment was offset. The confidence values, though, were not able to indicate that. Neither the ratio test of the distance post and prior to the transformations nor the Euclidean distance measures could provide good descriptors of the color assignment correctness. The correctness information, however, would be essential in the further search for the agent’s location. It would allow for accepting or discarding certain surfaces, when analyzing the environment, and would allow for estimating how firm the algorithm’s final answer was. In order to gain additional information about the true confidence level of the transforms, two different evaluators were examined simultaneously.

4.6.1 Simultaneous Double Matching

Out of the normalized transforms listed in columns 1, 2, 3, 4 of Figure 22, two were selected for the simultaneous calculation task. One was the transform described in column four and its auxiliary was the one located in column two. They were assigned to work together as both of them had a fairly high individual match rate. In case a failure occurred in correctly classifying a reflectance triplet they seemed to well supplement each other. In the succeeding discussion, the transform with the smallest distance evaluator is referred to as Transform 1 and the other is Transform 2.

The following modification was applied to the algorithm to consider both of the transfers. In case the two functions did not produce the same outcome for a surface, the model reflectance value assigned to that region was reevaluated. A similar sequence of calculations was applied as described above, but after the first round it was only the image regions that were not assigned 1.00 confidence (i.e.: the two algorithms did not agree on their classification label) whose value was reconsidered. After that, all the identically matched reflectance values were applied as a basis for calculating transaction multipliers, and the sum of total distances was calculated for each new function. The output with the smallest total difference provided the new assignments. The results of this evaluator are also listed on Figure 22 under the "Recalculated outcomes" keyword. This new combination produced five perfect matches and four very good ones, which constituted the best outcome that had been examined up to that point. The additional recalculation step did not take place if the reflectance of the largest image region was assigned identical classification. That step would either just repeat the calculations that had been completed in the first run or would change the whole nature of the transform that originally started out (in both Transform 1 and Transform 2) with analyzing the reflectance measures of the largest image region.

There was also a danger in relying on the two color identification methods. If there was a disagreement in the color classification task, there was no possible way to know which assignment was in fact the right one. There were two possibilities that could be followed from such a state. The image regions whose reflectances were differently evaluated by the two descriptors could be completely eliminated from the search. Or a confidence value could be assigned to the identification of the image region based upon the distance of the two different output values. As the first version had the potential of losing even correct information about the image regions, the code followed heuristics similar to that of the later suggestion. If the matches agreed the confidence value was 100%. If they disagreed, the confidence measures were determined by computing how close the two guesses of the participating transforms were to each other. (For instance, vanilla and light brown are located 0.565 units away from each other which is 32% of the total maximum distance in the reflectance space. Reflectance values can be found on Figure 20.) Two sub-cases were differentiated. If the confidence of the match fell below 75%, the region was dropped from the set to be analyzed in the environment model. If, however, that value exceeded 75%, the region was kept. Because of a better general performance of Transform 1 on its own, if there was a disagreement, it was always the value suggested by it that was registered by the algorithm for further reference.

Although Transform 1 and Transform 2 proved to be working well together (column 8, Figure 22), some good matches were also lost. In case one of the transforms produced a good result and the other one disagreed, the label was recalculated. Experiments showed that new value lied, in most cases, in-between the previous outcomes instead of remaining with one of the original solutions.

4.7 Limitation on "Initial" Regions

A final modification to the currently used algorithm that proved to be promising considered the actual reflectance values of the initial region of the operation. By closely analyzing the numerical values of the multipliers and the transformed triplets, it became clearly visible that extremely low reflectance measures were not adequate for the initial comparison role. They did not convey a sufficient amount of information about the described surface reflectance. When any of the components of the reflectance triplet was below 0.1, the transform multipliers had to become extremely huge to allow a match with one of the model colors. If the multiplier was too huge then lighter surfaces on the image were assigned reflectance values that exceed 1.0, the maximum possible value. The evaluation of these operations had to be eliminated from the algorithm. This problem was approached in two different ways. One introduced a procedure that would test the reflectance values of the initially analyzed image region itself. If any of the components of the triplet fell below 0.1, the image region was rejected the role to serve as the main comparison value. The other function introduced a less strict rule. It analyzed the reflectance values not before but after the transforms. If at that point any of the reflectance components exceeded 1.0, the transform was not considered by the algorithm as a possible option. Experiments showed that the results produced by the two different algorithms were quite similar. Compare column 2 and 4 of Figure 23. While the more restrictive approach had six perfect and two very good matches, the other operator managed to perform five perfect identifications and three very good ones. The evaluator of column 2 performed slightly better than that of column 4.

One interesting remark considering the new evaluator has to be mentioned. When comparing the performance of the procedure applying the new restriction on the initial region’s reflectance with the original version, the improvement did not seem to be outstanding. What is more, in one case, for example, wall regions were assigned olive green values by the new procedure (Main3.clr). This decision would normally be considered as a serious mistake. However, looking at the original input explains the false judgement. Some of the wall regions that were recognized by the algorithm were in a shadow or were exposed to inter-reflections [Figure 10-11]. These phenomena were not encountered for in the algorithm. That is why the new transform could not identify them. So how was it possible that the previous operator did pick the correct vanilla color for the wall segments even with these distortions? The explanation is the following. The initially analyzed dark area (with a reflectance component below 0.1) produced large transform multipliers. The shadowed wall regions, that had reduced reflectance measures compared to the ones without distortions, could still be matched with their original color "vanilla", as the multipliers all allowed for large differences between the pre and post-transform values. Since in the reflectance space, the light corner contains only the vanilla color, the shadowed regions could still be matched with their correct pairs.

This advantage of the former analysis was too model-dependent and the project had assumed no distorting shadows or reflections on the input images. Hence, the new modifications were kept and they replaced the old algorithm. The confidence value of the operations was still measured by the double evaluation of the transforms. As the smallest distance evaluator still performed better than the pre- /post-distance comparison, a higher weight was assigned to its values in case of a mismatch between the two outcomes.

4.8 Misidentification or Unknown Object?

Due to the assumptions formed by the current analysis, there is a serious problem that could not be addressed. As it was mentioned above, the algorithm implicitly assumed that each of the regions obtained from the input image represented a region that could be located in the environment model and that no aberrations were introduced by shadows or reflections. These limitations discarded the possibility of even small changes in the environment (for instance, flyers on the bulletin board of vivid colors or modifying the location of benches in the hallway). In reality, however, the environment is constantly changing, so the assumptions weakened the algorithm significantly. Currently, there is no way for the algorithm to tell whether the match could be improved by discarding one region and then reevaluating the input. This feature could be implemented in the future. However, the danger of discarding too many regions might be high. As the number of analyzed regions decreases, the probability of finding a good transform increases (as fewer and fewer number of regions have to match correctly at the same time). This might lead to having merely very general single regions (wall, door) for the location search, which would not provide enough information. Also as the number of regions is decreasing it becomes more difficult to make a judgement about the correctness of the matches. In the extreme case, there is only one region to be analyzed. There would be no possible way to judge the confidence value of the different color transform operations, as the first match is always declared to be 100% correct.

4.9 Number of Colors in the Locale Model

A difficult question that emerged while experimenting with the color identification transforms addresses the number of different constant reflectance triplets that should be stored in the environment model. The two extreme situations would be the following. In the specific case, there would be a different color assigned to each individual type of surface in the model. In the general one, however, similar surfaces (e.g.: doors, bookshelves) would be assigned exactly the same color. In the former case the identification algorithm would have to be extremely accurate. As this would be the only step differentiating between the environment surfaces, almost no error could be affordable. In the opposite case, the color transform would have to be only accurate enough to find some general color categories (for example: light and dark brown, green and black). Then it would be the task of a further operator to examine the possibility of any of the surfaces defined by the recognized color to occur on the input and be located in the environment.

This thesis project applied the latter mentioned scheme. It had two major reasons. First of all, a perfectly stable color transform has not been identified yet and hence it was essential to have an identification confidence check associated to each step. Secondly, the locale semantic net contained a lot of location information that could be used for advanced heuristics in the localization procedure to narrow down the set of matched surfaces. The current version of the code applied a moderately reduced color assignment set in which there were fourteen constant reflectance triplets stored for nineteen different types of surfaces [Figure 20].