Abstract: Presently, stereo matching algorithms are almost in purpose of pursuing high matching precision, the whole time spent in algorithms are too long. In this study, we proposed a stereo matching algorithm based on aligning genomic sequence, according to the comparability on the theory of aligning genomic sequences and stereo matching algorithm. Firstly, pixels in each epipolar on stereo image were transformed into the form of genomic sequences and then used calculation method of getting score matrix by comparison of genomic sequence to establish two-dimensional disparity space images. At last, we finally get disparity using searching optimization strategy in aligning genomic sequences to do global optimization. The experimental results show that the whole time of this method is greatly reduced and matching quality is still good.
INTRODUCTION
Stereo vision technology which is the hotspot (Chang et al., 2006; Zigh and Belbachir, 2010) of research attracts attentions of many scholar, is widely applied to fields of aviation and biomaterials. Stereo matching is the core technique of stereo vision, so the quality and efficiency of stereo matching determined effects of stereo vision technique in practical application (Asadpour and Golnadi, 2010; Barrois et al., 2010). According to the difference of matching primitive, stereo vision can be divided into phase matching, feature matching and local matching. Phase matching has the problem of phase singularity and phase wrap (He et al., 2005). Feature matching can only gain sparse disparity space and it need subsequent interpolation management (Perez et al., 2010). Local matching can gain dense disparity space, but it takes longer time (Saitoh, 2007). With constantly improving of hardware in recent years, Local matching gradually became the mainstream. To further improve the quality of the local matching algorithm, researchers brought in various of optimization algorithms (Xi et al., 2006; Lang et al., 2010), such as Dynamic Programming (DP), Graph Cut (GC), Belief Propagation (BP), etc. Web data (Scharstein and Szeliski, 2002) from http://vision.middlebury.edu/stereo/ established by Scharstein and Szeliski (2002) show that the output results of local matching algorithm based on global optimization. These results are close to the true disparity image.
The improvement of matching quality lead to lower speed of algorithm execution, Contradiction between matching quality and matching time restricts the further development of stereo vision. According to statistics of Scharstein and Szeliski (2002), the effect of the local matching mainly depends on which algorithm was used during the optimization. In general, the more complex the algorithm, the longer the optimization time, the better matching quality (Iqbal et al., 2010). Years of research shows that it is difficult to establish a method with higher matching quality and shorter matching time, from stereoscopy field itself to find technical breakthrough (Xu et al., 2010).
So, we have to turn our eyes to other fields. In this study, we proposed a stereo matching algorithm based on aligning genomic sequence, according to the comparability on the theory of aligning genomic sequences and stereo matching algorithm. The essence of both is to search best matching primitive under matching rule restrictions. Path searching method using in aligning genomic sequences is faster than global optimization algorithm using in stereo matching. If this method can be used in global optimization of stereo matching, the whole time of stereo matching maybe decrease.
THE COMPARABILITY ON THE THEORY OF ALIGNING GENOMIC SEQUENCES AND STEREO MATCHING ALGORITHM
Aligning genomic sequences is the research hotspot in biomaterials field with the characteristic of principle simple, higher speed and parallel computation.
Aligning genomic sequences and stereo matching belongs to different field, but have greatly similarity on theory. The essence is to search best matching primitive under matching rule restrictions. Stereo matching is referred to search the best matching of each pixel in correspondence epipolar. Aligning genomic sequences is to find similarities of two genomic sequences.
Further study found that the length of the genomic sequence corresponds to the length of epipolar in stereo images. Score matrix get from comparison of genomic sequence corresponds to two-dimensional disparity stereo images in stereo matching, searching optimization strategy in comparison of genomic sequence corresponds to global optimization strategy in stereo matching.
In short, it is possibility to bring the aligning genomic sequences technology into the field of stereo vision, so it will full play the feature of high execution speed and improve the real-time of stereo matching algorithm.
STEREO MATCHING ALGORITHM BASED ON ALIGNING GENOMIC SEQUENCE
The whole design idea that bring the thought of aligning genomic sequences into stereo matching is as follows: firstly, to do genomic sequence on pixels of the same name epipolar of stereo matching, and then to get score matrix of the genomic sequences established by the same name epipolar, lastly, to attain disparity of corresponding pixels between the same name epipolar using optimization strategy in comparison of genomic sequence.
Detailed realization is as follows:
Pixels in each epipolar on stereo image transformed into the form of genomic sequences: Genomic sequences are made up by four alkaline bases A, T, C, G. A genomic sequence can be regarded as character string composed by four characters. Similarly, aligning genomic sequences can be regarded as aligning two or more character string.
Generally, we do matching work on the same name epipolar in order to reduce execution time of stereo matching, when we bring the thought of aligning genomic sequences into stereo matching, firstly, we should consider how to change pixels of same name epipolar to the form of genomic sequence, that is to say turn them to character string.
In image processing, gray scale of pixels generally mapped to integer 0 to 255. We assumed the same name epipolar in two images composed by five pixels. The left are 12, 15, 14, 14, 15 and the right are 15, 14, 13, 14, 15. After doing genomic sequence on pixels the same name epipolar, they are changed into the character string form of “12”, “15”, “14”, “14”, “15” and “15”, “14”, “13”, “ 14”, “15”.
Using score matrix by comparison of genomic sequence to establish two-dimensional disparity space images: The method that attain score matrix by comparison of genomic sequence is as follows:
s stands for the first array for comparison, t stands for the second array. S (I, j) shows the score of best array ,that ith character in array s and jth character in array t, in score matrix. g stands for interval score, equals -1. p (I, j) shows the score of matching character ,that ith character in array s and jth character in array t. When right matching, the score plus 2, or minus 2. Counting function in the following points:
| (1) |
Border initial score in the following points:
| (2) |
Using this method, do comparison between pixel characters in two epipolar, two-dimensional disparity space images generated as shown in Fig. 1.
Here, a general process of computation of score matrix in aligning genomic sequence is showed. “x” stands for some character. Arabic numerals stands for a score.
Searching optimizing path and disparity identified on two-dimensional disparity space images: The path is shown in Fig. 2. In the Fig. 2, the line with black arrow shows the best path, if the line along the diagonal direction, it indicated right corresponding pixels. If the line along horizontal direction, we insert a blank(“—”) in the corresponding place in right epipolar pixel array.
| Fig. 1: | Computation of score matrix |
| Fig. 2: | Searching optimal path on score matrix |
If the line along vertical direction, we insert a blank(“—”) in the corresponding place in right epipolar pixel array. Then, new pixel array as follows:
| • | Left epipolar: “12” ,“15” ,“14”, “—” ,“14” , “15”. |
| • | Right epipolar: “—”, “15”, “14”, “13”, “14”, “15”. |
Then, according to the number of blanks, disparity of corresponding pixel can be computed. As shown above. There is a pixel disparity between two black 15.
After the above three links, we can confirm the disparity of corresponding pixel between a pair of same name epipolar. It can be applied to all images and get disparity stereo image.
Here, searching process of the optimal path is showed on the score matrix. Certainly, this score matrix also corresponds to disparity space image, this searching process also corresponds to global optimization of stereo matching.
EXPERIMENTAL RESULTS
First experiment: To test the validity of the method proposed in this study, we take Japan synthetic stereo images tuskuba as experimental data. The epipolar of stereo image has been adjusted and no noise. It is the international test matching algorithm standard image. Left image, right image and true disparity image of tuskuba, as shown in Fig. 3. The resolution of original image is 384*288.
Computer used in experiment is configured with 1.7G two-core CPU, memory 1G. In experiment we take tuskuba stereo image as input to do stereo matching respectively based on Graph Cut (GC), Belief Propagation(BP), Dynamic Programming(DP) and aligning genomic sequences proposed in this study.
GC, BP, DP are different global optimization strategy used in stereo matching. According to statistics of Scharstein and Szeliski (2002) GC and BP have a good matching precision. But matching time of them is too long. DP has a good split the difference of matching precision and matching time in all of the former stereo matching algorithm. Because GC, BP and DP are typical stereo matching algorithm, so we take them as a comparison with the method in this study.
Here, disparity images of four different algorithms are showed. They are Graph-Cut (GC), Belief Propagation (BP), Dynamic Programming (DP) and stereo matching algorithm based on aligning genomic sequences. From them, matching quality of different algorithms is clear at a glanceFrom the matching quality point, the matching effects of four methods are good. Method based on aligning genomic sequences and dynamic programming method proposed in the paper exist stripe flaw. That is because dynamic programming backdating method is used in global search optimization on score matrix.
Matching time of four methods is listed in Table 1. From the matching time point, the proposed methods are less time-consuming, just 0.5 sec, the time of GC, belief propagation and dynamic programming is 1/6 , 1/4, 1/2, respectively.
Second experiment: To test the robustness of the method proposed in this study, we adopt Gones stereo image as experimental data from the website. The epipolar of image has been adjusted and no noise. It is standard image used to test the international matching algorithm. Left image, right image and true disparity image of Gones, are shown in Fig. 5. The resolution of original image is 450*375.
To compare with first experiment, we still do stereo matching respectively based on Graph Cut (GC), Belief Propagation (BP), Dynamic Programming (DP) and aligning genomic sequences proposed in this study.
| Fig. 3: | Tuskuba synthetic stereo image |
| Fig. 4: | Experimental results |
| Fig. 5: | Cones synthetic image |
| Fig. 6: | Experiment result |
| Table 1: | Comparison of performance in four groups experiment |
| Table 2: | Comparison of performance in four groups experiment |
The final matching results are shown in Fig. 6, matching time is shown in Table 2.
Here, disparity images of four different algorithms are showed. They are Graph-Cut (GC), Belief Propagation (BP), Dynamic Programming (DP) and stereo matching algorithm based on aligning genomic sequences. From them, matching quality of different algorithms is clear at a glance from Fig. 6 and Table 2, the accordant conclusion of first experiment can be attained. That is, stereo matching method based on genomic sequences has characteristic of execution faster which largely reduced time under without taking from matching quality.
DISCUSSION
In order to evaluate other stereo matching methods and the method proposed in this study, six points were refined to discuss by later researchers.
| • | From the matching quality point, the matching effects of four methods compared in this study are good. And graph-cut method is the best |
| • | The matching effects of graph-cut method is best, but the time of this method is too long. Because graph-cut theory was used in global optimization |
| • | If consider both matching effects and matching time, stereo matching based on aligning genomic sequences proposed in this study is the best |
| • | Stripe flaw appear in both stereo matching based on aligning genomic sequences and dynamic programming method, because there is similarity in theory between the both methods |
| • | There are 7 searching directions in dynamic programming method and only 3 searching directions in our method in this study. So stereo matching based on aligning genomic sequences is very fast |
| • | More references can be considered between stereo matching and aligning genomic sequences |
CONCLUSIONS
In the study, through analyzing the comparability on the theory of aligning genomic sequences and stereo matching, we ensure the possibility to bring the aligning genomic sequences technology in stereo matching. The concrete realization is as follows: firstly, to do genomic sequence on the same-name epipolar of stereo matching, and then to get branch matrix by establishing genomic sequences using the same name epipolar after being genomic sequences, lastly, to attain parallax of corresponding pixels between the same name epipolar using optimization strategy in comparison of genomic sequence. The experiment results show that stereo matching method based on genomic sequences got high quality parallax in short time and laid the foundation for improving the real-time of stereo vision.
ACKNOWLEDGMENTS
This research was supported by Open Fund Supported by State Key Laboratory of Robotics and System (HIT) with grant number (SKLRS2009MS05, 2009-2011) conducted by People’s Republic of China, Youth Science Research Fund Project of Harbin University of Science and Technology with grant number (2009YF011, 2010-2011) conducted by People’s Republic of China, The Harbin Special Fund of Technological Innovation Talent with grant number (2010RFQXG039, 2010-2012) conducted by People’s Republic of China, The Scientific and Technological Project of Education Department of Heilongjiang Province with grant number (11541046, 2009-2011) conducted by People’s Republic of China and The Postdoctoral Sustentation Fund of Heilongjiang Province with postdoctoral number (69449, 2009-2011) conducted by People’s Republic of China.