基于方向优化的快速2代Bandlet变换

1、fast 2g bandelet transform based on optimaldirection#li qimin, li hongjie*510152025303540(college of mechanical engineering chongqing university, chongqing 400030)abstract: construction of quadtree and selection of the best geometry direction (bgds) are the mosttime-consuming parts in 2g bandelet tr

2、ansform, and the result of original method is not the best. tosolve the problem, in this paper, a bgds method based on the advance and retreat method waspresented firstly; then the genetic algorithm for bgds was proposed; finally, these two methods werecombined to get better results. experiments sho

3、w that these three methods all have some advantagescompared with original method. furthermore, the original bottom-up quadtree algorithm was improvedto a top-down quadtree algorithm, which has some advantages in processing some special images. inthe ending of this paper, the application of improved

4、bandelet based on genetic algorithm waspresented, and the time complexity and space complexity of these algorithms were compared.keywords: 2g bandelet transform; selection of best geometry direction; construction of quadtree0 introductionthe effect of wavelet transform for low-dimensional signal is

5、good, but forhigh-dimensional signal, the wavelet transform has great limitations. for this reason, erwan lepennec and stephane mallat presented the conception of 1g bandelet transform 1. after that, in2005, peyre and mallat presented 2g bandelet transform theory 2. 1g bandelet transform is amethod

6、based on the edge of the image, which can adaptively track the geometric regular directionof the image 3. 2g bandelet transform inherits the advantages of 1g bandelet transform, and hasmore robustness and more efficient processing rules; it's also very easy to be achieved 4 .the steps of 2g band

7、elet transform are as follows:1) set threshold, perform the 2d wavelet transform, get the image 2d wavelet transformcoefficients.2) perform the bottom-up quad tree algorithm in the image sub-bands getting from wavelettransform; sample the geometry direction of the image, and perform the 1d reorderin

8、g for 2dwavelet coefficients of image; then perform the 1d wavelet transform for the wavelet coefficients;finally, using lagrangian multiplier method to obtain the optimal direction;3) the 1d wavelet coefficients getting by the optimal direction is the bandeletcoefficients, save them 5. the anisotro

9、py of bandelet coefficients has been greatly reduced.however, original bandelet transform algorithm is very time-consuming, and the result is notthe most accurate. in this paper, new algorithms for the selection of the best geometry directionand construction of quadtree were presented. experiments s

10、how that the running speed of newalgorithms has greatly been improved, and the effect are more accurate than the original method's.the steps of original method for selection of best geometry direction of image, which wereproposed by mallat and peyre, are as follows6:1) sample and calculate all p

11、ossible directions: divide circumferential angle with sameinterval into some directions;2) calculate the corresponding lagrangian function value of each sampling direction:calculate the warped haar transform; calculate the approximate error; calculate the lagrangianfunction value;foundations: 教育部高等学

12、校博士学科点科研基金(no.20090191120007)；国家自然科学基金(no.50905190)brief author introduction:李奇敏，(1976-)，男，副教授，主要从事计算机图形学和计算机辅助设计研究。e-mail: qim_li-1-455055603) compare lagrangian function value of all sampling direction, take the direction thatmakes the lagrangian function get the minimum as the optimal direction o

13、f image, then computethe bandelet coefficients. based on the idea, the matlab program of searching the optimaldirection of image was proposed by mallat and peyre 7.from the above description, it shows that, in order to get precise optimal direction, we needto compute all sampling direction, includin

14、g warped haar transform, calculation of approximateerror and lagrangian function value. for large image, the computation of the process is very large,and the result is not very accurate. it is not convenient to apply the algorithm to large image. inreference 7, it explained the basic concepts of ban

15、delet transform, but didn't support the fast 2gbandelet transform algorithm. so, we present some algorithms to achieve fast 2g bandelettransform.fig.1. flow chart of advance and retreat method1 finding the optimal direction based on advanceand retreat methodadvance and retreat method is a method

16、 to search the range of optimal solution, its idea is:firstly, determining an initial point t 0 0,+) (or t 0 t min , t max )and the initial step length-2-h0 > 0 ; then searching forward along the t axis positive direction, and getting a newpointt0 + h0 , if the value of target function is lower a

17、t the new point than it at the initial point, that65is（t 0 + h0）< (t 0 ) ; next, increasing the step length to search forward from the new point, ifthe target function's value at the new point is rising, that is（t0 + h0） (t0 ); then, regardingt0 as the initial point to search along the t axis

18、 negative direction. when we find the rising point oftarget function, stop searching, then we get a search range. this algorithm is called advance andretreat method 8; its steps are showed in the figure 1.7075this algorithm regards lagrangian function as the target function, and finds its minimum.se

19、arching an appropriate value t0 as the initial point, and then using the advance and retreatmethod to search two endpoints of search range; finally, finding the t0 that make the lagrangianfunction get the minimum in the search range, this value is the optimal direction. the search rangeis compressed

20、, and the running speed is improved. according to the above analysis, a method tofind the best geometry direction of images was presented based on advance and retreat method:1) in the whole search range, sample some points with larger interval, respectively2n (the number of sampling points can not b

21、e too much or too little, too much ortoo little all will affect running time), this paper we do n=64;2) respectively compute lagrangian function value at these sampling points, regard the point80859095100t3) reduce sampling interval, use advance and retreat method to search the endpoints(è1，

22、32; 2 ) of search range, that is the search range of best geometry direction;4) regard è1，è 2 as the search range of the best geometry direction, and then compute thelagrangian function value of each sampling direction, the sampling direction corresponded theminimum value is the optimal di

23、rection.this algorithm firstly samples some directions from the set of directions, determine thestarting point, and then search the optimal range of best geometry direction. this algorithmcompress the possible set of directions, then find the optimal direction in the optimal range. thisalgorithm'

24、;s running speed is faster because the search range is compressed, the unnecessarycalculation is avoided.2 finding the optimal direction based on geneticalgorithmin the genetic algorithm, the possible solutions of problem domain is regarded as theindividual of population or chromosomes, then convert

25、ing the target function value to the fitnessfunction value, using the size of fitness function value to evaluate the merits of individual, andfinally, simulating the process of the genetic law and natural evolution, operating the coding of thepossible solutions by genetic operation9. genetic operati

26、on include: selection, crossover andmutation. crossover is the main method to generate new individual, which determines the geneticalgorithm's global searching capability10. the mutation operator is the auxiliary method togenerate new individual, which determines the local searching ability of g

27、enetic algorithm 11.thebasic steps of genetic algorithm are as follows: (1) coding, (2) generating initial population, (3)constructing fitness function, (4) performing the genetic operations, (5) judging the convergenceof genetic algorithm by setting the genetic algebra or the difference between the

28、 two successive-3->t ，t ，tcalled 1that makes lagrangian function get the minimum as the starting point 0 ;fitness values12.105110the global optimization ability and convergence of genetic algorithm are better. if we applygenetic algorithm to search the optimal direction of image, the running spee

29、d will be greatlyimproved; at the same time the results are more accurate, because of the increasing of coding bits.genetic algorithm's coding methods mainly include binary, decimal, real number, etc13. takingthe decoding into account, this algorithm uses the binary coding, and regard the lagran

30、gianfunction value as the fitness function. in order to avoid the algorithm into the local optimalsolution, the algorithm doesn't limit the difference between two successive fitness values, but limitthe genetic algebra.2.1algorithm descriptionbased on the above analysis, a method about searching

31、 the optimal direction of image was115120125130135140presented in this paper based on genetic algorithm, the algorithm is as follows:1) code all sampling directions, set the coding bits of individual gene and the individualnumber of population; this paper uses 12 bits to code possible solutions, the

32、 individual number8to code direction (see figure 2, figure 3.).2) construction of fitness: use the reciprocal of lagrangian function value as the fitnessfunction, decode the coding of individual gene, and compute the corresponding lagrangianfunction value and fitness function value.3) according to t

33、he size of fitness function value, perform the selection, crossover andmutation operation;4) after finishing the genetic operation of required algebra, get the final population, decodethe corresponding gene and compute the corresponding fitness function value;5) find the maximum of the fitness funct

34、ion, the corresponding direction is the optimaldirection.genetic algorithm has good convergence and global optimization ability, it not only cangreatly improve the running speed, but also can improve the accuracy of results, thus the algorithmhas certain superiority.fig.2. direction coding(a)binary

35、coding of direction (b) binary convert into decimal (c) corresponding directionfig.3. the conversion of coding and direction3 comprehensive methodadvance and retreat method search the optimal direction by determining the initial point,searching the optimal range, thus reducing the running time and g

36、etting the optimal results;-4-is 2 . the more bits to code, the more accurate the results are. here is an example by using 3 bitsgenetic algorithm search the image's optimal direction by performing genetic operation for initialpopulation. if we regard the search range which is obtained from the

37、advance and retreat methodas the new solution space, and then using genetic algorithm to find optimal solution, so that we145can combine the advantages of both.3.1algorithm descriptionthe steps of comprehensive method are as follows:1) in the whole search range, sample some points with larger interv

38、al, respectively called.150155160165170175little all will affect running time),this paper we do n=64;2) respectively compute the lagrangian function value of these sampling points, regardingt3) reducing sampling interval, use advance and retreat method to search the endpointsè1，è 2 of sear

39、ch range, that is the search range of optimal direction;4) regard the search range in the step 3 as the solutions space, and then code the solutionsspace;5) construction of fitness function: use the reciprocal of lagrangian function value as thefitness function, decoding the coding of individual gen

40、e, and computing the fitness function value.6) according to the size of fitness function value, perform the selection, crossover andmutation operation;7) after finishing the genetic operation of required algebra, get the final population, decodethe corresponding gene and compute the corresponding fi

41、tness function value;8) search the maximum of the fitness function, the corresponding direction is the optimaldirection.comprehensive method combines the advantages of advance and retreat method and geneticalgorithm, which not only can improve the speed, but also can improve the accuracy of the resu

42、lts.4 the comparison of several algorithms ofsearching optimal directionaccording to the above description, using matlab-2007b program, performing theprogram in the computer of amd athlon (tm) processor, graphics card ati ra-deon hd 4350,basic frequency is 2.7ghz and memory 2gb. optimal direction, c

43、orresponding lagrangianfunction value and running time of optimal algorithms and original algorithm were compared inthe following tables. the unit of optimal direction is radian (rad), the unit of running time issecond (s), and l is the minimum of t-he lagrangian function. using lena, barb, fishboat

44、 andpeppers of 16×16、 32×32 、64×64、128×128 pixels to test. the results are showed in the table1,table2, table3, table4.180185-5-t1，t 2，t n (the number of sampling points cannot be too much or too little, too much or toothe point that make lagrangian function get the minimum as th

45、e initial point 0 ;tab.1 the results of original algorithm190tab. 2 the results of advance and retreat methodpixels16×16 32×32 64×64 128×128imagelena d 1.4423 1.5074 1.5426 1.5568l 43.5 1473.9 5875.8 23431.0t 0.0253 0.0931 1.7635 13.5513barb d 0.1285 1.2689 0.0648 0.0299l 50.6 18

46、5.0 728.3 2990.7t 0.0302 0.2541 1.8952 38.7261fishboat d 0.0740 0.0513 0.0253 0.0299l 38.4 133.1 549.8 2010.9t 0.0236 0.2565 2.8630 45.0134peppers d 1.4968 0.0425 0.0211 0.0105l 45.4 193.3 741.8 2928t 0.0152 0.1995 3.2846 49.6235tab. 3 the results of genetic algorithmtab. 4 the results of comprehens

47、ive method195-6-pixelsimage16×1632×3264×64128×128lenad2.14371.51090.12591.5568l101360.65510.323431t0.02790.20090.927918.1081barbd1.93421.26900.06440.0299l49.3184.32727.72990.7t0.02580.26651.718116.5926fishboatd3.06770.05140.02530.0300l36.5132.5549.82010.2t0.02360.21130.713931.017

48、0peppersd1.49603.09963.12050.0107l44.8190.7739.22975.4t0.03230.11352.771723.7829pixelsimage16×1632×3264×64128×128lenad0.00700.21900.63891.5568l7.681345.35463.023431.0t0.02860.11300.447752.6349barbd1.69551.26930.06450.0299l46.1184.3727.72990.7t0.01710.22230.750833.5099fishboatd0.0

49、7530.05120.02510.0298l37.8132.5541.12010.2t0.02310.21881.495644.9217peppersd1.78110.06161.69210.0104l27.542.2104.92908.2t0.01870.04241.684126.8259pixelsimage16×1632×3264×64128×128lenad1.44231.50741.54261.5568l43.51473.95875.823431.0t0.03200.29164.139267.7605barbd0.12851.26890.064

50、80.0299l50.6185.0728.32990.7t0.03260.35623.584051.7669fishboatd0.07400.05130.02530.0299l38.4133.1549.82010.9t0.02880.25663.577052.0140peppersd1.49680.04250.02110.0105l45.4193.3741.82928t0.02870.25293.585152.6865from the above tables, we can see that the above methods all have some advantagescompared

51、 with the original algorithm. the running speed of advance and retreat method hasimproved compared with the original algorithm, and the effect is similar; genetic algorithm notonly can improve the speed, but also can obtain the same, even more accurate results;200comprehensive method can improve the

52、 image processing speed, and the results are moreaccurate.4.1the comparison of reconstructionthe results are showed in the figure 4. from the figure 4, we can see that the effect of thereconstruction image by genetic algorithm and comprehensive method is better than of the original205210method. firstly, because the optimal direction getting through the two methods is more accurate,the reconstruction image of genetic algorithm and comprehensive method is smoother. secondly,the two algorithms'